Recent extensions of the Event Calculus resulted in powerful formalisms, able to reason about a multitude of commonsense phenomena in causal domains, involving epistemic notions, functional fluents and probabilistic aspects, among others. Surprisingly, little attention has been paid to the problem of automatically revising (correcting) a Knowledge Base when an observation contradicts predictions regarding the world. Despite mature work on the related belief revision field, adapting such results for the case of action theories is non-trivial. This paper reports on ongoing work for addressing this problem by proposing a generic framework in the context of the Event Calculus, along with ASP encodings of the revision algorithm.
Action languages are well-established logical theories for reasoning about the dynamics of changing worlds, aiming at “formally characterizing the relationship between the knowledge, the perception and the action of autonomous agents” [Van Harmelen et al., 2007]. One of the most prominent action languages is the Event Calculus [Kowalski and Sergot, 1986; Miller and Shanahan, 2002], which incorporates certain useful features for representing causal and narrative information that differentiate it from other similar formalisms. The Event Calculus explicitly represents temporal knowledge, enabling reasoning about the effects of a narrative of events along a time line. It also relies on a non-monotonic treatment of events, in the sense that by default there are no unexpected effects or event occurrences.
Powerful extensions of the main formalism have been developed to accommodate, for instance, epistemic extensions [Miller et al., 2013; Ma et al., 2013; Patkos and Plexousakis, 2009], probabilistic uncertainty [Skarlatidis et al., 2015; D’Asaro et al., 2017] or knowledge derivations with non-binary-valued fluents [Miller et al., 2013]. Moreover, progress in generalizing the stable model semantics used in Answer Set Programming (ASP) has opened the way for the reformulation of Event Calculus axiomatizations into logic programs that can be executed with efficient ASP solvers [Ferraris et al., 2011]. This allowed for exploiting state-of-the-art tools that outperform previous SAT- or logic programming-based solvers in almost all classes of problems related to practical applications [Lee and Palla, 2012].
However, to the best of our knowledge, little work has been done on supporting belief change in the Event Calculus, in cases when the new information contradicts the already inferred knowledge. Specifically, the existing non-epistemic extensions accommodate belief update, which concerns beliefs that change as the result of the realization that the world has changed through some action. The epistemic extensions further focus on modeling the notions of knowledge, thus supporting belief expansion, where newly acquired information can enrich the belief state of agents about aspects that were previously considered unknown. Yet, the ability to accommodate, through proper revisions, sensed information that contradicts existing beliefs is not supported. This problem is more general than belief expansion or even than diagnosis, as it not only intends to identify the reasons that explain the contradictions, but also to suggest proper modifications of the belief state of the agent under certain, potentially domaindependent, criteria [Alchourron et al., 1985].
In this paper, we present steps towards a formal method for accommodating belief revision on top of Event Calculus axiomatizations. We consider both the epistemic and nonepistemic case, relying on the possible-worlds representation to give formal semantics to an agent’s belief state. We formalize notions of commonsense revisions that take into consideration different knowledge states, such as factual (or observed), inferred and unknown beliefs. Finally, we present a methodology and an ASP encoding that can implement the formalism. The current framework is based on certain simplifying assumptions, such as deterministic domains and lack of state constraints (state axioms), which limit its broadness. Yet, this work can form the substrate for further extensions concerning a richer set of commonsense features, such as default beliefs, non-determinism, introspective belief changes, non-binary aspects etc, along with formal results showing that it is generic enough to be applied to different Event Calculus dialects.
Example: Consider the classical Yale Shooting scenario, where a loaded gun is fired against a living, walking turkey. An observer may believe that, after the shot, the turkey is dead. If future observations contradict her beliefs, e.g., by noticing that the turkey is still walking, the observer will need to assess different potential revisions of her belief state: can it be that she was so mistaken and the shooter did not fire the gun in the first place? Or is it just that the initial, default belief about the gun being loaded was not accurate? Moreover, how would the revisions be affected if the initial state of the gun is unknown?
Although simplistic, this setting of the Yale Shooting scenario can be generalized to account for different levels of commonsense inferences, some of which may be domainindependent, e.g., revising aspects that were initially unknown rather than aspects that have already been observed, while others may be domain-dependent, e.g., considering certain observations as being less reliable than others. For such types of domains, we develop in the sequel a formal methodology for revising the belief state of an agent, taking into consideration commonsense and epistemic notions.
It should be noted that, even though the belief change literature has been used as a source of inspiration for addressing the problem, the related technical results cannot be directly applied, as they are based on assumptions that are not relevant for our setting (e.g., monotonicity of the underlying representation language). Thus, our approach leverages only the related methodologies, establishing connections among our ideas and the corresponding ideas from belief change.
The rest of the paper is structured as follows: in Section 2 we remind the basics about the Event Calculus that will be needed in the next sections. Sections 3 and 4 give the theoretical underpinnings of our methodology for the non-epistemic and the epistemic case respectively, describing the problem (and the proposed solution) in formal terms. In Section 5 we describe the implementation of the methodology in ASP, while in Section 6 we discuss related work. The paper concludes in Section 7 with remarks about our next steps. 2
Our account of change and causality is based on the discrete
time Event Calculus axiomatized in [Mueller, 2015], while
the modeling of possible worlds for representing epistemic
notions is inspired by the epistemic extension of the
Functional Event Calculus (E F E C) [Miller et al., 2013]. In
particular, we consider a sort E for events (variables e; e0; e1; :::), a
sort F for fluents (f; f 0; f1; :::) and a sort T for timepoints
(t; t0; t1; :::), which is restricted to the integers.1 The key
predicates are HoldsAt() F T denoting the truth value
of a fluent at a particular timepoint, Happens() E T
capturing the occurrence of events, Initiates() E F T
and T erminates() E F T , denoting that an event
e causes fluent f to become true or false respectively in the
next timepoint. The notions of cause, effect and inertia are
captured in the DE C domain independent set of axioms
In order to support epistemic reasoning, we introduce two new sorts, in the style of E F E C: a sort W for representing 1In the sequel, variables start with a small letter, and constants with a capital letter. Wherever not explicitly stated, variables are assumed to be universally quantified. possible worlds (variables w; w0; w1; :::) and a sort I for instants (variables i; i0; i1; :::). The idea is to represent time as a system of parallel lines, where each world is understood as an identifier for a possible time line. Finally, we assume that the constant Wa of sort W signifies the actual world. 3 3.1
The representation of a dynamic domain requires the coupling of domain-independent and domain-dependent axioms with our knowledge about the world and the related narrative. Overall, we define a Knowledge Base as follows: = DE C ^
domain is defined as 0 where ^ ^ ^ DE C is the conjunction of the Discrete Event Calculus domain-independent axioms, is the conjunction of the domain-dependent axioms, 0 is the initial knowledge, i.e., a conjunction of ground (:)HoldsAt(Fi; 0) axioms at timepoint 0,
is the narrative of actions, i.e., a conjunction of ground Happens(Ei; Tj ) axioms,
is a conjunction of unique name axioms.
Domain axioms in can be partially defined and then minimized to address the Frame Problem and related issues. 0 axioms cannot be partially defined, as we assume complete world knowledge initially (this assumption will be lifted in Section 4). We denote by j= the fact that implies .
We assume that from time to time we observe some part of the world, i.e., we obtain the truth value of certain fluents. Our current assumption is that observations can only contain a conjunction of (:)HoldsAt() statements. We denote by T an observation obtained at timepoint T .
Now let’s turn our attention to the problem of revising a
KB with an observation T . We follow the Principle of
Consistency Maintenance [Dalal, 1988], which requires that
the result of revising with T should be consistent. In
addition, we make the standard assumption that is expressed by
the Principle of Primacy of New Information [Dalal, 1988]
The special characteristics of the Event Calculus force us to introduce two new principles. The first is the Principle of Persistence of Background Knowledge, which states that the revision process will only affect the initial knowledge ( 0) and/or the narrative ( ). Thus, the domain-independent (DE C) and domain-dependent ( ) axioms, as well as the unique name axioms ( ), should not be affected. This avoids issues associated to the problem of learning the domain from observations, which is not in the scope of this paper.
The second new requirement is the Principle of Disallowing Proactive Change, which, informally, states that we cannot use an observation referring to time T in order to add events in the narrative beyond that timepoint. Essentially, this limits the direct effects of an observation (and the corresponding revision) to past timepoints, even though such effects may also have indirect ramifications related to the truth value of fluents in the future.
suno and Mendelzon, 1991] (also known as the Principle of
that the new KB should be as “close” as possible to the original KB; in other words, from all the possible change results (revision candidates) that satisfy the other principles, we should choose the one that retains “the most information”. 3.2
Following the above principles, we can formally define the set of revision candidates as follows:
an observation T , a KB T iff: = DE C ^ ^ 0 ^ ^ 0 is a revision candidate of and with 0 j=
by RC( ; T ).
0 is of the form 0 = DE C ^ ^ 00 ^ 0 ^ of Persistence of Background Knowledge). (Principle No formula in ( n 0) [ ( 0 n ) refers to timepoints t > T (Principle of Disallowing Proactive Change). 0 is a consistent KB (Principle of Consistency).
with
Note that Definition 2 imposes that the part DE C ^ ^ of all revision candidates is identical to the corresponding part of the original KB (following the Principle of Persistence of Background Knowledge), and also formalizes all other principles (except from the Principle of Minimal Change). The latter is not considered because RC( ; T ) is meant to represent all the conceivably possible revision results, not the optimal ones. The notion of minimal change is often subjective, context- and/or domain-dependent, so we chose to include it as a separately configurable component of our framework.
To formalize the Principle of Minimal Change, we will use the standard approach of introducing a preference relation T . The idea is that if 1 T 2, 1 is strictly more preferred than 2 for the result of the revision of with an observation at timepoint T . Note that this is different from the relations among interpretations [Katsuno and Mendelzon, 1991] and formulas [Gardenfors and Makinson, 1988] that have been used elsewhere for the same purpose. Establishing the connection among our preference relation and these works is part of our future work. For now, it suffices to assume that T is wellfounded (so that we can always find a minimal element in a non-empty set). Further properties (e.g., totality, transitivity) may improve algorithmic efficiency in identifying the optimal solution, but this is irrelevant for now.
We are now ready to define the revision operator. Intuitively, the idea is that we select those elements of RC( ; T ) that are minimal with respect to T . In case multiple minimal elements exist, their disjunction is taken. It is also interesting to note that, in the special case when RC( ; T ) = ;, we do not revise the KB; this can happen, e.g., when the observation itself is inconsistent or when there is no way to satisfy the observation without changing background knowledge, such as the domain axioms. Formally:
fined as follows:
if RC( ; T ) = ;. To define the preference relation more precisely, we will leverage a cost-based model which assesses minimality based on the amount of information lost or modified from the original KB in order to accommodate the observation. In particular, considering two KBs ; 0 the cost to move from to 0 will be defined on the basis of the formulas that can be inferred by one of these KBs but not the other. To formalise this, we first define the following sets: Modified Knowledge M KT ( ; 0) = fH oldsAt(F; T 0) j T 0 T and either j= H oldsAt(F; T 0) and 0 j= :H oldsAt(F; T 0), or j= :H oldsAt(F; T 0) and 0 j= H oldsAt(F; T 0)g. This represents all H oldsAt() statements whose truth value was changed during the transition from to 0, up to T .
New Events N ET ( ; 0) = fH appens(E; T 0) j T 0 T , j= :H appens(E; T 0) and 0 j= H appens(E; T 0)g. This represents all events that we had to add in the narrative of to accommodate the observation, up to T . Lost Events LET ( ; 0) = fH appens(E; T 0) j T 0 T , j= H appens(E; T 0) and 0 j= :H appens(E; T 0)g. This represents all events that we had to retract from the narrative of to accommodate the observation, up to T .
Note that the above definitions do not consider the consequences of changes for future timepoints, i.e., beyond a certain timepoint T . This will be used to ignore any future repercussions of our changes, considering only the changes up to the timepoint of the observation.
The cost between two KBs ; 0 up to the timepoint T is defined as: costT ( ; 0) = wM K jM KT ( ; 0)j + wN E jN ET ( ; 0)j + wLE jLET ( ; 0)j, where wM K ; wN E ; wLE are the corresponding weights associated to each change (a parameter of our model).
Now, the T relation can be easily defined as follows: 1 T 2 iff costT ( ; 1) < costT ( ; 2). It is trivial to show that this relation is well-founded, as required by the definition. 3.4
Note that the above definition of the cost function corresponds to the non-epistemic version that our current implementation supports. Yet, we also consider various alternative options:
Partitioning fluents and/or events into different “importance categories”, each with its own weight, w1; : : : ; wn. This way, e.g., two different “new events” would cost differently, depending on the weight of the involved event. For this case an aggregation function would be required, to aggregate wi with the weight (wMK ; wNE ; wLE ) of the corresponding category of the formula whose weight is considered. This could help accommodate the case where default fluents can more easily be changed than non-default ones, or for cases where specific fluents cost more (in terms of epistemic effort or practical consequences) to change.
Another future consideration would consider a degradation of the cost over time. This can support the intuition that it should be more expensive to change knowledge about past timepoints than knowledge about more recent timepoints. Again, this could be supported with an appropriate aggregation function, combining the weight coming from the type of change (wMK ; wNE ; wLE ), the weight coming from the fluent or event (wi) and the weight coming from the timepoint where the corresponding change occurred.
Further, it is clear that the theory requires a qualitative, relative ordering of the different revision candidates. Even though this can be reduced to the comparison of the result of numerical functions, like the above, it is still possible to use a purely qualitative comparison method, or even hybrid methods combining qualitative and quantitative components. For this early version of the work, we chose the more simple quantitative approach, which is also more amenable to the implementation method chosen (see Section 5).
The above ideas can be neatly formalized by considering a weight function associating a “weight” to each possible formula (HoldsAt(); Happens()) and computing the cost as the total “weight” of the formulas implied by but not 0 (or vice-versa).
Despite its early stage of development, the proposed T relation has several intuitively desirable formal properties. First, we show that “fewer” changes (with respect to the standard set-theoretic subset relation) are better than “more”: Proposition 1 Consider three KBs ; 1; 2. Set CT ( i) = if =j1; 2j=.If C;T i( 6j=1) anCdT ( re2fe),rsthteona ti1mepToin2t.t0 T g, for
As a corollary, we get that not changing a KB is always cheaper than changing it, and this will happen whenever the observation does not contradict our expectations: 0 for all ; 0; T . 2 RC( ; T ), then
.
.
T j=
Example (cont.) Returning to the Yale shooting example described before, the observer’s KB Y ale can be described by the following axiomatization, stating that the gun is loaded at timepoint 0 and fired at timepoint 1.
Initiates(Load; Loaded; t) (3.1) HoldsAt(Loaded; t) ! T erminates(Shoot; Loaded; t) (3.2) HoldsAt(Loaded; t) ! T erminates(Shoot; Alive; t) (3.3) HoldsAt(Alive; 0) (3.4) HoldsAt(Loaded; 0) (3.5) Happens(Shoot; 1) (3.6) That is, = (3.1) ^ (3.2) ^ (3.3), 0 = (3.4) ^ (3.5) and = (3.6), whereas the remaining components of Y ale follow from Definition 1. It can be shown that Y ale j= :HoldsAt(Alive; 2).
Assume now that the observer receives information that contradicts her current inferences, e.g., 3 = HoldsAt(Alive; 3) (note that Y ale 6j= HoldsAt(Alive; 3)). A possible reaction to this observation would be that the observer was mistaken and the shooter did not fire the gun. That is, 0 = ; and 00 = 0. So, a revision candidate of Y ale, following Definition 2, would be 0Y ale = DE C ^ ^ 00 ^ 0 ^ .
Another possible revision would be that the observer was mistaken and the gun was not loaded in the first place. That is, 00 = and 000 = (3:4) ^ :HoldsAt(Loaded; 0). The revision candidate of Y ale is now 0Y0 ale = DE C ^ ^ 000 ^ 00 ^ .
Consequently, 0Y ale; 0Y0 ale 2 RC( Y ale; 3). Note that many other KBs are included in RC( Y ale; 3), but all of them would introduce more changes (with regards to the subset relation) than these two (see also Proposition 1), so they are not considered due to lack of space.
To find the 3 -minimal element(s) of RC( Y ale; 3), we only need to compare 0 with 00. The weights associated with the cost function were set to wMK = 1; wNE = 2; wLE = 2, so the corresponding costs are: cost3( Y ale; 0Y ale) = 6, cost3( Y ale; 0Y0 ale) = 4, so 0Y0 ale 3 0Y ale and 0Y0 ale is the revision result. 4
The high demands that are imposed on autonomous systems in real domains have led to variations of Event Calculus theories that can support reasoning with partial world knowledge. Such epistemic extensions can accommodate both known and unknown fluents, using a special type of “sense” actions to acquire new knowledge, which by definition only affect the belief state of the agent, causing no effect to the state of the domain. In this section, we discuss how revision of beliefs can be achieved when the sensed information contradicts existing knowledge. We rely on the approach introduced in the recent E F E C dialect that implemented an adaptation of the possible worlds model to give formal semantics to belief predicates.
In E F E C, the function <>: W I ! T is introduced to map world/instant pairs to timepoints. Timepoint < W; I > represents instant I in possible world W , where: 8t9w; i:t =< w; i > (DOX1)
The time lines believed to be accessible at any given moment are captured by the relation K W W, which represents the accessibility relation between possible worlds, as in modal logics. As ordinary, we formally define belief of some fluent f at some timepoint as the fact that this fluent has the same truth value in all worlds that are accessible from the actual world: Bel(f; < Wa; i >) (DOX2) 8wK(w; Wa) ! HoldsAt(f; < w; i >) BelN ot(f; < Wa; i >) (DOX3) 8wK(w; Wa) ! :HoldsAt(f; < w; i >) BelW h(f; < Wa; i >) (DOX4) Bel(f; < Wa; i >) _ BelN ot(f; < Wa; i >)
In contrast to E F E C though, we do not consider K to be an equivalence relation.2 Instead, in order to model belief rather than knowledge, we only assume that K is serial, which is equivalent to stating that the agent cannot believe contradictions (also known as the Consistency Axiom): 8i:Bel(f; < Wa; i >) ! :BelN ot(f; < Wa; i >)(DOX5) 8i:BelN ot(f; < Wa; i >) ! :Bel(f; < Wa; i >)(DOX6) Notice that from the above axioms we do not assume that the actual world is accessible too (K is not reflexive). As a result, erroneous beliefs can still be inferred, requiring a revision mechanism whenever observations (that reflect Wa) do not comply with the agent’s beliefs.
Finally, we need to define a domain-independent axiom to ensure the existence of possible worlds in the initial state. 8f::BelW h(f; < Wa; 0 >) ! (DOX7) 9w1; w2:K(w1; Wa) ^ K(w2; Wa) ^
HoldsAt(f; < w1; 0 >) ^ :HoldsAt(f; < w2; 0 >) Notice that according to our assumption of never losing knowledge (there is no non-determinism), it is sufficient to preserve the number of possible worlds generated at the initial timepoint while reasoning, since there is no way of generating more worlds. We do not need to eliminate worlds either, in order to allow for reasoning about the past.
Based on the aforementioned formalization of belief, we extend the definition of a KB to accommodate lack of knowledge at the initial and at future timepoints: Definition 4 An epistemic KB is defined as e = DE C ^ DOX ^ ^ e 0 ^ ^ , where
DE C is the conjunction of the Discrete Event Calculus domain-independent axioms, DOX is the conjunction of the epistemic axioms to support beliefs,
is the conjunction of the domain-dependent axioms, e 0 is the initial beliefs, i.e., a conjunction of ground Bel(Fi; < Wa; 0 >), BelN ot(Fj ; < Wa; 0 >) axioms at timepoint 0,
is the narrative of actions, i.e., a conjunction of ground Happens(Ei; < w; Ij >) axioms,
is a conjunction of unique name axioms.
The definition for e is more general than the one given for . Specifically, if we assume complete world knowledge at timepoint 0, a single possible world is generated, making e equivalent to .
As before, axioms can be partially defined and then minimized to address the Frame Problem and related issues. e 0 2Note also that the current setting only permits belief statements that refer to the state of world fluent at the same time point. In other words, we do not represent the beliefs at some timepoint about the state of fluents at another timepoint. Such statements are supported in EF EC and will be considered for future extensions of our axiomatization. axioms can be partially defined as well; fluents that are unknown at time instant 0 generate the set of possible worlds according to axiom (DOX7).
The case of revision in the epistemic Event Calculus is virtually identical to the case of the non-epistemic one. Thus, whatever we discussed in Section 3 can be applied here as well. The main difference in the epistemic case is that we can now provide a more fine-grained preference relation, taking special provisions for the case where a fluent whose value was originally unknown, became known (true or false). To do so, an approach similar to the one used in Subsection 3.3 could be used, namely, identifying the sets of formulas of the form Bel(: : : ); BelN ot(: : : ); BelW h(: : : ) that are implied/not implied by e ; e 0 respectively.
In particular, considering two epistemic KBs e ; e 0 the cost to move from e to e 0 will be defined on the basis of the formulas that can be inferred by one of these KBs but not the other. To formalise this, we first define the following sets: Modified Knowledge M KT (e ; e 0) = fBel(F; < Wa; T 0 >) j T 0 T and either e j= Bel(F; < Wa; T 0 >) and e 0 j= BelN ot(F; < Wa; T 0 >), or e j= BelN ot(F; < Wa; T 0 >) and e 0 j= Bel(F; < Wa; T 0 >)g. This represents all Bel() or BelN ot() statements whose truth value was changed during the transition from e to e 0, up to T .
New Knowledge N KT (e ; e 0) = fBel(F; < Wa; T 0 >) j T 0 T and either e j= :BelW h(F; < Wa; T 0 >) and e 0 j= Bel(F; < Wa; T 0 >), or e j= :BelW h(F; < Wa; T 0 >) and e 0 j= BelN ot(F; < Wa; T 0 >)g. This represents all :BelW h() statements whose unknown value was changed to known during the transition from e to e 0, up to T .
Lost Knowledge LKT (e ; e 0) = f:BelW h(F; < Wa; T 0 >) j T 0 T and either e j= Bel(F; < Wa; T 0 >) and e 0 j= :BelW h(F; < Wa; T 0 >), or e j= BelN ot(F; < Wa; T 0 >) and e 0 j= :BelW h(F; < Wa; T 0 >)g. This represents all Bel() or BelN ot() statements whose truth value was changed to unknown during the transition from e to e 0, up to T .
New Events N ET ( ; 0) = fHappens(E; < Wa; T 0 > ) j T 0 T , j= :Happens(E; < Wa; T 0 >) and 0 j= Happens(E; < Wa; T 0 >)g. This represents all events that we had to add in the narrative of to accommodate the observation, up to T .
Lost Events LET ( ; 0) = fHappens(E; < Wa; T 0 > ) j T 0 T , j= Happens(E; < Wa; T 0 >) and 0 j= :Happens(E; < Wa; T 0 >)g. This represents all events that we had to retract from the narrative of to accommodate the observation, up to T .
The cost between two KBs e ; e 0 up to the timepoint T is defined as: costT (e ; e 0) = wMK jM KT (e ; e 0)j + wNK jN KT (e ; e 0)j + wLK jLKT (e ; e 0)j + wNE jN ET (e ; e 0)j + wLE jLET (e ; e 0)j, where wMK ; wNK ; wLK ; wNE ; wLE are the corresponding weights associated to each change (a parameter of our model).
Now, the T relation can be easily defined as follows: e 1 T e 2 iff costT (e ; e 1) < costT (e ; e 2). It is trivial to show that this relation is well-founded, as required by the definition.
The proposed framework was implemented for both the non-epistemic and the epistemic case, using the architecture shown in Figure 1.3 The figure shows the loop of steps performed whenever a new observation arrives, along with the corresponding input/output modules (rulesets). There are two main reasoning steps, interconnected via two Java programs: the first reasoning step generates one answer set in the nonepistemic case and multiple answer sets in the epistemic case, each denoting a possible world (see Section 4), and the second step generates cost-optimal revisions. Reasoning is performed by implementing the Event Calculus axiomatizations as ASP rules and by utilizing the Clingo reasoner [Gebser et al., 2011]. Similarly, the domain-dependent axioms, the epistemic axioms, the main program, the meta-program, the new observations and the current beliefs are all implemented in ASP. The current beliefs module contains the running information about the world state and the narrative of actions. A Java parser intervenes between the two reasoning steps to transform the information contained in the generated answer sets, i.e., the possible worlds, into the agent’s belief predicates. These are introduced in ASP form in the revision metaprogram, which provides the revision results, based on the 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 inconsistency, 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 3http://www.ics.forth.gr/isl/ CS17BelRevPaper/ revisions generator, via a logic program. Roughly, this program generates combinations of fluents in the initial state, as well as combinations of event occurrences at each timepoint, for every possible world, aiming at keeping only the combinations that lead to a consistent KB and are consistent with the new observation (revision candidates). The cost associated with each revision candidate is calculated, based on the cost function described in Section 4; this is implemented with ASP rules that penalize each truth value or event that is different from the output of the first reasoning step. Finally, an optimization statement filters out all non-optimal revision candidates (answer sets). At the end, the program returns the disjunction of the optimal candidates.
Returning to the Yale shooting example described before, an output of the program in the epistemic case is discussed next. Namely, the initial beliefs are that the turkey is alive at timepoint 0 and a shot happens at timepoint 1, but we do not know whether the gun is loaded or not at timepoint 0. Thus, we do not know whether the turkey is alive or not at timepoint 3. Assume now that we receive a new contradicting information that the turkey is alive at timepoint 3. We present the optimal revision that accommodates this observation into our knowledge base in Figure 2, based on the following weights: wMK = 1; wNK = 1; wLK = 2; wNE = 2; wLE = 2. More specifically, the optimal revision is to assume that we were mistaken and the gun was not loaded in the first place. Thus, we have the least possible cumulative cost, as we gain knowledge on the state of the turkey at timepoints 2 and 3, as well as, on the state of the gun at timepoints 0 and 1. Had we accepted the revision that the shooter did not fire the gun, we would lose knowledge and event happenings at various timepoints, and as a result, the cost would be greater in total. Belief change (also known as belief revision) is a mature field of study dealing with the adaptation of a KB in the face of new information [Alchourron et al., 1985]. Traditionally, two types of change have been considered: revision and update [Katsuno and Mendelzon, 1991]. Revision deals with cases where the new information is some observation or refinement of our knowledge about the world, whereas update deals with cases where the adaptation is dictated by some action or event that changed the world itself. The case of belief update is inherently captured by the semantics and reasoning of Event Calculus, where one can explicitly declare events, as well as the effects and preconditions of such events. However, studies regarding the revision of action theories when our observations of the actual world are inconsistent with the theory’s predictions regarding the world’s state are limited.
Most works in the classical belief change literature are dealing with the so-called classical logics [Flouris et al., 2006], which have certain nice properties, both in terms of semantics (monotonicity, compactness, inclusion of the classical tautological implication, etc) and in terms of syntax (closed with respect to the usual operators ^; _; :; etc), Extensions of these theories to apply for ontological languages [Flouris et al., 2006; Qi and Du, 2009], or compact and monotonic logics in general [Ribeiro et al., 2013] have been considered as well. However, to the best of our knowledge, no such study exists for non-monotonic formalisms, partly because many non-monotonic formalisms (most notably, defeasible logic, default logic and paraconsistent logics) have inherent ways to reason under inconsistency without trivializing inference. Thus, technical results from the related literature are not directly applicable in our setting.
Studies that account for epistemic considerations of the Event Calculus are more closely related to ours. More specifically, the E F E C variant introduced in [Miller et al., 2013; Ma et al., 2013] is the first to rely on the possible worlds semantics to reason about knowledge. E F E C supports a multitude of features, such as reasoning about the future and past, or dealing with non-determinism and concurrency. Our work utilizes the same underlying structures to formalize the treatment of epistemic notions, extending them with the ability to revise contradicting knowledge, although it is currently significantly limited in the set of supporting features. In [Patkos and Plexousakis, 2009], a different epistemic extension of discrete-time Event Calculus theories is presented, using a deduction-oriented model of knowledge.
Beyond the Event Calculus, possible-worlds based epistemic extensions for reasoning about actions and knowledge have been developed in the context of other calculi. The first approach that inspired this direction of research is owed to [Moore, 1985], who presented a Kripke-like formulation of epistemic notions of modal logic in action languages by reifying possible worlds as situations. [Scherl and Levesque, 2003] adapted this framework in the Situation 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 problem for knowledge. Other studies introduced further features: [Thielscher, 2000] adapted the model in the context of the Fluent Calculus, [Scherl, 2003] covered concurrent actions, while [Kelly and Pearce, 2008] introduced epistemic modalities for groups of agents. Non-possible-worlds based epistemic action frameworks include [Morgenstern, 1987; Demolombe and Pozos-Parra, 2000; Son and Baral, 2001; Petrick and Levesque, 2002; Vassos and Levesque, 2007; Liu and Lakemeyer, 2009]. In all these frameworks, knowledge is assumed to be always correct and observations that contradict inferred knowledge will lead to inconsistency.
The ability to deal with belief changes has lately started to gain interest within other action languages, as in [Shapiro et al., 2011] and [Schwering et al., 2015] in the Situation Calculus, but without taking time into account. [Van Zee et al., 2015] developed a new action formalism for revision of temporal belief bases; even though related to our work, [Van Zee et al., 2015] do not directly address the problem of revising theories in Event Calculus, but instead define a new logic of action that is closer to propositional logic, thereby allowing technical results from the belief change literature to be directly applicable in their framework. 7
This paper reported on early work towards a formal framework for changing Event Calculus theories in the face of new (and potentially unexpected) observations. Our framework is necessary in the cases where an intelligent agent observes, or otherwise becomes aware of, information that contradicts what was expected by the underlying theory. Even though the rich technical results from the belief change literature are not generally applicable to our setting, we leveraged on some key ideas and adapted them for our purposes. Our approach was based on a set of principles and a preference relation that models the well-known Principle of Minimal Change.
We are currently working on extending the framework with more features and providing a more efficient implementation, along with a more generic preference relation. We are working to accommodate default knowledge, irrelevant fluents, degradation of the cost over time and other domain-specific features. Our implementation will be extended to allow easy parameterization and customization of the preference relation to be used, even at run-time, in order to experiment with the behaviour of different preferences and preference families.
Also, we are planning on establishing stronger connections with existing results from belief change (e.g., satisfaction of certain postulates, or connections between our preference relation and various selection functions or orderings that have been used in other contexts), thereby more thoroughly understanding the properties of the proposed framework. Further, even though our theoretical framework is generic enough to support more complex flavours of action theories and DE C, our implementation will need to be significantly extended to support different Event Calculus dialects and a richer set of commonsense features such as non-determinism, state constraints, and introspective belief changes.