From: Kevin Sikorski (kws_at_cs.washington.edu)
Date: Fri Apr 04 2003 - 11:49:29 PST
Fast Planning Through Planning Graph Analysis
by: Avrim L. Blum, Merrick L. Furst
Summary:
This paper describes a planning approach which uses a "leveled" graph
approach based on iterated deepening to performing efficient STRIPS
planning.
The (two) most important ideas in the paper, and why:
Graphplan operates by casting at STRIPS planning problem as an "leveled"
action-state graph, building the graph one level at a time. This way,
the algorithm does not need to consider the full state-space, as a naive
planner might.
Tracking mutually exclusive actions through the graph significantly cuts
down on the search space by allowing graphplan to avoid having to plan
through large regions of the search space that can never be reached. In
some cases, this enables the algorithm to determine that a problem has no
solution by simply examining the Planning Graph, and without performing
any search at all.
The one or two largest flaws in the paper:
As stated above, graphplan relies on propagation of mutually exclusive
actions for its speedy execution. However, propagation is less effective
in very dense graphs, as might be seen in an instance of the Traveling
Salesman Problem. An "additional feature" was proposed to partially fix
this, but no performance data is available (making it appear that it was
not blindingly-fast). Also, the paper did not mention the STRIPS
representation of an arbitrary TSP problem.
Graphplan only applies to discrete, STRIPS-compatible domains. The
authors admit this problem, but do not provide any solutions. For many
continuous domains, one can discretize the state-space and action-space,
and perform graphplan on the result. However, there is no guarantee that
the discretization was too course to find a solution (in which case, the
algorithm may report that no solution exists, where there may be a
solution for a finer discretization). Conversely, an overly fine
discretization could unnecessarily inflate execution time.
Identify two important, open research questions on the topic, and why they
matter:
The Traveling Salesman Problem proved difficult for a vanilla graphplan
implementation, but this difficulty was somewhat alleviated by adding a
(poorly described) tweak. It is not made clear how this addition affects
the runtime of the algorithm. Furthermore, it is not known if there are
other STRIPS problems similar to TSP in which graphplan performs poorly.
Many common problems exhibit some form of symetry, such as the rocket
domain when ferrying cargo to two different locations. As pointed out in
the paper, graphplan currently ignores such symetries, which could
conceivably be exploited to speed searching.
This archive was generated by hypermail 2.1.6 : Fri Apr 04 2003 - 11:49:30 PST