SAPA: A Forward Chaining Heuristic Metric Temporal Planner

 

At the AIPS 2002 Planning Competition (IPC 3), SAPA was the undisputed master of its own domain(s)--producing high quality plans with some of the best planning times in two of the most complex domains (with time, durative effects and numerical resources). Overall, it is one of the best performers in the highest level of PDDL 2.1 setting, in terms of the complexity in metric and temporal constraints involved, used in the competition.

Sapa's GUI showing the solution of a Satellite problem. Click here for a bigger problem.

The executable jar file is available here.

Sapa's Java Applet

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.

Publications

         Sapa: A Scalable Multi-Objective Metric Temporal Planner
Minh B. Do and Subbarao Kambhampati. JAIR 2003.

         Improving the Temporal Flexibility of Position Constrained Metric Temporal Plans.
Minh B. Do and Subbarao Kambhampati. ICAPS 2003.

         Sapa: A Domain-Independent Heuristic Metric Temporal Planner
Minh B. Do and Subbarao Kambhampati. ECP 2001.

         Planning Graph-based Heuristics for Cost-sensitive Temporal Planning.
Minh B. Do and Subbarao Kambhampati. AIPS 2002.

         Improving 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.

Talks

         Here is the talk given at ECP 2001 in Toledo, Spain

         PowerPoint slides of AIPS Talk.

         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.

Source Code

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 [options]

 


Subbarao Kambhampati

Last modified: Mon May 6 07:34:12 MST 2002