Basic POCL Planning Algorithm

We briefly review how POCL planners work, and introduce the terminology used throughout this paper. For a thorough introduction to POCL planning, we refer the reader to the tutorial on least commitment planning by Weld (1994).

A (partial) plan can be represented by a tuple $\langle$$\mathcal {A}$,$\mathcal {L}$,$\mathcal {O}$,$\mathcal {B}$$\rangle$, where $\mathcal {A}$ is a set of actions, $\mathcal {L}$ a set of causal links, $\mathcal {O}$ a set of ordering constraints defining a partial order on the set $\mathcal {A}$, and $\mathcal {B}$ a set of binding constraints on the action parameters ( $\mathcal {B}$ = $\emptyset$ if ground actions are used). Each action a is an instance of some action schema A in the planning domain, and a plan can contain multiple instances of the same action schema. A causal link, a_i$\;\stackrel{{q}}{{\longrightarrow}}\;$a_j, represents a commitment by the planner that precondition q of action a_j is to be fulfilled by an effect of action a_i.

An open condition, $\;\stackrel{{q}}{{\longrightarrow}}\;$a_i, is a precondition q of action a_i that has not yet been linked to an effect of another action. An unsafe link (or threat) is a causal link, a_i$\;\stackrel{{q}}{{\longrightarrow}}\;$a_j, whose condition q unifies with the negation of an effect of an action that could possibly be ordered between a_i and a_j. The set of flaws of a plan $\pi$ is the union of open conditions and unsafe links: $\mathcal {F}$($\pi$) = $\mathcal {OC}$($\pi$) $\cup$ $\mathcal {UL}$($\pi$).

A POCL planner searches for a solution to a planning problem in the space of partial plans by trying to resolve all flaws in a plan. Algorithm 1 shows a generic procedure for POCL planning that given a planning problem returns a plan solving the problem (or failure if the given problem lacks a solution). A planning problem is a set of initial conditions $\mathcal {I}$ and a set of goals $\mathcal {G}$, and is represented by an initial plan with two dummy actions a₀ $\prec$ a_$\infty$, where the effects of a₀ represent the initial conditions of the problem and the preconditions of a_$\infty$ represent the goals of the problem. The procedure MAKE-INITIAL-PLAN used in Algorithm 1 returns the plan $\langle${a₀, a_$\infty$},$\emptyset$,{a₀ $\prec$ a_$\infty$},$\emptyset$$\rangle$. A set $\mathcal {P}$ of generated, but not yet visited, partial plans is kept. At each stage in the planning process, a plan is selected and removed from $\mathcal {P}$, and then a flaw is selected for that plan. All possible refinements resolving the flaw (returned by the procedure REFINEMENTS) are added to $\mathcal {P}$, and the process continues until $\mathcal {P}$ is empty (indicates failure) or a plan without flaws is found.

An open condition, $\;\stackrel{{q}}{{\longrightarrow}}\;$a_i, can be resolved by linking q to the effect of an existing or new action. An unsafe link, a_i$\;\stackrel{{q}}{{\longrightarrow}}\;$a_j threatened by the effect p of action a_k, can be resolved by either ordering a_k before a_i (demotion), or by ordering a_k after a_j (promotion). If we use lifted actions instead of ground actions, a threat can also be resolved by adding binding constraints so that p and ¬q cannot be unified (separation).