Deriving Properties of Belief Update from Theories of Action (II)
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Knowledge Representation. Pages 732-736.
© 1993 International Joint Conferences on Artificial Intelligence
Abstract
In [d el Val and Shoham , 1992] we showed that the postulates for belief update recently proposed by Katsuno and Mendelzon [1991] can be analytically derived using the formal th eo ry of action proposed by Lin and Shoham [1991] The ront ribution of this paper is twofold: • VVh ereas in [del Val and Shoham, 1992] we o nl y showed that our encoding of th e upd ate problem satisfied the KM postula tes. here we use an independently motivat Pd generalization of the theory of action us ed in t hat pap er to provide a one-to-one co rr es pondence between our construction a nd 1\ M updat e semantics. • VV e show how th e KIVI semantics can lw ge neralized by relaxing our construction in a numb er of ways, each justified in n' rtain intuitiv e circumstances and each corr es ponding to one specific postulate. It. fo llows that. there are reas onabl e upda.t.e ope rators outside the KM family.
- Aichourr6n Ft al .. 1985]
- Carlos E. Akhourr6n , Peter Gardenfors, and David Makinson . On the logic of theory change : Partial meet. functions for cont.ract.ion ilnd revision . .!oumal of Symbolic Logic, 50:510-.530. 198.
- [del \'al and Shoham, 1992] Alvaro del Val and Yoav Shoham. Deriving properties of belief update from the- ories of action. In PI'Oceedings of the Tenth Conference of 11u AAAI, 1992.
- [del Va.l, 1993] Alvaro del Val. Belief Revi$ion and Update. PhD thesis, Stanford University, 1993. [Gardenfors. 1988]
- Peter Gardenfors. /( nowledge in Flux. The ~UT Press, 1988.
- Goldszmidt and Pearl, 1992) Moises Goldszmidt and Judea Pearl. Ra.nk-based systems. In Proceedings of the Third Intenwtional Conference on P1•inciples of Knowledge Rep- resentation and Reasoning, 1992.
- [I\at.suno and Mendelzon, 1991] Hirofumi Katsuno and Al- berto 0. Mendelzon. On the difference between updating a knowledge database and revising it. In Proceedings of the Second International Conference on Principles of Knowl- edge Representation and Reasoning, 1991.
- Lifschit.z, 1990) Vladimir Lifschit.z. Frames in the space of situations. A1•tijicial Intelligence, 46 :365-376, 1990.
- Lin and Shoham, 1991) Fanghzen Lin and Yoav Shoham. Provably col'l'ect. theories of action (preliminary report). In Proceedings of the Ninth Conference of the AAAI, 1991.
- ~Iye rs a.nd Smit.h, 1988)
- Karen L. Myers and David E. Smit.h. The persistence of derived information . In Pro- carlings of /.he Seventh Conference of the AAAI, 1988.
- Reiter. 1992a.) Raymond Reiter. On specifying database up- dates. Technical Report KRR-TR-92-5, Computer Science Depa.rt.m ent. . U niversit.y of Toronto, 1992. [Reit.er, 199'2b)
- Raymond R. Reiter. On formalizing database updates: Preliminary report. In Proceedings of the Third Int ema/.ionCII Confe,•ence on Extending Database Technol- ogy. 1992 .
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Katsuno and Mendelzon [1991] have recently proposed a characterization of belief update in terms of a set. of postulates that every update operator should satisfy. Though these postulates are similar in spirit to those proposed by Gardenfors and colleagues [Akhourron ff a/. , 1985; G a rdenfors . 1988] to characterize beli ef rev i sion , one of the most. novel aspects of the KM proposal is the suggest ion that update and revision should be seen as two distinct types of belief change. Loosely speaking. the latter says that the beliefs may have been wrong and in need of revision , whereas the former says that. the be liefs were correct, but the world has in the meanwhiiP evolved and the beliefs must be updated. According to t.his proposctl , t.herefore, the problem of updatP i;; full da.ment.ally one of reasoning about change, a problem which has received substantial attention over the years in research on non-monotonic temporal reasoniug.
The question we set out to answer in [del Val <~nd Shoham, 1902] is the following : Why should the 1\\ I postulates be accepted? Our answer was based on the idea that since the basic intuition underlying update was one about change, it should be possible to reduce the KM proposal to a theory of action and change. Specifically, the logic behind our answer was as follows :
- We began with an independently motivated the ory of action, namely the one proposed in [Lin and Shoham, 1991].
- 'Ve provided a natural encoding of the update prob lem in this theory of action.
- Finally, we showed that this encoding allowed us to analytically derive the KM postulates.
This argument can be subject to a number of crit icisms . some of which have been articulated by Gold ;;zmidt and Pearl [1992].
- The construction of [del Val and Shoham, 1992] sat i.s_(l'e.s the postulates, but so do others, e.g. [Gold szmidt and Pearl, 1992]. The KM proposal, how ·~ ver , seems to be more general.
- It. can be argued that the representation theorem for 1\ l'vl operators ([Katsuno and Mendelzon, 1991], reviewed in section 2) provides sufficient validation for the KM proposal.
These are quite reasonable concerns, and our goal in this paper is to meet them. We retain the intuition that theories for reasoning about action and change should be at the basis of a solution to the problem of update, but try to answer a more general question than in [del Val and Shoham, 1992], namely: Under what circumstances should the KM postulates be accepted? Our answer has t1ro parts:
- Using an independently motivated generalization of our construction (in a nutshell, allowing the set of facts that. "persist by default" to depend on the cur rent. state of the world), we strengthen our previous results so as to identify a class of theories of action which stands in a one-to-one correspondence with the family of KM operators. We thus address the first. potential concern.
- We show that this correspondence is only achieved by imposing certain arbitrary restrictions on the theory of act. ion. Each of the restrictions we will consider corresponds to exactly one postulate, and t.!Jus the KM proposal can be seen as embodying
these same restrictive assumptions. We will show how relaxing these assumptions leads to reasonable update operators outside the KM family. \-\1e thus address the second concern.
In addition to answering these concerns , our construc tion will also allow us to shed some light on the predi cate frame, which plays a key technical role in a num ber of papers in reasoning about action [Lifschit.z. 1990; Lin and Shoham, 1991], but whose intuitive meaning was somewhat unclear.
One final question concerns our specific choice of a given formal framework to encode update. Admittedly, our formalization of update is comparatively compli cated, but we believe the added complication is worth the price in that we can thereby make explicit the tempo ral evolution of the database, provide greater flexibility for update operators, and explicate the impact on up date of some fundamental problems in reasoning about. change. As regards to language, we use the situation calculus, which allows us to make explicit. the temporal evolution of the database in a. relatively simple way, and with the convenience of using FOL. More generally, the idea of encoding update using techniques from rPasouing about action and non-monotonic temporal reasoning is justified because these techniques have proven fruitful in formulating , and then proposing solutions to, some key problems in reasoning about change. To illust.rak the connection between non-monotonic temporal reasoning and update, suppose we have a. database of facts about. university life, and that we want to update the database with the fact. that Smith is enrolled in CS205 this quar ter. Clearly. this uew fact should not affec t. 111a.ny other facts in the KB, such as the composition of the faculty or t.hc color of t.hc university buildings . On the otlwr ha11d , it. sh.onld have an effect. on , say, her schedule and t.llf' total number of units she is taking; and these changes can in turn have other indirect effects, e. g. on whet her she is a. full-time student. and the amount of tuition she has to pay. which in turn may depend on other factors such as whet.her she is an undergraduate, etc . These arf' clear instances of the fram·e and ramification problcllls. In particular , it. would be unreasonable to require th<" database user to specify in advance all what shou ld or should not. change as a result. of the update.
We believe, therefore , that. any proposed update ,;e mantics must. be defended in terms of its ability to pro vide solutions to these problems, as has also hePn ar gued by Reiter (1992a). The theory of action of [Lin and Shoham, 1991) has some well established properti t>;, in this regard in the case of actions with deterministi c (direct a11d indirect.) effect.s , and our generalization of it. appears to provide enough flexibility to deal with these problems in the context of indeterministic act.ions 1 . In principle, any other satisfactory solution t.o these prob lems could provide a foundation for update, but. t.he gen erality of the results presented in this paper j)I'OYicles strong evidence for the reasonableness of our encoding.
The st.ruct.ure of t.his paper is as foll ows. Sect.ion L.
1 See sect.ion 6 for examples of how indet.ennini;;tic actio 11 ~ can complicate the frame problem
reviews Katsuno and Mendelzon's approach to update. Sect ion 3 encodes the update problem in situation calcu lus . Sections 4 and 5 provide the one-to-one correspon dence between KM semantics and a class of theories of action. Section 6 considers the consequences of relaxing some of the restrictive assumptions on the theory of ac t.ion, thus generalizing the KM proposal. Related work is discussed in the concluding section .
2 Update in propositional languages: Review
Katsuno and Mendelzon proposed eight postulates that should be satisfied by update operators. Let o be an update operator for a propositional language C with a finite number of propositional variables Pc. The KM postulates are the following :
- ( Ul) '!/' o J1 implies p .
- (U2) If ·1/J implies J1 then 1/J o J1 is equivalent to 1/J .
- ( U3) If V' and p are satisfiable then 1/J o p. is also satis fiable.
- (U4) IfF 1/.· 1 = V'2 and F= P.1 = P.2 then 1/J1 o p.1 is t>quivalent. to V''.! o J12 ·
- (U5) (t/: o p)A¢ implies.,Po(p.A¢).
- (U6) lf 1/.·o p 1 impliesp.2 and lj;o p. 2 impliesp.1 then !.'· o p 1 is equivalent to 1/J o p.2.
- ( U7) If ~' is complete then ( 1/J o p.1) A ( 1/J o p. 2) implies ~ · o (p 1 V p. 2 ).
- (U8) (~'IV V'2) o pis equivalent to (¢1 o p) V (¢2 o Jl)
U pel ate operators satisfying these postulates can be cha racteri zed as follows. An update assignment is a func tion \\'hich assigns to each interpretation I a relation ~/ m·er the set of interpretations of the language. We say that this assignment. is faithful iff for any J, if I =f J then I~~ .} and J </:1 I . Let Mod(ifJ) stand for the mod Pis of the formula c/J, and Min(S, ~), for any set S and rela tion ~ over 5 , denote the set of elements of S that are minimal under <.
Theorem 1 (IIatsuno and Mendelzon, 1991] An update OJierator o sat1.sjies conditions (U1}-(U8) iff there exists a faithful ass ignment that maps each interpretation I to a partial ordu ~~ such that:
3 The update problem m situation calculus
The bas ic idea of our encoding of update is discussed in mor<" detail in [del Val and Shoham, 1992). Although updat.e is supposed to reflect changes that have taken place in t.he world over time, the update problem (like that. of belief revision) is almost always formulated using a language incorporating no model of time or change. Our approach consists in translating the update prob ]f'm into th(~ richer language of situation calculus, so as t.o rnake explicit. this temporal information. The initial database is taken to describe a particular situation, and the update formula is taken to describe the occurr«:>nce of a special action, denoted by A;, whose intuitive read ing is 'that action which, when taken in 5 , causes p.·. The updated database is taken to describe the situation 1·esult(A;, 5). A forma.! theory of action is then used to infer facts about the result of taking the particular act.ion in the particular situation . Finally, anything inferred abou t the resulting si tuation can be ba.cktranslat.ecl to the timeless framework of belief update.
We use the standard situation calculus formalism, a three sorted predicate calculus with action , situation and fluent sorts, the binary predicate holds, with argu ments of sort fluent and situation, respectively, and the binary function result , with arguments of sorts action and situation , respectively. The constant action terms have the form Af,, with the intuitive meaning just. de scribed, where 5 is any situation term and Jl is any sat isfiable formula. of the original propositional language [ over the variables P c. Situation terms include So, in tuitively denoting the initial situation, together with all terms of the form 1·esult(A, S) for A an action term and S a situation term. The set P of fluent terms includes all variables in P c, together with the "non-primit.iw'' fluent terms of the form not( '1/.·) and o1·( 1/>), for ·u· a fluent term. Non-primitive fluent terms are required to satisfy the following axioms:
We can now translate the formulas of [ into situation calculus . We first map any formula. 1/> E [ into a fluent term 'lj; 1 as follows :
(Other propositional connect ives are assumed to be de fined in terms of --. and V.) Propositional formul as are then translated as holding at. a. particular situation. We denote the translation of 1/> at situation S by ·lj· 5 . defined simply as ~·,s = holds(lj/, 5).
We now present the theory of action that we use to encode the update problem. The "causal theory" T for the actions we have introduced is given by the schema:
where p 1 is the fluent term corresponding to a satisfiable propositional formula p., and At and S are closed terms of the appropriate sorts.
We will now define a. circumscription policy to apply t.o this theory. Intuitively, our goal is to minimize changes ("abnormalities") between successive states of the world , one situation a.t a time. Following [Lin and Shoham, 1991), in [del Val and Shoham, 1992] we used ab(p , a. s) as an abbreviation for:
As it is clear from this definition, the role of the frame predicate (first introduced in [Lifschit.z. 1990]) is to select a set of fluent.s for which changes must be minimi:.wd. or in other words, a set of fluents whose va lue ·persists by default'. In [Lin and Shoham, 1991; dPI Val and Shoham, 1992], the set of changes that should be minimized was assumed to be fixed once and for all, by means of some axiom F uniquely determining some set. :F of "frame fluents" . This assumption is unnec essary, and is lifted in this paper. The set of facts that we think likely to persist in any given situation might well depend on the state of the world at the time. To allow for this dependence, we need to add a situation argument. to the predicate f7·ame . For greater clarity, we will in fact replace frame by a new binary predicate pt 1'Sistent with first argument of sort fluent and second argument of sort situation, redefining the abnormality predicate ab(p, a, s) to be an abbreviation for pe1·sistent(p, s) 1\ (holds(p, s) = --.holds(p, result( a, s))).
\Ve assume that knowledge about which facts are to be treated as persistent in each state is encoded in our theory of action by means of some persistence axiom (P), which we leave as a. parameter in the theory of action. This axiom, might, as a very simple example, declare every primitive fluent to be persistent at any situation. \ \'e want. maximum generality, but some assumptions are 1wedt>d in order to ensure that the persistence axiom ful fills its intended role. In particular, we require that the add ition of the persistence axiom results in a conserva tive extension of the theory of action with respect to the language obtained by removing the predicate persistent ; some further requirements are needed in order to en sure that the extension of persistent at any state de pends only on the current and possibly past state of the database , not. on future states or states along alternative "time branches". The formal statement of these require ments is given in the full paper and in [del Val, 1993].
Our circumscription policy is then as follows. Let N1 and N2 be unique names for fluents and situations, re spectively, let holds' and pe1·sistent' be two new pred icates with arguments of the same sort as holds and persist ent , and let W(s) be the set of formulas :
Our final theory of action, which we denote Comp(T) , stands for the union over all closed terms A and S of the appropriate sorts of
1.t. the circumscription ofab(p,ajA,sjS) in W(S) with holds and persistent allowed to vary. Intuitively, what this policy does is to minimize changes one situation at a t.ime. For any situation S, the minimization will allow holds t.o vary at any other point except at S , since holds' is kept fixed.
Suppose now that we are given an initial propositional database 11·. Let 'lj; 80 be the translation of 1jJ into sit uat ion calculus as holding at So . We can then take the result of updating 1jJ with Jl as the set of conse quenres about. the situation result(A;o, So) entailed by Comp(T) U { 1j/io }. To capture this, let
Define now the update operator o, for any database ~· and satisfiable formula p., as follows:
Definition 1 '1/.>op. f= ¢ iffholds(¢t,,·esult(A.~ 0 ,50 )) E U(t/J, p.).
The result of sequences of updates can be similarly defined.
4 From KM semantics to theories of action
The operator o just defined depends on the persistence axiom (P), which constrains the set of persistent ftuents at each particular state of the world. Definition 1 does not therefore characterize any specific operator. but a family of them. Interesting subfamilies can be obtained by making further restrictions on the persistence axiom.
We will consider three such restrictions. The first one (SDP, for "state determines persistent ftuents'') requires that complete knowledge of the state of the world in any given situation be sufficient to uniquely determine t lw set of persistent facts in that situation. The second one (PDS , for "persistent ftuents determine state" ) ensun's that the values of the persistent ftuents (at a sit.uation S, in a model of l-1'(5)) are sufficient to completely cha r acterize a state. Finally, the ''time independence .. con dition (TI) requires the set of persistent ftuent.s to be identical for identical states at different. times.
Before giving these restrictions, we need first to lw more precise about. the notion of "state" . For am· sit u ation term S we say that Rs is a state of situatio.n S' iff there is some set of closed fluent terms F such that.
and Rs is consistent with the axioms for non primitive ftuent.s. Intuitively, a state of a situation is a compl.;>t.e specification of the values of all fluents at that. situatio11. By analogy with the notation Mod( B) for the models of 0. for any set of formulas f(S) with holds as only predica te and S as only situation term, we use States(f(S))) to denote the set of states R .of S such that R f= r ( S). Intuitively, the set of states of f(S) c.orresponds to the models of the translation of f(S) into£.
The optional restrictions on the persistence axiom are then as follows:
Definition 2 (SDP condition) A theory of action satisfies the SDP condition iff the persist t nct anom is such that for· any situation term S. any statr R of S consistent with W(S), and any fluent ter111 0. either l-1'(5). R F= pe1·sistent(O, 5) or l·F(.':I). R f= ...,pe1·sistent(O, 5).
Definition 3 (PDS condition) 3 A theory of aclton satisfies the PDS condition iff for any situation l fr 11l S, any two states R1 and R2 of S , and any set of flu ent terms P such that {pe1·sistent(O. S') I (} E P} U {-,persistent({}, 5) I (} E P \ P} is const.sifnl ll'ilh IF(S) U R1: if R1 and R2 agree on the value of every pEP then R1 = R2.
2 Recall that 'P is the set of closed fluent. t.erms of t ht· language
3 This condition generalizes the "frame completeness con dition" of [del Val and Shoham, 1992) .
Definition 4 (TI condition) A theory of action sat isfies the TI condition if the persistence axiom has the form '<Is. P(s), where P(s) contains no situation term other than s.
We can now prove the following key result:
Theorem 2 For any update operator o satisfying {Ul} (l/8) there exists an operator o' based on definition 1 and satisfying the PDS, SDP, and TI conditions such that :
The key part of the proof is the choice of persistence axiom; the construction is given in the appendix. We remark that this theorem holds for arbitrary sequences of updates as well, and thus we can capture the temporal el'olution of the database under any KM operator.
5 From theories of action to KM semantics
Though we have shown that every KM operator can be ca.ptured in our generalized framework, a natural ques tion is whether this generalization is "the right one" . Does t.his construction still satisfy the KM postulates as the more restricted one of [del Val and Shoham, 1992j die!? The answer is , under certain conditions, positive.
The circumscription of ab for each situation and action results in a set of strict partial orderings <ab As S' over . .. . situation calculus interpretations, such that I< bAs s· a ' ~ ' J iff I and J have the sa.me domains and agree on everything except holds , pe1·sistent and ab, and the extension of ub(p. a/A~ , s/S') in I is a proper subset of its exten sion in J. As in [del Val and Shoham, 1992], models of Comp(T) can also be characterized in terms of orderings over st.at.es rather than over interpretations. The intu ition here is that the results of update should only de JWnd on the immediately preceding state and the action corresponding to the update formula, modulo some set of persistent ftuents associated to the preceding state. As the next lemma shows, the circumscription selects states of rf.sult( A.~ , S') which are "closest" to a given state of .':)', in the sense of differing in set-inclusion fewer persis tent fluent.s than any other state. The ordering we use is defined as follows:
Definition 5 Let R and T be states of some situation S'. and Ms a state of some situationS, and let F be a set of flu tnt terms. Hie say that R ~~s T iff
We can use these orderings to characterize Comv(T) . For example. for a single update, we have:
Lemma 3 Suppose the SDP condition holds, and for atty .~tal e R of 50 , let FR be the unique set of fluent lfrms {B I H'(So)UR F= pe1·sistent(8,So)}. Then .)'tat r s( l ' ( ~". 11)) =
As in the representation theorem for propositional up date, this can be seen as selecting for each state of the original theory (for each model, in the propositional case) the set of closest states (models) satisfying the up date formula. Similar characterizations can be obtained without. the SDP condition (in which case several partial orders will be associated to each state, corresponding to the various specifications of pe1·sistent at that state con sistent with the persistence axiom) and for sequences of updates. Using these charact.erizat.ions. we can obtain the converse of theorem 2:
Theorem 4 Suppose the PDS, SDP, and TI condition.s are satisfied. Then the update operator<> of definition 1 .satisfies postulates (Ul}-(UB).
6 Beyond KM semantics
So far we have achieved half the goal of this paper . with theorems 2 and 4 providing a very tight correspon dence between theories of action and KM semantics. As said , though , since our intuition is that theories of action should form the basis for update, we believe that further insight can be achieved by relaxing some of the assump tions embodied by the theories of action we have con sidered. The KM postulates identify an interesting cla::;s of operators , but. there are important operators outside this class. Specifically, it can be shown that postulates (U1), (U3) , (U5) , (U6) and (US) still hold if we lift. the SDP, PDS and TI assumptions from theorem 4. but the remaining postulates are lost .
How reasonable is (U2)? Consider the following ex ample, due to Goldszmidt and Pearl [1992] . Suppost' we order a robot. t.o paint. a wall in blue or white. If the wRII is initially white, then (U2) entai ls that it. will remain white after t.he act. ion . If the robot. has no way of kn0\1" ing the original color , however, there is no reason 11"l1y the color of the wall should persist after t.he action. For another example, suppose we know t.hat Frt>d decidf'd today whether to leave his current job to accept. anot.her offer, but we do not know his specific decision; according to (U2) , the result of updating the database cu7Ten t-job with current-job V new-job should be that Fred rejects the offer' In both cases, the problem arises becaust' ( ( l2) requires the database t.o remain unchanged when a dis junctive updat.e arrives and the disjunction is already satisfied by t.he database.
Theorem 5 In the presence of TI, the operator o 811it8fies (U2) i./J the PDS condition holds 4 .
Both Golclszmidt and Pearl , and Kat.suno and '\lendf'l zon , have a possible solution to this type of problem (the latter through the operation of "erasure"). In our view. the key issue is whether certain facts should persist or not when disjunctive updates arrive; our construction al lows for an explicit axiomatiza.t.ion of default persist.encf'. and thus we suggest that it will provide the greatest fiex ibility in handling this problem.
4 Throughout this section, o is assumed t.o be based 0 11 definition l. Wit.hout TI, PDS is still sufficient for ( l l:!). hut is only necessary if restricted to st.ates of t.he dat.ahase that are ''reachable" as a result of some sequence of upda.t.es .
The TI condition can also result overrestrictive in forc ing the set of persistent fluents at any state to be inde pendent of past states. This assumption is connected to postulate (U4), according to which the update of equiv alent databases with equivalent formulas should produce equivalent results. In the timeless framework in which the update problem is formulated in the. KM proposal, the postulate appears to encode a principle of syntax in dependence . If we consider the evolution of the database, however, it. is clear that. it implies more than that. Sup pose the database is represented by 1jJ1 at some time 1, is updated with J..l to yield a database 1/J2 , and after a series of updates the database ends up at time t in a state in which it can be represented by some formula 1/Jt which is equivalent to 1/.'1 ; according to (U4), updating 1/Jt with J..l should result. in a database equivalent to 1jJ2 .
Clearly, this is not always reasonable. Myers and Smith [1988] present a number of examples in which the reasonableness of treating a fact as persistent by default depends on the way in which we came to know that fact. Similarly, it is easy to find examples in which some fact should be treated as persistent or not in virtue of what cRuses it. For example, the practice of mountain climb ing results in a high risk of injury, but the risk will dis appear as soon as the practice is given up; whereas the professional practice of tennis might result in a high risk of (elbow) injury long after the practice is quit . Thus, ll"hether "high injury risk" needs to be treated as persis tent. depends on the circumstances that cause the risk.
Since the results of our circumscriptive policy at any given situation depend only on the set of persistent flu ents at that situation, it is easy to drop this assump tion as well , while preserving all postulates except (U4). This does not mean that updates depend on the syntac ti c form of the database, only that they depend on the ;:;Pt of persistent facts , which might differ for identical ;;t a.tes at different. times.
As the next theorem states, there is a very close con nection between (U4) and the TI condition: In order to establish this connection, we need a way to compare theories of action with different persistence axioms, so as to filter out "inconsequential" violations of Tl. Let us first explicitly include the persistence axiom in our nota tion for the update function, writing <>p to indicate that the underlying theory of action contains the persistence axiom ( P). '"re say that two theories of action with per sistence axioms (P) and (P* ), respectively, are update equil'altnt iff they are equivalent with respect to update, i. f . iff for any propositional 1/J, satisfiable propositional f/J ..... J.l n, 1\"e have: ( ... ((1/J <>p J..II) <>p J..l2) .. . ) <>p J..ln = ( ... ((l!·Op· p.J}Op· J12) ... )<>p· J..ln·
Theorem 6 The update operator<> satisfies (U4) iff it is based on a theory of action which is update equivalent to a theory of action satisfying the TI condition.
Finally, ( 07) is connected to SDP. Intuitively, a (non trivial) violation of SDP corresponds to situations in ll"hich we do not regard our knowledge of the domain t.o lw sufficient. to uniquely determine which facts are likely t.o persist, or in which we want to consider the ef f<'cts of alternative assumptions about persistence. This is a perhaps rare but certainly conceivable circumst.an(·(>, which is not covered by KM. We have:
Theorem 7
- If the SDP condition holds then o satisfies (U7).
- If o .satisfies {U7), and the PDS condition hold.s, then o is based on a theory of action which is update equivalent to a theory of action satisfying SDP.
There appears to be some subtle interaction between (U2) and (U7), which is why the PDS condition appears to be needed in order to derive SDP from (tl7) in the second part. of the theorem.
7 Discussion
In this paper, we have shown that there is a. very tight correspondence between a certain class of theories of ac tion and the class of update operators satisfying Katsuno and Mendelzon's update postulates. In addition to pro viding a one-to-one correspondence between these two classes, we have shown that there are reasonable opPra tors that do not satisfy all the postulates, and thus that the KM semantics can sometimes be too restrictive. Tlw failure of each of the postulates than can be violated in our construction, furthermore, can be directly traced to an specific assumption on the specification of the sf't of facts that should "persist by default". We hope t.o haw demonstrated that the greater complication of om con struction in comparison with the KM approach is worth its price in the expanded expressivity and flexibility to be gained from it.
Reiter [1992b; 1992a) has proposed an account of database update in terms of recent proposals for soh·ing the frame problem. The relation between his approach and ours is still unclear, as it is based on a slightly differ ent theory of action. The theory that Reiter uses appears vulnerable to the ramification problem, though it. is too early to say whether this is a fundamental limitation: in contrast., we can handle ramifications in exac tly thr same way as in [del Val and Shoha.m, 1992), wit.h~ut a need to explicitly list all the conceivable circumstances in which a fluent can change its value as a result. of an action or update. Goldszmidt and Pearl [1992) have also provided an alternative, in this case probabilistirallv 1110tivated , account of database update satisfying t. h~ 1\l'v[ postulates , under some special handling for disjunct ivP updates. Time is only implicit in their proposal. and. as any other KM opera.t.or, theirs is covered bv our con struction if disjunctive updates are handled a~ required for KM compliance.
Our results show that important insights can be ob tained by encoding the problem of database update in a theory of action. We are currently investiga.t.ing whether similar insights can also be obtained for dat.abase Jf vision, an area in which we expect t.o report positive results in the near future.
@inproceedings{ijcai1993p103,
title = {Deriving Properties of Belief Update from Theories of Action (II)},
author = {del Val, Alvaro and Shoham, Yoav},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {732--736},
year = {1993},
note = {Knowledge Representation},
url = {https://ijcai.org/proceedings/1993/103},
}
TY - CPAPER TI - Deriving Properties of Belief Update from Theories of Action (II) AU - del Val, Alvaro AU - Shoham, Yoav T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 732 EP - 736 UR - https://ijcai.org/proceedings/1993/103 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: