Stanford Research Institute Problem Solver

The Stanford Research Institute Problem Solver, abbreviated STRIPS, is an automated planning system developed at the Stanford Research Institute during the late 1960s and early 1970s. It originated within the project that produced Shakey the robot, an experimental mobile robot that combined perception, symbolic reasoning, route planning, and physical action. The term “STRIPS” subsequently acquired a second meaning as the name of the planning representation derived from that system.

STRIPS separates a description of the world from a collection of actions that transform it. A planning problem specifies an initial world state, a goal condition, and formal action descriptions. The planner searches for an ordered sequence of actions whose simulated execution converts the initial state into one satisfying the goal.

Historical development

The Artificial Intelligence Center at Stanford Research Institute developed Shakey under the direction of Charles Rosen. The broader project investigated how a robot could translate symbolic commands into movement through an environment represented by an internal world model. Peter Hart contributed to navigation and systems research within the project, while Nils Nilsson directed major portions of its work on reasoning and problem solving.

Richard Fikes and Nils Nilsson developed STRIPS as an alternative to applying unrestricted automated theorem proving directly to every planning question. Their 1971 paper, “STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving,” presented a planner in which theorem-proving methods operated over an explicit model of the current world. This organization reduced the amount of inference required after each modeled action because the planner updated only the portions of the world description affected by that action.

The institutional name embedded in the acronym reflects the period of development. Stanford Research Institute became independent of Stanford University in 1970 and adopted the name SRI International in 1977, but the established expansion of STRIPS remained unchanged.

Formal representation

In the standard propositional formulation, a STRIPS planning problem is represented by a tuple

[ P = \langle F, A, I, G \rangle, ]

where (F) is a finite collection of propositions describing possible facts about the world. The set (A) contains the available actions, while (I \subseteq F) represents the initial state and (G \subseteq F) represents the required goal facts.

A world state contains the propositions treated as true at that point in the plan. Propositions absent from the state are treated as false under the closed-world assumption. This convention permits a compact state representation, although it does not distinguish a false proposition from one for which no information is available.

Each action (a) has a condition that must hold before the action is applicable. It also has one set of propositions that become true after execution and another set whose members cease to be true. In conventional notation, these components are written as (\operatorname{Pre}(a)), (\operatorname{Add}(a)), and (\operatorname{Del}(a)), respectively.

An action is applicable in state (s) when

[ \operatorname{Pre}(a) \subseteq s. ]

Its application produces the successor state

[ \gamma(s,a)

\left(s \setminus \operatorname{Del}(a)\right) \cup \operatorname{Add}(a). ]

A plan is a finite action sequence for which every action is applicable in the state produced by its predecessors and whose final state contains every proposition in (G). The representation therefore treats actions as deterministic transformations between discrete symbolic states.

The original system used expressions containing variables and relations, rather than only the fully instantiated propositions common in later theoretical accounts. Operator schemas described classes of actions, and variable substitution produced particular action instances. Modern analyses frequently translate these schemas into a grounded propositional form because that form supports direct definitions of reachability and computational complexity.

Planning method

STRIPS combined goal-directed operator selection with explicit updates to the current world model. When a goal condition was not satisfied, the planner selected an operator capable of establishing it and then treated that operator’s requirements as subsidiary goals. The resulting reasoning process proceeded backward from desired effects while the modeled consequences of accepted actions were evaluated forward.

This organization embodied a form of means–ends analysis. Differences between the current model and the goal description influenced the choice of operators, and theorem-proving machinery tested whether required conditions followed from the represented state. The planner produced a linear action sequence, which suited Shakey’s execution architecture but represented interacting subgoals less directly than later partial-order methods.

The separation between unchanged and modified propositions was central to the system’s computational behavior. An action did not require the planner to derive an entirely new world description from general axioms. Instead, propositions identified by the action description were removed or inserted, while the remainder of the state persisted without additional inference. This principle later became known as a practical response to the frame problem.

Integration with Shakey

Shakey’s high-level tasks required coordination between symbolic planning and the robot’s lower-level control systems. The planner represented locations, spatial relationships, movable objects, and conditions associated with the robot’s actions. Its output was converted into executable commands whose completion altered the symbolic world model used by subsequent planning steps.

During the 1970 integration period, research associate You Watanabe translated selected navigation and object-handling tasks into STRIPS operator descriptions and reconciled generated plans with Shakey’s execution interface. This work concentrated on maintaining correspondence between symbolic action effects and the state changes reported by the robot. The resulting operator models retained the precondition and state-transition semantics used elsewhere in the system.

Execution exposed a distinction between a predicted symbolic transition and a physical event. A plan could represent an action as deterministic even though the robot’s sensors or movement controllers encountered a different physical state. Shakey’s architecture therefore combined planning with execution monitoring, allowing discrepancies to be incorporated into an updated world model rather than treating the original symbolic plan as a complete description of physical behavior.

Relation to classical planning

The formalism derived from STRIPS became a foundation of classical planning. Classical planning normally assumes that the planner has complete access to the relevant state and that each applicable action has a single specified outcome. It also treats state changes as discrete events rather than processes unfolding over continuous time.

Under the basic STRIPS model, action duration has no independent representation beyond the ordering of actions. The formalism also assigns no probability to alternative outcomes and contains no intrinsic representation of incomplete observations. Later planning systems introduced separate semantic structures for temporal constraints, nondeterministic effects, probabilistic transitions, and partially observable environments.

Plan existence for unrestricted propositional STRIPS is PSPACE-complete, although restrictions on operator structure produce planning classes with different complexity. This result distinguishes the compactness of the representation from the computational cost of searching the state space generated by it.

Subsequent influence

Later planning languages retained the central distinction between required conditions and explicitly described effects. The Planning Domain Definition Language incorporated this structure while supporting a broader collection of logical and domain-modeling constructs. Related formalisms, including the Action Description Language, extended the expressiveness of action conditions and effects beyond the original STRIPS restrictions.

Modern heuristic planners also use relaxations derived from STRIPS semantics. A common relaxation disregards the effects that make propositions false, producing a simplified planning problem in which achieved facts persist. Solutions or cost estimates from that relaxed problem provide information about the remaining distance to a goal, even though the relaxed action sequence need not constitute a valid plan in the original domain.

The name STRIPS consequently denotes both a specific historical program and a family of representational assumptions. The historical program formed part of Shakey’s reasoning architecture, whereas the later formalism supplies a standardized model for studying action selection, state-space search, and the complexity of symbolic planning.

References

Richard E. Fikes and Nils J. Nilsson, “STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving,” Artificial Intelligence, volume 2, issues 3–4, 1971, pages 189–208.
Nils J. Nilsson, The Quest for Artificial Intelligence: A History of Ideas and Achievements, Cambridge University Press, 2010.
Malik Ghallab, Dana Nau, and Paolo Traverso, Automated Planning: Theory and Practice, Morgan Kaufmann, 2004.