In this paper we de ne the notion of causes of events in trajectories of dynamic domains from the standpoint of an agent acting in this domain. We assume that the agent's knowledge about the domain is axiomatized in P-log with consistency restoring rules { a powerful knowledge representation language combining various forms of logical and probabilistic reasoning. The proposed model of causality is tested on a number of examples of causal domains frequently used in the literature.
This paper contributes to a research program aimed at nding precise mathematical formalization of substantial parts of commonsense knowledge and developing commonsense reasoning methods in knowledge representation languages based on Answer Set Prolog (ASP). We concentrate on causal reasoning, which seems to be of vital importance for our understanding of the world. The nature of causality and various causal relations has, for a long time, been debated by philosophers, physicists, statisticians, researchers in AI, etc. For recent work see, for instance, [5,6,13,16]. But despite the amazing progress, we do not yet have fully adequate understanding of the subject. There are still di erent interpretations of the intuitive meaning of causality, answers provided to causal questions by various formalisms do not always match the intuition, and some \causal stories" simply cannot be expressed in existing languages. In our approach we address these problems by using rich knowledge representation language capable of expressing non-trivial causal relations as well as various forms of commonsense background knowledge. We opted for logic programming language P-log with consistency-restoring rules (cr-rules) [1,3,10]. It is an extension of ASP with well known methodology for representing defaults and their direct and indirect exceptions, recursive de nitions, probability, direct and indirect e ects of actions (including parallel and non-deterministic actions), time, etc. Its non-monotonic reasoning system combines standard ASP reasoning, abduction, and probabilistic computation. We are primarily interested in dynamic domains and, as in ? Copyright © 2020 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0). many theories of action and change, view the agent's knowledge base as a description of possible trajectories of the domain. The events in these trajectories are caused by actions. This is di erent from a large body of work in which the agent's knowledge is represented by structural equations, causal logic or other formalisms emphasizing purely causal reasoning at the expense of background knowledge. Usually, but not always, these works provide counterfactual account of causality. There is, however, a number of recent approaches (see, for instance, [4,7,8,14]) which seem to share our philosophy. There are, however, many substantial di erences related to the power of our KR-language and other factors. The multiplicity of interpretations of the word cause is partially addressed by concentrating on what is often referred to as actual causes. In our approach time (or at least ordering of events) is an integral part of this notion. We further deal with this problem by dividing causes of events into those which consist of deliberate actions, those which contain at least one accidental (but known) action, and those which include some exogenous actions not native to the agent's model of the world. The methods of testing our de nitions and KR methodology are determined by our goal. We view our work as a step in an attempt to pass what J.Pearl calls Mini-Turing Test [17]: \The idea is to take a simple story, encode it on a machine in some way, and then test to see if the machine can correctly answer causal questions that a human can answer." So, naturally, we use this to test accuracy of our modeling and relationship with other approaches. (Of course, only a few of such examples are presented in this paper.) To make sure that wrong answers to these questions are not caused by inadequate representation of the problem, we pay serious attention to developing KR methodology which properly combines causal and background knowledge about the domain. The paper is organized as follows. We assume some knowledge of P-log and dene notions of background theory T and scenario S. The former contains general knowledge about the domain while the latter describes a particular story to be analyzed. Together they form the knowledge base of an agent, T (S), referred to as causal theory. Next section contains de nitions of three types of causes accompanied by some explanatory examples. This is continued by analyses of causal relations in several simple stories, followed by conclusion and future work. 2
Knowledge of an agent will be represented by a P-log program tailored for reasoning about e ects of actions and causes of events, Regular function symbols of a program will be partitioned into uent, action, static and auxiliary and used to form uent, action, static and auxiliary terms respectively. We assume that actions are Boolean. The last parameter of functions from the rst two groups is of a special sort called time-step (usually represented by natural numbers); timesteps are not allowed in statics. Recall that P-log terms formed by random are of the form random(m; f (x); p). This expression can also be viewed as an atom (a shorthand for random(m; f; p) = true), which states that, as the result of a random experiment m which is either genuine or deliberately interfered with, f (x) should take the value from fY : p(Y ) \ range(f )g. In addition, we require that for every time steps t1 and t2 occurring in m, f respectively, t2 > t1 if f is a uent, and t2 t1 if f is an action. Finally, both m and random(m; f (x); p) are viewed as action terms. Sometimes we say that f (x; t) is an instance of abstract uent (action) f (x) and that the value y of f (x; t) is the value of abstract uent (action) f (x) at time-step t. Atoms formed by action terms are called action atoms. Similarly for uent and static atoms. We are especially interested in properties of events { statements describing occurrences of actions and values of uents at given time-steps. More precisely an action event is a collection of action atoms. Similarly for uent events. An event is a uent event or an action event. The causal theory representing the agent's knowledge consists of a particular story (also called domain scenario or recorded history of the domain) to be analyzed and background theory representing agent's general knowledge. Scenario is a recorded history of time-stepped observations and deliberate (intended) actions which happened in the domain up to the current time-step. The initial time-step of a scenario is usually assumed to be 0. Observations are expressions of the form obs(atom), actions are of the form do(a(x; t) = y); do(a(x; t) = true) indicates a deliberate execution of action a(x; t); do(a(x; t) = f alse) { a deliberate refusal of such execution. Another form of do-operator is similar to do-operator of the original P-log [3] and Pearl's causal networks [16]. If random(m; e(x; t); p) is a random experiment and y is a possible value of e(x; t) then do(m; y) represents an intervention into random experiment m which forces e(x; t) to take value y. If the value y of e(x; t) is simply observed this is recorded as obs(e(x; t) = y). Whenever possible, we omit do from the description of actions in our scenarios.
Background theory is a P-log program T which contains no deliberate actions and observations and whose regular part (obtained from T by removing cr-rules) is consistent. T contains a set of causal mechanisms or causal laws of the form m : a(x) = y body; not ab(m); not interf ere(a(x); y)1 ( ) if a is an action and m : a(x) = y body; not ab(m) if a is a uent. In both rules body is non-empty and contains no default negation, m is the mechanism's name, ab and interf ere are auxiliary functions; interf ere(a(x); y) holds if action a(x) is deliberately assigned value di erent from y; ab(m) captures indirect exceptions to m. Each causal mechanism is accompanied by Contingency Axiom
ab(m) + body 1 If a(x) is formed by random(r; f (u); p), then m is omitted and the causal mechanism is named r. Random experiments are normally named by action terms. If the causal mechanism is not defeasible, then the contingency axiom and the corresponding \not ab(m)" from the body of a causal law can be omitted. Intuitively, the rst two rules say that normally body is a su cient cause for head. The guard interf ere(a(x); y) present in rule ( ) allows deliberate actions to defeat triggering defaults. We will use shorthand interf ere(a(x)) to denote interf ere(a(x); true). The Contingency Axiom for n allows causal mechanism m to be defeated by observations. It is a consistency-restoring rule of a version of ASP called CR-Prolog [2]. It says that \causal mechanisms m may be disabled, but such a possibility is very rare and, whenever possible, should be ignored". For more details, see [9]. In addition, a rule r of a causal theory must satisfy the following conditions: { If a time-step t occurs in r then some time-step occurs in head(r). { If t occurs in head(r) then (a) if head(r) is a uent atom then time-steps of uents and actions in body(r) do not exceed t and t 1 respectively, (b) if head(r) is an action atom then no time-step in body(r) exceeds t. Let us illustrate the notion of causal theory by formalizing two informal examples frequently used in the literature on causation.
Example 1 (Firing Squad). A certain chain of events is required for a lawful execution of a prisoner. First, the court must order the execution. The order goes to a captain, who signals the soldiers on the ring squad (denoted by a and b) to shoot. We'll assume that they are obedient and expert marksmen, so they only shoot on command, and if either of them shoots, the prisoner dies. Background theory F S for this example contains abstract actions court order, captain order, shoot(a) and shoot(b), inertial abstract uent dead and standard auxiliary symbols ab and interf ere. F S consists of causal mechanisms: [m1(T )] : captain order(T + 1) court order(T ); not ab(m1(T )); not interf ere(captain order(T + 1)) (1a) which is a defeasible version of dynamic causal law used in actions languages. Two other rules: [m2(G; T )] : shoot(G; T + 1) captain order(T ); not ab(m2(G; T )); not interf ere(shoot(G; T + 1)) [m3(G; T )] : dead(T + 1) shoot(G; T ); not ab(m3(G; T )) are defeasible triggers. We also have the contingency axioms:
ab(m1(T )) + court order(T )
ab(m2(G; T )) + captain order(T )
ab(m3(G; T )) + shoot(G; T )
(1b)
(1c)
(2a)
(2b)
(2c)
(3a)
(3b)
(3c)
(
:shoot(G; T ) :captain order(T ) :court order(T ) not shoot(G; T ) not captain order(T ) not court order(T ) The CWA for deliberate action court order will be accompanied by an indirect exception:
court order(T ) + We also need inertia axioms for dead: :dead(T + 1) dead(T + 1) :dead(T ); not dead(T + 1) dead(T ); not :dead(T + 1) Despite the fact that the story insists that the guards only shoot on command, the corresponding causal law is defeasible. This is essential since we would like to consider scenarios in which guards may refuse to follow the orders or simply fail to do so by unspeci ed reasons. Similarly for other causal mechanisms. Example 2 (Flipping a Coin). Theory T C has \transient" uent agreed to play (players agreed to start the game), and a \transient" uent h (the coin landed heads). Transient uents are partial functions which do not satisfy inertia. T C also contains action f lip ( ip the coin); h is de ned at time-steps immediately following f lip. Causal mechanism random(f lip(T ); h(T + 1)) agreed to play(T ); not ab(m(T )); not interf ere(random(f lip(T ); h(T + 1))) states that agreed to play triggers a random experiment f lip which ends in heads or in tails. We also need the contingency axiom and CWA for actions. Agent's knowledge base and its models: A scenario S is encoded in P-log as follows: obs(A), where A is time-stepped by 0 is encoded by A; if the time-step of A is greater than 0 then obs(A) is encoded by a constraint: \ not A". Dostatements of S remain unchanged. We denote this encoding by enc(S). Agent's knowledge base is given by causal theory
T (S) =def T [ enc(S) [ DO where S is a scenario of T and DO is a collection of axioms enforcing the intuitive meaning of do: { for every do(a(x; t) = y) from S axioms: a(x; t) = y
do(a(x; t) = y) where the former axiom connects do with an actual occurrence of an action, and the latter allows a deliberate action interfere with a defeasible trigger assigning values to action a(x); { for every do(m; y) from S, where m is the name of random experiment random(m; a(x; t); p), axioms do(m; a(x; t); y)
do(m; y) where the former axioms guarantees that on random experiments do coincides with the original do of P-log and the latter de nes interference with random experiments.
We only consider S for which T (S) is a coherent P-log program in which multiplicity of models can only be a result of general axiom (19) from [1] for random. As any such program, T (S) comes with the de nition of its possible worlds and probability function. A possible world W of T (S) can be viewed as a possible trajectory of a dynamic system associated with the program and written as W = h (tf ); (tf ); : : : ; (i); (i); : : : (tl 1); (tl)i where (i) is the set of all action events from W time-stepped by i and (i) is the set of all uent atoms of W time-stepped by i and statics from W . Note that though all actions from (i) start at i, their e ects may manifest themselves at di erent time-steps.
De nition 1 (Model). A model of scenario S of T is a possible world of T (S).
Let us demonstrate this notion by going back to the Firing Squad example.
Example 3 (Firing Squad: models). Let us x F S from Example 1. Then, in the
model of the scenario S0 = hobs(:dead(0))i the prisoner is alive at every time
step of the model. There are no actions. Scenario
S1 = hobs(:dead(0)); court order(0)i has one model, M 2:
:dead(0); court order(0), :dead(
Scenario S2 = hobs(:dead(0)); court order(0); :shoot(a; 2); :shoot(b; 2)i is more
interesting. Deliberate actions :shoot(a; 2); :shoot(b; 2) from S together with
axioms from DO cancel axiom m2(G; 2). The only model M of S2 contains
:dead(0); court order(0), :dead(
Example 4 (Flipping a Coin (Models)). It is easy to see that all models of
scenario S0 = hagreed to play(0)i contain random(f lip(0); h(
Our framework is based on the following assumptions: An agent is supplied with a ( xed) background theory T and a scenario S with the last time step n, which consists of observations and the complete collection of deliberate actions which occurred in the domain up to that time. In addition, we assume that every uninterrupted random experiment of a scenario is immediately followed by the observation of its outcome. Scenarios which do not satisfy these assumptions will be called illegal. In what follows we introduce three di erent types of cause: deliberate, accidental and exogenous. The best explanation of an event is given by nding its deliberate cause. If this is impossible we attempt to nd causes which include accidental (not deliberate) actions. As the last resort we allow causes containing unknown exogenous actions.
Deliberate Cause: Our de nition of a deliberate cause can be viewed as a formalization of the following intuition: \A cause of e(x; k) = y is a deliberate action event which initiates a chain of events bringing about e(x; k) = y. Moreover, must be in some sense minimal, i.e. no parts of can be removed without loss of causal information about e(x; k) = y." An expression \chain of events" from our informal description will be modeled by notion of proof 3 M be a set of ground literals, and M = fnot l : l is not satis ed by M g.
{ A sequence P = hr0; l0; r1; l1 : : : ; rn; lni where ls are literals from M and rs are rules or names of random experiments of program is called a proof of ln in M from (M; ` ln) if
For every i, body(ri) is satis ed by fl0; : : : ; li 1g [ M , li is the head of ri or li is e(k) = y and li 1 is random(n; e(k); p) representing a non-interrupted random experiment (i.e., there is no y such that do(n; e(k) = y) is in S), ri is n, and p(y) 2 fl0; : : : ; li 1g
No proper sub-sequence of P satis es the above conditions.
If M is a possible world of we simply say that P is a proof of ln in M ; { A scenario S of background theory T derives event e(k) = y in M (or simply T (S) derives e(k) = y) if there is a proof of e(k) = y in M from T (S); S derives e(k) = y if S derives e(k) = y in every model of S.
The idea of a deliberate (or intentional) action is formalized as follows. De nition 3 (Deliberate Action). Let S0 be the result of removing action event a(i) = y from a scenario S of T . We say that a(i) = y is deliberate in T (S) if no model of S0 contains a(i) = y.
To de ne a cause of an event e(k) = y in a scenario S of T we introduce a notion of the event's in ection point - a time-step i k such that i 1 is the last time-step of S in which the value of e(k) is not predicted to be y. To make this 3 A similar notion of a proof is given in [7]. Important and substantial di erences include special treatment for P-log literals formed by do and random, literals with default negation, and cr-rules. precise we need some notation: Let S[i] consists of observations of S made at points not exceeding i and all actions S which occurred at steps not exceeding i 1, i.e. S[i] =def fobs(f (j) = y) 2 S : j ig [ fa(j) = y 2 S : j < ig. De nition 4 (In ection Point). Step i is the in ection point for e(k) = y in T (S) if (a) T (S[i 1]) does not derive e(k) = y and (b) for every j 2 [i; k], T (S[j]) derives e(k) = y.
De nition 5 (Deliberate Cause). Let S be a scenario of T , obs(e(k) = y) 2
S, M be a model of S generated by a (possibly empty) abductive support R,
and i be the in ection point of e(k) = y in T R(S). A non-empty set of actions
from S is called a cause of e(k) = y (with respect to T (S)) in M if
(a) T R(S[i 1] [ ) derives e(k) = y in M ,
(b) for every there is a proof of e(k) = y from T R(S[i
which is not a proof of e(k) = y from T R(S[i 1] [ ) in M .
Consider scenario S1 from Example 3. Clearly, the in ection point for dead(
Causes Containing Accidental Actions. To see the need for causes with
accidental actions consider scenario S4 = fobs(:dead(0)); obs(dead(
Execution of a non-deliberate (accidental) action could be a part of an event's cause if it's deliberate execution could.
One should, however, be careful in formalizing this intuition. An attempt to do
that by simply adding the action to the original scenario does not work. Since
court order is derived by F S in the model of S4, it is not deliberate in scenario
S5 = S4 [ fcourt order(0)g and hence such a scenario is not legal.
One way to avoid the di culty is to remove from F S rule (
De nition 6 (Causes Containing Accidental Actions). Given a model M
of scenario S of T and action event M , is an accidental cause of e(k) = y
in M with respect to T (S) if there is an action event M such that
{ M is a model of scenario S =def S [ c( ; M ) of T1 = surg(T; ) (Note that,
by construction, all actions of S are deliberate), and
{ is a deliberate cause of e(k) = y in M with respect to T1(S ).
Now let us go back to scenario S4 from Example 3 and show that the cause of
dead(
To see how the de nition works for random events consider the unique model
M1 of scenario S1 = hobs(agreed to play(0)); obs(h(
The di erence between Pearl's actions and observations is important not only for computing probability of events but also for discovering their causes. So far, we have been looking for causes of events occurring in a model M among actions from M . Now we allow to search for causes among a speci c type of actions not present in M .
If an event has no cause consisting of deliberate and accidental actions
then it may be useful to admit causes containing unknown, exogenous
actions responsible for bringing about events in the initial state of the
scenario and/or abnormality relations in causal mechanisms of the theory.
The de nition is omitted due to space limitation. We simply illustrate the
intended behavior. Consider scenario S0 = hobs(:dead(0)); obs(:dead(
This example, often used to highlight di culties with counterfactual approach to causation, (see, for instance, [12]) deals with so called \late preemption". Example 5 (Breaking the Bottle). Suzy and Billy both throw rocks at a bottle. Suzy's rock arrives rst and shatters the bottle. Billy's arrives second and so does not shatter the bottle. Both throws are accurate: Billy's would have shattered the bottle if Suzy's had not.
The background theory, T S of the story, with steps ranging from 0 to 2 contains
actions throw(suzy) and throw(bill) with static attributes duration(suzy) =
1 and duration(bill) = 2 for durations of agents' throws, causal mechanism
m(A; T1)
shattered(T2)
throw(A; T1); duration(A) = D; T2 = T1 + D;
:shattered(T2 1); not ab(m(A; T1))
determining the e ect of throwing, contingency axiom for this rule and the
inertia axiom for shattered. Consider scenario
S0 = hobs(:shattered(0)); throw(suzy; 0); throw(bill; 0)i. The only model M0 of
S0 is: f:shattered(0); throw(suzy; 0); throw(bill; 0); shattered(
M1 = M0 [ f:shattered(
Example 6 (Hall's Neuron Net). Consider a neuron net from Figure 1. a c f d b If a link from neuron n1 to neuron n2 is ended by an arrow, then n1 stimulates n2; if it is ended by a bullet, then n1 inhibits n2; e is a \stubborn" neuron, requiring two stimulatory signals to re. For other neurons one stimulating signal is su cient.
A background theory N N for this example will have sorts for neurons, an action stim(S) which stimulate neurons from set S, Boolean uents stimulated and inhibited, and statics link and stubborn. The net will be represented by a collection of atoms link(a; d; stm), link(a; f; inh), etc., where link(X; Y; stm) / link(X; Y; inh) indicates that X stimulates/inhibits Y , and facts stubborn(e) [ f:stubborn(N ) : N 6= eg. We will need two time steps: 0 and 1 with 0 being used for the execution of actions and 1 for their e ects, and two inputs of action stim: s1 and s2 de ned by statics: member(c; s1), member(c; s2), member(a; s2). The causal mechanisms of N N are [m0(X; S)] : stimulated(X; 1)
stim(S; 0); member(X; S) [m1(X; Y )] : stimulated(Y; 1) [m2(Y )] : stimulated(Y; 1) :stubborn(Y ); :inhibited(Y; 1); link(X; Y; stm); stimulated(X; 1) stubborn(Y ); :inhibited(Y; 1); cardfX : link(X; Y; stm); stimulated(X; 1)g > 1 [m3(X; Y )] : inhibited(Y; 1)
link(X; Y; inh); stimulated(X; 1) We assume that all neuron directly stimulated by stim are included in its parameter S, which eliminates the possibility of parallel stim actions, i.e. we have :stim(S1; I)
stim(S2; I); S1 6= S2 Finally, we need the inertia axiom for the uents, and CWA with indirect exceptions for action stim: :stim(S; 0) not stim(S; 0) and stim(S; 0) + : Let us consider N N together with a scenario S0 = init [ fobs(stimulated(e; 1))g where init = fobs(:stimulated(X; 0)); obs(:inhibited(X; 0)) : neuron(X)g. The regular part of N N (S0) is inconsistent. There are two ways to restore consistency using the cr-rule, and therefore two models of S0: M1 containing stim(s1; 0) in which e is stimulated via neurons c, f , and b and M2 which contains stim(s2; 0). In M2 neuron f is inhibited and e is stimulated via neurons a, c, d, and b. Clearly, in the rst model stimulated(e; 1) is caused by stim(s1; 0) and in the second by stim(s2; 0). Hence in S0, stimulated(e; 1) has two possible causes. One can argue that stim(s2; 0) shall not be an actual cause of stimulated(e; 1) in S0 since there is a better \minimally su cient" candidate stim(s1; 0). Indeed, since s1 s2, action stim(s1) is simpler than stim(s2) but we believe that this does not preclude stim(s2; 0) from being viewed as a valid possible cause of stimulated(e; 1) in S0. This seems to agree with the Hall's view.
Example 7 (Adopted from [15] to our language).
Consider background theory with actions e1; e2, inertial uents d1; d2,d3, l, causal mechanisms: and inertia axioms for uents. Consider scenario:
S = fe1(0); e2(0); obs(:d1(0)); obs(:d2(0)); obs(:d3(0)); obs(:l(0))g
Our de nition agrees with the author of [15] and produce two causes of l(
The paper outlines a new approach to analyzing causes of events in trajectories of dynamic domains. The fuller version, available from https://www.depts. ttu.edu/cs/research/krlab/documents/causal2020 extended.pdf, contains more examples and a more detailed comparison with other approaches. In future, we plan to conduct some mathematical investigation of causal theories. Even though in some respects our formalism is a more powerful modeling tool than that of structural equations and graphical models advocated by Pearl and many others it remains to be seen if it can also expand their computational power.