From: Stefan B. Sigurdsson (stebbi_at_cs.washington.edu)
Date: Fri May 30 2003 - 12:04:09 PDT
Do and Kambhampati
Sapa: A domain-independent heuristic metric temporal planner
ECP 2001
Summary - This paper presents Sapa, a metric temporal planner that employs forward chaining search with search control heuristics. Its problem domain is STRIPS extended to durative actions with metric execution cost, and limited resources governing the number of actions that can be executed during the course of a plan. The key issue is the development of domain-independent search control heuristics.
Key ideas
- Sapa uses distance-based heuristics. A first pass employs a cyclic planning graph but ignores delete effects and resource constraints. A second pass tightens the heuristics by incorporating the resource constraints. The search is in state space but states are time-stamped; this can obviously significantly increase the size of the problem. The search algorithm employs a priority queue ordered by heuristic (A*) to select which node to expand next.
- The empirical results point at one heuristic (sum-act-adjusted) over others. This heuristic is based on the *number* (not the duration) of actions in a plan. It is therefore considerably more relaxed than a duration-based heuristic. It is then adjusted to include the minimal number of instantiations of the action that replenishes a constraining resource the most. I find it very interesting that the table of experimental results indicates that the analogous heuristic that takes action durations into account instead of action numbers, is far more expensive to work with - half the problems experimented with were not solved within a time limit using the richer heuristic. Even more interestingly, the more relaxed action number heuristic produces plans of the same quality when both heuristics work.
Questions
- What is the difference between the "hold process" and mutual exclusions? Isn't this the same idea?
- I really question the decision to eliminate mutexes from the planning graph. This decision is not adequately motivated in the paper. The planning graph is still very useful though - supports elimination of plans that do not meet deadlines, and the construction of several different heuristics including makespan (time duration) based ones.
- It's interesting that the first pass eliminates a lot of plans based on time constraints, but then the second phase can extend the remaining plans by inserting resource replenishing actions. How often do these insertions result in blowing the time limit for the extended plan? That depends on the available slack, which makes me doubt the usefulness of minimal slack-based heuristics. This characteristic of the SAPA algorithm seems to inflate the importance of maximum slack-based heuristics?
Directions
- Put the mutexes back in! This seems like a common thread in planning graph-based solvers, I can only guess that mutex computations are so complex that they get cut due to time constraints. (?) The TGP paper, with the intricate mutex discussion, seems to point the same way. Are there other reasons why mutexes are left out of planning graph-based solvers that I'm not seeing?
- Restricting resource usage to one action at a time seems very limiting on the plans that can be derived. Can this be accounted for by increasing the number of resources? I expect that would significantly complicate the search.
This archive was generated by hypermail 2.1.6 : Mon Jun 02 2003 - 12:26:20 PDT