Experimental Comparison of Flaw next up previous
Next: Experimental Design Up: Flaw Selection Strategies For Previous: Threat Delays Revisited  

Experimental Comparison of Flaw Selection Strategies


As discussed in the previous section, several different proposals have been made in the literature about how best to reduce the size of the search space during POCL planning. These include:

Moreover, different strategies have combined these preference schemes in different ways, and apparently conflicting claims have been made about the effects of these preferences on search-space size.

To resolve these conflicts, we performed experimental comparisons of POCL planners using a variety of flaw selection strategies. We gave particular attention to the comparison of LCFR and ZLIFO, because of the their apparently conflicting claims. LCFR generates its search space treating all flaws uniformly, using a least-cost approach to choose among them. ZLIFO distinguishes between flaw types (non-separable threats, open conditions, and separable threats), and uses a modified LIFO approach to select among the flaws in each class. The original LCFR studies would have led us to predict that ZLIFO would generate larger search spaces than did LCFR, but Gerevini and Schubert found just the opposite to be true. We aimed, then, to explain this discrepancy.

Our principal focus was on search-space size, for two reasons. First, the puzzle raised by LCFR and ZLIFO is one of space, not time. As we mentioned earlier, it is easy to see why ZLIFO would be faster than LCFR, even on a per node basis. A least-cost strategy must compute repair costs, while ZLIFO need only pop a stack containing the right type of flaws. The puzzle for us was not why ZLIFO was faster, but why it generated smaller search spaces. Second, we believe that understanding the effect of search control strategies on search-space size can lead to development of approximation techniques that produce speed-up as well; the QLCFR strategy [Joslin & Pollack, 1994] and Srinivasan and Howe's strategies (1995) are examples of this.

However, a secondary goal was to analyze the time requirements of the strategies we compared, and we therefore collected timing data for all our experiments. As we discuss in Section gif, the strategy that tends to generate the smallest search space achieves enough of a reduction to pay for its own overhead, by and large.

next up previous
Next: Experimental Design Up: Flaw Selection Strategies For Previous: Threat Delays Revisited

TOM Conversion
Wed Jun 25 17:40:58 EDT 1997