Flaw Selection Strategies for Partial-Order Planning
  Several recent studies have compared the relative efficiency of alternative
flaw selection strategies for partial-order causal link (POCL) planning. We
review this literature, and present new experimental results that generalize
the earlier work and explain some of the discrepancies in it. In particular, we
describe the Least-Cost Flaw Repair (LCFR) strategy developed and analyzed by
Joslin and Pollack (1994), and compare it with other strategies, including
Gerevini and Schubert's (1996) ZLIFO strategy. LCFR and ZLIFO make very
different, and apparently conflicting claims about the most effective way to
reduce search-space size in POCL planning. We resolve this conflict, arguing
that much of the benefit that Gerevini and Schubert ascribe to the LIFO
component of their ZLIFO strategy is better attributed to other causes. We show
that for many problems, a strategy that combines least-cost flaw selection with
the delay of separable threats will be effective in reducing search-space size,
and will do so without excessive computational overhead. Although such a
strategy thus provides a good default, we also show that certain domain
characteristics may reduce its effectiveness.
