worse performance. In particular, instead of using the maximum of the heuristic minimum nmber of actions required to support each precondition a ′ , we tested the use of the sum of such numbers, which can give an overestimation of the actual search cost.  We have also tested a version of Bestaction which does not consider (iv), i.e., without the term
[ ] Threats (a') ]. While this simplified version is faster to compute, overall the performance of the planner was on average worse both in terms of CPU-time and quality of the plans produced (detailed results of this experiment are available from the web page of LPG ).

Steps 1, 4 and 13 of RelaxedPlan estimate the earliest time required to achieve all goals in G. This is recursively defined as the maximum of
(a) the times assigned to the facts in G that are already true in the state INIT i (step 1);

(b) the estimated earliest time T(g) required to achieve every fact g in G that is an effect of an action currently in ACTS (step 4);
(c) the estimated earliest time required to complete the execution of the actions chosen by Bestaction to achieve each of the remaining facts in G (step 13).
The T-times of (b) are computed by steps 9–10 from the relaxed subplan derived to achieve them. Clearly the algorithm terminates, because either every (sub)goal p is reachable from INIT t (i.e., Num acts(p,l) ≥ 0), or at some point bestact = 0 holds, forcing immediate termination (see footnote 12). Moreover, it can be proved that the complexity of the algorithm is polynomial in the number of actions and facts in the planning problem/domain.

## 3.2.2 An Example Illustrating Relaxedplan

Suppose we are evaluating the addition of a to the current TA-graph A illustrated in Figure For each fact that is used in the example, the tables of Figure 4 give the relative 4.

Num acts -value or the temporal value ( Num acts for the unsupported facts, Time for the other nodes). The Num acts -value for a fact belonging to INIT t is zero. The duration of the actions used in the example are indicated in the corresponding table of Figure 4. Solid circle and square nodes represent precondition and action nodes in AU{a}; dotted circle and square nodes represent the precondition and action nodes that are considered during the evaluation process; finally, the gray circle and square nodes represent the precondition and action nodes that are selected by RelaxedPlan.

First we describe the derivation of the sets of actions in the relaxed plan for Pre ( a ) and Threats(a), i.e.,
S1 = A set (Relaxed Plan(Pre(a), IN IT1, 0)) and S2 = A set (Relaxed Plan(T hr eats(a), I N I T i , S i ))
respectively. Then we describe the derivation of the estimation of the earliest time when all preconditions in Pre(a) can be achieved, i.e., End time(RelaxedPlan(Pre(a),INITi, 0)),
Actions for Pre(a) in the Relaxed Plan Pre(a) is {p1,p2,p3} but, since p2 E INIT1, in the first execution of RelaxedPlan step 2 removes p2 from G. So, only p1 and p3 are the goals of the relaxed problem. Suppose that in order to achieve p 1 we can use a 1 , a 2 or a 3 (forming the set A g examined by