
| Problem      | Tt    | Mt   | #Btks   | EBL x"   | #Gen   | #Fail   | AvFM   | AvLn   |
|--------------|-------|------|---------|----------|--------|---------|--------|--------|
| Huge-Fact    | 3.20  | 1    | 2497K   | 1.04x    | 24243  | 33628   | 1.38   | 11.07  |
| BW-Large-b   | 2.74  | 0.18 | 1309K   | 1.21x    | 11708  | 15011   | 1.28   | 11.48  |
| Rocket-ext-a | 19.2  | 16.7 | 6188K   | 24x      | 62419  | 269499  | 4.3    | 24.32  |
| Rocket-ext-b | 7.36  | 4.77 | 7546K   | 9.2x     | 61666  | 265579  | 4.3    | 24.28  |
| Att-log-a    | 12hrs | -    | -       | 120x     | -      | -       | -      | -      |

Table 7: Performance of subset memoization with UB-Tree data structure (without EBL/DDB). The
"Tt" is the total cpu time and "Mt" is the time taken for checking memos. "\#Btks" is the number of backtracks. "EBLx" is the amount of speedup offered by EBL/DDB over subset memoization "\#Gen" lists the number of memos generated (and stored), "\#Fail" lists the number of memo-based failures, "AvFM" is the average number of failures identified per generated memo and "AvLn" is the average length of stored memos.

but with subset memo checking with UB-Tree data structure still enabled. The results are shown in in Table 7. The columns labeled "AvFM" show that as expected subset memoization does improve the utility of stored memos over normal Graphplan (since it uses a memo in more scenarios than normal Graphplan can). However, we also note that subset memoization by itself does not have any dramatic impact on the performance of Graphplan, and that EBL/DDB capability can significantly enhance the savings offered by subset memoization.

In (Kambhampati, 1998), I describe the general principles underlying the EBL/DDB techniques and sketch how they can be extended to dynamic constraint satisfaction problems. The development in this paper can be seen as an application of the ideas there. Readers needing more background on EBL/DDB are thus encouraged to review that paper. Other related work includes previous attempts at applying EBL/DDB to planning algorithms, such as the work on UCPOP+EBL system
(Kambhampati et al., 1997). One interesting contrast is the ease with which EBL/DDB can be added to Graphplan as compared to UCPOP system. Part of the difference comes from the fact that the search in Graphplan is ultimately on a propositional dynamic CSP, while in UCPOP's search is a variablized problem-solving search.

As I mentioned in Section 2, Graphplan planning graph can also be compiled into a normal CSP
representation, rather than the dynamic CSP representation. I used the dynamic CSP representation as it corresponds quite directly to the backward search used by Graphplan. We saw that the model provides a clearer picture of the mutex propagation and memoization strategies, and helps us unearth some of the sources of strength in the Graphplan memoization strategy–including the fact that memos are a very conservative form of no-good learning that obviate the need for the no-good management strategies to a large extent.

The dynamic CSP model may also account for some of the peculiarities of the results of my empirical studies. For example, it is widely believed in the CSP literature that forward checking and dynamic variable ordering are either as critical as, or perhaps even more critical than, the EBL/DDB
strategies (Bacchus & van Run, 1995; Frost & Dechter, 1994). Our results however show that for Graphplan, which uses the dynamic CSP model of search, DVO and FC are largely ineffective compared to EBL/DDB on the standard Graphplan. To some extent, this may be due to the fact that