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.
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$).
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