Steps Towards Commonsense-Driven Belief Revision in the Event Calculus Nikoleta Tsampanaki, Giorgos Flouris, Theodore Patkos Institute of Computer Science, FORTH, Greece {tsaban, fgeo, patkos}@ics.forth.gr Abstract state-of-the-art tools that outperform previous SAT- or logic programming-based solvers in almost all classes of problems Recent extensions of the Event Calculus resulted in related to practical applications [Lee and Palla, 2012]. powerful formalisms, able to reason about a mul- titude of commonsense phenomena in causal do- However, to the best of our knowledge, little work has been mains, involving epistemic notions, functional flu- done on supporting belief change in the Event Calculus, in ents and probabilistic aspects, among others. Sur- cases when the new information contradicts the already in- prisingly, little attention has been paid to the prob- ferred knowledge. Specifically, the existing non-epistemic lem of automatically revising (correcting) a Knowl- extensions accommodate belief update, which concerns be- edge Base when an observation contradicts predic- liefs that change as the result of the realization that the world tions regarding the world. Despite mature work on has changed through some action. The epistemic extensions the related belief revision field, adapting such re- further focus on modeling the notions of knowledge, thus sup- sults for the case of action theories is non-trivial. porting belief expansion, where newly acquired information This paper reports on ongoing work for addressing can enrich the belief state of agents about aspects that were this problem by proposing a generic framework in previously considered unknown. Yet, the ability to accom- the context of the Event Calculus, along with ASP modate, through proper revisions, sensed information that encodings of the revision algorithm. contradicts existing beliefs is not supported. This problem is more general than belief expansion or even than diagno- sis, as it not only intends to identify the reasons that explain 1 Introduction the contradictions, but also to suggest proper modifications of Action languages are well-established logical theories for rea- the belief state of the agent under certain, potentially domain- soning about the dynamics of changing worlds, aiming at dependent, criteria [Alchourron et al., 1985]. “formally characterizing the relationship between the knowl- In this paper, we present steps towards a formal method edge, the perception and the action of autonomous agents” for accommodating belief revision on top of Event Calculus [Van Harmelen et al., 2007]. One of the most prominent ac- axiomatizations. We consider both the epistemic and non- tion languages is the Event Calculus [Kowalski and Sergot, epistemic case, relying on the possible-worlds representation 1986; Miller and Shanahan, 2002], which incorporates cer- to give formal semantics to an agent’s belief state. We for- tain useful features for representing causal and narrative in- malize notions of commonsense revisions that take into con- formation that differentiate it from other similar formalisms. sideration different knowledge states, such as factual (or ob- The Event Calculus explicitly represents temporal knowl- served), inferred and unknown beliefs. Finally, we present a edge, enabling reasoning about the effects of a narrative of methodology and an ASP encoding that can implement the events along a time line. It also relies on a non-monotonic formalism. The current framework is based on certain sim- treatment of events, in the sense that by default there are no plifying assumptions, such as deterministic domains and lack unexpected effects or event occurrences. of state constraints (state axioms), which limit its broadness. Powerful extensions of the main formalism have been Yet, this work can form the substrate for further extensions developed to accommodate, for instance, epistemic exten- concerning a richer set of commonsense features, such as de- sions [Miller et al., 2013; Ma et al., 2013; Patkos and fault beliefs, non-determinism, introspective belief changes, Plexousakis, 2009], probabilistic uncertainty [Skarlatidis et non-binary aspects etc, along with formal results showing that al., 2015; D’Asaro et al., 2017] or knowledge derivations it is generic enough to be applied to different Event Calculus with non-binary-valued fluents [Miller et al., 2013]. More- dialects. over, progress in generalizing the stable model semantics Example: Consider the classical Yale Shooting scenario, used in Answer Set Programming (ASP) has opened the where a loaded gun is fired against a living, walking turkey. way for the reformulation of Event Calculus axiomatizations An observer may believe that, after the shot, the turkey is into logic programs that can be executed with efficient ASP dead. If future observations contradict her beliefs, e.g., by solvers [Ferraris et al., 2011]. This allowed for exploiting noticing that the turkey is still walking, the observer will need to assess different potential revisions of her belief state: can possible worlds (variables w, w0 , w1 , ...) and a sort I for in- it be that she was so mistaken and the shooter did not fire the stants (variables i, i0 , i1 , ...). The idea is to represent time as gun in the first place? Or is it just that the initial, default belief a system of parallel lines, where each world is understood as about the gun being loaded was not accurate? Moreover, how an identifier for a possible time line. Finally, we assume that would the revisions be affected if the initial state of the gun is the constant Wa of sort W signifies the actual world. unknown? Although simplistic, this setting of the Yale Shooting sce- 3 Revisions in the Non-Epistemic Case nario can be generalized to account for different levels of commonsense inferences, some of which may be domain- 3.1 Revision Setting and Principles independent, e.g., revising aspects that were initially un- The representation of a dynamic domain requires the cou- known rather than aspects that have already been observed, pling of domain-independent and domain-dependent axioms while others may be domain-dependent, e.g., considering cer- with our knowledge about the world and the related narrative. tain observations as being less reliable than others. For such Overall, we define a Knowledge Base as follows: types of domains, we develop in the sequel a formal method- ology for revising the belief state of an agent, taking into con- Definition 1 A Knowledge Base (KB) capturing a dynamic sideration commonsense and epistemic notions. domain is defined as Φ = DEC ∧ Σ ∧ Γ0 ∧ ∆ ∧ Ω where It should be noted that, even though the belief change liter- • DEC is the conjunction of the Discrete Event Calculus ature has been used as a source of inspiration for addressing domain-independent axioms, the problem, the related technical results cannot be directly applied, as they are based on assumptions that are not rele- • Σ is the conjunction of the domain-dependent axioms, vant for our setting (e.g., monotonicity of the underlying rep- • Γ0 is the initial knowledge, i.e., a conjunction of ground resentation language). Thus, our approach leverages only the (¬)HoldsAt(Fi , 0) axioms at timepoint 0, related methodologies, establishing connections among our ideas and the corresponding ideas from belief change. • ∆ is the narrative of actions, i.e., a conjunction of The rest of the paper is structured as follows: in Section ground Happens(Ei , Tj ) axioms, 2 we remind the basics about the Event Calculus that will be • Ω is a conjunction of unique name axioms. needed in the next sections. Sections 3 and 4 give the theoret- ical underpinnings of our methodology for the non-epistemic Domain axioms in ∆ can be partially defined and then min- and the epistemic case respectively, describing the problem imized to address the Frame Problem and related issues. Γ0 (and the proposed solution) in formal terms. In Section 5 axioms cannot be partially defined, as we assume complete we describe the implementation of the methodology in ASP, world knowledge initially (this assumption will be lifted in while in Section 6 we discuss related work. The paper con- Section 4). We denote by Φ |= φ the fact that Φ implies φ. cludes in Section 7 with remarks about our next steps. We assume that from time to time we observe some part of the world, i.e., we obtain the truth value of certain fluents. 2 Preliminaries Our current assumption is that observations can only contain a conjunction of (¬)HoldsAt() statements. We denote by ΓT Our account of change and causality is based on the discrete an observation obtained at timepoint T . time Event Calculus axiomatized in [Mueller, 2015], while Now let’s turn our attention to the problem of revising a the modeling of possible worlds for representing epistemic KB Φ with an observation ΓT . We follow the Principle of notions is inspired by the epistemic extension of the Func- Consistency Maintenance [Dalal, 1988], which requires that tional Event Calculus (EF EC) [Miller et al., 2013]. In partic- the result of revising Φ with ΓT should be consistent. In ad- ular, we consider a sort E for events (variables e, e0 , e1 , ...), a dition, we make the standard assumption that is expressed by sort F for fluents (f, f 0 , f1 , ...) and a sort T for timepoints the Principle of Primacy of New Information [Dalal, 1988] (t, t0 , t1 , ...), which is restricted to the integers.1 The key (and formalized by the postulate of success in the AGM pos- predicates are HoldsAt() ⊆ F × T denoting the truth value tulates [Alchourron et al., 1985]), which states that the new of a fluent at a particular timepoint, Happens() ⊆ E ×T cap- observation should always be entailed after the revision. turing the occurrence of events, Initiates() ⊆ E × F × T and T erminates() ⊆ E × F × T , denoting that an event The special characteristics of the Event Calculus force us to e causes fluent f to become true or false respectively in the introduce two new principles. The first is the Principle of Per- next timepoint. The notions of cause, effect and inertia are sistence of Background Knowledge, which states that the revi- captured in the DEC domain independent set of axioms (see sion process will only affect the initial knowledge (Γ0 ) and/or [Mueller, 2015]). As we restrict our considerations to deter- the narrative (∆). Thus, the domain-independent (DEC) and ministic domains for the time being, we do not axiomatize domain-dependent (Σ) axioms, as well as the unique name fluents that are released from the law inertia. axioms (Ω), should not be affected. This avoids issues associ- In order to support epistemic reasoning, we introduce two ated to the problem of learning the domain from observations, new sorts, in the style of EF EC: a sort W for representing which is not in the scope of this paper. The second new requirement is the Principle of Disallow- 1 In the sequel, variables start with a small letter, and constants ing Proactive Change, which, informally, states that we can- with a capital letter. Wherever not explicitly stated, variables are not use an observation referring to time T in order to add assumed to be universally quantified. events in the narrative beyond that timepoint. Essentially, this limits the direct effects of an observation (and the correspond- observation itself is inconsistent or when there is no way to ing revision) to past timepoints, even though such effects may satisfy the observation without changing background knowl- also have indirect ramifications related to the truth value of edge, such as the domain axioms. Formally: fluents in the future. Definition 3 The revision operator • is a binary operator, de- Finally, we adopt the Principle of Minimal Change [Kat- fined as follows: suno and Mendelzon, 1991] (also known as the Principle of Persistence of Prior Knowledge [Dalal, 1988]), which states • Φ • ΓT = Φ if RC(Φ, ΓT ) = ∅. that the new KB should be as “close” as possible to the orig- • Φ • ΓT = {Φ0 | Φ0 ∈ RC(Φ, ΓT ) and there is no W inal KB; in other words, from all the possible change re- Φ00 ∈ RC(Φ, ΓT ) such that Φ00 ≺TΦ Φ0 } otherwise. sults (revision candidates) that satisfy the other principles, we should choose the one that retains “the most information”. 3.3 Defining a Specific Preference Relation To define the preference relation more precisely, we will 3.2 The Revision Operator leverage a cost-based model which assesses minimality based Following the above principles, we can formally define the on the amount of information lost or modified from the orig- set of revision candidates as follows: inal KB in order to accommodate the observation. In partic- ular, considering two KBs Φ, Φ0 the cost to move from Φ to Definition 2 Given a KB Φ = DEC ∧ Σ ∧ Γ0 ∧ ∆ ∧ Ω and Φ0 will be defined on the basis of the formulas that can be an observation ΓT , a KB Φ0 is a revision candidate of Φ with inferred by one of these KBs but not the other. To formalise ΓT iff: this, we first define the following sets: • Φ0 is of the form Φ0 = DEC ∧Σ∧Γ00 ∧∆0 ∧Ω (Principle Modified Knowledge M K T (Φ, Φ0 ) = {HoldsAt(F, T 0 ) | of Persistence of Background Knowledge). T 0 ≤ T and either Φ |= HoldsAt(F, T 0 ) and Φ0 |= • No formula in (∆ \ ∆0 ) ∪ (∆0 \ ∆) refers to timepoints ¬HoldsAt(F, T 0 ), or Φ |= ¬HoldsAt(F, T 0 ) and t > T (Principle of Disallowing Proactive Change). Φ0 |= HoldsAt(F, T 0 )}. This represents all HoldsAt() • Φ0 is a consistent KB (Principle of Consistency). statements whose truth value was changed during the transition from Φ to Φ0 , up to T . • Φ0 |= ΓT (Principle of Primacy of New Information). New Events N E T (Φ, Φ0 ) = {Happens(E, T 0 ) | T 0 ≤ T , The set of all revision candidates of Φ with ΓT will be denoted Φ |= ¬Happens(E, T 0 ) and Φ0 |= Happens(E, T 0 )}. by RC(Φ, ΓT ). This represents all events that we had to add in the nar- Note that Definition 2 imposes that the part DEC ∧Σ∧Ω of rative of Φ to accommodate the observation, up to T . all revision candidates is identical to the corresponding part Lost Events LE T (Φ, Φ0 ) = {Happens(E, T 0 ) | T 0 ≤ T , of the original KB (following the Principle of Persistence of Φ |= Happens(E, T 0 ) and Φ0 |= ¬Happens(E, T 0 )}. Background Knowledge), and also formalizes all other prin- This represents all events that we had to retract from the ciples (except from the Principle of Minimal Change). The narrative of Φ to accommodate the observation, up to T . latter is not considered because RC(Φ, ΓT ) is meant to rep- Note that the above definitions do not consider the conse- resent all the conceivably possible revision results, not the op- quences of changes for future timepoints, i.e., beyond a cer- timal ones. The notion of minimal change is often subjective, tain timepoint T . This will be used to ignore any future reper- context- and/or domain-dependent, so we chose to include it cussions of our changes, considering only the changes up to as a separately configurable component of our framework. the timepoint of the observation. To formalize the Principle of Minimal Change, we will The cost between two KBs Φ, Φ0 up to the timepoint T is use the standard approach of introducing a preference rela- defined as: tion ≺TΦ . The idea is that if Φ1 ≺TΦ Φ2 , Φ1 is strictly more costT (Φ, Φ0 ) = wM K · |M K T (Φ, Φ0 )| + wN E · preferred than Φ2 for the result of the revision of Φ with an |N E T (Φ, Φ0 )| + wLE · |LE T (Φ, Φ0 )|, observation at timepoint T . Note that this is different from where wM K , wN E , wLE are the corresponding weights asso- the relations among interpretations [Katsuno and Mendelzon, ciated to each change (a parameter of our model). 1991] and formulas [Gardenfors and Makinson, 1988] that Now, the ≺TΦ relation can be easily defined as follows: have been used elsewhere for the same purpose. Establish- ing the connection among our preference relation and these Φ1 ≺TΦ Φ2 iff costT (Φ, Φ1 ) < costT (Φ, Φ2 ). It is trivial works is part of our future work. For now, it suffices to as- to show that this relation is well-founded, as required by the sume that ≺TΦ is wellfounded (so that we can always find a definition. minimal element in a non-empty set). Further properties (e.g., 3.4 Discussion on the preference function totality, transitivity) may improve algorithmic efficiency in identifying the optimal solution, but this is irrelevant for now. Note that the above definition of the cost function corre- We are now ready to define the revision operator. Intu- sponds to the non-epistemic version that our current imple- itively, the idea is that we select those elements of RC(Φ, ΓT ) mentation supports. Yet, we also consider various alternative that are minimal with respect to ≺TΦ . In case multiple mini- options: mal elements exist, their disjunction is taken. It is also inter- • Partitioning fluents and/or events into different “impor- esting to note that, in the special case when RC(Φ, ΓT ) = ∅, tance categories”, each with its own weight, w1 , . . . , wn . we do not revise the KB; this can happen, e.g., when the This way, e.g., two different “new events” would cost differently, depending on the weight of the in- (3.3) volved event. For this case an aggregation function HoldsAt(Alive, 0) (3.4) would be required, to aggregate wi with the weight HoldsAt(Loaded, 0) (3.5) (wM K , wN E , wLE ) of the corresponding category of Happens(Shoot, 1) (3.6) the formula whose weight is considered. This could help That is, Σ = (3.1) ∧ (3.2) ∧ (3.3), Γ0 = (3.4) ∧ (3.5) and accommodate the case where default fluents can more ∆ = (3.6), whereas the remaining components of ΦY ale fol- easily be changed than non-default ones, or for cases low from Definition 1. It can be shown that ΦY ale |= where specific fluents cost more (in terms of epistemic ¬HoldsAt(Alive, 2). effort or practical consequences) to change. Assume now that the observer receives informa- • Another future consideration would consider a degrada- tion that contradicts her current inferences, e.g., tion of the cost over time. This can support the intuition Γ3 = HoldsAt(Alive, 3) (note that ΦY ale 6|= that it should be more expensive to change knowledge HoldsAt(Alive, 3)). A possible reaction to this obser- about past timepoints than knowledge about more re- vation would be that the observer was mistaken and the cent timepoints. Again, this could be supported with an shooter did not fire the gun. That is, ∆0 = ∅ and Γ00 = Γ0 . appropriate aggregation function, combining the weight So, a revision candidate of ΦY ale , following Definition 2, coming from the type of change (wM K , wN E , wLE ), would be Φ0Y ale = DEC ∧ Σ ∧ Γ00 ∧ ∆0 ∧ Ω. the weight coming from the fluent or event (wi ) and Another possible revision would be that the observer was the weight coming from the timepoint where the corre- mistaken and the gun was not loaded in the first place. sponding change occurred. That is, ∆00 = ∆ and Γ000 = (3.4) ∧ ¬HoldsAt(Loaded, 0). The revision candidate of ΦY ale is now Φ00Y ale = • Further, it is clear that the theory requires a qualita- DEC ∧ Σ ∧ Γ000 ∧ ∆00 ∧ Ω. tive, relative ordering of the different revision candi- Consequently, Φ0Y ale , Φ00Y ale ∈ RC(ΦY ale , Γ3 ). Note that dates. Even though this can be reduced to the compari- many other KBs are included in RC(ΦY ale , Γ3 ), but all of son of the result of numerical functions, like the above, them would introduce more changes (with regards to the sub- it is still possible to use a purely qualitative compari- set relation) than these two (see also Proposition 1), so they son method, or even hybrid methods combining qualita- are not considered due to lack of space. tive and quantitative components. For this early version To find the ≺3Φ -minimal element(s) of RC(ΦY ale , Γ3 ), of the work, we chose the more simple quantitative ap- we only need to compare Φ0 with Φ00 . The weights proach, which is also more amenable to the implemen- associated with the cost function were set to wM K = tation method chosen (see Section 5). 1, wN E = 2, wLE = 2, so the corresponding costs are: The above ideas can be neatly formalized by considering a cost3 (ΦY ale , Φ0Y ale ) = 6, cost3 (ΦY ale , Φ00Y ale ) = 4, so weight function associating a “weight” to each possible for- Φ00Y ale ≺3Φ Φ0Y ale and Φ00Y ale is the revision result. mula (HoldsAt(), Happens()) and computing the cost as the total “weight” of the formulas implied by Φ but not Φ0 4 Revisions in the Epistemic Case (or vice-versa). Despite its early stage of development, the proposed ≺TΦ The high demands that are imposed on autonomous systems relation has several intuitively desirable formal properties. in real domains have led to variations of Event Calculus theo- First, we show that “fewer” changes (with respect to the stan- ries that can support reasoning with partial world knowledge. dard set-theoretic subset relation) are better than “more”: Such epistemic extensions can accommodate both known and unknown fluents, using a special type of “sense” actions to ac- Proposition 1 Consider three KBs Φ, Φ1 , Φ2 . Set C T (Φi ) = quire new knowledge, which by definition only affect the be- {φ | Φ |= φ, Φi 6|= φ and φ refers to a timepoint t0 ≤ T }, for lief state of the agent, causing no effect to the state of the do- i = 1, 2. If C T (Φ1 ) ⊂ C T (Φ2 ), then Φ1 ≺TΦ Φ2 . main. In this section, we discuss how revision of beliefs can As a corollary, we get that not changing a KB is always be achieved when the sensed information contradicts existing cheaper than changing it, and this will happen whenever the knowledge. We rely on the approach introduced in the recent observation does not contradict our expectations: EF EC dialect that implemented an adaptation of the possible worlds model to give formal semantics to belief predicates. Proposition 2 Φ ≺TΦ Φ0 for all Φ, Φ0 , T . In EF EC, the function <>: W × I → T is introduced to Proposition 3 If Φ ∈ RC(Φ, ΓT ), then Φ • ΓT = Φ. map world/instant pairs to timepoints. Timepoint < W, I > represents instant I in possible world W , where: Proposition 4 If Φ |= ΓT , then Φ • ΓT = Φ. ∀t∃w, i.t =< w, i > (DOX1) Example (cont.) Returning to the Yale shooting example The time lines believed to be accessible at any given mo- described before, the observer’s KB ΦY ale can be described ment are captured by the relation K ⊆ W × W, which repre- by the following axiomatization, stating that the gun is loaded sents the accessibility relation between possible worlds, as in at timepoint 0 and fired at timepoint 1. modal logics. As ordinary, we formally define belief of some Initiates(Load, Loaded, t) (3.1) fluent f at some timepoint as the fact that this fluent has the HoldsAt(Loaded, t) → T erminates(Shoot, Loaded, t) same truth value in all worlds that are accessible from the ac- (3.2) tual world: HoldsAt(Loaded, t) → T erminates(Shoot, Alive, t) Bel(f, < Wa , i >) ≡ (DOX2) ∀wK(w, Wa ) → HoldsAt(f, < w, i >) axioms can be partially defined as well; fluents that are un- BelN ot(f, < Wa , i >) ≡ (DOX3) known at time instant 0 generate the set of possible worlds ∀wK(w, Wa ) → ¬HoldsAt(f, < w, i >) according to axiom (DOX7). BelW h(f, < Wa , i >) ≡ (DOX4) The case of revision in the epistemic Event Calculus is vir- Bel(f, < Wa , i >) ∨ BelN ot(f, < Wa , i >) tually identical to the case of the non-epistemic one. Thus, In contrast to EF EC though, we do not consider K to be an whatever we discussed in Section 3 can be applied here as equivalence relation.2 Instead, in order to model belief rather well. The main difference in the epistemic case is that we than knowledge, we only assume that K is serial, which is can now provide a more fine-grained preference relation, tak- equivalent to stating that the agent cannot believe contradic- ing special provisions for the case where a fluent whose value tions (also known as the Consistency Axiom): was originally unknown, became known (true or false). To ∀i.Bel(f, < Wa , i >) → ¬BelN ot(f, < Wa , i >)(DOX5) do so, an approach similar to the one used in Subsection 3.3 ∀i.BelN ot(f, < Wa , i >) → ¬Bel(f, < Wa , i >)(DOX6) could be used, namely, identifying the sets of formulas of Notice that from the above axioms we do not assume that the form Bel(. . . ), BelN ot(. . . ), BelW h(. . . ) that are im- the actual world is accessible too (K is not reflexive). As a plied/not implied by eΦ, eΦ0 respectively. result, erroneous beliefs can still be inferred, requiring a revi- In particular, considering two epistemic KBs eΦ, eΦ0 the sion mechanism whenever observations (that reflect Wa ) do cost to move from eΦ to eΦ0 will be defined on the basis of not comply with the agent’s beliefs. the formulas that can be inferred by one of these KBs but not Finally, we need to define a domain-independent axiom to the other. To formalise this, we first define the following sets: ensure the existence of possible worlds in the initial state. ∀f.¬BelW h(f, < Wa , 0 >) → (DOX7) Modified Knowledge M K T (eΦ, eΦ0 ) = ∃w1 , w2 .K(w1 , Wa ) ∧ K(w2 , Wa ) ∧ {Bel(F, < Wa , T 0 >) | T 0 ≤ T and either eΦ |= HoldsAt(f, < w1 , 0 >) ∧ ¬HoldsAt(f, < w2 , 0 >) Bel(F, < Wa , T 0 >) and eΦ0 |= BelN ot(F, < Notice that according to our assumption of never losing Wa , T 0 >), or eΦ |= BelN ot(F, < Wa , T 0 >) and knowledge (there is no non-determinism), it is sufficient to eΦ0 |= Bel(F, < Wa , T 0 >)}. This represents all Bel() preserve the number of possible worlds generated at the ini- or BelN ot() statements whose truth value was changed tial timepoint while reasoning, since there is no way of gener- during the transition from eΦ to eΦ0 , up to T . ating more worlds. We do not need to eliminate worlds either, New Knowledge N K T (eΦ, eΦ0 ) = in order to allow for reasoning about the past. {Bel(F, < Wa , T 0 >) | T 0 ≤ T and either eΦ |= Based on the aforementioned formalization of belief, we ¬BelW h(F, < Wa , T 0 >) and eΦ0 |= Bel(F, < extend the definition of a KB to accommodate lack of knowl- Wa , T 0 >), or eΦ |= ¬BelW h(F, < Wa , T 0 >) and edge at the initial and at future timepoints: eΦ0 |= BelN ot(F, < Wa , T 0 >)}. This represents Definition 4 An epistemic KB is defined as eΦ = DEC ∧ all ¬BelW h() statements whose unknown value was DOX ∧ Σ ∧ eΓ0 ∧ ∆ ∧ Ω, where changed to known during the transition from eΦ to eΦ0 , up to T . • DEC is the conjunction of the Discrete Event Calculus domain-independent axioms, Lost Knowledge LK T (eΦ, eΦ0 ) = {¬BelW h(F, < Wa , T 0 >) | T 0 ≤ T and either • DOX is the conjunction of the epistemic axioms to sup- eΦ |= Bel(F, < Wa , T 0 >) and eΦ0 |= ¬BelW h(F, < port beliefs, Wa , T 0 >), or eΦ |= BelN ot(F, < Wa , T 0 >) and • Σ is the conjunction of the domain-dependent axioms, eΦ0 |= ¬BelW h(F, < Wa , T 0 >)}. This represents all • eΓ0 is the initial beliefs, i.e., a conjunction of ground Bel() or BelN ot() statements whose truth value was Bel(Fi , < Wa , 0 >), BelN ot(Fj , < Wa , 0 >) axioms changed to unknown during the transition from eΦ to at timepoint 0, eΦ0 , up to T . • ∆ is the narrative of actions, i.e., a conjunction of New Events N E T (Φ, Φ0 ) = {Happens(E, < Wa , T 0 > ground Happens(Ei , < w, Ij >) axioms, ) | T 0 ≤ T , Φ |= ¬Happens(E, < Wa , T 0 >) and Φ0 |= Happens(E, < Wa , T 0 >)}. This represents all • Ω is a conjunction of unique name axioms. events that we had to add in the narrative of Φ to accom- The definition for eΦ is more general than the one given modate the observation, up to T . for Φ. Specifically, if we assume complete world knowledge at timepoint 0, a single possible world is generated, making Lost Events LE T (Φ, Φ0 ) = {Happens(E, < Wa , T 0 > eΦ equivalent to Φ. ) | T 0 ≤ T , Φ |= Happens(E, < Wa , T 0 >) and As before, ∆ axioms can be partially defined and then min- Φ0 |= ¬Happens(E, < Wa , T 0 >)}. This represents imized to address the Frame Problem and related issues. eΓ0 all events that we had to retract from the narrative of Φ to accommodate the observation, up to T . 2 Note also that the current setting only permits belief statements that refer to the state of world fluent at the same time point. In other The cost between two KBs eΦ, eΦ0 up to the timepoint T words, we do not represent the beliefs at some timepoint about the is defined as: state of fluents at another timepoint. Such statements are supported costT (eΦ, eΦ0 ) = wM K · |M K T (eΦ, eΦ0 )| + wN K · in EF EC and will be considered for future extensions of our axiom- |N K T (eΦ, eΦ0 )| + wLK · |LK T (eΦ, eΦ0 )| + wN E · atization. |N E T (eΦ, eΦ0 )| + wLE · |LE T (eΦ, eΦ0 )|, where wM K , wN K , wLK , wN E , wLE are the correspond- revisions generator, via a logic program. Roughly, this pro- ing weights associated to each change (a parameter of our gram generates combinations of fluents in the initial state, as model). well as combinations of event occurrences at each timepoint, Now, the ≺TΦ relation can be easily defined as follows: for every possible world, aiming at keeping only the combi- eΦ1 ≺TΦ eΦ2 iff costT (eΦ, eΦ1 ) < costT (eΦ, eΦ2 ). It is nations that lead to a consistent KB and are consistent with trivial to show that this relation is well-founded, as required the new observation (revision candidates). The cost associ- by the definition. ated with each revision candidate is calculated, based on the cost function described in Section 4; this is implemented with 5 Implementation ASP rules that penalize each truth value or event that is dif- ferent from the output of the first reasoning step. Finally, The proposed framework was implemented for both the an optimization statement filters out all non-optimal revision non-epistemic and the epistemic case, using the architecture candidates (answer sets). At the end, the program returns the shown in Figure 1.3 The figure shows the loop of steps per- disjunction of the optimal candidates. formed whenever a new observation arrives, along with the Returning to the Yale shooting example described before, corresponding input/output modules (rulesets). There are two an output of the program in the epistemic case is discussed main reasoning steps, interconnected via two Java programs: next. Namely, the initial beliefs are that the turkey is alive at the first reasoning step generates one answer set in the non- timepoint 0 and a shot happens at timepoint 1, but we do not epistemic case and multiple answer sets in the epistemic case, know whether the gun is loaded or not at timepoint 0. Thus, each denoting a possible world (see Section 4), and the sec- we do not know whether the turkey is alive or not at timepoint ond step generates cost-optimal revisions. Reasoning is per- 3. Assume now that we receive a new contradicting informa- formed by implementing the Event Calculus axiomatizations tion that the turkey is alive at timepoint 3. We present the as ASP rules and by utilizing the Clingo reasoner [Gebser optimal revision that accommodates this observation into our et al., 2011]. Similarly, the domain-dependent axioms, the knowledge base in Figure 2, based on the following weights: epistemic axioms, the main program, the meta-program, the wM K = 1, wN K = 1, wLK = 2, wN E = 2, wLE = 2. new observations and the current beliefs are all implemented More specifically, the optimal revision is to assume that we in ASP. The current beliefs module contains the running in- were mistaken and the gun was not loaded in the first place. formation about the world state and the narrative of actions. Thus, we have the least possible cumulative cost, as we gain A Java parser intervenes between the two reasoning steps to knowledge on the state of the turkey at timepoints 2 and 3, as transform the information contained in the generated answer well as, on the state of the gun at timepoints 0 and 1. Had sets, i.e., the possible worlds, into the agent’s belief predi- we accepted the revision that the shooter did not fire the gun, cates. These are introduced in ASP form in the revision meta- we would lose knowledge and event happenings at various program, which provides the revision results, based on the timepoints, and as a result, the cost would be greater in total. DOX axioms described in Section 4. Finally, a Java parser parses all other modules needed for automating the process and for connecting the reasoning to the outside world. The most important module is the revision meta-program, which implements the revision algorithm. In case of inconsis- tency, it takes as input the new observation and the result from the Java parser, which expresses the running belief state. The meta-program computes the revision using the cost-optimal 3 http://www.ics.forth.gr/isl/ CS17BelRevPaper/ Figure 2: The output of the Java agent, divided in two sec- tions. The upper section in blue represents the original belief state, and the lower section in green represents the revised Figure 1: The reasoning loop for revising the KB of an agent. belief state of the agent. 6 Related Work tures: [Thielscher, 2000] adapted the model in the context of the Fluent Calculus, [Scherl, 2003] covered concurrent ac- Belief change (also known as belief revision) is a mature field tions, while [Kelly and Pearce, 2008] introduced epistemic of study dealing with the adaptation of a KB in the face of modalities for groups of agents. Non-possible-worlds based new information [Alchourron et al., 1985]. Traditionally, epistemic action frameworks include [Morgenstern, 1987; two types of change have been considered: revision and up- Demolombe and Pozos-Parra, 2000; Son and Baral, 2001; date [Katsuno and Mendelzon, 1991]. Revision deals with Petrick and Levesque, 2002; Vassos and Levesque, 2007; cases where the new information is some observation or re- Liu and Lakemeyer, 2009]. In all these frameworks, knowl- finement of our knowledge about the world, whereas update edge is assumed to be always correct and observations that deals with cases where the adaptation is dictated by some ac- contradict inferred knowledge will lead to inconsistency. tion or event that changed the world itself. The case of belief The ability to deal with belief changes has lately started to update is inherently captured by the semantics and reasoning gain interest within other action languages, as in [Shapiro et of Event Calculus, where one can explicitly declare events, al., 2011] and [Schwering et al., 2015] in the Situation Cal- as well as the effects and preconditions of such events. How- culus, but without taking time into account. [Van Zee et al., ever, studies regarding the revision of action theories when 2015] developed a new action formalism for revision of tem- our observations of the actual world are inconsistent with the poral belief bases; even though related to our work, [Van Zee theory’s predictions regarding the world’s state are limited. et al., 2015] do not directly address the problem of revising Most works in the classical belief change literature are theories in Event Calculus, but instead define a new logic of dealing with the so-called classical logics [Flouris et al., action that is closer to propositional logic, thereby allowing 2006], which have certain nice properties, both in terms technical results from the belief change literature to be di- of semantics (monotonicity, compactness, inclusion of the rectly applicable in their framework. classical tautological implication, etc) and in terms of syn- tax (closed with respect to the usual operators ∧, ∨, ¬, etc), 7 Conclusion Extensions of these theories to apply for ontological lan- guages [Flouris et al., 2006; Qi and Du, 2009], or compact This paper reported on early work towards a formal frame- and monotonic logics in general [Ribeiro et al., 2013] have work for changing Event Calculus theories in the face of new been considered as well. However, to the best of our knowl- (and potentially unexpected) observations. Our framework is edge, no such study exists for non-monotonic formalisms, necessary in the cases where an intelligent agent observes, partly because many non-monotonic formalisms (most no- or otherwise becomes aware of, information that contradicts tably, defeasible logic, default logic and paraconsistent log- what was expected by the underlying theory. Even though ics) have inherent ways to reason under inconsistency without the rich technical results from the belief change literature are trivializing inference. Thus, technical results from the related not generally applicable to our setting, we leveraged on some literature are not directly applicable in our setting. key ideas and adapted them for our purposes. Our approach was based on a set of principles and a preference relation that Studies that account for epistemic considerations of the models the well-known Principle of Minimal Change. Event Calculus are more closely related to ours. More specif- We are currently working on extending the framework with ically, the EF EC variant introduced in [Miller et al., 2013; more features and providing a more efficient implementation, Ma et al., 2013] is the first to rely on the possible worlds along with a more generic preference relation. We are work- semantics to reason about knowledge. EF EC supports a mul- ing to accommodate default knowledge, irrelevant fluents, titude of features, such as reasoning about the future and past, degradation of the cost over time and other domain-specific or dealing with non-determinism and concurrency. Our work features. Our implementation will be extended to allow easy utilizes the same underlying structures to formalize the treat- parameterization and customization of the preference relation ment of epistemic notions, extending them with the ability to to be used, even at run-time, in order to experiment with the revise contradicting knowledge, although it is currently sig- behaviour of different preferences and preference families. nificantly limited in the set of supporting features. In [Patkos Also, we are planning on establishing stronger connections and Plexousakis, 2009], a different epistemic extension of with existing results from belief change (e.g., satisfaction of discrete-time Event Calculus theories is presented, using a certain postulates, or connections between our preference re- deduction-oriented model of knowledge. lation and various selection functions or orderings that have Beyond the Event Calculus, possible-worlds based epis- been used in other contexts), thereby more thoroughly under- temic extensions for reasoning about actions and knowl- standing the properties of the proposed framework. Further, edge have been developed in the context of other calculi. even though our theoretical framework is generic enough to The first approach that inspired this direction of research is support more complex flavours of action theories and DEC, owed to [Moore, 1985], who presented a Kripke-like for- our implementation will need to be significantly extended to mulation of epistemic notions of modal logic in action lan- support different Event Calculus dialects and a richer set of guages by reifying possible worlds as situations. [Scherl commonsense features such as non-determinism, state con- and Levesque, 2003] adapted this framework in the Situa- straints, and introspective belief changes. tion Calculus, using possible situations to specify how the mental state of an agent should change with ordinary and sense actions, providing also a solution to the frame prob- lem for knowledge. Other studies introduced further fea- References [Miller et al., 2013] R. Miller, L. Morgenstern, and [Alchourron et al., 1985] C. Alchourron, P. Gärdenfors, and T. Patkos. Reasoning about knowledge and action in an epistemic event calculus. In Commonsense-13, 2013. D. Makinson. On the logic of theory change: Partial meet contraction and revision functions. Journal of Symbolic [Moore, 1985] R. C. Moore. A formal theory of knowl- Logic, 50:510–530, 1985. edge and action. In Formal Theories of the Commonsense World, pages 319–358. J. Hobbs, R. Moore (Eds.), 1985. [Dalal, 1988] M. Dalal. Investigations into a theory of [Morgenstern, 1987] L. Morgenstern. Knowledge precondi- knowledge base revision: Preliminary report. In AAAI-88, pages 475–479, 1988. tions for actions and plans. In IJCAI-87, 1987. [Mueller, 2015] E.T. Mueller. Commonsense Reasoning: An [D’Asaro et al., 2017] F. A. D’Asaro, A. Bikakis, L. Dick- Event Calculus Based Approach. Morgan Kaufmann Pub- ens, and R. Miller. Foundations for a probabilistic event lishers Inc., San Francisco, CA, USA, 2nd edition, 2015. calculus. In LPNMR-17, pages 57–63, 2017. [Patkos and Plexousakis, 2009] T. Patkos and D. Plex- [Demolombe and Pozos-Parra, 2000] R. Demolombe and ousakis. Reasoning with knowledge, action and time in M. P. Pozos-Parra. A simple and tractable extension of dynamic and uncertain domains. In IJCAI-09, 2009. situation calculus to epistemic logic. In ISMIS-00, pages [Petrick and Levesque, 2002] R. Petrick and H. Levesque. 515–524, 2000. Knowledge equivalence in combined action theories. In [Ferraris et al., 2011] P. Ferraris, J. Lee, and V. Lifschitz. KR-02, pages 303–314, 2002. Stable models and circumscription. Artificial Intelligence, [Qi and Du, 2009] G. Qi and J. Du. Model-based revision 175(1):236–263, 2011. operators for terminologies in Description Logics. In [Flouris et al., 2006] G. Flouris, D. Plexousakis, and G. An- IJCAI-09, pages 891–897, 2009. toniou. On generalizing the AGM postulates. In STAIRS- [Ribeiro et al., 2013] M.M. Ribeiro, R. Wassermann, 06, pages 132–143, 2006. G. Flouris, and G. Antoniou. Minimal change: Relevance [Gardenfors and Makinson, 1988] P. Gardenfors and and recovery revisited. 201:59–80, 2013. D. Makinson. Revisions of knowledge systems using [Scherl and Levesque, 2003] R. Scherl and H. Levesque. epistemic entrenchment. In TARK-88, pages 83–95, 1988. Knowledge, action, and the frame problem. Artificial In- telligence, 144(1-2):1–39, 2003. [Gebser et al., 2011] Martin Gebser, Benjamin Kaufmann, Roland Kaminski, Max Ostrowski, Torsten Schaub, and [Scherl, 2003] R.B. Scherl. Reasoning about the interaction Marius Schneider. Potassco: The Potsdam answer set solv- of knowlege, time and concurrent actions in the situation ing collection. AI Communications, 24(2):107–124, 2011. calculus. In IJCAI-03, pages 1091–1096, 2003. [Schwering et al., 2015] C. Schwering, G. Lakemeyer, and [Katsuno and Mendelzon, 1991] H. Katsuno and A.O. M. Pagnucco. Belief revision and progression of knowl- Mendelzon. On the difference between updating a edge bases in the epistemic situation calculus. In IJCAI- knowledge base and revising it. In KR-91, 1991. 15, 2015. [Kelly and Pearce, 2008] R.F. Kelly and A.R. Pearce. Com- [Shapiro et al., 2011] S. Shapiro, M. Pagnucco, plex epistemic modalities in the situation calculus. In KR- Y. Lespérance, and H.J. Levesque. Iterated belief 08, pages 611–620, 2008. change in the situation calculus. Artificial Intelligence, [Kowalski and Sergot, 1986] R. Kowalski and M. Sergot. A 175(1):165–192, 2011. logic-based calculus of events. New Generation Comput- [Skarlatidis et al., 2015] A. Skarlatidis, A. Artikis, J. Filip- ing, 4(1):67–95, 1986. pou, and G. Paliouras. A probabilistic logic programming [Lee and Palla, 2012] J. Lee and R. Palla. Reformulating the event calculus. TPLP, 15:213–245, 2015. situation calculus and the event calculus in the general the- [Son and Baral, 2001] T. C. Son and C. Baral. Formalizing ory of stable models and in answer set programming. JAIR, sensing actions – a transition function based approach. Ar- 43(1):571–620, 2012. tificial Intelligence, 125(1-2):19–91, 2001. [Liu and Lakemeyer, 2009] Y. Liu and G. Lakemeyer. On [Thielscher, 2000] M. Thielscher. Representing the knowl- first-order definability and computability of progression edge of a robot. In KR-00, pages 109–120, 2000. for local-effect actions and beyond. In IJCAI-09, 2009. [Van Harmelen et al., 2007] F. Van Harmelen, V. Lifschitz, [Ma et al., 2013] J. Ma, R. Miller, L. Morgenstern, and and B. Porter. Handbook of Knowledge Representation. Elsevier Science, San Diego, USA, 2007. T. Patkos. An Epistemic Event Calculus for ASP-based reasoning about knowledge of the past, present and future. [Van Zee et al., 2015] M. Van Zee, D. Doder, M. Dastani, In LPAR-13, pages 75–87, 2013. and L. Van Der Torre. AGM revision of beliefs about ac- tion and time. In IJCAI-15, pages 3250–3256, 2015. [Miller and Shanahan, 2002] R. Miller and M. Shanahan. [Vassos and Levesque, 2007] S. Vassos and H. Levesque. Some alternative formulations of the event calculus. Com- putational Logic: Logic Programming and Beyond, Essays Progression of situation calculus action theories with in- in Honour of R. Kowalski Part 2, 2408(1):452–490, 2002. complete information. In IJCAI-07, 2007.