oization." As we shall see in this paper, Graphplan's brand of learning is quite limited as there is no explicit analysis of the reasons for failure. Instead the explanation of failure of a search node is taken to be all the constraints in that search node. As explained in (Kambhampati, 1998), this not only eliminates the opportunities for dependency directed backtracking, it also adversely effects the utility of the stored memos.

Adding full-fledged EBL and DDB capabilities in effect gives Graphplan both the ability to do intelligent backtracking, and the ability to learn generalized memos that are more likely to be applicable in other situations. Technically, this involves generalizing conflict-directed backjumping
(Prosser, 1993), a specialized version of EBL/DDB strategy applicable for binary CSP problems1 to work in the context of dynamic constraint satisfaction problems (as discussed in (Kambhampati, 1998)). Empirically, the EBL/DDB capabilities improve Graphplan's search efficiency quite dramatically–giving rise to up to 1000x speedups, and allowing Graphplan to easily solve several problems that have hither-to been hard or unsolvable. In particular, I will report on my experiments with the bench-mark problems described by Kautz and Selman (1996), as well as 4 other domains, some of which were used in the recent AIPS planning competition (McDermott, 1998).

I discuss the utility issues involved in storing and using memos, and point out that the Graphplan memoization strategy can be seen as a *very* conservative form of CSP no-good learning. While this conservative strategy keeps the storage and retrieval costs of no-goods –the usual bane of no-good learning strategies–under control, it also loses some learning opportunities. I then present the use of "sticky values" as a way of recouping some of these losses. Empirical studies show that sticky values lead to a further 2-4x improvement over EBL.

In addition to EBL and DDB, I also investigated the utility of forward checking and dynamic variable ordering, both in isolation and in concert with EBL and DDB. My empirical studies show that these capabilities typically lead to an additional 2-4x speedup over EBL/DDB, but are not by themselves competitive with EBL/DDB.

Finally, I consider the utility of the EBL/DDB strategies in the context of random-restart search strategies (Gomes, Selman, & Kautz, 1998) that have recently been shown to be good at solving hard combinatorial problems, including planning problems. My results show that EBL/DDB
strategies retain their advantages even in the context of such random-restart strategies. Specifically, EBL/DDB strategies enable Graphplan to use the backtrack limits more effectively–allowing it to achieve higher solvability rates, and more optimal plans with significantly smaller backtrack and restart limits.

This paper is organized as follows. In the next section, I provide some background on viewing Graphplan's backward search as a (dynamic) constraint satisfaction problem, and review some of the opportunities this view presents. In Section 3, I discuss some inefficiencies of the backtracking and learning methods used in normal Graphplan that motivate the need for EBL/DDB capabilities.

Section 4 describes how EBL and DDB are added to Graphplan. Section 5 presents empirical studies demonstrating the usefulness of these augmentations. Section 7 investigates the utility of forward checking and dynamic variable ordering strategies for Graphplan. Section 8 investigates the utility of EBL/DDB strategies in the context of random-restart search. Section 9 discusses related work and Section 10 presents conclusions and some directions for further work.

1. Binary CSP problems are those problems where all initial constraints are between pairs of variables.

2