In this paper, we have synthesized much of the previous work on flaw selection for partial-order causal link planning, showing how earlier studies relate to one another, and have developed a concise notation for describing alternative flaw selection strategies.
We also presented the results of a series of experiments aimed at clarifying the effects of alternative search-control preferences on search-space size. In particular, we aimed at explaining the comparative performance of the LCFR and ZLIFO strategies. We showed that neither of these flaw selection strategies consistently generates smaller search spaces, but that by combining LCFR's least-cost approach with the delay of separable threats that is included in the ZLIFO strategy, we obtain a strategy--LCFR-DSep--whose space performance was nearly always as good as the better of LCFR or ZLIFO on a given problem. We therefore concluded that much of ZLIFO's advantage relative to LCFR is due to its delay of separable threats rather than to its use of a LIFO strategy. Although we were unable to resolve the question of whether least-cost selection is required for unforced, as well as forced flaws, we found no evidence that a LIFO strategy for unforced flaws was better. On the other hand, separable-threat delay is clearly advantageous. An open question is exactly why it is so advantageous. We have conducted preliminary experiments that suggest that much of the search-space reduction that results from delaying separable threats can also be achieved by making separation systematic, something that UCPOP v.4 does not do.
We also considered the question of computation time, and showed that often LCFR-DSep only requires computation time comparable to that of ZLIFO. LCFR-DSep can therefore be seen as paying for its own computational overhead by its search-space reduction. Moreover, Peot and Smith's DSep-LC provides a good approximation of LCFR-DSep: although it produces somewhat larger search spaces, it does so more quickly.
These conclusions, however, are tempered by the fact that for certain clusters of problems, our combined strategy, LCFR-DSep, does not generate minimal search spaces. As we saw, for the Tileworld problems, what is most important is to recognize the need for a particular temporal ordering among plan steps, and this recognition can be obtained by resolving separable threats early. For the Trains and Get-Paid/Uget-Paid domains, what matters most is recognizing that a particular effect can in fact only be achieved in one way, and this is only recognized when a particular flaw is selected--a flaw which happens generally not to be the least cost flaw available. The lesson to be learned from these sets of problems is that although we now understand the reasons that LCFR and ZLIFO perform the way they do, and how to combine the best features of both to create good default strategies for POCL planning, it is clear that domain-dependent characteristics such as those we identified in the Trains and Tileworld domains must still be taken into account in settling on a flaw selection strategy for any domain.