probability p one of the graphs in N ( σ, A ) is chosen randomly, and with probability 1 - p the next A-graph is chosen according to the minimum value of the evaluation function.

If a solution graph is not reached after a certain number of search steps ( max_steps ), the current A-graph and max steps are reinitialized, and the search is repeated up to a userdefined maximum number of times ( max_restarts ). Figure 2 gives a formal description of Walkplan with restarts.

Gerevini and Serina (2002) proposed some heuristic functions for evaluating the search nneeeiiiibbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb more powerful heuristic functions for LA-graphs and TA-graphs.  These techniques are implemented in the latest version of our planner and were used in the 3rd IPC.

## 3.2 Neighborhood And Heuristics For Temporal Action Graphs

The search neighborhood for an inconsistency σ in an LA-graph A is the set of LA-graphs that can be derived from A by adding an action node supporting σ, or removing the action with precondition σ (in linear graphs the only type of inconsistencies are unsupported preconditions). An action a supporting σ can be added to A at any level l preceding the level of σ, and such that the desired effect of α is not blocked before or at the level of σ
(assuming that the underlying planning graph contains a at level l ). The neighborhood for σ contains a linear action graph for each of these possibilities.

Since at any level of an LA-graph there can be at most one action node (plus any number of no-ops), when we remove an action node from A , the corresponding action level becomes
"empty" (i.e., it contains only no-ops). 9  If the LA-graph contains adjacent empty levels, and in order to resolve the selected inconsistency a certain action node can be added at any of these levels, then the corresponding neighborhood contains only one of the resulting graphs.

When we add an action node to a level l that is not empty, the LA-graph is extended by one level, all action nodes from l are shifted forward by one level, and the new action is inserted at level l (Figure 8 in Section 3.4 gives an example). Moreover, when we remove an action node a from the current LA-graph, we can also remove each action node b supporting only the preconditions of a . Similarly, we can remove the actions supporting only the preconditions of b, and so on.  While this induced pruning is not necessary, an experimental analysis showed that it tends to produce better quality plans more quickly.

The elements of the neighborhood are evaluated according to an action evaluation function E estimating the cost of adding ( E ( a ) i ) or removing an action node a ( E ( a ) r ). In general, E consists of three weighed terms evaluating three aspects of the quality of the current plan that are affected by the addition/removal of a :

$$E(\,a\,)=$$
$$\;,\;\left\{\begin{array}{l l}{E(a)^{i}=\alpha\cdot E x e c u t i o n_{\pounds}o s t(a)^{i}+\beta\cdot T e m p o r a l_{\pounds}o s t(a)^{i}+\gamma\cdot S e a r c h_{\pounds}o s t(a)^{i}+\beta\cdot E x e c u t i o n_{\pounds}o s t(a)^{i}+\beta\cdot T e m p o r a l_{\pounds}o s t(a)^{i}+\gamma\cdot S e a r c h_{\pounds}o s t(a)^{i})}\end{array}\right.$$

The first term of E estimates the increase of the plan execution cost ( Execution cost ),
the second estimates the end time of a ( Temporal cost ), and the third estimates the increase