Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Reasoning About Actual Causes in Nondeterministic Domains
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends actual-cause formalization in the nondeterministic situation calculus with "certainly causes" and "possibly causes" for agent actions and an extended regression operator that avoids enumerating all executions.
Problem
Determining actual causes of observed effects for agent actions in nondeterministic domains where the environment's reactions are unknown; prior formalization enumerates all executions, which is computationally intractable.
Approach
Defines certainly-causes and possibly-causes for agent actions in the nondeterministic situation calculus and extends Reiter-style regression (Rext) so these causal queries reduce to regressable formulas about the initial situation, sidestepping the second-order foundational axioms.
Key results
- Proves an extended regression theorem (Theorem 1): an extended regressable formula φ holds in an NDBAT D iff D_S0 ∪ D_una entails R*_ext[φ], reducing certainly/possibly-cause queries to formulas about the initial situation.
- On a robot navigation running example, shows move(I0,I1) certainly causes Vul, while move(I1,I2) only possibly causes it (Proposition 2).
Limitations
- No implementation or empirical evaluation of computational efficiency.
- Restricted to scenarios that are sequences of actions without concurrency.
- Only objective causation; epistemic causation under nondeterminism left to future work.
Experimental setup
Baselines: Rostamigiv et al. 2024 direct translation approach
Builds on: Khan and Lespérance 2021 achievement cause De Giacomo and Lespérance 2021 nondeterministic situation calculus Batusov and Soutchanski 2018 Rostamigiv et al. 2024
Closest papers by meaning
- Situation Calculus Semantics for Actual Causality (AAAI 2018 · similarity 0.89)
- From Actions to Programs as Abstract Actual Causes (AAAI 2022 · similarity 0.88)
- Improving Causal Explanations (NeurIPS 2026 · similarity 0.87)
- From Probability to Counterfactuals: the Increasing Complexity of Satisfiability in Pearl's Causal Hierarchy (ICLR 2025 · similarity 0.85)
- Systems with Switching Causal Relations: A Meta-Causal Perspective (ICLR 2025 · similarity 0.83)
- A New Approach to Backtracking Counterfactual Explanations: A Unified Causal Framework for Efficient Model Interpretability (ICML 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.