16.412J/6.834 Intelligent Embedded Systems


Graphplan Planning Software

Course Software

Graphplan is a planning algorithm based on the notion of a plan graph. A plan graph represents facts achievable in a future level based on application of feasible operators at the present level. The first level represents the initial state, and the last level contains all the facts that appear in the goal state (as well as, possibly, many others). Mutually exclusive relations between facts and operators are maintained at each level of the plan graph. After the plan graph has been generated, Graphplan searches backward from the goal (last) level to generate a feasible plan.

Source code, along with instructions for building and running an executable are provided here. The source code is in C, and a Makefile is provided. Building and running the executable should work on any Unix system with C. Example problems (fact and operator files) are included as well.

More details on Graphplan can be found at the Graphplan home web site . An excellent reference paper is:
A. Blum, M. Furst, "Fast Planning Through Planning Graph Analysis" , Artificial Intelligence, 90:281--300 (1997). This is the original paper describing the algorithm and its implementation.



Building the Executable

First, download the source .
This is a .tar.gz file. To unzip, on a Unix system, do:

gunzip Graphplan-source.tar.gz

(this produces Graphplan-source.tar). Now do:

tar -xvf Graphplan-source.tar

(this extracts the sources and puts them into a sub-directory). Go to this subdirectory and do:


(this makes the executable). The make file (Makefile) is relatively straightforward (you may want to take a quick look at it). It assumes gcc is the C compiler, but you can modify this to refer to a different compiler.


Running Graphplan

Instructions for running the executable, as well as some example fact and operator files, are given here .

For convenience, here is an example fact and operator file for the tire changing domain:
fixit_facts1 ,
fixit_ops .


Home | Announcements | Class-Readings | Final Project