VHPOP extends the capabilities of classical POCL planners by also **supporting planning**
with durative actions. This is accomplished by adding a simple temporal network **(STN)**
(Dechter, Meiri, & Pearl, 1991) to the regular plan representation of a POCL planner. The STN records temporal constraints between actions in a plan, **and supersedes the simple** ordering constraints usually recorded by POCL planners. The use of STNs permits actions with interval constraints on the duration (a feature that was not utilized by any of the domains at IPC3 that VHPOP **could handle). The approach we take to temporal POCL**
planning is essentially the same as the constraint-based interval approach described by Smith, Frank, and J´onsson (2000), and similar techniques for handling durative actions in a POCL framework can be traced back at least to Vere's DEVISER **(Vere, 1983).**
Our contribution to temporal POCL planning is demonstrating that the same heuristic techniques shown to boost the performance of classical POCL **planning can also be effective**
in domains with durative actions, validating the feasibility of the POCL paradigm for temporal planning on a larger set of benchmark problems than **has been done before.**

## 2. 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 hA,L, O,Bi, where A **is a set of actions,**
L a set of causal links, O **a set of ordering constraints defining a partial order on the set** A, and B a set of binding constraints on the action parameters (B = ∅ **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, aiq
−→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**,q
−→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,** aiq
−→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 π **is the union of open conditions and unsafe**
links: F(π) = OC(π) **∪ UL**(π).

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** I
and a set of goals G**, 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 h{a0, a∞}, ∅, {a0 ≺ a∞}, ∅i. A set 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 P**, and then a flaw is selected for that plan. All possible refinements**
resolving the flaw (returned by the procedure Refinements) are added to P**, and the**
process continues until P **is empty (indicates failure) or a plan without flaws is found.**