essentially be seen as adapting conflict-directed backjumping strategy (Prosser, 1993), and generalizing it to work with dynamic constraint satisfaction problems.

The algorithm is shown in pseudo-code form in Figure 4. It contains two mutually recursive procedures find-plan and assign-goals. The former is called once for each level of the planning-graph. It then calls assign-goals to assign values to all the required conditions at that level. assign-goals picks a condition, selects a value for it, and recursively calls itself with the remaining conditions. When it is invoked with empty set of conditions to be assigned, it calls find-plan to initiate the search at the next (previous) level.

In order to illustrate how EBL/DDB capabilities are added, let's retrace the previous example, and pick up at the point where we are about to assign P4 at level k , having assigned P1; P2 and P3. When we try to assign the value A8 to P4, we violate the mutex constraint between A6 and A8.

An explanation of failure for a search node is a set of constraints from which F alse can be derived.

The complete explanation for this failure can thus be stated as:

$$\begin{array}{l l l l l l l l l l l}{{P_{2}}}&{{}}&{{A_{6}}}&{{}}&{{P_{4}}}&{{}}&{{A_{8}}}&{{}}&{{P_{2}}}&{{}}&{{A_{6}}}&{{}}&{{P_{4}}}&{{}}&{{A_{8}}}\end{array}$$

Of this, the part P2 A6 P4 A8 can be stripped from the explanation since the mutual exclusion relation will hold as long as we are solving this particular problem with these particular actions. Further, we can take a cue from the conflict directed backjumping algorithm (Prosser, 1993), and represent the remaining explanation compactly in terms of "conflict sets." Specifically, whenever the search reaches a condition c (and is about to find an assignment for it), its conflict set is initialized as c . Whenever one of the possible assignments to c is inconsistent (mutually exclusive) with the current assignment of a previous variable c 0
, we add c 0 to the conflict set of c. In the current example, we start with P4 as the conflict set of P4, and expand it by adding P2 after we find that A8 cannot be assigned to P4 because of the choice of A6 to support P2. Informally, the conflict set representation can be seen as an incrementally maintained (partial) explanation of failure, indicating that there is a conflict between the current value of P2 and one of the possible values of P4 (Kambhampati, 1998).

We now consider the second possible value of P4, viz., A9, and find that it is mutually exclusive with A5 which is currently supporting P1. Following our practice, we add P1 to the conflict set of P4. At this point, there are no further choices for P4, and so we backtrack from P4, passing the conflict set of P4, viz., P1; P2; P4 as the reason for its failure. In essence, the conflict set is a shorthand notation for the following complete failure explanation (Kambhampati, 1998):6

$P_{4}$$A_{8}$$P_{4}$$A_{9}$$P_{1}$$A_{5}$$P_{4}$$A_{9}$$P_{2}$$A_{6}$$P_{1}$$A_{8}$$P_{1}$$A_{5}$$P_{2}$$A_{6}$

It is worth noting at this point that when P4 is revisited in the future with different assignments to the preceding variables, its conflict set will be re-initialized to P4 before considering any assignments to it.

The first advantage of the conflict set is that it allows a transparent way of supporting dependency directed backtracking (Kambhampati, 1998). In the current example, having failed to assign P4, we have to start backtracking. We do not need to do this in a chronological fashion however.