From the first observation, the estimated cheapest cost of achieving a given goal g at time point tg is C(**g, t**g). We do not need to look at the value of C(**g, t**) at time point **t < t**g. The second observation helps us in efficiently evaluating the heuristic value for an objective function f involving both time and cost. Specifically, we need compute f at only the (finite number of)time points where the cost function of some fact or action changes. We will come back to the details of the heuristic estimation routines in Section 4.

Returning to our running example, Figure 6 shows graphically the earliest time point at which each action can be applied (C(**A, t**) < ∞) and Figure 7 shows how the cost function of facts/actions change as the time increases. Here is an outline of the update process in this example: at time point t = 0, four actions can be applied. They are D
c1 t→p
, D
c2 t→p
, D
c1 t→lv, D
c2 t→la. These actions add 4 events into the event queue Q = {e1 = hat **phx, t** = 1.0, c = 2.0, Dc1 t→p i, e2 = hat phx, 1.5, 1.5, Dc2 t→p i, e3 = hat lv, 3.5, 3.0, Dc1 t→lv i, e4 = hat la, 7.0, 6.0, Dc2 t→lai}. After we advance the time to t =
1.0, the first event e1 is activated and C(at **phx, t**) is updated. Moreover, because at phx is a precondition of Fp→la, we also update C(Fp→la, t) at te = 1.0 from ∞ to 2.0 and put an event e = hat la, 2.5, 8.0, Fp→lai, which represents Fp→la's effect, into Q. We then go on with the second event hat phx, 1.5, 1.5, Dc2 t→p i and lower the cost of the fact at phx and action Fp→la. Event e = hat la, 3.0, 7.5, Fp→lai is added as a result of the newly improved cost of Fp→la. Continuing the process, we update the cost function of at la once at time point t = 2.5, and again at t = 3.0 as the delayed effects of actions Fp→la occur. At time point t = 3.5, we update the cost value of at lv and action Tlv→la and introduce the event e = hat la, 6.0, 5.5, Tlv→lai. Notice that the final event e
′ = hat la, 7.0, 6.0, Dc2 t→lai representing a delayed effect of the action D
c2 t→la applied at t = 0 will not cause any cost update. This is because the cost function of at la has been updated to value c = 5.5 < ce
′ at time t = 6.0 < te
′ = 7.0.

Besides the values of the cost functions, Figure 7 also shows the supporting actions (SA(**f, t**),
defined in Section 3.1) for the fact (goal) at la. We can see that action Tlv→la gives the best cost of C(at **la, t**) = 5.5 for t ≥ 6.0 and action Fp→la gives best cost C(at **la, t**) = 7.5 for 3.0 ≤ t < 5.5 and C(at **la, t**) = 8.0 for 2.5 ≤ t < 3.0. The right most graph in Figure 7 shows similar cost functions for the actions in this example. We only show the cost functions of actions Tlv→la and Fp→la because the other four actions are already applicable at time point t**init** = 0 and thus their cost functions stabilize at 0.

## 3.3 Termination Criteria For The Cost Propagation Process

In this section, we discuss the issue of when we should terminate the cost propagation process. The first thing to note is that cost propagation is in some ways inherently more complex than makespan propagation. For example, once a set of literals enter the planning graph (and are not mutually exclusive), the estimate of the makespan of the shortest plan for achieving them does not change as we continue to expand the planning graph. In contrast, the estimate of the cost of the cheapest plan for achieving them can change until the planning graph levels off. This is why we need to carefully consider the effect of different criteria for stopping the expansion of the planning graph on the accuracy of the cost estimates. The first intuition is that we should not stop the propagation when there exist top level goals for which the cost of achievement is still infinite (unreached goal). On the other hand, given our objective function of finding the cheapest way to achieve the goals, we need not continue the propagation when there is no chance that we can improve the cost of achieving