case, where 0 **< α <** 1, then we have to find the time point t, τ0 ≤ t ≤ τ∞, such that ht(S) =
f(C(PS, t), t) = α.C(PS, t) + (1 − α).t has minimum value.9 In our ongoing example, given our goal of being in Los Angeles (at la), if α = 0, the heuristic value is h(S) = τ0 = 2.5 which is the earliest time point at which C(at **la, t**) < ∞. The heuristic value corresponds to the propagation through action chain (D
c1 t→p
, Fp→la). If α = 1 and **Deadline**(AtLA) ≥ 6.0, then h(S) = 5.5, which is the cheapest cost we can get at time point τ∞ = 6.0. This heuristic value represents another solution (D
c1 t→lv, Tlv→la). Finally, if 0 **< α <** 1, say α = 0.55, then the lowest heuristic value h(S) = α.C(PS, t) + (1 − α).t is h(S) = 0.55 ∗ 7.5 + 0.45 ∗ 3.0 = 5.47 at time point 2.5 < t = 3.0 < 6.0. For α = 0.55, this heuristic value h(S) = 5.47 corresponds to yet another solution involving driving part way and flying the rest: (D
c2 t→p
, Fp→la).

Notice that in the general case where 0 **< α <** 1, even though time is measured continuously, we do not need to check every time point t: τ0 **< t < τ**∞ to find the value where h(S) = f(C(PS, t), t)
is minimal. This is due to the fact that the cost functions for all facts (including goals) are *step* functions. Thus, we only need to compute h(S) at the time points where one of the cost functions C(gi, t) changes value. In our example above, we only need to calculate values of h(S) at τ0 = 2.5, t = 3.0 and τ∞ = 6.0 to realize that h(S) has minimum value at time point t = 3.0 for α = 0.55.

Before we end this section, we note that when there are multiple goals there are several possible ways of computing C(PS) from the cost functions of the individual goals. This is a consequence of the fact that there are multiple rules to propagate the cost, and there are also interactions between the subgoals. Broadly, there are two different ways to extract the plan costs. We can either directly use the cost functions of the goals to compute C(PS), or first extract a relaxed plan from the temporal planning graph using the cost functions, and then measure C(PS) based on the relaxed plan. We discuss these two approaches below.

## 4.1 Directly Using Cost Functions To Estimate C(Ps)

After we terminate the propagation using any of the criteria discussed in Section 3.3, let G =
{(g1, t1),(g2, t2)...(gn, tn)}, ti = **Deadline**(gi) be a set of goals and CG = {c1**, ...c**n|ci =
C(gi**, Deadline**(gi)} be their best possible achievement costs. If we consider G as the set of preconditions for a dummy action that represents the goal state, then we can use any of the propagation rules (max/sum) discussed in Section 3.2 to directly estimate the total cost of achieving the goals from the given initial state. Among all the different combinations of the propagation rules and the aggregation rules to compute the total cost of the set of goals G, only the *max-max* (maxpropagation to update C(gi, t), and cost of G is the maximum of the values of C(gi**, Deadline**(gi))
is admissible. The *sum-sum* rule, which assumes the total independence between all facts, and the other combinations are different options to reflect the dependencies between facts in the planning problem. The tradeoffs between them can only be evaluated empirically.