Planning Graphs and Heuristics

Planning graphs and domain-independent heuristics are the techniques that made classical planning fast, by compactly analyzing reachability and by automatically estimating the distance from a state to the goal.

Definition

A planning graph is a layered structure that interleaves proposition and action levels with mutex constraints to approximate reachability; planning heuristics are functions, often computed from such structures or from delete-relaxed problems, that estimate the cost of reaching the goal from a state.

Scope

This topic covers the planning graph data structure introduced by Graphplan, including levels of propositions and actions and the mutual-exclusion (mutex) relations that capture which facts and actions cannot co-occur, and the family of domain-independent heuristics derived from relaxed problems (notably ignoring delete effects) that drive modern heuristic-search planners. It addresses how reachability information is computed and used to guide search. The underlying classical planning model is covered in the related topic.

Core questions

• How does a planning graph represent reachable propositions and actions level by level?
• What are mutex relations, and how do they capture incompatibility between facts and actions?
• How is the delete-relaxation used to derive admissible or informative planning heuristics?
• How do these heuristics turn planning into efficient heuristic search?

Key concepts

• planning graph
• proposition and action levels
• mutual exclusion (mutex)
• Graphplan
• delete-relaxation
• h-max and h-add heuristics
• FF heuristic and relaxed plans
• heuristic forward search

Key theories

Planning graph and Graphplan

Graphplan builds a planning graph that compactly encodes which propositions and actions are reachable at each level and which pairs are mutually exclusive, then extracts a plan by searching backward through this structure, dramatically speeding up planning.

Delete-relaxation heuristics

Ignoring the delete effects of actions yields a relaxed planning problem that is much easier to solve; the cost of solving this relaxation provides informative, often admissible heuristics (such as h-max and h-add and the FF heuristic) that guide forward search.

Heuristic search planning

State-of-the-art classical planners combine automatically derived heuristics with best-first or greedy search and enhancements such as preferred operators, achieving strong general-purpose performance across diverse domains.

Clinical relevance

Planning graphs and delete-relaxation heuristics are the core technology of competition-winning planners used in robotics, logistics, and autonomous control, where they let domain-independent planners solve large problems quickly without hand-crafted search guidance.

History

Blum and Furst's Graphplan (1995, journal version 1997) introduced the planning graph and revolutionized planning speed. The late 1990s and 2000s saw the rise of delete-relaxation heuristics, with the FF planner (Hoffmann and Nebel, 2001) and later Fast Downward (Helmert, 2006) establishing heuristic forward search as the dominant approach.

Key figures

• Avrim L. Blum
• Merrick L. Furst
• Jörg Hoffmann
• Bernhard Nebel
• Malte Helmert

Seminal works

• blum1997
• hoffmann2001

Frequently asked questions

What is a mutex in a planning graph?

A mutex (mutual exclusion) relation marks two propositions or two actions that cannot both hold or be applied at the same level, for example because one action deletes a precondition of the other. Mutexes make the planning graph a tighter approximation of true reachability.

Why does ignoring delete effects give a useful heuristic?

Without delete effects, achieving one goal never undoes another, so the relaxed problem is much easier to solve and never harder than the original. The cost of the relaxed plan is therefore a lower bound or informed estimate of the real cost, making it an effective heuristic to guide search.