Walkplan(Π, max_steps, max_restarts, p)
Input : A planning problem II, the maximum number of search steps max_steps ,
the maximum number of search restarts max_restarts , a noise factor p (0 ≤ p ≤ 1).

Output : A solution graph representing a plan solving Π or f ail .

1.  for i ← 1  to max restarts do 2.

A ← an initial A-graph derived from the planning graph of Π ;
3.

for j ← 1 to max_steps do 4.

if A is a solution graph then 5.

return A
6.

σ ← an inconsistency in A ;
7.

N(σ, Α) ← neighborhood of A for σ; if 3 A ′ E N (σ, A) such that the quality of A ′ is not worse than the quality of A
8.

9.

then A ← A ′ (if there is more than one A ′ -graph, choose randomly one)
10.

else if random < p then 11.

A ← an element of N (σ, A) randomly chosen 12.

else A ← best element in N(σ, Α);
13. return fail. Figure 2: General scheme of Walkplan with restarts. random is a randomly osen value between 0 and 1. The quality of an action graph in the neighborhood is measured using an evaluation function estimating the cost of the graph modification used to generate it from the current action graph.

σ. At each step of the local search scheme, the elements of the neighborhood are evaluated according to a function estimating their quality, and an element with the best quality is then chosen as the next possible A-graph (search state). The quality of an A-graph depends on a number of factors, such as the number of inconsistencies and the estimated number of search steps required to resolve them, the overall cost of the actions in the represented plan and its makespan. 8 Gerevini and Serina (1999) proposed three general strategies for guiding the local search:
Walkplan, Tabuplan and T-Walkplan. In this paper we focus on Walkplan, which is the strategy used by LPG in the 3rd IPC, as well as in the experimental tests presented in Section 4. Walkplan is similar to Walksat, a stochastic local search method for solving propositional sssee to the state of the element in the neighborhood is the A-graph which has the lowest decrease of quality with respect to the current A-graph, i.e., it does not consider possible improvements. Like Walksat, our strategy uses a noise parameter p. Given an A-graph A and an inconsistency σ, if there is a modification for σ that does not decrease the quality of A , then this modification is performed, and the resulting A-graph is chosen as the next A-graph; otherwise, with