corresponding to the preconditions and positive effects of [a] are in A, together with the edges connecting them to a Notice that an action graph can represent an invalid plan for the problem under consideration, since it may contain some inconsistencies, i.e., an action with precondition nodes that are not supported, or a pair of action nodes involved in a mutex relation. In general, a precondition node q at a level i is supported in an action graph A of G if either (i) in A
there is an action node at level i - 1 representing an action with (positive) effect [q], or (ii) i = 1 (i.e., [q] is a proposition of the initial state). An action graph without inconsistencies represents a valid plan and is called a solution graph.

Definition 2 A solution graph for G is an action graph A s of G such that all precondition nodes of the actions in A g are supported, and there is no mutex relation between action nodes of A s .

For large planning problems the construction of the planning graph can be computationally very expensive, especially because of the high number of mutex relations. For this reason our planner considers only pairs of actions that are persistently mutex, derived using a dedicated algorithm given in Appendix A. An experimental comparison with IPP's implementation of the planning graph construction (Koehler, Nebel, Hoffmann, & Dimopoulos, 1997) showed that in practice our method for deriving mutex relations is considerably more efficient than the "traditional" method for deriving the mutex relations in the fixed-point level of the graph. Moreover, for the problems that we tested, our method derived all the persistent mutex relations found by the traditional method.

The definition of action graphs and the notion of supported facts can be made stronger by observing that the effects of an action node can be automatically propagated to the next levels of the graph through the corresponding no-ops, until there is an interfering action blocking the propagation (if any), or the last level of the graph has been reached. The use of the no-op propagation, that we presented in previous work (Gerevini & Serina, 2002), leads to a smaller search space and can be incorporated into the definition of action graph.

Definition 3 An action graph with propagation is an action graph A such that if a is an action node of A at a level l, then, for any positive effect [e] of [a] and any level l' > l of A, the no-op of e at level l' is in A, unless there is another action node at a level l''
(l ≤ l" < l') which is mutex with the no-op.

Since in the rest of this paper we consider only action graphs with propagation, we will abbreviate their name simply to action graphs (leaving implicit that they include the no-op propagation).

In most of the existing planners based on planning graphs, when the search for a solution graph fails, G is iteratively expanded by adding an extra level and performing a new search using the resulting graph. In systematic planners like GRAPHPLAN (Blum & Furst, 1997), STAN (Fox & Long, 1998b) and IPP (Koehler et al., 1997) the search fails when there exists no solution graph, while in planners that use local search like BLACKBOX (Kautz & Selman, 1999) or GPG (Gerevini & Serina, 1999) the search fails when a certain search limit is exceeded. As we will show, in LPG there is no need to explicitly treat this kind of search failure, since the size of the graph is incrementally increased during search (i.e., the graph extension can be part of a local search step).