Graphplan
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 one is possible, a sequence of operations for reaching a goal state. The name graphplan 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 atomic facts, arranged into alternate levels, and edges are of three kinds: from an atomic fact
to the actions for which it is a condition
, and 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
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
). Both reduce the automated planning problem to search for plans of different fixed horizon lengths.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for automated planning developed by Avrim Blum
Avrim Blum
Avrim Blum is a prominent computer scientist who in 2007 was inducted as a Fellow of the Association for Computing Machinery "for contributions to learning theory and algorithms."-Biography:...
and Merrick Furst in 1995. Graphplan takes as input a planning problem expressed in STRIPS
STRIPS
In artificial intelligence, STRIPS is an automated planner developed by Richard Fikes and Nils Nilsson in 1971. The same name was later used to refer to the formal language of the inputs to this planner...
and produces, if one is possible, a sequence of operations for reaching a goal state. The name graphplan is due to the use of a novel planning graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
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 atomic facts, arranged into alternate levels, and edges are of three kinds: from an atomic fact
Fact
A fact is something that has really occurred or is actually the case. The usual test for a statement of fact is verifiability, that is whether it can be shown to correspond to experience. Standard reference works are often used to check facts...
to the actions for which it is a condition
Condition
-Logic:* Logical conditional* Necessary and sufficient condition, condition of another means that the former statement is true if and only if the latter is true-Computer programming:* Conditions, a generalization of exceptions in exception-handling...
, and from an action
Action
Action may refer to:* Action theory , concerning the processes causing intentional human bodily movements* Social actions, person taking account of others* Action , a characteristic of a stringed instrument...
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
In geometric measurements, length most commonly refers to the longest dimension of an object.In certain contexts, the term "length" is reserved for a certain dimension of an object along which the length is measured. For example it is possible to cut a length of a wire which is shorter than wire...
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
Satplan 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 satisfiability such as the DPLL algorithm or WalkSAT.Given a problem instance in planning, with a given...
). Both reduce the automated planning problem to search for plans of different fixed horizon lengths.