sented by this node respectively, we will use a to indicate both of them (the appropriate interpretation will be clear from the context).

## 3.1  Basic Search Procedure: Walkplan

Given a planning graph G , the local search process of LPG starts from an initial A-graph of G (i.e., a partial plan), and transforms it into a solution graph (i.e., a valid plan) through the iterative application of graph modifications improving the current partial plan.  The two basic modifications consist of an extension of the A-graph to include a new action node, or a reduction of the A-graph to remove an action node (and the relevant edges). 7  At any step of the search process, which produces a new A-graph, the set of actions that can be added or removed is determined by the inconsistencies that are present in the current A-graph.

The general scheme for searching for a solution graph (a final state of the search) consists of two main steps. The first step is an initialization of the search in which we construct an initial A-graph. The second step is a local search process in the space of all A-graphs, starting from the initial A-graph. We can generate an initial A-graph in several ways. Four possibilities that can be performed in polynomial time, and that we have implemented are:
an empty A-graph (i.e., containing only the no-ops of the facts in the initial state, and the special action nodes a start and aend ); a randomly generated A-graph; an A-graph where all precondition facts are supported, but in which there may be some violated mutex relations; and an A-graph obtained from an existing plan given as input to the process.  The last option is particularly useful in the plan optimization phase, as well as for solving plan adaptation problems (Gerevini & Serina, 2000). In the current version of LPG, the default initialization strategy is the empty action graph with the fixed-point level as the last level of the graph. Further details on the initialization step can be found in earlier papers on planning through local search and action graphs (Gerevini & Serina, 1999, 2000).

Once we have computed an initial A-graph, each basic search step selects an inconsistency in the current A-graph. If this is an unsupported fact node, then in order to resolve (eliminate) it, we can either add an action node that supports it, or we can remove an action node that is connected to that fact node by a precondition edge. If the chosen inconsistency is a mutex relation, then we can remove one of the action nodes of the mutex relation. Note that the elimination of an action node can remove several inconsistencies (e.g., all those corresponding to the unsupported preconditions of the action removed). On the other hand, obviously the addition of an action node can introduce several new inconsistencies.  The strategy for selecting the next inconsistency to handle may have a significant impact on the overall performance (this has been extensively studied in the context of causal-link partialorder planning, e.g., Pollack, Joslin, & Paolucci, 1997; Gerevini & Schubert, 1996).  Our planner includes several strategies that we are currently testing. The default strategy that we used in the 3rd IPC and in all experiments presented in Section 4, prefers inconsistencies appearing at the earliest level of the graph.

Given an action graph A and an inconsistency σ in A, the neighborhood N(σ, A) of σ in A is the set of A-graphs obtained from A by applying a graph modification that resolves