Planning: STRIPS & the frame problem

Planning is state-space search

Planning finds a *sequence of actions* that turns a start state into a goal state — which is exactly state-space search: states are world descriptions, operators are actions, and a plan is a solution path. So BFS, DFS, and A\* from Modules 3–4 all apply. What is new is that a state is no longer an atomic symbol but a *collection of predicates* about the world (e.g. on(C,A), clear(B), handempty), and that creates a hard problem.

The frame problem

When an action changes part of the world, a planner must know which parts *stay the same*. Naively you would write a frame axiom for every (action, predicate) pair that does not change — *"unstacking C from A does not change the colour of the table, the lighting, B's position..."* The number of such axioms blows up. This is the frame problem: representing the non-effects of actions is exponentially expensive.

STRIPS operators solve it

STRIPS represents each operator with three lists:

- Preconditions — what must be true to apply it. - Add list — predicates it makes true. - Delete list — predicates it makes false.

The STRIPS assumption is the key trick: *any predicate not in the add or delete list is assumed unchanged.* That single convention replaces all the frame axioms — you specify only what an action *changes*, and everything else persists automatically. For example:

unstack(X, Y):
  pre:    on(X,Y), clear(X), handempty
  add:    holding(X), clear(Y)
  delete: on(X,Y), clear(X), handempty

Everything not mentioned (the table, other blocks) simply carries over. This is the closed-world assumption applied to *change*.

Worked example — blocks-world plan by BFS

Start with C on A, and A, B on the table; goal on(B, A). We BFS over states, applying every legal STRIPS operator and never revisiting a state. The planner must first clear A (which is blocked by C) before it can stack B:

unstack(C,A) → putdown(C) → pickup(B) → stack(B,A)

Notice the planner *discovers* it must move C out of the way: that interaction between subgoals (clearing A is a precondition of the real goal) is the non-linearity that makes planning harder than plain search. The Python below runs this exact search and prints the plan.