Flaw Selection Strategies

In the original implementations of SNLP and UCPOP threats are selected before open conditions. When there is more than one threat (or open condition) that can be selected, the one added last is selected first (LIFO order). Several alternative flaw selection strategies have been proposed in an attempt to improve the performance exhibited by POCL planners.

Peot and Smith (1993) show that the number of searched plans can be reduced by delaying the resolution of some threats. The most successful of the proposed delay strategies are DSep, which delays threats that can be resolved through separation, and DUnf, which delays threats that can be resolved in more than one way.

Joslin and Pollack (1994) suggest that all flaws should be treated uniformly, and that the flaw with the least number of refinements should be selected first. Their flaw selection strategy, LCFR, can be viewed as an instance of the most-constrained-variable heuristic used in simple search rearrangement backtracking (Bitner & Reingold, 1975; Purdom, 1983). The main disadvantage with LCFR is that computing the repair cost for every flaw can incur a large overhead for flaw selection. This can lead to longer planning times compared to when using the default UCPOP strategy, even if the number of search nodes is significantly smaller with LCFR. A clever implementation of LCFR can, however, reduce the overhead for flaw selection considerably.

Schubert and Gerevini (1995) argue that a LIFO strategy for selecting open conditions helps the planner maintain focus on the achievement of a particular high-level goal. Their ZLIFO strategy is a variation of the DSep strategy, with the difference being that open conditions that cannot be resolved, or can be resolved in only one way, are selected before open conditions that can be resolved in more than one way. Gerevini and Schubert (1996) present results indicating that ZLIFO often needs to generate fewer plans than LCFR before a solution is found, and has a smaller overhead for flaw selection. These results are disputed by Pollack et al. (1997). They instead attribute much of the power of ZLIFO to its delaying of separable threats, and propose a variation of LCFR, LCFR-DSep, that also delays separable threats. Since we chose to work with ground actions at IPC3, separability was not an issue for us.