Causality, Constraints and Indirect Effects

1 Introduction

The goal of this paper is the formulation of a well­ founded solution to the ramification problem: the prob­ lem of determining the indirect effects of an action. The solution follows recent approaches that give causality a prominent role [McCain & Turner, 1997; Lin, 1995] but relies on a novel model of causal reasoning that is based on two simple ideas; namely that the values that a vari­ able may take are a function of the values of its causes, and that the form of that function is determined by the causal rules acting upon the variable. The model is closely related to models of causal reasoning based on Bayesian Networks (e.g., [Goldszmidt & Pearl, 1992; Darwiche & Pearl, 1994; Geffner, 1996]) and Structural Equation Models [Simon, 1953; Druzdzel & Simon, 1993; Pearl , 1996]) but does not appeal t.o probabilities or rankings of any sort. It also combines (propositional) action rules and causal rules in a clear manner, provides a simple way for determining when 'derived informa­ tion' can be assumed to persist [Myers & Smith, 1988;

·Mailing address from US and Europe: Hector Geffner, Bamco CCS 144-00, P.O.BOX 02-5322, Miami Florida 331025322, USA. E-mail: hector@usb.ve.

Giunchiglia & Lifschitz, 1995], and provides another per­ spective on the distinction between 'qualification' and 'ramification' constraints [Lin & Reiter, 1994].

The paper starts with the description of the causal model in Section 2, and proceeds in Section 3 with the model of actions and time. The two models are inte­ grated in Section 4 and two extensions are considered in Section 5. A brief summary closes the paper in Section 6.

2 Causality

The causal model provides a semantics for collections of causal rules defined over a simple language made up of two sets of symbols: variables and values. All atoms are of the from x = x, where x is a variable and x is a value. The language is the closure of all such atoms under the standard propositional connectives.

Each variable x has also a domain Dx of values. For example, the variable temperature may take values from the domain Dtemp = {high, medium, low}, distance may take values from Ddi·t = {1, 2, 3, ... , 10}, rain may take values from the boolean domain Drain = { t , f}, etc.

A state s is an interpretation that assigns to each vari­ able x a value x from its domain. We call x the deno­ tation of x in s and refer to it as x'. Atoms x = x are true in a state s when x' = x, conjunctions A 1\ B are true in s when both A and B are true in s, disjunctions A V B are true in s when A or B are true, etc. A state thus provides an interpretation for all formulas in the language, and is a model of a set. of formulas when it satisfies (i.e., makes true) each formula in the set.

Causal rules are of the form F --+ A where F is a formula and A is an atom. Causal rules express mechanisms by which the truth of F normally causes the truth of A [Simon, 1953; Druzdzel & Simon, 1993; Pearl, 1996]. Causal rules in which the truth ofF always causes the truth of A are written as F :::> A. We call the former, default causal rules and the latter strict causal rules.

For example, using the expressions x and ·x to ab­ breviate atoms of the form x = t and x = f for boolean variables x, a situation in which a car may fail to start due a dead battery can be modeled as:

turn_key --+ car ....starts dead_battery :::) -.car ...starts lights -+ dead_battery where the last rule says that a battery dies when the lights are left on for a long time.

The semantic problem in causal reasoning is the prob­ lem of characterizing in a meaningful way the conse­ quences that follow from a set C of causal rules possibly extended with a set 0 of observations (atoms). While the models of the resulting causal theories T = (C, 0) are the states s that satisfy the strict rules in C and the formulas in 0, not all such models can be considered. Defeasible causal rules in C must play a role as well yet it hasn't been clear what such role actually is.

For instance, the simplest idea of focusing on the models that violate minimal sets of defaults does not work. 1 Such account correctly predicts dead_battery from the observation lights but incorrectly retracts the prediction in the presence of the additional but irrel­ evant piece of information turn_key. This problem is avoided by approaches in which causal rules are regarded as one-directional rules of inference. 2 However, those approaches do not explain why reasoning 'forward' is of­ ten the right thing to do, nor when reasoning 'forward' may fail (as when the three atoms above are all true). An interpretation of causal theories that sheds light on this question is [Goldszmidt & Pearl, 1992), where causal theories are seen as describing a family of Bayesian Net­ works [Pearl, 1988) that make explicit the independences in the theory. Our model is related to [Goldszmidt & Pearl, 1992] but is simpler and more transparent as it also appeals to notions of independence but does not rely on either Bayesian Networks or rankings of any sort.

2.1 The Model

The model is based on two ideas that are very simple and appear in one way or the other in several accounts of causal reasoning (e.g. [Goldszmidt & Pearl, 1992; Darwiche & Pearl, 1994; Geffner, 1996]):

1. the values that a variable x may take in a given state s is a function of the value of the causes of x in s
2. the form of that function is determined by a stan­ dard interpretation of the rules that express causal influences over x

In order to formalize these two ideas, we express the set of causal influences acting on a variable x in a theory T = (C, 0) by Tx; i.e. Tx contains all the rules in C of the form F :::) x = x or F -+ x = x. We call Tx the (causal) microtheory for x. 3 The microtheories Tx will be used to determine the possible values of x in a given state s. We assume that no variable is its own cause; i.e., no rule involves the same variable in both its body and its head.

1 Strict and defeasible rules F -+ A are violated in a state s when s satisfies F but does not satisfy A.

2 This clirectionality can be defined procedurally as in in­ heritance hierarchies and logic programs or by means of a formalism like Reiter's default logic. .

3 These microtheories are similar to the ones considered in [Darwiche & Pearl, 1994] even if their use here is clifferent. Indeed, many of our micro theories are 'inconsistent' accord­ ing to the criterion in [Darwiche & Pearl, 1994].

We write sj[x = x] for x E Dx to denote the state that makes x = x true and is otherwise identical to s. We also say that a model sj[x = x] of the microtheory Tx is a minimal model of Tx when no other model sj[x = x'] of Tx violates a strictly smaller set of rules from Tx. The ideas above can then be expressed as follows:

1. for each variable x there is a function ¢x(s) ~ Dx, such that x E ¢x(s) means that xis a possible value of x given the causes of x that are true in s
2. the function ¢x(s) is such that x E ¢x(s) iff s/[x = x] is a minimal model of the microtheory Tx

If min is a function that takes a collection of states and returns the ones that violate a minimal set of defaults from Tx but no strict rules, then the definition of the functions ¢x above can be expressed equivalently as:

Default rules of different priorities can be accommodated in this definition by doing the mimization lexicographi­ cally (stronger rules first).

The functions ¢x, that we call causal functions, de­ termine the values that a variable x can take given the value of its causes. We say that a state s is a causal interpretation relative to a set of rules when the actual value of every variable x ins is compatible with the value of its causes; i.e., when x· E ¢x(s). We also say that s is a causal model of a causal theory T = ( C, 0) when s is a causal interpretation relative to C that satisfies the observations 0. We assume throughout that causal theories are consistent in the sense that ¢x ( s) is never empty.

The consequences of a causal theory T are the formulas that hold in all its (causal) models.

Example 1 The domain theory considered above involves four boolean variables: turn_key, lights, dead_battery and carLstarts. The microtheories for the first two variables are empty and hence from (1):

The microtheories for car ..starts and dead_battery, on the other hand, are given by the first two rules and third rule respectively, and hence:

Clearly the state s that makes:

is a causal interpretation, while the state s' that corre­ sponds to the 'unintended' model:

is not as 4>dead...battery(s') = {t} and thus dead_battery·' ¢ 4>dead...battery(s'). Indeed, the state s is the only causal interpretation that satisfies the observations 0 {turn....key, lights}, and thus s is the only causal model of the theory T = (C, 0).

2.2 Related Models

Theories of Action. The model above is a refinement of the minimal model semantics in which a single global minimization over the whole set of rules is replaced by multiple minimizations over the local microtheories Tx. Moreover, the local minimizations are done over a a fixed state s in which only the value of the variable x is al­ lowed to change. Something similar occurs in the re­ cent approaches to the frame problem. It is well known that if default rules are added for fluents and persis­ tence violations are minimized, the resulting semantics is too weak [Hanks & McDermott, 1987]. The most re­ cent approaches to the frame problem thus replace the global minimization by local minimizations in which the current state and actions are fixed, and the resulting state is allowed to change [Gelfond & Lifschitz, 1993; Reiter, 1991]. The result is that the action and persis­ tence rules get compiled into state transition functions that determine the states that can follow a given state s and action a, very much like causal rules above get com­ piled into the causal functions 4>x ( s) that determine the states of the variable x that can 'follow' a given state of its causes.

Bayesian Networks. The definition of the causal in­ terpretations s above involves a fixed point condition: s has to be such that the value x' of each variable x belongs to 4>x(s). This fixed point condition can be sim­ plified when the causal rules in the theory do not involve cycles. Indeed, let us define the. causes of x as any min­ imal set of variables causes(x) that shield x from all other variables; i.e., [causes(x)]' = [causes(x)]'' must imply 4>x(s) = 4>x(s'). Then it is easy to show that the function 4>x(s) can be replaced by an equivalent func­ tion ~x(causes' (x)) where the global state s is replaced by the local state of x's causes. Then if there are no causal cycles and thus the variables can be ordered into a sequence x11 x2 , ··· , Xn such no variable is preceded by one of its causes, the causal interpretations s can be computed iteratively by setting the value of each variable x;, from i = 1 ton, to any value x; E ~x,(causes'(x;)). Indeed, the model that results in this case is exactly a Bayesian Network in which probabilities are replaced by "' measures [Goldszmidt & Pearl, 1992] that are either 0 (plausible) or oo (impossible).

Structural Equation Models. In the presence of cycles, the resulting models cannot be interpreted as Bayesian Networks but as Structural Equation Mod­ els [Simon, 1953; Druzdzel & Simon, 1993]. Structural Equation Models are used widely in Economics and the Social Sciences and have the form of a set of simultane­ ous equations of the form:

where x; stands for the value of variable x;, f; is an er­ ror variable, and /; is a deterministic function. Such equations are called structural as their form is im­ portant: equations that are mathematically equivalent are no necessarily structurally equivalent. 4 Structural equations represent mechanisms that propagate exter­ nal perturbations on the right hand side variables to changes in the left hand side variable but not the other way around. For example, an structural equation like spending = income/2 + f predicts that doubling the income may double the level of spending but does not predict that doublin~ the level of spending will double the income (see also lPearl, 1996]).

The equation that defines our causal interpretations can be expressed in the form:

that is very close to (2) except that the function 4>x., unlike the function f; above, does not have to pick a single value for the variables x;.

Coherent Models. Some approaches to causal reason­ ing replace the notion of minimal models by the notion of coherent models [Geffner, 1992; McCain & Turner, 1997]). Roughly, a model is coherent when all default violations are causally explained. In our language, we can consider the violation of a default rule F ---+ A ex­ plained in a model s, when there is conflicting defeasible or strict rule F' ---+ A' that is 'active' in s, i.e., whose body and head both hold in s. It is very easy to show then that causal and coherent models coincide. In this sense, coherence considerations which otherwise appear somewhat ad-hoc, can be justified by the ideas that de­ fine the causal models.

3 Time and Actions

Many causal relations such as the action of toggling a switch cannot be modeled without a notion of time or context. In this section we focus on such causal rela­ tions and consider the interpretation of temporal causal rules of the form F ---t A where F and A are formulas and atoms as before. Strict temporal rules are written as F ==> A. The difference between a (non-temporal) causal rule F---+ A and a temporal (causal) rule F---+ A is that the former says that A is normally true in the state s when F is true in s, while the latter says that A is normally true in the state following s when F is true in s. The action of toggling a switch can be modeled by the temporal rules of the form (the notation is similar to [Gelfond & Lifschitz, 1993]):

4 Note that the same holds for 'qualification' and 'ramifica­ tion' constraints [Lin & Reiter, 1994]: they may be logically equivalent yet, for the same structural reasons, they behave in different ways. See Section 5.2.

The semantics of temporal rules involves sequences of states s0 , s1 , s2 , ... , called trajectories, where s; refers to the state of the world at time i. As before, the temporal interpretations will be the trajectories that interpret all variables x in a way that is compatible with the causal function ¢~ determined by the causal microtheory r; (we use the index t to express that we are dealing now with temporal rules only).

The microtheories r; are defined exactly as before as the collection of rules that express causal influences on x; namely the rules of the form F ---+ x = x and F ==> X= X.

These microtheories are interpreted by means of ex­ tended states of the form s//(x] = x, where s represents a state at some time point and x = x represents the value of x at the next time point. More precisely, an extended state s//[x = x] satisfies a temporal rule F ---+ x = x' if F' is false or x = x' is true.

The function ¢~ ( s) is defined as the set of values x E Dx for which the extended state s//[x = x] satisfies all strict rules in r; and violates a minimal set of default rules from r;. In analogy to ( 1):

Now x E ¢~(s) no longer means that x is a possible value of x in the state s, but a possible value of x in the states following s. This suggests that the temporal interpretations could be defined as the trajectories s0 , s1, s2, ... in which the condition x''+ 1 E ¢x(s;) holds for all variables x and all time points i > 0.

This actually captures the semantics of the rules but misses something important: the law of inertia that ex­ presses the tendency of certain variables, usually called fluents, to retain their values.

The persistence of fluents can be captured by extend­ ing the causal functions ¢~ ( s) into stronger functions ¢; ( s) in which the value x' of fluents is allowed to per­ sist when the rules in Tx provide no reason for a change.

More precisely we assume that the value of x persists when the rules in Tx do no discriminate among the values of x; i.e. when ¢~(s) = Dx. The extended or persistent causal function ¢>; for fluent variables x is thus defined as follows:

For non-fluent variables, ¢;(s) ~r ¢x(s).

With the functions ¢; ( s), the temporal interpretations can be defined in complete analogy to the causal inter­ pretations as:

Definition 1 A state trajectory s0 , s1 , ... is a temporal interpretation relative to a given set of temporal rules, if x' '+ 1 E ¢; ( s;) for each variable x and each time point i > 0.

3.1 Temporal Theories

The models of a temporal theory T = (D, A, 0) com­ prised of a set D of temporal rules, a set A of actions, and a set 0 of observations, are the temporal interpre­ tations (relative to D) that are compatible with both the actions A and the observations 0.

Actions and observations in temporal theories are en­ coded by means of temporal atoms of the form x[i] = x, where x is an action or fluent variable respectively, x belongs to Dx , and i is a time index (i.e., a non-negative integer) . For boolean variables x[i] = t and x(i] = f are abbreviated as x[i] or ....,x[i]. For simplicity, action variables are assumed boolean.

A trajectory s0 , St, ... is compatible with the observa­ tions 0 when x'' = x ifx[i] =xis in 0, and is compatible with the actions A when for all action variables x, x' · = t iff x[i] E A. 5

The consequences of a temporal theory are the tem­ poral atoms x(i] = x that are true in all models, where x(i] =xis true in a model s0 , s 1, ·.. , when x'' = x.

The model that results from these definitions is similar to several other models of action. Here we draw a simple comparison with the model A of Gelfond and Lifschitz [Gelfond & Lifschitz, 1993]. For simplicity we consider domain descriptions DA comprised only of actions rules 'A causes B if C' and initial conditions 'initially L'. 6 Such description can be expressed as a set D of temporal rules of the form AI\C ---+ B and a set 0 of observations L[O]. Then, it is easy to show that:

Theorem 1 A value proposition L after Ao, .. . An is entailed by DA iff L[n+ 1] follows from the temporal the­ ory T = (D, A, 0), where A= {Ao[O], A1[1], ... , An[n]}

Example 2: The YSP [Hanks & McDermott, 1987] can be encoded by means of two temporal rules of the form:

All variables are boolean, and load and shoot stand for actions. Given the observation alive[O] and the actions load[1] and shoot[3], ....,afive[4] follows. This is because ¢~oaded(s) = {t} iff load' = t or loaded' = t , while <t>:live(s) = {f} iff shoot' = loaded' = t or alive' = f. Then, since in all models so, s1, s2, ... , load and shoot are true in the states s 1 and s3 and false in all other states, we get that loaded' 1 must be true, loaded' 2 and loaded' 3 must also be true, and thus, alive'· must be false.

5 The double implication for actions captures that actions not included in A must be false. A similar 'closed world as­ sumption' for actions is implicit in approaches such as [Gel­ fond & Lifschitz, 1993; Reiter, 1991] in which actions are not represented as part of the state of the system.

6 We assume that the domain description is consistent in the sense that no pair of rules associated with the same action have antecedents that are jointly satisfiable and consequents that are jointly unsatisfiable.

4 Causal and Temporal Rules Combined

We consider now the combination of temporal (causal) rules and (non-temporal) causal rules. Namely the ex­ tended temporal theories that we consider now are of the form T = (D, C, A, 0) where (D, A, 0) stands for a temporal theory as before, and C stands for a set of (non-temporal) causal rules. Temporal and causal rules play the role of effect axioms and ramification constraints [Lin & Reiter, 1994] respectively.

For example, the scenario in [Kartha & Lifschitz, 1994] that involves two switches and a light that is 'on' when the switches are in the same position can be modeled by a theory with temporal rules:

The semantics of temporal theories extended in this way must combine the causal and temporal rules into a single causal function ¢; for each variable x. For sim­ plicity, we follow other formalisms and assume that all temporal rules are strict, and all variables are boolean. These two assumptions decouple the causal rules from the temporal rules, allowing us to define the persistent causal function ¢; for fluent variables x (that now takes two sucessive states Sp and Sc as arguments) as: 7

This definition assumes that fluent variables persist when neither the temporal or causal rules tell us other­ wise. The restrictions above can be removed by simply defining a causal function t/>x ( Sp, Sc) in terms of a single microtheory Tx that includes both causal and temporal rules.

Provided with the functions 4>:, and assuming that actions are exogenous (and hence that action variables do not occur in the head of rules), the resulting temporal interpretations can be defined as follows:

Definition 2 A trajectory so, s1, ... is a temporal in­ terpretation relative to a set of temporal rules and causal rules if for each variable x, x·o E ¢~(so), and x'i+l E ¢;(s;, Si+l) for each i 2:: 0.

The models of an extended temporal theory T (D, C, A, 0) are the temporal interpretations relative to the rules in D and C that are compatible with the ac­ tions A and the observations 0.

7 The conditions are to be evaluated top down.

and causal rules:

Example 3. Using the rules above, we prove that if sw1 and sw2 are initially true and false respectively, and the action toggle2 is done, then sw1 stays true, sw2 becomes true and hence on becomes true as well (see [Lin, 1995] for~ similar example) . Clearly, ¢;w 1 (s;,s;+!) = {t} iff either togglell\ --.swl or --.togglell\ sw1 is true in s;. Samething similar holds for ¢;w 2 ( s;, s;+l). Then since toggle2[1] must be the only true action in the trajectory, swl must remain true at all points, sw2 must become true at time 2, and thus on must too become true at time 2.

5 Extensions

5.1 Non-persistent Causation

Rieger and Grinberg [Rieger & Grinberg, 1977] develop a language for representing causal mechanisms that, among other features, includes two different types of cause-effect relations: continuous relations in which the cause has to remain present in order to sustain the ef­ fect (e.g., wet :::> hard_to_grasp) and one-shot relations in which the effect remains true even after the cause that triggered the effect has vanished (e.g., in_water :::> wet) . In our model we have not made this distinction, yet this distinction is often needed.

Consider for instance a scenario from [Myers & Smith, 1988] cited in [Giunchiglia & Lifschitz, 1995]: if an object is put on the table it becomes safe for the baby, yet if removed from the table it won't necessarily remain safe. Such a scenario can be modeled by the temporal rules:

and the causal rule:

When the action put is performed, on_table and safe be­ come true, but if later remove is done, on_table becomes false but safe remains true. That's clearly anomalous. The problem, using the terminology of Rieger and Grin­ berg, is that we are modeling all causal rules as one-shot rules, yet the causal rule on_table --+ safe is a contin­ uous rule; i.e., safe is true as long as on_table is true. We call such rules, non-persistent rules.

Assuming now that all (non-temporal) causal rules are non-persistent, and for simplicity, that all rules are strict, the definition (6) of the function 4>: can be changed to:

where a variable x is not assumed to persist in states where it could have been caused by a non-persistent causal rule. 8

8 More accurate definitions are possible but the one above is simple and fits naturally into the format of the previous definition (6).

In the example above, the new definition means that safe won't be assumed to persist in states s in which on_table holds. Yet if on_table persists so will be safe due of the rule on_table -+ safe.

5.2 Action Constraints

Strict causal rules of the form F ::::> A stand for a mech­ anism by which interventions to make F true make A true as well. Other type of expressions have the same logical form but do not have this property For exam­ ple, the constraint eat ::::> have_food is always true yet we don't expect have_food to become true by perform­ ing the action eat. In other words, eat ::::> have_food does not stand for any mechanism. Something sim­ ilar occurs with the so-called integrity constraints in databases like high_salary ::::> is_a_boss. Indeed, while causal rules express conditions that are self-enforcing in the model (i.e., they are assumed to be enforced by a mechanism), constraints like eat ::::> have_food and high_salary ::::> is_a_boss express conditions that must be enforced by the agent. For that reason we call the latter constraints action constraints (they correspond to the qualification constraints in [Lin & Reiter, 1994]).

In order to accommodate action constraints in our model, let us say that a theory T = (D, C, A, 0) complies with a set AC of action constraints if every state s; of every model so, s1 , ... ofT satisfies those constraints. If so, we say that the theory T' = (D, C, AC, A, 0) that re­ sults from incorporating those constraints is consistent. Otherwise we say that the theory is inconsistent.

Note that we do not prune the models that violate the constraints. When there are such models we simply de­ clare the theory inconsistent. This is to comply with the so-called 'causality principle' in system theory [Padulo & Arbib, 1974] by which (exogenous) actions should not have an effect on the past. This principle holds for con­ sistent theories but does not hold for inconsistent ones.

6 Summary

We have developed an approach to the ramification prob­ lem in terms of a simple and well-founded model of causal reasoning that is related to recent theories actions, Bayesian Networks and Structural Equation Models (see Section 2.2). A number of refinements and extensions that would be desirable are a more accurate model of non-persistent causation, constraints introducing inter­ actions among mechanisms (e.g., a rigid bar among two moving blocks), and a more expressive language.