Graphplan
From Wikipedia, the free encyclopedia
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 any, a sequence of operations for reaching a goal state. The name graphplan is due its use of a planning graph as an intermediate structure to reduce the amount of search needed to find the solution.
The graph used by graphplan is not the search space graph, a graph in which possible states are nodes and edges indicate reachability. The nodes of the graph are instead conditions and actions, arranged into alternate levels of conditions and actions.
The conditions of the first levels are those initially true. The third level contains all conditions that can actually be made true at the second time point by executing some actions, etc. The odd levels contain the actions that can be performed at each time step. By definition, each level (of actions or conditions) can be built from the previous one (of conditions or actions, respectively).
A level of action can contain one or more actions that can be executed in isolation but not together. As a result, the next level of conditions can contain conditions that cannot be made true at the same time because they are made true by actions that cannot all be executed at the same time. Graphplan stores incompatibility of actions and conditions at each level, and uses them to determine the incompatibilities at the next level.
The graph produced by graphplan contains all conditions that can be made true and all actions that can be executed at some time point, but can also contain other conditions and actions. The actual search for a plan can be done by backward chaining (starting from the goal and recursively establishing which subgoals have to be reached to reach the goal) or by using an encoding of the problem in a propositional satisfiability or constraint satisfaction problem. The graph is used in this phase to reduce the number of possibilities the algorithm has to consider.
[edit] References
- A. Blum and M. Furst (1997). Fast planning through planning graph analysis. Artificial intelligence. 90:281-300.
- S. Russell and P. Norvig (2003). Artificial Intelligence: A Modern Approach, Second Edition. Upper Saddle River, New Jersey: Prentice Hall.
