Threat Preference and Delay

The original SNLP algorithm [McAllester & Rosenblitt, 1991] adopted a flaw selection strategy in which threats are resolved before open conditions, and early versions of the widely used UCPOP planning system [Penberthy & Weld, 1992] did the same. SNLP does not specify a principle for selecting among multiple threats or multiple opens; UCPOP used LIFO for this purpose. Employing the notation above, we can describe the basic UCPOP strategy as:

UCPOP {n,s}LIFO/{o}LIFO

The first study of alternative flaw selection strategies was done by Peot and Smith (1993), who relaxed the requirement that threats always be resolved before open conditions, and examined several strategies for delaying the resolution of some threats. They analyzed five different strategies for delaying the repair of threats; of these, two are provably superior: DSep and DUnf.

DSep (Delay Separable Threats) was motivated by the observation that sometimes separable threats can simply disappear in the planning process as blocking variable bindings are introduced. As we pointed out earlier, nonseparable threats may also ``disappear'', but typically this is less frequent. Moreover, if the resolution of all threats--separable and nonseparable--were delayed, then nonseparable threats would only disappear early as a side effect of step reuse, making their disappearance even less frequent.

The DSep strategy therefore defers the repair of all separable threats until the very end of the planning process. However, like UCPOP, it continues to give preference to nonseparable threats:

DSep {n}LIFO/{o}LIFO/{s}LIFO

Actually, Peot and Smith do not specify a tie-breaking strategy for choosing among multiple threats; we have here indicated this as LIFO. They explored three different tie-breaking strategies for selecting open conditions (FIFO, LIFO, and least-cost); here we list LIFO, but one can also specify the alternatives:

DSep-LC {n}LIFO/{o}LC/{s}LIFO
DSep-FIFO {n}LIFO/{o}FIFO/{s}LIFO

Peot and Smith prove that the search space generated by a POCL planner using DSep will never be larger than the search space generated using the UCPOP strategy. This result holds when the tie-breaking strategy for open conditions is LIFO or FIFO, but not LC, a point we will return to later in the paper.

Peot and Smith's second successful strategy is DUnf (Delay Unforced Threats). It makes use of the notion of forced flaws. As we stated earlier, a flaw is forced if there is at most one possible way to repair it. The DUnf strategy delays the repair of all unforced threats:

DUnf {n,s}₀LIFO / {n,s}₁LIFO / {o}LIFO / {n,s}_2-infinityLIFO

We can define DUnf-LC and DUnf-FIFO in a manner analogous to that used for DSep-LC and DSep-FIFO:

DUnf-LC {n,s}₀LIFO / {n,s}₁LIFO / {o}LC / {n,s}_2-infinityLIFO
DUnf-FIFO {n,s}₀LIFO / {n,s}₁LIFO / {o}FIFO / {n,s}_2-infinityLIFO

Peot and Smith proved that the DUnf strategy would never generate a larger search space than either of the remaining two strategies that they examined. They also proved that that DSep and DUnf are incomparable: there exist planning problems for which DSep generates a smaller search space than DUnf, and other problems for which the reverse is true.

Peot and Smith support their theoretical results on DSep and DUnf with experiments showing that, at least for the domains they examined, these strategies can result in significant decrease in search-space size. The decrease in search is correlated with the difficulty of the problem, and consequently, as the problems get more difficult, these strategies reduce search time as well as space. That is, on large enough problems, they ``pay for'' their own overhead.

In follow-on work, Peot and Smith (1994) describe a strategy called DMin, which generates smaller search spaces than both DSep and DUnf. DMin combines a process of pruning dead-end nodes with the process of flaw selection. It gives preference to forced threats. If there are no forced threats, it checks to see whether all the remaining nonseparable threats could be repaired simultaneously. If so, it leaves them as threats, and selects an open condition to repair; if there are no open conditions, then presumably it selects a remaining unforced threat to repair. On the other hand, if it is impossible to repair all the unforced, nonseparable threats, then the node is a dead end, and can be pruned from the search space. Note that some dead-end nodes can be recognized immediately, even without doing the complete consistency checking of DMin. This is because an unrepairable flaw cannot subsequently become repairable, hence, any node containing a flaw with repair cost of zero is a dead end. Consequently, all flaw selection strategies should give highest priority to such flaws [Joslin & Pollack, 1996, Joslin, 1996].