Computing Ramifications by Postprocessing

1 Introduction

The ramification problem [Finger, 1987] is usually re­ garded as one of the challenges to all formal frameworks for reasoning about actions and change. It states that it is unreasonable to specify explicitly all changes that are caused by the execution of some action. Rather the spec­ ification should concentrate on immediate effects, and so­ called indirect effects are then implicitly derived by some additional general knowledge of dependencies. Consider, as an example, an electric circuit containing a switch and a light bulb. Here one might wish to specify that the only direct effect of toggling the switch is a change of its posi­ tion while the state of the bulb is indirectly affected via a general law (called domain constraint) that describes the causal connection between the switch's state and the bulb [Lifschitz, 1990].

It has often been argued (see, e.g., [Ginsberg and Smith, 1988]} that STRIPS-like approaches (Fikes and Nilsson, 1971] are inherently unsuited to tackle the rami­ fication problem since they are based on the idea that all fluents remain unchanged which are not explicitly men­ tioned in an action description. In this paper, however, we propose to regard the set effluents which is obtained after having applied some action description merely as a preliminary approximation of the resulting situation­ which then is computed by performing additional post­ processing steps that model indirect effects according to given domain constraints.

Our approach consists of two steps. First, we show how the post-processing computations just mentioned can be performed on the basis of additional knowledge of so-called causal relationships. These define how the occurrence of a particular atomic effect might cause the additional occurrence of ce~;tain other effects. The inten­ tion is to apply such rules if and as long as the situation at hand (which has been obtained by computing the di­ rect effects of an action) violates the domain constraints. Second, we illustrate how causal relationships can be au­ tomatically generated from given domain constraints by taking into account general knowledge of how facts can possibly affect each other.

The applicability of our solution is demonstrated by extending a concrete STRIPs-like yet purely deductive method which is based on Equational Logic Program­ ming (ELP) [Holldobler and Schneeberger, 1990]. In contrast to STRIPS, this approach has recently turned out to have a wide range of applicability as regards gen­ eral aspects of topical interest, e.g., postdiction prob­ lems, reasoning about nondeterministic and concur­ rent actions, etc. [Thielscher, 1994; Bornscheuer and Thielscher, 1994]. Moreover, this method is provably equivalent to a modification of the Connection Method designed for planning problems [Bibel, 1986] and to an approach to planning based on Linear Logic [Masseron et al., 1990] (see [Grofie et al., 1995]).

The rest of this paper is organized as follows. In Section 2, we introduce the formal notion of a causal relationship. Based on this concept, we define post­ processing steps used to compute ramifications accord­ ing to underlying domain constraints. In Section 3, we present an algorithm to generate causal relationships au­ tomatically given some domain constraints and a formal specification of which fluents are causally connected. In Section 4, we turn to the ELP-based approach and show how to integrate our solution to the ramification prob­ lem. To this end, we extend the basic logic program by clauses expressing domain constraints and model­ ing the successive application of single causal relation­ ships. The adequateness of this extension is proved wrt the semantics developed in Section 2. Finally, our proposal is discussed and future research is outlined in Section 5. In particular, we compare the employ­ ment of causal relationships with methods based on the distinction between frame and non-frame fluents made to address the ramification problem [Lifschitz, 1990; Kartha and Lifschitz, 1994)-and show the limitedness of the latter.

2 Applying Causal Relationships

A formal framework to reason about actions and change requires the basic notion of a situation, which is a par­ tial snapshot of the world at a particular instant of time. So-called fluents serve as the atomic elements to de­ scribe situations-these are properties whose truth val­ ues may change in the course of time [McCarthy and Hayes, 1969). For sake of simplicity, we assume a finite number of propositional constants as the underlying set of fluents throughout this paper.

Definition 1 Let :F be a finite set of symbols, called fluents. A situation S is a set of fluent literals, i.e., expressions of the form f or 7, where f E :F , such that each fluent occurs either affirmatively (f) or negatively ( 7) in S. ·

For convenience, let us agree to interpret 7 as f, and by Ill we denote the affirmative part of a fluent literal l, i.e., l/1 = 171 = f where f E :F .

Example 1 The basic version of the Yale Shooting scenario [Hanks and McDermott, 1987) consists of the fluents loaded and alive , which determine the state of a gun and a turkey, respectively. For instance, the situ­ ation {loaded, alive} describes the fact that the gun is unloaded and the turkey is alive. ·

Example 2 The Electric Circuit domain [Lifschitz, 1990) consists of two binary switches whose positions are described by the fluents switch1 and switch2 , respec­ tively, plus a light bulb represented by the fluent light . The set { switch1 , switch2 , light} , for instance, describes a situation where the two switches are in different posi­ tions and the light is off. ·

Actions are specified in a STRIPS-like fashion by stat­ ing a set of fluent literals to be removed from along with a set of fluent literals to be added to the situation at hand. Such an action is applicable if all literals to be removed are contained in the current situation:

Definition 2 Let :F be a set offluents. An action de­ scription is a triple (C, a,£) where C, called condition, and £, called effect, are sets of fluent literals and the action name a is a symbol. Such an action description is applicable in a situation S iff C ~ S . The application yields the set (S \C) U £. ·

Example 1 (continued) The action of loading the gun can be formalized by the triple

This action description is applicable in the situation S = {loaded, alive} since {loaded} ~ S ; its application yields ( S \ {loaded}) U {loaded} = {loaded, alive} . ·

Since the effects of an action may vary from situa­ tion to situation, one often needs more than just a single specification such as (1). In order to avoid unintended conflicts in case of multiple descriptions of one action, we employ the following partial order on action descrip­ tions [Holldobler and Thielscher, 1995):

Definition 3 An action description (Ct, a1 , £1 ) is more specific than a description (C2 , a2 , £2 ) iff a 1 = a2 and C1 :::::> C2 . If A is a set of action descriptions, s a situation and a an action name then a successor of S is obtained by applying the most specific (wrt A) applicable action description of a to S . ·

Example 1 (continued) The action of shooting with the gun might be defined by

stating that the gun becomes unloaded. Additionally, shooting at a living turkey with a previously loaded gun causes him to drop dead, i.e.,

Following Definition 2, both (2) and (3) are applicable in the situation {loaded, alive} . However, ( 3) is more specific than (2) and, hence, the only successor of S is {loaded, alive} as intended. ·

In the sequel, we assume that any given set of action descriptions is deterministic, i.e., contains at most one most specific applicable description for each action and situation. Furthermore, its application shall always pre­ serve the condition of being a situation (see Definition 1) .

Our concept of a situation suggests that first of all each possible combination of fluent values describes a possible situation in the domain being modeled. In more complex scenarios, however, fluents might depend on each other. These dependencies are expressed by means of domain constraints, which are formalized as (propositional) for­ mulae built up from fluent literals and the usual logical connectives:

Definition 4 Let :F be a set of fluents. The set of fluent formulae is the smallest set such that the constant T (true) and each fluent literal f and 7 ( f E :F) are fluent formulae ; and if F and G are fluent formulae then (F 1\ G), (F v G), (F => G), and (F ¢ G) are also fluent formulae .

If S is a situation and F a fluent formula then the notion of F being true in S , written S f= F , is induc­ tively defined as follows:

1. S f= f (resp. S f= 7) iff f E S (resp. 7 E S ), for each f E :F;
2. S f= (F 1\ G) iff both S f= F and S f= G;

4. S f= ( F V G) iff S f= F or S f= G (or both);

1. Sf= (F =>G) iff S [i: F or Sf= G (or both); and
2. S f= (F ¢? G) iff S f= F and S f= G or else S [i: F and S [i: G .

·

Example 1 (continued) The Yale Shooting scenario is extended by two fluents, dead and walking , stat­ ing whether the turkey is dead and whether he is walk­ ing around, respectively [Baker, 1991). The constraint alive <=? dead then formalizes the obvious connection between these two fluents while walking => alive states that our turkey must be alive to take some exercises. ·

Example 2 (continued) We assume that our electric circuit is designed such that the light bulb is on if and only if the two switches are in the same position (see also Figure 1 in Section 5). This is expressed via the domain constraint light <=? ( switch1 <=? switch2) . ·

The ramification problem now arises as soon as do­ main constraints describe dependencies which are not reflected in some action description. Since the frame as­ sumption tells us that fluents keep their value unless they are explicitly mentioned in such an action description, the domain constraints become violated through the ex­ ecution of that action. For instance, applying (3) to the (reasonable) situation {loaded, alive, dead, walking} yields the set S' = {loaded, alive, dead, walking} accord­ ing to Definition 2, which now violates both underlying domain constraints from above.

From a theoretical point of view it is of course conceiv­ able to integrate all domain constraints into the various action descriptions, by making intensive use of our speci­ ficity criterion. From a practical point of view, however, this would soon lead to an intractable number of action descriptions when trying to model slightly more complex scenarios. Moreover, adding a new domain constraint to a scenario might force, in the worst case, the reconstruc­ tion of a completely new set of action descriptions.

Instead of exhaustively integrating domain constraints into action descriptions, we should view these con­ straints as reason for certain indirect effects in addi­ tion to the effects explicitly occurring when executing actions according to Definition 2. These indirect effects are computed by performing additional post-processing steps. Hence, the basic idea is to regard a set like S' = {loaded, alive, dead, walking} from above as a mere approximation which requires further investigation to obtain the finally resulting situation. If and as long as the preliminarily obtained set violates the given do­ main constraints, particular indirect effects are gener­ ated. To this end, we need information of the various causal connections between the fluents in the domain un­ der consideration. For instance, our domain constraint alive <=? dead suggests that if some action affects the fluent alive then it also influences, indirectly, the flu­ ent dead . In particular, this information should lead to the replacement of dead by dead in S' . Such a replacement-triggered by what will be called a causal relationship below-is considered as a single step in the post-process to be performed in order to address ram­ ifications. It is of course inevitably necessary to know which of the two fluents alive and dead in S' was an immediate effect of the action that has just been exe­ cuted. Otherwise, one could as well argue that the oc­ currence of dead should lead to the replacement of alive by alive , which is clearly not intended in this example.

Moreover, since indirect effects potentially cause addi­ tional effects, it is necessary to keep in mind all computed effects during the post-process. The following definition of a causal relationship and its application to a set offlu­ ents in conjunction with a particular set of effects makes this idea manifest:

Definition 5 A causal relationship is an expression of the form C : e "-' f where C is a fluent formula and e, f are fluent literals. Let S be a situation and £ a set of fluent literals then such a relationship is applicable to (S, E) iff S f= C, f E S and e E £. Its application yields S' = (S \ {7}) U {!} and £' = £ U {!}.

Let S be a consistent (wrt a set of given domain con­ straints 'D) situation and (C, a,£) be a most specific applicable action description (wrt a fixed set A). A consistent (wrt 'D) set S' is a result of executing a in S if some ( S', £') can be obtained by applying a sequence of causal relationships to ( ( S \ C) U t:, £) . · In words, a causal relationship consists of a condition C that has to be satisfied, a particular effect e that must have been occurred (directly or indirectly), and a fluent that changes its value as an indirect effect caused by e . A resulting situation is then obtained by applying a pure action description following Definition 3 and, afterwards, using causal relationships ·until the underlying domain

constraints become satisfied.

Example 1 (continued) Let the following two causal relationships be given:

If S = {loaded, alive, dead, walking} denotes the situa­ tion at hand then the application of (3) yields the set ( S \ C) U t: = {loaded, alive, dead, walking} along with t: = {loaded, alive} . Now, the two relationships ( 4) can be sequentially applied as follows:

The resulting situation does no longer violate the domain constraints and is exactly the intended solution. ·

Example 2 (continued) Consider the relationship

Furthermore, let ( switch1, toggle 11 switch1) be one spec­ ification of toggling the first switch. This descrip­ tion is applicable in { switch1, switch2, light} and yields S' = { switch1, switch2, light} along with the set of ef­ fects t: = { switch1} . Because of S' f= switch2 , the causal relationship (5) is applicable and yields { switch1, switch2, light} , which now is compatible with the underlying domain constraint. ·

The reader should be aware of the fact that Defini­ tion 5 does neither guarantee uniqueness nor even ex­ istence of a successor situation. Both aspects will be discussed in Section 5.

3 Extracting Causal Relationships

The causal relationships used in the previous section were given as part of the problem specification. In this section, we investigate the possibility to extract these rules automatically from arbitrary domain constraints. Doing this, however, one is faced with a well-known prob­ lem: Recall the formula light {::} ( switch1 {::} switch2) , and consider the set of fluents { switch11 switch2, light} being obtained by changing the position of the first switch (Example 2). This situation violates the underly­ ing constraint. To correct this via a ramifications step, there are two different possibilities even in case we are aware oft he fact that the first switch has just changed its position. Either we could replace light by light or else switch2 by switch2 . Both are (minimal) changes result­ ing in a situation that satisfies our domain constraint. Obviously, the latter contradicts our intuition; yet no syntactical criterion tells us which of the two changes should be preferred. By using the given, intended causal relationship (5), we have obtained the desired result. But first of all our constraint suggests as well the counterin­ tuitive relationship light : switch1 "--' switch2 .

This is a general problem arising in any formal ap­ proac.h to the ramification problem. Several ways to overcome it are informally discussed in [Ginsberg and Smith, 1988]. The most promising and reasonable solu­ tion, which we adapt here, seems to be the incorporation of additional knowledge of the domain into the reason­ ing process. For instance, we know from general laws of physics that changing a switch's position might immedi­ ately influence the bulb but not another switch. 1

Domain knowledge of how fluents possibly affect each other is formally specified by a binary influence rela­ tion I on the set of fluents. For example, defining I = {(switch1, light), (switch2, light)} encodes the fact that a change of a switch's position can possibly influence the state of the light bulb but not vice versa. Based on this additional information, all intended causal relation­ ships can be extracted automatically from given domain constraints by considering each possible way to satisfy a violated constraint through the change of certain fluents:

Algorithm 1 Let :F be a set of fluents, 'D a set of domain constraints and I ~ :F x :F an influence relation. For each D E 'D do:

1. Let F1 1\ ... 1\ Fn be the conjunctive normal form (CNF) of D ( n 2:1 ). For each i = 1, . . . ,n do:
2. Let Fi = L1 V . . . V Lm where each Lj is a fluent literal ( m 2: 1 ). For each j = 1, ... , m do:
3. For each k = 1, ... , m such that j f k and ( ILj I, IL~c I) E I generate this causal relationship:

·

1 1t is important to distinguish between immediate and possibly indirect influence. Though two switches cannot di­ rectly affect each other, they might be causally connected indirectly through, for instance, a relay (see also Figure 1).

Note that a domain constraint might yield an exponen­ tial number of causal relationships if its CNF consists of exponentially many literals. But the overall number of relationships is linear in the size of 'D because each constraint is treated separately.

Example 2 (continued) Consider the domain con­ straint D = light {::} ( switch1 <=> switch2) and the in­ fluence relation I = { ( switch1 , light), ( switch2, light)} . The CNF of D is

Let us apply the second and third step of Algorithm 1 to the first conjunct, light V switch1 V switch2 :

• In case Lj=l = light, no causal relationship is gen­ erated since I includes neither (light, switch1 ) nor (light, switch2) .
• -:-;---;- · In case Lj=2 = switch1 , this causal relationship is generated due to ( switch1, ILk=1l = light) E I :

(c.f. (5)), whereas (switch1 , 1Lk=31 = switch2) (/_ I prevents us from generating the unintended rela­ tionship light : switch1 "--' switch2 .

• In case Lj=3 = switch2 , this causal relationship is generated due to (switch2, ILk=1l = light) E I :

while (switch2, IL1c=2l = switch1) (/_ I suppresses the generation of another one.

Correspondingly, the remaining conjuncts in the CNF above yield these six causal relationships:

switch2 : switch1 "'--> light switch1 : switch2 "'--> light switch2 : switch1 "'--> light switch1 : switch2 "--' light switch2 : switch1 "'--> light switch1 : switch2 "--' light

·

Example 1 (continued) Given the influence rela­ tion I = { (alive, dead), (dead , alive), (alive, walking)} , the reader is invited to verify that our two domain con­ straints yield these five causal relationships:

·

4 Ramification in ELP

The completely reified representation of situations is the distinguishing feature of the ELP-based approach [Holldobler and Schneeberger, 1990]. To this end, the fluent literals being true in a situation are treated as terms and are connected using a special binary function symbol, denoted by o and written in infix notation:

Definition 6 LetS= {ft, ... ,fm,fm+l· · ··· fn} be a set of fluent literals then

is the term representation of S .

·

Intuitively, the order of the fluent literals occurring in a term representation should be irrelevant, which is why we employ an underlying equational theory, viz

where 0 is a constant denoting a unit element for o .

Based on this equational theory, written (AC1), the reasoning process described in Definitions 2 and 3 is en­ coded by means of an equational logic program (see, e.g., [Holldobler, 1989]) as follows. Each action de­ scription (C, a, E) is represented by the unit clause action ( rc, a, re) . The application of actions, which in­ cludes consideration of the specificity criterion, is per­ formed on the basis of these three program clauses: 2

In words, the ternary predicate causes ( i, [ a1 , ... , an], g) expresses the fact that the application of the sequence [ a1, ... , an] of actions to the initial situation i yields the goal situation g . If n 2: 1 then an action description of a 1 with condition c and effect e is selected such that c is contained in i, i.e., 3V. c o V =Act i; the description is most specific wrt i ; and the recursive call uses the resulting situation Voe along with the sequence p = [ a2, ... , an] . An instance non.specific (a, c, i) states the existence of a description for a which is more spe­ cific wrt the situation i than the particular description with condition c. Following Definition 3, such a more specific action description must have some condition c' such that c' is contained in i and the set corresponding to c' is a strict superset of the set corresponding to c . 3

The clauses in (7) plus the ones encoding a given set of action descriptions in conjunction with the equa­ tional theory (AC1) form the basic ELP to reasoning about actions. Since this logic program does not only require a special unification procedure but also contains negative literals, an adequate computation mechanism is SLDENF-resolution, i.e., SLD-resolution augmented by theory unification and the negation-as-failure prin­ ciple to handle negative subgoals [Shepherdson, 1992; Thielscher, 1995]. In [Holldobler and Thielscher, 1995], the application of this calculus to our ELP has been proved adequate wrt the semantics given by Defini­ tions 1-3. 4

2 We use a PROLOG-like syntax, i.e., constants and pred­ icates are in lower cases whereas variables are denoted by upper case letters. As usual, the term [h I t] denotes a list · with head h and tail t .

3 In order to treat equality subgoals, we implicitly add the clause X =Acl X encoding reflexivity.

4 It is important to realize that the axioms (AC1) essen­ tially model the data structure multiset rather than sets;

4.1 Integrating Domain Constraints

As a first step towards integrating our solution to the ramification problem into the ELP-based approach, we have to provide a way to express domain constraints. To this end, we overload to a certain extent the four logical connectives 1\ , V , => and {:} , introduced in Defini­ tion 4, by treating them as special binary functions in our logic program. Given a fluent formula F , by Tp we denote its term representation based on these functions (and where the special formula T is represented by the unit element 0 ). The following clauses encode the no­ tion of a formula being true in a particular situation:

These clauses are adequate wrt Definition 4:

Proposition 7 Let :F be a set of fiuents, F a fluent formula and S a situation. Furthermore, let rs and Tp denote term representations of S and F , respec· tively, then S f= F iff ( 8) U { <-holds ( rp, rs)} has an SLDENF-refutation wrt {AC1}.

Proof: If F = T then S f= F. Correspondingly, the query <-holds (0, rs) can be refuted by applying the first clause in ( 8) since rs =ACt 0 o rs .

If F =I (resp. F = 1) for some IE :F then S f= F iff I E S (resp. 1 E S ). Correspondingly, the query <- holds ( rp, rs) can only be resolved by applying the first clause in (8) and only if rs and I o V (resp. 1 o V) are (AC1)-unifiable.

The various cases where F is a complex formula can be easily proved by induction on its structure. 5 ·

Based on this formalization, an underlying set of do­ main constraints { D1 , ... , Dn} is used to define consis­ tency of situations via the following program clause:

4.2 Causal Relationships in ELP

To integrate into the ELP-based approach causal re­ lationships and their application in order to address the ramification problem, we introduce a new predicate ramify( rs, re, rs·, re·) . Its intended meaning is that the application of some causal relationship to a pair ( S, &) yields a pair ( S', E') . More precisely, each causal rela­ tionship C : e '"'-+ I is encoded via the unit clause

In words, if the situation at hand contains the fluent lit­ eral 1 and entails C , and if in addition e has occurred as effect then f is replaced by f . Furthermore, f is added to the current set of effects. For brevity, given a set 'R of causal relationships by (10)n we denote the set of program clauses encoding the elements of 'R .

the necessity of this sophistication, as regards our pro­ gram (7), has been shown in [Grofle et al., 1995]. We neglect this difference here-which is justified by results presented in [Thielscher, 1994].

5 Regarding the fifth clause in (8), note that a subgoal ·holds( 'TF, rs) has an SLDENF -refutation iff the affirmative query +--- holds ( 'TF, Ts) finitely fails, i.e., is not refutable.

In order to apply causal relationships in a post-process after having applied an action description, the body of the second clause defining causes in our original pro­ gram, (7), is extended by a literal named consistify:

An instance consistify(v o e, e, s) is intended to express the fact that the preliminarily computed (possibly in­ consistent) situation v o e along with the effect e can be transformed into a resulting (consistent) situation s through the successive application of causal relationships (c.f. Definition 5):

In words, if the situation at hand is already consistent (c.f. (9)) then it describes an acceptable result. On the other hand, we can apply a causal relationship to the situation S along with the effects E that yields a new situation S' and a new set of effects E' according to Definition 5, which are then used in a recursive call.

The following main result states the adequateness of our extended program wrt the proposal of Section 2:

Theorem 8 Let :F be a set of fiuents, 'R a set of causal relationships, 1) a set of domain constraints and S, t:, S' three sets of fiuents. If S is the outcome of hav­ ing applied some most specific action description with ef­ fect t: to some consistent situation then S' is a resulting situation iff +-- consistify( Ts, re, Ts·) has an SLDENF­ refutation wrt (9)1J U (10)n U (12) and (ACJ).

Proof (sketch): There is a one-to-one correspon­ dence between the application of a causal relationship according to Definition 5 and the application of the cor­ responding clause ( 10). Furthermore, the first clause in (12) in conjunction with Proposition 7 requires S' to satisfy 1). The formal proof is by induction on the num­ ber of applied causal relationships and the length of the refutation, respectively. ·

Example 1 (continued) Given the encodings of the two relationships in ( 4), of the underlying domain con­ straints, and of the action description (3), i.e.,

action( loaded o alive, shoot, loaded o alive).

it is possible to find an SLDENF-refutation for the query +-- causes (loaded o alive o dead o walking, [shoot], G) with answer G r-+ loaded o alive o dead o walking . ·

5 Discussion

We have proposed the application of single causal rela­ tionships in a post-processing step in order to address the ramification problem. Moreover, it has been illus­ trated how an adequate set of such relationships can be automatically extracted from given domain constraints by taking into account general knowledge of how fluents can possibly affect each other. Finally, we have inte­ grated both domain constraints and our method to com­ ply with them into an approach to reason about actions and change based on Equational Logic Programming.

The merits of causal relationships shall be illustrated by an example that shows the limitedness of a common, simpler way to avoid unintended ramifications, namely, the distinction between so-called frame and non-frame fluents [Lifschitz, 1990; Kartha and Lifschitz, 1994]:6 Consider the extended Electric Circuit scenario depicted in Figure 1. Two switches and the light bulb are related as usual , i.e., light ¢:> ( switch1 ¢:> switch2) ; the addi­ tional relay is controlled by the first and third switch through relay ¢:> switch1 1\ switch3 ; and the relay is intended to force the second switch into the upper po­ sition if activated, i.e., relay =} switch2. Now, in order to prefer the light bulb changing its state to a switch unexpectedly jumping its position (see Section 3), we are supposed to consider switch1 and switch2 frame and light non-frame. Accordingly, switch3 and relay should be considered frame and non-frame, respectively. However, if we take the situation depicted in Figure 1 and change the position of the first switch then it is im­ possible to distinguish between these two outcomes: Ei­ ther the relay becomes activated and causes the second switch to jump into the upper position (as intended) or else the relay remains deactivated and the third switch opens magically! This is because in both cases a sec­ ond frame fluent (aside from switch1 ) is affected, yet no preference is discernible. In contrast, and the reader is invited to verify this, given the natural influence relation I = {(switch1, light), (switch2, light), (switch1, relay),

6 Roughly spoken, the idea there is to prefer changes of non-frame fluents to changes of frame fluents whenever addi­ tional effects have to be considered in order to satisfy domain constraints.

(switch3 , relay), (relay, switchz)}, Algorithm 1 gener­ ates an adequate set of causal relationships whose ap­ plication according to Definition 5 yields the intended, unique resulting situation.

A second merit of causal relationships is that they en­ able us to comply with the observation that domain con­ straints might give rise to qualifications rather than ram­ ifications [Lin and Reiter, 1994]. Consider, for instance, the action of enticing the turkey to walk. 7 The effect of executing this action shall be {walking} . Yet in case the turkey is not alive, the constraint walking => alive should clearly not lead to his revival. Rather it im­ poses an additional qualification on our new action. This is reflected in the causal relationships (6): None of them is applicable to S = {alive, dead, walking} , [ = {walking}; hence, no resulting situation is obtained here following Definition 5. Our logic program developed in Section 4 behaves accordingly-the reader is invited to verify that +--- causes (alive o dead o walking, [entice], G) has no SLDENF-refutation given the encoding of(6) and the action description action (walking, entice, walking) .

The example just discussed illustrates the possibility that a resulting situation does not at all exist, i.e., the available causal relationships might not always be suffi­ cient to satisfy the underlying domain constraints. As we have seen, this induces (additional) qualifications. On the other hand, it is also conceivable that multiple suc­ cessor situations can be obtained by applying different sequences of causal relationships all resulting in the sat­ isfaction of the domain constraints. This induces nonde­ terminism. Both non-existence as well as multitude ofre­ sulting situations rise the important question of general criteria that guarantee a unique successor. A compar­ ison with the concept of revision programs, introduced in [Marek and Truszczynski, 1994], might help to ad­ dress this problem. Revision programs along with their application in order to modify states of databases resem­ ble causal relationships and their application in order to compute ramifications. In [Marek and Truszczynski, 1995], two syntactic conditions have been proved guar­ antee of a unique revised database. Whether and how these results can be adapted to our approach depends on the formal correspondence between the two concepts and is left as future work.

Acknowledgments

The author is grateful to Christoph Herrmann and the anonymous referees for helpful comments on an earlier version of this paper. Thanks also to the participants of the AAAI 95 Spring Symposium on Theories of Actions for several interesting discussions related to the work re­ ported here.