STRIPS (Stanford Research Institute Problem Solver)

A state in STRIPS is a complete snapshot of the world, represented as a set of ground literals (atomic propositions that are true). It is a conjunction of positive predicates with their arguments bound to specific objects. For example, a simple robotic world state could be {On(Robot, Floor), At(Robot, RoomA), DoorClosed(Door1)}. The closed-world assumption is often applied, meaning any literal not explicitly listed in the state is assumed to be false.

An action is a parameterized operator that defines how the agent can change the state. It is not a specific instance but a template with variables. Each action schema consists of three key lists:

• Precondition List: A set of literals that must be true in the current state for the action to be applicable.
• Add List: The set of literals the action makes true.
• Delete List: The set of literals the action makes false.

Example: Move(x, y, z)

• Pre: At(Robot, x), Adjacent(x, y), DoorOpen(z)
• Add: At(Robot, y)
• Del: At(Robot, x)

A complete STRIPS planning problem is a tuple (P, A, I, G).

• P: A set of predicates (the vocabulary).
• A: A set of action schemas.
• I: The initial state, a set of ground literals true at the start.
• G: The goal state, a set of ground literals (often a partial state) that must be true upon completion.

The planner's task is to find a sequence of ground actions (instances of schemas with variables replaced by objects) that, when applied to I, results in a state where all literals in G are true.

This is the fundamental simplifying rule of the formalism: an action changes the world only by the literals explicitly listed in its Add and Delete lists. Everything else remains unchanged. This is also known as the law of inertia. It enables efficient reasoning by limiting the frame problem—the challenge of representing what does not change when an action occurs. In STRIPS, if a fact isn't mentioned, it persists.

A plan is an ordered sequence of ground actions [a1, a2, ..., an]. A plan is a solution to the planning problem if:

1. Action a1 is applicable in the initial state I (all its preconditions are in I).
2. For every subsequent action ak, it is applicable in the state produced by applying all previous actions a1 through a(k-1) to I.
3. After applying the entire sequence to I, the resulting final state satisfies the goal G. Finding this sequence is a search problem in the space of possible states.

Hierarchical Task Network planning builds upon the STRIPS representation by adding a library of methods for decomposing complex tasks. While STRIPS searches through a space of primitive actions, an HTN planner searches through a space of possible decompositions. This makes it more efficient for complex, structured domains like manufacturing or logistics.

• Relation to STRIPS: HTN methods often have preconditions and effects modeled similarly to STRIPS operators.
• Practical Dominance: HTN is often preferred in industrial robotics (e.g., NASA's Europa system, game AI) because its hierarchical nature mirrors human engineering design.

Modern domain-independent planners, such as FastForward (FF) and Fast Downward, use the STRIPS/PDDL representation as their input. Their innovation lies in advanced heuristic search techniques. FF, for example, uses a relaxed planning graph heuristic—ignoring delete effects to quickly estimate the cost to the goal—making it vastly more scalable than the original STRIPS solver.

• Performance Leap: These planners can solve problems with thousands of actions and state variables.
• Core Representation: Despite advanced search, the underlying state transition model is still fundamentally the STRIPS action representation.

In robotics, STRIPS-style task planning is used for the high-level symbolic reasoning layer in a hierarchical architecture. The task planner generates a sequence of symbolic actions (e.g., pick(block_A), place(block_A, table)). This sequence is then sent to a motion planner (e.g., RRT, trajectory optimization) that computes the detailed, continuous robot motions to execute each symbolic action.

• Symbolic-Continuous Divide: STRIPS handles the 'what' and logical order; motion planning handles the 'how' and geometric feasibility.
• Integrated Systems: Frameworks like ROSPlan explicitly use PDDL (STRIPS' successor) to define tasks for robotic systems.

The STRIPS model of goal reduction and means-ends analysis profoundly influenced early AI and cognitive science. It provided a computable model for the General Problem Solver (GPS) theory. The core idea—representing knowledge as facts and changes as operations on those facts—is a foundational pattern in agent architectures, production systems, and even the design of behavior trees for game AI.

• Cognitive Modeling: Early theories of human problem-solving were directly inspired by STRIPS-like planning.
• Agent Design: The Belief-Desire-Intention (BDI) agent model uses a plan library conceptually similar to a set of STRIPS operators.

STRIPS' simplicity is also its key limitation, which drove the development of more expressive planning formalisms:

• No Concurrency: Classic STRIPS assumes actions are sequential. Real-world tasks often require parallel execution.
• No Time or Resources: Actions have no duration, and there is no representation of numeric resources (e.g., battery level).
• Deterministic & Fully Observable: STRIPS assumes actions always succeed and the world state is perfectly known.
• Representational Inefficiency: Describing complex domains can require a combinatorial explosion of predicates and actions.

These limitations led to temporal planners, probabilistic planners (like POMDPs), and planners that handle numeric fluents and soft constraints.

A planning paradigm that decomposes high-level tasks into networks of subtasks using a library of predefined methods. Unlike STRIPS' state-space search, HTN planning is task-oriented. It starts with an abstract task (e.g., "Deliver Package") and recursively decomposes it using methods (e.g., "Navigate to Location then Place Object") until it reaches primitive tasks that correspond directly to executable actions. This approach often yields more efficient plans for complex, structured domains by leveraging domain knowledge encoded in the method hierarchy.

• Key Elements: Compound Tasks (non-primitive), Primitive Tasks (executable actions), Methods (recipes for decomposition), Constraints (ordering, variable binding).

The algorithmic process of computing a feasible path or trajectory for a robot from a start to a goal configuration while avoiding obstacles and respecting kinematic/dynamic constraints. While STRIPS produces a sequence of discrete logical actions (e.g., grasp(block_A)), motion planning computes the continuous geometric and temporal details required for physical execution. This is the bridge between symbolic AI planning and real-world robotics.

• Core Problem: Find a path in the robot's Configuration Space (C-Space).
• Major Algorithm Families: Sampling-based (RRT, PRM), Graph-search-based (A* on grids), Optimization-based (Trajectory Optimization).
• Constraints: Collision avoidance, joint limits, dynamics, torque limits.

An integrated approach that solves long-horizon problems requiring both discrete task-level reasoning (like STRIPS) and continuous motion planning. TAMP algorithms interleave or jointly reason about symbolic actions (e.g., which object to pick) and their geometric feasibility (e.g., whether a collision-free grasp trajectory exists). This is critical for robotics, as a logically sound STRIPS plan may be geometrically impossible.

• Core Challenge: The interdependence of discrete choices and continuous constraints.
• Common Paradigms: Interleaved search (plan then try to motion-plan, backtrack if fails), Symbolic-geometric backtracking, Integrated belief-space planning.
• Output: A hybrid plan interleaving discrete actions with parameterized motion primitives.

A fundamental algorithm family for efficiently exploring large state spaces, such as those generated by STRIPS. A* is a best-first search algorithm that uses a cost function f(n) = g(n) + h(n), where g(n) is the cost to reach node n and h(n) is a heuristic estimating the cost from n to the goal. For STRIPS planning, effective heuristics (like Relaxed Plan Heuristic or Fast Forward (FF) heuristic) are derived by simplifying the planning problem (e.g., ignoring delete lists) to estimate remaining effort.

• Role in Planning: Drives the forward search through the space of world states.
• Critical Requirement: The heuristic h(n) must be admissible (never overestimates) for A* to guarantee optimality.
• Modern Use: Foundation for many state-of-the-art classical planners like Fast Downward.

The processes that ensure a generated STRIPS plan is correct and executable in a dynamic world. Plan Validation formally verifies that a plan sequence, when applied to the initial state using the action definitions, logically achieves the goal. Execution Monitoring occurs during real-world robot operation, comparing the expected state (from the plan's predictions) to the observed state from sensors. Discrepancies (e.g., an object is missing) trigger replanning or failure recovery routines.

• Validation Method: Often performed via progression or simulation of the plan.
• Monitoring Triggers: State predicate violations, action precondition failures, unexpected exogenous events.
• Response: Replanning from the current state, plan repair, or invoking contingency handlers.