GraphPlan

GraphPlan is a classical artificial intelligence planning algorithm that uses planning graphs to find a sequence of actions that achieves a given goal from an initial state. It was introduced by Avrim Blum and Merrick Furst in the mid-1990s and has since influenced many planning systems. The core idea is to construct a planning graph, which alternates layers of propositions (facts) and actions. The initial proposition layer encodes the facts true in the initial state. Each subsequent proposition layer adds facts that become true as the effects of actions from the preceding action layer are applied, while each action layer contains actions whose preconditions are present in the previous proposition layer. The graph also records mutex (mutual exclusion) relations that capture incompatible actions or propositions.

The graph is expanded until the top-level proposition layer contains the goals and no mutex relations prevent a consistent combination of actions. If such a level is reached, GraphPlan attempts to extract a plan by a backward search: it selects actions that can achieve each goal in that top layer, ensuring that their preconditions and the mutex constraints are satisfied by earlier levels. If extraction fails, the graph is extended with another level and the process repeats. A plan, when found, is a sequence of actions that achieves the original goals from the initial state.

GraphPlan provides a useful heuristic known as the level heuristic (h+), which estimates the minimum planning level at which goals can appear without resolving all future mutexes. While powerful, GraphPlan can face exponential growth in large or densely connected domains, and plan extraction can be computationally intensive. Its design, however, has made it a foundational approach and influenced many subsequent planning systems and heuristics in STRIPS-like frameworks.