Graphplan

Graphplan is an algorithm for automated planning developed by Avrim Blum and Merrick Furst in 1995. Graphplan takes as input a planning problem expressed in STRIPS and produces, if one is possible, a sequence of operations for reaching a goal state. The name "graph"plan is due to the use of a novel "planning graph" to reduce the amount of search needed to find the solution from straightforward exploration of the "state space graph", in which the nodes are possible states and edges indicate reachability through a certain action.

In Graphplan's "planning graph" nodes are actions and propositions, arranged into alternate levels, and edges are of three kinds: from a proposition to the actions for which it is a condition, and from an action to the propositions it makes true or false; the first level contains true propositions representing the initial state. Lists of incompatible propositions that cannot be true at the same time and incompatible actions that cannot be executed together are also maintained.

The algorithm then iteratively extends the planning graph, proving that there are no solutions of length l-1 before looking for plans of length l by backward chaining: supposing the goals are true, Graphplan looks for the actions and previous states from which the goals can be reached, pruning as many of them as possible thanks to incompatibility information.

References

*A. Blum and M. Furst (1997). Fast planning through planning graph analysis. Artificial intelligence. 90:281-300.
*Russell Norvig 2003

External links

* [http://www.cs.cmu.edu/~avrim/graphplan.html Avrim Blum's Graphplan home page]
* [http://www.philippe-fournier-viger.com/plplan.html PLPLAN: A Java GraphPlan Implementation]