Planning Heuristics and GraphPlan

This builds on Classical Planning, which set up the PDDL representation, forward and backward search, and the relaxation heuristics that ignore preconditions or delete lists. Here we build the data structure that sharpens those heuristics and can be searched for a plan directly.

The planning graph and GraphPlan

Every heuristic so far can be inaccurate. A planning graph is a data structure that gives better estimates, and can also be searched directly for a plan by the GraphPlan algorithm. It is a polynomial-size approximation to the exponential tree of all possible action sequences: it cannot say for certain whether the goal is reachable, but it estimates how many steps it takes, and it never overestimates — so the estimate is admissible.¹

A planning graph is a directed graph of alternating levels: a state level $S_0$ for the initial state, an action level $A_0$ of every action that might apply in $S_0$, then $S_1$, $A_1$, and so on. Roughly, $S_i$ holds every literal that could hold at time $i$, and $A_i$ every action that could have its preconditions met at time $i$. Planning graphs work only for propositional (variable-free) problems, so the schemas are propositionalized first.

Two devices make the levels work. A persistence action (or no-op), drawn as a small square, carries every literal forward unchanged — for each literal $C$ we add an action with precondition $C$ and effect $C$, so a literal can persist if no action negates it. And mutex (mutual-exclusion) links, drawn as curved lines, record pairs that cannot co-occur. Constructing the graph never requires choosing among actions — it just records which choices are impossible — so it stays polynomial.

The graph is built until it levels off — two consecutive levels are identical. For a problem with $l$ literals and $a$ actions each $S_i$ has at most $l$ nodes and $A_i$ at most $a+l$ (counting no-ops), so a graph of $n$ levels has size $O(n(a+l{)}^2)$, and building it takes the same time.

Expanding the graph, level by level

Work through the have cake and eat cake too problem in full. Two fluents are in play, $Have(Cake)$ and $Eaten(Cake)$, and there are two real actions:

The initial state is $Have(Cake)\wedge \neg Eaten(Cake)$, and the goal is $Have(Cake)\wedge Eaten(Cake)$ — have your cake and have eaten it too. Build the graph:

• $S_0$ holds the two initial literals: $Have(Cake)$ and $\neg Eaten(Cake)$.
• $A_0$ holds every action whose preconditions are present and non-mutex in $S_0$. $Eat(Cake)$ qualifies (its precondition $Have(Cake)$ is in $S_0$); $Bake(Cake)$ does not, since its precondition $\neg Have(Cake)$ is absent. Two persistence actions also appear, one for each $S_0$ literal.
• $S_1$ holds every literal any $A_0$ action can produce. $Eat$ adds $\neg Have(Cake)$ and $Eaten(Cake)$; the persistence actions carry $Have(Cake)$ and $\neg Eaten(Cake)$ forward. So $S_1=\{Have,\neg Have,Eaten,\neg Eaten\}$ — all four literals now appear.
• $A_1$ adds $Bake(Cake)$, whose precondition $\neg Have(Cake)$ is now present, alongside $Eat(Cake)$ and the four persistence actions.
• $S_2$ again holds all four literals. Because $S_2$ carries the same literals as $S_1$ with the same mutex structure, the graph has leveled off after $S_2$.

The mutexes are what make the graph accurate, and each of the five rules can be shown firing on this small instance.

Reading the five rules off this graph:

• Inconsistent effects. $Eat(Cake)$ has effect $\neg Have(Cake)$; the $Have$-persistence no-op has effect $Have(Cake)$. One negates the other, so the two actions are mutex in $A_0$.
• Interference. $Eat(Cake)$ deletes $Have(Cake)$, which is the precondition of the $Have$-persistence no-op. An effect of one negates a precondition of the other, so they are mutex (the pair marked interfere above).
• Competing needs. In a later level, $Bake(Cake)$ needs $\neg Have(Cake)$ while $Eat(Cake)$ needs $Have(Cake)$; those preconditions are themselves a mutex literal pair, so the two actions are mutex by competing needs.
• Negation (literals). In $S_1$, $Have(Cake)$ and $\neg Have(Cake)$ are trivially mutex — one is the negation of the other.
• Inconsistent support (literals). In $S_1$, $Have(Cake)$ and $Eaten(Cake)$ are mutex: the only way to have $Eaten(Cake)$ at this level is $Eat$, whose companion effect is $\neg Have(Cake)$, and the only way to keep $Have(Cake)$ is the no-op, which is mutex with $Eat$ by interference. Every pair of producers conflicts, so the literals are mutex. This is why the goal $Have\wedge Eaten$ cannot be read as achieved at $S_1$ — the search must expand to $S_2$, where $Bake$ has broken the support conflict and the pair is no longer mutex.

Heuristics from the planning graph

Once built, the graph supplies several estimates. If any goal literal never appears in the graph, the problem is unsolvable. Otherwise the level cost of a goal literal $g_i$ — the first level at which it appears — estimates the cost of achieving it. Because a level may host several actions at once, a serial planning graph (one that adds mutexes between every pair of non-persistence actions, forcing one real action per level) gives level costs closer to the true action count.

To estimate the cost of a conjunction of goals, three heuristics build on level costs. Max-level takes the maximum level cost over the goals: admissible, but often loose. Level-sum adds the level costs (the subgoal-independence assumption): inadmissible in general but accurate for largely decomposable problems. Set-level finds the first level at which all goal literals appear with no pair mutex: admissible, dominates max-level, and works very well when subgoals interact, because the mutexes capture the interaction the other two ignore.

Serial versus parallel graphs, and a worked level cost

A plain planning graph is parallel: level $A_i$ may hold several non-mutex actions at once, and a level index counts rounds of simultaneous action, not individual steps. A serial planning graph adds a mutex between every pair of real (non-persistence) actions in a level, so at most one real action can be chosen per level. A serial graph therefore counts steps the way a totally ordered plan does, and its level costs track the true plan length more closely, at the price of more levels and a larger graph.

The difference shows up numerically on the cake problem. Take the two goal literals and read their level costs off the parallel graph built above:

• $Have(Cake)$ appears already at $S_0$, so its level cost is $0$.
• $Eaten(Cake)$ first appears at $S_1$ (produced by $Eat$ in $A_0$), so its level cost is $1$.

Now compute the three conjunction heuristics for the goal $Have(Cake)\wedge Eaten(Cake)$:

Max-level says $1$: at least one action is needed, which is true but weak — one action cannot achieve the goal, because $Eat$ makes $Eaten$ true only by making $Have$ false. Level-sum says $2$, treating the two subgoals as independent. Set-level looks for the first level where both literals appear and are non-mutex; at $S_1$ they are mutex by inconsistent support, so set-level must go to $S_2$, giving $2$. The true optimal plan is $[Eat(Cake),Bake(Cake)]$ of length $2$, so here set-level is exact while max-level underestimates. Set-level's extra accuracy comes entirely from consulting the mutex that max-level and level-sum discard.

The GraphPlan algorithm

GraphPlan extracts a plan directly from the graph rather than merely reading a heuristic off it. It alternates two operations. $\text{Expand-Graph}$ adds one level. When all goals appear non-mutex in the current state level, $\text{Extract-Solution}$ searches backward through the graph for a conflict-free plan; if that fails, GraphPlan expands another level and tries again.

$\text{Extract-Solution}$ can be cast as a Boolean CSP (variables are actions at each level, values are in or out of the plan, constraints are the mutexes and goals) or, equivalently, as a backward search: start at the last level $S_n$ with the problem's goals, and at each state pick a conflict-free subset of the previous action level whose effects cover the current goals, taking the selected actions' preconditions as the next set of goals. Conflict-free means no two chosen actions are mutex and no two of their preconditions are mutex. The search succeeds when it reaches $S_0$ with all goals satisfied. When it fails for a set of goals at a level, that $(level,goals)$ pair is recorded as a no-good and reused, both to prune and in the termination test.

Extracting the cake plan

Follow $\text{Extract-Solution}$ on the cake graph, which has leveled off with a solution appearing at $S_2$. The goal set is $\{Have(Cake),Eaten(Cake)\}$, both non-mutex at $S_2$, so extraction begins there and works backward.

At $S_2$, cover $Have(Cake)$ with $Bake$ from $A_1$ and cover $Eaten(Cake)$ with the $Eaten$-persistence no-op. These two are conflict-free, so their preconditions become the goals at $S_1$: $Bake$ needs $\neg Have(Cake)$ and the no-op needs $Eaten(Cake)$. At $S_1$, both are covered by choosing $Eat$ in $A_0$ (it produces $\neg Have$ and $Eaten$ together), whose single precondition $Have(Cake)$ is the $S_0$ goal — and $Have(Cake)$ holds in $S_0$. Extraction reaches $S_0$ with all goals met, so it succeeds. Reading the chosen real actions from $S_0$ forward gives the plan $[Eat(Cake),Bake(Cake)]$. Had a level's goal set failed to extract, that $(level,goals)$ pair would be cached as a no-good so no later search revisits it.

GraphPlan is guaranteed to terminate. Literals and actions increase monotonically (persistence actions keep literals around; an action reappears once its preconditions do), while mutexes and no-goods decrease monotonically. Since neither count can pass its finite bound or drop below zero, the graph and its no-goods must both level off; once they have, if a goal is still missing or mutex with another, GraphPlan can stop and return failure — no later level could add a solution.

Other approaches

Three families dominate fully automated classical planning today: forward search with strong heuristics (above), search over a planning graph (GraphPlan and its descendants), and translation to Boolean satisfiability. The last, and two logic-flavored alternatives, are covered below.

SATPlan. Planning as satisfiability translates a PDDL problem into a propositional formula that a SAT solver decides, following the same encoding as propositional logic inference. Propositionalize the actions, assert $F^0$ for each initial-state fluent and $\neg F^0$ for the rest, expand the goal into a disjunction over constants, and add three families of axioms: successor-state axioms $F^{t+1}\leftrightarrow ActionCauses{F}^t\vee (F^t\wedge \neg ActionCausesNot{F}^t)$ tying each fluent to the actions that make it true or false, precondition axioms $A^t\Rightarrow \text{Pre}(A{)}^t$, and action-exclusion axioms making every action distinct. The result is handed to a SAT solver, which searches for a satisfying assignment — a plan — up to a bounded horizon.

For example, instantiate the successor-state schema for the fluent $Have(Cake)$ in the cake problem. Only $Bake$ makes it true and only $Eat$ makes it false, so at time $t$ the axiom reads

$Have(Cake)$ holds at $t+1$ exactly when $Bake$ was applied at $t$, or it held at $t$ and $Eat$ was not applied to remove it. This single biconditional encodes both the effect (the $Bake$ disjunct) and the frame axiom (the persistence disjunct) for that fluent in one line, which is why the encoding grows only linearly in fluents times horizon rather than quadratically. The companion precondition axiom $Eat(Cake{)}^t\Rightarrow Have(Cake{)}^t$ forbids eating a cake that is not there, and an action-exclusion axiom $\neg (Eat(Cake{)}^t\wedge Bake(Cake{)}^t)$ forbids doing both at once. With a horizon of two steps the solver finds a satisfying assignment that sets $Eat(Cake{)}^0$ and $Bake(Cake{)}^1$ true and the rest false — the same two-step plan the planning graph extracted.

Constraint satisfaction. A bounded planning problem encodes naturally as a CSP, much like the SAT encoding but with a single variable $Actio{n}^t$ per time step whose domain is the set of possible actions — no per-action variables, no exclusion axioms. Planning graphs themselves can be compiled into a CSP.

Partial-order planning. Every approach so far produces a totally ordered plan: a strict linear sequence. That over-commits — loading 30 packages onto one plane and 50 onto another are independent, yet a total order arbitrarily interleaves them. A partial-order plan is instead a set of actions plus ordering constraints $Before(a_i,a_j)$, imposed only where genuinely required.

Partial-order plans are built by searching the space of plans rather than the space of states: begin with the empty plan (just Start and Finish), find a flaw (an unachieved precondition), and fix it by adding an action or an ordering constraint, always making the least commitment that resolves the flaw and no more. Through the 1980s and 90s this was the leading way to handle independent subproblems, because it represents branches of a plan explicitly. By 2000 forward-search planners had developed heuristics good enough to find those independent subproblems on their own, so partial-order planning is no longer competitive on general classical problems — but it remains the technology of choice for tasks like operations scheduling, and for domains where a human must read and verify the plan, such as spacecraft operations.

PDDL and modern planning heuristics

The relaxations in this lesson started a line of research that turned domain-independent planning into a competitive field with a common benchmark and steadily better heuristics.

A shared language came first. McDermott and colleagues introduced PDDL, the Planning Domain Definition Language, in 1998 as the input format for the first International Planning Competition (IPC), held at the AIPS conference.² A common syntax meant planners could be run head to head on the same domains, and the competition has recurred since, driving successive extensions of the language for numeric fluents, durative actions, and preferences.

Then came sharper heuristics built on the relaxations here. Bonet and Geffner cast planning as heuristic search and defined the additive and max heuristics $h_{\text{add}}$ and $h_{\max }$ from the delete relaxation, estimating a conjunction's cost by summing or maximizing over the subgoals' relaxed costs.³ In the same period, Hoffmann and Nebel's FF (FastForward) planner extracted a relaxed plan from a delete-relaxed planning graph and used its length as the heuristic, paired with an enforced-hill-climbing search; FF won the 2000 IPC and its relaxed-plan heuristic became a standard baseline.⁴

Hoffmann, Porteous, and Sebastia formalized a complementary signal, landmarks — facts that must hold at some point in every plan — and showed how to extract them and order them, turning which subgoals are unavoidable into a heuristic.⁵ Richter and Westphal combined a landmark-count heuristic with FF's relaxed-plan heuristic in the LAMA planner, which won the sequential satisficing track of the 2008 IPC.⁶ The connection to AIMA's chapter is direct: every one of these systems reads its heuristic off a mechanically relaxed version of the schemas, exactly as this lesson develops.

The takeaway

Classical planning makes a single trade. By committing to a factored representation — states as sets of fluents, actions as schemas that name only what changes — it gives up the opacity of atomic search states, and in return a program gains the ability to read the problem's structure. That structure lets forward search regress and lift, lets a relaxation drop a precondition or a delete list mechanically, and lets a planning graph bound the distance to the goal. The hand-built heuristics of informed search came one insight at a time; here, the same accuracy is derived automatically, because the representation itself is something the planner can inspect.