approach of building a precedence-constrained plan from the position-constrained plan returned by Sapa. Section 7 discusses the implementation of Sapa, presents some empirical results where Sapa produces plans with tradeoffs between cost and makespan, and analyzes its performance in the 2002 International Planning Competition (IPC 2002). We present a discussion of the related work in Section 9 and conclude in Section 10.

## 2. Handling Concurrent Actions In A Forward State Space Planner

Sapa addresses planning problems that involve durative actions, metric resources, and deadline goals. In this section, we describe how such planning problems are represented and solved in Sapa. We first describe the action representation, and then present the forward chaining state search algorithm used by Sapa.

## 2.1 Action Representation & Constraints

Planning is the problem of finding a set of actions and the start times of their execution to satisfy all causal, metric, and resource constraints. In this section, we will briefly describe our representation, which is an extension of the action representation in PDDL2.1 Level 3 (Fox & Long, 2001), the most expressive representation level used in the third international competition. Our extensions to PDDL2.1 are: (i) interval preconditions; (ii) delayed effects that happen at time points other than action's start and end time points; (iii) deadline goals.

We shall start with an example to illustrate the action representation in a simple temporal planning problem. This problem and its variations will be used as the running examples throughout the rest of the paper. Figure 2 shows graphically the problem description. In this problem, a group of students in Tucson need to go to Los Angeles (LA). There are two car rental options. If the students rent a faster but more expensive car (*Car1*), they can only go to Phoenix (PHX) or Las Vegas
(LV). However, if they decide to rent a slower but cheaper *Car2*, then they can use it to drive to Phoenix or directly to LA. Moreover, to reach LA, the students can also take a *train* from LV or a flight from PHX. In total, there are 6 movement actions in the domain: *drive-car1-tucson-phoenix*
(D
c1 t→p
, Dur = 1.0, Cost = 2.0), *drive-car1-tucson-lv* (D
c1 t→lv, Dur = 3.5, Cost = 3.0), *drive-car2-*
tucson-phoenix (D
c2 t→p
, Dur = 1.5, Cost = 1.5), *drive-car2-tucson-la* (D
c2 t→la),*Dur = 7.0, Cost =*
6.0, fly-airplane-phoenix-la (Fp→la, *Dur = 1.5, Cost = 6.0*), and use-train-lv-la (Tlv→la, Dur = 2.5, Cost = 2.5). Each move action A (by car/airplane/train) between two cities X and Y requires the precondition that the students be at X (at(X)) at the beginning of A. There are also two temporal effects: ¬at(X) occurs at the starting time point of A and at(Y ) at the end time point of A. Driving and flying actions also consume different types of resources (e.g fuel) at different rates depending on the specific car or airplane used. In addition, there are refueling actions for cars and airplanes.

The durations of the refueling actions depend on the amount of fuel remaining in the vehicle and the refueling rate. The summaries of action specifications for this example are shown on the right side of Figure 2. In this example, the costs of moving by train or airplane are the respective ticket prices, and the costs of moving by rental cars include the rental fees and gas (resource) costs.

As illustrated in the example, unlike actions in classical planning, in planning problems with temporal and resource constraints, actions are not instantaneous but have durations. Each action A has a duration DA, starting time SA, and end time (EA = SA + DA). The value of DA can be statically defined for a domain, statically defined for a particular planning problem, or can be dynamically decided at the time of execution. For example, in the traveling domain discussed