Planning graph-based heuristics for cost-sensitive temporal planning
Bùi Quang Minh, Subbarao Kambhampati · 2002
Real world planners need to be sensitive to the quality of the plans they generate. Unlike classical planning where quality is often synonymous with plans having least num-ber of actions, in temporal planning plan quality is multi-dimensional. It involves both temporal aspects of the plan (such as makespan, slack, tardiness) and execution cost as-pects (such as cumulative action cost, resource consumption). Until now, most domain-independent temporal planners have concentrated solely on the former, ignoring the latter. In this paper, we consider the problem of developing heuristics that are sensitive to both makespan and cost, and develop a plan-ning graph-based approach for this purpose. Our approach involves augmenting a (temporal) planning graph data struc-ture with a mechanism to track the execution cost of the goals and subgoals. Since the cost of achieving a goal is depen-dent on the amount of available time, we need to track the cost of a literal as a function of time. We present a method-ology for efficiently tracking the cost functions, and discuss how they can be used as the basis for deriving heuristics to support any objective function based on makespan and exe-cution cost. We demonstrate the effectiveness of this general method for deriving cost- and makespan-sensitive heuristics in the context of Sapa a forward chaining planner for metric temporal domains that we have been developing. A version of Sapa using a subset of the techniques discussed 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.