Welcome to the Graphplan Home Page
Graphplan is a general-purpose planner for STRIPS-style domains, based on ideas used in graph algorithms. Given a problem statement, Graphplan explicitly constructs and annotates a compact structure called a Planning Graph, in which a plan is a kind of "flow" of truth-values through the graph. This graph has the property that useful information for constraining search can quickly be propagated through the graph as it is being built. Graphplan then exploits this information in the search for a plan. Graphplan was created by Avrim Blum and Merrick Furst, with subsequent extensions and improvements made by many researchers at many different institutions around the world.
|How to try it out
To try out Graphplan, go to the Graphplan home directory. This directory contains source code, object code for the DECstation and Sparcstation, a variety of sample domains, and a README file that describes how to run Graphplan and how to make up your own domains and problems. The program allows you to see an animation (in X) of what it's doing. For instance, look at a simple TSP domain. Here is what the animation looks like on a more interesting Flat Tire World (fixit) domain (graph creation omitted). Here is an explanation of what's going on.
A. Blum and M. Furst, "Fast Planning Through Planning Graph Analysis" [pdf], Artificial Intelligence, 90:281--300 (1997). This is the original paper that describes the algorithm used.
A. Blum and J. Langford, "Probabilistic Planning in the Graphplan Framework", in Proceedings of ECP'99. (c) Springer-Verlag. Describes how the planning graph structure can be used for probabilistic planning. See the Probabilistic Graphplan page.
Since the initial creation of Graphplan, a number of researchers have pushed these ideas in a variety of exciting directions, including:
Algorithms and Complexity | Computer Science Department | School of Computer Science
This page maintained by Avrim Blum (firstname.lastname@example.org). Last modified: June 2001