## Definition **GRAPHPLAN** (Blum & Furst, 1995) is a [[Classical Planning]] algorithm that constructs a layered data structure called a **planning graph** and then extracts a valid plan from it. Influential both as a standalone planner and as the source of *heuristics* powering later planners. ## The Planning Graph A directed bipartite layered graph alternating between: - **Proposition layers** $P_0, P_1, \dots, P_k$ — sets of facts that *could* hold at step $k$. - **Action layers** $A_0, A_1, \dots, A_{k-1}$ — sets of actions that *could* be applied at step $k$ (including "no-op" actions to maintain facts). Construction is monotonic: each layer is a superset of what's actually achievable; facts and actions only get *added* as the graph grows. ## Mutex Relations Two facts are **mutex** at layer $i$ if they cannot both hold simultaneously in any reachable state at step $i$. Two actions are mutex if they cannot both be applied at the same step. Mutex relations propagate as the graph grows. Mutex pruning prevents many incompatible action combinations without explicit search. ## The Algorithm ``` build planning graph until either: - all goals appear non-mutex in current proposition layer → try extraction - graph levels off (no new facts/actions) without containing goals → no plan exists extraction (backward search through the graph): for each goal fact in the layer: find a non-mutex action achieving it recursively extract preconditions of those actions if extraction succeeds → return the plan else → grow the graph one more layer; retry ``` ## Properties - **Sound and complete** for classical planning. - **Polynomial** in the number of facts and actions *per graph layer*; the graph can grow exponentially in the worst case. - Often faster than purely search-based planners on certain domain classes (e.g., logistics). ## Influence Even when GRAPHPLAN itself isn't competitive on modern benchmarks, the planning graph survives as a **heuristic generator**: - Goal-distance estimates from the graph give admissible heuristics. - Landmark extraction operates on the graph. - The relaxed planning graph (ignoring delete lists) underlies the FF heuristic — see [[Heuristic Planning]]. ## When to Use - Domains with strong parallelism (many actions executable simultaneously). - As a heuristic-computation backend within other planners. - Pedagogically — GRAPHPLAN remains the cleanest example of how structure exploitation beats brute search. ## Related - [[Classical Planning]] - [[Heuristic Planning]] - [[STRIPS]]