Reasoning about Actual Causes in Nondeterministic Domains – Extended Version
Shakil M. Khan, Yves Lespérance, Maryam Rostamigiv · 2024
Read Reasoning about Actual Causes in Nondeterministic Domains – Extended Version by Shakil M. Khan, Yves Lespérance, Maryam Rostamigiv (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-16728.txt.
Introduction
Shakil Khan, Yves Lesperance, and Maryam Rostamigiv study how to reason about actual causes when the world is not deterministic, in a 2024 paper. In such settings, the environment makes choices an agent cannot control or fully know. Most past work on root causes assumed full determinism.
Building on early work in the situation calculus, a formal logic of actions, they define two notions: certainly causes and possibly causes. These capture whether an agent action must have caused an outcome or merely could have. They then show how regression, a backward reasoning method in that logic, can be extended to answer such questions.
Catalog record
| CREATOR | Shakil M. Khan, Yves Lespérance, Maryam Rostamigiv |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-16728
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reasoning about Actual Causes in Nondeterministic Domains – Extended Version Shakil M. Khan, Yves Lespérance, Maryam Rostamigiv Abstract Reasoning about the causes behind observations is crucial to the formalization of rationality. While extensive research has been conducted on root cause analysis, most studies have predominantly focused on deterministic settings. In this paper, we investigate causation in more realistic nondeterministic domains, where the agent does not have any control on and may not know the choices that are made by the environment. We build on recent preliminary work on actual causation in the nondeterministic situation calculus to formalize more sophisticated forms of reasoning about actual causes in such domains. We investigate the notions of “Certainly Causes” and “Possibly Causes” that enable the representation of actual cause for agent actions in these domains. We then show how regression in the situation calculus can be extended to reason about such notions of actual causes. 1 University of Regina, Regina, SK, Canada 2 York University, Toronto, ON, Canada [email protected], [email protected], [email protected] Introduction The term causation refers to a collection of closely-related important philosophical problems dealing with causes and their effects that has been studied since the time of Aristotle. Determining the “actual” causes of an observed effect, which are events chosen from a recorded history of actions that occurred prior to the observation of the effect (also known as the scenario) is one such problem (called “efficient” cause in Aristotelian lingo) that has been extensively researched. Motivated by David Hume’s philosophical work and Herbert Simon’s early contributions, Pearl ( Pearl 1998 ; Pearl 2000 ) , and later Halpern ( Halpern 2000 ; Halpern 2015 ; Halpern 2016 ) , Halpern and Pearl ( Halpern and Pearl 2005 ) , and others ( Eiter and Lukasiewicz 2002 ; Hopkins 2005 ; Hopkins and Pearl 2007 ) developed computational formalizations of this problem within Structural Equations Models (SEM). While their inspirational work significantly advanced this field, their approach based on SEM has been nevertheless criticized for its limited expressiveness ( Hopkins 2005 ; Hopkins and Pearl 2007 ; Glymour et al. 2010 ) , and others have expanded SEM with additional features ( Leitner-Fischer and Leue 2013 ) or proposed alternate formalizations of actual cause, e.g. ( Bochman 2018 ; Beckers and Vennekens 2018 ; de Lima and Lorini 2024 ) . In response to these criticisms, in recent years researchers have become increasingly interested in studying causation within more expressive action-theoretic frameworks, in particular in that of the situation calculus ( Batusov and Soutchanski 2017 ; Batusov and Soutchanski 2018 ; Khan and Soutchanski 2020 ) . Among other things, this allows one to formalize causation from the perspective of individual agents by defining a notion of epistemic causation ( Khan and Lespérance 2021 ) and by supporting causal reasoning about conative effects, which in turn has proven useful for explaining agent behaviour using causal analysis ( Khan and Rostamigiv 2023 ) and has the potential for defining important concepts such as responsibility and blame ( Yazdanpanah et al. 2023 ) . While there has been a lot of work on actual causation, the vast majority of the work in this area has focused on deterministic domains. However, a distinguishing feature of the real world is that change is often unpredictable. Very few studies address causation in nondeterministic systems, and those that do, are formalized in SEM-based causal models that are known to have limited expressiveness and suffer from a variety of problems. For instance, recently Beckers ( 2024 ) presented an extension of causal models to deal with nondeterminism. However, despite improving on expressivity of causal models, it is not clear how one can formalize various aspects of action-theoretic/dynamic frameworks there, e.g. non-persistent change supported by fluents, possible dependency between events, temporal order of event occurrence, etc. To deal with this, building on previous work on actual causation in the situation calculus ( Batusov and Soutchanski 2018 ; Khan and Lespérance 2021 ) , more recently ( Rostamigiv et al. 2024 ) formalized actual causes in more expressive nondeterministic action-theoretic domains. They used the nondeterministic situation calculus ( De Giacomo and Lespérance 2021 ) as their base framework. They introduced notions of “Certainly Causes” and “Possibly Causes” that enable the representation of actual cause when the agent does not control her actions’ outcomes and does not know the choices that are made by the environment. However, this early work formalizes reasoning about causes in these domains by considering all possible evolutions of the scenario, which makes reasoning computationally intractable. 1 1 1 They reason about “Certainly Causes” by considering all the possible executions of the scenario, and determining whether the given action was an actual cause in each of them. However, the number of distinct executions of such a scenario/agent action sequence is exponential in the number of nondeterministic actions in the scenario. In this paper, we build on this preliminary work and formalize more effective forms of reasoning about actual causes in such nondeterministic domains. In particular, we extend regression in the situation calculus to provide a more effective mechanism to reason about actual causes. The paper is structured as follows. In the next section, we provide an overview of the situation calculus and nondeterministic situation calculus (NDSC) and introduce our running example. Then, we examine the definition of actual cause proposed earlier. After that, we present the definitions of various causal notions in the NDSC. Next, we formalize reasoning about actual causes in the NDSC. In particular, we prove some properties showing how regression in the situation calculus can be extended to deal with these notions. Finally, we conclude the paper with some discussion. Preliminaries Situation Calculus (SC). The situation calculus is a well-known second-order language for representing and reasoning about dynamic worlds ( McCarthy and Hayes 1969 ; Reiter 2001 ) . In the SC, all changes are due to named actions, which are terms in the language. Situations represent a possible world history resulting from performing some actions. The constant S_{0} is used to denote the initial situation where no action has been performed yet. The distinguished binary function symbol \mathit{do}(a,s) denotes the successor situation to s resulting from performing the action a . The expression \mathit{do}([a_{1},\cdots,a_{n}],s) represents the situation resulting from executing actions a_{1},\cdots,a_{n} , starting with situation s . As usual, a relational/functional fluent representing a property whose value may change from situation to situation takes a situation term as its last argument. There is a special predicate \mathit{Poss}(a,s) used to state that action a is executable in situation s . Also, the special binary predicate s\sqsubset s^{\prime} represents that s^{\prime} can be reached from situation s by executing some sequence of actions. s\sqsubseteq s^{\prime} is an abbreviation of s\sqsubset s^{\prime}\lor s=s^{\prime} . s<s^{\prime} is an abbreviation of s\sqsubset s^{\prime}\land\mathit{Executable}(s^{\prime}) , where \mathit{Executable}(s) is defined as \forall a^{\prime},s^{\prime}.\;do(a^{\prime},s^{\prime})\sqsubseteq s\supset\mathit{Poss}(a^{\prime},s^{\prime}) , i.e. every action performed in reaching situation s was possible in the situation in which it occurred. s\leq s^{\prime} is an abbreviation of s<s^{\prime}\vee s=s^{\prime} . In the SC, a dynamic domain is specified using a basic action theory (BAT) \mathcal{D} that includes the following sets of axioms: (i) (first-order or FO) initial state axioms \mathcal{D}_{S_{0}} ,