--- title: Planning Heuristics and GraphPlan module: Logic and Planning moduleNumber: 3 lessonNumber: 8 order: 308 summary: > Every relaxation heuristic can be inaccurate, and none can tell how far apart subgoals sit. The planning graph is a polynomial-size structure that does better: leveled off the problem, it yields admissible distance estimates and a record of which actions and fluents cannot coexist. This part builds the graph, reads heuristics from it, extracts plans with GraphPlan, and closes with the other classical approaches — SATPlan and partial-order planning — and the representational trade that makes all of it work. topics: [Logic] sources: - book: AIMA ref: "Ch. 10 — Classical Planning; §10.3 Planning Graphs" - book: AIMA ref: "§10.4 Other Classical Planning Approaches" --- This builds on [Classical Planning](/artificial-intelligence/logic-and-planning/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.[^graph] 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. $$ % caption: The planning graph for the "have cake and eat cake too" problem up to % level $S_2$. Small squares are persistence actions (no-ops), rectangles are real % actions, straight lines are preconditions and effects, and curved links are % mutexes. Not every mutex is drawn. \begin{tikzpicture}[>=stealth, font=\scriptsize, lit/.style={font=\scriptsize, anchor=west}, act/.style={draw, minimum width=15mm, minimum height=5mm, font=\scriptsize, fill=black!3}, noop/.style={draw, minimum size=3mm, fill=white}] \definecolor{acc}{HTML}{2348F2} \definecolor{mx}{HTML}{C0392B} % column headers \foreach \x/\lab in {0/S0, 2.6/A0, 5.2/S1, 7.8/A1, 10.4/S2} { \node[font=\scriptsize\bfseries, text=black] at (\x,3.55) {\lab}; } % --- S0 literals --- \node[lit] (h0) at (-0.6,2.2) {Have(Cake)}; \node[lit] (ne0) at (-0.6,0.2) {not Eaten(Cake)}; % --- A0 --- \node[noop] (nh0) at (2.6,2.2) {}; \node[act] (eat0) at (2.6,1.2) {Eat(Cake)}; \node[noop] (nne0) at (2.6,0.2) {}; % --- S1 --- \node[lit] (h1) at (4.6,2.6) {Have(Cake)}; \node[lit] (nh1) at (4.6,1.9) {not Have(Cake)}; \node[lit] (e1) at (4.6,0.7) {Eaten(Cake)}; \node[lit] (ne1) at (4.6,0.0) {not Eaten(Cake)}; % --- A1 --- \node[act] (bake1) at (7.8,2.9) {Bake(Cake)}; \node[noop] (nh1a) at (7.8,2.4) {}; \node[noop] (nnh1a) at (7.8,1.9) {}; \node[act] (eat1) at (7.8,1.2) {Eat(Cake)}; \node[noop] (ne1a) at (7.8,0.7) {}; \node[noop] (nne1a) at (7.8,0.0) {}; % --- S2 --- \node[lit] (h2) at (9.6,2.9) {Have(Cake)}; \node[lit] (nh2) at (9.6,2.2) {not Have(Cake)}; \node[lit] (e2) at (9.6,0.7) {Eaten(Cake)}; \node[lit] (ne2) at (9.6,0.0) {not Eaten(Cake)}; % edges S0 -> A0 \draw[black] (h0.east) -- (nh0.west); \draw[black] (h0.east) -- (eat0.west); \draw[black] (ne0.east) -- (nne0.west); % edges A0 -> S1 \draw[black] (nh0.east) -- (h1.west); \draw[black] (eat0.east) -- (nh1.west); \draw[black] (eat0.east) -- (e1.west); \draw[black] (nne0.east) -- (ne1.west); % a couple of mutex links (curved) \draw[mx, thick] (h1.west) to[bend right=32] (e1.west); \draw[mx, thick] (eat0.north) to[bend left=28] (nh0.south); \end{tikzpicture} $$ 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. > **Definition (Mutex link).** A mutual-exclusion constraint between two nodes at the > same level. Two _actions_ are mutex if their effects are inconsistent, if one's > effect negates the other's precondition (interference), or if their preconditions > are themselves mutex (competing needs). Two _literals_ are mutex if one negates the > other, or if every pair of actions achieving them is mutex (inconsistent support). 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: $$ % caption: The two action schemas for the cake problem. Eat consumes the cake; % Bake creates a new one, but only when there is none to overwrite. \begin{tikzpicture}[>=stealth, font=\footnotesize, sch/.style={draw, align=left, minimum width=52mm, minimum height=17mm, inner sep=6pt, font=\scriptsize}] \definecolor{acc}{HTML}{2348F2} \node[sch] (eat) at (0,0) {\textbf{\texttt{Eat(Cake)}}\\[2pt] pre: \texttt{Have(Cake)}\\ e\/f\/f: \texttt{not Have(Cake)}\\ \phantom{e\/f\/f: }\texttt{and Eaten(Cake)}}; \node[sch] (bake) at (6.4,0) {\textbf{\texttt{Bake(Cake)}}\\[2pt] pre: \texttt{not Have(Cake)}\\ e\/f\/f: \texttt{Have(Cake)}}; \end{tikzpicture} $$ 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. $$ % caption: Concrete mutexes in the cake graph. In level $S_1$, the pair % $Have(Cake)$ / $Eaten(Cake)$ is mutex by inconsistent support (every way of % producing them conflicts); in $A_0$, Eat and the Have-persistence no-op are mutex % by interference. Red curves mark the mutex pairs named in the text. \begin{tikzpicture}[>=stealth, font=\scriptsize, lit/.style={font=\scriptsize, anchor=west}, actn/.style={draw, minimum width=14mm, minimum height=5mm, font=\scriptsize, fill=black!3}, noop/.style={draw, minimum size=3mm, fill=white}] \definecolor{acc}{HTML}{2348F2} \definecolor{mx}{HTML}{C0392B} \foreach \x/\lab in {0/S0, 3.0/A0, 6.0/S1} { \node[font=\scriptsize\bfseries, text=black] at (\x,3.3) {\lab}; } % S0 \node[lit] (h0) at (-0.7,2.2) {Have(Cake)}; \node[lit] (ne0) at (-0.7,0.2) {not Eaten(Cake)}; % A0 \node[noop] (nh0) at (3.0,2.2) {}; \node[actn] (eat0) at (3.0,1.2) {Eat(Cake)}; \node[noop] (nne0) at (3.0,0.2) {}; % S1 \node[lit] (h1) at (5.4,2.7) {Have(Cake)}; \node[lit] (nh1) at (5.4,2.0) {not Have(Cake)}; \node[lit] (e1) at (5.4,0.8) {Eaten(Cake)}; \node[lit] (ne1) at (5.4,0.1) {not Eaten(Cake)}; % edges \draw[black] (h0.east) -- (nh0.west); \draw[black] (h0.east) -- (eat0.west); \draw[black] (ne0.east) -- (nne0.west); \draw[black] (nh0.east) -- (h1.west); \draw[black] (eat0.east) -- (nh1.west); \draw[black] (eat0.east) -- (e1.west); \draw[black] (nne0.east) -- (ne1.west); % mutex: interference in A0 (Eat deletes Have, no-op needs/keeps Have) \draw[mx, thick] (eat0.north) to[bend left=22] (nh0.south); \node[mx, font=\scriptsize, anchor=east] at (2.25,1.15) {interfere}; % mutex: inconsistent support in S1 (Have vs Eaten) \draw[mx, thick] (h1.west) to[bend right=34] (e1.west); \node[mx, font=\scriptsize, anchor=west] at (5.05,1.75) {inconsist.}; \end{tikzpicture} $$ 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)$: $$ h_{\max} = \max(0, 1) = 1, \qquad h_{\text{sum}} = 0 + 1 = 2, \qquad h_{\text{set}} = 2. $$ 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. $\textsc{Expand-Graph}$ adds one level. When all goals appear non-mutex in the current state level, $\textsc{Extract-Solution}$ searches backward through the graph for a conflict-free plan; if that fails, GraphPlan expands another level and tries again. ```algorithm caption: $\textsc{GraphPlan}(problem)$ — extract a plan from the planning graph $graph \gets \textsc{Initial-Planning-Graph}(problem)$ $goals \gets \textsc{Conjuncts}(problem.\textsc{Goal})$ $nogoods \gets$ an empty hash table for $tl = 0$ to $\infty$ do if $goals$ all non-mutex in $S_{tl}$ of $graph$ then $solution \gets \textsc{Extract-Solution}(graph, goals, \textsc{NumLevels}(graph), nogoods)$ if $solution \neq failure$ then return $solution$ if $graph$ and $nogoods$ have both leveled off then return $failure$ $graph \gets \textsc{Expand-Graph}(graph, problem)$ ``` $\textsc{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 $\textsc{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. $$ % caption: Extract-Solution on the cake graph. At S2 the goals Have and Eaten are % covered by the Have-persistence no-op and Bake (chosen in A1); their preconditions % become the S1 goals not-Have and Eaten, covered by Eat (in A0). Its precondition % Have is the S0 goal, which holds. The extracted plan is Eat then Bake. Chosen % actions are boxed in blue. \begin{tikzpicture}[>=stealth, font=\scriptsize, lit/.style={font=\scriptsize, anchor=west}, chosen/.style={draw=acc, text=acc, thick, minimum width=14mm, minimum height=5mm, font=\scriptsize}, noopc/.style={draw=acc, thick, minimum size=3.4mm}, goalt/.style={font=\scriptsize, anchor=west, text=mx}] \definecolor{acc}{HTML}{2348F2} \definecolor{mx}{HTML}{C0392B} \foreach \x/\lab in {0/S0, 2.7/A0, 5.4/S1, 8.1/A1, 10.8/S2} { \node[font=\scriptsize\bfseries, text=black] at (\x,3.1) {\lab}; } % S0 goal: Have \node[goalt] (h0) at (-0.7,1.2) {Have(Cake)}; % A0 chosen: Eat \node[chosen] (eat0) at (2.7,1.2) {Eat(Cake)}; % S1 goals: not Have, Eaten \node[goalt] (nh1) at (4.7,2.0) {not Have(Cake)}; \node[goalt] (e1) at (4.7,0.5) {Eaten(Cake)}; % A1 chosen: Bake, and Have-persistence noop \node[chosen] (bake1) at (8.1,2.6) {Bake(Cake)}; \node[noopc] (nne1) at (8.1,0.5) {}; % S2 goals: Have, Eaten \node[goalt] (h2) at (9.6,2.6) {Have(Cake)}; \node[goalt] (e2) at (9.6,0.5) {Eaten(Cake)}; % backward links (draw as effects/precond) \draw[acc, thick] (bake1.east) -- (h2.west); \draw[acc, thick] (nne1.east) -- (e2.west); \draw[black] (nh1.east) -- (bake1.west); \draw[black] (e1.east) -- (nne1.west); \draw[acc, thick] (eat0.east) -- (nh1.west); \draw[acc, thick] (eat0.east) -- (e1.west); \draw[acc, thick] (h0.east) -- (eat0.west); \end{tikzpicture} $$ 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](/artificial-intelligence/logic-and-planning/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} \iff ActionCausesF^t \vee (F^t \wedge \neg ActionCausesNotF^t)$ tying each fluent to the actions that make it true or false, _precondition_ axioms $A^t \Rightarrow \textsc{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)^{t+1} \iff Bake(Cake)^t \;\vee\; \big(Have(Cake)^t \wedge \neg Eat(Cake)^t\big). $$ $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](/artificial-intelligence/search/constraint-satisfaction), much like the SAT encoding but with a single variable $Action^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. $$ % caption: A partially ordered solution to the spare-tire problem. The two Remove % actions are unordered relative to each other; both need only precede PutOn. Boxes % are actions; arrows are ordering constraints. \begin{tikzpicture}[>=stealth, font=\footnotesize, act/.style={draw, minimum width=30mm, minimum height=8mm, font=\scriptsize}, se/.style={draw, minimum width=15mm, minimum height=8mm, font=\scriptsize, thick}] \definecolor{acc}{HTML}{2348F2} \node[se] (start) at (0,0) {Start}; \node[act] (rt) at (4.4,1.1) {Remove(Spare, Trunk)}; \node[act] (rf) at (4.4,-1.1) {Remove(Flat, Axle)}; \node[act] (po) at (8.6,0) {PutOn(Spare, Axle)}; \node[se] (fin) at (12.2,0) {Finish}; \draw[->, black] (start) -- (rt); \draw[->, black] (start) -- (rf); \draw[->, acc, thick] (rt) -- (po); \draw[->, acc, thick] (rf) -- (po); \draw[->, black] (po) -- (fin); \end{tikzpicture} $$ 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.[^pddl98] 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. $$ % caption: A rough timeline of public milestones after AIMA's core material: PDDL % and the first planning competition (1998), the FF heuristic (2001) and the % additive/max delete-relaxation heuristics (2001), landmark heuristics (2004), and % the LAMA planner (2010). \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{mx}{HTML}{C0392B} \draw[black, thick] (0,0) -- (12,0); \foreach \x/\yr in {0/1998, 3.4/2001, 7.0/2004, 10.6/2010} { \fill[acc] (\x,0) circle (2.2pt); \node[font=\scriptsize, text=black, anchor=north] at (\x,-0.18) {\yr}; } \node[text=acc, font=\scriptsize, align=center, anchor=south] at (0,0.2) {PDDL and\\f\/irst IPC}; \node[text=acc, font=\scriptsize, align=center, anchor=south] at (3.4,0.2) {FF heuristic;\\h-add / h-max}; \node[text=acc, font=\scriptsize, align=center, anchor=south] at (7.0,0.2) {landmark\\heuristics}; \node[text=acc, font=\scriptsize, align=center, anchor=south] at (10.6,0.2) {LAMA}; \end{tikzpicture} $$ 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.[^bg01] 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.[^ff01] 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.[^landmarks04] 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.[^lama10] 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](/artificial-intelligence/search/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. [^graph]: **AIMA**, §10.3 — Planning Graphs: leveled literal/action structure, persistence actions, the three action-mutex and two literal-mutex conditions, level-cost / max-level / level-sum / set-level heuristics, and the GraphPlan expand-extract loop with its monotonic termination argument. [^pddl98]: McDermott, D., Ghallab, M., Howe, A., Knoblock, C., Ram, A., Veloso, M., Weld, D., and Wilkins, D. (1998). _PDDL — The Planning Domain Definition Language._ Technical Report, AIPS-98 Planning Competition Committee. Defined the shared input language for the first International Planning Competition. [^bg01]: Bonet, B. and Geffner, H. (2001). Planning as heuristic search. _Artificial Intelligence_, 129(1–2), 5–33. Introduced the $h_{\text{add}}$ and $h_{\max}$ delete-relaxation heuristics and the HSP planners. [^ff01]: Hoffmann, J. and Nebel, B. (2001). The FF planning system: fast plan generation through heuristic search. _Journal of Artificial Intelligence Research_, 14, 253–302. The FF planner, its relaxed-plan heuristic from a delete-relaxed planning graph, and enforced hill-climbing. [^landmarks04]: Hoffmann, J., Porteous, J., and Sebastia, L. (2004). Ordered landmarks in planning. _Journal of Artificial Intelligence Research_, 22, 215–278. Formalized landmarks and their orderings and used them as a source of heuristic guidance. [^lama10]: Richter, S. and Westphal, M. (2010). The LAMA planner: guiding cost-based anytime planning with landmarks. _Journal of Artificial Intelligence Research_, 39, 127–177. The LAMA planner, combining a landmark-count heuristic with the FF heuristic; winner of the sequential satisficing track of IPC 2008.