Classical Planning: STRIPS and PDDL

Core Idea

Classical planning finds a sequence of actions that turns an initial state into one that satisfies a goal, in a world that is fully observable, deterministic and static. Instead of writing a custom state representation for every problem, planners describe states as sets of logical facts and actions as reusable schemas with preconditions and effects. This style comes from STRIPS, a planner built at SRI International around 1971, and is standardized today in PDDL, the Planning Domain Definition Language. Because the representation is shared, one general planner can solve logistics, robot and puzzle problems, and it can compute domain-independent heuristics automatically.

How It's Best Learned

Write the blocks world in PDDL style by hand: predicates such as On(x, y) and Clear(x), one Move action schema, an initial state and a goal. Apply actions to states on paper using "remove the delete list, add the add list" until the goal holds. Then run forward search with and without the ignore-delete-lists heuristic, and examine the Sussman anomaly to see why goals cannot always be achieved one at a time.

Common Misconceptions

• Planning is a completely different technique from search. (Classical planners usually are search algorithms; what is new is the factored, logical representation of states and actions, which yields general heuristics.)
• Facts not listed in a state are unknown. (Classical planning uses the closed-world assumption: any fact not listed is false.)
• A goal with several parts can always be solved by achieving each part in turn and keeping it. (Subgoals can interfere; in the Sussman anomaly, achieving either subgoal first forces it to be undone later.)

Explainer

Search algorithms such as breadth-first search and A* treat a state as an opaque object. The programmer supplies a successor function and a goal test for each new problem. Classical planning opens up the state. Each state is a set of facts written in logic, and each action is described by what it requires and what it changes. That shared structure lets one planner handle many domains, and it lets the planner compute its own heuristics.

The representation comes from STRIPS, the Stanford Research Institute Problem Solver, developed by Richard Fikes and Nils Nilsson around 1971 for the Shakey robot project. A state is a conjunction of ground facts, such as On(A, B) and Clear(C). Under the closed-world assumption, anything not listed is false. An action schema has parameters, a precondition and an effect. In the blocks world, Move(b, x, y) requires On(b, x), Clear(b) and Clear(y). Its effect adds On(b, y) and Clear(x) and deletes On(b, x) and Clear(y). Applying an action to a state is simple set arithmetic: remove the delete list, then add the add list. Today domains and problems are written in PDDL, introduced in 1998 for the International Planning Competition.

Given this representation, planning is search. Forward (progression) search starts from the initial state and applies applicable actions. Backward (regression) search starts from the goal and asks which actions could have made a goal fact true. The factored form makes general heuristics possible. A common idea is to ignore delete lists. In that relaxed problem, facts once achieved stay true, so an approximate plan is found quickly, and its length estimates the true remaining cost. The FF planner made this approach well known. Other methods translate planning into propositional satisfiability (SATPlan) or build a layered planning graph (Graphplan).

Planning also exposes a trap. Goals usually have several parts, and it is tempting to solve them one at a time. The Sussman anomaly in the blocks world shows that this can fail. Whichever subgoal you achieve first, you must undo it to achieve the second. A correct plan interleaves steps that serve both.

Classical planning assumes a deterministic, fully observable world. Extensions handle time, resources, uncertainty and partial observability. The core lesson carries over: a good representation of actions turns many problems into one general search.