Minimal Change and Maximal Coherence: A Basis for Belief Revision and Reasoning about Actions

1 Introduction

Belief revision is the process by which an agent re­ vises her set of beliefs at the current instant of time, based on some input from the external world, to move into the next instant of time, possibly with a different set of beliefs. Thus the essential problem in belief revision is determining what beliefs the agent must acquire and what beliefs the agent must give up.

Reasoning about actions usually involves deter­ mining the state of the world after an action has been performed. Again this involves determining what beliefs should change and what beliefs should not change when moving from one state to another. The latter problem has long been known as the frame problem [McCarthy and Hayes, 1969]. Associated with this is the problem of specifying all the side­ effects or ramifications of an action and making sure that the agent acquires (or gives up) beliefs about those side-effects as well.

Both belief revision and reasoning about actions,

Norman Y. Foo

University of Sydney Sydney, NSW-2006

Australia

Email: norman@basser.oz.au

involve reasoning about change. However very little work has been done in analyzing the principles com­ mon to both these areas. Work on belief revision has for the most part concentrated on building efficient systems that perform belief revision [Doyle, 1979, de Kleer, 1986]. Work on reasoning about actions has addressed both the computational and founda­ tional aspects [Brown, 1987, Georgeff and Lansky, 1987], but has been studied independently of belief revision. In this paper, we present a unified picture of both areas by formalizing the underlying princi­ ples of belief revision and reasoning about actions.

Minimal change and maximal coherence are two of the most important principles involved in reason­ ing about change. Minimization has been used in AI and philosophical logic in a variety of ways. In this paper, by minimizing change we mean minimiz­ ing the acquisition of beliefs or minimizing the loss of beliefs when an agent moves from one state to an­ other . By maximizing coherence we mean retaining as many coherent beliefs as possible during a state change.

Theories of belief revision can be divided into two broad categories - the coherence and foundational theories of belief revision. A detailed analysis of both these theories has been carried out elsewhere [Rao and Foo, 1989]. In this paper we give a brief overview of the coherence theory of belief revision, which is based on the principles of minimal change and maximal coherence. The axiomatization of the theory is based on the work by Alchourron, Gar­ denfors and Makinson [1985] (henceforth called the AGM-theory) and the semantics is based on · the possible-worlds formulation . · This theory of belief revision is then used to describe a theory of actions which has a clear semantics and also solves the con­ ceptual frame and ramification problems. 1 One of the advantages of having a uniform framework for belief revision and reasoning about actions, is that it facilitates reasoning in dynamic situations, where the world changes during the execution of an action. As the paper is part of the first author's thesis, interested readers are referred to the complete report [Rao, 1989] for more details.

1 No claims are being made regarding the computa­ tional efficiency of our solution. We address only the conceptual problem in this paper.

2 Coherence Theory of Belief Revision

The underlying logic of belief revision is a modal logic of time-dependent beliefs. The formula BEL( a, t, <P) denotes that the agent a believes <P at time t. A branching time temporal logic is used with a stan­ dard first-order interpretation. Quantifying individ­ ual constants into the scope of modal operators is not allowed, but is allowed for time constants. The semantics for such a belief system can be given in terms of a slightly modified Kripke interpretation. The axiomatization is a KD45 axiomatization to­ gether with the axioms of transitivity and backwards linearity for time [Rao, 1989].

Further, we shall treat the BEL operator as a self-belief operator as in Autoepistemic Logic (AEL) [Konolige, 1988, Moore, 1985]. This interpretation will be called an autoepistemic K ripke interpreta­ tion denoted by AKI. The attractive feature of such a time-dependent AE belief system is that the stable sets or possible worlds are uniquely determined by the first-order formulas and universal AE (UAE) be­ liefs (formulas of the form 'v't BEL( a, t, <P )) that they contain. This feature will be exploited in discussing the dynamics of the belief system.

There are three possible states (ignoring the in­ consistent state) in which an agent could be at some time t and world w with respect to a formula <P re­ ceived by the agent from the external world. These states are: (1) the agent believes in <P at t, (2) the agent believes in ·<P at t, and (3) the agent does not believe in <P nor ·<P at t and hence the agent is uncommitted about ¢. By dynamics of belief systems or belief revision we mean the process by which an agent moves from one of the three states (1, 2 or 3) to any of the other two. Ignoring the trivial transitions of remaining in the same state we are left with six different transitions: (1-2) (N­ )Expansion: Uncommitted state - Belief in (·) ¢, (3-4) (N-)Contraction: Belief in ( 'J <P - Un­ committed state, (5-6) (N- )Revision: Belief in ( <P) ·<P - Belief in ( ·<P) ¢. The terminology and approach is an extension of the AGM-theory.

Three dynamic modal operators, EXP. CON, and REV, are introduced to denote the above transitions. Thus EXP(a, t, ¢, u) is read as 'the expansion by the agent a at time t with respect to <P results in time u ', where <P is a first-order sentence and t and u are time points. In fact, u is the next time point to t. Note that there can be more than one next instant, . as the underlying temporal logic is a branching time temporal logic. This makes the logic more expressive than situation calculus [McCarthy and Hayes, 1969] and is equivalent in expressive power to the extended situation calculus discussed by Georgeff [1987].

2 The word "belief revision" will be used in the more general sense to denote dynamics of belief systems and the word "revision" will be used in the more restricted sense as defined above.

The semantics of dynamic operators is based on selection functions, which select some possible worlds as being closer to the current world than the others. When the agent performs expansion or con­ traction, he is said to move into one of these closer worlds and designate these worlds as the worlds of the next time instant(s). The interpretation for this language and the semantics of the dynamic opera­ tions are formally defined as follows:

Definition: The dynamic coherence interpreta­ tion is a tuple, CI = (£, C, AKI}, where £ and C are expansion and contraction functions that map W (worlds), AC (agent constants} TD (time points), and 2w (set of worlds) to a 2T (set of time points) and AKI is an autoepistemic Kripke interpretation.

Definition: A dynamic coherence interpretation CI, satisfies a well-formed formula <P at world w and time point 3 t (written as CI, w, t I= ¢) given the following conditions,

1. CI, w, t I= EXP(a, t, ¢, u) iff u E £(w, a, t, II<PIIc 1 ), where <Pis a first-order sentence.
2. CI, w, t I= CON(a, t, ¢, u) iff u E C(w, a, t, II<PIIc 1 ), where <Pis a first-order sentence.
3. CI, w, t I= REV( a, t , ¢, u) iff CI, w. t I= CON( a, t, ·¢. v) and CI, w, v I= EXP(a, v, ¢, u), where <P is a first-order sentence.

The notation II<PIICJ stands for all the worlds of the interpretation CI, which satisfy ¢. More for­ mally, II<PIICJ = {w I CI, w, t I= <P for all t E TD }. The unique properties of AEL allows us to restrict our attention to first-order sentences rather than ar­ bitrary belief formulas [Rao, 1989].

Axioms (AE1) - (AE5) and (AC1) - (AC4) of Appendix -1 capture the proof-theoretic notion of minimal change and maximal coherence for expan­ sion and contraction, respectively. The seman­ tic conditions analogous to these axioms capture the semantic notion of closest possible worlds [Rao, 1989]. The description of these axioms and seman­ tic conditions and a constructive procedure for £ and C can be found elsewhere [Rao and Foo, 1989, Rao, 1989] . The class of models whose £ (C) se­ lection function satisfies these semantic conditions are called £-models (C-models) . We shall refer to the modal system KD45 together with the above axioms and inference rules as the Coherence Modal System or CS-modal system. We define the class of coherence V-models as models whose B relation is a B-model (i .e. B is serial, transitive and euclidean), £ is a £-model and C is a C-model. The proof of the following theorem, which provides a sound and complete theory of belief revision, is given in the complete report [Rao, 1989].

3 Temporal variables and constants are mapped to time points by a standard temporal assignment [Rao, 1989] .

Theorem: The coherence modal system or the CS-modal system is sound and complete with re­ spect to the class of coherence V-models.

3 Reasoning about Actions

In this section we shall treat actions as a special type of dynamic operation and define it in terms of the other dynamic operators, EXP, CON and REV. Thus reasoning about actions is also based on the intuitive principles of minimal change and maximal coherence. As expansions and contractions can be viewed as the semantic counterparts of the addlist and deletelist of STRIPS [Fikes and Nilsson, 1971], the logic described here can be viewed as a semantic theory for STRIPS and the principles of ~init?al change and maximal coherence as a generalizatiOn of the STRIPS assumption.

In addition to predicate letters the logic of actions consists of action letters, which are used to form ac­ tion formulas. The symbols';' and 'II' denote sequen­ tial and parallel actions. The modal operator ACT is used to denote the performance of an action. If the modal ACT formula is satisfiable/provable then the action is said to be successful; otherwise the action is said to have failed. This allows reasoning about both successful and failed actions which is crucial for reasoning about real world domains [Georgeff, 1987]. A well-formed action formula can either be a simple action formula or a sequential or parallel action formula. A simple action formula is denoted by z(s1, ... sn)a where z is an action letter, sl···sn are first-order terms and a is the agent who is per­ forming the action. The modal formula ACT(t, 'lj; , u) is read as 'at timet, action formula 'lj; is carried out to reach time point u'. The action formula 'lj; can be a combination of sequential or parallel action formulas .

Actions have usually been defined in terms of pre­ conditions, which must hold before the action is per­ formed , and the consequents, which must hold af­ ter the action has been performed. This approach has been used in situation calculus [McCarthy and Hayes, 1969] and STRIPS [Fikes and Nilsson, 1971] . Thus associated with every simple action formula 'lj;, ar~ two formulas p.P and c.P, which are res~ec­ tively the precondition and consequent of 'lj;. Given the current world, a time point and a simple action formula, the action function A selects the closest possible world(s) at the next time point(s), that sat­ isfy the following conditions:

• the precondition formula of the action is be­ lieved in the current world
• the consequent of the action must be believed at the next time instant, with minimal change and maximal coherence with respect to the original world.

The interesting part of the condition is the italicized part which helps in solving the frame and ramifica­ tion problems. In the case of sequential action formulas the action function A will select the closest world~ with respect to each and every action formula in that sequence. In the case of parallel action for­ mulas, the action function A tries to select the same closest worlds with respect to all the action formulas executed in parallel. As the closest world is required to be consistent, parallel actions that interfere will be blocked by the action formula [Rao, 1989].

A plan interpretation, PI, is a dynamic coherence interpretation CI, together with an action function A 4 · The modal operator ACT is given a semantics similar to the semantics of EXP and CON usine; the selection function A . This is done elsewhere lRao, 1989] and here we discuss only the axioms of sim­ ple and sequential actions. The axioms which follow determine how the selection function A is related to the other functions discussed in the previous sec­ tion. The axioms and inference rules are listed in Appendix - I.

The Axiom of Simple Actions (AAl) states that if agent a performs a simple action at time t to result in time u, then the precondition of the.ac­ tion must have been believed by the agent at time t and the agent must have revised at t with respect to the consequent of the action: The Axiom of Se­ quential Actions (AA2) states that carry.ing out a sequence of actions is equivalent to carrymg out the first action and then carrying out the next ac­ tion in the resulting state. In addition to the above axioms we also need the inference rule (RA1) which states that equivalent actions have equivalent effects. The axiom of parallel actions and the soundness and completeness of the system are discussed in the com­ plete report [Rao, 1989].

Example: Consider a situation occurring at time point t1, in which blocks A a.nd B are ~n the table. The situation at t1 can be said to contam the following set of beliefs.

Now if the agent carries out the ac­ tion 'move( A, B)a 1 , assuming that no qual!ficat!on disables this action (i .e., ignoring the qualificatiOn problem), one would ideally like to comple~ely de­ termine the state of the world after the actiOn has been performed without stating any frame axioms. This is in fact the crux of the frame and ramification problems.

4 The selection function A can be described in terms of the selection functions [ and C described earlier. This, together with the constructive proced_ure for th: selection functions [ and C, makes the selection funct10n A less

mysterious.

If t2 is the time point after the action move( A, B)a 1 , and the action has the usual precon­ ditions and consequents [Lifschitz, 1987], then from the axiom of simple actions we have:

Using the domain closure axiom and unique names assumption it is easy to verify that the precondi­ tion is satisfied by the belief system at time t 1. If the revision formula is satisfiable at tb we not only have the successful completion of the action move( A, B)a 1 , but also a completely determined next state giving all the beliefs of the agent at that time point. As discussed earlier, revision with respect to on(A,B) is contraction with respect to -.on(A,B) followed by expansion with respect to on(A,B). Let t2' be the time point after contraction. Using the axioms of contraction and the beliefs at time t1, one can derive the following beliefs for time t2'. (The satisfaction of these beliefs can also be verified using the selection function & or the corre­ sponding construction procedure.)

Contraction forces the agent to give up belief in -.on(A,B). If the agent continues to believe on(A,table), then the UAE belief (L2) will force him to believe -.on(A,B) as well. Hence the agent is forced to give up belief in on( A, table) as well.

Expanding at t2' with respect to the formula on(A,B), yields the following beliefs at time t2.

Expansion forces the agent to believe on(A,B). From the UAE belief (L2) the agent is also forced to be­ lieve -.on(A,table). The primary effect of the ac­ tion is to make the agent believe on(A,B) and the secondary effect or ramifications of the action is to make the agent believe -.on(A,table). Thus the for­ mula ACT(tl, move( A, B)a 1 , t2) is satisfiable and the time point t2 gives all the beliefs of the agent after the action has been performed. Thus our the­ ory of actions provides an inferential solution and a model-theoretic solution to the frame and ramifi­ cation problems based on the principles of minimal change and maximal coherence.

The example presented above is a very simple one and has been used mainly to illustrate the theory. More complicated, multiple-agent, dynamic-world problems are discussed in the complete report [Rao, 1989]. For example consider the situation where block B is an ice-block and it melts before the block A can be placed on top of it. As this is a change caused by nature, we essentially have a revision by the agent NATURE at time t1 with respect to the formula -.on( B. table). It is impossible to have a sin­ gle time point where the move action by the agent and the above revision be satisfiable. As the agent has no control over the changes caused by NATURE, we can impose a partial order on the dynamic op­ erations and conclude that the revision performed by the agent NATURE succeeds and the move action by the agent fails. Thus the unified theory of be­ lief revision and reasoning about actions provides a framework for reasoning about dynamic, real-world situations, where the world changes during the per­ formance of an action.

4 Comparison

AGM Theory

There are significant differences between the co­ herence theory of belief revision as outlined by Giu­ denfors et. a!. [1985, 1988] and that of section 2. Firstly, AGM-theory carries out the dynamic anal­ ysis at a meta-level and hence lacks a model-theory and the soundness and completeness result as out­ lined in this paper. Also unlike the theory outlined in section 2, AGM-theory does not handle nested be­ liefs and does not exhibit static nonmonotonic prop­ erties [Rao, 1989]. Finally, AGM-theory does not consider reasoning about actions.

Lifschitz's Approach

Lifschitz [1987] introduces two predicates, success and affects, to define the notion of a successful action and the notion of what fluents are affected by an ac­ tion. Using these, he defines the law of change(LC) and law of inertia(LI) By circumscribing the predi­ cate causes, Lifschitz is able to solve the frame prob­ lem. This is hardly surprising because causes de­ scribes the dynamics of the belief system by speci­ fying what changes when the agent moves from one state to another as a result of an action. The pres­ ence of (LC) and minimization of causes is essen­ tially equivalent to minimizing the change caused by an action. Similarly, the presence of (LI) alld minimization of causes is equivalent to maximizing the coherence between state changes. Also the def­ initions of causes and precond are analogous to the axiom of simple actions. Hence Lifschitz's theory es­ sentially embodies the principles of minimal change and maximal coherence.

However there are significant differences between our approach and that of Lifschitz. Firstly, Lif­ schitz's approach does not solve the ramification problem. Also the minimization process of Lifschitz is local [Hanks and McDermott, 1987] (i .e. , with re­ spect to a particular predicate) and relies on the user to specify the world in certain ways, whereas in the theory proposed here the minimization process is global (i.e., with respect to all the beliefs of the agent) and is independent of the syntax. Finally, the approach is incapable of handling dynamic situ­ ations. This is because the ontology is not powerful enough to represent or reason about changes caused by the external world. Shoham's Approach Based on the notion of preferential logics, Shoham [1987] introduces the logic of chronological igno­ rance. The underlying logic is a modal logic of tem­ poral knowledge. A model M2 of the above logic is preferred over another model M1 , if M2 is chronolog­ ically more ignorant than M1 . The preferred mod­ els in the logic of chronological ignorance are the chronologically maximally ignorant (c. m. i.) mod­ els. By considering only the c.m.i. models of the given problem Shoham is able to solve the qualifi­ cation problem (see the complete report [Rao, 1989] for more details) and extended prediction problem (a generalized form of the frame problem).

The notion of c.m.i . models can be simplified as follows - (1) prefer maximally ignorant models at each state (or time point) and (2) prefer maximally ignorant models when moving from one time point to another or during a state change. The first solves the qualification problem and the second solves the frame problem. Notice that in both cases one need not worry about a sequence of time points chrono­ logically backward from the current time point. 5

The net effect of revision is to believe as much of the original beliefs as possible and acquire as few beliefs as required. Acquiring as few beliefs as pos­ sible is the same as minimization of beliefs or max­ imization of non-beliefs (or ignorance in the case of knowledge). Thus (2) above, embodies the principle of minimal change.

The main differences between Shoham 's approach and the one outlined in this paper are as follows: Firstly, his theory does not provide an axiomatic approach to the frame and ramification problems. Secondly, the principles of minimal change and max­ imal coherence are more general than the notion of chronologically maximizing ignorance. As a result our theory can be applied to database updates, be­ lief revision, and reasoning about actions. However, it should be noted that Shoham defines a special class of theories called causal theories, which have an unique c.m.i model, and gives an algorithm for computing it. As mentioned before, this paper does not address the issue of efficient algorithms for com­ puting contractions and revisions.

Reiter's Approach

In default logic [Reiter, 1980] one assumes by de­ fault that all actions and facts are normal. Ac­ tions which change the truth-value of certain facts are considered to be abnormal with respect to those facts . Thus given the default rules and the abnor­ mality conditions the theory is supposed to pre­ dict the facts that will hold after the action has been performed. Unfortunately, this approach and other similar approaches using circumscription lead to counter-intuitive results as shown by Hanks and McDermott [1987].

5 This fact was also noted by Lifschitz [1987].

In our opm10n, the classical nonmonotonic the­ ories like default logic and circumscription are not suitable for reasoning about change because they do not take into account the interaction with the envi­ ronment. They are suitable only for static reason­ ing where the agent "jumi>s to conclusions" based on incomplete information [Rao, 1989] . Attempts to rectify the problem and make them suitable for dy­ namic reasoning, require extensive reformulation as done by Lifschitz and in any case has to incorporate some principles of change as discussed in this paper.

Possible-worlds Approach

Ginsberg and Smith [1987] first proposed the use of the possible-worlds model for solving the qual­ ification, frame, and ramification problems. They provide a constructive procedure for computing the closest possible worlds. Their approach has certain problems [Winslett, 1988] as they minimize the for­ mulas in the world and not the beliefs of the agent at a particular world as done in this paper. The sig­ nificant difference between the possible-models ap­ proach (PMA) [Winslett, 1988] and our approach is the inability of the PMA to represent uncommitted states of the agent . This makes the notion of mini­ mal change different in the two theories.

None of the above approaches are capable of han­ dling dynamic situations 6 (the ice block example), where the state of the world changes during the ex­ ecution of an action. This requires an explicit cou­ pling of belief revision and reasoning about actions as carried out in this paper. Such situations will become more common when one starts addressing real-world problems.

5 Conclusion

This paper unifies the work in belief revision and rea­ soning about actions by analyzing the principles of minimal change and maximal coherence which forms a core part of both the areas. A sound and complete theory of belief revision is provided which is then used to represent and reason about actions. This theory of action solves the conceptual frame and ramification problems by utilizing the intuitive prin­ ciples of minimal change and maximal coherence. It also provides a framework to reason about dynamic situations.

Acknowledgement: We would like to thank Mike Georgeff, Dave Wilkins and the anonymous referees' for their helpful comments. The first au­ thor was supported by the Sydney University Post­ graduate Scholarship and the Research Foundation for Information Technology. Thanks are also due to IBM Corp. for their generous support during our stay at IBM T.J. Watson Research Center and IBM Thornwood respectively.

6 More recently, Lifschitz and Rabinov [1989] have proposed a circumscriptive formalism to deal with dy­ namic situations. But their solution still suffers from some of the other drawbacks mentioned earlier and is incapable of representing multiple-agent domains.