Events, Time, and the Situation Calculus

Representing Time and Change

The world changes over time. We need FOL representations that capture: 1. Properties that hold at specific times 2. Actions that cause changes 3. What persists (frame axioms)

The Situation Calculus

A formalism for reasoning about actions and their effects.

Key Terms

Situation: a “snapshot” of the world — the result of a sequence of actions from an initial state
S₀: the initial situation
Result(a, s): the situation resulting from performing action a in situation s
Fluent: a condition that can change between situations — written F(s) or F(x, s)

Example Axioms

-- Fluent: whether John has a book in situation s
Has(John, Book1, S₀)

-- Effect of Give action
∀x,y,o,s Has(x,o,s) ∧ At(y,s) → Has(y,o,Result(Give(x,y,o),s))

-- Successor-state axiom (handles frame problem)
∀x,o,s Has(x,o,Result(a,s)) ↔
    (∃y a=Give(y,x,o) ∨ Has(x,o,s) ∧ ¬∃y a=Give(x,y,o))

The successor-state axiom combines effect axioms + frame axioms: an object is possessed after action a iff either the action gave it, or it was possessed before and not given away.

The Frame Problem

Problem: if the world has 1000 fluents and 100 actions, you need 99,000 frame axioms (“action X doesn’t change fluent Y”) just to say what stays the same.

Solution: Successor-state axioms (Reiter’s solution): - One axiom per fluent: “fluent F holds in Result(a,s) iff action a caused F, OR F held in s and a didn’t prevent F” - Replaces 99,000 frame axioms with 1000 successor-state axioms

The Event Calculus

An alternative to situation calculus for continuous time and concurrent events.

Key Predicates

Predicate	Meaning
`Happens(e, t)`	Event e occurs at time t
`HoldsAt(f, t)`	Fluent f is true at time t
`Initiates(e, f, t)`	Event e initiates fluent f at t
`Terminates(e, f, t)`	Event e terminates fluent f at t
`Clipped(t1, f, t2)`	Fluent f was terminated between t1 and t2

Core Axiom

HoldsAt(f, t) ↔
    ∃e,t1 Happens(e,t1) ∧ t1<t ∧ Initiates(e,f,t1) ∧ ¬Clipped(t1,f,t)

Clipped(t1,f,t2) ↔
    ∃e,t Happens(e,t) ∧ t1<t<t2 ∧ Terminates(e,f,t)

Event calculus supports: - Concurrent events - Continuous quantities (volume, temperature) - Non-deterministic timing

Processes (Activities)

Some events are processes (extended in time) rather than instantaneous:

LiftingA(Person, Object): starts at t1, ends at t2, object in air during [t1,t2]

Distinguished from actions (point events) via:

Process(e): ∃t1,t2 StartsAt(e,t1) ∧ EndsAt(e,t2) ∧ t1<t2

Mental Objects and Beliefs

FOL can represent an agent’s beliefs using modal operators lifted into predicates:

Believes(John, King(Richard))
Knows(Mary, ¬Alive(Wumpus))

Problem: referential opacity — Believes(John, ==(Morning_Star, Evening_Star)) ≠ Believes(John, ==(Venus, Venus)) even though Morning_Star = Evening_Star = Venus.

Solution: quote the formula (treat it as an object), not evaluate it.

Summary

Situation calculus and event calculus are the canonical FOL frameworks for reasoning about change: - Situation calculus: discrete actions/situations, successor-state axioms solve frame problem - Event calculus: continuous time, concurrent events, better for temporal reasoning - Both remain active in formal verification and automated planning (Ch.11)