Reasoning About Persistence: A Theory of Actions

1 Introduction

Winslett proposed a method for reasoning about ac­ tion, which she called a possible models approach (PMA) [Winslett, 1988). The PMA was devised to remove some difficulties in Ginsberg and Smith's possible worlds ap­ proach (PWA) for reasoning about action [Ginsberg and Smith , 1987a; Ginsberg and Smith, 1987b]. As argued by Winslett, although the PWA is an elegant, simple and powerful technique for reasoning about action, it fails to solve the frame problem {What facts about the world remain true when an action is performed?), ramifi­ cation problem (What facts about the world must change when an action is performed?) and qualification problem (When is it reasonable to assume that an action will suc­ ceed?), if the PWA is forced to operate with incomplete information [Winslett, 1988].

The basic idea of the PWA is to take a logical theory as the description of the world. The effect of an action is modeled by incorporating a set offormulas F (that spec­ ify the effects of the action) into the world description T. The description of the possible worlds after the action are the maximal subsets S of T U F that are consistent and F <;;; S [Ginsberg and Smith, 1987a].

The PMA, on the other hand, distinguisheS the state of the world from a theory that describes the world. The state of the world is identified with a Herbrand model. This distinction leads to different effects in represent­ ing the frame principle of actions between the PWA and PMA. In particular, the frame principle of actions says that there are minimal changes in the world when an ac­ tion is performed. The PWA translates this into "min­ imal changes in the description of the world when an action is performed." However, as has been shown by Winslett [Winslett, 1988], since a minimal change in the state of the world does not necessarily correspond to a minimal change in the description of the world, the PWA may not give a correct handling of incomplete in­ formation. On the other hand, the PMA represents the minimal change on the state of the world rather than on the description of the world when an action is performed, and thus can avoid the problems with the PWA.

Does the PMA always give satisfactory results for rea­ soning about action? In this paper, we show that the PMA is sometimes incorrect in that it may give unin­ tuitive results relative to the frame problem, and for its dual, the ramification problem. In developing our alter­ native approach we found it helpful to classify actions into definite and indefinite actions to systematize a com­ parison between the PMA and our new proposal. The PMA is shown to be inadequate for both definite and indefinite actions in the general case. Our proposal for reasoning about actions is based on persistence. We show that our approach can avoid the problems with the PMA and PWA in most cases, and yield more intuitive results, regardless of whether the action is definite or indefinite.

The paper is organized as follows. In the following section we briefly review the PMA, and illustrate the problem with the PMA by an intuitive example. We then start to develop our new approach. In section 3 we introduce the concepts of definite and indefinite ac­ tions, which are helpful for our discussion. We define the persistence set in section 4, and based on this def­ inition we give a precise representation of the effect of action. In section 5 we present more examples to show how our approach works for reasoning about action. We then compare our approach with the PMA in detail from a logical viewpoint in section 6. Finally, we discuss the related work with our approach presented in this paper.

2 The Problem with the PMA

We first briefly review Winslett's PMA. LetT be a first order theory, which is treated as a description of the world and C be a subset of formulas in T representing the d~main constraints about the world called protected formulas. To reason about the effects of performing an action with post-condition F (a first order formula), the PMA considers the effect of the action on each possible state of the world, that is, on each model ofT. The PMA changes the truth valuations of the ground atoms in each model as little as possible in order to make both F and the protected formulas of T true in that model. The possible states of the world after the performance of the action are all those models thus produced. Winslett made a Herbrand universe assumption so that models are simply subset of the Herbrand base.

Formally, we say that two models Mt and M2 differ on a ground atom p if p appears in exactly one of Mt and M2. Let Diff(M1 , M2) denote the set of all different ground atoms between Mt and M2, M a model ofT, and F a first order formula. Incorporate(F, M) is the set of all models M' such that

1. F and the protected formulas of T are true in M';

1. for any model Mn satisfying 1, Diff(M, Mn) ~ Diff(M, M') implies Mn = M'.

Then Winslett defined the possible states of the world resulting from applying an action with post-condition F as

UMeModei·(T) Incorporate(F, M) .

The PMA uses the principle of minimal change on models to represent the frame principle of actions when an action is performed. The question is: is it always reasonable? Let us consider the following example.

Example 1. Imagine an instructional computer system in which all programs have three statuses called running, terminated, and abnormally terminated ( ab-terminated). At any time point , each program has only one of the three statuses. We also assume that for any program, the only occurrence of abnormal termina­ tion of the program is caused by system errors. The program executes the next instruction on receiving the input "continue". Formally, we have two domain con­ straints (i.e., protected formulas in Winslett's terminol­ ogy) to represent this world:

(1) 'l:/xy (running(x, y) E!1 terminated(x, y)$

ab-terminated(x, y)),

(2) 'l:/xy (system-ok(y) :J -,ab-terminated(x, y)), where $is exclusive or, running(x, y) means that pro­ gram x is running on system y (similarly for the mean­ ings of terminated(x,y) and ab-terminated(x,y)), and system-ok(y) means that system y is at a normal status. Suppose the current unprotected formulas are

(3) system-ok(a),

(4) running(p, a).

From the definition of the PMA, the current descrip­ tion of the world T consists of (1) - (4), and the only model So ofT consists of ground atoms (3) and ( 4), i.e., So = {system-ok(a), running(p, a)}. By the Herbrand model convention the negative ground atoms such as

-,terminated(p, a) and ...,ab-terminated(p, a) are omit­ ted. Now consider the action continue . After this ac­ tion, what is the status of program p? Intuitively, after a while, the status of p has two possibilities - one is still running, the other is terminated (since there is no any explicit information to infer that system errors may have occurred after continue, p's status will not be ab­ normally terminated). So the post-condition of continue is simply running(p, a) V terminated(p, a). Now what can we say for the result of continue? From the previ­ ous definition, it is easy to show that

UMeModei.(T) Incorporate(Post(continue), M) =So:

That is, the only possible state of the world resultmg from action continue is that nothing has changed, i.e., the program will run forever if no system error occurs. However, this is unreasonable from our intuition. It is not difficult to show that the PWA also gives the same result: the only possible world to add running(p, a) V terminated(p, a) in T is T itself. 0

The reason for this unintuitive result is that the PMA represents the frame principle of actions by the minim~l change on models when an action is performed, and th1s is not always correct . This can be easily seen if we con­ sider the persistence of facts in the state of the world when an action is performed. Informally, we say that a fact persists if given that no relevant action has oc­ curred over a stretch of time, the fact does not change its truth value over that time [Shoham, 1988]. In our example, the effect of action continue is running(p, a) V terminated(p, a), and the initial state of the world is {system-ok(a), running(p, a)} . The only fact that persists is system-ok(a), and since running(p, a) V terminated(p, a) may or may not cause the truth value of running(p, a) to change, we have no any reason to say that running(p, a) must persist, where the PMA does just because the state { system-ok(a), running(p, a)} satisfies the formula running(p, a) Vterminated(p, a) be­ fore continue is performed. The assumptions underlying the PMA can therefore be sometimes too strong.

3 Definite and Indefinite Actions

Consider a first order language L with equality. Let F(p) be a first order formula, where pis a tuple of non-equality predicate symbols occurring in the formula. Let I be a Herbrand interpretation of the language, and III the universe of I. For simplifying our discussion, in this pa­ per, we fix the universe of interpretations in lang~age ~ · That is, we only consider the class of interpretatwns m which for any two interpretations lt,h of L, lltl = II2I , and each function symbol (constant is a 0-ary function symbol) of L has the same interpretation in It and I2 respectively.

Definition 1 A formula F(p) is definite if for any two interpretations It, h such that It I= F(p) and h I= F(p), and for each Pi E p and each tuple of constants (functions) c which has the same arity as Pi, It I= Pi(c) iff h I= Pi( c). 0

Intuitively, a formula F is definite if for any two inter­ pretations (remember that we fix the universe of inter­ pretations of L) in which F is satisfied, each predicate symbol occurring in F has the same extension in these two interpretations. We say that a formula is indefinite if it is not definite and not a tautology. It is not difficult to decide if a formula is indefinite.

Proposition 1 The following results hold:

1. 3x[-.]p(x) is indefinite, where p is a non-equality predicate symbol,
2. for any formulas Ft and F2, where Ft "¥ F2, Ft V F2 is indefinite if Ft V F2 is not a tautology.

The notation [-.] means that the negation sign -.may or may not appear . 0 .

From the concepts of definite and indefinite formu­ las, we classify actions into two kinds, - definite and indefinite actions. Herbrand models represent states of the world and it is assumed that there is a set of do­ main constraints C about the world, which are satis­ fied by each state of the world. An action a is defined by a pre-condition Pre( a) and a post-condition Post( a), where Pre(a) and Post(a) are first order formulas. We say that a is applicable to a state S of the world if S f= Pre(a) . Informally, action a changes the state of the world from one to another, and in the resulting state of the world, Post( a) is satisfied. The aim of this paper is to give a reasonable representation for the possible re­ sulting states of the world when an action is performed on a state of the world . We also assume that the pre­ condition Pre( a) is complete, in the sense that the action can definitely be performed if the pre-condition is satis­ fied. The post-condition of the action, however, will not be assumed complete, since there may be many ramifi­ cations of an action in any particular situation.

Definition 2 An action a is definite if

1. Post(a) is a definite formula, and
2. for any formulaF satisfying {Post(a)}UC f= F but C ~ F , where F is not followed from the expansion rule or the 3-introduction rule (i .e., not followed via A f= A VB or A(c) f= 3xA(x)), F is definite. 0

Following Definition 2, we say an action a is indefinite if Post( a) is indefinite; or for some formula F satisfying Condition 2 of Definition 2, F is indefinite.

4 A Persistence-based Theory of Actions

In this section, we define a precise representation for the possible states of the world resulting from actions based on persistence. Let So be the current state of the world, C be the set of domain constraints and a be an action.

Definition 3 Suppose action a is applicable to S0 , i.e., So f= Pre(a) . Let

1 By the Her brand model convention the negative ground atoms are omitted. However, for convenience in our discus­ sion, we assume -.f; E So if f; ~ So, where f; is in the Herbrand base.

The persistence set 6.(a, So) of So with respect to the action a is defined as

We explain this definition as follows. Let a be an ac­ tion applicable to S0 · Obviously, after a's performance, a fact fin So must change iff is inconsistent with Post( a) with respect to C, i.e., {Post(a)}UC f= -.f. We call such a fact non-persistent. On the other hand, iff or -.f ap­ pears in a disjunction which is entailed by Post(a) (or together with other formulas, i.e., C), we say that f is indefinitely affected by a. The intuitive meaning of an in­ definite effect is that after performing a the satisfaction of Post(a) in the resulting state may or may not cause a change of the truth value off, but we do not know which is the case. Finally, if there exists a subset F of So in which some fact is non-persistent or indefinitely affected by a, and f is entailed by F (or together with C), then f is implicitly affected by a because after a's performance, f may lose its justification F . In this case, if there is no other justification for f, it is incautious to assume that f is persistent. We call those facts that are either implicitly or indefinitely affected by a muta­ ble. Thus, the persistent facts in So are those that are not non-persistent or not mutable. This is shown by the following diagram.

Intuitively, the persistence set 6.(a, So) is the maximal set that includes all facts in So which must persist when a is performed, and further, it excludes any fact in So whose truth value must or might change only after a's performance. In fact, this persistence definition is based on a conservative principle. As discussed in Section 2, it is generally assumed that if an action is irrelevant to some fact, that fact will persist during the performance of that action. Unfortunately, there is no purely logical method which is strong enough to formalize the irrel­ evance of actions in the general case [Shoham, 1987]. But we can resort to the dual. It is possible to identify the widest possible scope of action relevance, and this is through non-persistent and mutable sets. More details about persistence can be found in [Zhang and Foo, 1992].

Proposition 2 For any state of the world So and any action a which is applicable to So, the persistence set il(a, So) is unique. 0

The representation of the persistence-based formaliza­ tion of actions can then be expressed as follows.

Definition 4 We say that a Herbrand interpretation S is a possible resulting state of the world after action a is performed on the state of the world So, if

1. S I= C, 2. S I= Post(a), and

• 3 . .il(a, So)~ S .

We define the set of all such resulting states as the pos­ sible states of the world resulting from applying action a on S0 , denoted as Result( a, S0 ) . Call this way of deter­ mining the possible resulting states the Persistence Set Approach, PSA in brief. 0

5 More Examples

Let us consider the example presented in Section 2 once again. From Definition 2 and Definition 3, we know that continue is indefinite, and the persistence set il(continue, So)= {system-ok(a)} (recall that So= {system-ok(a),running(p,a)}), thus there are two pos­ sible states of the world

S = {system-ok(a), running(p, a)}, and S' = { system-ok( a), terminated(p, a)},

which are the desired results for this example. The PSA can differ from the PMA even for definite actions, as is shown in the next example.

Example 2. Consider the living room domain which was first proposed by Ginsberg and Smith [Ginsberg and Smith, 1987a] and reconsidered by Winslett [Winslett, 1988; Winslett, 1991]. Ignoring the detailed semantic de­ scription of this domain (see [Ginsberg and Smith, 1987a; Winslett, 1988]), here we just summarize its set of do­ main constraints C as follows :

1. duct(x) = (x = duct1 V x = duct2)
2. location(x) = (duct(x) V x =floor)
3. (on(x, y) /1. on(x, z)) ::> (y = z)
4. (on(x, y) /1. on(z, y)) ::> (z = x Vy =floor)
5. (blocked( duct!) /1. blocked(duct2)) = stuf fy(room)
6. (duct(y) /1. 3xon(x,y)) = blocked(y)
7. on(x , y) ::> (location(y) /1. -.location(x))
8. 3yon(x, y) V location(x)

Suppose the initial description of the world T is CU {on(TV,ductl), on(plant, duct2),on( magazine,/loor), 3yon(newspaper, y)}. (Re­ member that the PWA and the PMA do not exclude incomplete information in the world description) . From (4) and (8) we know that T 1- on( newspaper, floor) . Furthermore, it is easy to see that the only Herbrand model So of T 2 is

{ on(TV, duct1 ), on(plant, duct2), on( newspaper, floor), on( magazine, floor), blocked( ductl), blocked( duct2), stuffy( room)} .

So in the initial state of the world, the newspaper is on the floor . Now consider an action to move TV from duct 1 to floor (i.e., moving(TV, floor) . Its pre-condition is on(TV, ductl) and post-condition is on(TV, floor)) . Ac­ cording to the PWA, the only possible world with this action is

Now the question is: is the newspaper still on the floor? What we can get from T' is T' I= on( newspaper, floor) Von( newspaper, duct1) .

Thus from the PWA, there are two possible posi­ tions of the newspaper - one says that after action moving(TV, floor) the newspaper is still on the floor , which is the intuitive result from the frame principle; the other says that after the action, the newspaper flies to duct 1. How can we explain the second possible po­ sition of the newspaper? One explanation is that this change is caused by powerfully sucking air through the windows [Winslett, 1988]. But why can't the magazine change its position for the same reason?

The PSA, on the other hand, avoids this unintuitive result. From Definition 3, the persistence set of So with respect to moving(TV, floor) is

{on(plant, duct2), on( magazine , floor), on( newspaper, floor), blocked(duct2)} .

So the only resulting state S after this action is

{on(TV, floor), on(plant , duct2), blocked(duct2), on( magazine, floor), on( newspaper, floor)},

and this is our desired result .

It is not difficult to show that moving(TV, floor) is a definite action. By applying the PMA, however , what we get are not only the desirable state S, but also other five undesirable states [Winslett , 1988] . Winslett ar­ gued that there was a way to introduce some prioriti­ zation on predicates, such that the undesired states can be eliminated by minimizing certain predicates accord­ ing to the prioritization [Winslett, 1991]. Winslett also showed that this idea is closely related to Lifschitz's pri­ oritized circumscription [Lifschitz, 1985]. However, this approach is not suitable for indefinite actions. Consider­ ing Example 1 (ignoring the detail) it is not difficult to show that applying the PMA, regardless of how priori­ tization on predicates are defined, the desirable results are not obtainable [Zhang and Foo, 1992] . 0

2 Following Winslett, we omit the "location" and "duct" atoms in the model for brevity.

6 Comparison with the PMA

In previous sections, we have shown that the PSA can give more intuitive results than the PMA for both def­ inite and indefinite actions. Sometimes the PMA gives more possibilities than expected (i.e., move TV from duct1 to the floor in Example 2), and sometimes it gives less (i.e., the continue action in Example 1). Our objec­ tive in this section is to provide a comparison of logical properties of the PMA with the PSA.

Despite the fact that the basic motivations of these two approaches are quite different we can examine the relations between them by considering the mutable sets obtained from these two different approaches. Let So be an initial state of the world, C the set of domain constraints of the world, a an action applicable to So, and ~(a, So) the persistence set of So with respect to a. Let f(a, So) be the set of non-persistent facts of So (the facts that must change), i.e., r(a, So) = {! I f E So and {Post(a)} U C I= -.!}. Obviously, for any S E Result( a, So) and S' E Incorporate(Post(a), So), f(a, So) n S = 0 and f(a , So) n S' = 0. The mutable set obtained from the PSA is

and its analog obtained from the PMA, DPMA(a, So), is

We know that in the PMA, n Incorporate(Post(a), So) is the set of all facts that are true in every possible model. So So-n Incorporate(Post(a), So)- f(a, So) is the set of mutable facts corresponding to the PMA.

Definition 5 Let f be a positive or negative ground atom /, E a set of positive or negative ground atoms. We say that E is a support setoff with respect to C, where C is a set of formulas, if

1. E and C are consistent,
2. E U C I= /, where E ~ f and C ~ f,
3. for any f' E E, E- {!'} U C ~ f. 0

Definition 6 Let So be a state of the world, C the set domain constraints of the world, F C So and f E So. We say that F influences J, if there e~ists a support set E off with respect to C in So, i.e., E ~ S0 , such that F~E. o

Directly from this definition, we know that if F in­ fluences f, then for any non-empty subset F' of F, F' influences f. We say that F uniquely influences f if there exists the unique minimal support set E off with respect to C in So such that F ~ E. So far, we have the following result.

Proposition 3 Let a be a definite or indefinite action applicable to So . Then

1. for each fact f E DpsA(a, So), f is influenced by some subset of f(a, So) or indefinitely affected by a;
2. if DPMA(a, So)- DpsA(a, So)::/; 0, then for each fact f E DPMA(a, So)- DpsA(a, So), f is neither uniquely influenced by any subset of f(a, So) nor indefinitely affected by a. 0

This proposition simply says that each mutable fact obtained by the PSA is based on some logical relevance, i.e., influence or indefiniteness. However, in the PMA, some fact may be mutable for no reason. This is why the PMA may have some unintended effects in reasoning about an action.

7 Related Work

In this paper, we presented a formalization of actions based on persistence, which we call the Persistence Set Approach (PSA), and compared it with the PMA in de­ tail. We showed that the PSA provides a unified frame­ work for representing effects of definite and indefinite actions, and argued that it is conceptually simple and plausible for reasoning about action. We notice that the computation of persistence sets seems difficult generallr. In the full version of this paper ([Zhang and Foo, 1992]) we present an algorithmic description and a computa­ tional analysis of the PSA necessary for its implementa­ tion. We argue that it is possible to get a computation­ ally tractable method for some special cases, i.e., only definite actions occur or all constraints are Horn clauses. More details about the computation of persistence sets will be considered in our further work.

We think that the PSA can be applied as a general methodology for modeling state change. There are a number of issues related to the PSA that we are consid­ ering. Here we list some of them:

• the problem of multiple extensions
• persistence updating in knowledge bases
• representing temporal persistence

The PSA, at least in general, induces multiple exten­ sions from a single description of the world (i.e., Ex­ ample 1) . In order to avoid conflicting extensions (or unintuitive resulting states) it is necessary to provide more domain information in the PSA for some appli­ cations. It seems feasible to introduce some perference policy into the PSA to handle the problem of multiple extensions (i.e., the idea of prioritized circumscription [Lifschitz, 1985] or eptistemic entrenchment [Gardenfors and Makinson, 1988]).

The other related work is knowledge base updates. While there are many approaches in this area, most of them have some limitations [Katsuno and Mendel­ zan, 1991] . One of the difficulties is to update knowl­ edge base with indefinite information (i.e., something like p( a) V q( b) or 3xp( x)). As the PSA provides a unified viewpoint for processing definite and indefinite informa­ tion, we argue that the idea of persistence may provide new insights into knowledge base updates. Furthermore, it seems that the PSA also provides a unified representa­ tion for upadtes and actions. In [Zhang and Foo, 1993b], we show that under the persistent semantics, given a spe­ cific update operator some related action (or a sequence of actions) can be generated.

The PSA presents a principle of persistence for rea­ soning about change, which is quite different from the principle of minimality that is widely used in current approaches. It would not be difficult to combine the persistence idea into other formalisms . In [Zhang and Foo, 1993a] we presented a persistence-based formaliza­ tion within the situation calculus framework [McCarthy and Hayes, 1969] to represent temporal persistence, and showed that the Yale Shoolting Problem [Hanks and Mc­ Dermott, 1987] is solved in a natural way, that is quite different from those minimality-based methods.

Acknowledgements

This research is supported in part by a grant from the Australian Research Council. The first author is sup­ ported by a SOPF scholarship from the Australian Gov­ ernment. Discussions with members of the Knowledge Systems Group of the University of Sydney have im­ proved the presentation.