The simple example above shows that makespan and execution cost, while nominally independent of each other, are nevertheless related in terms of the overall objectives of the user and the constraints on a given planning problem. More specifically, for a given makespan threshold (e.g.

to be in LA within six hours), there is a certain estimated solution cost tied to it (shuttle fee and ticket price to LA) and analogously for a given cost threshold there is a certain estimated time tied to it. Thus, in order to find plans that are good with respect to both cost and makespan, we need to develop heuristics that track cost of a set of (sub)goals as a function of time.

Given that the planning graph is an excellent structure to represent the relation between facts and actions (c.f., Nguyen et al., 2001), we will use a temporal version of the planning graph structure, such as that introduced in TGP (Smith & Weld, 1999), as a substrate for propagating the cost information. In Section 3.1, we start with a brief discussion of the data structures used for the cost propagation process. We then continue with the details of the propagation process in Section 3.2, and the criteria used to terminate the propagation in Section 3.3.

## 3.1 The Temporal Planning Graph Structure

We now adapt the notion of temporal planning graphs, introduced by Smith and Weld (1999), to our action representation. The temporal planning graph for a given problem is a bi-level graph, with one level containing all *facts*, and the other containing all *actions* in the planning problem. Each fact has links to all actions supporting it, and each action has links to all facts that belong to its precondition and effect lists.4 Actions are durative and their effects are represented as events that occur at some time between the action's start and end time points. As we will see in more detail in the later parts of this section, we build the temporal planning graph by incrementally increasing the time (makespan value) of the graph. At a given time point t, an action A is activated if all preconditions of A can be achieved at t. To support the *delayed effects* of the activated actions (i.e.,
effects that occur at the *future* time points beyond t), we also maintain a global event queue for the entire graph, Q = {e1, e2**, ...e**n} sorted in the increasing order of event time. The event queue for the temporal graph differs from the event queue for the search state (discussed in the previous section) in the following ways:
- It is associated with the whole planning graph (rather than with each single state).

- It only contains the *positive* events. Specifically, the negative effects and the resource-related effects of the actions are not entered in to the graph's queue.

- All the events in Q have *event costs* associated with each individual event (see below).
Each event in Q is a 4-tuple e = h**f, t, c, A**i in which: (1) f is the fact that e will add; (2) t is the time point at which the event will occur; and (3) c is the cost incurred to enable the execution of action A which causes e. For each action A, we introduce a cost function C(**A, t**) = v to specify the estimated cost v that we incur to enable A's execution at time point t. In other words, C(**A, t**)
is the estimate of the cost incurred to achieve all of A's preconditions at time point t. Moreover, each action will also have an *execution cost* (C**exec**(A)), which is the cost incurred in executing A