Sapa's GUI showing the solution of a Satellite problem. Click here for a bigger problem.
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 number 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 aspects (such as cumulative action cost, resource consumption). Until now, most domain-independent temporal planners have concentrated solely on the former, ignoring the latter. Sapa is a domain-independent heuristic forward chaining planner that can handle durative actions, metric resource constraints, and deadline goals. In Sapa, we specially concentrate on the problem of developing heuristics that are sensitive to both makespan and cost, and develop a planning graph-based approach for this purpose. Our approach involves augmenting a (temporal) planning graph data structure with a mechanism to track the execution cost of the goals and subgoals. Since the cost of achieving a goal is dependent on the amount of available time, we need to track the cost of a literal as a function of time. We present a methodology 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 execution cost. A version of Sapa using a subset of the techniques discussed in the papers listed in this page 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.
Scalable Multi-Objective Metric Temporal Planner
Minh B. Do and Subbarao Kambhampati. JAIR 2003.
Improving the Temporal Flexibility of Position Constrained Metric
Minh B. Do and Subbarao Kambhampati. ICAPS 2003.
A Domain-Independent Heuristic Metric Temporal Planner
Minh B. Do and Subbarao Kambhampati. ECP 2001.
Graph-based Heuristics for Cost-sensitive Temporal Planning.
Minh B. Do and Subbarao Kambhampati. AIPS 2002.
the Temporal Flexibility of Position Constrained Metric Temporal Planning.
Minh B. Do and Subbarao Kambhampati. Temporal Planning Workshop, AIPS 2002.
Sapa: A Multi-objective Heuristic
Metric Temporal Planner.
Minh B. Do, Subbarao Kambhampati, and Dan Bryce. Technical Report.
§ PowerPoint slides of AIPS Workshop talk. Contains more detail information, compared to the workshop paper, on the implementation framework using leveled CSP or Mixed ILP.
NOTE: As of September 3rd, 2004, we have placed a new version of SAPA for download. The newer version fixes several bugs, and also uses more efficient data structures. The source code for Sapa is available here in tarred/gzipped form.. The executable jar file is available here. If you are a first-time user, please send a mail to rao, who lives at asu dot edu, if you download the code.You can use the planner without unjarring the file by typing: java -jar Sapa2_stable_200406.jar
Last modified: Mon May 6 07:34:12 MST 2002