Reasoning About Actual Causes in Nondeterministic Domains

Shakil M. Khan, Yves Lespérance, Maryam RostamigivAAAI 2025 · DOI

Abstract: This paper addresses the challenge of reasoning about actual causation in nondeterministic environments. By extending the Situation Calculus, the authors formalize two new notions of causality—Certainly Causes and Possibly Causes—and introduce an Extended Regression Operator ($R_{ext}$). This operator allows for efficient computation of causal queries by transforming them into first-order logical formulas, effectively bypassing the exponential complexity of traditional tree-search methods.

Introduction

In AI, "Actual Causation" involves identifying which specific actions in a history were responsible for a particular outcome. While frameworks like Judea Pearl’s Structural Equation Models (SEM) are widely used, they often struggle with expressiveness regarding time, changing properties (fluents), and complex action sequences. Furthermore, most existing work assumes a deterministic world where actions have fixed outcomes.

In reality, environments are often unpredictable. If a robot moves through a risky area, it might become "vulnerable" depending on environmental factors beyond its control. This paper provides a formal logic to determine blame in such nondeterministic settings without falling into the computational trap of exhaustive state-space searches.

Formalizing Nondeterministic Causality

The authors build upon the Nondeterministic Situation Calculus (NDSC), where an action is split into the agent's intent and the environment's reaction. This structure generates a tree of possible outcomes for any given sequence of agent actions.

Figure 2: A tree of environmental reactions showing how a fluent $v$ (vulnerability) can manifest across different paths.

Within this framework, two key causal concepts are introduced:

  • Possibly Causes (PCauses): An action is a possible cause if there exists at least one path through the environment's reactions where that action triggered the observed effect.
  • Certainly Causes (CCauses): An action is a certain cause if, in every possible scenario consistent with the observed outcome, that action was responsible. This allows for filtering out theoretical futures that do not align with what was actually observed.

The Running Example

To demonstrate the logic, the paper utilizes a benchmark scenario involving a robot navigating a grid with specific "risky" locations ($I_1, I_2$).

Figure 1: A robot navigation scenario with risky locations $I_1$ and $I_2$.

In this scenario, the robot moves from $I_0 \rightarrow I_1 \rightarrow I_2 \rightarrow I_3$. The goal is to formally prove whether the move to $I_1$ or $I_2$ was the actual cause of the robot eventually becoming vulnerable, even if the vulnerability only manifests several steps later. The logic correctly distinguishes between the "trigger" (the direct cause) and "indirect causes" (preconditions).

Efficient Reasoning via Extended Regression

The core technical innovation is the Extended Regression Operator ($R_{ext}$). Traditionally, checking causal queries in nondeterministic trees is computationally intractable because it requires simulating every possible branch.

The authors prove that causal queries can be recursively "regressed" into the initial state ($S_0$). This process transforms complex second-order logic queries into compact first-order logical formulas. This shift makes the system practical for real AI applications by "collapsing" the tree of possibilities into a single logical check against starting conditions.

Key Results and Future Work

The researchers mathematically established the Soundness and Completeness of their regression operator. Their results show that the approach is not only accurate but also efficient, producing compact formulas even as the number of nondeterministic steps increases.

Future work aims to expand this framework to handle concurrency (simultaneous actions) and epistemic uncertainty (reasoning about what an agent believes caused an event). Additionally, the authors plan to implement the logic in a programming environment like Prolog to further test its scalability in complex real-world domains.

Summary updated

BibTeX
@inproceedings{khan2025reasoning,
  author = {Shakil M. Khan and Yves Lespérance and Maryam Rostamigiv},
  title = {{Reasoning About Actual Causes in Nondeterministic Domains}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i14.33647},
}
Figure