=Paper= {{Paper |id=Vol-2052/paper19 |storemode=property |title=Steps Towards Commonsense-Driven Belief Revision in the Event Calculus |pdfUrl=https://ceur-ws.org/Vol-2052/paper19.pdf |volume=Vol-2052 |authors=Nikoleta Tsampanaki,Giorgos Flouris,Theodore Patkos |dblpUrl=https://dblp.org/rec/conf/commonsense/TsampanakiFP17 }} ==Steps Towards Commonsense-Driven Belief Revision in the Event Calculus== https://ceur-ws.org/Vol-2052/paper19.pdf

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. Gä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. Lespé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.