Is a planning graph itself a plan?

No. A planner must select a consistent supporting set of actions.

Can it supply heuristic information?

Yes. Appearance levels and mutex relationships can support estimates, with guarantees depending on the particular heuristic and cost assumptions.

Does a mutex always persist forever?

No. More steps may allow facts that were previously incompatible to be achieved together.

AI Glossary / Graphs and symbolic AI / Advanced

Planning graph

Definition

A planning graph is a layered data structure that summarizes which facts and actions may become available as a planning problem progresses. It alternates proposition or literal layers with action layers and records relationships such as preconditions, effects, and mutual exclusions. Introduced with Graphplan, it supports plan search and planning heuristics. It represents possibilities and constraints rather than a single chosen course of action.

What it means

An action may make a fact achievable without making it achievable alongside every other fact in the same layer. A planning graph preserves this distinction by marking certain pairs as mutually exclusive, often shortened to mutex. These marks help reject incompatible choices before a planner explores them in detail.
The graph is not a conventional state-space graph whose nodes each describe a complete world state. One proposition layer can combine facts arising from different possible histories. Reading the whole layer as one achievable state is therefore a serious mistake.

How it works

The first proposition layer contains the initial facts. An action layer includes actions whose preconditions are available and compatible at the preceding layer. Persistence actions, also called no-ops, carry facts forward. The next proposition layer collects available effects.
Actions can be mutex because one interferes with the other's conditions or effects, or because their preconditions are mutex. Facts can be mutex when every pair of actions supporting them is mutex. Exclusions may change at later levels.
Graphplan searches backward for compatible action choices supporting the goals, then their preconditions. Goal presence without pairwise mutex is a necessary gateway to this search, not a general proof that a complete plan exists. Pairwise checks do not capture every larger incompatibility.

Three practical examples

A packing planner models a shared preparation bench. Two operations may each be possible next, yet cannot occupy the bench together. Mutex relationships expose that conflict when the resource is represented in the action model.
A robot planner distinguishes reaching room A from reaching room B after one move. Both locations may appear as possibilities, but the robot cannot occupy both in a valid state under the location model.
A maintenance planner estimates how many action layers are required before replacement and inspection goals can coexist. Such estimates can guide search, but they are not automatically estimates of elapsed hours when actions have different durations.

Think of it this way

Think of a menu of possible next steps with incompatibility notes. Seeing two items on the menu does not mean they can both be ordered under the same constraints.

Worked example

A fictional workshop needs to prepare items X and Y using one bench. Initially only Free is true. Use three actions:
PrepareX requires Free, adds ReadyX and Busy, and deletes Free. PrepareY requires Free, adds ReadyY and Busy, and deletes Free. Reset requires Busy, adds Free, and deletes Busy. Neither Reset nor either preparation action deletes a readiness fact. The goal is ReadyX together with ReadyY.
At proposition layer P0, Free is available. Action layer A0 contains PrepareX, PrepareY, and the persistence action for Free. The two preparation actions are mutex because each deletes the other's Free precondition.
At P1, ReadyX and ReadyY both appear. They remain mutex: their only supporting preparation actions cannot occur together. Free and Busy also appear as alternatives, rather than a claim that the bench has both conditions simultaneously.
At the next action layer, Reset can follow a preparation. P2 allows ReadyX together with Free, supported by retaining ReadyX while resetting the bench. It similarly allows ReadyY together with Free. However, ReadyX and ReadyY are still mutex at P2.
At A2, PrepareY can occur while ReadyX persists. Consequently, P3 supports both readiness goals without that mutex. A valid plan is PrepareX, Reset, PrepareY; either preparation can come first.
Three action steps are necessary in this model. Both preparations require the bench to be free, and the first removes that condition, so a reset must separate them. The graph's first appearances of the individual goals at P1 do not justify a one-step plan. Free is not a final goal, so no final reset is needed.

Illustrative case study

Fictional team Orchard Automation builds a workflow planner for preparing sample kits. A demonstration initially permits two preparation tasks to run together because the shared workstation is absent from the model. The team adds explicit workstation availability and reset effects, then examines the resulting action exclusions.
Reviewers compare the extracted plan with the stated operations and test whether changing the final goal to include an available workstation adds a necessary reset. They also keep real task durations separate from the abstract planning layers. This fictional case illustrates model validation; the planning graph cannot discover a missing physical constraint merely because that constraint matters operationally.

Common misconceptions and mistakes

All facts in a layer need not hold together. The layer summarizes possibilities across alternatives.
No mutex between each pair of goals does not guarantee that all goals have a jointly consistent supporting plan.
A persistence action expresses an unchanged fact; it is not necessarily a real task requiring a worker.
A planning layer is not automatically one minute, one shift, or one executed action. Compatible actions may share a layer.
A compact graph does not remove the general difficulty of searching for a valid plan.

Business use

Planning graphs help explain dependencies, conflicts, and reasons a proposed sequence is too short. Their value depends on accurate preconditions and effects. Review shared resources, restoration actions, and final-state requirements before trusting the output. Distinguish minimizing parallel action layers from minimizing the number of actions, financial cost, or actual duration. These objectives can favor different plans and require appropriate modeling.

Check your understanding

Why are PrepareX and PrepareY mutex initially?

Answer: Each deletes Free, which the other requires.

When can both readiness goals coexist in the example?

Answer: At P3, after three action steps.

If Free is also a final goal, what must follow the shown plan?

Answer: Another Reset, giving four steps.

Related terms

Graphplan
Mutex
Precondition
State-space search
STRIPS
action effect
persistence action
planning heuristic
parallel plan

Learn next

Construct the workshop's first three proposition layers and mark the stated exclusions. Then add a second independent bench and define its actions precisely before predicting how the minimum number of layers changes.

Sources

Blum and Furst, Fast Planning Through Planning Graph Analysis: https://www.cs.cmu.edu/~avrim/Papers/graphplan.pdf Russell and Norvig, Planning, section on planning graphs: https://aima.cs.berkeley.edu/newchap11.pdf AIMA glossary, planning graph: https://github.com/aimacode/aima-glossary/blob/master/glossary.md

Previous: Planning and control layer Next: Plate notation