Understanding Automated Planning
Classical planning addresses fully observable, deterministic, static, single-agent environments, and its contribution is representational rather than algorithmic. A state is a conjunction of fluents that are ground, positive and function-free. Under the closed-world assumption any fluent not mentioned is false, so negation never has to be written down, and under the unique names assumption distinct constants denote distinct objects. The effect is that a state can be treated interchangeably as a logical sentence to reason with or as a set to manipulate, and most planning algorithms take the second reading.
Actions are given as schemas in PDDL, the Planning Domain Definition Language, a descendant of STRIPS. A schema names the action, lists its variables, and gives a precondition and an effect. The positive literals of the effect form the add list and the negated ones the delete list, so applying a ground action to a state is a single set expression: remove the delete list, then add the add list. Everything else persists by default. This is how classical planning handles the frame problem - not by proving what stays the same, but by restricting attention to domains where most actions leave most things alone and then describing only the change.
A schema is a lifted representation, raising reasoning from propositional logic to a restricted fragment of first-order logic. Where a propositional agent needed one sentence per orientation, time step and location, a single schema covers them all. The economy is real but grounding it is expensive: a schema multiplies out over every argument domain, so a flight action with ten planes and five airports contributes two hundred ground actions on its own. Some care is also required with spurious instances, such as flying from an airport to itself, which is excluded by an inequality precondition.
A goal is written like a precondition, as a conjunction of literals whose variables are read existentially, and a state achieves it when it entails it. That completes a search problem: initial state, applicable actions, result function, goal test. Forward search over this space is complete but badly uninformed, because grounding produces many actions irrelevant to any particular goal. Backward search from the goal considers only relevant actions and so branches less, but its nodes are sets of states rather than states. The decisive advantage of the representation is that a heuristic can be extracted by editing the schemas themselves.
How to Calculate
Result(s, a) = (s \ Del(a)) ∪ Add(a), applicable when Precond(a) ⊆ s
where
- s
- a state: the set of ground positive fluents true in it, everything else false
- Add(a)
- the positive literals of the action’s effect
- Del(a)
- the literals the action’s effect negates
- Precond(a)
- the literals that must hold for the action to be applicable
Example of Automated Planning
The spare-tire problem starts from At(Flat, Axle) ∧ At(Spare, Trunk) with the goal At(Spare, Axle). Breadth-first forward search returns a three-step plan: remove the flat from the axle, remove the spare from the trunk, put the spare on the axle.
The flat must come off first because PutOn carries the negative precondition ¬At(Flat, Axle). Without it the two-step shortcut would be legal, which shows negative preconditions doing work that add and delete lists alone cannot.
The air-cargo domain with two cargos, two planes and two airports expands three schemas into twenty ground actions, and its optimal plan is six steps: load both cargos, fly each plane to the other airport, unload both.
Advantages and Disadvantages
Pros
- The same domain-independent solver handles any problem expressible in the language, with no hand-written search.
- Schema structure supports heuristics derived automatically by relaxation, rather than invented per domain.
- State update is set arithmetic, which keeps implementations short and makes reasoning about them straightforward.
Cons
- Grounding a schema multiplies out over every argument domain and can explode before search even begins.
- The classical assumptions - deterministic, fully observable, static, single agent - exclude most real environments.
- Restricting states to ground positive function-free fluents rules out expressive descriptions that some domains genuinely need.
Frequently Asked Questions
How is this different from ordinary search?
Ordinary search treats a state as an atom that can only be tested for goalhood, so any heuristic must be supplied by hand. Planning uses a factored state and inspectable action descriptions, which means the solver can construct its own heuristic by relaxing the schemas. The search algorithms themselves are unchanged.
Why are negative literals banned from states but allowed in preconditions?
A state must be finite, and listing everything false is not. The closed-world assumption makes absence mean falsity, so a state needs only positive fluents. A precondition is a query rather than a description, so asking whether something is absent is both meaningful and cheap.
Is backward search better because it branches less?
It branches less, since only actions whose add list supplies a needed literal are relevant. But each node is a goal description standing for many states, possibly containing variables, so matching requires unification and good heuristics are harder to define. Forward search with a strong derived heuristic has generally won.
The Bottom Line
Automated planning is a bet that the right representation beats a better search: describe actions by what they change, keep states factored, and a domain-independent solver can then read the problem description closely enough to build its own heuristics. Everything that makes the language restrictive is what makes that possible.