subplan computed for the preconditions of a ), and Threats ( a 7 ) is empty, the best action chosen by RelaxedPlan to support q is a7. It follows that the set of actions returned by RelaxedPlan is {a1,a1,a5,a7}.

## Temporal Value For Pre(A)

We now consider the evaluation of the temporal value returned by RelaxedPlan( Pre ( a ),
INIT t (). According to the temporal values specified in the table of Figure 4, the value of t at step 1 is Time (p2) = 220. As illustrated above, RelaxedPlan for Pre (a) is recursively executed to evaluate the preconditions of a 1 (the action chosen to achieve p 1 ) and then of a 4 (the action chosen to achieve p4 ). In the evaluation of the preconditions of a4 , at step 1 of RelaxedPlan( Pre(a 4 ), INIT t , 0)) t is set to 50, i.e., the maximum value between Time(p 9 )
and Time(p10) and the algorithm returns (0, 50).

In the evaluation of the preconditions of a 1 , at step 1 of Relaxed Plan( Pre(a 1 ), INIT 1 , 0 ))
t is set to Time(p5) = 170, at step 8 RelaxedPlan(Pre(a4), INITi, 0)) returns (0,50), while steps 9–10 set T ( p 12 ) to 50+100 (the duration of a 4 ), and at step 13 t is set to MAX {170, 50+
100}. Hence, the recursive execution of Relaxed Plan applied to the preconditions of a 1 returns ({a 4 }, 170), and at step 13 of Relaxed Plan( Pre(a), I NITi, () t is set to MAX { 220, 170+ 70} = 240.

As we have seen in the first part of the example, the action chosen to support p3 is a5. The recursive execution of RelaxedPlan(Pre(a5),INITi, {a1, a4}) applied to the preconditions of a5 returns ({a1,a4}, 170). In fact, the only precondition of a5 that is not in INIT t ( p 12 ) is achieved by an action already in ACTS ( a t ).  Moreover, since T ( p 12 ) = 150 and Time (p 11 ) = 170, the estimated end time of a 5 is 170 + 30 = 200. At step 13 of RelaxedPlan( Pre (a), I NIT i , 0) t is then set to MAX {240, 200} and the output of Relaxed-
Plan is ({a1,a1,a5}, 240).

## 3.2.3 Estimating The Terms Of E

As noted before, the terms of the action evaluation function E are computed by using the relaxed (sub)plan π, for a set of preconditions. The number of actions in π, and the threats of these actions are used to define a heuristic estimate of the additional search cost that would be introduced by adding an action a to the current TA-graph, or removing it
(i.e., the Search cost terms of E ). Note that in general this is not an admissible heuristic, because it can overestimate the minimum number of search steps needed to cope with the inconsistency under consideration.

The Temporal cost term of E ( a ) is an estimation of the earliest time when the new action a would terminate, given the actions in π, and the earliest time when π, can be applied in the context of the current action graph. 13  The Temporal cost term of E ( a ) r is an estimation of the earliest time when all preconditions that would become unsupported by removing a from the current action graph could be supported again.

The Execution cost term of E ( a ) is an estimation of the additional execution cost that would be required to satisfy the preconditions of a , and is derived by summing the cost of each action a ′ in π r ( Cost ( a ′ )). The Execution cost term of E ( a ) ′ is estimated similarly by