Instead, we jump back to the most recent variable (condition) taking part in the conflict set of P4 –
in this case P2. By doing so, we are avoiding considering other alternatives at P3, and thus avoiding one of the inefficiencies of the standard backward search. It is easy to see that such backjumping is sound since P3 is not causing the failure at P4 and thus re-assigning it won't avert the failure.

Continuing along, whenever the search backtracks to a condition c, the backtrack conflict is absorbed into the current conflict set of c. In our example, we absorb P1; P2; P4 into the conflict set of P2, which is currently P2 (making P1; P2 ; P4 the new conflict set of P2). We now assign A11, the only remaining value, to P2. Next we try to assign P3 and find that its only value A7 is mutex with A11. Thus, we set conflict set of P3 to be P3; P2 and backtrack with this conflict set. When the backtracking reaches P2, this conflict set is absorbed into the current conflict set of P2 (as described earlier), giving rise to P1; P2 ; P3; P4 as the current combined failure reason for P2. This step illustrates how the conflict set of a condition is incrementally expanded to collect the reasons for failure of the various possible values of the condition.

At this point, P2 has no further choices, so we backtrack over P2 with its current conflict set, P1; P2; P3 ; P4 . At P1, we first absorb the conflict set P1; P2; P3; P4 into P1's current conflict set, and then re-initiate backtracking since P1 has no further choices.

Now, we have reached the end of the current level (k ). Any backtracking over P1 must involve undoing assignments of the conditions at the kth level. Before we do that however, we do two steps: memoization and regression.

## 4.1 Memoization

Before we backtrack over the first assigned variable at a given level, we store the conflict set of that variable as a memo at that level. We store the conflict set P1; P2; P3; P4 of P1 as a memo at this level. Notice that the memo we store is shorter (and thus more general) than the one stored by the normal Graphplan, as we do not include P5 and P6, which did not have anything to do with the failure7

## 4.2 Regression

Before we backtrack out of level k to level k, we need to convert the conflict set of (the first assigned variable in) level k so that it refers to the conditions in level k. This conversion process involves regressing the conflict set over the actions selected at the kth level (Kambhampati, 1998). In essence, the regression step computes the (smallest) set of conditions (variables) at the kth level whose supporting actions spawned (activated, in DCSP terms) the conditions (variables)
in the conflict set at level k . In the current case, our conflict set is P1 ; P2; P3; P4 . We can see that P2, P3 are required because of the condition G1 at level k, and the condition P4 is required because of the condition G2.

In the case of condition P1, both G1 and G4 are responsible for it, as both their supporting actions needed P1. In such cases we have two heuristics for computing the regression: (1) Prefer choices that help the conflict set to regress to a smaller set of conditions (2) If we still have a choice between multiple conditions at level k, we pick the one that has been assigned earlier. The motivation for the first rule is to keep the failure explanations as compact (and thus as general) as possible,