ℹ️ Note: This note was originally about STRIPS specifically, then expanded (merge from planning-i_30-04-26.md, 23/05/26) to cover all of Classical Planning: STRIPS + Situation Calculus + PDDL + the three problems (Frame / Qualification / Ramification) + relaxation heuristics. The filename stays STRIPS.md so existing wikilinks across the vault continue to resolve. The original atomic-note material (worked Python planner, PDDL extensions table, “where STRIPS is used today”) lives at the bottom.
Planning = find a sequence of actions that transforms an initial state into a goal state in a fully observable, deterministic, static environment.
Unlike local search (don’t care about path) or classical search (treat states as opaque): planning exploits the internal structure of states (collections of properties).
Three classical challenges: Frame, Qualification, Ramification.
Two main classical formalisms covered in the lecture: Situation Calculus (deductive/logical) and STRIPS (state-based). PDDL is the modern extension of STRIPS.
A third family, probabilistic planning (MDPs), is mentioned on the “Planning Formalized” slide and covered separately in Planning II.
Searching vs. Planning
Approach
Cares about sequence?
Uses internal state structure?
Local Search
No
No
Classical Search
Yes
No (states are opaque)
Planning
Yes
Yes — states are collections of properties
This is the framing slide that motivates everything else.
The Three Problems (Frame / Qualification / Ramification) ⚠️
These are exam-critical. Know each by name and have a concrete example ready.
Problem
Definition
Lecture example (Kiva / Blocksworld)
Frame problem
Actions change the world, but most things stay the same — how do we represent that efficiently?
When moving one PSU, the state of all other PSUs is unchanged. When putting A on the table, A stays clear, B stays on C, C stays on the table.
Qualification problem
Actions may have an endless list of preconditions we cannot fully enumerate.
We may be unable to move a robot because it ran out of power / has a malfunction / its path is blocked / …
Ramification problem
Actions may have unintended side-effects.
When a robot moves a PSU, it also moves every item stored inside the PSU.
⚠️ Exam trap: all three are distinct. Don’t conflate Frame ↔ Ramification. Frame is about what stays unchanged; Ramification is about extra things that change without us asking.
See also: Frame Problem for the dedicated deep-dive note.
Situation Calculus (Deductive Planning)
History. Introduced by McCarthy (1963); used for plan construction via resolution by Green (1969); further developed as Event Calculus (Kowalski 1986) and Fluent Calculus (Thielscher 2000).
Features (slides):
States are described by logical formulas (subsets of FOL).
Operators are described by logical axioms.
Plans can be computed by Theorem Provers.
Situation Calculus does NOT use the Closed-World Assumption.
Situations and Fluents
Fluent = a predicate that can change over time. It gets an additional argument representing the current situation.
Situations are terms, either
Atomic (constants like S1), or
Complex, built from atomic situations by applying operators, e.g. put_on_table(A, S1) or put(B, A, put_on_table(A, S1)).
⚠️ Note on notation: the slides write the resulting situation as put(A,B,S₁) (the operator name is the function symbol). The R&N textbook uses do(a, S). The slides do not use do(...).
Describe preconditions and effects of operators (Horn-clause / implication form: head <- body).
% put(X, Y, S):on(X, Y, put(X, Y, S)) <- clear(X, S), clear(Y, S)clear(Z, put(X, Y, S)) <- on(X, Z, S), clear(X, S), clear(Y, S)% put_on_table(X, S):clear(Y, put_on_table(X, S)) <- on(X, Y, S), clear(X, S)ontable(X, put_on_table(X, S)) <- clear(X, S)
Remark from the slide: different variables refer to different entities. Some frameworks require an explicit X ≠ Y to enforce this.
Frame Axioms — and the Frame Problem in Situation Calculus
The slides state it bluntly: we need axioms not only for what changes, but also for what stays the same. A frame axiom for put(X, Y, S):
on(Y, Z, put(X, Y, S)) <- on(Y, Z, S)
“After putting X on Y, Y still rests on Z if it did before.”
The slide listing on “Frame Axioms” gives six such axioms for the single operator put. Cost: roughly O(actions × fluents) frame axioms — that is the practical face of the frame problem.
Planning Problem in Situation Calculus
Define initial state as logical axioms (e.g. on(d,c,s1), clear(d,s1), ontable(a,s1) …).
Define goal as a theorem (e.g. on(a,b,G), on(b,c,G)).
Apply a Theorem Prover.
The plan is extracted from the proof (Green’s trick — proof witnesses the situation term that names the goal state).
How Situation Calculus “addresses” the three problems (slide)
Qualification: preconditions inside effect axioms can theoretically capture it.
Frame: frame axioms can theoretically capture it.
Ramification: additional axioms can theoretically capture it.
In practice: difficult to guarantee coverage of all cases; runtime can suffer.
Planning with Golog (mention only on slide)
Golog combines Logic Programming with Situation Calculus — high-level programs (while, if, proc) compiled down to situation-calculus reasoning. Not exam-critical detail, but referenced on the slides.
Summary slide (Situation Calculus)
The Situation Calculus is the basic example of Deductive Planning.
States = sets of fluents (logical atoms).
Operators + effects described by logical axioms.
Planning reduces to Theorem Proving.
Pro: deductive reasoning ability comes for free.
Con: verification and computational performance can be a problem.
STRIPS = Stanford Research Institute Problem Solver.
History. Developed by Fikes & Nilsson (1971). Foundation of modern state-based planners (PDDL).
STRIPS is what made planning tractable: instead of axiomatizing every (action, fluent) non-effect like Situation Calculus does, STRIPS sidesteps the Frame Problem by saying “anything not in the ADD or DEL list is unchanged.” Imperative, not logical. Pragmatic, not pretty.
Features (slides):
States are represented by sets of (ground) atoms.
Operators act directly on states.
Planning can be performed by Classical Search or tailor-made algorithms.
STRIPS uses the Closed-World Assumption (CWA): atoms in the state are true; all others are false.
The core formalism — STRIPS as a 4-tuple
A STRIPS planning problem is a 4-tuple (S, A, I, G):
Component
What it is
S — state space
Set of all states. Each state = a set of ground atoms (propositions like OnTable(A), Clear(B)).
A — operators
Set of action schemas, each with PRE/ADD/DEL lists.
I — initial state
A specific state ⊆ S.
G — goal
A set of atoms that must hold in the goal state.
States in STRIPS
Domain D = {a, b, c, d}; Predicates P = {ontable¹, clear¹, on²}.
A state is a set of ground atoms, e.g. s = {ontable(a), ontable(c), ontable(d), clear(a), clear(b), clear(d), on(b,c)}.
A goal G is also a set of ground atoms, e.g. G = {on(b,c), ontable(c)}.
An instantiated operator o is applicable in state s iff PRE(o)⊆s.
The successor state is s′=(s∖DEL(o))∪ADD(o).
(First delete, then add.)
⚠️ The Closed-World Assumption (CWA)
States are sets of atoms. Anything not in the set is assumed false. This is the CWA, and it’s the secret sauce that lets STRIPS “solve” the Frame Problem (see Frame Problem):
No need for frame axioms — anything not in ADD/DEL stays as it was
No need to assert ¬Holding(B) for every block — absence = falsity
Cost: STRIPS can’t represent “I don’t know whether P is true” (no Open World)
This is the OPPOSITE of Description Logics, which use the Open World Assumption.
How STRIPS addresses the three problems
Problem
STRIPS handling
Qualification
PRE-list
Frame
”solved” — anything not in ADD/DEL is unchanged automatically (closed-world + frame convention)
Ramification
ADD-list and DEL-list (you must enumerate them)
Slide: “STRIPS ‘solves’ the Frame problem and allows a more convenient problem representation.” The scare quotes are deliberate — STRIPS shifts the bookkeeping from explicit axioms into a convention; it does not eliminate the underlying issue.
Planning via Classical Search
States = sets of atoms.
Successors = states reachable by applying any applicable operator.
Backward Planning (regression / relevant-state search): start from goal, apply operators backwards until an initial state is reached. Advantage: may consider fewer irrelevant actions.
Plan-space search (POP, etc.) is NOT in the slides — only state-space search (forward/backward) is.
Lecture conclusions (STRIPS)
STRIPS is the basic example of state-based planning.
States = sets of atoms; operators = PRE/ADD/DEL triple.
Frame problem “solved” by leaving everything unchanged that is not changed explicitly.
Planning comes down to classical search.
State-based planning can be more efficient than deductive planning, but planning remains hard in general.
PDDL (Planning Domain Definition Language)
PDDL extends STRIPS significantly. Development driven by the International Planning Competition (IPC) since 1998.
What the slides actually cover for PDDL:
LISP-like syntax:f(x,y,z) becomes (f x y z).
A PDDL representation contains at least a domain definition (types, actions) and a problem definition (initial state, goal).
:requirements flag — e.g. :strips, :typing.
:action, :parameters, :precondition, :effect (where :effect combines ADD + DEL via (and (P) (not (Q)))).
Numeric fluents — e.g. Contains(P, I, 100) meaning PSU P contains 100 instances of item I.
:typing with (:types player location monster element chest) and typed parameters (?p - player ?l1 - location).
⚠️ NOT in the lecture slides (commonly conflated from R&N or PDDL spec): :adl, conditional effects, action costs, durative actions, axioms beyond derived predicates. Mention only with a flag if asked.
Minimal example from the slides (blocksworld)
(define (domain blocksworld) (:requirements :strips) (:action move :parameters (?b ?t1 ?t2) :precondition (and (block ?b) (table ?t1) (table ?t2) (on ?b ?t1) (not (on ?b ?t2))) :effect (and (on ?b ?t2) (not (on ?b ?t1)))))
And a problem file:
(define (problem move-blocks-from-a-to-b) (:domain blocksworld) (:init (and (block a) (block b) (table x) (table y) (on a x) (on b x))) (:goal (and (on a y) (on b y))))
Forward search must be guided. A heuristic estimates the cost from the current state to the goal — usually by solving a relaxed problem.
Ignore-PRE-DEL Heuristic
Relax by ignoring both PRE and DEL of every operator.
Each operator then simply satisfies a number of goals (0, 1, 2, …).
Computing the minimum number of operators needed to cover the goal = set-cover problem ⇒ still NP-hard.
A greedy polynomial-time approximation works in practice — but the resulting heuristic is not admissible (it may overestimate; A* optimality not guaranteed).
Blocksworld illustration (slide): initial {ontable(A), on(C,A), ontable(B), clear(C), clear(B)}, goal on(A,B), on(B,C). Identify the goal with U = {onTable(C), on(B,C), on(A,B)}; each operator with the subset of U it satisfies: Put(A,B): {on(A,B)}, Put(A,C): {}, Put(B,C): {on(B,C)}, … Estimated cost = number of unsatisfied literals.
Warehouse illustration (slide): goal = items at a location; PSUs = subsets of items; minimal set cover = PSUs we must carry.
Ignore-DEL Heuristic
Relax by ignoring only the DEL list.
In the relaxed problem, no operator can undo a goal.
Relaxed problem is still NP-hard, but approximate solution computable in polynomial time.
The resulting heuristic is again not admissible.
Modern planners use heuristic forward search with these relaxation-based heuristics (h_max, h_add, h_FF all descend from Ignore-DEL).
Frame ≠ Qualification ≠ Ramification. Know one concrete example for each. (Confusing them is the single most common exam mistake.)
STRIPS uses CWA; Situation Calculus does not.
The slides put scare quotes around STRIPS “solving” the frame problem — it’s a representational convenience, not a logical solution. Situation Calculus must write explicit frame axioms.
DEL contains positive atoms that are removed; do not write ¬clear(B) into ADD.
Ignore-PRE-DEL and Ignore-DEL heuristics are NOT admissible → A* optimality not guaranteed.
The lecture’s situation term is put(A, B, S₁), not the R&N do(a, S).
PDDL coverage in the slides is limited to :strips, :typing, numeric fluents, derived predicates. Things like :adl, conditional effects, action costs, durative actions are not lecture material — they belong to the broader PDDL spec.
Plan-space search (e.g. POP) is NOT in the slides — only state-space (forward / backward) search.
The “syntactic vs. ontological frame problem” framing (Shanahan / Dennett) is external philosophy of AI — not the lecture’s framing. Do not invoke it on the exam unless the question explicitly asks.
Complexity claim — PSPACE-completeness of classical PROPSTRIPS(R&N background; not in the lecture slides): the slides only state set-cover / NP-hardness for the heuristics’ relaxed subproblems, and the general remark “planning remains hard in general.”
“STRIPS solves the Frame Problem.” → FALSE. It sidesteps it via CWA + ADD/DEL. The ontological problem (knowing which actions actually change which things) is just pushed onto the modeler.
STRIPS can’t handle uncertainty. Actions are deterministic, the world is fully observable, no probabilities. For uncertainty → MDPs (Markov Decision Process (MDP)).
Ground operators vs. action schemas. A schema like pickup(X) has free variable X. Grounding substitutes specific blocks: pickup(A), pickup(B). A planner works with grounded operators (potentially many).
✅ Frame problem handled by convention — no axioms to write.
✅ Plugs straight into any classical search algorithm.
Cons.
⚠️ Closed-world assumption means you cannot represent “unknown” facts.
⚠️ ADD/DEL must enumerate every directly-changed atom; ramifications (indirect effects) need to be encoded by hand into ADD/DEL of every operator they apply to.
Goal. Given an initial-state theory T₀, a set of effect axioms E, and a set of frame axioms F, prove the goal G(σ) for some ground situation term σ. The witness σ is the plan.
SIT-CALC-PLAN(T₀, E, F, G): T ← T₀ ∪ E ∪ F Use a theorem prover (e.g. resolution) to derive: ∃σ. G(σ) Extract σ from the proof — σ is a nested term like put(B, C, put_on_table(A, S₁)) return σ as the plan
Cost. First-order theorem proving is semi-decidable in general; for restricted Horn-like fragments (as used in the lecture’s examples) it is decidable but can still be expensive.
Pros.
✅ States are first-class logical theories — deductive reasoning comes for free.
✅ No closed-world assumption — explicit handling of unknowns.
✅ All three problems (Frame/Qualification/Ramification) can in principle be addressed by writing the right axioms.
Cons.
❌ Frame axiom explosion: roughly O(actions × fluents) axioms — the practical face of the frame problem.
❌ Performance can be a problem; verifying coverage is hard (slide: “difficult to guarantee that all cases are covered, and runtime may suffer”).
3. Ignore-PRE-DEL heuristic
Goal. Estimate the cost from state s to goal G by relaxing the planning problem: drop PRE and DEL of every operator. Each operator then “covers” some subset of the goal literals.
h_PRE-DEL(s, G): U ← G \ s # unsatisfied goal literals for each operator scheme o, each instantiation i: cover(o,i) ← ADD(o,i) ∩ U # goals this op would satisfy return MIN-SET-COVER({cover(o,i) | over all (o,i)}, U) # In practice: a polynomial-time GREEDY set-cover approximation.
⚠️ Greedy approximation may overestimate ⇒ NOT admissible ⇒ A* loses its optimality guarantee.
⚠️ Ignoring PRE makes the relaxation very loose — heuristic can be wildly off when preconditions are restrictive.
4. Ignore-DEL heuristic
Goal. Same idea, but only DEL is ignored. PRE still matters. In the relaxed world no action can ever undo a goal, so once a fact becomes true it stays true.
h_DEL(s, G): s* ← s repeat: for each applicable operator o (using ADD only, no DEL): s* ← s* ∪ ADD(o) until no new atoms are added or G ⊆ s* return length of (shortest) sequence of ops used to reach G (NP-hard) # In practice: polynomial-time approximation (e.g. h_max, h_add, h_FF).
Cost. Exact: NP-hard. Approximation: polynomial.
Pros.
✅ Tighter than Ignore-PRE-DEL — respects preconditions.
✅ Underpins the most successful classical planning heuristics in IPC (h_max, h_add, h_FF).
Cons.
⚠️ Approximation is NOT admissible ⇒ A* optimality not guaranteed.
Goal. Find a plan = sequence of operators leading from the initial state s₀ to a state satisfying the goal G.
CLASSICAL-PLAN(s₀, G, Operators, heuristic h): frontier ← priority queue ordered by f(n) = g(n) + h(n) push (s₀, [], 0) onto frontier closed ← {} while frontier not empty: (s, plan, g) ← frontier.pop() if G ⊆ s: # STRIPS goal test return plan # SUCCESS if s ∈ closed: continue closed.add(s) for each operator scheme o, each instantiation i: if PRE(o,i) ⊆ s: # applicable? s' ← (s \ DEL(o,i)) ∪ ADD(o,i) if s' ∉ closed: frontier.push((s', plan + [o,i], g + 1)) return FAILURE # no plan exists
Cost. Worst-case exponential in plan length; practical performance dominated by the heuristic h. The general planning decision problem is intractable (slide remark: “planning remains hard in general”; PSPACE-complete for grounded propositional STRIPS — R&N background, not in the lecture slides).
Pros.
✅ Reuses any classical search algorithm (BFS, DFS, A*, IDA*).
✅ Easy to plug different heuristics (Ignore-PRE-DEL, Ignore-DEL, h_FF, …).
✅ Same pattern works for backward search (start from G, apply operators in reverse).
Cons.
⚠️ Branching factor = number of applicable instantiated operators — can be huge.
⚠️ Uninformed search blows up immediately on realistic problems → heuristic quality is everything.
⚠️ Forward search may waste time on irrelevant actions; backward search may waste time on unreachable subgoals — neither dominates in general.
— Original atomic-note material below —
Kept verbatim from the pre-merge STRIPS hub — the runnable Python planner with visualisation, the historical “where STRIPS is used today” map, and the limitations/extensions tables.
Visualisations (Python)
Figures to make STRIPS concepts concrete. Each toggle renders in Obsidian’s Execute Code (Pyodide); the first install line is for the browser sandbox only.
🐍 Figure — Forward state-space search tree (Blocksworld, BFS) ⭐
import micropipawait micropip.install("matplotlib")import matplotlib.pyplot as pltfrom collections import deque, defaultdict# State = a set of stacks (each stack a tuple bottom->top). 3 blocks A, B, C.# A block can move if it is CLEAR (= the top of its stack), onto the table or# onto another clear block. This is the state-level view of STRIPS actions.def norm(stacks): return frozenset(stacks)INIT = norm([("A",), ("B",), ("C",)]) # all on the tableGOAL = norm([("C", "B", "A")]) # C on table, B on C, A on B -> "CBA"def successors(state): """Yield (action_label, new_state) for every legal single move.""" stacks = list(state) for i, s in enumerate(stacks): X = s[-1] # top block = clear = movable others = stacks[:i] + stacks[i+1:] src_rest = s[:-1] # source stack after removing X if len(s) > 1: # move X onto the table (skip no-op) new = list(others) + ([src_rest] if src_rest else []) + [(X,)] yield (f"{X}→table", norm(new)) for j, s2 in enumerate(others): # move X onto a clear block Y Y = s2[-1] new = [st for k, st in enumerate(others) if k != j] if src_rest: new.append(src_rest) new.append(s2 + (X,)) yield (f"{X}→{Y}", norm(new))# --- BFS forward search, recording the search tree ---parent = {INIT: None} # state -> (parent_state, action)depth = {INIT: 0}order = [INIT]q = deque([INIT])while q: st = q.popleft() for act, ns in successors(st): if ns not in parent: parent[ns] = (st, act); depth[ns] = depth[st] + 1 order.append(ns); q.append(ns)# --- solution path (backtrack from goal) ---path, node = set(), GOALwhile node is not None: path.add(node) node = parent[node][0] if parent.get(node) else Nonedef label(state): return " ".join(sorted("".join(s) for s in state))# --- layered layout: y = -depth, x spread per level ---levels = defaultdict(list)for st in order: levels[depth[st]].append(st)pos = {}for d, nodes in levels.items(): for i, st in enumerate(nodes): pos[st] = (i - (len(nodes) - 1) / 2, -d)fig, ax = plt.subplots(figsize=(13, 7))for st in order: # edges if parent[st]: ps, act = parent[st] (x1, y1), (x2, y2) = pos[ps], pos[st] on = st in path and ps in path ax.plot([x1, x2], [y1, y2], "-", color="#c0392b" if on else "#cfcfcf", lw=2.4 if on else 1.0, zorder=1) ax.text((x1 + x2) / 2, (y1 + y2) / 2, act, fontsize=6, color="#c0392b" if on else "#999", ha="center", va="center", bbox=dict(boxstyle="round,pad=0.1", fc="white", ec="none", alpha=0.75), zorder=2)for st in order: # nodes x, y = pos[st] fc = ("#2c3e50" if st == INIT else "#27ae60" if st == GOAL else "#f9e79f" if st in path else "#ecf0f1") tc = "white" if st in (INIT, GOAL) else "black" ax.text(x, y, label(st), fontsize=8, fontweight="bold", ha="center", va="center", bbox=dict(boxstyle="round,pad=0.3", fc=fc, ec="black", lw=1.2), zorder=3, color=tc)ax.set_title("Planning I — forward state-space search (Blocksworld, BFS)\n" "dark = initial state · green = goal · yellow = solution plan · grey = explored\n" "goal 'CBA' = C on table, B on C, A on B", fontsize=11)ax.axis("off"); plt.tight_layout(); plt.show()# --- print the extracted plan ---plan, node = [], GOALwhile parent.get(node): ps, act = parent[node]; plan.append(act); node = psplan.reverse()print(f"Explored {len(order)} states · PLAN ({len(plan)} steps): " + " → ".join(plan))
What this figure shows. Classical planning is search over world states. Every node is a complete Blocksworld configuration; every edge is one STRIPS action (move a clear block onto the table or onto another clear block). BFS expands the whole reachable space (13 states for 3 blocks) outward from the initial state (dark) until it reaches the goal (green); the yellow path is the extracted plan. This is exactly the “Planning via Classical Search” idea — the planner never executes, it searches the state graph for a path, then returns the action sequence. Swap GOAL or add a 4th block to watch the tree explode (the reason heuristics like Ignore-DEL exist).
import micropipawait micropip.install("matplotlib")import matplotlib.pyplot as pltimport matplotlib.patches as patches# Three states under a sequence of STRIPS actions on 4 blocks A, B, C, D.# The sequence:# put_on_table(D) -> put(B, A) -> put(C, B)# State = list of stacks (each stack is bottom -> top).states = [ ("Initial", [["A"], ["B"], ["C"], ["D"]]), ("After put(B,A) — B stacked on A", [["A", "B"], ["C"], ["D"]]), ("Goal — after put(C,B): C on B on A", [["A", "B", "C"], ["D"]]),]COLOURS = {"A": "#e74c3c", "B": "#3498db", "C": "#2ecc71", "D": "#f1c40f"}fig, axes = plt.subplots(1, 3, figsize=(12, 4.2))for ax, (title, stacks) in zip(axes, states): # table line ax.axhline(0, color="black", lw=2.5) # draw each stack for x_off, stack in enumerate(stacks): for h, block in enumerate(stack): ax.add_patch(patches.Rectangle( (x_off + 0.2, h), 0.6, 0.9, facecolor=COLOURS[block], edgecolor="black", lw=1.5)) ax.text(x_off + 0.5, h + 0.45, block, ha="center", va="center", fontsize=15, fontweight="bold", color="white") ax.set_xlim(-0.3, 4.5) ax.set_ylim(-0.3, 4) ax.set_title(title, fontsize=10) ax.set_xticks([]); ax.set_yticks([]) for spine in ax.spines.values(): spine.set_visible(False)plt.suptitle("STRIPS Blocksworld — state evolution under a 2-action plan", fontsize=13, fontweight="bold")plt.tight_layout(rect=[0, 0, 1, 0.94]); plt.show()
What this shows. Three Blocksworld states laid out as stacks of coloured blocks on a table. Each step applies one STRIPS operator. The visual makes the state-as-set-of-atoms idea concrete: in the rightmost panel, the atoms holding are {on(C,B), on(B,A), ontable(A), ontable(D), clear(C), clear(D)}. Everything else (including clear(A) and clear(B), which were true in the initial state) is false by the Closed-World Assumption — they are simply absent from the set.
🐍 Figure — BFS search tree on a tiny 3-block Blocksworld
import micropipawait micropip.install("matplotlib")from collections import dequeimport matplotlib.pyplot as plt# Tiny domain: 3 blocks A, B, C, robot arm. Encode atoms as a frozenset of strings.# Operators: pickup(X), putdown(X), stack(X,Y), unstack(X,Y) — classic Blocksworld.BLOCKS = ["A", "B", "C"]def ops(blocks): out = [] for x in blocks: out.append(("pickup(%s)" % x, {f"Clear({x})", f"OnTable({x})", "HandEmpty"}, {f"Holding({x})"}, {f"OnTable({x})", f"Clear({x})", "HandEmpty"})) out.append(("putdown(%s)" % x, {f"Holding({x})"}, {f"OnTable({x})", f"Clear({x})", "HandEmpty"}, {f"Holding({x})"})) for y in blocks: if x == y: continue out.append((f"stack({x},{y})", {f"Holding({x})", f"Clear({y})"}, {f"On({x},{y})", f"Clear({x})", "HandEmpty"}, {f"Holding({x})", f"Clear({y})"})) out.append((f"unstack({x},{y})", {f"On({x},{y})", f"Clear({x})", "HandEmpty"}, {f"Holding({x})", f"Clear({y})"}, {f"On({x},{y})", f"Clear({x})", "HandEmpty"})) return outOPS = ops(BLOCKS)def apply(state, op): _, pre, add, dele = op if not pre.issubset(state): return None return frozenset((state - dele) | add)# Initial: all on table. Goal: On(A,B) — minimal, gives a small tree.initial = frozenset({"OnTable(A)", "OnTable(B)", "OnTable(C)", "Clear(A)", "Clear(B)", "Clear(C)", "HandEmpty"})goal = {"On(A,B)"}# BFS recording (parent, action) for each state. Cap to keep tree small.parent = {initial: (None, None)}order = [initial] # discovery ordergoal_state = Nonequeue = deque([initial])MAX_STATES = 12while queue and len(order) < MAX_STATES: s = queue.popleft() if goal.issubset(s): goal_state = s; break for op in OPS: s2 = apply(s, op) if s2 is None or s2 in parent: continue parent[s2] = (s, op[0]) order.append(s2); queue.append(s2) if goal.issubset(s2): goal_state = s2# Compact state label: stacks + helddef label(state): held = [b for b in BLOCKS if f"Holding({b})" in state] on = {b: y for b in BLOCKS for y in BLOCKS if f"On({b},{y})" in state} table = [b for b in BLOCKS if f"OnTable({b})" in state] stacks = [] for bot in sorted(table): st = [bot] while True: above = [b for b, y in on.items() if y == st[-1]] if not above: break st.append(above[0]) stacks.append("-".join(st)) parts = [] if stacks: parts.append(",".join(stacks)) if held: parts.append(f"hold:{held[0]}") return "\n".join(parts) if parts else "∅"# Compute depths + layoutdepth = {initial: 0}children = {s: [] for s in order}for s in order: p, _ = parent[s] if p is not None: depth[s] = depth[p] + 1 children[p].append(s)# Layered layout: assign x by in-order traversal of subtree leaf positionspos = {}counter = [0]def visit(s): if not children[s]: pos[s] = (counter[0], -depth[s]); counter[0] += 1; return xs = [] for c in children[s]: visit(c); xs.append(pos[c][0]) pos[s] = ((min(xs) + max(xs)) / 2, -depth[s])visit(initial)# Path from initial to goal_statepath = set()if goal_state is not None: cur = goal_state while cur is not None: path.add(cur); cur = parent[cur][0]fig, ax = plt.subplots(figsize=(13, 7))for s in order: p, act = parent[s] if p is None: continue x1, y1 = pos[p]; x2, y2 = pos[s] on_path = s in path and p in path ax.plot([x1, x2], [y1, y2], color="#27ae60" if on_path else "#bbb", lw=2.4 if on_path else 1, zorder=1) ax.text((x1+x2)/2, (y1+y2)/2, act, fontsize=6, ha="center", va="center", color="#333", bbox=dict(boxstyle="round,pad=0.1", fc="white", ec="none", alpha=0.85))for s in order: x, y = pos[s] is_goal = s == goal_state on_path = s in path fc = "#2ecc71" if is_goal else ("#aed6f1" if on_path else "#ecf0f1") ec = "#27ae60" if on_path else "#7f8c8d" lw = 2 if on_path else 0.8 ax.text(x, y, label(s), ha="center", va="center", fontsize=7, bbox=dict(boxstyle="round,pad=0.3", fc=fc, ec=ec, lw=lw), zorder=3)ax.set_title(f"BFS state-space tree — tiny Blocksworld (3 blocks)\n" f"Goal: On(A,B) · {len(order)} states explored · path highlighted in green", fontsize=11)ax.axis("off")plt.tight_layout(); plt.show()
What this shows. A real BFS expansion of the STRIPS state space, capped at 12 states for legibility. Each node is one state (compactly labelled by its stacks + the held block); each edge is one ground operator that takes you from parent to child. The green path is the shortest plan BFS found to reach On(A,B) — typically pickup(A) → stack(A,B). The grey siblings are alternative states BFS also generated but didn’t need. This is exactly what CLASSICAL-PLAN (algorithm 5 above) does internally — with a heuristic, A* would prune most of the grey nodes.
🐍 Figure — STRIPS operator semantics: BEFORE → PRE/DEL/ADD → AFTER
import micropipawait micropip.install("matplotlib")import matplotlib.pyplot as pltimport matplotlib.patches as patches# Action: put(A, B) --- restack A onto B (assumes A was on table, both clear)# PRE: {ontable(A), clear(A), clear(B)}# ADD: {on(A,B)}# DEL: {ontable(A), clear(B)}before = {"ontable(A)", "ontable(B)", "ontable(C)", "clear(A)", "clear(B)", "clear(C)"}pre = {"ontable(A)", "clear(A)", "clear(B)"}dele = {"ontable(A)", "clear(B)"}add = {"on(A,B)"}after = (before - dele) | addCOLOURS = {"A": "#e74c3c", "B": "#3498db", "C": "#2ecc71"}def draw_stacks(ax, state, title): ax.axhline(0, color="black", lw=2.5) # Build stacks on_table = [b for b in ["A", "B", "C"] if f"ontable({b})" in state] on = {b: y for b in ["A", "B", "C"] for y in ["A", "B", "C"] if f"on({b},{y})" in state} for x_off, bot in enumerate(sorted(on_table)): stack = [bot] while True: above = [b for b, y in on.items() if y == stack[-1]] if not above: break stack.append(above[0]) for h, block in enumerate(stack): ax.add_patch(patches.Rectangle( (x_off + 0.2, h), 0.6, 0.9, facecolor=COLOURS[block], edgecolor="black", lw=1.5)) ax.text(x_off + 0.5, h + 0.45, block, ha="center", va="center", fontsize=14, fontweight="bold", color="white") ax.set_xlim(-0.3, 4); ax.set_ylim(-0.3, 3.5) ax.set_title(title, fontsize=11, fontweight="bold") ax.set_xticks([]); ax.set_yticks([]) for sp in ax.spines.values(): sp.set_visible(False)def draw_atoms(ax, atoms, title, colour, check_against=None): ax.set_title(title, fontsize=10, fontweight="bold", color=colour) ax.axis("off") for i, atom in enumerate(sorted(atoms)): mark = "" if check_against is not None: mark = " ✓" if atom in check_against else " ✗" ax.text(0.05, 0.85 - i * 0.18, f"• {atom}{mark}", transform=ax.transAxes, fontsize=11, family="monospace", color=colour)fig = plt.figure(figsize=(15, 6))gs = fig.add_gridspec(2, 5, height_ratios=[1, 1.1], hspace=0.4, wspace=0.35)# Top row: BEFORE state | PRE check | DEL list | ADD list | AFTER stateax_b = fig.add_subplot(gs[0, 0]); draw_stacks(ax_b, before, "BEFORE state")ax_pre = fig.add_subplot(gs[0, 1])draw_atoms(ax_pre, pre, "PRE — must hold", "#16a085", check_against=before)ax_del = fig.add_subplot(gs[0, 2])draw_atoms(ax_del, dele, "DEL — remove these", "#c0392b")ax_add = fig.add_subplot(gs[0, 3])draw_atoms(ax_add, add, "ADD — add these", "#2980b9")ax_a = fig.add_subplot(gs[0, 4]); draw_stacks(ax_a, after, "AFTER state")# Bottom row: full atom set BEFORE and AFTER for comparisonax_sb = fig.add_subplot(gs[1, :2])draw_atoms(ax_sb, before, "BEFORE — full atom set (CWA: all else is false)", "#2c3e50")ax_sa = fig.add_subplot(gs[1, 3:])draw_atoms(ax_sa, after, "AFTER — full atom set", "#2c3e50")# Centre arrow with actionax_arrow = fig.add_subplot(gs[1, 2]); ax_arrow.axis("off")ax_arrow.annotate("", xy=(0.95, 0.5), xytext=(0.05, 0.5), xycoords="axes fraction", arrowprops=dict(arrowstyle="->", lw=2.5, color="#34495e"))ax_arrow.text(0.5, 0.7, "put(A, B)", ha="center", fontsize=13, fontweight="bold", color="#34495e", transform=ax_arrow.transAxes)ax_arrow.text(0.5, 0.3, "s' = (s \\ DEL) ∪ ADD", ha="center", fontsize=10, family="monospace", color="#7f8c8d", transform=ax_arrow.transAxes)fig.suptitle("STRIPS operator put(A, B) — PRE check, DEL/ADD application, state transition", fontsize=13, fontweight="bold")plt.show()
What this shows. A single STRIPS operator dissected side-by-side. BEFORE: three blocks on the table; the atom set is shown bottom-left. PRE (green) lists the atoms that must hold for put(A,B) to be applicable — each is checked against the BEFORE set with a ✓. DEL (red) removes ontable(A) and clear(B). ADD (blue) adds on(A,B). The state-update rule s' = (s \ DEL) ∪ ADD is applied — note the order: delete first, then add. AFTER: A now sits on B; the new atom set on the bottom-right confirms on(A,B) is in and the deleted atoms are gone. Anything not mentioned in ADD/DEL (e.g. ontable(C), clear(C)) is unchanged automatically — that is the Frame Convention STRIPS uses to “solve” the frame problem.
Worked Blocksworld example (Python planner)
The canonical STRIPS domain. Blocks on a table; a robot arm picks them up and stacks them.
See it in code — tiny STRIPS planner with forward BFS
🐍 Code anzeigen / ausblenden
# Pyodide / Obsidian Execute Code: install matplotlib first.# In normal Python (terminal / Jupyter), delete the next 2 lines.import micropipawait micropip.install("matplotlib")from collections import dequeimport matplotlib.pyplot as pltimport matplotlib.patches as patches# --- Operator schema: PRE / ADD / DEL ---def operator(name, pre, add, dele): return {'name': name, 'pre': set(pre), 'add': set(add), 'del': set(dele)}def ground_blocksworld_ops(blocks): """Generate ground operators for the given blocks.""" ops = [] for x in blocks: ops.append(operator(f'pickup({x})', pre={f'Clear({x})', f'OnTable({x})', 'HandEmpty'}, add={f'Holding({x})'}, dele={f'OnTable({x})', f'Clear({x})', 'HandEmpty'})) ops.append(operator(f'putdown({x})', pre={f'Holding({x})'}, add={f'OnTable({x})', f'Clear({x})', 'HandEmpty'}, dele={f'Holding({x})'})) for y in blocks: if x == y: continue ops.append(operator(f'stack({x},{y})', pre={f'Holding({x})', f'Clear({y})'}, add={f'On({x},{y})', f'Clear({x})', 'HandEmpty'}, dele={f'Holding({x})', f'Clear({y})'})) ops.append(operator(f'unstack({x},{y})', pre={f'On({x},{y})', f'Clear({x})', 'HandEmpty'}, add={f'Holding({x})', f'Clear({y})'}, dele={f'On({x},{y})', f'Clear({x})', 'HandEmpty'})) return opsdef apply_op(state, op): """Apply STRIPS operator if PRE holds. Returns new state or None.""" if not op['pre'].issubset(state): return None return (state - op['del']) | op['add']def forward_search(initial, goal, ops, max_depth=10): """BFS over states until goal atoms are subset of state.""" queue = deque([(initial, [])]) seen = {frozenset(initial)} while queue: state, plan = queue.popleft() if goal.issubset(state): return plan, state if len(plan) >= max_depth: continue for op in ops: new_state = apply_op(state, op) if new_state is not None and frozenset(new_state) not in seen: seen.add(frozenset(new_state)) queue.append((new_state, plan + [op['name']])) return None, None# --- Solve a Blocksworld instance ---blocks = ['A', 'B', 'C']initial = {'OnTable(A)', 'On(B,A)', 'OnTable(C)', 'Clear(B)', 'Clear(C)', 'HandEmpty'}goal = {'On(A,B)', 'On(B,C)'}plan, final_state = forward_search(initial, goal, ground_blocksworld_ops(blocks))print("PLAN:")for i, action in enumerate(plan, 1): print(f" {i}. {action}")print(f"\nFinal state contains goal: {goal.issubset(final_state)}")# --- Trace + visualize each state ---def state_to_stacks(state, blocks): """Convert atom set to a list of stacks (lists of block names, bottom-up).""" on_table = {b for b in blocks if f'OnTable({b})' in state} on = {b: nxt for b in blocks for nxt in blocks if f'On({b},{nxt})' in state} # Build stacks stacks = [] for bottom in on_table: stack = [bottom] # Find what's on top of the current top while True: top = stack[-1] above = [b for b, n in on.items() if n == top] if not above: break stack.append(above[0]) stacks.append(stack) held = [b for b in blocks if f'Holding({b})' in state] return stacks, held# Replay the plan and collect statesstates = [initial]state = initialfor action in plan: op = next(o for o in ground_blocksworld_ops(blocks) if o['name'] == action) state = apply_op(state, op) states.append(state)# Plot the stacks at each stepfig, axes = plt.subplots(1, len(states), figsize=(2.5 * len(states), 4))colors = {'A': '#e74c3c', 'B': '#3498db', 'C': '#2ecc71'}for ax, s, label in zip(axes, states, ['Initial'] + plan): stacks, held = state_to_stacks(s, blocks) # Draw table line ax.axhline(0, color='black', lw=2) # Draw stacks for x_offset, stack in enumerate(stacks): for h, block in enumerate(stack): ax.add_patch(patches.Rectangle((x_offset + 0.2, h), 0.6, 0.9, facecolor=colors[block], edgecolor='black')) ax.text(x_offset + 0.5, h + 0.45, block, ha='center', va='center', fontsize=14, fontweight='bold', color='white') # Draw held block if held: b = held[0] ax.add_patch(patches.Rectangle((len(blocks) + 0.2, 3), 0.6, 0.9, facecolor=colors[b], edgecolor='black')) ax.text(len(blocks) + 0.5, 3.45, b, ha='center', va='center', fontsize=14, fontweight='bold', color='white') ax.text(len(blocks) + 0.5, 2.7, '✋', ha='center', fontsize=14) ax.set_xlim(-0.5, len(blocks) + 1.5); ax.set_ylim(-0.3, 5) ax.set_title(label, fontsize=10) ax.set_xticks([]); ax.set_yticks([])plt.suptitle(f'STRIPS Blocksworld plan ({len(plan)} steps)', fontsize=14)plt.tight_layout(); plt.show()
What you’ll see:
The planner finds a multi-step sequence like unstack(B,A), putdown(B), pickup(B), stack(B,C), pickup(A), stack(A,B).
The plot shows each intermediate state — blocks on the table, blocks being held (✋), blocks stacked.
The plan is optimal (BFS finds the shortest one). For larger problems you’d use heuristic search (FF, LAMA, Fast Downward) instead of BFS.
Forward vs. backward search
Direction
How it works
When to prefer
Forward (progression)
Start at I, apply operators, search forward until G holds
Small initial state, large goal
Backward (regression)
Start at G, find operators whose ADD list contains goal atoms, regress through PRE
Small goal, large initial state
Modern planners use heuristic forward search with relaxation-based heuristics (ignore DEL → Ignore-Delete heuristic; ignore PRE → Ignore-Precondition).
Limitations of pure STRIPS
❌ No types or numeric fluents — everything is binary atoms (PDDL adds these)
❌ No disjunctive preconditions (e.g. “X is red OR blue”)
❌ No conditional effects (e.g. “if X is metal, then add Magnetized(X)”)
❌ No temporal reasoning (durative actions, deadlines)
❌ Deterministic only — no probabilities
PDDL extensions
Each limitation is addressed by some PDDL extension:
Extension
Adds
PDDL 1.2 (1998)
Types, equality, basic STRIPS
PDDL 2.1 (2002)
Numeric fluents, durative actions, plan metrics
PDDL 2.2
Derived predicates, timed initial literals
PDDL 3.0
Preferences, constraints, hard/soft goals
PPDDL
Probabilistic effects (for MDP-style problems)
Where STRIPS-style planning is used today
PDDL planners (Fast Downward, LAMA, FF, Pyperplan) — all use STRIPS internals + heuristics. Used in academic and industrial planning.
International Planning Competition (IPC) — since 1998, runs benchmarks on STRIPS-derived domains
NASA mission planning — Mars rovers (Spirit, Opportunity, Curiosity) use derivatives of STRIPS for daily activity scheduling (ASPEN/Casper systems)
Video game AI — F.E.A.R. (2005) famously used GOAP (Goal-Oriented Action Planning), a STRIPS-derived system. Modern game AI systems (HTN planners, behavior trees) trace back to STRIPS.
Manufacturing assembly planning — automotive assembly lines use STRIPS-derived planners
STRIPS is symbolic; continuous spaces need geometric reasoning
Long-horizon robotic tasks with perception
LLM-based planning agents (ReAct, AutoGPT, Devin)
LLMs handle qualification problem better, replan when preconditions fail
Task-and-motion planning
PDDLStream, hybrid TAMP systems
Combine symbolic STRIPS with geometric/continuous reasoning
Game AI (modern)
Behavior trees, utility AI, neural policies
Behavior trees are easier to author by game designers
Where STRIPS still wins: when (a) the domain is genuinely symbolic and discrete, (b) you need a guaranteed-optimal plan, (c) you need explanations (every action’s preconditions are explicit), and (d) the world is deterministic enough to model with binary atoms.
See also
PDDL and STRIPS — the combined original note (PDDL details there)
Frame Problem — the central challenge STRIPS sidesteps