# 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 ,,,, where is a set of actions, a set of causal links, a set of ordering constraints defining a partial order on the set , and a set of binding constraints on the action parameters ( = 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, aiaj, 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, 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, aiaj, 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 is the union of open conditions and unsafe links: () = () ().

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 and a set of goals , and is represented by an initial plan with two dummy actions a0 a, where the effects of a0 represent the initial conditions of the problem and the preconditions of a represent the goals of the problem. The procedure MAKE-INITIAL-PLAN used in Algorithm 1 returns the plan {a0, a},,{a0 a},. A set of generated, but not yet visited, partial plans is kept. At each stage in the planning process, a plan is selected and removed from , and then a flaw is selected for that plan. All possible refinements resolving the flaw (returned by the procedure REFINEMENTS) are added to , and the process continues until is empty (indicates failure) or a plan without flaws is found.

An open condition, ai, can be resolved by linking q to the effect of an existing or new action. An unsafe link, aiaj 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