From: Nan Li (annli_at_cs.washington.edu)
Date: Fri Apr 04 2003 - 13:20:55 PST
Fast Planning Through Planning Graph Analysis/A. Blum, M. Furst
This paper describes a smart approach to planning in STRIPS-like domains.
It has combined advantages of both total-order planners and partial-order
planners at that time: it generates partial-order plans, yet the
well-defined structure grants its ability to search more efficiently, and
more importantly, halt.
Graphplan basically does a forward breadth-first search. The breadth-first
manner search allows the planner to make strong commitments in the search
yet still generate partial-order plans. To break through the inefficiency
of breadth-first search, the authors come up with a strategy of
maintaining a local harmony, by marking and excluding "mutually exclusive"
actions. Any two mutually exclusive actions can never occur at the same
step in a partial order. Even more, the authors define and mark "mutually
exclusive" propositions, further narrowing down candidates at each step of
the breadth-first search.
Another important concept of this paper is, the planning graph is not a
state-space graph, neither a plan-space graph. Rather, it records and
shows how much the work has been done. After each iteration, the graph
records the information of what can be done and what can not so far. Note
that at the proposition level, not the state of world after actions is
written down, but the changes. The add/delete-effects and the original
state, together with mutually exclusive marks, can implicitly represent
all possible states of the world after actions taken, and save a lot of
time and space. Of course, to check whether the goal states have been
achieved is not so direct as in a state-space graph, but as shown in the
paper, a backward-chaining search can do it without much cost, because the
number of steps is fixed.
As mentioned above, the "mutually exclusive actions" concept is a very
important factor of the planner's success. However, the authors seem not
to offer enough details about how to build all exclusive relations among
actions. About the paper itself, the whole picture might be clearer if the
authors give a pseudo-code algorithm.
I don't think there is much work to do in non-STRIPS domains based on this
algorithm. In STRIPS-like domains, the "mutually exclusive" definition can
be dug deeper for situations like conditional-effects, resources
constraints.
--
This archive was generated by hypermail 2.1.6 : Fri Apr 04 2003 - 13:20:56 PST