Reasoning About Causal Knowledge in Nondeterministic Domains

1 Introduction

Actual or token-level causality [Halpern, 2016] refers to the problem of determining the causes of observed effects from a perceived history of actions. Actual causality plays a crucial role in effective decision-making and planning in multiagent systems. For instance, when an agent's plans fail to bring about her goals, it would be useful to understand why they failed, as this can aid the task of replanning by allowing the agent to generate better plans. However, for this to work, the agent must be able to reason about her own as well as other agents' causal knowledge. While extensive research has been conducted on actual causality [Pearl, 1998; Pearl, 2000; Halpern, 2000; Eiter and Lukasiewicz, 2002; Bochman, 2003; Hopkins, 2005; Hopkins and Pearl, 2007; Halpern, 2015; Batusov and Soutchanski, 2017; Batusov and Soutchanski, 2018; Bochman, 2018; Khan and Soutchanski, 2020; Beckers, 2021; Gladyshev et al., 2023; Bochman, 2023], only a couple deal with causal knowledge [Chockler et al., 2015; Khan and Lesp´erance, 2021].

A distinguishing feature of the real world is that change is often unpredictable. Unfortunately, the vast majority of the work in the area has focused on deterministic domains and only recently have researchers started investigating actual causation in nondeterministic domains [Rostamigiv et al., 2024; Beckers, 2024; Khan et al., 2025], where the outcome of the agent's actions depends on unpredictable environment reactions. Importantly, none have studied causal knowledge and its dynamics in such nondeterministic domains.

To deal with this, in this paper we propose a framework for reasoning about causal knowledge in nondeterministic domains. Our formalization is based on the recently proposed nondeterministic situation calculus (NDSC) [De Giacomo and Lesp´erance, 2021] and a model of actual causation in the situation calculus [Khan and Lesp´erance, 2021]. In our account, the agent may not know the environment reactions to her actions and their outcomes, and may be uncertain about which actions caused a condition to come about. But she can perform sensing actions to acquire knowledge about the state and use it to gain knowledge about causes. Our formalization supports reasoning about observed epistemic effects, recognizes sensing actions as causes of both physical and epistemic effects, and allows an agent to acquire causal knowledge by performing knowledge-producing actions. We also examine how regression can be used to reason about causal knowledge.

Our contribution in this paper is three-fold. First, we give a new successor-state axiom for the knowledge-accessibility relation and show how one can model knowledge update in the NDSC, and study some of its properties. As we will see, this is quite different from its deterministic situation calculus counterpart, as in such NDSC domains an agent might lose knowledge after executing an action. Secondly, we discuss how a recently proposed account of causation in the situation calculus [Khan and Lesp´erance, 2021] can be naturally combined with this account of knowledge in the NDSC to model causal knowledge in the NDSC. As mentioned, our formalization supports epistemic effects and recognizes sensing actions as causes. Finally, we extend knowledge regression in the situation calculus [Scherl and Levesque, 2003] and show how one can reason about causal knowledge in the NDSC.

2 Action and Nondeterminism

Situation Calculus (SC). Our base framework is the situation calculus [McCarthy and Hayes, 1969; Reiter, 2001], which we will not cover in detail here, except to remind the reader of the following: S0 is used to denote the initial situation, do(a, s) for the successor situation to s resulting from performing the action a, and do([a1, · · · , an], s) to represent the situation resulting from executing actions a1, · · · , an, starting with situation s. Relational/functional fluents take situation terms as their last argument. Poss(a, s) states that action a is executable in situation s. s ⊏ s′ represents that s′ can be reached from situation s by executing some sequence of actions. s ⊑ s′ .= s ⊏ s′ ∨ s = s′ . s < s′ is an abbreviation of s ⊏ s′ ∧ Executable(s′ ), where Executable(s) is defined as ∀a′ , s′ . do(a′ , s′ ) ⊑ s ⊃ Poss(a′ , s′ ). s ≤ s′ is an abbreviation of s < s′ ∨ s = s′ .

In the SC, a dynamic domain is specified using a basic action theory (BAT) D that includes: (i) initial state axioms DS0 ; (ii) action precondition axioms Dap characterizing Poss(a, s); (iii) successor-state axioms Dss indicating precisely when the fluents change; (iv) unique-names axioms Duna for actions; and (v) foundational axioms Σ, describing the structure of situations [Levesque et al., 1998].

A key feature of BATs is the existence of a sound and complete regression mechanism for answering queries about situations resulting from performing a sequence of actions [Pirri and Reiter, 1999; Reiter, 2001]. In a nutshell, the regression operator R∗ reduces a formula ϕ about a particular future situation to an equivalent formula R∗ [ϕ] about the initial situation S0. A formula ϕ is regressable if and only if (i) all situation terms in it are of the form do([a1, . . . , an], S0), (ii) in every atom of the form Poss(a, σ), the action function is specified, i.e., a is of the form A(t1, . . . , tn), (iii) it does not quantify over situations, and (iv) it does not contain ⊏ or equality over situation terms. Thus in essence, a formula is regressable if it does not contain situation variables. In Section 4, we will define a one-step variant of R∗ , denoted using Rext . R∗ can then be defined as the repeated application of Rext until further applications leave the formula unchanged. Another key result about BATs is the relative satisfiability theorem [Pirri and Reiter, 1999; Reiter, 2001]: D is satisfiable if and only if DS0 ∪ Duna is satisfiable (the latter being a purely first-order theory).

We will use uppercase Greek letters Φ, Ψ, etc. for situationsuppressed SC formulae, which are defined as follows:

where ⃗x and x are object terms. Also, we will use α and σ, possibly with decorations, to represent ground action and situation terms, respectively. Finally, we use uppercase Latin letters for ground terms, lowercase Latin letters for variables. Nondeterministic Situation Calculus (NDSC). An important limitation of the standard SC is that atomic actions are deterministic. De Giacomo and Lesp´erance [2021] (DL21) proposed a simple extension of the framework to handle nondeterministic actions while preserving the solution to the frame problem. For any primitive action by the agent in a nondeterministic domain, there can be a number of different outcomes. (DL21) takes the outcome as being determined by the agent's action and the environment's reaction to this action. This is modeled by having every action type/function A(⃗x, e) take an additional environment reaction parameter e, ranging over a new sort Reaction of environment reactions. The agent cannot control the environment reaction, so it performs the reaction-suppressed version of the action A(⃗x) and the environment then selects a reaction e to produce the complete action A(⃗x, e). The reaction-suppressed version of the action A(⃗x) is called an agent action and the full version of the action A(⃗x, e) is called a system action.

We represent nondeterministic domains using action theories called Nondeterministic Basic Action Theories (NDBATs), which can be seen as a special kind of BAT, where (1) every agent action takes an environment reaction parameter; (2) for each agent action we have an agent action precondition formula, Possag(a(⃗x), s) .= ϕagPoss a (⃗x, s); (3) for each agent action we have a reaction independence requirement, stating that the precondition for the agent action is independent of any environment reaction ∀e. Poss(a(⃗x, e), s) ⊃ Possag(a(⃗x), s); (4) for each agent action we also have a reaction existence requirement, stating that if the precondition of the agent action holds then there exists a reaction to it which makes the complete system action executable, i.e., the environment cannot prevent the agent from performing an action when its agent action precondition holds Possag(a(⃗x), s) ⊃ ∃e. Possag(a(⃗x, e), s). The above requirements must be entailed by an NDBAT.

An NDBAT D is the union of the following disjoint sets: including (1) foundational axioms, (2) unique-names axioms for actions, (3) axioms describing the initial situation, (4) successor-state axioms (SSA) indicating how fluents change after system actions, and (5) system action precondition axioms, indicating when system actions can occur; while these axioms generally follow the form: Poss(a(⃗x, e), s) ≡ ϕPoss a (⃗x, e, s), in practice, these axioms often take the form: Poss(a(⃗x, e), s) ≡ Possag(a(⃗x), s) ∧ φPoss (⃗x, e, s), where Possag(a(⃗x), s) denotes conditions necessary for the agent action a(⃗x) to occur and ϕPoss a (⃗x, e, s) captures additional conditions influenced by the environment's response.

In the NDSC, executing an agent action in a situation may result in different situations and outcomes depending on the environment reaction. To capture this, (DL21) introduced the defined predicate Doag(⃗a, s, s′ ), meaning that the system may reach situation s′ when the agent executes the sequence of agent actions ⃗a starting in situation s for some environment reactions. A condition Φ may possibly hold after some executions of a sequence of agent actions ⃗a starting in situation s, denoted by PAfter(⃗a, Φ, s), or it may certainly hold after all executions of ⃗a in s, denoted by CAfter(⃗a,Φ, s). Similarly, (DL21) define notions of ⃗a being possibly/certainly executable. See [De Giacomo and Lesp´erance, 2021] for details.

3 Knowledge in the SC and NDSC

We now extend the framework of NDSC to accommodate knowledge and sensing. For simplicity, in both deterministic SC and NDSC, we assume the existence of two categories of primitive actions: ordinary/non-knowledge-producing actions and binary sensing/knowledge producing actions.

Formalizing Knowledge in SC. Following [Moore, 1985; Scherl and Levesque, 2003], we model knowledge using a possible worlds account adapted to the SC. There can now be multiple initial situations. Init(s) means that s is an initial situation. The actual initial state is denoted by S0. K(s′ , s) is used to denote that in situation s, the agent thinks that she could be in situation s′ . Using K, the knowledge of an agent is defined as: 1 Know(Φ, s) .= ∀s′ . K(s′ , s) ⊃ Φ[s′ ], i.e. the agent knows Φ in s if Φ holds in all of her K-accessible situations in s. We also use the abbreviations KWhether(Φ, s) .= Know(Φ, s) ∨ Know(¬Φ, s), i.e., the agent knows whether Φ holds in s and KRef (θ, s) .= ∃t. Know(θ = t, s), i.e., she knows who/what θ refers to. K is constrained to be reflexive and Euclidean (and thus transitive) in the initial situation to capture the fact that the agent's knowledge is true, and that she has positive and negative introspection.

The dynamics of knowledge is specified by a SSA for K that supports knowledge expansion as a result of sensing actions. The information provided by a binary sensing action is specified using the predicate SF(a, s); e.g., we might have SF(senseonTable(b), s) ≡ onTable(b, s), i.e., the action senseontable(b) will tell the agent whether the block b is on the table in the situation where it is performed. SF is specified to be uniformly true for non-sensing actions. [Scherl and Levesque, 2003] specifies the SSA for K as follows: 2

Thus, after an action happens, the agent learns that it was executable and it has happened. Moreover, if the action is a binary sensing action, the agent acquires knowledge of the associated proposition. As shown in [Scherl and Levesque, 2003], the constraints on K then continue to hold after any sequence of actions since they are preserved by the SSA for K. Scherl and Levesque [Scherl and Levesque, 2003] also showed how one can define regression for knowledge-producing actions.

Thus to model knowledge, one uses a theory that is similar to before, but with modified foundational axioms to allow for multiple initial epistemic states. Also, action preconditions can now include knowledge preconditions and initial state axioms can now include axioms describing the epistemic states of the agents. Finally, the aforementioned axioms for K are included. See [Reiter, 2001] for details.

Accommodating Nondeterminism. In deterministic domains, an agent's knowledge evolves predictably based on her actions. In contrast, in the NDSC, the agent must reason not only about the actions she performed but also about how the environment might react to those actions, reactions that she does not observe. For simplicity here, we will assume that the (binary) sensing actions A(⃗x) are deterministic (unlike the ordinary actions), and thus are coupled with a constant success reaction Suc to produce the associated system actions A(⃗x, Suc).

The key to modeling knowledge in such a setting is the SSA for the knowledge fluent K, which specifies how the agent's knowledge evolves after performing an action. We modify it as follows to account for the fact that the agent does not observe the environment reaction:

1Φ can contain a placeholder now in the place of the situation terms. Also, Φ[s] denotes the formula obtained by restoring the situation argument s into all fluents in Φ.

2 For simplicity, in this paper we deal with binary sensing actions exclusively, and thus we use the SF fluent [Levesque, 1996]. We could have generalized this easily.

Thus after A(⃗x, e) happens, the agent learns that for some environment reaction e′ , A(⃗x, e′ ), which was executable, has happened, and just like the deterministic case, if the action is a binary sensing action, the agent acquires knowledge of the associated proposition. This thus models that if there are more than one possible reactions for A(⃗x), the agent will not know the actual environment reaction.

[Scherl and Levesque, 2003] proved some properties to show that their axiomatization ensures that knowledge changes as appropriate. Let us examine which of these properties still hold unchanged for our axiomatization of knowledge in the NDSC, and which hold in a modified form. First, we still have that knowledge-producing actions do not change the state of the world, and the only fluent whose truth value is altered by a knowledge-producing action is K:

Theorem 1 (Knowledge-Producing Effects - Theorem 1 in [Scherl and Levesque, 2003]). For all situations s, all fluents P (other than K) and knowledge-producing system action terms α, if P(s) then P(do(α, s)).

This follows from the requirement that knowledge-producing actions do not affect fluents other that K.

Secondly, we still have that agents know the consequences of knowledge acquired through knowledge-producing actions:

Theorem 2 (Knowledge Incorporation - Theorem 3 in [Scherl and Levesque, 2003]). For a knowledge-producing system action α, a fluent or the negation of a fluent F , a fluent or the negation of a fluent P, and a situation s, if the axiomatization entails that Know(F ≡ SF(α), s), F(s), Poss(α, s), and Know(F ⊃ P, s) hold, then Know(P, do(α, s)) holds as well.

We also have the following result showing that ignorance persist unless the agent knows that the action affects the fluent in question or produces knowledge about it:

Theorem 3 (Default Persistence of Ignorance). For a system action a(⃗x, e) and a situation s, if ¬Know(P, s) holds and the axiomatization entails that ∀e′ , s.Poss(a(⃗x, e′ ), s) ⊃ (P(do(a(⃗x, e′ ), s)) ≡ P(s)) and ¬Know(∀e′ .[(Poss(a(⃗x, e′ )) ∧ SF(a(⃗x, e′ ))) ⊃ P], s), then ¬Know(P, do(a(⃗x, e), s)) holds as well.

This is a modification of Theorem 2 in [Scherl and Levesque, 2003], where we take into account the fact that the agent does not observe the environment reaction.

[Scherl and Levesque, 2003] show (their Theorem 4) that in the deterministic SC, agents never forget, i.e., if an agent knows P in situation s, then P remains known in do(a, s), provided that the action a does not make P false. This property no longer holds in non-deterministic domains. Instead, we have that:

Theorem 4 (Memory). For all fluents P and situations s, if Know(P, s) holds, then Know(P, do(a(⃗x, e), s)) holds as long as the axiomatization entails that

That is, the knowledge of P persists as long as P persists after the agent action for all possible reactions.

[Scherl and Levesque, 2003] also show (their Theorem 5) that in the deterministic SC, agents know the effects of ordinary actions. Instead, we have that this holds for certain effects of the action (i.e., effects that hold no matter what the environment reaction is):

Theorem 5 (Knowledge of Certain Effects of Actions). If a(⃗x, e) is an ordinary action (not a knowledge-producing action) and if the axiomatization entails that ∀e′ , s.ϕ[s] ∧ Poss(a(⃗x, e′ ), s) ⊃ P(do(a(⃗x, e′ ), s)), where ϕ is an arbitrary formula with situation terms suppressed and P is a fluent or its negation, then the following is also entailed:

Finally, we prove a property that shows that in the NDSC, the agent's knowledge in situation do(α(e), s) can be reduced to the agent's knowledge in s. This will serve as a basis of our proposed extended knowledge-regression operator.

Proposition 1. Let D be an NDBAT, α(⃗x) be a ground agent action term, φ be a situation-suppressed SC formula. Then we have the following. When α(⃗x) is a regular (nonknowledge-producing) agent action:

When α(⃗x) is a knowledge producing agent action with sensed-fluent axiom SF (α(⃗x, e), s) ≡ ψ[s]:

The proofs of Theorems 3, 4, and 5 are similar to that of the corresponding results in [Scherl and Levesque, 2003]. Proposition 1 can be proved easily by applying the definition of Know and using the successor-state axiom for K.

Example. Consider a robot navigating between locations and communicating. The robot communicates only if the location is not risky and it hasn't become vulnerable. The robot moves between connected locations (agent action move(i, j)) and communicates from the current location (agent action comm(i)). Moving to a risky location may make the robot vulnerable, represented by the system action move(i, j, e) where e can be either Vul (vulnerable) or NotVul (not vulnerable). The communication action has a single successful outcome, represented by the system action comm(i, e) where e = Suc. The precondition axioms for these are as follows:

(1) Possag (move(i, j), s) ≡ At (i, s) ∧ Connected (i, j), (2) Possag (comm(i), s) ≡ ¬Vul (s) ∧ ¬Risky(i, s), (1′ ) Poss(move(i, j, e), s) ≡ Possag (move(i, j), s) ∧ (Risky(j, s) ⊃ (e = Vul ∨ e = NotVul )) ∧ (¬Risky(j, s) ⊃ e = NotVul ), (2′ ) Poss(comm(i, e), s) ≡ Possag (comm(i), s) ∧ e = Suc.

The fluents in this example are Vul (s), which denotes that the robot is vulnerable in situation s, At(i, s), which states that the robot is at location i in s, and Risky(i, s), which indicates that location i is risky in s. Certain locations are risky initially and they remain the only risky ones as actions are performed. Additionally, there is a non-fluent Connected(i, j) indicating a path from location i to j.

The SSA for these fluents are as follows:

(3) At (j, do(a, s)) ≡ ∃i, e. a = move(i, j, e)

∨ (At (j, s) ∧ ∀j ′ , e′ . ¬(a = move(j, j ′ , e′ ))),

1. Vul (do(a, s)) ≡ ∃i, j. a = move(i, j, Vul ) ∨ Vul (s),
2. Risky(i, do(a, s)) ≡ Risky(i, s).

We also have the following initial state axioms:

There are four locations I0 to I3 in this domain, and the interconnections between these are given by the Connected(i, j) predicate, where (i, j) are the pairs (I0, I1), (I1, I0), (I1, I2), (I2, I1), (I2, I3), and (I3, I2). We will refer to this NDBAT as D1.

We assume the following initial knowledge:

(9) Know(At(I0), S0), (10) Know(¬Vul , S0), (11) ¬KWhether (Risky(I1), S0), (12) ¬KWhether (Risky(I2), S0), (13) Know((Risky(I1) ∧ ¬Risky(I2)) ∨ (¬Risky(I1) ∧ Risky(I2)), S0).

Initially, there are two possible worlds related to S0: S0, where the robot is at location I0, is not vulnerable, and I2 only is risky, and S1 0 , where the robot is at location I0, is not vulnerable, and I1 only is risky. We also have sensing actions senseR(j, e) and senseV (e), and the following sensed-fluent axioms: senseR(j, e) senses whether location j is Risky:

senseV (e) senses whether the robot has become vulnerable:

Let DK 1 denote this axiomatization with knowledge. In this domain, we can show the following results:

Proposition 2.

4 Reasoning About Causal Knowledge

Causal Knowledge in the SC. Actual causation is the problem of identifying the relevant actions within a given history of events (known as the scenario), those that were responsible for causing an observed effect. When the effect is assumed to be initially false, this problem is referred to as achievement causation. Building on Batusov and Soutchanski's [2018] definition of actual causes, Khan and Lesp´erance [2021] (KL21, henceforth) recently formalized causal knowledge in the (deterministic) SC. Both proposals constrain scenarios to be linear sequences of actions. (KL21)'s account can handle causes of epistemic effects, allowing an agent to incorporate knowledge-preconditions of actions and reason about the causes of newly acquired knowledge. They showed that an agent may be uncertain about a cause, but might know it after performing some knowledge-producing actions.

To formalize reasoning about causal knowledge, (KL21) introduced the concept of an epistemic dynamic formula.

Definition 1. Let ⃗x, θa, and ⃗y range over object terms, system actions, and object/system action variables, respectively. The class of situation-suppressed epistemic dynamic formulae φ is defined by: φ ::= P(⃗x) | Poss(θa) | After(θa, φ) | ¬φ | φ1 ∧φ2 | ∃⃗y. φ | Know(φ).

Given an epistemic dynamic formula φ, actual causes of φ are defined relative to a causal setting ⟨D, s, φ⟩, where D is a BAT and s is the scenario. Since we are dealing with achievement causality exclusively, it is also assumed that D |= Executable(s) ∧ ¬φ[S0] ∧ φ[s]. Here φ[s] denotes the formula obtained from φ by restoring the appropriate situation argument into all fluents in φ. Formally:

Definition 2.

Since all changes in the SC are result of actions, the potential causes of an effect φ are identified with the set of action terms occurring in a situation s. However, since s may contain multiple instances of the same action, it is necessary to uniquely identify where these actions were performed. To address this, (KL21) required that each situation be associated with an integer timestamp, formalized using the following axioms: time(S0) = 0,

∀a, s, ts.time(do(a, s)) = ts ≡ time(s) = ts - 1.

Causes are then a set of action-timestamp pairs.

Following [Batusov and Soutchanski, 2018], (KL21) define both primary and indirect notions of causes. Given an effect φ and scenario s, if some action of the action sequence in s triggers the formula φ to change from false to true relative to D, and if there are no actions in s after it that change φ back to false, then this action is an actual cause of achieving φ in s. Such causes are referred to as primary causes:

Definition 3 (Primary Cause (KL21)).

That is, a executed at timestamp ts is the primary cause of effect φ in situation s iff a was executed in a situation with timestamp ts in scenario s, a caused φ to change to true, and no subsequent actions on the way to s falsified φ.

Now, note that a (primary) cause a might have been nonexecutable initially. Also, a might have only brought about the effect conditionally and this context condition might have been false initially. Thus earlier actions in the trace that contributed to the preconditions and the context conditions of a cause must be considered as causes as well. The following definition captures both primary and indirect causes: 3

Definition 4 (Actual Cause (KL21)).

Thus, Causes is defined to be the least relation P such that if a executed at timestamp ts directly causes φ in scenario s then (a, ts, φ, s) is in P, and if a′ executed at ts′ is a direct cause of φ in s, the timestamp of s′ is ts′ , s′ < s, and (a, ts, [Poss(a′ ) ∧ After(a′ , φ)], s′ ) is in P (i.e. a executed at ts is a direct or indirect cause of [Poss(a′ ) ∧After(a′ , φ)] in s′ ), then (a, ts, φ, s) is in P. Here the effect [Poss(a′ ) ∧ After(a′ , φ)] is that a′ be executable and φ hold after a′ .

Example (cont'd). Consider the (system) action sequence σ1 and effect φ1, where σ1 = do([comm(I0, Suc), move(I0, I1,NotVul), move(I1, I2,Vul), move(I2, I3,NotVul)], S0) and φ1 = Vul . This is depicted in the left branch of the right tree in Figure 1. We can show that:

Proposition 3 (Causes of φ1 in σ1).

Thus, e.g., move(I1, I2, Vul ) executed at 2 is a cause since it directly caused the effect. Moreover, move(I0, I1,NotVul) executed at 1 can be shown to be an indirect cause of φ1. This is because by axioms (1) and (1′ ) the primary cause of moving from location I1 to I2 i.e. move(I1, I2,Vul) is only possible when the robot is at I1, which in this scenario was brought about by move(I0, I1, NotVul ).

With this definition of Causes(a, t, ψ, s), (KL21) showed that one can use it just like any other formula in the context of Know. One can state that an agent knows in some situation s that a executed at time t is a cause of an effect ψ, i.e. Know(Causes(a, t, ψ, now), s), which by definition of knowledge means that ∀s′ . K(s′ , s) ⊃ Causes(a, t, ψ, s′ ), i.e. in all her epistemic alternatives s′ , a at t is a cause of ψ.

Recently, [Khan et al., 2025] showed that Causes in do(a, s) can be reduced to a formula that only mentions Causes in s:

Proposition 4 (Proposition 3 in [Khan et al., 2025]).

D |= Causes(b, t, φ, do(a, s)) ≡ (time(s) = t ∧ b = a ∧ ¬φ[s] ∧ φ[do(a, s)]) ∨ (time(s) > t ∧ φ[s] ∧ φ[do(a, s)] ∧ Causes(b, t, φ, s)) ∨ (time(s) > t ∧ ¬φ[s] ∧ φ[do(a, s)] ∧ Causes (b, t, Poss (a) ∧ After (a, φ), s)).

3 In this, we need to quantify over situation-suppressed epistemic dynamic formulae. Thus we must encode such formulae as terms and formalize their relationship to the associated SC formulae. This is tedious but can be done essentially along the lines of [De Giacomo et al., 2000]. We assume that we have such an encoding and use formulae as terms directly.

Causal Knowledge in the NDSC. Exploiting our formalization of knowledge for the NDSC from Sec. 3, we can reason about how the agent's causal knowledge changes when her knowledge is updated.

Example (cont'd). Consider the robot's causal knowledge in σ1. Recall that the robot is unsure about the initial situation and cannot see the environment reactions to her actions; thus she must consider all possible executions of the agent action sequence associated with the scenario σ1 starting in the initial situations that she considers possible when dealing with causal knowledge. Figure 1 shows these executions of this agent action sequence, i.e. [comm(I0), move(I0, I1), move(I1, I2), move(I2, I3)], starting in K-alternate initial situations S0, where location I2 is risky, and S1 0 , where I1 is risky. Here, the superscripts v and nv represent environment choices Vul and NotVul , respectively, and v/¬v indicates whether the agent has become vulnerable or not. Thus, e.g., in this tree s1 = do(comm(I0, Suc), S0) and snv 2 = do(move(I0, I1,NotVul), s1), etc. The actual situations and execution is shown in red, and the blue dashed-line shows the (partial) K-accessibility relation. Finally, snv 42 = σ1.

We can show that:

Proposition 5 (Causal Knowledge in σ1).

DK 1 |= Know(¬∃e.Causes(comm(I0, e), 0, φ1), σ1) ∧ Know(¬φ1 ∨ ∃e.Causes(move(I0, I1, e), 1, φ1), σ1) ∧ ¬KWhether (∃e.Causes (move(I1, I2, e), 2, φ1), σ1) ∧ Know(¬∃e.Causes(move(I2, I3, e), 3, φ1), σ1).

Thus, line 1 and 4 above says that the robot knows that comm and the last move actions are not causes of φ1 = Vul since these do not involve moving to a risky location; line 2, that the robot knows that either she has not become vulnerable, or for some environment reaction e, the first move action (either directly, as in the case when e = Vul , or indirectly, when e = NotVul ) caused φ1 (note that it can be shown that the robot does not know if she has become vulnerable in σ1); and line 3, that she does not know whether the second move action is a cause, as even in the case where she became vulnerable, it might have been the first move action that caused it (e.g. as in the case for snv 44 ). Again, since the robot cannot see the environment reactions and does not know which of S0 and S1 0

is the actual initial situation, as far as she is concerned, after executing this agent action sequence, she might be in any of the situations snv 41 , snv 42 (which is σ1), snv 43 , or snv 44 ; see Fig. 1.

Moreover, we can show that in addition to the above knowledge, the robot will learn that moving from I0 to I1 is indeed a cause of Vul after sensing Vul in σ1, i.e. in σ2 = do(senseV (Suc), σ1):

Proposition 6 (Causal Knowledge in σ2 (Partial)).

This is because after sensing for Vul , she will drop all situations fromK where Vul does not hold, and will thus have s54 and σ2 in K, in each of which the second move is a cause.

Finally, after sensing whether location I2 is risky, she will also know the following in σ3 = do(senseR(I2 , Suc), σ2):

Proposition 7 (Causal Knowledge in σ3 (Partial)).

To see this, note that since the robot initially knew that either I0 or I1 but not both is risky (by Axiom (13)), knows that (non)risky locations remain (non)risky (by Axiom (5)), and just learned that I2 is risky, she will also know that I1 is not risky. Consequently, σ3 is the only K-accessible situation in σ3. The result follows from this and the fact that move(I0, I1,NotVul) and move(I1, I2,Vul) are the only causes of φ1 in σ3 (similar to in Proposition 3).

Extending Regression for Reasoning About Causal Knowledge in the NDSC. We start by extending the set of regressable formulae to include Causes(b, t, φ, do(a, s)) and Know(ϕ, do(a, s)), with the same restrictions on their arguments as imposed in the original definition of regressable formula [Scherl and Levesque, 2003]. We also extend R to define regression of these additional constructs. We denote this one-step extended regression operator using Rext. As usual, we use R∗ext to denote the repeated application of Rext until further applications leave the argument formula unchanged.

Definition 5 (The Extended Regression Operator Rext). (1) When ϕ is a non-fluent atom, including equality atoms without functional fluents as arguments, or when ϕ is a fluent atom, whose situation argument is S0, Rext[ϕ] = ϕ.

(2a) For a non-functional fluent F, whose successorstate axiom in D is F(⃗x, do(a, s)) ≡ ΦF (⃗x, a, s), Rext[F (⃗t, do(α, σ))] = ΦF (⃗t, α, σ).

(2b) For an equality literal with a functional fluent f, whose successor-state axiom is f (⃗x, do(a, s)) = y ≡ Φf (⃗x, y, a, s), Rext[f (⃗t, do(α, σ)) = t′ ] = Φf (⃗t, t′ , α, σ).

(2c) For a Poss literal with the action precondition axiom of the form Poss(A(⃗x), s) ≡ ΠA(⃗x, s), Rext[Poss(A(⃗t), σ)] ≡ Rext[ΠA(⃗t, σ)].

(3) For any non-atomic formulae, regression is defined inductively: Rext[¬ϕ] = ¬Rext[ϕ], Rext[ϕ1 ∧ ϕ2] = Rext[ϕ1] ∧ Rext[ϕ2], Rext[∃v. ϕ] = ∃v. Rext[ϕ].

(4) If ϕ is an extended regressable formula of the form Causes(b, t, φ, do(a, s)), then:

Rext[Causes(b, t, φ, do(a, s))] =

(time(s) = t ∧ b = a ∧ ¬φ[s] ∧ Rext[φ[do(a, s)]]) ∨

(time(s) > t ∧ φ[s] ∧ Rext[φ[do(a, s)]] ∧ Causes(b, t, φ, s)) ∨ (time(s) > t ∧ ¬φ[s] ∧ Rext[φ[do(a, s)]]∧

Causes(b, t, Poss(a) ∧ Rext[φ[do(a, s′ )]]-1 , s)).

(5a) The regression of the Know operator when α(⃗x) is not a knowledge producing action:

(5b) The regression of the Know operator when α(⃗x) is a knowledge producing action with sensed-fluent axiom SF (α(⃗x, e), s) ≡ ψ[s]:

Rext[Know(ϕ, do(α(⃗x, Suc), s))] = (ψ[s] ∧ Know (ψ ∧ P oss(α(⃗x, Suc)) ⊃ Rext[ϕ[do(α(⃗x, Suc), s′ )]]-1 , s)) ∧ (¬ψ[s] ∧ Know (¬ψ ∧ P oss(α(⃗x, Suc)) ⊃ Rext[ϕ[do(α(⃗x, Suc), s′ )]]-1 , s))

Cases 4 and 5 can be justified directly using Propositions 4 and 1 above. Intuitively, these reduce causes in scenario do(a, s) to that in scenario s via reasoning by cases and using the definition of causes and regression; 4 and reduce knowledge in do(α(⃗x, e), s) to that in s.

With this definition in hand, we now present our key result.

Theorem 6. If ϕ is an extended regressable formula and D is an NDBAT, then D |= ϕ iff DS0 ∪Duna |=R∗ext [ϕ].

The proof is similar to that of the knowledge regression theorem in [Scherl and Levesque, 2003], but uses Prop. 1 and 4. Example (cont'd). Let σ∗ = do([move(I0, I1,NotVul), move(I1, I2, Vul )], S0). Note that:

We can show the following:

Proposition 8 (Example: Regression of Causal Knowledge).

Rext [Know(¬φ1 ∨ ∃e.Causes(move(I0, I1, e), 0, φ1)), σ∗ )] = Know(∀e′ . Poss(move(I1, I2, e′ )) ⊃ ψ∗ , σ∗∗ ), where, σ∗∗ = do(move(I0, I1,NotVul), S0) and, ψ∗ = ¬(e′ = Vul ∨Vul) ∨ ∃e.[[time > 0 ∧ Vul ∧ Causes(move(I0, I1, e), 0, Vul )] ∨ [time > 0 ∧ ¬Vul ∧ e′ = Vul ∧ Causes(move(I0, I1, e), 0, Poss(move(I1, I2, e′ )) ∧ (e′ = Vul ∨ Vul ))].

Thus the robot's knowledge in σ∗ that ¬φ1 ∨ ∃e.Causes(move(I0, I1, e), 0, φ1) can be reduced to her knowledge in the previous situation σ∗∗ that for all environment reactions e′ for which the agent action move(I1, I2) is possible, ψ∗ holds, where the latter means that either e′ is NotVul and she is not currently vulnerable; or she is vulnerable, and move(I0, I1) (directly) caused Vul for some e; or she is not vulnerable, e′ is Vul , and for some e, move(I0, I1) caused move(I1, I2, e′ ) to be possible and make Vul hold afterwards.

4 Note that the formulae inside the context of Causes and Know are situation-suppressed. On the other hand, the regression operator Rext requires a situation argument. To deal with this, here we introduce a new situation variable s′ and use the φ-1 operator from [Scherl and Levesque, 2003] that suppresses the situation argument of φ by removing the last (situation) argument of all the fluents in φ. Thus, e.g., Rext [φ[do(α(⃗x, e), s′ )]]-1 introduces the situation term do(α(⃗x, e), s′ ) to the situation suppressed formula φ, performs the regression, and then suppresses the situation argument in the result.

Repeated applications of Rext yields a formula containing knowledge about S0 that can be checked against the initial state axioms and Duna in DK 1 .

5 Conclusion

Motivated by the utility of actual causality in multiagent systems and the nondeterministic nature of real world action and change, in this paper we studied reasoning about causal knowledge in the NDSC [De Giacomo and Lesp´erance, 2021]. We first adapted [Scherl and Levesque, 2003] to obtain a formalization of knowledge change and sensing in the NDSC. We then combined this with a previously proposed definition of causal knowledge in the deterministic SC [Khan and Lesp´erance, 2021] to obtain a formalization of causal knowledge in the NDSC. Finally, we also defined a regression operator in the NDSC to reason about causal knowledge.

Recently, Khan, Lesp´erance, and Rostamigiv [2025] studied actual causality in the non-epistemic NDSC. As well as system actions as causes, they considered agent actions as causes and showed that one can define two different notions of causes for the latter, "certainly causes" and "possibly causes". But unlike us they did not study knowledge update in the NDSC or investigate causal knowledge dynamics.

To the best of our knowledge, our formalization is the first to deal with causal knowledge in nondeterministic domains. The only other account of causal knowledge besides [Khan and Lesp´erance, 2021] that we are aware of is the one proposed by Chockler et al. [2015], who formalized causal knowledge while defining responsibility/blame in legal cases. In that framework, an agent's uncertainty of the causal setting is modeled using an "epistemic state", which is a pair (K, Pr), where K is a set of causal settings and Pr is a probability distribution over K. The proposal is based on structural equations [Simon, 1977], and thus has limited expressiveness [Glymour et al., 2010; Hopkins, 2005; Hopkins and Pearl, 2007]. Also, unlike us, they take events to be deterministic. In contrast, our framework is more expressive (first-order) and incorporates a formal model of domain dynamics and knowledge change. This allows for an interesting interplay between causality and knowledge. In addition, we incorporate nondeterminism and formalize reasoning about causal knowledge.

In this work, we focused on knowledge and not belief. The relation between actual causes, nondeterminism, and causal knowledge becomes more intricate if we incorporate the latter. Dealing with this is future work. Finally, in the future we would like to investigate reasoning that involves concurrent actions by multiple agents [De Giacomo et al., 2016] and define responsibility and blame using our formalization [Yazdanpanah et al., 2019; Naumov and Tao, 2020; Parker et al., 2023].

Acknowledgements

This work is partially supported by the National Science and Engineering Research Council of Canada, by the University of Regina, and by York University.