Situation Calculus Semantics for Actual Causality

Vitaliy Batusov, Mikhail SoutchanskiAAAI 2018 · DOI

Introduction

In the fields of artificial intelligence and philosophy, the study of "actual causality"—also known as token-level causality—seeks to identify the specific events that caused a particular outcome in a given scenario. A classic example is determining whether a forest fire was caused by an arsonist’s match or a lightning strike in a specific instance where both occurred.

For years, the dominant framework for analyzing these questions has been the Halpern-Pearl (HP) approach, which utilizes structural equations. However, while effective for simple scenarios, the HP framework faces significant challenges when applied to complex, dynamic environments. This paper proposes a shift in perspective, moving the study of actual causality out of the limited world of propositional logic and into the expressive realm of Situation Calculus (SC). By modeling causality through first-order logic and action sequences, the authors provide a more intuitive and robust way to handle timing, relationships, and change.

The Limitations of Structural Equation Models

The authors identify several "ailments" inherent in standard structural equation models (SEMs):

  1. Low Expressivity: SEMs are essentially propositional. They struggle to represent objects, complex relationships, or the passage of time without becoming unwieldy.
  2. Subjective Contingencies: To handle "preemption"—where one potential cause beats another to the punch—the HP approach requires researchers to select specific "possible worlds" or contingencies. This process often feels arbitrary and lacks a formal grounding in the domain's physics.
  3. Coarseness: These models often fail to distinguish between a persisting condition (e.g., the presence of oxygen) and a transitional event (e.g., striking a match), both of which might be necessary for an outcome but play different causal roles.

Methodology: Situation Calculus and Achievement Chains

To address these issues, the authors leverage Situation Calculus, a logic-based language designed to represent change through "situations" (sequences of actions) and "fluents" (properties that change over time). The core of their methodology rests on two pillars:

Successor State Axioms (SSAs)

Instead of static equations, the authors use SSAs to describe exactly how an action changes the world. This allows the model to capture the underlying dynamics of a system rather than just correlations between variables.

The Achievement Condition and Regression

The authors define a cause as an action that triggers a change in a formula's truth value—specifically, making a false formula true such that it remains true until the end of the narrative. To identify these actions, they employ a standard SC tool called regression. By looking backward from an effect and recursively applying regression, the framework uncovers an "Achievement Causal Chain": a sequence of actions that were both necessary and sufficient to bring about the final state.

Benchmarking Intuition

As a theoretical logic paper, the work evaluates its definitions against classic "intuition benchmarks" in causality research:

  • The Assassin: In a scenario where one assassin poisons a drink and a second assassin's backup plan is rendered moot, SC correctly identifies the first assassin as the cause. Unlike the HP approach, SC achieves this naturally by analyzing the actual sequence of events, without needing to invent complex contingencies.
  • The Switch: In this paradox, an engineer flips a switch to divert a train, but the train reaches its destination regardless of the path. SC correctly identifies that flipping the switch is not a cause of the arrival if the arrival was already guaranteed by the track's topology.
  • Blocks World: To demonstrate the power of first-order logic, the authors use a scenario involving an infinite chain of blocks. This allows them to perform quantified causal queries (e.g., "Did any move action cause the tower to be clear?"), a task impossible for propositional SEMs.

Key Results and Theoretical Contributions

The paper provides a formal bridge between logic-based AI and structural causality. Two major theorems prove that the SC-based definition is equivalent to the most recent "modified" HP definition ($HP^m$) when applied to simple domains. This suggests that SC is not just an alternative, but a more expressive generalization of existing causal theories.

Furthermore, the SC approach exhibits elaboration tolerance. If new details are added to a story (such as a third assassin), the SC axioms do not require a total rewrite, whereas structural equations often must be completely restructured to accommodate new variables.

Limitations and Future Directions

While the paper marks a significant advancement, it focuses primarily on achievement causes—actions that make something happen. It does not yet deeply explore maintenance causes, which are actions that prevent a state from failing. Additionally, building a "Basic Action Theory" in Situation Calculus is more labor-intensive than writing structural equations, as it requires a formalization of the domain's physics.

Finally, while reasoning in first-order logic is generally undecidable, the authors note that for specific "narratives" (fixed sequences of actions), the computational complexity remains manageable, often scaling linearly with the length of the narrative. Future work will likely focus on extending these semantics to broader classes of causal reasoning and automated discovery of action theories.

Summary updated

BibTeX
@inproceedings{batusov2018situation,
  author = {Vitaliy Batusov and Mikhail Soutchanski},
  title = {{Situation Calculus Semantics for Actual Causality}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11561},
}
Figure