Preferential Semantics for Causal Systems

1 Introduction

One of the cornerstone developments in the field of reasoning about action (and nonmonotonic reasoning) was Shoham's preferential semantics [Shoham, 1988]. While work in this area has since progressed, preferential semantics remain an important and intuitively appealing concept. It furnishes a se­ mantics for a class of nonmonotonic logics. Under this idea The principal aim of this paper is to determine whether it is possible to supply McCain and Turner's causal theory of actions with a preferential-style semantics. More specifi­ cally, the contributions of this paper are as follows. We show that it is not possible to characterise McCain and Turner's causal theory via a traditional preferential semantics applied to interpretations of the original (unaugmented) language. We rectify this, not by abandoning preferential semantics but by augmenting it with a further relational structure. A similar re­ sult was sought by Peppas et al. [Peppas et al., 1997] but the counterexample they present assumes a transitive and total ordering where we only assume. transitivity, and the se~an­ tics they develop only charactenses a subset of the possible McCain and Turner causal systems whereas the semantics we present captures all.

In arriving at this result we introduce two state-selection mechanisms: state elimination systems and state transition systems. State transition systems enhance a preference struc­ ture, based on symmetric difference, with a binary relation on states. State elimination systems function as a way of tying together McCain and Turner causal systems and state transi­ tion systems. Both state elimination systems and state tran~i­ tion systems give a clearer insight into the nature of causality at play in McCain and Turner's causal theory of actions.

The results contained herein are significant on a number of fronts. They allow us to gain a deeper understanding of the nature of causality underpinning McCain and Turner's frame­ work. They also permit us to place McCain and Turner's causal theory in the context of other nonmonotonic logics whose semantics make use of preferential structures. It has previously been suggested that minimal change and causal­ ity are interreducible (for instance [Gustafsson and Doherty, 1996]). However, such works make use of an expanded lan­ guage. In doing so they move away from the ideal of a con­ cise solution to the frame and ramification problems. We, on the contrary, claim that minimal change and causality can co­ exist in separate roles and, moreover, can complement each other.

This paper is structured as follows. In the next two sections . we shall outline some basic terminology and notation fol­ lowed by a brief overview of McCain and Turner's [McCain and Turner, 1995] causal theory of action. In section 4 we shall show that it is not possible to supply a straightforward preferential semantics to capture McCain and Turner's ap­ proach. The solution we suggest here is not to abandon pref­ erential semantics entirely but rather to augment it. In sec­ tions 5-7 we investigate the different state selection mecha­ nisms, giving the desired result. We end with a discussion of the significance of these results and our conclusions.

2 Technical Preliminaries

Throughout this paper we shall be working with a fixed fini­ tary propositional language £ whose propositional letters we shall callfiuents. The set of all fluents is denoted by :F. A lit­ eral is a fluent or the negation of a fluent. A state (or world) is defined as a maximal consistent set of literals. The set of all literals will be denoted N. The set of all states will be denoted W. By [1>] we denote all states consistent with the sentence¢> E £ (i.e., [ ¢>] = { w E W : w f- 1>} ). Occasionally we will refer to[¢>] as the ¢>-states (or ¢>-worlds).

3 Causal Systems

In this section we briefly review McCain and Turner's [Mc­ Cain and Turner, 1995] causal theory of actions. In so doing we shall introduce some further notation that will be useful for the remainder of the paper.

As outlined above, McCain and Turner introduce a new connective => to stand for the existence of a causal relation­ ship between sentences ¢> and '¢ of the underlying language £. This allows for expressions of the form ¢> => '¢ (where ¢>, '¢ E £) 1 which are termed causal laws (or casual rules). 2 A set of causal laws D is referred to as a causal system. Given any set of sentences r ~ £and a causal system D, the (causal) closure off in Dis denoted Cv(f) and defined to be the smallest superset of r closed under classical logical con­ sequence and such that for any 1> => '¢ E D, if 1> E Cv(f), then'¢ E Cv(f). We also say that r causally implies 1> with respect to D if and only if¢> E Cv (f) and denote this frvv1>·

Another notion that will be of importance is that of a legit­ imate state with respect to a causal system D. Any stater is legitimate with respect to D if and only if r = Cv(r) n N. That is, a state is legitimate if and only if it does not contra­ vene any causal laws of D. The set of legitimate states with respect to Dis denoted by Legitv.

McCain and Turner's aim is to determine the set of possible next (or resultant) states Resv(E, w) given an initial state w and the direct effects (or post-conditions) of an action repre­ sented by the sentence E. 3 Formally speaking, we have for any causal system D a function Resv mapping a legitimate (initial) state w and sentence E (direct effects) to the set of states Resv(E, w) according to the definition [McCain and Turner, 1995]:

We often refer to the elements of Resv(E, w) as causal fixed-points. Note that it follows from this definition that if r E Resv(E, w), then r E [E] (i.e., r must satisfy the di­ rect effects of the action). Intuitively speaking, the elements of Resv(E, w) are simply those E-states where all changes with respect to w can be justified by the underlying causal system.

We are now in a position to state our aims more clearly. The desire is to mimic McCain and Turner's fixed-point def­ inition using a preference ordering over states and in such a way as not to introduce auxiliary sentences into our language. More specifically, we wish to investigate whether this is at all possible; whether we can provide a preferential-style seman­ tics characterising Resv ( E, w) for any legitimate state wand sentence E.

1 Note that nesting of=> is not permitted.

2 For the sake of simplicity we shall assume here that the an­ tecedent of any causal law is consistent.

3 We shall refer to actions only through their direct effects as they play no direct role in McCain and Turner's framework.

4 Impossibility Results

In this section we clearly specify what we mean by a preferen­ tial semantics. We then present an impossibility result show­ ing that a traditional preferential semantics is not capable of characterising McCain and Turner's fixed-point definition.

We are given an initial state w E W and a (strict) prefer­ ence ordering <w~ W x Won states. The only restriction we place on <w is that it satisfy transitivity. Adhering to the essence of preferential semantics [Shoham, 1988] we seek to define those states resulting from the occurrence of an action with direct effects Eat initial state w as the minimal E-states under <w. The following condition expresses these desider­ ata:

Now, according to McCain and Turner, there is no need to consider illegitimate states as possible resultant states since they contradict the causal laws. Hence, we begin by focusing on a variant of condition (P):

We are now in a position to state a fundamental result of this section; that, in general, it is not possible to satisfy the condition (P') (with transitive <w ). Note firstly that a non­ triviallanguage is one with at least three ftuents.

Theorem 4.1 (First Impossibility Theorem)

Given a non-trivial language .C, there exists a causal system V and (initial) state w E W such that no ordering <w on states (generated by .C) satisfies (P').

Proof: Assume that .C has three propositional letters a, b, c. Let the initial state be w = {a, b, c} and define s1, s2, s3 and s4 to be the following states: s1 = { ·a, b, c }, s2 = {a, ·b, c}, s3 = {·a, ·b, c} and s4 = {·a, b, ·c}. Finally let V be the following causal system: V = { ·at\ c => ·b, ·b !\ c => ·a, ·a !\ b => ·c }.

Consider now the following direct effects (post-conditions) of actions . .6.1 = ·a !\ c, .6.2 = ·b !\ c, .6.3 = (b f-t ·c) and .6.4 = (/\ s1) V (/\ s2) V (/\ s3) V (/\ s4). Clearly, states s1 and s3 satisfy .6.1; s2 and s3 satisfy .6.2; 83 and s4 satisfy .6.3; and all four states s1, s2, s3, s4 satisfy .6.4.

Suppose a (transitive) ordering on states <w satisfying condition (P') exists. Now, the following is easily (albeit te­ diously) verified. Resv(.6.1, w) = {s3} from which we con­ cludes1 <f.w s3.Resv(.6.2, w) = {s3},therefores2 <f.w 83. Resv(.6.3, w) = {s3, {a, b, ·c} }, therefore s4 <f.w s3. Finally, Resv(.6.4, w) = {s4} from which it follows that (s1 <w s3) V (s2 <w s3) V (s4 <w s3). This leads us to a contradiction. ·

The following impossibility result now follows quite straightforwardly and is more appropriate for our purposes given that condition (P) is a more faithful rendering of the spirit of preferential semantics than condition (P'). It allows us to conclude that a traditional preferential semantics (cap­ tured by condition (P)) cannot, in general, be given to McCain and Turner's causal theory of actions.

Theorem 4.2 (Second Impossibility Theorem)

Given a non-trivial language .C, there exists a causal system V and (initial) state w E W such that no ordering <w on states (generated by .C) satisfies (P).

We shall not give away preferential semantics entirely however. Our aim now becomes to retain as much of pref­ erential semantics as possible and include a further mecha­ nism to capture the influence of causality. To this end we in­ vestigate separate (though related) mechanisms for selecting possible resultant states.

5 State-Selection Mechanisms

Taking a step backwards for a moment, we can simply view McCain and Turner's approach as a state-selection mecha­ nism. More specifically, McCain and Turner's causal the­ ory of actions, given some domain knowledge in terms of a causal theory V, specifies a way of selecting a subset Resv(E, w) of [E] given an initial state wand direct effects E. Resv(E, w) returns exactly those states that are possible upon the occurrence of an action with direct effects E at state w.

Viewing this as a selection function however, we consider Resv(E, w) to be a function selecting the 'best' states from among [E] (with respect to w). This is the view we shall adopt here in presenting two further state-selection mecha­ nisms: state elimination systems and state transition systems. State transition systems will provide the augmented preferen­ tial semantics we seek in terms of our aims.

This desired result is achieved in two steps. We begin by showing how to intertranslate McCain and Turner causal sys­ tems and state elimination systems in a way that preserves the selection process. We then show how to intertranslate state elimination systems and state transition systems (again preserving the selection process). In truth, we could do away with state elimination systems and simply translate directly between causal systems and state transition systems. How­ ever, we choose not to do so because it simplifies the proofs and provides further insight into the nature of causality cap­ tured by McCain and Turner's approach.

6 Mechanism 1: State Elimination Systems

In this section we describe our first state-selection mech­ anism: state elimination systems. The underlying idea is to use state elimination rules to discard E-states from fur­ ther consideration for we have noted above that in Mc­ Cain and Turner's [McCain and Turner, 1995] causal theory Resv(E, w) ~ [E]. A state rejected or eliminated by a state elimination rule is one which contravenes a causal relation­ ship deemed to hold in the resultant state (in fact, in the causal system,as a whole).

Definition 6.1 (State elimination rule)

A state elimination rule (or simply, elimination rule) is an ex­ pression ofthefonn {rb r2, · · ·, Tk> Tk+l· · · ·, rn} C> {rb r2, · · ·, rk} where each Ti is a state.

A state elimination systemS is a set of state elimination rules. An elimination rule functions by rejecting certain states from among those currently considered possible. Suppose that ac­ cording to an agent's current beliefs it considers the states that are possible to be among { r1 , · · · , r n}. An elimination rule like that in Definition 6.1 allows the agent to reject states Tk+l>'' ', Tn.

Let us briefly consider the mechanics of a state elimination system. At any point we are working with the set of states currently being entertained (a subset of [E]). We repeatedly apply elimination rules to this set of states to reject the ille­ gitimate ones (those not possible) focusing on the possible resultant states. All elimination rules need to be applied until no further states can be rejected to ensure that all illegitimate states have been purged and only definite possibilities remain. To put it another way, a state elimination system acts as a fil­ tering mechanism; illegitimate states are successively filtered out through use of elimination rules.

Definition 6.2 (~and ~ )

In a state elimination system S, we shall say that a set of states Q yields a set of states R in one step, denoted by Q ~ R, iff there exists an elimination rule Xt>Y such that Q <; X and R = Q n Y. We define ~ to be the reflexive transitive closure of~.

After the application of certain elimination rules we find that any further application does not result in the rejection of additional states. At this point we reach a compact set of states; a point of equilibrium.

Definition 6.3 (Compact state)

A set of states Q is compact (in S) iff for any R such that Q ~ R, it follows that Q = R. If Q is a singleton and compact, we will call the state in Q compact.

One last notion that we require is that of an E-predecessor of a given state; those E-states preceding the given state with respect to an ordering based on symmetric difference. More formally:

Definition 6.4 ( E-predecessor)

Given any two states w, r and any sentence E, the E­ predecessors of r with respect to w is defined to be the set ~r , EDw = {r' : r' E [E]andDiff(w,r') <; Diff(w,r)} where Diff(x, y) denotes the symmetric difference of states x andy (i.e., (x \ y) U (y \ x)) as in the PMA [Winslett, 1988}.

It is clear that any r E [E] is an E-predecessor of itself with . respect tow (i.e., r E ~r, ED-w). TheE-predecessors of r with respect to w are just the E-states which agree with w on at least those fluents where w and r agree and possibly others. If one considers a PMA ordering [Winslett, 1988] of states ~w (i.e., r ~w s iff Diff(w, r) <; Diff(w, s)), then the E-predecessors are those E-states at least as close tow as r.

We are now in a position to define a state-selection mecha­ nism based on state elimination systems.

Definition 6.5 (Nexts(E, w))

With any state elimination system S we associate a result function Nexts (mapping a compact (in S) state w and a sentence E to the set of states Nexts(E, w)) defined as fol­ lows: Nexts(E, w) = {r E [E] : r is compact (inS) and ~r , EDw ~ {r} }.

In the following section we characterise Resv(E, w) in terms of Nexts(E, w). First, however, let us briefly con­ sider the definition of Nexts(E, w). According to the defi­ nition above, a state r is a possible resultant state if and only if all its E-predecessors (with respect to w) are rejected by elimination rules in S but r and only r is retained. If r is re­ tained along with some other state,then there is some closer state (one with 'less' change) consistent with the state elimi­ nation systemS (and, therefore, causal system D) under con­ sideration. Moreover, it means that there is something in the state(s) for which causality cannot account. If r is rejected on the other hand, it must violate a causal relationship. For these reasons we only consider the E-predecessors of r to determine whether it belongs to Nexts(E, w); we need to determine whether r is illegitimate or whether a 'closer' state satisfies the causal relationships. If either is the case, we can safely reject the state. Otherwise, we can retain the state.

6.1 Causal Systems and State Elimination Systems

We now establish the interrelationship between causal sys­ tems and state elimination systems. This will give us a way of moving back and forth between the two systems facilitat­ ing the final intertranslation between causal systems and state transition systems. The following definition will prove use­ ful.

Definition 6.6 (Selection-equivalent)

A causal system D is selection-equivalent to a state elimi­ nation systemS iff Resv(E, w) = Nexts(E, w),for every sentence E and state w.

The notion of selection-equivalence will be useful in relating causal systems and state elimination systems. Moreover, it will be useful in relating any two state-selection mechanisms (in an obvious way).

We now tum to the main result of this section. A state elimination system can exactly capture a causal system (and vice versa).

Theorem 6.7 For every causal system there exists a selection-equivalent state elimination system. Conversely, for every state elimination system there exists a selection­ equivalent causal system.

Proof (Sketch)

( => ) Let D be an arbitrary causal system. For every causal law cp => '¢ in D, produce the elimination rule [cp]t>[cp 1\ '¢]. Call S the set of elimination rules so produced. It is not dif­ ficult to verify that for any legitimate state w and sentence E, Resv(E, w) = Nexts(E, w) (simply notice that for any stater, [(w n r) U {E}] = ~r, EDw).

( ~ ) Let S be an arbitrary state elimination system. For every elimination rule Xt>Y produce the causal law cp => '¢, where cp, '¢ are such that [cp] = X and ['¢] = Y (since our language is a finitary propositional one, such cp and '¢ al­ ways exist). The set of causal laws so produced, call it D, is selection-equivalent to S. ·

Of particular note in this proof is the relationship between causal laws and elimination rules: ¢ => '¢ if and only if [¢]t>[¢ 1\ '¢](or, equivalently, [¢]t>[¢] n ['¢)).

We can also identify an important class of state elimination systems that will be useful later (in the proof of Theorem 7.3).

Definition 6.8 ( S Unary)

A state elimination system S is unary iff every elimination rule eliminates precisely one state, i.e. for all (Xt>Y) E S, X \ Y is a singleton.

The following result reveals an interesting and important as­ pect of unary state elimination systems.

Theorem 6.9 Every state elimination system is selection­ equivalent to a unary state elimination system.

7 Mechanism 2: State Transition Systems

In this section we consider our second (and last) state­ selection mechanism: state transition systems. Again, we shall obtain a direct characterisation of causal systems (and state elimination systems). In this case we have a preferen­ tial mechanism augmented by further structure to achieve the result we desire in this paper.

A state transition system consists of a binary relation on states intended to represent possible transitions between states due to the presence of causality. It is this relation that, together with a preferential ordering based on symmetric dif­ ference, will be used to determine possible resultant states.

We begin with some requisite definitions.

Definition 7.1 A state transition system M is a binary rela­ tion on the set W of states (i.e., M ~ W x W). Whenever (r , r') E M we will writer ....... r'. We shall say that a stater is final (in M) iff for any r' such that r ....... r', r = r'.

The binary relation M can be considered to represent state transitions due to the influence of causality.

We are now in a position to define the mechanism for selecting possible resultant states (or successor states) SuccM (E, w) for a state transition system M given initial state wand action with direct effects E.

Definition 7.2 (SuccM(E, w))

To any state transition system M we associate a function SuccM (mapping a final (in M) state w and a sentence E to the set of states SuccM(E,w)) defined as follows: SuccM (E, w) = {r' E [E] : r' is final (in M) and there is a Hamiltonian path through states in ~r' , EDw} .

A Hamiltonian path is one which traverses every vertex (here states) of a graph [Wilson, 1985]. In this case, the graph's vertices are the E-predecessors of r' and the edges are given by the binary relation M (i.e., there is an edge between states r' and s iff (r', s) E M). The significance of a Hamiltonian path will be considered further in the next section.

It is important to notice that SuccM(E, w) is determined by two components: a preference ordering on states, based on symmetric difference, used to derive theE-predecessors of r' with respect tow (i .e., ~r' , EDw) and the binary relation on states M. We maintain that the preference ordering captures the principle of minimal change while the binary relation cap­ tures the effect of causality. Notice firstly that a state must be reachable via a Hamiltonian path through all E-predecessors ending in r'. If this is not possible, either a 'closer' E-state is consistent with the causal relationships that hold (absence of Hamiltonian path) orr' violates a causal relationship (path does not end at r'; i.e., r' is not final). Another important point is that, like state elimination systems, we only need con­ sider E-predecessors of r' (with respect to w) to determine whether it is a possible resultant state.

7.1 State Elimination Systems and State Transition Systems

In this section we establish an intertranslation between state elimination systems and state transition systems. We can then use the results of Section 6.1 to establish a correspondence between causal systems and state transition systems. This gives us the result we seek: an augmented preferential se­ mantics for McCain and Turner's causal theory of actions.

Theorem 7.3 For every state elimination systemS there is a selection-equivalent state transition system M. Conversely, for every state transition system M there is a selection­ equivalent state elimination system S .

Proof. (Sketch)

( =} ) Let S be a state elimination system. Let S' be a unary state elimination system that is selection-equivalent to S. From S' we construct a selection-equivalent state transi­ tion system M. First we require some definitions.

Consider an arbitrary set of states Q with cardinality n + 1. We shall say that the string of elimination rules a 1 ; a2; · · · ; an dissolves Q iff after applying these rules suc­ cessively (in the order given), all but one of the states of Q are eliminated and, furthermore, the one remaining state is compact.

Assume that a 1 ; a2; · · · ;an dissolves Q and for all 1 ::; i ::; n, let r i be the state of Q that is eliminated by the rule a i; let us also call w the one state of Q that is not eliminated. We shall call the sequence of states r 1 ; r 2 ; · · · ; r n; w a trace for Q (in S').

We now construct from S' a state transition system M in the following manner. For any two states r , r', (r, r') E M if and only if there is a dissolvable set of states Q containing r and r', such that for some trace of Q in S', r' appears imme­ diately after r. It can be shown that M is selection-equivalent toS'.

( ¢:: ) Essentially proved by reversing the construction presented above. ·

The central result of this paper, as expressed by the follow­ ing corollary, is now obtained by combining theorems 6.7 and 7.3.

Corollary 7.4 For every causal system D there exists a selection-equivalent state transition system M. Conversely, for every state transition system M there exists a selection­ equivalent causal system D.

This result states that it is possible to exactly characterise Mc­ Cain and Turner's causal theory of actions via a preferential­ style semantics (defined in terms of symmetric difference) augmented with a binary relation on states and through the notion of a Hamiltonian path.

8 Discussion

One of the morals that we have attempted to stress in this work is that it is possible to retain preferential semantics and augment it in capturing the causal theory of McCain and Turner. We maintain that the preferential component of state transition systems relates to the principle of minimal change while the binary relation on states relates to the causal system. It is our contention that both of these components- minimal change and causality- are required if one is to supply a con­ cise solution to the frame problem; the two can co-exist and, in fact, complement each other.

It has been suggested that other preferential-style ap­ proaches to reasoning about action are capable of capturing McCain and Turner's causal theory of actions (for instance, [Gustafsson and Doherty, 1996]); an apparent contradiction of what is suggested by our impossibility theorems in Sec­ tion 4. However, this and similar approaches are able to do so only by augmenting the original language£ (with, for in­ stance, predicates like occlucf.es or so-called frame ftuents). At the outset we made clear that we did not wish to adopt this tactic. To do so would be to call into question our adher­ ence to the quest for conciseness in seeking a solution to the frame problem and, more specifically, the ramification prob­ lem. Moreover, the ontological status of added predicates is not always clear and places a huge burden on the designer who must determine whether and when to occlude predicates.

The notion of a Hamiltonian path through E-predecessors in a state transition system to determine possible resultant states is an interesting one. Essentially, a Hamiltonian path serves as a contextual mechanism much in the same way that augmenting the underlying language through the addition of extra predicates does. The additional information allows the effects of causality to contribute in certain situations and not in others.

9 Conclusion and Future Work

In this paper we set out to determine whether it is possible to furnish McCain and Turner's [McCain and Turner, 1995] causal theory of actions with a preferential semantics in the spirit of Shoham [Shoham, 1988]. We demonstrated, through use of an impossibility theorem (Theorem 4.2), that this is not possible in general when we do not embellish the origi­ nal language £ and assume the preferential ordering satisfies transitivity. Choosing not to abandon preferential semantics entirely, we then adopted an abstract view in terms of state­ selection mechanisms introducing two such systems: state · elimination systems and state transition systems. The lat­ ter of these provides the sought after semantics augmenting a preferential structure based on symmetric difference with a binary relation on states and making use of the notion of a Hamiltonian path. The former provides a stepping stone and, of equal importance, gives further insight into the na­ ture of causality at play in McCain and Turner's approach. Significantly, we show that causal systems, state elimination systems and state transition systems, as defined here, are (se­ lection) equivalent. That state transition systems augment a preferential structure with a binary relation on states demon­ strates, we claim, that minimal change and causality - the former captured by preferential semantics and the latter by a binary relation - together are essential in furnishing a con­ cise solution to the frame and ramification problems.

Providing McCain and Turner's causal theory of action with an augmented preferential semantics allows compari­ son with other logics of action and provides an interesting direction for future work. Another avenue for future work would be a contrast of Sandewall's causal propagation semantics [Sandewall, 1996] and our state transition systems. This would indirectly link Sandewall's semantics with Mc­ Cain and Turner's causal theory of actions giving further in­ sight into causal approaches to reasoning about action. It may also be possible to modify the approach here in terms of state transition systems and Hamiltonian paths to capture other causal approaches such as that of Thielscher [Thielscher, 1997]. Note, however, that Thielscher's system does not sat­ isfy the property that the possible resultant states lie among the E-states. This suggests that such a result is not likely to be a straightforward extension of the current work.

Acknowledgements

The authors would like to thank members of the School of Computing Science at Simon Fraser University for their com­ ments on this work.