matic increases in the average run time. For example, for the Att-log-a problem, with 5 restarts and 50 backtracks, and 20 levels limit, Graphplan was able to solve the problem 99% of the time, with an average plan length of 14 steps and 82 actions. In contrast, without EBL/DDB, Graphplan was able to solve the problem in only 2% of the cases, with an average plan length of 19 steps and 103 actions. If we double the restarts and backtracks, the EBL/DDB version goes to 100% solvability with an average plan length of 11.33 steps and 69.53 actions. The standard Graphplan goes to 11%
solvability and a plan length of 17.6 steps and 100 actions. If we increase the number of levels to 30, then the standard Graphplan solves 54% of the problems with an average plan length of 25.6 steps and 136 actions. It takes 20 restarts and 200 backtracks, as well as a 30-level limit before standard Graphplan is able to cross 90% solvability. By this time, the average run time is 31 minutes, and the average plan length is 22 steps and 119 actions. The contrast between this and the 99% solvability in 0.4 minutes with 14 step 82 action plans provided by Graphplan with EBL and 5 restarts and 50 backtracks is significant! Similar results were observed in other problems, both in logistics
(Att-log-b, Att-log-c) and other domains (Rocket-ext-a, Rocket-ext-b).

The results also show that Graphplan with EBL/DDB is able to generate and reuse memos effectively across different restart epochs. Specifically, the numbers in the columns titled "Av. MFSL"
give the average number of memo-based failures per search level.22 We note that in all cases, the average number of memo-based failures are significantly higher for Graphplan with EBL than for normal Graphplan. This shows that EBL/DDB analysis is helping Graphplan reduce wasted effort significantly, and thus reap better benefits out of the given backtrack and restart limits.

## 9. Related Work

In their original implementation of Graphplan, Blum and Furst experimented with a variation of the memoization strategy 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 a stored memo is found to be a subset of the current goal set. Since complete subset checking is costly, they experimented with a "partial" subset memoization where only subsets of length n and n are considered for an n sized goal set.

As we mentioned earlier, Koehler and her co-workers (Koehler et al., 1997) have re-visited the subset memoization strategy, and developed a more effective solution to complete subset checking that involves storing the memos in a data structure called UB-Tree, instead of in hash tables. The results from their experiments with subset memoization are mixed, indicating that subset memoization does not seem to improve the cpu time performance significantly. 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 memos. In contrast, the EBL/DDB extension described here supports dependency directed backtracking, and by reducing the average length of stored memos, increases their utility significantly, thus offering dramatic speedups.

To verify that the main source of power in the EBL/DDB-Graphplan is in the EBL/DDB part and not in the UB-Tree based memo checking, I re-ran my experiments with EBL/DDB turned off,