Classical Planning: Schemas, Relaxations and Graphs

Search will solve a planning problem, given a heuristic. The interesting question is where the heuristic comes from, and the answer turns out to be a claim about representation rather than about algorithms.

A. What a factored state buys

A problem-solving agent treats a state as an atom. It can test the state for goalhood and nothing else, so every heuristic has to be supplied from outside. A logical agent can look inside a state, but reasons with ground sentences and drowns in them: in the wumpus world, moving forward needed a separate sentence for each of four orientations, $T$ time steps and $n^2$ locations.

Planning takes the middle path. A state is a collection of variables - a conjunction of fluents that are ground, positive and function-free:

$$\mathrm{At}(\mathit{Flat}, \mathit{Axle}) \wedge \mathrm{At}(\mathit{Spare}, \mathit{Trunk}) .$$

Under the closed-world assumption anything unmentioned is false, so negation never has to be written down. The state is then readable two ways at once, as a logical sentence or as a set, and almost every algorithm takes the second.

Actions are schemas, describing only what changes:

$$\begin{array}{l} \mathrm{Action}(\mathrm{Fly}(p, \mathit{from}, \mathit{to}), \\ \quad \textsc{Precond}: \mathrm{At}(p, \mathit{from}) \wedge \mathrm{Plane}(p) \wedge \mathrm{Airport}(\mathit{from}) \wedge \mathrm{Airport}(\mathit{to}) \\ \quad \textsc{Effect}: \neg\mathrm{At}(p, \mathit{from}) \wedge \mathrm{At}(p, \mathit{to})) \end{array}$$

The positive literals are the add list, the negated ones the delete list, and applying an action is one set expression: $\mathrm{Result}(s, a) = (s \setminus \mathrm{Del}(a)) \cup \mathrm{Add}(a)$. The frame problem is not solved so much as declined: attention is restricted to domains where most actions leave most things alone, and persistence becomes the default.

B. The cost of grounding

A schema is compact; its instances are not. With two cargos, two planes and two airports, three air-cargo schemas expand to twenty ground actions, and the flight schema alone with ten planes and five airports gives $10 \times 5 \times 4 = 200$.

The guard on the last comprehension is not tidiness. Without it the schema produces $\mathrm{Fly}(P_1, JFK, JFK)$, whose effect is $\neg\mathrm{At}(P_1, JFK) \wedge \mathrm{At}(P_1, JFK)$, a contradiction; the principled fix is an inequality precondition.

This is why forward search struggles. It is complete and, at uniform cost, optimal, but it will consider flying an empty plane between two irrelevant airports as readily as loading the right cargo. Backward search from the goal considers only relevant actions, regressing a goal to $(g \setminus \mathrm{Add}(a)) \cup \mathrm{Precond}(a)$, and branches far less - but its nodes are sets of states rather than states, which needs unification and leaves the good heuristics harder to define.

C. Heuristics by deletion

Here the representation pays. A heuristic is the cost of an easier problem, and the schemas can simply be edited.

Ignore preconditions strips every precondition, making every action applicable everywhere. What remains is covering the unmet goal literals with as few add lists as possible. This is where the classical puzzle heuristics come from: in the 8-puzzle, dropping $\mathrm{Blank}(s_2) \wedge \mathrm{Adjacent}(s_1, s_2)$ gives misplaced-tiles, and dropping $\mathrm{Blank}(s_2)$ alone gives Manhattan distance. Both fall out mechanically.

Ignore delete lists strips every negative effect. Nothing can undo anything, so progress is monotonic and hill-climbing finds an approximate relaxed plan in polynomial time.

On air cargo, both report 2 at the initial state against a true cost of 6 (the delete-list figure counts the layers of the relaxed problem, as a planning graph does; the shortest relaxed plan itself is 5 actions):

The margins are small because the problem is small. What matters is that nobody wrote a heuristic for air cargo.

D. What a planning graph notices

A planning graph alternates literal levels and action levels, adds a persistence action for every literal, and is built in polynomial time with no search. Its substance is the mutex links, recording pairs that cannot hold together: actions with inconsistent effects, actions that interfere, actions with competing needs, and literals whose every pair of producers is mutex.

Take the smallest problem that makes the point. Initially you have a cake; you want to have it and to have eaten it. Eating deletes having, and baking requires not having.

Both goal literals appear at $S_1$, so per-literal reasoning says one step is enough. It is not: at $S_1$ they are mutex, because the only way to have the cake is to persist it and the only way to have eaten it is to eat it, and eating deletes having. By $S_2$ the mutex is gone and the graph has levelled off.

The level cost of a literal is where it first appears, giving three heuristics. Max-level takes the largest, level-sum adds them, and set-level waits for the first level where all goal literals appear with no mutex among them. Here they give $1$, $1$ and $2$. The optimal plan - eat the cake, then bake another - has length $2$, so only set-level is right, and only it looked at whether the goals could coexist.

Max-level and set-level are admissible and set-level dominates. Level-sum treats subgoals as independent and can overshoot, so it is inadmissible in general, which does not stop it from being the most useful of the three in practice.

The figure below builds that graph rather than quoting it - every mutex in it is computed from the three action conditions and the two literal ones, which is why the counts come out 0, 4, 3, 3 on their own. Look at the line joining the two goal literals. It is there at S1 and gone at S2, and that single disappearing line is the whole difference between a heuristic that answers 1 and the true answer of 2.

Where this leaves you

The approximation runs one way only. A literal absent at level $i$ is genuinely unachievable within $i$ steps, which is what makes level costs lower bounds. A literal present, even without a mutex, promises nothing; only pairwise inconsistencies are computed, so a three-way conflict passes unnoticed. That asymmetry is the honest shape of the whole subject: classical planning does not make hard problems easy, it makes the description of a problem something a solver can read. The training path Classical Planning builds the schemas, the relaxations and the graph by hand and in code.