of the number of search steps needed to reach a solution graph ( Search cost ). The coefficients of these terms are used to normalize them, and to weigh their relative importance
(more on this in Section 3.6).

In the computation of the terms of E there is an important tradeoff to consider.  On one hand, an accurate evaluation of them could lead to valid plans of good quality within few search steps. On the other hand, the computation of E should be fast "enough", because the neighborhood could contain many elements, and an accurate evaluation of its elements could slow down the sear excessively. In the design of our heuristics for evaluating the terms of E we took this tradeoffinto account trying to find an appropriate balance between informativeness and efficiency of computation.

The evaluation of the terms of E is based on computing particular relaxed plans for achieving certain action preconditions in the context of the current TA-graph. In the next subsections, first we describe how these relaxed plans are derived, and then we give a detailed description of how the terms of E are defined using relaxed plans.

## 3.2.1 Relaxed Plans For Action Preconditions

Suppose we are evaluating the addition of at a level l of the current linear action graph A . The three terms of E are heuristically estimated by computing a relaxed plan π r containing a minimal set of actions for achieving (1) the unsupported preconditions of a and (2) the set E of preconditions of the other actions in the LA-graph that would become unsupported by adding a (because it would block the no-op propagation currently used to support such preconditions). This plan is relaxed because during its construction we do not consider the possible interference between actions resulting from delete-effects.

7r is computed in two stages. First we deal with the preconditions of type (1) and then with the preconditions of type (2). The generation of 7r depends on the actions in the current partial plan (the plan represented by A) in two ways:
- The actions in the current plan are used to define an initial state for the problems of achieving the preconditions of a and those in Σ . In particular, the relaxed subplan for the preconditions of a is computed from the state INIT t obtained by applying the actions in A up to level l - 1, ordered according to their corresponding levels. 10  The relaxed subplan for achieving Σ is computed from INIT t modified by the effects of a, and it can reuse the actions in the relaxed subplan previously computed for the preconditions of a .

- In the process of deriving a relaxed plan, when we choose an action, we consider its potential interference with the no-ops that support a precondition of some action in A at a level following l , and we prefer actions that do not block the propagation of such no-ops. The motivation is that taking these interferences into account during the construction of a relaxed plan can lead to a better estimate of the cost required to support preconditions of type (1) and (2) in the context of the search that we are conducting to transform the current action graph into a solution graph (more details below).