
## 5. Empirical Evaluation Of The Effectiveness Of Ebl/Ddb

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 backjumping (Kambhampati, 1998). 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 EBL/DDB approach described in the previous section on top of a Graphplan implementation in Lisp.8 The changes needed to the code to add EBL/DDB capability were relatively minor - only two functions needed non-trivial changes9. I also added the UB-Tree subset memo checking code described in (Koehler et al., 1997). I then ran several comparative experiments on the "benchmark" problems from (Kautz & Selman, 1996), as well as from four other domains.

The specific domains included blocks world, rocket world, logistics domain, gripper domain, ferry domain, traveling salesperson domain, and towers of hanoi. Some of these domains, including the blocks world, the logistics domain and the gripper domain were used in the recent AI Planning Systems competition. 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 Graphplan with EBL/DDB capabilities.10

## 5.1 Run-Time Improvement

The first thing we note is that EBL/DDB techniques can offer quite dramatic speedups - from 1.6x in blocks world all the way to 120x in the logistics domain (the Att-log-a problem is unsolvable by normal Graphplan after over 40 hours of cpu time!). We also note that the number of backtracks reduces significantly and consistently with EBL/DDB. Given the lengh of some of the runs, the time Lisp spends doing garbage collection becomes an important issue. I thus report the cumulative time
(including cpu time and garbage collection time) for Graphplan with EBL/DDB, while I separate the cpu time from cumulative time for the plain Graphplan (in cases where the total time spent was large enough that garbage collection time is a significant fraction). Specifically, there are two entrys in the column corresponding to total time for the normal Graphplan. The first entry is the cpu time spent, while the second entry in parenthesis is the cumulative time (cpu time and garbage collection time) spent. The speedup is computed with respect to the cumulative time of Graphplan with EBL/DDB and cpu time of plain Graphplan. 11 The reported speedups should thus be seen as conservative estimates.