ultimately, metric temporal planners need to deal with objective functions that are based on both makespan and cost. One recent research effort that recognizes the multi-objective nature of planning is the MO-GRT system (Refanidis & Vlahavas, 2001a). On one hand, the MO-GRT approach is more general than our approach in the sense that it deals with a set of non-combinable quality metrics. The MO-GRT approach however treats time similar to other consumable resources (with infinite capacity). Temporal constraints on the planning problems (such as when an effect should occur during the course of action), goal deadlines, or concurrency are *ignored* in order to scale down the problem to the classical planning assumptions. Metric-FF (Hoffmann, 2002) and MIPS
(Edelkamp, 2001) are two other forward state space planners that can handle resource constraints.

Both of them generate sequential plans. MIPS handles durative actions by putting in the action duration and post-processing the sequential p.c plans. Multi-Pegg (Zimmerman, 2002) is another recent planner that considers cost-time tradeoffs in plan generation. Multi-Pegg is based on the Graphplan approach, and focuses on classical planning problems with non-uniform cost actions.

ASPEN (Chien et al., 2000) is another planner that recognizes the multi-attribute nature of plan quality. ASPEN advocates an iterative repair approach for planning, that assumes the availability of a variety of hand-coded plan repair strategies and their characterization in terms of their effects on the various dimensions of plan quality. LPG (Gerevini & Serina, 2002) is another planner that employs local search techniques over the action-graph. Unlike ASPEN, LPG considers domain independent repair strategies that involve planning graph-based modifications.

Although we evaluated our cost-sensitive heuristics in the context of Sapa, a forward chaining planner, the heuristics themselves can also be used in other types of planning algorithms. For example, TGP can be made cost-sensitive by making it propagate the cost functions as part of planning graph expansion. These cost functions can then be used as a basis for variable and value ordering heuristics to guide its backward branch-and-bound search. A similar approach in classical planning has been shown to be successful by Kambhampati and Nigenda (2000).

Besides Graphplan-based approaches, our framework can also be used in both forward and backward state-space and partial order planners to guide the planning search. It is possible due to the fact that directional searches (forward/backward) all need to evaluate the distances between an initial state and a set of temporal goals.

Our work is also related to other approaches that use planning graphs as the basis for deriving heuristic estimates such as Graphplan-HSP (Kambhampati & Nigenda, 2000), AltAlt (Nguyen et al., 2001), RePOP (Nguyen & Kambhampati, 2001), and FF (Hoffmann & Nebel, 2001). In the context of these efforts, our contribution can be seen as providing a way to track cost as a function of time on planning graphs. An interesting observation 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 needed to carefully consider the effect of different criteria for stopping the expansion of the planning graph on the accuracy of the cost estimates (Section 3.3).

Another interesting point is that within classical planning, there was often a confusion between the notions of cost and makespan. For example, the "length of a plan in terms of number of actions" can either be seen as a cost measure (if we assume that actions have unit costs), or a makespan measure (if we assume that the actions have unit durations). These notions get teased apart naturally in metric temporal domains.