STRIPS

The initial state is a complete snapshot of the world at the start of the planning problem, represented as a conjunction of ground literals (atomic facts) that are true. It defines the starting conditions for all objects and their properties. For example, in a logistics domain, the initial state might specify At(Package1, WarehouseA) ∧ At(Truck1, Depot). All facts not explicitly stated are assumed false, adhering to the closed-world assumption.

The goal state is a partial description of the desired world configuration, specified as a conjunction of literals that must be true at the end of a valid plan. Unlike the initial state, it does not need to be complete. A plan is successful if its final state logically entails the goal. For instance, a goal could be At(Package1, WarehouseB) ∧ Fuel(Truck1) > 50. The planner is indifferent to any other world facts as long as the goal conditions are satisfied.

Actions (or operators) are the mechanisms for state transformation. Each action is defined by three key lists:

• Preconditions: Literals that must be true in the current state for the action to be applicable.
• Add List: Literals that become true after the action executes.
• Delete List: Literals that become false after the action executes (STRIPS' key innovation).

For example, a Drive(Truck, From, To) action would have preconditions like At(Truck, From), an add effect At(Truck, To), and a delete effect At(Truck, From).

Preconditions are the set of facts that must hold in the current world state for an action to be legally executed. They enforce the causal constraints of the domain. Preconditions are checked before an action is applied. If any precondition is false, the action is inapplicable. In STRIPS, preconditions are conjunctions of positive literals; negative preconditions (requiring something to be false) were a later extension. This forces the planner to sequence actions to make preconditions true.

These two lists define how an action changes the world state.

• The Add List specifies new facts that become true. It directly models the action's intended consequences.
• The Delete List specifies facts that become false. This explicitly models state change, solving the frame problem by declaring what changes, rather than inferring what stays the same.

This ADD/DELETE formalism ensures state transitions are deterministic and efficiently computable. Effects are applied after the action's preconditions are satisfied.

The foundational vocabulary of the planning domain.

• Objects: The entities that exist in the world (e.g., Truck1, WarehouseA, Package23).
• Predicates: The properties and relations that can be true or false of objects (e.g., At(x, y), Connected(x, y), FuelLevel(x)).

States are conjunctions of ground atoms, which are predicates instantiated with specific objects (e.g., At(Truck1, WarehouseA)). Actions are defined using variables (e.g., ?t, ?from) that are instantiated with objects during planning.

The quintessential STRIPS problem involves a robot arm manipulating blocks on a table. The initial state describes blocks stacked in a specific configuration. The goal state specifies a desired arrangement (e.g., a tower). Actions include pickup(x), putdown(x), stack(x,y), and unstack(x,y), each with preconditions (e.g., clear(x) and handempty) and effects (e.g., holding(x)). This domain elegantly demonstrates the representation of add effects (new true propositions) and delete effects (propositions made false).

This domain models moving packages between locations using vehicles. Key components:

• Objects: Packages, Trucks, Airplanes, Locations (e.g., cities, airports).
• Predicates: at(obj, loc), in(obj, vehicle), in-city(loc, city).
• Actions: load(pkg, vehicle, loc), unload(pkg, vehicle, loc), drive(truck, from, to), fly(plane, from, to).

Preconditions enforce logical constraints (e.g., a truck and package must be at the same location to load). The planner must sequence actions to satisfy the goal at(package, destination_city). This problem highlights conjunctive goals and the use of different action types within a single plan.

A classic AI problem formalized in STRIPS. A monkey must fetch bananas hanging from the ceiling. The monkey needs to move a box under the bananas, climb the box, and grasp the bananas.

Key Propositions: at(monkey, loc), at(box, loc), height(monkey, low/high), has(monkey, bananas). Actions: goto(loc), pushbox(loc), climbbox, graspbananas.

The precondition for graspbananas requires the monkey and box to be at the same location and the monkey to be at a high height. This problem illustrates intermediate subgoals and the need to achieve certain propositions (height(monkey, high)) that are not part of the final goal but are necessary for action execution.

A famous Blocks World scenario that exposed limitations in early goal-ordering planners. The initial state has three blocks: A on C, and B on the table. The goal state is A on B, and B on C (on(A,B) ∧ on(B,C)).

A naive planner might pursue subgoals independently, leading to an interference problem. For example, achieving on(A,B) first might require moving C, which could then interfere with later achieving on(B,C). A correct STRIPS planner must find a sequence that respects these dependencies, often requiring temporary deconstruction of a partially achieved goal. This anomaly motivated the development of more sophisticated non-linear planning algorithms.

A domain involving resource preparation and concurrent conditions. The goal is to prepare a meal (e.g., cooked food and a set table).

Propositions: clean(hands), dirty(hands), has(ingredient), cooked(food), set(table). Actions: wash_hands (pre: dirty(hands), effect: clean(hands)), cook(food) (pre: clean(hands) ∧ has(ingredient), effect: cooked(food) ∧ dirty(hands)).

This problem demonstrates conditional effects (cooking makes hands dirty) and maintenance goals (clean(hands) must be true to start cooking but can be false afterward). It shows how STRIPS actions model state changes that enable and disable future actions.

A mathematical puzzle perfectly suited for STRIPS representation. The goal is to move a stack of disks from one peg to another, obeying the rule that a larger disk can never be placed on a smaller one.

Objects: Disks (D1, D2,...), Pegs (P1, P2, P3). Predicates: on(disk, peg|disk), clear(top_object), smaller(disk1, disk2). Action: move(disk, from, to).

Preconditions for move(D, X, Y) are: on(D, X), clear(D), clear(Y), and if Y is a disk, smaller(D, Y). This domain showcases the use of typed objects (disks vs. pegs) and relational predicates (smaller) to encode complex rules within action preconditions, ensuring only valid physical moves are planned.

The set of simplifying assumptions that define the STRIPS paradigm and its direct successors. Understanding these highlights STRIPS's scope and limitations:

• Deterministic Actions: Actions have known, certain effects.
• Fully Observable State: The agent has complete knowledge of the world.
• Static Environment: Only the agent's actions change the world.
• Discrete Time: Planning happens in discrete steps.
• Finite Set of Actions/Objects: The problem is bounded.
• Goal is a Conjunction of Literals: The desired state is a set of facts that must be true.