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, ai$ \;\stackrel{{q}}{{\longrightarrow}}\;$aj, represents a commitment by the planner that precondition q of action aj is to be fulfilled by an effect of action ai.

An open condition, $ \;\stackrel{{q}}{{\longrightarrow}}\;$ai, is a precondition q of action ai that has not yet been linked to an effect of another action. An unsafe link (or threat) is a causal link, ai$ \;\stackrel{{q}}{{\longrightarrow}}\;$aj, whose condition q unifies with the negation of an effect of an action that could possibly be ordered between ai and aj. 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 a0 $ \prec$ a$\scriptstyle \infty$, where the effects of a0 represent the initial conditions of the problem and the preconditions of a$\scriptstyle \infty$ represent the goals of the problem. The procedure MAKE-INITIAL-PLAN used in Algorithm 1 returns the plan $ \langle${a0, a$\scriptstyle \infty$},$ \emptyset$,{a0 $ \prec$ a$\scriptstyle \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.


\begin{algorithm}
% latex2html id marker 102\caption{Generic POCL planning alg...
...textbf{return} failure (problem lacks solution)
\end{algorithmic}\end{algorithm}

An open condition, $ \;\stackrel{{q}}{{\longrightarrow}}\;$ai, can be resolved by linking q to the effect of an existing or new action. An unsafe link, ai$ \;\stackrel{{q}}{{\longrightarrow}}\;$aj threatened by the effect p of action ak, can be resolved by either ordering ak before ai (demotion), or by ordering ak after aj (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).

Håkan L. S. Younes
2003-08-26