and the motivation for the second rule is to support deeper dependency directed backtracking. It is important to note that these heuristics are aimed at improving the performance of the EBL/DDB
and do not affect the soundness and completeness of the approach.

In the current example, the first of these rules applies, since P1 is already required by G1, which is also requiring P2 and P3. Even if this was not the case (i.e., G1 only required P1), we still would have selected G1 over G4 as the regression of P1, since G1 was assigned earlier in the search.

The result of regressing P1 ; P2; P3; P4 over the actions at kth level is thus G1; G2 . We start backtracking at level k with this as the conflict set. We jump back to G2 right away, since it is the most recent variable named in the conflict set. This avoids the inefficiency of re-considering the choices at G3 and G4, as done by the normal backward search. At G2, the backtrack conflict set is absorbed, and the backtracking continues since there are no other choices. Same procedure is repeated at G1. At this point, we are once again at the end of a level–and we memoize G1; G2 as the memo at level k. Since there are no other levels to backtrack to, Graphplan is called on to extend the planning-graph by one more level.

Notice that the memos based on EBL analysis capture failures that may require a significant amount of search to rediscover. In our example, we are able to discover that G1; G2 is a failing goal set despite the fact that there are no mutex relations between the choices of the goals G1 and G2.

## 4.3 Using The Memos

Before we end this section, there are a couple of observations regarding the use of the stored memos.

In the standard Graphplan, memos at each level are stored in a level-specific hash table. Whenever backward search reaches a level k with a set of conditions to be satisfied, it consults the hash table to see if this exact set of conditions is stored as a memo. Search is terminated only if an exact hit occurs. Since EBL analysis allows us to store compact memos, it is not likely that a complete goal set at some level k is going to exactly match a stored memo. What is more likely is that a stored memo is a subset of the goal set at level k (which is sufficient to declare that goal set a failure). In other words, the memo checking routine in Graphplan needs to be modified so that it checks to see if some subset of the current goal set is stored as a memo. The naive way of doing it - which involves enumerating all the subsets of the current goal set and checking if any of them are in the hash table, turns out to be very costly. One needs more efficient data structures, such as the setenumeration trees (Rymon, 1992). Indeed, Koehler and her co-workers (Koehler, Nebel, Hoffman,
& Dimopoulos, 1997) have developed a data structure called UB-Trees for storing the memos. The UB-Tree structures can be seen as a specialized version of the "set-enumeration trees," and they can efficiently check if any subset of the current goal set has been stored as a memo.

The second observation regarding memos is that they can often serve as a failure explanation in themselves. Suppose we are at some level k, and find that the goal set at this level subsumes some stored memo M. We can then use M as the failure explanation for this level, and regress it back to the previous level. Such a process can provide us with valuable opportunities for further back jumping at levels above k. It also allows us to learn new compact memos at those levels. Note that none of this would have been possible with normal memos stored by Graphplan, as the only way a memo can declare a goal set at level k as failing is if the memo is exactly equal to the goal set. In such a case regression will just get us all the goals at level k , and does not buy us any backjumping or learning power (Kambhampati, 1998).