STRIPS (Stanford Research Institute Problem Solver) | AI Planning

FOUNDATIONAL AUTOMATED PLANNING FORMALISM

What is STRIPS (Stanford Research Institute Problem Solver)?

STRIPS is the seminal formalism for representing and solving problems in classical automated planning.

STRIPS (Stanford Research Institute Problem Solver) is a foundational formalism for representing classical planning problems, defining a world state as a set of true logical propositions and an action by its preconditions (facts that must be true for it to execute), add effects (facts it makes true), and delete effects (facts it makes false). This representation, known as the STRIPS operator, provides a clear, computationally tractable model of state transitions, enabling algorithms to search for sequences of actions that transform an initial state into a desired goal state. It directly addresses the frame problem by explicitly declaring all changes an action causes, implicitly assuming all other facts remain unchanged.

The STRIPS formalism underpins modern automated planning and is the basis for the standard Planning Domain Definition Language (PDDL). Its action-centric model enables efficient heuristic search algorithms like Graphplan and informs forward search and backward search (regression planning) techniques. While limited to deterministic, fully observable environments, STRIPS established the core concepts—states, actions, preconditions, and effects—essential for more advanced frameworks like Hierarchical Task Networks (HTN), temporal planning, and Markov Decision Processes (MDPs).

FORMAL DEFINITION

Core Components of the STRIPS Formalism

STRIPS (Stanford Research Institute Problem Solver) is the foundational formalism for classical planning, defining a world as a set of logical propositions and actions as operators that transform this world state.

State Representation

In STRIPS, a world state is represented as a finite set of ground, function-free logical propositions that are true. For example, a simple logistics state could be {At(Truck1, WarehouseA), Loaded(Package23)}. The closed-world assumption is typically applied: any proposition not explicitly listed in the state is assumed to be false. This propositional representation provides a discrete, symbolic snapshot of the environment that the planner reasons over.

Action Schema

An action is defined by a parameterized operator with three key components:

Precondition: A conjunction of literals (positive propositions) that must hold in the current state for the action to be executable.
Add List: The set of propositions that become true after the action's execution.
Delete List: The set of propositions that become false after execution.

For example, a Drive(t, from, to) action would have:

Precondition: At(t, from)
Add List: At(t, to)
Delete List: At(t, from)

The STRIPS Assumption

This is a critical simplifying assumption: an action's effects are exactly the union of its Add and Delete lists. Any proposition not mentioned in these lists is assumed to remain unchanged. This directly addresses the frame problem by providing an efficient, local specification of change. It implies deterministic, instantaneous action execution where the only state changes are those explicitly declared, enabling tractable forward and backward search through the state space.

Planning Problem Definition

A STRIPS planning problem is a 3-tuple (I, G, A) where:

I: The initial state, a complete set of true propositions.
G: The goal specification, a conjunction of literals (can include negated propositions).
A: A finite set of ground (instantiated) actions derived from the action schemas.

The planner's task is to find a sequence of actions [a1, a2, ..., an] from A such that, when applied to I, the resulting state satisfies all conditions in G. The sequence is called a plan.

Example: The Blocks World

A canonical STRIPS domain is the Blocks World, with propositions like On(A, B) and Clear(C), and actions:

Pickup(x):
- Pre: Clear(x), On(x, Table), HandEmpty
- Add: Holding(x)
- Del: Clear(x), On(x, Table), HandEmpty
Putdown(x):
- Pre: Holding(x)
- Add: Clear(x), On(x, Table), HandEmpty
- Del: Holding(x) This domain perfectly illustrates precondition interaction and goal regression.

Limitations and Extensions

STRIPS' simplicity is also its limitation, leading to major extensions:

ADL (Action Description Language): Adds quantified preconditions, conditional effects, and disjunctive goals.
PDDL (Planning Domain Definition Language): The modern standard, incorporating STRIPS as a base but supporting types, numeric fluents, durative actions, and derived predicates.
Non-Linear Planning: Early planners using STRIPS, like the original STRIPS program, could generate partially ordered plans, a capability not inherent to the basic formalism.

FORMALISM

How STRIPS-Based Planning Works

STRIPS (Stanford Research Institute Problem Solver) is the foundational formalism for classical automated planning, defining a world model based on logical propositions and actions with explicit preconditions and effects.

STRIPS models the world as a state—a set of true logical propositions. An action is defined by its preconditions (propositions that must be true for it to execute), an add list (propositions it makes true), and a delete list (propositions it makes false). This elegantly solves the frame problem by explicitly declaring all changes, assuming everything else remains unchanged. A planning problem is defined by an initial state, a goal state (a set of propositions), and a set of such actions.

A STRIPS planner searches for a sequence of actions that transforms the initial state into a goal state. Search algorithms like forward search (state-space search) or backward search (regression planning) navigate the state space. Heuristic functions, often derived from a relaxed version of the problem, estimate the cost to the goal and guide algorithms like A search*. The output is a plan: a totally ordered sequence of executable primitive actions.

STRIPS

Frequently Asked Questions

STRIPS (Stanford Research Institute Problem Solver) is the foundational formalism that defines the core logic of automated planning. These questions address its mechanics, historical significance, and modern applications.

STRIPS (Stanford Research Institute Problem Solver) is a formal language and problem-solving model for representing automated planning problems. It works by defining the world as a state composed of logical propositions (facts that are true or false). An action is defined by its preconditions (facts that must be true for it to execute), its add list (facts it makes true), and its delete list (facts it makes false). A planner searches through the space of possible action sequences, applying actions whose preconditions are met in the current state to generate a new state, until it finds a sequence (a plan) that transforms the initial state into a state satisfying all goal conditions.

AUTOMATED PLANNING SYSTEMS

Related Terms

STRIPS established the foundational language for automated planning. These related concepts define the formalisms, algorithms, and extensions built upon its core ideas.

PDDL (Planning Domain Definition Language)

PDDL is the standardized, first-order logic-based language for formally defining planning domains and planning problems, directly descended from the STRIPS representation. It separates the domain (actions, predicates, types) from the problem (objects, initial state, goal).

Key Components: :domain file defines action schemas with preconditions and effects. :problem file specifies object instances and the initial/goal states.
Purpose: Enables the creation of portable, shareable planning benchmarks and facilitates the development of general-purpose planners.
Evolution: Has expanded through multiple international planning competitions to include features like typing, durative actions, and derived predicates.

EXPLORE

Planning as Satisfiability (SATPlan)

SATPlan is an approach that encodes a bounded-length planning problem into a propositional logic formula. A satisfying assignment found by a Boolean satisfiability (SAT) solver corresponds directly to a valid plan.

Mechanism: The encoding creates variables for each possible fact at each time step and each possible action at each step. Constraints enforce action preconditions, effects, and frame axioms.
Advantage: Leverages the immense power of modern SAT solvers, which can often handle very large combinatorial search spaces efficiently.
Relation to STRIPS: Provides a powerful alternative solving technique for classical STRIPS problems, demonstrating the deep connection between planning and logical reasoning.

Hierarchical Task Network (HTN) Planning

HTN planning is a problem-solving method that decomposes high-level tasks into networks of subtasks using domain-specific knowledge, recursively refining them into primitive STRIPS-like actions.

Core Concepts: Uses methods (recipes for task decomposition) and operators (primitive actions, equivalent to STRIPS actions). Planning proceeds by selecting methods to decompose abstract tasks until only executable operators remain.
Contrast with STRIPS: STRIPS searches a space of world states. HTN searches a space of tasks, using knowledge about how to achieve things, not just what the world state is. This often leads to more efficient planning for complex, structured domains.
Use Case: Ideal for domains with known procedural knowledge, such as manufacturing processes or military mission planning.

Frame Problem

The frame problem is the challenge of efficiently representing and reasoning about which aspects of the world remain unchanged when an action is performed.

STRIPS Solution: STRIPS introduced a seminal, though limited, solution via the STRIPS assumption: anything not explicitly listed in an action's add or delete lists is assumed to persist unchanged. This is implemented through its delete lists.
Significance: Before STRIPS, axiomatic representations required stating numerous "frame axioms" for every action and unaffected fact, leading to combinatorial explosion.
Limitations: The STRIPS solution works for propositional representations but becomes more complex in first-order logic with variables, leading to the ramification problem (indirect effects) and qualification problem (unstated preconditions).

State Space & Action Space

These are the fundamental constructs within which a STRIPS planner operates.

State Space: The set of all possible configurations of the world, defined by the truth values of all ground propositions. A STRIPS state is a set of true propositions. The planner's job is to find a path through this space from the initial state to a goal state.
Action Space: The set of all ground instances of action schemas that are applicable in a given state. Applicability is determined by checking if the state satisfies the action's preconditions.
Search Paradigms: Forward search (progression) explores the state space by applying actions from the initial state. Backward search (regression) explores from the goal by inverting actions, a technique often more efficient for STRIPS-style problems.

Graphplan Algorithm

Graphplan is a planning algorithm that constructs a planning graph, a layered structure compactly representing state progression over time, before searching it for a solution.

Planning Graph Layers: Alternates between proposition layers (facts that could be true) and action layers (actions whose preconditions could be met). It includes mutual exclusion (mutex) relations to mark incompatible actions or propositions.
Process: The graph expands forward until the goal propositions appear in a proposition layer without being mutually exclusive. A backward search then extracts a valid plan from the graph.
Advantage over pure STRIPS search: The graph structure and mutex relations provide powerful constraint propagation, often making solution extraction faster than naive state-space search for many problems.