Node and Flaw Selection next up previous
Next: Notation Up: Background Previous: Background  

Node and Flaw Selection

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 gif is a generic POCL algorithm, in which we highlight the two search decisions.gif 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.

   

POCL (init,goal)
dummy-plan <- make-skeletal-plan (init,goal)
nodes <- dummy-plan
While nodes is not empty do:
CHOOSE (and remove) a partial plan P from nodes. (Node Selection)
If P has no flaws
then return P
else do:
SELECT a flaw from P. (Flaw Selection)
Add all refinements of P to nodes.
Return failure (because nodes has become empty without a flaw-free plan being found.)

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 S1 with effect E, and a causal link <S2,F,S3>, where E and F are complementary literals that necessarily unify: either they are complementary ground literals (E = ¬F), or else they are complementary literals where each of E's variables is identical with, or forced by a binding constraint to be equivalent to the variable in the same position in F (e.g., E = p(x,y) and F = ¬p(x,y) , where there is currently a binding constraint that y = z).gif

Nonseparable threats can be repaired in at most two ways: by promoting S1, requiring it to occur after S3, or by demoting it, requiring it to occur before S2. 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.gif Over time, the repair cost for an unresolved nonseparable threat can only decrease.

A separable threat consists of a step S1 with an effect E, and a causal link <S2,F,S3>, where E and F are complementary literals that can be unified, but where such a unification is not forced (e.g., where E=p(x) and F=p(y) and there does not exist a binding constraint x=y). In such circumstances, the threat may disappear if a subsequent variable binding blocks the unification. (A nonseparable threat may also disappear if a subsequent ordering constraint has the effect of imposing promotion or demotion.) The repair cost for a separable threat may be higher than that for an nonseparable threat: not only can promotion and demotion be used, but so can separation, which involves forcing a variable binding that blocks the unification. Separation can introduce one repair for each unbound variable in the threat. For example, if the effect P(x,y,z) threatens <S2,¬P(t,u,v),S3>, there are three possible repairs: x<>t, y<>u, z <> v and . As with nonseparable threats, the repair cost for a separable threat that remains unresolved can only decrease over time.


next up previous
Next: Notation Up: Background Previous: Background

TOM Conversion
Wed Jun 25 17:40:58 EDT 1997