{{short description, Algorithm for automated planning
Graphplan is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
for
automated planning
Automation describes a wide range of technologies that reduce human intervention in processes, namely by predetermining decision criteria, subprocess relationships, and related actions, as well as embodying those predeterminations in machines ...
developed by
Avrim Blum
Avrim Blum (born 27 May 1966) is a computer scientist. In 2007, he was made a List of Fellows of the Association for Computing Machinery, Fellow of the Association for Computing Machinery "for contributions to learning theory and algorithms." Blu ...
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
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
'', to reduce the amount of search needed to find the solution from straightforward exploration of the ''state space graph''.
In the ''state space graph'':
* the nodes are possible states,
* and the edges indicate reachability through a certain action.
On the contrary, in Graphplan's ''planning graph'':
* the nodes are actions and atomic facts, arranged into alternate levels,
* and the edges are of two kinds:
*# from an atomic fact to the actions for which it is a condition,
*# from an action to the atomic facts it makes true or false.
the first level contains true atomic facts identifying the initial state.
Lists of incompatible facts 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
Length is a measure of distance. In the International System of Quantities, length is a quantity with dimension distance. In most systems of measurement a base unit for length is chosen, from which all other units are derived. In the Interna ...
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.
A closely related approach to planning is the Planning as Satisfiability (
Satplan
Satplan (better known as Planning as Satisfiability) is a method for automated planning. It converts the planning problem instance into an instance of the Boolean satisfiability problem, which is then solved using a method for establishing satisfia ...
). Both reduce the automated planning problem to search for plans of different fixed horizon lengths.