with EBL+DVO, and up to 1.2x speedup with EBL+FC+DVO, in several cases, the cpu times *increase* with FC and DVO. Once again, I attribute this to the overheads of forward checking (and to a lesser extent, of dynamic variable ordering). Most importantly, by comparing the results in the Tables 4 and 5, we can see that EBL/DDB capabilities are able to bring about significant speedups even over a Graphplan implementation using FC and DVO.

## 8. Ebl/Ddb & Randomized Search

Recent years have seen increased use of randomized search strategies in planning. These include both purely local search strategies (Gerevini, 1999; Selman, Levesque, & Mitchell, 1992) as well as hybrid strategies that introduce a random restart scheme on top of a systematic search strategy (Gomes et al., 1998). The BLACKBOX planning system (Kautz & Selman, 1999) supports a variety of random restart strategies on top of a SAT compilation of the planning graph, and empirical studies show that these strategies can, probabilistically speaking, scale up much better than purely systematic search strategies.

I wanted to investigate if (and by how much) EBL & DDB techniques will help Graphplan even in the presence of these newer search strategies. While EBL and DDB techniques have little applicability to purely local search strategies, they could in theory help random restart systematic search strategies. Random restart strategies are motivated by an attempt to exploit the "*heavytail*" distribution (Gomes et al., 1998) of the solution nodes in the search trees of many problems.

Intuitively, in problems where there are a non-trivial percentage of very easy to find solutions as well as very hard to find solutions, it makes sense to restart the search when we find that we are spending too much effort for a solution. By restarting this way, we hope to (probabilistically) hit on the easier-to-find solutions.

I implemented a random-restart strategy on top of Graphplan by making the following simple modifications to the backward search:
1. We keep track of the number of times the backward search backtracks from one level of the plan graph to a previous level (a level closer to the goal state), and whenever this number exceeds a given limit (called *backtrack limit*), the search is restarted (by going back to the last level of the plan graph), assuming that the number of restarts has not also exceeded the given limit. The search process between any two restarts is referred to as an *epoch*.

2. The supporting actions (values) for a proposition variable are considered in a randomized order. It is this randomization that ensures that when the search is restarted, we will look at the values of each variable in a different order.21
Notice that random-restart strategy still allows the application of EBL and DDB strategies, since during any given epoch, the behavior of the search is identical to that of the standard backward search algorithm. Indeed, as the backtrack limit and the number of restarts are made larger and larger, the whole search becomes identical to standard backward search.