Understanding Planning Graph
A planning graph alternates state levels and action levels. The first state level holds the literals of the initial state together with the negation of every atom the domain mentions and the initial state omits. Each action level holds every action whose preconditions are all present and pairwise consistent at the preceding state level, plus a persistence action for each literal that simply carries it forward. The next state level holds every literal produced by any action in that action level. Construction is polynomial in the size of the problem and involves no search at all, which is what makes the structure affordable as a heuristic source.
A level does not assert that everything in it can hold simultaneously, and mutual-exclusion links record where it cannot. Two actions are mutex if they have inconsistent effects, meaning one deletes what the other adds; if they interfere, meaning one deletes a precondition of the other; or if they have competing needs, meaning preconditions that were mutex at the previous level. Two literals are mutex if one is the negation of the other, or if every pair of actions producing them is itself mutex. These conditions are local and cheap, which is precisely why the resulting approximation is one-sided.
Growing the graph eventually produces a level identical to its predecessor in both literals and mutexes, at which point the graph has levelled off and no further level can add information. The level cost of a literal is the index of the first level at which it appears, and because a literal absent at level i is genuinely unachievable within i steps, level costs are lower bounds. That yields three heuristics for a conjunctive goal: the maximum level cost among the goal literals, their sum, and the set level, the first level at which all of them appear with no mutex pair among them.
Max-level and set-level are admissible, and set-level dominates max-level because it additionally insists that the goals be jointly consistent. Level-sum adds level costs as though the subgoals were independent and can therefore overestimate, so it is inadmissible in general, though it is frequently the most informative of the three in practice. The graph also underpins GraphPlan, which searches backwards through the levels for a plan directly rather than only using the structure to score states.
How to Calculate
levelcost(l) = min{ i : l ∈ S_i }; setlevel(g) = min{ i : g ⊆ S_i, no pair of g mutex at S_i }
where
- S_i
- the literals of the i-th state level of the graph
- l
- a single literal whose earliest possible appearance is being measured
- g
- the conjunctive goal, treated as a set of literals
- mutex
- a recorded pair that provably cannot hold together at that level
Example of Planning Graph
In the "have cake and eat cake too" problem, S0 holds Have(Cake) and ¬Eaten(Cake) with no mutexes. Bake cannot appear in the first action level because its precondition ¬Have(Cake) is not yet present.
At S1 all four literals are present with four mutex pairs. Have(Cake) and Eaten(Cake) are mutex because their only producers are the persistence action for Have and Eat(Cake), and Eat deletes Have, which is interference.
The mutex disappears at S2, where the graph levels off. Max-level and level-sum both return 1, set-level returns 2, and the optimal plan - eat the cake, then bake another - indeed has length 2, so only set-level is exact here.
Advantages and Disadvantages
Pros
- Built in polynomial time with no search, so the cost of the heuristic stays far below the cost of planning.
- Mutex reasoning catches interactions between subgoals that per-literal heuristics systematically miss.
- Supplies a whole family of heuristics from one structure, with a clear admissibility ordering among them.
Cons
- Defined for propositional problems, so a schema domain must be grounded first, which can be expensive.
- The approximation is one-sided: absence proves unachievability, but presence proves nothing.
- Only pairwise mutexes are computed, so larger inconsistencies among three or more literals go undetected.
Frequently Asked Questions
Why does the graph include persistence actions?
Without them a literal true at one level could vanish at the next simply because no action happened to re-produce it. A persistence action, sometimes called a no-op, has the literal as both precondition and effect, which lets it carry forward and lets mutex reasoning treat carrying it forward as a choice competing with other actions.
What does levelling off mean and why does it happen?
Levels are monotone: literals accumulate and mutexes only disappear. Since both are bounded, the process must reach a level identical to its predecessor in literals and mutexes, after which every later level is identical too. That is the point at which no further information can be extracted from the graph.
If level-sum is inadmissible, why use it?
Admissibility guarantees optimality but says nothing about speed, and max-level is often so weak that search is impractical. Level-sum is usually much closer to the true cost, so a planner willing to give up a guarantee of optimality frequently solves problems the admissible heuristics cannot reach at all.
The Bottom Line
A planning graph buys information about a hard problem by solving a cheap relaxation of it exhaustively rather than approximately. The mutex links are the substance: they turn a naive reachability count into a structure that notices when two goals get in each other’s way, which is exactly the failure mode that sinks simpler planning heuristics.