
## 5.2 Reduction In Memo Length

The results also highlight the fact that the speedups offered by EBL/DDB are problem/domain dependent - they are quite meager in blocks world problems, and are quite dramatic in many other domains including the rocket world, logistics, ferry, gripper, TSP and Hanoi domains. The statistics on the memos, shown in Table 1 shed light on the reasons for this variation. Of particular interest is the average length of the stored memos (given in the columns labeled "AvLn"). In general, we expect that the EBL analysis reduces the length of stored memos, as conditions that are not part of the failure explanation are not stored in the memo. However, the advantage of this depends on the likelihood that only a small subset of the goals at a given level are actually taking part in the failure.

This likelihood in turn depends on the amount of inter-dependencies between the goals at a given level. From the table, we note that the average length reduces quite dramatically in the rocket world and logistics12, while the reduction is much less pronounced in the blocks world. This variation can be traced back to a larger degree of inter-dependency between goals at a given level in the blocks world problems.

The reduction in average memo length is correlated perfectly with the speedups offered by EBL
on the corresponding problems. Let me put this in perspective. 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 Graphplan is re-discovering an 8-sized failure embedded in 24 8

possible ways in the worst case 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 EBL/DDB.

## 5.3 Utility Of Stored Memos

The statistics in Table 1 also show the increased utility of the memos stored by Graphplan with EBL/DDB. Since EBL/DDB 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 failures discovered through the use of memos to the number of memos generated in the first place. This can be seen as a measure of the average "utility" of the stored memos. We note that the utility is consistently higher with EBL/DDB. As an example, in Rocketext-b, we see that on the average an EBL/DDB generated memo was used to discover failures 101 times, while the number was only 3.2 for the memos generated by the normal Graphplan.13

## 5.4 Relative Utility Of Ebl Vs. Ddb

From the statistics in Table 1, we see that even though EBL can make significant improvements in run-time, a significant fraction of the run time with EBL (as well as normal Graphplan) is spent in memo checking. This raises the possibility that the overall savings are mostly from the DDB part and that the EBL part (i.e, the part involving storing and checking memos) is in fact a net drain
(Kambhampati, Katukam, & Qu, 1997). To see if this is true, I ran some problems with EBL (i.e., memo-checking) disabled. The DDB capability as well as the standard Graphplan memoization