they were unable to solve Att-log-a with plain Graphplan, but could solve it easily with EBL/DDB
added.

Finally, it is worth pointing out that even with EBL/DDB capabilities, I was unable to solve some larger problems in the AT&T benchmarks, such as bw-large-c and Att-log-b. This is however not an indictment against EBL/DDB since to my knowledge the only planners that solved these problems have all used either local search strategies such as GSAT, randomized re-start strategies, or have used additional domain-specific knowledge and pre-processing. At the very least, I am not aware of any existing implementations of Graphplan that solve these problems.

## 6. On The Utility Of Graphplan Memos

One important issue in using EBL is managing the costs of storage and matching. Indeed, as discussed in (Kambhampati, 1998), naive implementations of EBL/DDB are known to lose the gains made in pruning power in the matching and storage costs. Consequently, several techniques have been invented to reduce these costs through selective learning as well as selective forgetting. It is interesting to see why these costs have not been as prominent an issue for EBL/DDB on Graphplan. I think this is mostly because of two characteristics of Graphplan memoization strategy:

1. Graphplan's memoization strategy provides a very compact representation for no-goods, as well as a very selective strategy for remembering no-goods. Seen as DCSP, it only remembers subsets of activated variables that do not have a satisfying assignment. Seen as a CSP (c.f.

Figure 2), Graphplan only remembers no-goods of the form

## P I 1 P I 2    P I M

(where the superscripts correspond to the level of the planning graph to which the proposition belongs), while normal EBL implementations learn no-goods of the form

P i
$$a_{1}\;\;\;\;\;P_{2}^{j}\;\;\;\;\;a_{2}\;\;\;\;\;P_{m}^{k}$$
$$a_{\mathrm{m}}$$
m am Suppose a planning graph contains n propositions divided into l levels, and each proposition P at level j has at most d actions supporting it. A CSP compilation of the planning graph will have n variables, each with d+ 1 values (the extra one for ). A normal EBL implementation for such a CSP can learn, in the worst case, d 2)nno-goods.15 In contrast, Graphplan remembers only l 2 n l memos16–a very dramatic reduction. This reduction is a result of two factors:
(a) Each individual memo stored by Graphplan corresponds to an exponentially large set of normal no-goods (the memo

$$P_{2}^{i}$$

P i
1 P i
2    P i
$$P_{\mathrm{m}}^{i}$$
is a shorthand notation for the conjunction of dmno-goods corresponding to all possible non- assignments to P i 1    P i m)