

![0_image_0.png](0_image_0.png)

with the other subgoals. If we remember P1; P2; P3 ; P4 as the memo as against P1    P6 , the remembered memo would be more general, and would have a much better chance of being useful in the future.

After the memo is stored, the backtracking continues into level k - once again in a chronological fashion, trying to reassign G4; G3; G2 and G1 in that order. Here we see the **third** indication of inefficiency caused by chronological backtracking - G3 really has no role in the failure we encountered in assigning P3 and P4 - since it only spawns the condition P5 at level k . Yet, the backtracking scheme of Graphplan considers reassigning G3. A somewhat more subtle point is that reassigning G4 is not going to avert the failure either. Although G4 requires P1 one of the conditions taking part in the failure, P1 is also required by G1 and unless G1 gets reassigned, considering further assignments to G4 is not going to avert the failure.

For this example, we continue backtracking over G2 and G1 too, since they too have no alternative supports, and finally memoize G1; G2; G3; G4 at this level. At this point the backward search fails, and Graphplan extends the planning graph by another level before re-initiating the backward search on the extended graph.

## 4. Improving Backward Search With Ebl And Ddb

I will now describe how Graphplan's backward search can be augmented with full fledged EBL
and DDB capabilities to eliminate the inefficiencies pointed out in the previous section. Informally, EBL/DDB strategies involve explanation of failures at leaf nodes, and regression and propagation of leaf node failure explanations to compute interior node failure explanations, along the lines described in (Kambhampati, 1998). The specific extensions I propose to the backward search can