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,
*a _{i}*

An *open condition*,
*a _{i}*, is a precondition

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
*a*_{0} *a*_{}, where the effects of *a*_{0} 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
{*a*_{0}, *a*_{}},,{*a*_{0} *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,
*a _{i}*, can be resolved by linking

Håkan L. S. Younes

2003-08-26