that were used in the 3rd IPC to handle domains specified in the recent PDDL2.1 language supporting "durative actions" and numerical quantities (Fox & Long, 2003).

The general search scheme of our planner is Walk-plan, a stochastic local search procedure similar to the well-known Walk-sat (Selman, Kautz, & Cohen, 1994).  Two of the most important extensions on which we focus in this paper concern the use of temporal action graphs (TA-graphs), instead of simple A-graphs, and some new techniques to guide the local search process. In a TA-graph, action nodes are marked with temporal values estimating the earliest time when the corresponding action terminates, while fact nodes are marked with temporal values estimating the earliest time when the corresponding fact becomes true. A set of ordering constraints is maintained during search to handle mutually exclusive actions, and to represent the temporal constraints implicit in the "causal" relations between actions in the current plan.

The new heuristics exploit some reachability information to weigh the elements (TA-
graphs) in the search neighborhood that resolve an inconsistency selected from the current TA-graph. The evaluation of these TA-graphs is based on the estimated number of search steps required to reach a solution (a valid plan), its estimated makespan, and its estimated execution cost. LPG is an incremental planner, in the sense that it produces a sequence of valid plans each of which improves the quality of the previous ones.  Plan quality is modeled by execution and temporal costs in a flexible way (the user can determine the relative importance of the plan quality criteria).

In the 3rd IPC, our planner demonstrated excellent performance on a large set of test problems in terms of both speed to compute the first solution and quality of the best solution computed by the incremental process. LPG was the fully-automated planner that solved the greatest number of problems, and the one with the highest success ratio between attempted problems and solved problems.

The paper is organized as follows. Section 2 presents the action and plan representation used in the competition version of LPG . Section 3 describes LPG 's local search neighborhood, some new heuristics for temporal action graphs, and the techniques for computing the reachability and temporal information used in these heuristics. Moreover, in this section we describe how LPG handles numerical variables and the incremental process to produce good quality plans. Section 4 presents the results of an experimental analysis using the test problems of the 3rd IPC, and illustrating the efficiency of our approach especially for temporal planning.  Section 5 gives conclusions, and mentions current and future work. Finally, a collection of appendices describes lpg's algorithm for computing the mutual exclusion relations used during search, and gives details about some of the experimental results presented in Section 4.

## 2.  Action And Plan Representation

In this section we introduce our graph-based representations for STRIPS and temporal plans, which can be seen as an elaboration of planning graphs (Blum & Furst, 1997).

## 2.1  Planning  Graphs And  Actions  Graphs

A planning graph is a directed acyclic levelled graph with two kinds of nodes and three kinds of edges. The levels alternate between a fact level, containing fact nodes, and an action