# Graphplan

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Graphplan
> Markdown URL: https://mediated.wiki/source/Graphplan.md
> Source: https://en.wikipedia.org/wiki/Graphplan
> Source revision: 1305057901
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{short description|Algorithm for automated planning}}
'''Graphplan''' is an [algorithm](/source/algorithm) for [automated planning](/source/automated_planning) developed by [Avrim Blum](/source/Avrim_Blum) and [Merrick Furst](/source/Merrick_L._Furst) in 1995. Graphplan takes as input a planning problem expressed in [STRIPS](/source/Stanford_Research_Institute_Problem_Solver) 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](/source/Graph_(discrete_mathematics))'', 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](/source/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](/source/Satplan)). Both reduce the automated planning problem to search for plans of different fixed horizon lengths.

==References==

*A. Blum and M. Furst (1997). '''[http://www.sciencedirect.com/science/article/pii/S0004370296000471 Fast planning through planning graph analysis]'''. Artificial intelligence. 90:281-300.

==External links==

*[https://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]
*[http://nplanner.codeplex.com NPlanner: A .NET GraphPlan Implementation] {{Webarchive|url=https://web.archive.org/web/20131231195113/http://nplanner.codeplex.com/ |date=2013-12-31 }}
*[https://emplan.sourceforge.net/ Emplan and JavaGP: C++ and Java implementations of Graphplan]
*[http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-825-techniques-in-artificial-intelligence-sma-5504-fall-2002/lecture-notes/Lecture12FinalPart1.pdf MIT OpenCourseWare lecture on GraphPlan and making planning graphs]

Category:Automated planning and scheduling
Category:Search algorithms

---
Adapted from the Wikipedia article [Graphplan](https://en.wikipedia.org/wiki/Graphplan) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Graphplan?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.