planninggraphs

Planning graphs are a data structure used in automated planning to represent the progression of states and actions from an initial state toward a set of goals. A planning graph is built as a sequence of alternating proposition (state) levels and action levels. The initial proposition level P0 encodes the literals true in the initial state, and the first action level A0 contains actions whose preconditions are all in P0. From each pair (Pi, Ai), the next proposition level Pi+1 is formed by adding the effects of the actions in Ai. To preserve possible future states, no-op or persistence actions carry literals forward from Pi to Pi+1. Within each level, mutual exclusion (mutex) relations are established to mark pairs of actions or propositions that cannot co-occur, such as incompatible effects or competing needs.

Construction proceeds iteratively: new action levels are added for which preconditions are satisfied by the preceding proposition level, and new proposition levels are generated from the effects of those actions. The graph grows until a goal literal appears in some proposition level or no further literals can be produced (a fixed point). Once built, the planning graph supports heuristic measures and planning guidance.

Uses and variants: planning graphs underpin several heuristic methods used in AI planning. The level heuristic (h_level) uses the first level in which all goals are simultaneously present, ignoring mutex constraints to yield a relaxed estimate. The level-sum heuristic (h_ls) sums the first level at which each individual goal appears, also under a relaxed assumption. GraphPlan-based planners extract a complete plan from the graph, while relaxed planning approaches (which may ignore certain constraints) use the graph to obtain fast, informative estimates. Extensions exist for handling numeric fluents, durative actions, and conditional effects.

Limitations: planning graphs can become large, especially for complex domains, and their usefulness depends on the domain structure. They provide lower-bound estimates and guidance but do not by themselves guarantee optimal plans.