Although the main ideas of POCL planning have been in the literature for more than two decades, serious efforts at comparing alternative plan generation algorithms have been relatively recent. What made these comparisons possible was the development of a set of clear algorithms with provable formal properties, notably TWEAK [Chapman, 1987], and SNLP [McAllester & Rosenblitt, 1991]. These algorithms were not intended to add functionality to known planning methods, but rather to capture the essential elements of these known methods in a readily analyzable fashion.

In analyzing POCL algorithms, researchers have found it useful to
decouple the search control strategy from the underlying plan
refinement process. Figure is a generic POCL
algorithm, in which we highlight the two search
decisions. Following convention, we use **
CHOOSE** to indicate that node selection is a backtracking point, and
**SELECT** to indicate that flaw selection is not. A given
node may not lead to a solution, and so it may be necessary to backtrack and
consider alternative nodes. On the other hand, if a node does lead to
a solution, that solution will be found regardless of the order in
which its flaws are selected. See Weld's (1994) tutorial paper
for more discussion of this difference.

**Figure:** The Basic POCL Planning Algorithm

The generic algorithm sketched in the figure must be supplemented with
search strategies that implement the **CHOOSE** and **SELECT**
operators. Most POCL algorithms perform node selection using a
best-first ranking that computes some function of the number of steps
(denoted *S*), open conditions (*OC*), and unsafe conditions (*UC*,
*i.e.*, threats) in the partial plan. Gerevini and Schubert
(1996) have argued that, in general, only steps and
open conditions should be included in the ranking function, and we
adopt that strategy in our experiments, except where otherwise
indicated.

Having chosen a node, a POCL planning algorithm must then select a
flaw--open condition or threat--within that node to repair. Open
conditions are repaired by *establishment*, which consists either
in adding a new step that has a unifying condition as an effect (along
with a causal link from that new step to the condition), or else in
simply adding a new causal link from an existing step with a unifying
effect. We use the term *repair cost* to denote the number
of possible ways to repair a flaw.

For an open condition *o*, the repair cost *R*(*o*) is *I* + *S* + *N*,
where

*I* = the number of conditions in the initial state that unify with
*o* given the current binding constraints,

*S* = the number of
conditions in the effects of existing plan steps that unify with *o*
given the current binding constraints, counting only existing plan
steps that are not constrained to occur after the step associated with
*o*, and

*N* = the number of conditions in the effects of operators
in the library that unify with *o* given the current binding
constraints.

Note that over time, the repair cost for an open condition that is not resolved may either increase, as new steps that might achieve the condition are added to the plan, or decrease, as steps already in the plan are constrained by temporal ordering or variable binding so that they can no longer achieve the condition.

In considering the cost of threat repair, it is useful to distinguish
between *nonseparable* and *separable* threats. Nonseparable
threats consist of a step *S _{1}* with effect

Nonseparable threats can be repaired in at most two ways: by *
promoting* S_{1}, requiring it to occur after S_{3}, or by *
demoting* it, requiring it to occur before S_{2}. Of course, already
existing temporal ordering constraints may block one or both or these
repair options, which is why there are *at most* two possible
repairs.
Over time, the repair cost for an unresolved
nonseparable threat can only decrease.

A separable threat consists of a step S_{1} with an effect *E*, and a
causal link *<S _{2},F,S_{3}>*, where

Wed Jun 25 17:40:58 EDT 1997