What does mutex mean?

It marks a pair of actions or facts that cannot coexist at the relevant planning level under the algorithm's rules.

Does Graphplan minimize the number of actions?

Its original optimality guarantee concerns the number of parallel steps under its stated semantics, which is a different objective.

Can all non-mutex goals automatically be achieved together?

No. Pairwise compatibility is not enough to certify every combination; the algorithm still searches for a consistent supporting plan.

AI Glossary / Graphs and symbolic AI / Intermediate

Graphplan

Definition

Graphplan is an automated planning algorithm developed by Avrim Blum and Merrick Furst. It builds a layered planning graph containing possible facts and actions, tracks pairs that cannot coexist, and searches backward for actions that jointly achieve the goals. The original algorithm addresses classical, STRIPS-like planning problems with explicitly described action preconditions and effects.

What it means

A planner needs more than a list of individually possible actions. It must find a compatible combination whose preconditions can all be supported and whose effects achieve the requested result. Graphplan organizes useful information about these possibilities before and during the search for a plan.
Its planning graph is not the full state-space graph. A fact layer can contain facts arising from different alternative histories, including incompatible alternatives. Being present in a layer therefore means something weaker than being simultaneously true in one actual state. Mutual-exclusion information and plan extraction help resolve that difference.

How it works

Begin with the initial facts. Add an action layer containing actions whose requirements are supported, along with persistence actions that carry facts forward. Add the facts those actions could produce, then repeat to extend the planning horizon. Mark mutually exclusive action or fact pairs, commonly called mutex pairs.
When the goals occur without the relevant pairwise exclusions at a fact layer, attempt backward extraction. Select compatible supporting actions and recursively support their preconditions at earlier layers. Record failed goal combinations to avoid repeating unsuccessful searches. If extraction fails, the graph may be extended and the search attempted again. Non-mutex goals are a useful screening condition, not by themselves a complete plan.

Three practical examples

A planning class models preparation tasks with explicit prerequisites and studies which tasks can share a parallel step.
A research team reproduces a classical planning benchmark using the original algorithm's assumptions and plan-length definition.
A workflow-modeling exercise uses mutex relationships to expose actions that compete for a modeled exclusive resource.

Think of it this way

Think of building a timetable of things that might be possible at each stage, while marking combinations that clash. The planner then works backward to select a consistent route through those possibilities. The analogy is limited because the planning graph is a formal reachability structure, not a fully committed calendar, and its discrete steps need not equal real elapsed minutes.

Worked example

Consider a toy preparation problem with initial facts RawA and RawB. Action PrepareA requires RawA, adds ReadyA, and deletes RawA. PrepareB similarly changes RawB into ReadyB. Action Finish requires both ReadyA and ReadyB and adds Done. The goal is Done, and the model includes no shared-resource restriction between the preparation actions.
At the first action layer, PrepareA and PrepareB can both appear and are compatible. At the next fact layer, ReadyA and ReadyB are available together. Finish can then occur in the second action layer, producing Done. The resulting parallel plan has two steps: {PrepareA, PrepareB}, then {Finish}. It contains three non-persistence actions.
Now add a single reusable tool. Both preparation actions require ToolFree and delete it; a separate return-tool action is needed to restore availability after preparation. The original two preparation actions are now mutex because each deletes a precondition of the other. The earlier two-step plan no longer applies. This change follows from the altered action model, not from a change in the goal. The example also shows why parallel depth and total action count are different measurements.

Illustrative case study

In a fictional course project, Juniper Studio models two preparation jobs as independent and obtains a parallel plan. A reviewer notices that both jobs actually need the same exclusive machine, which the model omits.
The team adds explicit machine-availability facts and acquisition/release effects. It then checks the resulting plan against the revised action definitions. The invented case illustrates that an algorithm can correctly solve an incomplete model while producing a plan unsuitable for the intended situation. It makes no claim of industrial scheduling performance.

Common misconceptions and mistakes

A planning graph is not already a valid plan, and the presence of every goal in one layer does not prove joint achievability. Even absence of pairwise mutexes does not eliminate every higher-order incompatibility; backward extraction still matters.
The original algorithm's shortest-plan result concerns its parallel-step semantics, not automatically the smallest number of actions, lowest financial cost, or shortest real execution time. Graphplan also does not inherently solve arbitrary uncertainty, continuous control, or partially observed tasks. Those require an appropriate extension or a different planning formulation.

Business use

Graphplan is useful for understanding how explicit action models support systematic planning and how incompatibility information can prune search. Its ideas also provide context for later planning techniques and planning-graph heuristics.
For a project inspired by this approach, document initial facts, goals, action preconditions, effects, and resource restrictions. Specify whether plan quality means parallel depth, action count, cost, or another measure. Validate the extracted plan independently against the action model, and assess whether the model captures the operational requirements that matter. A formally valid plan remains conditional on those modeling choices.

Check your understanding

Why does the toy plan have two parallel steps but three actions?

Answer: PrepareA and PrepareB share the first step because they are independent in the initial model. Finish occupies the second step. Counting steps groups compatible actions, while counting actions counts all three individually.

Related terms

Planning graph
Precondition
automated planning
STRIPS
effect
mutual exclusion
persistence action
plan extraction
parallel plan

Learn next

Draw fact and action layers for the toy problem and mark the new mutex after adding the shared tool. Then compare parallel plan depth with total action count. This clarifies both the representation and the exact kind of optimality being discussed.

Sources

Sources: Blum and Furst, Fast Planning Through Planning Graph Analysis, original paper: https://www.cs.cmu.edu/afs/cs/usr/avrim/www/Papers/graphplan.pdf Author's Graphplan project page: https://www.cs.cmu.edu/~avrim/graphplan.html

Previous: Graphite graph generative model Next: Grasping