From Actions to Programs as Abstract Actual Causes

Bita Banihashemi, Shakil M. Khan, Mikhail SoutchanskiAAAI 2022 · DOI

Introduction

In the fields of artificial intelligence and formal verification, the study of "actual causation" (also known as token causation) seeks to answer a fundamental question: given a specific sequence of events that resulted in an outcome, which specific events are responsible for that outcome? While traditional causal frameworks, largely influenced by the work of Judea Pearl and Joseph Halpern, have focused on discrete, primitive events, modern autonomous systems operate through complex control flows. These systems are governed by programs containing loops, branches, and non-deterministic choices.

This paper extends the theory of actual causation from simple actions to complex, non-deterministic programs. By leveraging the Situation Calculus and a robust abstraction framework, the authors provide a method to identify programs as "weak potential causes," allowing for causal reasoning at high levels of abstraction rather than through the computationally expensive analysis of low-level implementation details.

The Challenge of Programmatic Causality

Identifying causation in software-heavy systems presents unique challenges. Unlike a single physical action, a program is often non-deterministic; one execution path might lead to a desired (or undesired) effect, while another path within the same program might not. For instance, if a rescue robot fails a mission, was the failure caused by a specific motor command, or by the high-level "search and rescue" protocol itself?

Existing models struggle with this hierarchy. Reasoning about causes at the level of individual lines of code is not only computationally prohibitive but often fails to provide the intuitive explanations required for human-centric debugging or legal accountability. The goal is to move the causal focus from "Action A caused Effect E" to "Program δ caused Effect E."

Methodological Framework

Situation Calculus and ConGolog

The authors build their framework on the Situation Calculus (SC), a logic-based formalism for representing changing worlds. To represent complex programs, they utilize ConGolog, a high-level logic programming language that allows for the definition of complex behaviors including concurrency and non-determinism.

Weak Potential Causes

A central contribution of the paper is the definition of a program as a "weak potential cause." Under this definition, a program is considered a cause if there exists at least one execution path that triggers the observed effect and ensures the effect persists. This distinguishes it from "strong" causes, where every possible execution path must lead to the effect. This flexibility is essential for capturing the causal impact of non-deterministic software.

The Abstraction Framework

To bridge the gap between high-level (HL) intent and low-level (LL) execution, the authors introduce a refinement mapping ($m$). This mapping links HL actions (e.g., rescue(robot, location)) to LL ConGolog programs (e.g., a sequence of clear_rubble and evacuate).

The framework relies on $m$-bisimulation to ensure that the HL model is a faithful representation of the LL system. A critical requirement identified by the authors is "non-transiency": for abstraction to remain causally valid, low-level effects must not be transient. If a fluent (a state variable) flickers true and then false within the execution of a single high-level action, the causal link between the HL and LL models may break.

Key Theoretical Results

The paper provides several foundational proofs that validate this abstract approach to causality:

  1. Equivalence to Primitive Theories: The authors demonstrate that when a program consists only of a simple sequence of actions, their definition of programmatic causation aligns perfectly with established theories of actual causation for primitive events.
  2. Correspondence Theorems: Through a series of theorems (Theorems 15–19), the authors prove the relationship between HL and LL causes. Under a "Sound Abstraction," identifying a cause at the high level is sufficient to guarantee that the corresponding low-level implementation is also a cause. Conversely, under a "Complete Abstraction," any cause identified at the low level can be mapped back to a high-level cause.
  3. Efficiency Gains: By reasoning at the HL, the state space and action sequences are significantly reduced. This allows for valid causal conclusions to be drawn without the exhaustive search required by low-level traces.

Discussion and Future Work

While this paper establishes a rigorous semantic foundation for programmatic causation, several areas remain for future exploration. The current framework is purely qualitative; it does not account for the probability of specific execution paths, which is a vital component of "weak" causation in real-world stochastic environments.

Furthermore, the theory currently assumes that the refinement mapping ($m$) is provided by the user. Future research could investigate methods for the automated discovery of these abstractions from source code. Finally, while the proofs focus on a two-layer (HL/LL) relationship, extending this to multi-level software stacks would further enhance the utility of the framework for complex, modern AI systems.

By treating programs as first-class causal citizens, this work provides a scalable path toward more interpretable and verifiable autonomous systems.

Summary updated

BibTeX
@inproceedings{banihashemi2022from,
  author = {Bita Banihashemi and Shakil M. Khan and Mikhail Soutchanski},
  title = {{From Actions to Programs as Abstract Actual Causes}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20485},
}
Figure