Situation Calculus

methods-of-ai

Situation Calculus (McCarthy & Hayes, 1969) is a logical formalism for reasoning about actions and their effects in dynamic worlds. It’s the alternative to STRIPS-style planning: instead of representing states as sets of atoms and modifying them imperatively, Situation Calculus models time as a sequence of situations connected by actions, all inside First-Order Logic.

It’s the theoretical foundation of AI planning. STRIPS / PDDL are what you actually use in practice; Situation Calculus is what you learn for the exam to understand why STRIPS exists.

The three building blocks

1. Situations

Situations are terms (not states) that represent snapshots of the world at a point in time:

S₀ — the initial situation (a constant)
do(a, s) — the situation that results from performing action a in situation s

So do(put(A, B), do(pickup(A), S₀)) denotes the situation: from the start, pick up A, then put A on B.

2. Fluents

Fluents are predicates or functions whose truth value can change across situations. The situation is passed as an extra argument:

On(A, B, s) — “A is on B in situation s”
Clear(x, s) — “x has nothing on top of it in situation s”

Contrast with rigid predicates (don’t change over time): Block(A), Color(red).

3. Axioms

Action precondition axiom — when an action is possible:
Poss(pickup(x), s) ↔ Clear(x, s) ∧ HandEmpty(s)
Effect axiom — what becomes true after an action:
Poss(pickup(x), s) → Holding(x, do(pickup(x), s))
Frame axiom — what stays the same after an action:
Color(x, c, s) → Color(x, c, do(a, s)) for every (action × fluent) pair that doesn’t change

⚠️ The Frame Problem in living color

Effect axioms are easy. Frame axioms are a nightmare: if you have n actions and m fluents, you potentially need O(n · m) frame axioms — one per (action, fluent) pair that doesn’t change.

Example: 5 actions, 10 fluents → up to 50 frame axioms, each something like “moving block A doesn’t change the color of block B.” Practically impossible at scale.

Two famous “fixes”:

Fix	Idea	Limitation
Reiter’s Successor State Axiom (1991)	Combine all positive + negative effects on a fluent into one biconditional	Elegant; standard textbook solution; still requires explicit specification per fluent
STRIPS’ closed-world assumption	”Anything not in the ADD or DEL list of an action is unchanged”	Sidesteps frame axioms syntactically — but ontological problem remains (see Frame Problem)

This is the whole reason STRIPS exists: trading some logical generality for practical tractability.

Worked mini-example

The blocks world. Initial situation S₀: A on table, B on table, C on A.

Fluents at S₀:
  OnTable(A, S₀), OnTable(B, S₀), On(C, A, S₀)
  Clear(B, S₀), Clear(C, S₀), HandEmpty(S₀)

Action: pickup(C)
  Preconditions: Clear(C, S₀) ∧ HandEmpty(S₀)  → satisfied
  Effects in do(pickup(C), S₀):
    Holding(C), Clear(A) become true
    HandEmpty, Clear(C), On(C, A) become false
  Frame (must be axiomatized):
    OnTable(A, do(pickup(C), S₀)),  OnTable(B, do(pickup(C), S₀))

To plan “stack C on B,” you do logical deduction: find a sequence of actions a₁, a₂, … such that the goal On(C, B, do(aₙ, do(aₙ₋₁, …, S₀))) is entailed by the axioms.