
| Problem      | EBL+DDB   | DDB   | Speedup   |       |       |
|--------------|-----------|-------|-----------|-------|-------|
| Btks         | Time      | Btks  | Time      |       |       |
| Att-log-a    | 2186K     | 1.95  | 115421K   | 235   | 120x  |
| Tower-6      | 4098K     | 2.37  | 97395K    | 121   | 51x   |
| Rocket-ext-a | 764K      | .83   | 3764K     | 17.18 | 21x   |
| Gripper-8    | 4426K     | 2.43  | 5426K     | 4.71  | 1.94x |
| TSP-10       | 2238K     | 1.1   | 4308K     | 2.3   | 2.09x |
| Huge-Fct     | 2004K     | 3.21  | 2465K     | 3.83  | 1.19x |

strategies were left in.14 The results are shown in Table 2, and demonstrate that the ability to store smaller memos (as afforded by EBL) is quite helpful–giving rise to 120x speedup over DDB alone in the Att-log-a problem, and 50x speedup in Tower-6 problem. Of course, the results also show that DDB is an important capability in itself. Indeed, Att-log-aand tower-6 could not even be solved by the standard Graphplan, while with DDB, these problems become solvable. In summary, the results show that both EBL and DDB can have a net positive utility.

## 5.5 Utility Of Memoization

Another minor, but not well-recognized, point brought out by the statistics in Table 1 is that the memo checking can sometimes be a significant fraction of the run-time of standard Graphplan. For example, in the case of Rocket-ext-a, standard Graphplan takes 19.4 minutes of which 11.7 minutes, or over half the time, is spent in memo checking (in hash tables)! This raises the possibility that if we just disable the memoization, perhaps we can do just as well as the version with EBL/DDB. To see if this is the case, I ran some of the problems with memoization disabled. The results show that in general disabling memo-checking leads to worsened performance. While I came across some cases where the disablement reduces the overall run-time, the run-time is still much higher than what you get with EBL/DDB. As an example, in the case of Rocket-ext-a, if we disable the memo checking completely, Graphplan takes 16.5 minutes, which while lower than the 19.4 minutes taken by standard Graphplan, is still much higher than the .8 minutes taken by the version of Graphplan with EBL/DDB capabilities added. If we add DDB capability, while still disabling the memochecking, the run time becomes 2.4 minutes, which is still 3 times higher than that afforded with EBL capability.

## 5.6 The C Vs. Lisp Question

Given that most existing implementations of Graphplan are done in C with many optimizations, one nagging doubt is whether the dramatic speedups due to EBL/DDB are somehow dependent on the moderately optimized Lisp implementation I have used in my experiments. Thankfully, the EBL/DDB techniques described in this paper have also been (re)implemented by Maria Fox and Derek Long on their STAN system. STAN is a highly optimized implementation of Graphplan that fared well in the recent AIPS planning competition. They have found that EBL/DDB resulted in similar dramatic speedups on their system too (Fox, 1998; Fox & Long, 1999). For example,