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:
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 
, the strategy
that tends to generate the smallest search space achieves enough of a
reduction to pay for its own overhead, by and large.