In this paper, we concentrated on developing heuristics that can be sensitive to multiple dimensions of plan quality (specifically, makespan and cost). An orthogonal issue in planning with multiple criteria is how the various dimensions of plan quality should be combined during optimization. The particular approach we adopted in our empirical evaluation–namely, considering a linear combination of cost and time–is by no means the only reasonable way. Other approaches involve non-linear combinations of the quality criteria, as well as "tiered" objective functions (e.g. rank plans in terms of makespan, breaking ties using cost). A related issue is how to help the user decide the "weights" or "tiers" of the different criteria. Often the users may not be able to articulate their preferences between the various quality dimensions in terms of precise weights. A more standard way out of this dilemma involves generating all non-dominated or Pareto-optimal plans16, and presenting them to the user. Unfortunately, often the set of non-dominated plans can be exponential (c.f., Papadimitriou & Yannakakis, 2001). The users are then expected to pick the plan that is most palatable to them. Unfortunately, the users may not actually be able to judge the relative desirability of plans when the problems are complex and the plans are long. Thus, a more practical approach may involve resorting to other indirect methods such as preference elicitation techniques
(c.f. Chajewska, Getoor, Norman, & Shahar., 1998).

## 10. Conclusion

In this paper, we presented Sapa, a domain-independent heuristic forward chaining planner that can handle durative actions, metric resource constraints, and deadline goals. Sapa is a forward-chaining planner that searches in the space of time-stamped states. It is designed to be capable of handling the multi-objective nature of metric temporal planning. Our technical contributions include (i) a planning-graph based method for deriving heuristics that are sensitive to both cost and makespan
(ii) an easy way of adjusting the heuristic estimates to take the metric resource limitations into account and (iii) a way of post-processing the solution plans to improve their execution flexibility. We described the technical details of extracting the heuristics and presented an empirical evaluation of the current implementation of Sapa. An implementation of Sapa using a subset of the techniques presented in this paper was one of the best domain independent planners for domains with metric and temporal constraints in the third International Planning Competition, held at AIPS-02.

We are extending Sapa in several different directions. To begin with, we want to make Sapa support more expressive domains, including exogenous events and a richer set of temporal and resource constraints (e.g a rover can not recharge the battery after sunset). Another direction involves extending our multi-objective search to involve other quality metrics. While we considered cost of a plan in terms of a single monetary cost associated with each action, in more complex domains, the cost may be better defined as a vector comprising the different types of resource consumption.

Further, in addition to cost and makespan, we may also be interested in other measures of plan quality such as robustness and execution flexibility of the plan. Our longer term goal is to support plan generation that is sensitive to this extended set of tradeoffs. To this end, we plan to extend our methodology to derive heuristics sensitive to a larger variety of quality measures. Finally, we also plan to consider the issues of planner-scheduler interactions in the context of Sapa (c.f., Srivastava, Kambhampati, & Do, 2001).