Does mutex mean the two actions can never both occur?

Not necessarily. They may be forbidden in the same step while remaining usable sequentially.

Can mutex relationships disappear at later levels?

Yes. Additional actions can provide compatible support for facts that conflicted earlier.

If no goal pair is mutex, has a plan been found?

No. Pairwise checks are useful pruning information, but joint feasibility and a supporting action sequence still need to be established.

AI Glossary / Graphs and symbolic AI / Intermediate

Mutex

Definition

Mutex is short for mutual exclusion. In a planning graph, a mutex relationship marks two actions that cannot occur together at a particular action level, or two propositions that cannot both hold at a particular proposition level under the planning model. These relationships help a planner reject incompatible combinations before exploring them in detail.

What it means

A planning graph contains possible actions and possible facts across successive levels. Their presence does not mean every combination is jointly achievable. Mutex annotations add information about conflicts that would otherwise be hidden by this compact representation.
The meaning is specific to the level and model. Two facts can be incompatible early in a plan yet compatible after additional actions. Other exclusions persist because they follow from the action definitions or domain invariants. This entry concerns automated planning; an operating-system mutex is a related mutual-exclusion mechanism for coordinating access, not the same data structure or reasoning procedure.

How it works

Planning-graph systems mark action conflicts when effects contradict, when one action removes a condition needed by another, or when their prerequisites are themselves mutually exclusive. The original Graphplan formulation groups effect and precondition deletion conflicts under interference and also propagates competing-needs conflicts.
Proposition conflicts propagate from their possible supporting actions. If every way of supporting one fact conflicts with every way of supporting another, the pair is marked mutex at that level. Persistence actions, which carry existing facts forward, are part of this reasoning. These efficient pairwise rules do not capture every possible incompatibility among larger sets of goals, so absence of a mutex mark is not a complete proof of plan feasibility.

Three practical examples

A transport planner can reject loading a package at a depot in the same parallel step as moving its vehicle away, when movement deletes a loading prerequisite.
A robot planner can discover that two destination facts cannot both hold for the same robot in a modeled state.
A planning debugger can inspect mutex explanations to find missing resource assumptions or unexpectedly conflicting action effects.

Think of it this way

Think of a timetable that marks two activities as unable to share a slot. The marker helps avoid a bad combination before building the whole schedule. The analogy is limited because planning mutex relationships can be inferred through several levels of prerequisites and effects, and a pairwise timetable check cannot capture every larger scheduling conflict.

Worked example

Consider an invented delivery model. Initially, VanAtDepot, PackageAtDepot, and Fuel are true. Load requires VanAtDepot and PackageAtDepot; it adds PackageInVan and deletes PackageAtDepot. Drive requires VanAtDepot and Fuel; it adds VanAtCustomer and deletes VanAtDepot and Fuel.
Both Load and Drive appear as individually possible actions at the first action level. However, they are mutex: Drive deletes VanAtDepot, a prerequisite of Load. They cannot share that parallel step under Graphplan's noninterference semantics.
At the next proposition level, PackageInVan is supported by Load and VanAtCustomer by Drive. With only these ways to establish the two facts at that level, their supports are mutex, so the facts are marked mutex too.
At a later level, a sequential plan can load first and drive second. PackageInVan persists while Drive establishes VanAtCustomer, since Drive does not delete PackageInVan in this model. The two facts can now coexist. The example shows a level-dependent exclusion, not a permanent assertion that a package and its vehicle can never reach the customer together.

Illustrative case study

In a fictional dispatch-planning prototype, a manager sees both “package loaded” and “vehicle arrived” in a planning-graph display and assumes the delivery can finish after one action step. The developer adds the mutex annotations to the display and explains that the facts represent separate possibilities at that early level.
The team verifies the two-step load-then-drive plan and checks that the action model preserves a loaded package during travel. It also documents the parallel-step semantics so users do not interpret every visible action as simultaneously executable. The case illustrates explanation of a planning representation, not measured dispatch performance.

Common misconceptions and mistakes

Do not confuse individual reachability with joint reachability. A graph level can contain two facts that cannot be achieved together. Conversely, an early mutex relationship does not necessarily rule out a goal permanently; additional levels may provide compatible support.
Another mistake is assuming that pairwise compatibility guarantees compatibility of an entire goal set. Three or more goals can be jointly impossible even when each pair is achievable. The planner still needs plan extraction and other reasoning. Finally, mutex annotations are only as meaningful as the action model: an omitted capacity constraint cannot be recovered merely by trusting a conflict display.

Business use

For organizations evaluating automated planning, mutex explanations can make rejected schedules or action combinations easier to inspect. They connect a conflict to concrete prerequisites, effects, or supporting actions, rather than presenting an unexplained failure.
Use these explanations during model review. Check whether shared resources, location changes, and persistence are represented correctly. Keep a distinction between a symbolic parallel step and physical elapsed time: a planning model may not include realistic durations. A successful symbolic plan still needs an execution design that matches the real system's timing and control requirements.

Check your understanding

Why can Load and Drive not share the first action step in the worked example?

Answer: Drive deletes VanAtDepot, which Load requires. Under the stated noninterference semantics, this deletion makes the actions mutex even though both are individually applicable initially.

Related terms

Planning graph
Graphplan
Mutual exclusion
action precondition
interference
competing needs
inconsistent support
persistence action
joint feasibility

Learn next

Next, add an action that independently delivers the package without using the van. Determine whether it provides a non-mutex support for PackageAtCustomer at an earlier level. Focus on all supporting-action pairs rather than assuming that one conflicting support pair is enough to mark two propositions mutex.

Sources

Blum and Furst, Fast Planning Through Planning Graph Analysis, sections 2.2 and 3 on exclusion propagation and search: https://www.cs.cmu.edu/~avrim/Papers/graphplan.pdf . Relevant original-paper sections were read, including the limits of pairwise exclusion tests. The van example and fictional case are original simplified illustrations.

Previous: Mutation rate Next: Mutual information