Graph-based Planners are based on ideas used in graph algorithms. Given a problem statement, a Graph-based Planner 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. The Graph-based Planner then exploits this information in the search for a plan[1].

Graphplan: The first planner to use a planning graph, developed by Avrim Blum and Merrick Furst from the Carnegie Mellon University.

- Description by author:
**Graphplan**is a general-purpose planner for STRIPS-style domains. It takes the initial conditions and operator definitions and uses them to construct a leveled graph. The initial conditions are the first level of the graph. The next level consists of actions that might be performed at time 1. The level after that consists of facts that might be true at time 2. The level after that is actions that might be performed at time 2, etc. In the animation, the initial conditions are in a column at the left edge of the page and the levels go left to right. When we create the graph, we also propagate exclusion relations left to right. These are properties of the graph that are used to limit search. This part is all fairly quick and in any case is polynomial time. In the searching phase, Graphplan performs a fairly standard sort of backward-chaining search, but using the information propagated when creating the graph. This limits the amount of searching performed. - Publications:
- A. Blum and M. Furst, "Fast Planning Through Planning Graph Analysis", 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. Describes how the planning graph structure can be used for probabilistic planning.

- A. Blum and M. Furst, "Fast Planning Through Planning Graph Analysis", Artificial Intelligence, 90:281--300(1997). This is the original paper that describes the algorithm used.
- Source Code: Remote, Local, object code: for the DECstation (Local) and Sparcstation (Local).
- Platform: Linux and SunOS
- Input Language:Strips-style Language, Sample Domains
- Implementation Language:
**GCC** - Running Introductions:By the author, Local.

Blackbox: **blackbox = satplan + graphplan**, developed by Henry Kautz at the University of Washington.

- Description by author:
**Blackbox**is a planning system that works by converting problems specified in STRIPS notation into Boolean satisfiability problems, and then solving the problems with a variety of state-of-the-art satisfiability engines. The front-end employs the graphplan system. There is extreme flexibility in specifying the engines to use. For example, you can tell it to use walksat (Selman, Kautz, and Cohen 1994) for 60 seconds, and if that fails, then satz (Li and Anbulagan 1997) for 1000 seconds. This gives blackbox the capability of functioning efficiently over a broad range of problems. The name blackbox refers to the fact that the plan generator knows nothing about the SAT solvers, and the SAT solvers know nothing about plans: each is a "black box" to the other. - Publications:
- Unifying SAT-based and Graph-based Planning, Proc. IJCAI-99, Stockholm.

- Source Code: Remote.

Local: Source Version 4.1x, a previous version(excutable on Solaris). Object code: for Linux version3.9 and Windows version3.9. - Platform: Windows, Linux and SunOS
- Input Language: PDDL. Domain Examples.
- Instructions.
- Implementation Language:
**GCC** - See Also: SAT Planners

DPPLAN : A planner based on the planning graph, using different search procedures on the planning graph, which are not compelled to be directional. It has been developed by Marco Baioletti with the help of Alfredo Milani from the Universities of Perugia and Siena.

- Description by author:
**DPPLAN**, as its ancestor Graphplan, is a general-purpose planner for STRIPS-style domains. It takes the initial conditions and operator definitions and uses them to construct a leveled graph, called the planning graph. The actual construction is similar to that one performed on STAN, but with different methods and data structures. The search procedures are based on a process similar to the Davis-Putnam procedure for propositional logic, but applied on the graph nodes. The authors have defined propagation rules which alters the value of the nodes in a non directional way. Several strategies for choosing the node are implemented. - Publications:
- M. Baioletti, S. Marcugini, A. Milani. DPPlan: an Algorithm for Fast Solutions Extraction from a Planning Graph.
*5th International Conference on Artificial Intelligence Planning & Scheduling (AIPS2000)*, Breckenridge, CO, USA, April 14-17, 2000.

(This is the original paper that describes the algorithm used.)

- M. Baioletti, S. Marcugini, A. Milani. DPPlan: an Algorithm for Fast Solutions Extraction from a Planning Graph.
- Source Code Download: Remote.
- Platform: Linux, SunOS and Windows
- Input Language:PDDL2.1.
- Implementation Language: GCC
- Instructions

IPP : The IPP planning system was developed by Jana Koehler, Joerg Hoffmannr, Michael Brenner, and Frank Rittinger at the University of Freiburg from Fall 1996 to Spring 1999.

- Description by author:
**IPP**is based on planning graphs as originally developed by Blum and Furst, but extended them to cover ADL, in particular conditional effects and complex logical preconditions. IPP competed already in the first planning competition in 1998 where it demonstrated a superior performance in the ADL track. Today, IPP is no longer maintained and has only entered the AIPS2000 competition to provide a basis for comparison for the newer ADL planners as the system has only marginally changed. - Publications.
- Source Code: Remote, Local.
- Input Language:
PDDL
and ADL.

Domain Examples. - Implementation Language:
**C** - Instructions.

LPG developed by Alfonso Gerevini and Ivan Serina from the University of Brescia.

- Description by author:
**LPG**(Local search for Planning Graphs) is a planner based on local search and planning graphs that handles PDDL2.1 domains involving numerical quantities and durations. The system can solve both plan generation and plan adaptation problems. The basic search scheme of LPG was inspired by Walksat, an efficient procedure to solve SAT-problems. The search space of LPG consists of of "action graphs", particular subgraphs of the planning graph representing partial plans. The search steps are certain graph modifications transforming an action graph into another one. LPG exploits a compact representation of the planning graph to define the search neighborhood and to evaluate its elements using a parametrized function, where the parameters weight different types of inconsistencies in the current partial plan, and are dynamically evaluated during search using discrete Lagrange multipliers. - Publications.
- Source Code: Remote, Local for Linux and Local for SunOS.
- Platform: Linux & SunOS
- Input Language: PDDL2.1.
- Implementation Language:
**GCC** - Instructions.
- See Also: Temporal planners and Heuristic planners

PropPlan from Michael Fourman at the University of Edinburgh.

- Description by author:
**PropPlan**is a planner based on naive breadth-first state-space search. PropPlan uses Ordered Binary Decision Diagrams, popularised by Bryant, to implement exhaustive state space exploration.PropPlan handles full ADL and domain axioms. It also generalises ADL and STRIPS actions by allowing general formulae as effects, and by separating the specification of the fluents an action may change from the constraints it imposes on the changed values. The competition version of PropPlan is based on a simple elimination of timeless predicates, followed by straigntforward, forward chaining exhaustive breadth-first search to establish a layered set of reachable states until the goal-set is reached, then backward chaining for plan extraction.

- Publications:
- Michael P. Fourman Propositional Planning(Planning.ps), Workshop on Model Theoretic Approaches to Planning, AIPS 2000, Breckenridge Colorado, April 2000.
- Informatics report EDI-INF-RR-0034, April 2000.

- Michael P. Fourman Propositional Planning(Planning.ps), Workshop on Model Theoretic Approaches to Planning, AIPS 2000, Breckenridge Colorado, April 2000.
- Online Demo.
- Platform:Linux
- Input Language: PDDL and ADL.
- Implementation Language:
**StandardML** - See Also: BDD planners

Sensory Graphplan developed by Dan Weld et al from the University of Washington.

- Description by author:
**Sensory Graphplan**(SGP) is a sound, complete planner based on Blum and Furst's Graphplan. SGP includes support for conditional effects, universal and existential quantification, uncertainty, sensing actions, and uses the PDDL language syntax. SGP is written in Lisp, is efficient, and is well-suited for use in the classroom or research. - Publications:
- Corin R. Anderson, David E. Smith, and Daniel S. Weld. Conditional
Effects in Graphplan. In Proceedings of AIPS '98. 1998.
- Daniel S. Weld, Corin R. Anderson, David E. Smith. Extending Graphplan
to Handle Uncertainty & Sensing Actions. In Proceedings of AAAI '98. 1998.

- Corin R. Anderson, David E. Smith, and Daniel S. Weld. Conditional
Effects in Graphplan. In Proceedings of AIPS '98. 1998.
- Source Code:Remote, Local.
- Input Language: PDDL.
- Implementation Language:
**Lisp** - See Also: Planners handling Uncertainty

STAN developed by Maria Fox and Derek Long at the University of Strathclyde.

- Description by author:
**STAN**is a hybrid of two planning strategies:- The original Graphplan-based STAN algorithm;
- A forward planner using a heuristic function based on the length of the relaxed plan (as in HSP and FF).

The key new contribution that STAN makes is the use of domain analysis techniques to select automatically between these strategies, depending on a number of domain features, and to inform search within these strategies. These domain analysis techniques now go way beyond type and invariant analysis and include the automatic identification of certain combinatorial optimisation sub-problems and the invocation of specialised solvers for tackling them.

- Publications.
- Source Code: Remote, Local.
- Platform: Linux
- Input Language: PDDL.
- Implementation Language:
**C** - See Also: Heuristic planners

TGP Temporal Graphplan, from Dan Weld et al at the University of Washington.

- Description by author:
**TGP**operates by incrementally expanding a compact planning graph representation that handles actions of differing duration. The key to TGP performance is tight mutual exclusion reasoning which is based on an expressive language for bounding mutexes and includes mutexes between actions and propositions. Our experiments demonstrate that mutual exclusion reasoning remains valuable in a rich temporal setting. - Publications:
- Smith and Weld. Temporal Planning with Mutual Exclusion Reasoning. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. 1999.

- Source Code: Remote, Local.
- Implementation Language:
**Lisp** - See Also: Temporal planners