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.
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.
Last modified: Mon May 6 07:34:12 MST 2002