---
title: Classical Planning
module: Logic and Planning
moduleNumber: 3
lessonNumber: 7
order: 307
summary: >
  Classical planning represents a problem in a factored language, PDDL: states are
  sets of ground fluents, and actions are lifted schemas with a precondition and an
  effect. That structure turns planning into search — forward through states or
  backward through goals — and lets a program read heuristics straight off the
  schemas by relaxing the problem. This first part develops the representation, the
  two search directions, and the domain-independent heuristics that come from
  ignoring preconditions or delete lists.
topics: [Logic]
sources:
  - book: AIMA
    ref: "Ch. 10 — Classical Planning; §10.1 Definition of Classical Planning"
  - book: AIMA
    ref: "§10.2 Algorithms for Planning as State-Space Search"
---


We have already met two agents that choose their actions by looking ahead. The
[search](/artificial-intelligence/search/uninformed-search) agent finds a sequence
of actions leading to a goal, but it works over _atomic_ states — opaque labels
with no internal parts — so it needs a hand-built heuristic to move well. The
logical agent of [first-order logic](/artificial-intelligence/logic-and-planning/first-order-logic)
reasons about the structure of the world, but inference over ground sentences gets
swamped once there are many objects and time steps. Classical planning keeps the
best of each: a representation structured enough that a program can derive its own
heuristics, yet restricted enough that search stays tractable.[^intro]

The difference is the **factored representation**. Instead of naming each state, we
describe it by a collection of variables — which cargo is where, which plane is at
which airport — and describe each action by the small set of variables it changes.
A single action schema then stands for thousands of ground actions, and a program
can inspect that schema and reason about it. This lesson covers fully
observable, deterministic, static environments with a single agent; uncertainty and
multiple agents come later.

## The PDDL representation

Planning problems are written in **PDDL**, the Planning Domain Definition
Language. PDDL specifies the four things a search needs: the initial state, the
actions available in a state, the result of applying an action, and the goal
test.[^pddl]

A **state** is a conjunction of **fluents** that are ground, functionless atoms —
for example, $At(P_1, SFO) \wedge At(P_2, JFK)$. Three conventions keep states
finite and unambiguous. The _closed-world assumption_ says any fluent not
mentioned is false. The _unique-names assumption_ says distinct constant names
denote distinct objects. And a state may be read two ways: as a conjunction to be
manipulated by logical inference, or as a _set_ of fluents to be manipulated by set
operations — the set semantics is often easier. Certain fluents are barred: $At(x,
y)$ is not allowed (non-ground), nor is $\neg Poor$ (a negation), nor $At(Father(Fred),
SFO)$ (a function symbol).

> **Definition (Fluent).** A ground, functionless atom whose truth can change over
> time, such as $At(C_1, SFO)$. A state is the set of fluents that hold; under the
> closed-world assumption, every fluent outside the set is false.

**Actions** are described by **action schemas**. A schema is a _lifted_
representation — it lifts reasoning from propositional logic up to a restricted
fragment of first-order logic — consisting of an action name, the variables it
uses, a **precondition**, and an **effect**:

$$
% caption: An action schema for flying a plane. The precondition names the states
% in which the action applies; the effect names exactly what changes, leaving
% everything else untouched. Variables $p$, $from$, $to$ are implicitly universally
% quantified.
\begin{tikzpicture}[>=stealth, font=\small,
  row/.style={font=\footnotesize},
  tag/.style={font=\scriptsize\bfseries, text=black, anchor=east}]
  \definecolor{acc}{HTML}{2348F2}
  \node[draw=acc, text=acc, minimum width=88mm, minimum height=27mm] (box) at (0,0) {};
  \node[row, anchor=west, text=acc] at (-4.2,0.85) {\texttt{Action( Fly(p, from, to) )}};
  \node[tag] at (-2.65,0.05) {PRECOND:};
  \node[row, anchor=west] at (-2.5,0.05) {\texttt{At(p, from) and Plane(p)}};
  \node[row, anchor=west] at (-2.5,-0.45) {\texttt{and Airport(from) and Airport(to)}};
  \node[tag] at (-2.65,-1.0) {EFFECT:};
  \node[row, anchor=west] at (-2.5,-1.0) {\texttt{not At(p, from) and At(p, to)}};
\end{tikzpicture}
$$

An action $a$ is **applicable** in a state $s$ when $s$ entails the precondition:
$s \models \textsc{Precond}(a)$. Formally, $a \in \textsc{Actions}(s) \iff s
\models \textsc{Precond}(a)$, where the variables in $a$ are treated as universally
quantified, free to be instantiated to any objects. A schema with $v$ variables in
a domain with $k$ object names has $O(v^k)$ possible ground instantiations, which is
why we keep it lifted rather than enumerating them.

The **result** of executing an applicable action $a$ in $s$ is defined by removing
the fluents that appear as negative literals in the effect (the **delete list**,
$\textsc{Del}(a)$) and adding those that appear as positive literals (the **add
list**, $\textsc{Add}(a)$):

$$
\textsc{Result}(s, a) = (s - \textsc{Del}(a)) \cup \textsc{Add}(a).
$$

This is the classical answer to the frame problem. The schema mentions only what
changes; everything the effect does not touch is assumed to stay the same, so we
never have to write down the vast list of facts that an action leaves alone. A
requirement of every schema is that any variable in the effect also appears in the
precondition, so once the precondition is matched against a ground state, all
variables are bound and $\textsc{Result}(s, a)$ produces only ground atoms.

> **Definition (Action schema).** A lifted description
> $\textsc{Action}(\text{name}(\bar{x}), \textsc{Precond}, \textsc{Effect})$ where
> the precondition and effect are conjunctions of literals over the variables
> $\bar{x}$. It implicitly defines $\textsc{Actions}(s)$ (which ground actions
> apply) and $\textsc{Result}(s, a)$ (their effect). Applying it splits the effect
> into an add list and a delete list.

A set of schemas defines a planning _domain_; adding an **initial state** (a
conjunction of ground atoms) and a **goal** (a conjunction of literals, possibly
with variables read existentially) defines a specific _problem_. The problem is
solved by any sequence of actions ending in a state that entails the goal.

### Example: air cargo transport

The air cargo domain moves cargo between airports by loading it onto planes,
flying, and unloading. Two predicates carry the state: $In(c, p)$ (cargo $c$ is
inside plane $p$) and $At(x, a)$ (object $x$, plane or cargo, is at airport $a$).
Three schemas act on them.

$$
% caption: The air-cargo domain. Loading moves cargo from an airport into a plane;
% flying moves a plane; unloading moves cargo back out at the destination. A piece
% of cargo is "At" nowhere while it is "In" a plane.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  sch/.style={draw, align=left, minimum width=44mm, minimum height=20mm, inner sep=6pt, font=\scriptsize},
  hd/.style={font=\scriptsize\bfseries, text=acc}]
  \definecolor{acc}{HTML}{2348F2}
  \node[sch] (load) at (0,0)
    {\textbf{\texttt{Load(c, p, a)}}\\[2pt]
     pre: \texttt{At(c,a) and At(p,a)}\\
     \phantom{pre: }\texttt{and Cargo(c) and Plane(p)}\\
     e\/f\/f: \texttt{not At(c,a) and In(c,p)}};
  \node[sch] (fly) at (5.4,0)
    {\textbf{\texttt{Fly(p, from, to)}}\\[2pt]
     pre: \texttt{At(p,from) and Plane(p)}\\
     \phantom{pre: }\texttt{and Airport(from), Airport(to)}\\
     e\/f\/f: \texttt{not At(p,from) and At(p,to)}};
  \node[sch] (unl) at (10.8,0)
    {\textbf{\texttt{Unload(c, p, a)}}\\[2pt]
     pre: \texttt{In(c,p) and At(p,a)}\\
     \phantom{pre: }\texttt{and Cargo(c) and Plane(p)}\\
     e\/f\/f: \texttt{At(c,a) and not In(c,p)}};
\end{tikzpicture}
$$

Some care is needed so the $At$ predicates stay correct: when a plane flies, the
cargo inside it goes along, but basic PDDL has no universal quantifier to say so.
Instead, cargo ceases to be $At$ anywhere while it is $In$ a plane, and
becomes $At$ the new airport only when unloaded — so $At$ means "available for use
at a given location." For the problem with cargo $C_1$ at SFO bound for JFK and
$C_2$ at JFK bound for SFO, one solution is

$$
[\,Load(C_1, P_1, SFO),\; Fly(P_1, SFO, JFK),\; Unload(C_1, P_1, JFK),\;
Load(C_2, P_2, JFK),\; Fly(P_2, JFK, SFO),\; Unload(C_2, P_2, SFO)\,].
$$

### Example: the blocks world

The blocks world is one of the oldest planning domains: cube-shaped blocks on a
table, stackable one atop another, moved by a robot arm that lifts one block at a
time. We write $On(b, x)$ for block $b$ resting on $x$ (a block or the table). Since
PDDL has no quantifier to say "nothing is on $b$," we introduce a predicate
$Clear(x)$, true when $x$ has a clear space to hold a block. The $Move$ schema
slides a block $b$ from $x$ to $y$ when both $b$ and $y$ are clear; a companion
$MoveToTable$ handles moving a block onto the table, so that $Clear$ is maintained
correctly when the table is involved.[^blocks]

The delete list carries the bookkeeping here. $Move(b, x, y)$ adds $On(b, y)$
and $Clear(x)$, and deletes $On(b, x)$ and $Clear(y)$ — the block leaves its old
support (which becomes clear) and covers its new one (which stops being clear). The
figure below shows the state transition on a three-block tower.

$$
% caption: A state transition in the blocks world. Applying $Move(C, A, \text{Table})$
% deletes $On(C, A)$ and $Clear(\text{Table})$ conceptually and adds $On(C,
% \text{Table})$ and $Clear(A)$, turning the left state into the right one.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  blk/.style={draw, minimum size=9mm, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  % --- left state: C on A, A on table, B on table ---
  \draw[black, line width=1.4pt] (-0.4,0) -- (2.4,0);
  \node[blk] (A) at (1.4,0.5) {A};
  \node[blk] (C) at (1.4,1.4) {C};
  \node[blk] (B) at (0.2,0.5) {B};
  \node[font=\scriptsize, text=black] at (1.0,-0.4) {start state};
  % --- arrow ---
  \draw[->, acc, very thick] (3.2,0.7) -- (4.7,0.7);
  \node[font=\scriptsize, text=acc, anchor=south] at (3.95,0.78) {Move(C, A, Table)};
  % --- right state: C on table, A on table, B on table ---
  \begin{scope}[xshift=5.4cm]
    \draw[black, line width=1.4pt] (-0.4,0) -- (2.9,0);
    \node[blk] (A2) at (1.4,0.5) {A};
    \node[blk] (C2) at (2.6,0.5) {C};
    \node[blk] (B2) at (0.2,0.5) {B};
    \node[font=\scriptsize, text=black] at (1.2,-0.4) {result state};
  \end{scope}
\end{tikzpicture}
$$

### The complexity of planning

Two decision problems fix the difficulty. **PlanSAT** asks whether any plan solves
a problem; **Bounded PlanSAT** asks whether one of length $k$ or less exists (useful
for finding _optimal_ plans). Both are decidable for classical planning because the
number of states is finite — but add function symbols and the state space becomes
infinite, at which point PlanSAT is only semidecidable. Both problems sit in
PSPACE, harder than NP. Even severe restrictions barely help: disallowing negative
effects keeps both NP-hard, though also disallowing negative preconditions drops
PlanSAT to P.

These worst-case results are less discouraging than they sound. Agents are rarely
asked to plan for arbitrary instances; they face specific domains — blocks world, air
cargo — that are often far easier than the theoretical worst case. For many such
domains Bounded PlanSAT is NP-complete while PlanSAT is in P, so finding _some_ plan
is easy and finding an _optimal_ one is the hard part. Good heuristics matter most
in that gap, and this is the advantage of the classical formalism: its structured
representation has enabled very accurate domain-independent heuristics, where
logic-based successor-state systems have had much less success.

## Planning as state-space search

A planning problem _is_ a search problem: an initial state, an
$\textsc{Actions}$ function, a $\textsc{Result}$ function, and a goal test. The
declarative schema representation additionally lets us search from
either end — **forward** from the initial state toward a goal, or **backward** from
the goal toward the initial state.

$$
% caption: Two directions of search. Forward (progression) search applies
% applicable actions from the initial state toward the goal; backward (regression)
% search applies actions in reverse from the goal toward the initial state, working
% over sets of relevant states.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={draw, minimum width=22mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  % --- forward ---
  \node[st] (f0) at (0,0) {At(P1,A)\\At(P2,A)};
  \node[st] (f1) at (4.4,0.9) {At(P1,B)\\At(P2,A)};
  \node[st] (f2) at (4.4,-0.9) {At(P1,A)\\At(P2,B)};
  \draw[->, acc, thick] (f0) -- (f1) node[midway, above, font=\scriptsize, sloped] {Fly(P1,A,B)};
  \draw[->, acc, thick] (f0) -- (f2) node[midway, below, font=\scriptsize, sloped] {Fly(P2,A,B)};
  \node[font=\scriptsize\bfseries, text=black, anchor=west] at (-1.9,1.5) {(a) f\/orward};
  % --- backward ---
  \begin{scope}[yshift=-3.4cm]
    \node[st] (b0) at (4.4,0) {At(P1,B)\\At(P2,B)};
    \node[st] (b1) at (0,0.9) {At(P1,A)\\At(P2,B)};
    \node[st] (b2) at (0,-0.9) {At(P1,B)\\At(P2,A)};
    \draw[->, acc, thick] (b0) -- (b1) node[midway, above, font=\scriptsize, sloped] {Fly(P1,A,B)};
    \draw[->, acc, thick] (b0) -- (b2) node[midway, below, font=\scriptsize, sloped] {Fly(P2,A,B)};
    \node[font=\scriptsize\bfseries, text=black, anchor=west] at (-1.9,1.5) {(b) backward};
  \end{scope}
\end{tikzpicture}
$$

### Forward (progression) search

Forward search maps a planning problem onto any of the heuristic search algorithms
we already have — [A\*](/artificial-intelligence/search/informed-search), for
example — provided we record the actions used to reach each state. It was long
assumed impractical, for two reasons.

First, forward search explores _irrelevant_ actions. To buy a copy of a book from
an online seller, the domain might have a schema $Buy(isbn)$ with effect
$Own(isbn)$; with ten-digit ISBNs that is ten billion ground actions, and an
uninformed forward search would start enumerating all of them. Second, planning
problems have huge state spaces. In an air cargo problem with 10 airports, each
holding 5 planes and 20 pieces of cargo (50 planes and 200 packages in all), the
average branching factor runs to roughly 2000 actions per state: every plane can fly
to any of 9 other airports, and every one of 200 packages can be loaded or unloaded. The search graph down to the obvious
solution has on the order of $2000^{41}$ nodes.

> **Definition (Branching factor).** The average number of actions applicable in a
> state. In planning it is large because the factored representation multiplies out:
> each object can participate in many actions independently, so the number of ground
> actions grows as a product over objects.

Even this modest instance is hopeless without an accurate heuristic. Forward search
is practical because strong domain-independent heuristics can be derived
automatically — the subject of the next section.

#### A forward-search trace

For example, run forward search by hand on a two-plane air-cargo
instance small enough to follow completely. The objects are two planes $P_1, P_2$,
two cargoes $C_1, C_2$, and two airports $SFO, JFK$. The initial state is

$$
s_0 = \{\,At(C_1, SFO),\; At(C_2, JFK),\; At(P_1, SFO),\; At(P_2, JFK)\,\}
$$

together with the static facts $Cargo(C_1), Cargo(C_2), Plane(P_1), Plane(P_2),
Airport(SFO), Airport(JFK)$, which no action ever changes. The goal is $At(C_1, JFK)
\wedge At(C_2, SFO)$: swap the two cargoes. At each step we apply the three schemas
from the air-cargo domain and, guided by a heuristic that prefers actions moving a
cargo toward its destination, commit to one action. The static facts are omitted from
each state below since they never change.

The trace runs six actions deep. Starting from $s_0$, $Load(C_1, P_1, SFO)$ is
applicable because $At(C_1, SFO)$ and $At(P_1, SFO)$ both hold; applying it deletes
$At(C_1, SFO)$ and adds $In(C_1, P_1)$. The chosen sequence and the resulting states:

$$
% caption: A complete forward-search trace on the two-plane air-cargo problem. Each
% row is a state (only the fluents that changed from the row above are highlighted in
% blue); the label on the arrow is the action applied to reach the next row. Six
% actions carry both cargoes to their destinations.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  stt/.style={draw, align=left, minimum width=64mm, inner sep=5pt, font=\scriptsize},
  arr/.style={font=\scriptsize, text=acc, anchor=west}]
  \definecolor{acc}{HTML}{2348F2}
  % states down the left column, actions to the right of each arrow
  \node[stt] (s0) at (0,0)
    {\textbf{s0}\\ At(C1,SFO), At(C2,JFK),\\ At(P1,SFO), At(P2,JFK)};
  \node[stt] (s1) at (0,-2.1)
    {\textbf{s1}\\ \textcolor{acc}{In(C1,P1)}, At(C2,JFK),\\ At(P1,SFO), At(P2,JFK)};
  \node[stt] (s2) at (0,-4.2)
    {\textbf{s2}\\ In(C1,P1), \textcolor{acc}{In(C2,P2)},\\ At(P1,SFO), At(P2,JFK)};
  \node[stt] (s3) at (0,-6.3)
    {\textbf{s3}\\ In(C1,P1), In(C2,P2),\\ \textcolor{acc}{At(P1,JFK)}, At(P2,JFK)};
  \node[stt] (s4) at (0,-8.4)
    {\textbf{s4}\\ In(C1,P1), In(C2,P2),\\ At(P1,JFK), \textcolor{acc}{At(P2,SFO)}};
  \node[stt] (s5) at (0,-10.5)
    {\textbf{s5}\\ \textcolor{acc}{At(C1,JFK)}, In(C2,P2),\\ At(P1,JFK), At(P2,SFO)};
  \node[stt] (s6) at (0,-12.6)
    {\textbf{s6 = goal}\\ At(C1,JFK), \textcolor{acc}{At(C2,SFO)},\\ At(P1,JFK), At(P2,SFO)};
  \foreach \a/\b in {s0/s1, s1/s2, s2/s3, s3/s4, s4/s5, s5/s6}
    \draw[->, acc, thick] (\a) -- (\b);
  \node[arr] at (2.6,-1.05) {Load(C1, P1, SFO)};
  \node[arr] at (2.6,-3.15) {Load(C2, P2, JFK)};
  \node[arr] at (2.6,-5.25) {Fly(P1, SFO, JFK)};
  \node[arr] at (2.6,-7.35) {Fly(P2, JFK, SFO)};
  \node[arr] at (2.6,-9.45) {Unload(C1, P1, JFK)};
  \node[arr] at (2.6,-11.55) {Unload(C2, P2, SFO)};
\end{tikzpicture}
$$

The trace shows two details. When $Fly(P_1, SFO, JFK)$ fires between
$s_2$ and $s_3$, the cargo $C_1$ inside $P_1$ has no $At$ fluent at all — it is
recorded only by $In(C_1, P_1)$ — so nothing needs to be said about carrying it along;
this is the $At$/$In$ encoding from the domain definition. And the goal is
tested by entailment, not equality: $s_6$ contains four fluents but the goal names only
two, and $s_6 \models At(C_1, JFK) \wedge At(C_2, SFO)$ holds regardless of where the
planes ended up. A heuristic that miscounts here — say, one that ignored the two
$Load$ steps as irrelevant — would still find this plan, because forward search
commits to whole actions and checks applicability at every step.

### Backward (regression) relevant-states search

Backward search — also called **relevant-states** search — starts at the goal and
applies actions in reverse until it reaches the initial state. As in belief-state
search, each node is a _set_ of states, described by a conjunction of literals: the
goal $\neg Poor \wedge Famous$ describes every state in which $Poor$ is false and
$Famous$ is true, with all other fluents free. With $n$ ground fluents there are
$2^n$ states but $3^n$ descriptions, since each fluent can be positive, negative, or
unmentioned.

Backward search only works when we can **regress** from a state description to its
predecessor, and PDDL was designed to make that easy. Given a ground goal
description $g$ and a ground action $a$, the regression of $g$ over $a$ is

$$
g' = (g - \textsc{Add}(a)) \cup \textsc{Precond}(a).
$$

The effects the action added need not have held before, and the preconditions must
have held or the action could not have fired. $\textsc{Del}(a)$ does not appear:
we know those fluents are false _after_ the action, but we can say nothing about
whether they held before, so we leave them out.

The actions worth regressing over are the **relevant** ones — those that could be
the _last_ step of a plan reaching the current goal.

> **Definition (Relevance).** An action $a$ is relevant to a goal $g$ if at least
> one of its effects unifies with a literal in $g$ (it contributes to the goal) and
> none of its effects negates a literal in $g$ (it does not undo the goal). An
> action that achieves $A \wedge B$ but deletes $C$ is not relevant to $A \wedge B
> \wedge C$: it could never be the _final_ step.

To get the full benefit of backward search we regress over _partially_
instantiated actions, not just ground ones. For the goal $At(C_2, SFO)$, the schema
$Unload(C_2, p', SFO)$ regresses to the description $In(C_2, p') \wedge At(p', SFO)
\wedge \dots$, quantifying implicitly over $p'$ — any plane will do, and we never
commit to which. This is the advantage of the lifted representation: one description
covers any choice of plane. Backward search keeps the branching factor
lower than forward search for most domains, but because it reasons over state _sets_
rather than individual states, good heuristics are harder to come by. That is the
main reason most current systems favor forward search.

#### A backward-search trace

Running regression by hand on the same instance the forward trace used shows the
mechanics. Take the two-plane air-cargo problem again — planes $P_1, P_2$,
cargoes $C_1, C_2$, airports $SFO, JFK$ — with the goal

$$
g_0 = At(C_1, JFK) \wedge At(C_2, SFO)
$$

and work _backward_, one action at a time, until a description reaches something the
initial state already entails. Each node is a conjunction of literals standing for a
set of states, and at each step we pick a **relevant** action — one whose effect
supplies a goal literal without deleting another — and regress the goal through it
using $g' = (g - \textsc{Add}(a)) \cup \textsc{Precond}(a)$. We regress over
_partially instantiated_ schemas, leaving the plane variable open where the goal does
not force it.

Start at $g_0$. Only two schema instances can produce $At(C_1, JFK)$ or $At(C_2,
SFO)$ as a _final_ step, and neither deletes the other's goal, so both are relevant.
Regress over $Unload(C_2, p, SFO)$ first: it adds $At(C_2, SFO)$, so that literal
drops out of the goal and the unload's preconditions come in, quantified over the
open plane $p$.

$$
% caption: A complete backward-regression trace on the two-plane air-cargo problem,
% the same instance the forward trace solved. Each row is a goal description (a set
% of states); the arrow label is the action regressed over, read bottom-to-top as the
% eventual plan. Literals introduced by a regression step are highlighted in blue.
% Open plane variables (p, q) are never committed to a specific plane.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  stt/.style={draw, align=left, minimum width=74mm, inner sep=5pt, font=\scriptsize},
  arr/.style={font=\scriptsize, text=acc, anchor=west}]
  \definecolor{acc}{HTML}{2348F2}
  \node[stt] (g0) at (0,0)
    {\textbf{g0 = goal}\\ At(C1,JFK), At(C2,SFO)};
  \node[stt] (g1) at (0,-2.0)
    {\textbf{g1}\\ At(C1,JFK), \textcolor{acc}{In(C2,p), At(p,SFO)}};
  \node[stt] (g2) at (0,-4.0)
    {\textbf{g2}\\ \textcolor{acc}{In(C1,q), At(q,JFK)}, In(C2,p), At(p,SFO)};
  \node[stt] (g3) at (0,-6.2)
    {\textbf{g3}\\ In(C1,q), At(q,JFK), In(C2,p), \textcolor{acc}{At(p,JFK)}};
  \node[stt] (g4) at (0,-8.6)
    {\textbf{g4}\\ In(C1,q), \textcolor{acc}{At(q,SFO)}, In(C2,p), At(p,JFK)};
  \node[stt] (g5) at (0,-11.0)
    {\textbf{g5}\\ \textcolor{acc}{At(C1,SFO)}, At(q,SFO), In(C2,p), At(p,JFK)};
  \node[stt] (g6) at (0,-13.6)
    {\textbf{g6}\\ At(C1,SFO), At(q,SFO),\\ \textcolor{acc}{At(C2,JFK)}, At(p,JFK)};
  \foreach \a/\b in {g0/g1, g1/g2, g2/g3, g3/g4, g4/g5, g5/g6}
    \draw[->, acc, thick] (\a) -- (\b);
  \node[arr] at (2.9,-1.0) {Unload(C2, p, SFO)};
  \node[arr] at (2.9,-3.0) {Unload(C1, q, JFK)};
  \node[arr] at (2.9,-5.1) {Fly(p, JFK, SFO)};
  \node[arr] at (2.9,-7.4) {Fly(q, SFO, JFK)};
  \node[arr] at (2.9,-9.8) {Load(C1, q, SFO)};
  \node[arr] at (2.9,-12.3) {Load(C2, p, JFK)};
\end{tikzpicture}
$$

Read the trace from $g_0$ down and each step regresses over the action named on the
arrow:

- **$g_0 \to g_1$**, over $Unload(C_2, p, SFO)$. The action adds $At(C_2, SFO)$
  (removed from the goal) and requires $In(C_2, p) \wedge At(p, SFO)$ (added). The
  static conditions $Cargo(C_2), Plane(p)$ come in too but are omitted here since
  $s_0$ supplies them for any plane. The plane $p$ stays open — the partial
  instantiation described above.
- **$g_1 \to g_2$**, over $Unload(C_1, q, SFO)$'s sibling $Unload(C_1, q, JFK)$. It
  supplies $At(C_1, JFK)$ and demands $In(C_1, q) \wedge At(q, JFK)$, with $q$ a
  second open plane.
- **$g_2 \to g_3$**, over $Fly(p, JFK, SFO)$. To get $At(p, SFO)$ we regress the fly:
  its effect $At(p, SFO)$ leaves, and its precondition $At(p, JFK)$ enters. $In(C_2,
  p)$ is untouched — flying does not disturb loaded cargo — so it rides along.
- **$g_3 \to g_4$**, over $Fly(q, SFO, JFK)$, symmetrically turning $At(q, JFK)$ into
  the requirement $At(q, SFO)$.
- **$g_4 \to g_5$**, over $Load(C_1, q, SFO)$. Loading adds $In(C_1, q)$ (leaves) and
  needs $At(C_1, SFO) \wedge At(q, SFO)$; the cargo's airport fact $At(C_1, SFO)$
  enters the description.
- **$g_5 \to g_6$**, over $Load(C_2, p, JFK)$, the last regression: $In(C_2, p)$
  leaves and $At(C_2, JFK) \wedge At(p, JFK)$ enters.

Now compare $g_6$ against the initial state $s_0 = \{At(C_1, SFO), At(C_2, JFK),
At(P_1, SFO), At(P_2, JFK)\}$. The cargo literals $At(C_1, SFO)$ and $At(C_2, JFK)$
match directly. The two open planes are bound by $At(q, SFO)$ and $At(p, JFK)$: taking
$q = P_1$ and $p = P_2$ makes $g_6$ entailed by $s_0$. Search halts, and reading the
arrow labels _bottom to top_ recovers a plan,

$$
[\,Load(C_2, P_2, JFK),\; Load(C_1, P_1, SFO),\; Fly(P_1, SFO, JFK),\;
Fly(P_2, JFK, SFO),\; Unload(C_1, P_1, JFK),\; Unload(C_2, P_2, SFO)\,],
$$

the same six-action solution the forward trace found, differing only in the order of
the two independent $Load$ steps. The trace shows two things. The plane
variables $p$ and $q$ stay uncommitted for the whole regression and are pinned only at
the last matching step, so a single backward path stands in for _all_ ways of
assigning the two planes — the branching that forward search would have paid for at
$s_0$. And $\textsc{Del}(a)$ never enters a regressed description: when $Fly(p, JFK,
SFO)$ is regressed, its delete effect $\neg At(p, JFK)$ is simply dropped, because the
precondition already asserts that $At(p, JFK)$ holds in the predecessor.
The cost is that every node describes a _set_ of states, which is why accurate
heuristics — the subject of the next section — are harder to attach here than in the
forward direction.

## Domain-independent heuristics from relaxed problems

Neither search direction is efficient without a good heuristic $h(s)$ estimating the
distance from $s$ to the goal. From informed search we know that an **admissible**
heuristic — one that never overestimates — is obtained by defining a **relaxed
problem** that is easier to solve, then using its exact solution cost as the
heuristic. The [informed search](/artificial-intelligence/search/informed-search)
lesson invented such relaxations by hand, one clever insight per domain. Planning's
factored representation changes that: a program can relax the _schemas_ mechanically,
so the heuristic comes for free.

> **Definition (Relaxed problem).** An easier problem obtained by dropping
> constraints from the original. Because the relaxed problem admits every solution
> of the original (plus more), its optimal solution cost is a lower bound on the
> original's — hence an admissible heuristic. In planning the constraints live in
> the action schemas, so a program can relax them without human insight.

Think of the search space as a graph whose nodes are states and whose edges are
actions. There are two ways to make it easier: add edges (so paths get shorter), or
merge nodes into an abstraction with fewer states.

$$
% caption: Two families of relaxation. Adding edges keeps every state but makes
% goals reachable in fewer steps (ignore-preconditions, ignore-delete-lists);
% state abstraction merges many ground states into one, shrinking the graph.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=40mm, minimum height=13mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, draw=acc, text=acc, thick] (root) at (0,0) {relax the planning problem};
  \node[box] (edge) at (-3.4,-2.3) {add edges\\(easier to f\/ind a path)};
  \node[box] (abs)  at (3.4,-2.3)  {merge states\\(fewer states to search)};
  \node[font=\scriptsize, text=black, align=center] at (-3.4,-3.7) {ignore preconditions,\\ignore delete lists};
  \node[font=\scriptsize, text=black, align=center] at (3.4,-3.7) {state abstraction,\\subgoal decomposition};
  \draw[->, acc, thick] (root) -- (edge);
  \draw[->, acc, thick] (root) -- (abs);
\end{tikzpicture}
$$

**Ignore preconditions.** The **ignore-preconditions heuristic** drops every
precondition from every action, so each action is applicable in every state and any
unsatisfied goal fluent can be achieved in one step (if some action achieves it at
all). This _almost_ implies the heuristic is the number of unsatisfied goals, but
not quite: one action may achieve several goals, and one action may undo another.
Accounting for the first and ignoring the second, we relax further — remove all
effects except the goal literals — and count the minimum number of actions whose
effects together cover the goal. That is the **set-cover problem**, which is
NP-hard; a greedy approximation runs in polynomial time and comes within a factor of
$\log n$ of the true minimum, at the cost of admissibility.

It is also possible to ignore only _selected_ preconditions. For the sliding-block
puzzle encoded with a $Slide(t, s_1, s_2)$ schema, dropping the $Blank(s_2) \wedge
Adjacent(s_1, s_2)$ preconditions gives the misplaced-tiles heuristic; dropping only
$Blank(s_2)$ gives Manhattan distance. Both classic heuristics fall out of the same
schema by deleting preconditions — the ease of manipulating schemas is the
advantage of the factored representation.

**Ignore delete lists.** Assume goals and preconditions contain only positive
literals. The **ignore-delete-lists** heuristic removes every negative literal from
every effect, so no action ever undoes another's progress. The relaxed problem makes
_monotonic_ progress toward the goal: once a fluent becomes true it stays true.
Finding the optimal relaxed solution is still NP-hard, but an approximate one is
found in polynomial time by hill-climbing, because the relaxed state space has no
local minima and no dead ends — a wide, downhill path to every goal.[^ignoredel]

$$
% caption: The ignore-delete-lists relaxation. Each dot is a state and its height
% is the heuristic value; states on the floor are goals. Removing delete lists
% erases local minima, so hill-climbing walks straight downhill to a solution.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % ground plane
  \draw[black, fill=black!5] (-0.4,0) -- (7.4,0) -- (8.6,1.0) -- (0.8,1.0) -- cycle;
  \node[font=\scriptsize, text=black, anchor=west] at (6.3,0.35) {goals (f\/loor)};
  % a monotone-descending set of states (no local minima)
  \coordinate (a) at (1.2,3.4);
  \coordinate (b) at (2.3,2.5);
  \coordinate (c) at (3.4,1.8);
  \coordinate (d) at (4.5,1.15);
  \coordinate (e) at (5.6,0.75);
  \foreach \p/\lift in {a/3.4,b/2.5,c/1.8,d/1.15,e/0.75} {
    \fill[acc] (\p) circle (2.2pt);
  }
  \draw[acc, thick] (a) -- (b) -- (c) -- (d) -- (e);
  % stems to floor to show "height = heuristic"
  \draw[black, dashed] (1.2,3.4) -- (1.2,1.06);
  \draw[black, dashed] (2.3,2.5) -- (2.3,0.98);
  \draw[black, dashed] (5.6,0.75) -- (5.6,0.66);
  \node[acc, anchor=south, font=\scriptsize] at (1.2,3.5) {start};
  \node[font=\scriptsize, text=black, anchor=west] at (2.6,2.9) {height = h(state)};
\end{tikzpicture}
$$

A live system built on this idea is **FF** (FastForward): a forward searcher that
computes the ignore-delete-lists heuristic with the help of a planning graph, then
runs hill-climbing modified to keep the plan, falling back to iterated deepening
when it hits a plateau.

**State abstraction.** Relaxing the actions does nothing to shrink the number of
states, and many problems have $10^{100}$ of them. A **state abstraction** is a
many-to-one map from ground states to abstract ones. The simplest kind ignores some
fluents. In an air cargo problem where all packages happen to share a destination
and sit at 5 airports, dropping every $At$ fluent except those for one plane and one
package at each airport cuts $10^{155}$ states to about $10^{17}$; the abstract
solution is shorter (hence admissible) and extends back to the original by inserting
the missing $Load$ and $Unload$ actions.

**Decomposition.** A conjunctive goal $G$ can be split into subgoals $G_1, \dots,
G_n$ solved independently, their costs combined. Taking the _maximum_ subgoal cost
is always admissible. Taking the _sum_ — the **subgoal independence** assumption — is
more accurate but admissible only when the subplans do not interact: it is optimistic
when one subplan deletes another's goal, pessimistic when two subgoals share an
action. Which combination is safe depends on how the subproblems interact, and
planning graphs, next, help estimate that.


## Where this continues

The relaxations above — ignore preconditions, ignore delete lists, decompose into
subgoals — each give a heuristic, but each can be badly inaccurate, and none of them
can estimate how subplans interact. A single data structure does
better: a polynomial-size approximation to the problem that both sharpens the
heuristic and can be searched directly for a plan.

This continues in
[Planning Heuristics and GraphPlan](/artificial-intelligence/logic-and-planning/planning-graphs-and-graphplan),
which builds the planning graph, reads an admissible heuristic off its level costs
and mutex structure, extracts a plan with GraphPlan, and closes with SATPlan,
partial-order planning, and the central trade-off of classical planning.

[^intro]: **AIMA**, Ch. 10 — Classical Planning, introduction and §10.1: planning as a middle ground between atomic-state search and ground first-order inference, on fully observable, deterministic, static, single-agent problems.
[^pddl]: **AIMA**, §10.1 — Definition of Classical Planning: the PDDL representation, states as conjunctions of ground fluents under closed-world and unique-names assumptions, action schemas with precondition and effect, and the $\textsc{Result}(s,a) = (s - \textsc{Del}(a)) \cup \textsc{Add}(a)$ semantics.
[^blocks]: **AIMA**, §10.1.3 — Example: The Blocks World: the $On$/$Clear$ encoding, the $Move$ and $MoveToTable$ schemas, and why a $Clear$ predicate substitutes for the missing universal quantifier.
[^ignoredel]: **AIMA**, §10.2.3 — Heuristics for Planning: ignore-preconditions (reducing to set cover), ignore-delete-lists (monotonic progress, hill-climbable), selected-precondition relaxations for the sliding-block puzzle, state abstraction, and subgoal decomposition.