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.