Automated planning

A search algorithm can find a route on a map, and a logic agent can prove that a fact follows from what it knows. Automated planning asks a harder, more general question: given where I am now and where I want to be, what sequence of actions gets me there? A warehouse robot that must fetch a part, a Mars rover scheduling a day of science, a factory line assembling a product — each needs a plan: an ordered list of actions that transforms the initial state into one that satisfies a goal.

On the surface this is just search — states, actions, a goal test — the same machinery you met in . The twist that makes planning its own field is how it describes the world. A plain search treats each state as an opaque blob — a single node with no visible parts. A planner cracks that blob open and represents a state as a set of facts. That one change — a factored representation — is what lets a planner reason about goals, derive its own heuristics, and scale to worlds far too large to draw as a graph.

Factored states: a world made of facts

In ordinary search a state is atomic — node #57 — and you learn nothing by looking at it. In planning a state is a set of true facts (also called fluents, because they can change — "flow" — over time). Everything not in the set is assumed false (the closed-world assumption). A little blocks-on-a-table world might be in this state:

\{\,\mathrm{OnTable}(A),\ \mathrm{OnTable}(B),\ \mathrm{Clear}(A),\ \mathrm{Clear}(B),\ \mathrm{ArmEmpty}\,\}

Reading it off: block A and block B both sit on the table, nothing is stacked on either (both are clear), and the robot arm holds nothing. Because the description is structured, we can talk about parts of it: "is A clear?" is just a membership test, and a goal need only mention the facts we care about. This exposed structure is the whole point — a planner can see why a state does or doesn't match the goal, instead of treating states as indistinguishable dots.

Actions as schemas: STRIPS

If states are sets of facts, an action is a rule for editing that set. The classic language for this is STRIPS (from the Stanford Research Institute Problem Solver, 1971). Each action schema has three fact-lists:

An action is defined by three sets of facts:

Applying an applicable action to a state s gives the new state s' = (s \setminus \mathrm{Delete}) \cup \mathrm{Add}. The goal is a partial state — a set of conditions to achieve — and any state whose facts include all of them counts as a goal.

Here is one blocks-world action, spelled out concretely. To pick block A up off the table:

Notice the delete list carefully: once the arm is holding A, it is no longer on the table, no longer clear (you can't stack on a block that's in the gripper), and the arm is no longer empty. An action must retract everything it makes false, not just assert what it makes true — a point we'll come back to.

A plan is a chain of edits

Put a start state, a couple of actions, and a goal together and you get a plan: a chain of states, each obtained from the last by applying one action's delete-then-add. Step through a two-action plan whose goal is On(A, B) — watch each action's effects rewrite the fact set.

The initial state matches nothing in the goal; after Pickup(A) the arm holds A; after Stack(A, B) the fact On(A, B) is finally true, so the goal — a partial specification asking only for On(A, B) — is satisfied. The two-action sequence is the plan.

Planning is search — over facts

Once actions edit fact-sets, finding a plan is a search problem, and there are two natural directions to search in:

Either way it is still search — breadth-first, depth-first, or heuristic-guided. The crucial difference from route-finding is that the state graph is never written out in advance. It is defined implicitly by the action schemas: successors are computed on demand by testing preconditions and applying add/delete lists. A blocks world with a dozen blocks has astronomically many states, but the planner only ever touches the handful it visits.

// A tiny STRIPS forward planner: BFS over sets of facts. type Action = { name: string; pre: string[]; add: string[]; del: string[] }; const actions: Action[] = [ { name: "Pickup(A)", pre: ["OnTable(A)", "Clear(A)", "ArmEmpty"], add: ["Holding(A)"], del: ["OnTable(A)", "Clear(A)", "ArmEmpty"] }, { name: "Stack(A,B)", pre: ["Holding(A)", "Clear(B)"], add: ["On(A,B)", "Clear(A)", "ArmEmpty"], del: ["Holding(A)", "Clear(B)"] }, ]; const start = ["OnTable(A)", "OnTable(B)", "Clear(A)", "Clear(B)", "ArmEmpty"]; const goal = ["On(A,B)"]; const holds = (facts: string[], s: Set<string>) => facts.every((f) => s.has(f)); const key = (s: Set<string>) => [...s].sort().join(","); function plan(): string[] | null { const s0 = new Set(start); const queue = [{ state: s0, path: [] as string[] }]; const seen = new Set([key(s0)]); while (queue.length > 0) { const { state, path } = queue.shift()!; if (holds(goal, state)) return path; // all goal facts present → done for (const a of actions) { if (!holds(a.pre, state)) continue; // preconditions must hold const next = new Set(state); for (const f of a.del) next.delete(f); // apply the DELETE list first for (const f of a.add) next.add(f); // then the ADD list const k = key(next); if (seen.has(k)) continue; // skip states already visited seen.add(k); queue.push({ state: next, path: [...path, a.name] }); } } return null; } const result = plan(); console.log(result ? "Plan found: " + result.join(" -> ") : "No plan exists");

The planner prints Pickup(A) -> Stack(A,B) — exactly the chain the diagram walked through. Nothing about the map was hard-coded; the successor states were generated from the schemas.

The most common beginner bug is forgetting the delete list. It is tempting to write only what an action achieves — Stack(A, B) adds On(A, B), job done. But if the action doesn't also delete the facts that become false (Holding(A), and Clear(B) — you can't stack another block on B now), the state accumulates contradictions. You end up in an impossible world where the arm holds a block that is simultaneously resting on another, and later actions fire on preconditions that should no longer hold. Every fact an action makes false must appear in its delete list.

A second subtlety: the goal is partial. Asking for On(A, B) does not pin down where block C is, or whether the arm is empty — many full states satisfy it. The goal is a set of conditions, and the goal test is "do all these facts hold?", not "is the state exactly equal to this one?".

Because the factored, fact-based description hands the planner something a plain graph search never has: structure it can analyse to invent its own heuristics, automatically, for any domain. The most famous trick is the ignore-delete-lists relaxation: throw away every delete list, so facts can only ever accumulate and never disappear. That relaxed problem is far easier to solve, and the length of its solution is an admissible-ish estimate of the real distance to the goal — a ready-made, domain-independent heuristic to feed to an informed search. You cannot do this to an opaque search graph, because there is nothing inside a node to relax. The state space also stays implicit: it is described by a compact set of schemas and never enumerated, so a planner can operate in worlds with more states than there are atoms in the universe, visiting only the sliver it actually explores. Structure in, leverage out — that is the bargain the factored representation buys.