STRIPS (Stanford Research Institute Problem Solver)

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.

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)

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.

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.

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.

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.

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.

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.

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).

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 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.