From: Stanley Kok (koks_at_cs.washington.edu)
Date: Thu Apr 03 2003 - 15:24:15 PST
Paper Title: Fast Planning Through Planning Graph Analysis
Authors: Avrim L. Blum and Merrick L. Furst
One-line summary:
The paper describes Graphplan, an algorithm that creates a graph to
represent and solve STRIPS-like planning problems.
Most Important Ideas in the Paper:
1. The structure of the graph that Graphplan creates allows one to
easily analyze Graphplan's properties and complexity, and to derive
its termination condition. Furthermore,the creation of mutex edges
amongst propositional and action nodes enables the algorithm to
detect impossible plans early, thereby speeding up the solution
process.
2. Graphplan is relatively insensitive to goal-ordering. This is
important because little is known at the initial stage of a planning
problem to guide the ordering of a goal set, and the algorithm need
not spend unnecessary processing time finding a good goal-ordering.
Flaw in the Paper:
1. By the paper's admission, it unfairly compares the performance of
Prodigy and UCPOP (implemented in Lisp) to that of Graphplan
(implemented in C). Even though the former planners are run on faster
machines, it is unclear whether the graphs reflect an accurate
comparison of performance.
Important, open research questions:
1. The Graphplan structure is reminiscent of Constraint-Satisfaction
Problem (CSP) graphs. How can it use CSP techniques? Its performance
may be enhanced by proven CSP heuristics or it could be totally cast
as a CSP, allowing generic CSP solvers to be used for planning.
2. Graphplan actions are deterministic. Can Graphplan be extended
to handle stochastic actions? This better model the real-world
scenario where an agent is uncertain about the results of its actions.
This archive was generated by hypermail 2.1.6 : Thu Apr 03 2003 - 15:24:16 PST