Classical Planning

We have already met two agents that choose their actions by looking ahead. The 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 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.¹

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.²

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).

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:

An action $a$ is applicable in a state $s$ when $s$ entails the precondition: $s\models \text{Precond}(a)$. Formally, $a\in \text{Actions}(s)\leftrightarrow s\models \text{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, $\text{Del}(a)$) and adding those that appear as positive literals (the add list, $\text{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 $\text{Result}(s,a)$ produces only ground atoms.

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.

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

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.³

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.

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 $\text{Actions}$ function, a $\text{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.

Forward (progression) search

Forward search maps a planning problem onto any of the heuristic search algorithms we already have — A*, 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.

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

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:

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

The effects the action added need not have held before, and the preconditions must have held or the action could not have fired. $\text{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.

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^{\prime },SFO)$ regresses to the description $In(C_2,p^{\prime })\wedge At(p^{\prime },SFO)\wedge \dots$, quantifying implicitly over $p^{\prime }$ — 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

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^{\prime }=(g-\text{Add}(a))\cup \text{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$.

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,

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 $\text{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 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.

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.

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.⁴

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, 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.