Improving Graphplan's Search with EBL & DDB Techniques

1 Introduction

Graphplan [Blum & Furst, 97] is currently one of the more efficient algorithms for solving classical planning problems. Four of the five competing systems in the recent AIPS-98 planning competition were based on the Graph plan algorithm [McDermott, 98]. Extending the efficiency of the Graphplan algorithm thus seems to be a worth-while activity. In this pa­ per, I describe my experience with adding explanation-based learning (EBL) and dependency-directed backtracking capa­ bilities (DDB) to Graphplan's backward search. Both EBL and DDB are based on explaining failures at the leaf-nodes of a search tree, and propagating those explanations upwards through the search tree [Kambhampati, 98]. DDB involves using the propagation of failure explanations to support intel­ ligent backtracking, while EBL involves storing interior-node failure explanations, for pruning future search nodes. Graph­ plan does use a rudimentary form of failure-driven learning that it calls "memoization." As we shall see in this paper, Graphplan's brand of learning is quite weak as there is no explicit analysis of the reasons for failure. Instead the expla­ nation of failure of a search node is taken to be all the con­ straints in that search node. As explained in [Kambhampati, 98], this not only eliminates the opportunities for dependency directed backtracking, it also adversely affects the utility of the stored memos.

*This research is supported in part by NSF young investigator award (NYI) IRI-9457634, ARPA/Rome Laboratory planning ini­ tiative grant F30602-95-C-0247, Army AASERT grant DAAH0496-l-0247, AFOSR grant F20602-98-l-0182 and NSF grant IRI9801676. I thank Maria Fox, Derek Long, Terry Zimmerman, Amol Mali and Biplav Srivastava for comments on this work.

Adding full-fledged EBL and DDB capabilities in ef­ fect gives Graphplan both the ability to do intelligent back­ tracking, and the ability to learn generalized memos that are more likely to be applicable in other situations. Tech­ nically, this involves generalizing conflict-directed back­ jumping [Prosser, 93], a well-known technique in CSP, to work in the context of Graphplan's backward search. Empiri­ cally, the EBUDDB capabilities improve Graphplan's search efficiency quite dramatically-allowing it to easily solve sev­ eral problems that have hither-to been hard or unsolvable. In particular, I will report on my experiments with the bench­ mark problems used in [Kautz & Selman, 96], as well as four other standard test domains. The experiments show up-to 100 fold speedups on individual problems.

This paper is organized as follows. In the next section, I provide some background on Graphplan's backward search. In Section 3, I discuss some inefficiencies of the backtracking and learning methods used in normal Graphplan that motivate the need for EBUDDB capabilities. Section 4 describes how EBL and DDB are added to Graphplan. Section 5 presents empirical studies demonstrating the usefulness of these aug­ mentations. Section 6 discusses related work and Section 7 presents conclusions and some directions for further work.

2 Review of Graphplan algorithm

Graphplan algorithm [Blum & Furst, 97] can be seen as a "disjunctive" version of the forward state space planners [Kambhampati et. al., 97a]. It consists of two interleaved phases - a forward phase, where a data structure called "planning-graph" is incrementally extended, and a backward phase where the planning-graph is searched to extract a valid plan. The planning-graph (see Figure 1) consists of two alter­ nating structures, called "proposition lists" and "action lists." Figure 1 shows a partial planning-graph structure. We start with the initial state as the zeroth level proposition list. Given a k level planning graph, the extension of structure to level k + 1 involves introducing all actions whose preconditions are present in the kth level proposition list. In addition to the actions given in the domain model, we consider a set of dummy "persist" actions, one for each condition in the kth level proposition list. A "persist-C" action has C as its pre­ condition and C as its effect. Once the actions are introduced, the proposition list at level k + 1 is constructed as just the union of the effects of all the introduced actions. Planning­ graph maintains the dependency links between the actions at level k + 1 and their preconditions in level k proposition list and their effects in level k + 1 proposition list. The planning­ graph construction also involves computation and propaga­ tion of "mutex" constraints. The propagation starts at level 1, with the actions that are statically interfering with each other (i.e., their preconditions and effects are inconsistent) la­ beled mutex. Mutexes are then propagated from this level forward by using two simple propagation rules. In Figure 1, the curved lines with x-marks denote the mutex relations.

The search phase on a k level planning-graph involves checking to see if there is a sub-graph of the planning-graph that corresponds to a valid solution to the problem. This in­ volves starting with the propositions corresponding to goals at level k (if all the goals are not present, or if they are present but a pair of them are marked mutually exclusive, the search is abandoned right away, and planning-graph is grown an­ other level). For each of the goal propositions, we then se­ lect an action from the level k action list that supports it, such that no two actions selected for supporting two different goals are mutually exclusive (if they are, we backtrack and try to change the selection of actions). At this point, we recursively call the same search process on the k-1level planning-graph, with the preconditions of the actions selected at level k as the goals for the k - 1 level search.· The search succeeds when we reach level 0 (corresponding to the initial state).

Previous work [Kambhampati et. a!., 97a] had expli­ cated the connections between this backward search phase of Graphplan algorithm and the constraint satisfaction problems (specifically, the dynamic constraint satisfaction problems, as introduced in [Mittal & Falkenhainer, 90]).

3 Some inefficiencies in Graphplan's backward search

To motivate the need for EBL and DDB, we shall first re­ view the details of Graphplan's backward search, and pin­ point some of its inefficiencies. We sh~ll base our dis~ussion on the example planning graph from Ftgure 1. Assummg that G1 · · · G4 are the top level goals of the problem we are inter­ ested in solving, we start at level k, and select actions to sup­ port the goals G1 · · · G4 . To keep matters simple, we shall assume that the search assigns the conditions (variables) at each level from top to bottom (i.e., G1 first, then Gz and so on). Further, when there is a choice in the actions (values) that can support a condition, we will consider the top actions first. Since there is only one choice for each of the conditions at level k, and none of the actions are mutually exclusive with each other, we select the actions A1 , A2 , A3 and A4 for sup­ porting the conditions at level k. We now have to make sure that the preconditions of A1 , A2 , A3 , A4 are satisfied at level k - 1. We thus subgoal on the conditions P1 · · · Ps at level k - 1, and recursively start the action selection for them. We select the action As for P1 _ For P2 , we have two supporting actions, and using our convention, we select As first. For P3, A1 is the only choice. When we get down to selecting a sup­ port for P4 , we again have a choice. Suppose we select As first. We find that this choice is infeasible as As is mutually exclusive with As that is already chosen. So, we backtrack and choose A9 , and find that it too is mutually exclusive with a previously· selected action, As . We now are stymied as there are no other choices for P4 · So, we have to backtrack and undo choices for the previous conditions. Graphplan uses a chronological backtracking approach, whereby, it first tries to see if P3 can be re-assigned, and then Pz and so on. Notice the first indication of inefficiency here - the failure to as­ sign P4 had nothing to do with the assignment for P3 , and yet, chronological backtracking will try to re-assign P3 in the vain hope of averting the failure. This can lead to a large amount of wasted effort had it been the case that P3 did indeed have other choices.

As it turns out, we find that P3 has no other choices and backtrack over it. P2 does have another choice - A11 . We try to continue the search forward with this value for Pz, but hit an impasse at P3-since the only value of P3, A1 is mutex with A11 . At this point, we backtrack over P3 , and continue back­ tracking over P2 and P1 , as they too have no other remaining choices. When we backtrack over P1 , we need to go back to level k and try to re-assign the goals at that level. Before this is done, the Graphplan search algorithm makes a "memo" signifying the fact that it failed to satisfy the goals P1 · · · Ps at this level, with the hope that if the search ever subgoals on these same set of goals in future, we can scuttle it right away with the help of the remembered memo. Here is the second indication of inefficiency- we are remembering all the subgoals P1 · · · Ps even though we can see that the prob­ lem lies in trying to assign P1 , P2 , P3 and P4 simultaneously, and has nothing to do with the other sub goals. If we remem­ ber { P1 , P2 , P3 , P4 } as the memo as against { P1 · · · Ps}, 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 en­ countered in assigning P3 and P4 - since it only spawns the condition Ps at level k - 1. Yet, the backtracking scheme of Graph plan considers reassigning G3 · A somewhat more .sub­ tle point is that reassigning G4 is not going to avert the fatlure either. Although G4 requires P1 one of the conditions taking part in the failure, P1 is also required by G1 and unle~s G1 gets reassigned, considering further assignments to G4 IS not going to avert the failure.

For this example, we continue backtracking over Gz and G1 too, since they too have no alternative supports, and fi­ nally memoize { G1 , G2 , G3 , G4 } at this level. At this point the backward search fails , and Graphplan extends the plan­ ning 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 sec­ tion. Informally, EBUDDB strategies involve explanation of failures at leaf nodes, and regression and propagation of leaf node failure explanations to compute interior node fail­ ure explanations, along the lines described in [Kambhampati, 98]. The specific extensions I propose to the backward search can essentially be seen as adapting conflict-directed back­ jumping strategy [Prosser, 93], and generalizing it to work with Graphplan's backward search (which can be seen as a form of dynamic constraint satisfaction problem). The de­ velopment here parallels the framework described in [Kamb­ hampati, 98].

The algorithm is shown in pseudo-code form in Figure 2. It contains two mutually recursive procedures find-plan and assign-goals. The former is called once for each level of the planning-graph. It then calls assign-goals to assign values to all the required conditions at that level. assign-goals picks a condition, selects a value for it, and recursively calls itself with the remaining conditions. When it is invoked with an empty set of conditions to be assigned, it calls find-plan to initiate the search at the next (previous) level.

In order to illustrate how EBL/DDB capabilities are added, Jet's retrace the previous example, and pick up at the point where we are about to assign P4 at level k - 1, having as­ signed P1 , P2 and P3 . When we try to assign the value As to P4 , we violate the mutex constraint between A6 and As. An explanation of failure for a search node is a set of constraints from which False can be derived. The complete explanation for this failure can thus be stated as:

Of this, the part P2 = A6 => P4 =f. As can be stripped from the explanation since the mutual exclusion relation will hold as long as we are solving this particular problem with these particular actions. Further, we can take a cue from the conflict directed back-jumping algorithm [Prosser, 93], and represent the remaining explanation compactly in terms of "conflict sets." Specifically, whenever the search reaches a condition c (and is about to find an assignment for it), its con­ flict set is initialized as { c}. Whenever one of the possible assignments to c is inconsistent (mutually exclusive) with the current assignment of a previous variable c', we add c' to the conflict set of c. In the current example, we start with { P4 } as the conflict set of P4 , and expand it by adding P2 after we find that As cannot be assigned to P4 because of the choice of A6 to support P2 · Informally, the conflict set representation can be seen as an incrementally maintained (partial) expla­ nation of failure, indicating that there is a conflict between the current value of P2 and one of the possible values of P4 [Kambhampati, 98].

Find- Plan( G:goals, pg: plan graph, k: level)

If k=O. Return an empty subplan P with success. If there is a memo M that is a subset of G, Fail. and return M as the conflict set Call Assign- goals( G. pg. k. nil). If Assign-goals fails and returns a conflict set M. Store M as a memo Regress Mover actions selected at level k+ I to get R Fail and return R as the conflict set If Assign-goals succeeds, and returns a k-level Return P with success subplan P. Assign- goals( G:goals, pg: plan graph, k: level, A: actions) If G is empty. Let U union of preconditions of the actions in A Call Find- plan( U, pg, k-1 ) If it fails and returns a conflict set R, Fail and return R If it succeeds and returns a subplan P of length k-1 Succeed and return a k length subplan P.A lfG is not empty, Select a goal g from G Let cs = ( g }, and Ag be the set of actions from level k in pg that support g Ll: If Ag is empty. Fail and return cs as the conflict set Else, pick an action a from Ag If a is mutually exclusive with some action b in A Let I be the goal tha! b was selected to support Set cs=cs+{l} GotoLI Else ( a is not mutually exclusive with any action in A) Call Assign- goals( G -1 g }, pg, k, A +(a} ) If the call fails and returns a conflict set C If g is part of C Set cs = cs + C ;conflict set absorption GotoLI Else ( g is not part of C) Fail and return C as the conflict set ;dependency directed backjumping

We now consider the second possible value of P4 , viz., A9 , and find that it is mutually exclusive with As which is currently supporting P1 · Following our practice, we add P1 to the conflict set of P4 · At this point, there are no further choices for P4 , and so we backtrack from P4 , passing the conflict set of P4, viz., { P1 , P2 , P4} as the reason for its fail­ ure. In essence, the conflict set is a shorthand notation for the following complete failure explanation [Kambhampati, 98]: 1

It is worth noting at this point that when P4 is revisited in the future (with different assignments to the preceding vari­ ables), its conflict set will be re-initialized to { P4 } before considering any assignments to it.

1 We strip the first (disjunctive) clause since it is present in the graph structure, and the next two implicative clauses since they are part of the mutual exclusion relations that will not change for this problem. The conflict set representation just keeps the condition (variable) names of the last two clauses -denoting, in essence, that it is the current assignments of the variables P1 and P2 that are causing the failure to assign P4.

De~en~~ncy directe~ bac~tracking: The first advantage of mamtammg the conflict set IS that it allows a transparent way of dependency directed backtracking [Kambhampati, 98]. In the current example, having failed to assign P4 , we have to start backtracking. We do not need to do this in a chronologi­ cal fashion however. 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 back-jumping 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 cur­ ~ent conflict set of c. In our example, we absorb {Pi , P2, P4 } mto the conflict set of P2 , which is currently { P2 } (making {Pi , P2, P4} the new conflict set of P2 ). We now assign An, the only remaining value, to P2 · Next we try to assign P3 and find that its only value A7 is mutex with An. Thus, we set conflict set of P3 to be { P3 , P2 } and backtrack with this con­ flict set. When the backtracking reaches P2 , this conflict set is absorbed into the current conflict set of P2 (as described earlier), giving rise to {Pi, P2, P3 , P4 } as the current com­ bined failure reason for P2 · This step illustrates how the con­ flict 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, {Pi , P2, P3 , P4 }. At Pi, we first absorb the conflict set {Pi, P2, P3 , P4 } into Pi's cur­ rent conflict set, and then re-initiate backtracking since Pi has no further choices.

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

Memoization: Before we backtrack over the first assigned variable at a given level, we store the conflict set of that vari­ able as a memo at that level. In the current example, we store the conflict set {Pi, P2, P3 , P4 } of Pi as a memo at this level. Notice that the memo we store is shorter (and thus more gen­ eral) 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 failure. 2

Regression: Before we backtrack out of level k - 1 to level k, we need to convert the conflict set of (the first assigned variable in) level k-1 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, 98]. 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 - 1. In the current case, our conflict set is {Pi , P2, P3 , P4 }. We can see that P2, P3 are required because of the condition Gi at level k, and the condition P4 is required because of the condition G2 ·

2 While in the current example, the memo includes all the condi­ tions up to P4 (which is the farthest we have gone in this level), even this is not always necessary. We can verify that P3 would not have been in the memo set if An were not one of the supporters of P2 ·

In the case of condition Pi, both Gi and G4 are responsible for it, as both their supporting actions need Pi. In such cases we have two heuristics for computing the regression: (1) Pre­ fer choices that help the conflict set to regress to a smaller set of conditions (2) If we still have a choice between multi­ ple conditions at level k, pick the one that has been assigned earlier. The motivation for the first rule is to keep the fail­ ure explana~ions as compact (and thus as general) as possible, and the motivation for the second rule is to support deeper de­ pendency directed backtracking. It is important to note that these heuristics are aimed at improving the performance of the EBUDDB and do not affect the soundness and complete­ ness of the approach.

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

The result of regressing {Pi, P2, P3 , P4 } over the actions at kth level is thus { Gi, G2 }. We start backtracking at level k ~ith t~i~ as the conflict set. w_e jump back to G2 right away, smce It IS the most recent vanable 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 ~acktra~k conflict set is absorbed, and the backtracking contmues smce there are no other choices. Same procedure is repeated at Gi . At this point, we are once again at the end of a level-and we memoize { Gi , 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 fail­ ures that may require a significant amount of search to redis­ cover. In our example, we are able to discover that { Gi , G2 } is a failing goal set despite the fact that there are no mutex relations between the choices of the goals Gi and G2 ·

Using the Memos (EBL): 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 oc­ curs. 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 check­ ing if any of them are in the hash table- turns out to be very costly. One needs more efficient data structures, such as the set-enumeration trees [Rymon, 92]. Indeed, Koehler and her co-workers [Koehler et. a!., 97] have developed a (seeming variation of set-enumeration tree) data structure called DB­ Trees for storing the memos. The UB-Tree structures 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 + 1, and does not buy us any back­ jumping or learning power [Kambhampati, 98] .

5 Empirical Evaluation

We have now seen the way EBL and DDB capabilities are added to the backward search by maintaining and updating conflict-sets. We also noted that EBL and DDB capabilities avoid a variety of inefficiencies in the standard Graphplan backward search. That these augmentations are soundness and completeness preserving follows from the corresponding properties of conflict-directed back-jumping [Kambhampati, 98] . The remaining (million-dollar) question is whether these capabilities make a difference in practice. I now present a set of empirical results to answer this question.

I implemented the EBUDDB approach described in the previous section on top of a Graphplan implementation in lisp. 3 The changes needed to the code to add EBUDDB capa­ bility were minor- only two functions Assign-goals and find-plan-needed non-trivial changes. I also added the UB-Tree subset memo checking code described in [Koehler et. a!., 97]. I then ran several comparative experiments on the "benchmark" problems from [Kautz & Selman, 96], as well as from four other domains. The specific domains in­ cluded blocks world, rocket world, logistics domain, grip­ per domain, ferry domain, traveling salesperson domain, and towers of hanoi. The specifications of the problems as well as domains are publicly available. Table 1 shows the statistics on the times taken and number of backtracks made by normal Graphplan, and Graph plan with EBUDDB capabilities.

3 The original lisp implementation of Graphplan was done by Mark Peot. The implementation was subsequently improved by David Smith.

Runtime Reductions & Solvability improvements: The first thing we note is that EBUDDB techniques can offer quite dramatic speedups - upto lOOx in the seven domains I tested. We also note that the number of backtracks re­ duces significantly and consistently with EBUDDB. More­ over, EBUDDB techniques push the solvability horizon as many problems were unsolvable without EBL even after 3-4 hours of cpu time! 4

Reduction in Memo Length: The results also show that as expected the length of memos stored by Graphplan de­ creased substantially when EBUDDB strategies are em­ ployed. For example, the average memo length (the column named "AvLn" in Table 1) goes down from 32 to 8 in logis­ tics, and 24 to 8 in the ferry domain. Furthermore, the relative reductions in memo length in different domains are well cor­ related with the speedups seen in those domains. Specifically, we note that blocks world domain, which shows a some­ what lower (~2x) speedup also has lower memo-length re­ duction (from 11.8 to 10). Similarly, the fact that the average length of memos for rocket-ext-a problem is 8.5 with EBL, and 24 without EBL, shows in essence that normal Graph­ plan is re-discovering an 8-sized failure embedded in many many possible ways in a 24 sized goal set - storing a new memo each time (incurring both increased backtracking and matching costs)! It is thus no wonder that normal Graphplan performs badly compared to Graphplan with EBUDDB.

Utility of stored memos: Since EBUDDB store more general (smaller) memos than normal Graphplan, they should, in theory, generate fewer memos and use them more often. The columns labeled "AvFM" give the ratio of the number of fail­ ures discovered through the use of memos to the number of memos generated in the first place. This can be seen as a rough measure of the average "utility" of the stored memos. We note that the utility is consistently higher with EBUDDB in all the solved problems. As an example, in rocket-ext-b. we see that on the average an EBUDDB generated memo was used to discover failures 101 times, while the number was only 3.2 for the memos generated by the normal Graphplan.

4 For our lisp system configuration, this amounted to about 12-20 hours of real time including garbage collection time.

The C vs. Lisp question: Given that most existing imple­ mentations of Graphplan are done in C with many optimiza­ tions, one nagging doubt is whether the dramatic speedups due to EBUDDB are somehow dependent on the moderately optimized Lisp implementation I have used in my experi­ ments. Thankfully, the EBUDDB techniques described in this paper have also been (re)implemented by Maria Fox and Derek Long on their STAN system. STAN is a highly op­ timized implementation of Graphplan that fared well in the recent AlPS planning competition. They have found that EBUDDB resulted in the same dramatic speedups on their system too [Fox, 98].

6 Related Work

In their original implementation of Graphplan, Blum and Furst experimented with a variation of the memoization strat­ egy called "subset memoization". In this strategy, they keep the memo generation techniques the same, but change the way memos are used, declaring a failure when~ stored memo is found to be a subset of the current goal set. Smce complete subset checking is costly, they experimented with a "partial" subset memoization where only subsets of length n and n- 1 are considered for an n sized goal set.

As we mentioned earlier, Koehler and her co-workers [Koehler et. al., 97] have re-visited the subset memoization strategy, and developed a more effective solution to ~omplete subset checking that involves storing the memos m a data structure called UB-Tree, instead of in hash tables. The re­ sults from their own experiments with subset memoization, a.s well as my replication of those experiments [Kambhampat1, 98b], are mixed at best, and indicate that the improvements are nowhere near those achievable through DDB and EBL. The reason for this is quite easy to understand - while they improved the memo checking time with the UB-Tree data structure they are still generating and storing the same old long me~os. In contrast, the EBUDDB extension described here supports dependency directed backtracki~g, and by r~­ ducing the ;1verage length of stored memos, mcreases the1r utility significantly, thus offering dramatic speedups.

[Kambhampati, 98] describes the general principles un­ derlying the EBUDDB techniques and sketches how they can be extended to dynamic constraint satisfaction problems. [Kambhampati, 97a] discusses the relations between <?rap~­ plan and dynamic CSP problems. The development m this paper can be seen as an application of the ideas from these two papers.

7 Conclusion and Future work

In this paper, I motivated the need for adding EB~DB ca­ pabilities to Graphplan's backward search, and descnbed the changes needed to support these capabilities in Graphplan. I also presented and analyzed empirical results to demon­ strate that EBUDDB capabilities significantly enhance the efficiency of Graph plan on benchmark problems in seven dif­ ferent domains. Based on these results, and the fact that I have not encountered any problems where EBL/DDB turned out to be a significant net drain on efficiency, I conclude that EBUDDB extensions are very useful for Graphplan.

There are several ways in which this work can be (and is being) extended. Recently, I have added forward checking and dynamic variable ordering capabilities on top of EBL & DDB in Graphplan, and initial results show further improve­ ments (up to a factor of 4) in run time [Kambhampati, 98b]. The success of EBUDDB approaches in Graphplan is in part due to the high degree of redundancy in the planning graph structure. In [Zimmerman & Kambhampati, 99], we inves­ tigate techniques that are even more aggressive in exploiting this redundancy to improve planning performance. Finally, we are also studying the utility of memo-forgetting strategies such as relevance based learning [Bayardo & Schrag, 97], as well as inter-problem memo transfer.