and the set of preconditions of actions in RP that are not currently supported by facts in SF. The estimated heuristic value for the current (partial) relaxed plan and the current goal set is computed as follows: h(S) = h(RP) + h(G) in which h(RP) = f(C(RP), T(RP)). For the given set of goals G, h(G) = minτ0<t<τ∞ f(C(G, t), t) is calculated according to the approach discussed in the previous section (Section 4). Finally, C(RP) = PA∈RP C**exec**(A) and T(RP) is the makespan of RP, where actions in RP are aligned according to their causal relationship (see below). We will elaborate on this in the example shown later in this section.

At the start, G is the set of top level goals, RP is empty and SF contains facts in the initial state.

Thus C(RP) = 0, T(RP) = 0 and h(S) = h(G). We start the extraction process by backward search for the *least expensive* action A supporting the first goal g1. By least expensive, we mean that A contributes the smallest amount to the objective function h(S) = h(RP) + h(G) if A is added to the current relaxed plan. Specifically, for each action A that supports g1, we calculate the value hA(S) = h(RP + A) + h((G \ Effect(A)) S**P recond**(A)) which estimates the heuristic value if we add A to the relaxed plan. We then choose the action A that has the smallest hA(S) value.

When an action A is chosen, we put its preconditions into the current goal list G, and its effects into the set of supported facts SF. Moreover, we add a precedence constraint between A and the action A1 that has g1 as its precondition so that A gives g1 before the time point at which A1 needs it. Using these ordering relations between actions in RP and the mutex orderings discussed in Section 5.1, we can update the makespan value T(RP) of the current (partial) relaxed plan.

In our ongoing example, suppose that our objective function is h(S) = f(C(PS), T(PS)) =
α.C(PS)+(1−α).T(PS ), with α = 0.55 and the infinite-lookahead criterion is used to stop the cost propagation process. When we start extracting the relaxed plan, the initial setting is G = {at la},
RP = ∅ and SF = {at **tucson**}. Among the three actions D
c2 t→la, Tlv→la and Fp→la that support the goal at la, we choose action A = Fp→la because if we add it to the relaxed plan RP, then the estimated value hA(S) = h(RP + A) + h((G \ at la)Sat phx) = (α ∗ C**exec**(Fp→la) + (1 −
α) ∗ Dur(Fp→la)) + mint(f(C(at phx), t)) = (0.55*6.0 + 0.45*1.5) + (0.55*1.5 + 0.45*1.5) =
5.475. This turns out to be the smallest among the three actions. After we add Fp→la to the relaxed plan, we update the goal set to G = {at phx}. It is then easy to compare between the two actions D
c2 t→phx and D
c1 t→phx to see that D
c2 t→phx is cheaper for achieving *at-phx* given the value α = 0.55.

The final cost C(PS) = 6.0 + 1.5 = 7.5 and makespan of T(PS) = 1.5 + 1.5 = 3 of the final relaxed plan can be used as the final heuristic estimation h(S) = 0.55 ∗ 7.5 + 0.45 ∗ 3 = 5.475 for the given state.

Notice that in the relaxed-plan extraction procedure, we set the time points for the goal set to be the goal deadlines, instead of the latest time points where the cost functions for the goals stabilized. The reason is that the cost values of facts and actions *monotonically decrease* and the costs are *time-sensitive*. Therefore, the later we set the time points for goals to start searching for the relaxed plan, the better chance we have of getting the low-cost plan, especially when we use the k-lookahead approximation approach with k 6= ∞. In our ongoing example, if we use the zero-lookahead option to stop the propagation, we find that the smallest cost is C(in la) = 8.0 at t = 2.5. If we search back for the relaxed plan with the combination (in la, 2.5) then we would find a plan P1 = (D
c1 t→p
, Fp→la). However, if we search from the goal deadline, say t = 7.0, then we would realize that the lowest cost for the precondition in phx of Fp→la at t = 7.0 − 1.5 = 5.5 is C(in **phx,** 5.5) = 1.5 (caused by D
c2 t→p at time point t = 2.0) and thus the final plan is P2 =
(D
c2 t→p
, Fp→la) which is cheaper than P1.