Representing Actions with PDDL

Search treated a state as a black box you could only test for goalhood. Logic could look inside a state but had to reason with ground sentences, and drowned. Planning takes the middle path: a state is a collection of variables, and that structure is what makes automatic heuristics possible.

States as sets of fluents

A state is a conjunction of fluents that are ground, function-free atoms. For the spare-tire problem the initial state is

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

Three restrictions make this tractable rather than merely expressive.

• Ground. $\mathrm{At}(x, y)$ is not a state fluent; it has a variable in it.
• Positive. $\neg \mathrm{Poor}$ is not allowed. Under the closed-world assumption any fluent not mentioned is false, so negation is free and implicit rather than written down.
• Function-free. $\mathrm{At}(\mathrm{Father}(\mathit{Fred}), \mathit{Sydney})$ is out; the unique names assumption then makes distinct constants distinct objects.

The payoff is that a state can be read two ways at once: as a logical conjunction to be reasoned with, or as a set of fluents to be manipulated with set operations. Most planning algorithms take the second reading, and it is why the code below is so short.

Actions as schemas

The frame problem is the difficulty of saying what stays the same when something changes. Classical planning sidesteps it by concentrating on problems where most actions leave most things alone, and then describing an action purely by what changes. Everything unmentioned persists.

An action schema is a lifted description standing for many ground actions:

$$\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 effect splits into an add list, the positive literals, and a delete list, the negated ones. Applying a ground action $a$ to a state $s$ is then one line of set arithmetic:

$$\mathrm{Result}(s, a) = (s \setminus \mathrm{Del}(a)) \cup \mathrm{Add}(a) ,$$

and $a$ is applicable when $\mathrm{Precond}(a) \subseteq s$.

This lifting is the whole economy of the representation. In the wumpus world the logical agent needed a separate sentence for moving forward at each of four orientations, $T$ time steps and $n^2$ locations. One schema replaces all $4Tn^2$ of them.

Grounding, and counting

A schema is a promise; a planner works with the ground actions it expands into. The air cargo domain has three schemas, and with two cargos, two planes and two airports they expand to twenty ground actions.

Note the guard. Without it the schema also produces $\mathrm{Fly}(P_1, JFK, JFK)$, whose effect would be $\neg\mathrm{At}(P_1, JFK) \wedge \mathrm{At}(P_1, JFK)$ - a contradiction. The fix is an inequality precondition requiring the two airports to differ.

Grounding also scales badly, which is the point of keeping schemas around as long as possible. Ten planes and five airports give $\mathrm{Fly}$ alone $10 \times 5 \times 4 = 200$ ground actions, and the count grows as the product of every domain in the schema.

Move the three domains below and watch the product. At two of everything it is the twenty above; push the planes to ten and the airports to five and Fly alone contributes two hundred, before any other schema is counted. Load and Unload grow with the cargo and Fly does not, because a schema only multiplies out over the arguments it actually mentions.

The guard is worth turning off once. Without the inequality precondition the schema produces one Fly(p, a, a) per plane per airport, and the figure counts them. It is not a tidying-up detail: without it the schema describes actions whose effect both asserts and denies that the plane is where it is.

A goal is a precondition

A goal is written like a precondition: a conjunction of literals, possibly with variables, which are read existentially. So $\mathrm{At}(p, \mathit{SFO}) \wedge \mathrm{Plane}(p)$ means some plane is at San Francisco. A state satisfies a goal when it entails it, which under the closed-world assumption is just a subset test on the positive literals.

This is not a weaker logic, it is a chosen fragment. Every restriction - ground, positive, function-free, effects-only - exists so that the structure of an action is open to inspection. The next lesson turns that structure into search, and the one after into heuristics derived automatically from the schemas themselves. None of that is available when a state is an atom.

Before the quiz

Be able to say what a factored representation is and what it buys, list the three restrictions on state fluents and what the closed-world assumption does, write an action schema and apply it as set arithmetic, count the ground actions a schema expands into, and explain why an inequality precondition is sometimes needed.