Textbook of AI

STRIPS, the Stanford Research Institute Problem Solver, 1971, is the planning formalism introduced by Richard Fikes and Nils Nilsson at SRI as the planning component of the Shakey robot. STRIPS gave the AI planning community a representation that was simple enough to reason about, expressive enough to model real-world tasks, and tractable enough to admit search algorithms. Half a century later, STRIPS is still the conceptual core of most classical planners.

Representation

A STRIPS problem consists of:

• A finite set of propositional fluents (atoms) describing the world; e.g. at(robot, room1), holding(robot, box), door-open(door12).
• An initial state $I$: a set of fluents asserted true; everything else is false (the closed-world assumption).
• A goal $G$: a set of fluents that must hold in the final state.
• A set of operators (action schemas), each with three components:
  • a precondition , fluents that must hold for the operator to apply;
  • an add list, fluents made true by the operator;
  • a delete list, fluents made false by the operator.

Everything not in the add or delete lists is unaffected, the STRIPS assumption, also called the frame assumption, which sidesteps the much-discussed frame problem by fiat.

Example: a blocks-world unstack operator

operator: unstack(x, y)
  precondition: clear(x) ∧ on(x, y) ∧ handempty
  add:          holding(x) ∧ clear(y)
  delete:       on(x, y) ∧ clear(x) ∧ handempty

A plan is a sequence of grounded operators that transforms $I$ into a state satisfying $G$. Planning is the search problem of finding such a sequence.

Search algorithms

Classical STRIPS planning is PSPACE-complete (Bylander 1994), but in practice strong heuristics make it tractable:

• Forward search through state space, using heuristics like $h^+$ (the cost of the delete-relaxation, pretend deletes do not exist), $h_{\mathrm{FF}}$ (the FastForward relaxed-plan length), and landmark heuristics.
• Backward search from goal to initial state.
• Plan-space planning (POP, UCPOP), which works on partially-ordered plans rather than state sequences.
• SAT-based planning (BlackBox, SatPlan), encoding bounded-horizon planning as a SAT problem.

PDDL and modern planners

The STRIPS representation, despite its severe simplifications, proved expressive enough to support a half-century of planning research. Modern academic planners use the PDDL (Planning Domain Definition Language, McDermott et al. 1998), a syntactically-cleaner descendant of STRIPS with extensions for:

• Typed parameters (PDDL 1.x);
• Numeric fluents and durative actions (PDDL 2.1, Fox & Long 2003);
• Derived predicates and timed initial literals (PDDL 2.2);
• Probabilistic effects (PPDDL);
• Multi-agent planning (MA-PDDL).

Practical planners, FastForward (FF), FastDownward, LAMA, ENHSP, OPTIC, routinely solve PDDL problems with millions of grounded actions. The biennial International Planning Competition (IPC) has driven steady benchmark progress since 1998.

Modern relevance

STRIPS-style planning is widely used in robotics (PR2, Atlas), spacecraft autonomy (NASA's Remote Agent on Deep Space 1, Mars rover sequencing), logistics (Amazon warehouse robot dispatch) and elevator scheduling. The classical-planning community has, in recent years, begun integrating learned heuristics, sometimes from deep neural networks, into otherwise STRIPS-style planners, partially closing the gap between symbolic and learned approaches. Large language models have also been used as planners directly (PlanBench, ReAct, Tree-of-Thoughts), but tend to under-perform classical planners on benchmark domains, especially for long-horizon problems.