
## 2.2 Linear And Temporal Action Graphs

The first version of LPG (Gerevini & Serina, 2002) was based on action graphs where each level may contain an arbitrary number of action nodes, as in the usual definition of planning graph. The version of the system that participated in the 3rd IPC uses a restricted class of action graphs, called linear action graphs, combined with some additional data structures supporting a more expressive action and plan representation. In particular, the new system can handle actions having temporal durations and preconditions/effects involving numerical quantities, as specified in PDDL2.1 (Fox & Long, 2003). In this paper we focus mainly on planning for temporal domains, where LPG showed particularly good performance with respect to the other (fully-automated) participants of the 3rd IPC.

In order to keep the presentation simple, we describe our techniques considering mainly preconditions of type "over all" (i.e., preconditions that must hold during the whole action execution) and effects of type "at end" (i.e., effects that hold at the end of the action execution). 2 In Section 3.4 we discuss how we handle the other types of preconditions and effects in the test domains of the 3rd IPC.

Definition 4 A linear action graph (LA-graph) of G is an A-graph of G in which each level of actions contains at most one action node representing a domain action and any number of no-ops.

It is important to note that having only one action in each level of an LA-graph does not prevent the generation of parallel (partially ordered) plans. In fact, from any LA-graph we can easily extract a partially ordered plan where the ordering constraints are (1) those between mutex actions and (2) those implicit in the causal structure of the represented plan.

Regarding the first constraints, if a and b are mutex and the level of a precedes the level of b, then [a] is ordered before [b]; regarding the second constraints, if a has an effect node that is used (possibly through the no-ops) to support a precondition node of b, then [ a ] is ordered before [ δ ].  These causal relations between actions producing an effect and actions consuming it are similar to the causal links in partial-order planning (e.g., McAllester & Rosenblitt, 1991; Penberthy & Weld, 1992; Nguyen & Kambhampati, 2001). LPG keeps track of these relationships during search and uses them to derive some heuristic information useful for guiding the search (more details on this in the next section), as well as to extract parallel plans from the solution graph.

For temporal domains where actions have durations and plan quality mainly depends on the makespan, rather than on the number of actions or graph levels, the distinction between one action or more actions per level is scarcely relevant. The order of the graph levels should not imply any ordering of the actions (e.g., an action at a certain level could terminate before the end of an action at the next level).

Since in LA-graphs there is at most one action node for each level, and every inconsistency is an unsupported precondition, the use of this representation has some advantages over general A-graphs:
- LA-graphs can be represented by simpler data structures, which allow one to manage the no-op propagation, the inconsistency identification and selection, and the numerical effect propagation more efficiently.