Compiling Causal Theories into Successor State Axioms

16 concepts9 papers1 proposal

When building intelligent agents, engineers face a fundamental dilemma in knowledge representation. On one hand, humans prefer to specify the physics of an environment using high-level, intuitive causal rules (e.g., "flipping the switch turns on the light"). On the other hand, automated planners and reasoning engines require low-level, computationally efficient operational models that explicitly state exactly what changes—and what stays the same—after every possible action.

Bridging this gap requires solving the notorious ramification problem: accounting for all the indirect side effects of an action without manually enumerating them. For instance, if an action moves a truck, it indirectly moves everything inside the truck.

A powerful line of research addresses this by automatically compiling high-level causal theories into Successor State Axioms (SSAs) within classical logic formalisms like the situation calculus. This compilation process allows developers to write clean, declarative world models while giving automated systems the precise, loop-free formulas they need to compute state transitions efficiently.


The Target: Successor State Axioms and Explanation Closure

To understand why we compile causal theories, we must first understand the ideal target representation. In complex environments, tracking what does not change (the frame problem) is as difficult as tracking what does. Successor State Axioms solve this by consolidating all direct and indirect effects into a single, bidirectional logical formula for each state variable (or fluent).

An SSA takes the following conceptual form: $$\text{Fluent is True tomorrow} \iff \text{An action made it true} \lor (\text{It was already true} \land \text{No action made it false})$$

The core mechanism that makes this compilation possible is the principle of explanation closure. As shown by Sheila A. McIlraith in the context of model-based diagnosis, explanation closure assumes that any observed change in a system's state must be the result of a known action or a strictly defined indirect ramification. By integrating state constraints directly into this closure procedure, McIlraith demonstrated that complex dynamic systems could automatically generate SSAs, eliminating the need for engineers to manually predict every failure mode or side effect.


The Mechanics of Causal Completion

How does a compiler transform a raw set of causal laws into these clean, bidirectional axioms? The process relies on treating domain constraints not as static logical implications, but as directional causal forces.

If we represent a domain constraint as a standard logical implication, such as $\text{Alarm} \leftarrow \text{WireCut}$, standard logic allows the contrapositive: $\neg\text{WireCut} \leftarrow \neg\text{Alarm}$. This causes paradoxes in action languages, where preventing an alarm might magically undo a physical action like cutting a wire. Early action languages, such as Language C introduced in An Action Language Based on Causal Explanation: Preliminary Report, solved this by establishing a dedicated syntax for "causally explained" transitions, ensuring that causes strictly propagate forward to their effects.

Building on this directional intuition, Fangzhen Lin developed automated compilation procedures that compute the strongest necessary and weakest sufficient conditions for a fluent to change.

[ High-Level Causal Rules ] (e.g., Action A causes X; X causes Y)
            │
            ▼
[ Causal Completion / Quantifier Elimination ] 
            │
            ▼
[ Successor State Axioms ] (Consolidated, loop-free classical logic)
            │
            ▼
[ Operational Formats ] (e.g., STRIPS Add/Delete Lists for fast planning)

As detailed in Compiling Causal Theories to Successor State Axioms and STRIPS-Like Systems, the compiler ingests high-level rules describing how conditions force specific effects. It then performs a "Causal Completion Procedure"—mathematically isolating the fluents and eliminating intermediate quantifiers. This automatically resolves the ramification problem by tracing how updates propagate through physical dependencies. The resulting SSAs can then be stripped down into standard "add/delete" lists, allowing high-performance, low-level planning systems like STRIPS to run on domains specified from first principles (Fangzhen Lin).


Overcoming Loops and Nonmonotonicity

Real-world domains are rarely simple, linear chains of cause and effect; they often contain cyclic dependencies (e.g., two interconnected valves where the status of each depends on the other). Simple completion procedures fail in the presence of these loops because they can create self-justifying circular logic.

To resolve this, Lin et al. introduced a double minimization technique using circumscription within the situation calculus. By applying a second layer of logical minimization, the compiler can unroll cyclic dependencies, isolating the true external triggers from the internal feedback loops. This allows even loopy, complex causal side-effects to be compiled into standard, computationally efficient SSAs.

To ensure these translations remain mathematically sound when variables are involved, Lifschitz et al. mapped the semantics of action descriptions to classical second-order logic. This foundational mapping guarantees that every state change derived by the compiled theory is explicitly justified by an underlying causal law, preventing arbitrary or uncaused state fluctuations.

Bridging Logic Programming and SAT Solvers

This compilation paradigm also provides a vital bridge between different AI programming traditions. For instance, Answer Set Programming (ASP) is highly expressive and naturally handles the law of inertia, but its stable model semantics can be computationally heavy.

Vladimir Lifschitz proved that under a structural property called $\Gamma$-tightness, the complex stable model semantics of a logic program become perfectly equivalent to a much simpler program completion (Vladimir Lifschitz). This allows ASP-style action descriptions to be compiled directly into standard first-order logic SSAs.

At the lowest level of computation, Alexander Bochman demonstrated that these nonmonotonic causal theories can be reduced to determinate theories consisting entirely of Horn rules (Alexander Bochman). Because Horn rules preserve the essential nonmonotonic semantics while stripping away logical complexity, this reduction allows modern, lightning-fast classical SAT solvers to efficiently compute the consequences of high-level causal systems.


Applications: From Planning to Actual Causality

Once a high-level causal theory has been successfully compiled into Successor State Axioms, the practical benefits extend far beyond fast planning. Because SSAs explicitly map out the exact conditions under which properties change over time, they create a transparent, traceable history of a system's execution.

This explicit temporal tracing is precisely what makes the framework ideal for diagnosing responsibility. Batusov et al. leveraged this capability to formalize actual causality—the task of identifying the specific event that triggered an outcome within a narrative.

In their framework, a causal link is established when an action triggers a transition in an SSA's truth value from false to true, and that value remains stable until the end of the sequence. Because the underlying rules were compiled cleanly, this logic-based approach can handle complex timing, overlapping actions, and dynamic state transitions that traditional, static structural equation models struggle to capture.

Key Foundational Work

Representing Actions and State Constraints in Model-Based Diagnosis (1997) — contributed 1 concept elements to this direction.
An Action Language Based on Causal Explanation: Preliminary Report (1998) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 9 papers
  2. Version 1 · 2026-10-04 · 9 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_causal_rule_compilation_c1bcac41,
  title = {causal rule compilation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/causal-rule-compilation/rdr_c1bcac41cd1d4853aef09d62079b6d98},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_causal_rule_compilation_c1bcac41_v2,
  title = {causal rule compilation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/causal-rule-compilation/rdr_c1bcac41cd1d4853aef09d62079b6d98/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake