Event calculus

The event calculus is a logical theory for representing and reasoning about events and about the way in which they change the state of some real or artificial world. It deals both with action events, which are performed by agents, and with external events, which are outside the control of any agent.

The event calculus represents the state of the world at any time by the set of all the facts (called fluents) that hold at the time. Events initiate and terminate fluents:

A fluent holds at a time
if the fluent is initiated by an event that happens at an earlier time
and the fluent is not terminated by any event that happens in the meantime.^{[citation needed]}

The event calculus differs from most other approaches for reasoning about change by reifying time, associating events with the time at which they happen, and associating fluents with the times at which they hold.

The original version of the event calculus, introduced by Robert Kowalski and Marek Sergot in 1986,^[1] was formulated as a logic program and developed for representing narratives and database updates.^[2] Kave Eshghi showed how to use the event calculus for planning,^[3] by using abduction to generate hypothetical actions to achieve a desired state of affairs.

It was extended by Murray Shanahan and Rob Miller in the 1990s^[4] and reformulated in first-order logic with circumscription. These and later extensions have been used to formalize non-deterministic actions, concurrent actions, actions with delayed effects, gradual changes, actions with duration, continuous change, and non-inertial fluents.

Van Lambalgen and Hamm showed how a formulation of the event calculus as a constraint logic program can be used to give an algorithmic semantics to tense and aspect in natural language.^[5]

Fluents and events

In the event calculus, fluents are reified. This means that fluents are represented by terms. For example, $ℎ 𝑜 𝑙 𝑑 𝑠 𝐴 𝑡 (o n (g r e e n_b l o c k, t a b l e), 1)$ expresses that the $𝑔 𝑟 𝑒 𝑒 𝑛_𝑏 𝑙 𝑜 𝑐 𝑘$ is on the $𝑡 𝑎 𝑏 𝑙 𝑒$ at time $1$ . Here $ℎ 𝑜 𝑙 𝑑 𝑠 𝐴 𝑡$ is a predicate, while $𝑜 𝑛 (𝑔 𝑟 𝑒 𝑒 𝑛_𝑏 𝑙 𝑜 𝑐 𝑘, 𝑡 𝑎 𝑏 𝑙 𝑒)$ is a term. In general, the atomic formula

ℎ 𝑜 𝑙 𝑑 𝑠 𝐴 𝑡 (f l u e n t, t i m e)

expresses that the

𝑓 𝑙 𝑢 𝑒 𝑛 𝑡

holds at the

𝑡 𝑖 𝑚 𝑒 .

Events are also reified and represented by terms. For example, $ℎ 𝑎 𝑝 𝑝 𝑒 𝑛 𝑠 𝐴 𝑡 (m o v e (g r e e n_b l o c k, r e d_b l o c k), 3)$ expresses that the $𝑔 𝑟 𝑒 𝑒 𝑛_𝑏 𝑙 𝑜 𝑐 𝑘$ is moved onto the $𝑟 𝑒 𝑑_𝑏 𝑙 𝑜 𝑐 𝑘)$ at time $3$ . In general:

ℎ 𝑎 𝑝 𝑝 𝑒 𝑛 𝑠 𝐴 𝑡 (e v e n t, t i m e)

expresses that the

𝑒 𝑣 𝑒 𝑛 𝑡

happens at the

𝑡 𝑖 𝑚 𝑒 .

The relationships between events and the fluents that they initiate and terminate are also represented by atomic formulae:

𝑖 𝑛 𝑖 𝑡 𝑖 𝑎 𝑡 𝑒 𝑠 (e v e n t, f l u e n t, t i m e)

expresses that if the

𝑒 𝑣 𝑒 𝑛 𝑡

happens at the

𝑡 𝑖 𝑚 𝑒

then the

𝑓 𝑙 𝑢 𝑒 𝑛 𝑡

becomes true after the

𝑡 𝑖 𝑚 𝑒

.

𝑡 𝑒 𝑟 𝑚 𝑖 𝑛 𝑎 𝑡 𝑒 𝑠 (e v e n t, f l u e n t, t i m e)

expresses that if the

𝑒 𝑣 𝑒 𝑛 𝑡

happens at the

𝑡 𝑖 𝑚 𝑒

then the

𝑓 𝑙 𝑢 𝑒 𝑛 𝑡

ceases to be true after the

𝑡 𝑖 𝑚 𝑒

.

Domain-independent axiom

The event calculus was developed in part as an alternative to the situation calculus,^[6]^[7] as a solution to the frame problem, of representing and reasoning about the way in which actions and other events change the state of some world.

There are many variants of the event calculus. But the core axiom of one of the simplest and most useful variants can be expressed as a single, domain-independent axiom:

ℎ 𝑜 𝑙 𝑑 𝑠 𝐴 𝑡 (F, T 2) \leftarrow

[ℎ 𝑎 𝑝 𝑝 𝑒 𝑛 𝑠 𝐴 𝑡 (E 1, T 1) \land 𝑖 𝑛 𝑖 𝑡 𝑖 𝑎 𝑡 𝑒 𝑠 (E 1, F, T 1) \land (T 1 < T 2) \land

\neg \exists E 2, T [ℎ 𝑎 𝑝 𝑝 𝑒 𝑛 𝑠 𝐴 𝑡 (E 2, T) \land 𝑡 𝑒 𝑟 𝑚 𝑖 𝑛 𝑎 𝑡 𝑒 𝑠 (E 2, F, T) \land (T 1 \leq T < T 2)]

The axiom states that

a fluent

F

holds at a time

T 2

if

an event

E 1

happens at a time

T 1

and

E 1

initiates

F

at

T 1

and

T 1

is before

T 2

and

it is not the case that there exists an event

E 2

and a time

T

such that

E 2

happens at

T

and

E 2

terminates

F

at

T

and

T 1

is before or at the same time as

T

and

T

is before

T 2

.

The event calculus solves the frame problem by interpreting this axiom in a non-monotonic logic, such as first-order logic with circumscription^[8] or, as a logic program, in Horn clause logic with negation as failure.^[1] In fact, circumscription is one of the several semantics that can be given to negation as failure,^[9] and it is closely related to the completion semantics for logic programs^[10] (which interprets if as if and only if).

The core event calculus axiom defines the $h o l d s A t$ predicate in terms of the $h a p p e n s A t$ , $i n i t i a t e s$ , $t e r m i n a t e s$ , $<$ and $\leq$ predicates. To apply the event calculus to a particular problem, these other predicates also need to be defined.

The event calculus is compatible with different definitions of the temporal predicates $<$ and $\leq$ . In most applications, times are represented discretely, by the natural numbers, or continuously, by non-negative real numbers. However, times can also be partially ordered.

Domain-dependent axioms

To apply the event calculus in a particular problem domain, it is necessary to define the $i n i t i a t e s$ and $t e r m i n a t e s$ predicates for that domain. For example, in the blocks world domain, an event $m o v e (O b j e c t, P l a c e)$ of moving an object onto a place initiates the fluent $o n (O b j e c t, P l a c e)$ , which expresses that the object is on the place and terminates the fluent $o n (O b j e c t, P l a c e 1)$ , which expresses that the object is on a different place:

𝑖 𝑛 𝑖 𝑡 𝑖 𝑎 𝑡 𝑒 𝑠 (m o v e (O b j e c t, P l a c e), o n (O b j e c t, P l a c e), T i m e) .

𝑡 𝑒 𝑟 𝑚 𝑖 𝑛 𝑎 𝑡 𝑒 𝑠 (m o v e (O b j e c t, P l a c e), o n (O b j e c t, P l a c e 1), T i m e) \leftarrow d i f f e r e n t (P l a c e 1, P l a c e) .

If we want to represent the fact that a $F l u e n t$ holds in an initial state, say at time 1, then with the simple core axiom above we need an event, say $i n i t i a l i s e (F l u e n t)$ , which initiates the $F l u e n t$ at any time:

𝑖 𝑛 𝑖 𝑡 𝑖 𝑎 𝑡 𝑒 𝑠 (i n i t i a l i s e (F l u e n t), F l u e n t, T i m e) .

Problem-dependent axioms

To apply the event calculus, given the definitions of the $h o l d s A t$ , $i n i t i a t e s$ , $t e r m i n a t e s$ , $<$ and $\leq$ predicates, it is necessary to define the $h a p p e n s A t$ predicates that describe the specific context of the problem.

For example, in the blocks world domain, we might want to describe an initial state in which there are two blocks, a red block on a green block on a table, like a toy traffic light, followed by moving the red block to the table at time 1 and moving the green block onto the red block at time 3, turning the traffic light upside down:

ℎ 𝑎 𝑝 𝑝 𝑒 𝑛 𝑠 𝐴 𝑡 (i n i t i a l i s e (o n (r e d_b l o c k, g r e e n_b l o c k), 0)

ℎ 𝑎 𝑝 𝑝 𝑒 𝑛 𝑠 𝐴 𝑡 (i n i t i a l i s e (o n (g r e e n_b l o c k, t a b l e), 0)

ℎ 𝑎 𝑝 𝑝 𝑒 𝑛 𝑠 𝐴 𝑡 (m o v e (r e d_b l o c k, t a b l e), 1)

ℎ 𝑎 𝑝 𝑝 𝑒 𝑛 𝑠 𝐴 𝑡 (m o v e (g r e e n_b l o c k, r e d_b l o c k), 3)

A Prolog implementation

The event calculus has a natural implementation in pure Prolog (without any features that do not have a logical interpretation). For example, the blocks world scenario above can be implemented (with minor modifications) by the program:

holdsAt(Fluent, Time2) :- 
    before(Time1, Time2),
    happensAt(Event, Time1),
    initiates(Event, Fluent, Time1),
    not(clipped(Fluent, Time1, Time2)).
        
clipped(Fluent, Time1, Time2) :-
    terminates(Event, Fluent, Time),
    happensAt(Event, Time), 
    before(Time1, Time),
    before(Time, Time2).

initiates(initialise(Fluent), Fluent, Time).
initiates(move(Object, Place), on(Object, Place), Time).
terminates(move(Object, Place), on(Object, Place1), Time).

happensAt(initialise(on(green_block, table)), 0).
happensAt(initialise(on(red_block, green_block)), 0).
happensAt(move(red_block, table), 1).
happensAt(move(green_block, red_block), 3).

The Prolog program differs from the earlier formalisation in the following ways:

The core axiom has been rewritten, using an auxiliary predicate clipped(Fact, Time1, Time2). This rewriting enables the elimination of existential quantifiers, conforming to the Prolog convention that all variables are universally quantified.
The order of the conditions in the body of the core axiom(s) has been changed, to generate answers to queries in temporal order.
The equality in the condition $T 1 \leq T$ has been removed from the corresponding condition before(Time1, Time). This builds in a simplifying assumption that events do not simultaneously initiate and terminate the same fluent. As a consequence, the definition of the $t e r m i n a t e s$ predicate has been simplified by eliminating the condition that $d i f f e r e n t (P l a c e 1, P l a c e)$ .

Given an appropriate definition^{[note 1]} of the predicate before(Time1, Time2), the Prolog program generates all answers to the query what holds when? in temporal order:

?- holdsAt(Fluent, Time).
Fluent = on(green_block,table),     Time = 1.
Fluent = on(red_block,green_block), Time = 1.
Fluent = on(green_block,table),     Time = 2.
Fluent = on(red_block,table),       Time = 2.
Fluent = on(green_block,table),     Time = 3.
Fluent = on(red_block,table),       Time = 3.
Fluent = on(red_block,table),       Time = 4.
Fluent = on(green_block,red_block), Time = 4.
Fluent = on(red_block,table),       Time = 5.
Fluent = on(green_block,red_block), Time = 5.

The program can also answer negative queries, such as which fluents do not hold at which times? However, to work correctly, all variables in negative conditions must first be instantiated to terms containing no variables. For example:

timePoint(1).
timePoint(2).
timePoint(3).
timePoint(4).
timePoint(5).

fluent(on(red_block, green_block)).
fluent(on(green_block, red_block)).
fluent(on(red_block, table)).
fluent(on(green_block, table)).

?- timePoint(T), fluent(F), not(holdsAt(F, T)).
F = on(green_block,red_block),  T = 1.
F = on(red_block,table),        T = 1.
F = on(red_block,green_block),  T = 2.
F = on(green_block,red_block),  T = 2.
F = on(red_block,green_block),  T = 3.
F = on(green_block,red_block),  T = 3.
F = on(red_block,green_block),  T = 4.
F = on(green_block,table),      T = 4.
F = on(red_block,green_block),  T = 5.
F = on(green_block,table),      T = 5.

Reasoning tools

In addition to Prolog and its variants, several other tools for reasoning using the event calculus are also available:

Extensions

Notable extensions of the event calculus include Markov logic networks–based variants^[12] probabilistic,^[13] epistemic^[14] and their combinations.^[15]

References

1 2 Kowalski, Robert; Sergot, Marek (1986-03-01). "A logic-based calculus of events". New Generation Computing. 4 (1): 67–95. doi:10.1007/BF03037383. ISSN 1882-7055. S2CID 7584513.
↑ Kowalski, Robert (1992-01-01). "Database updates in the event calculus". The Journal of Logic Programming. 12 (1): 121–146. doi:10.1016/0743-1066(92)90041-Z. ISSN 0743-1066.
↑ Eshghi, Kave (1988). "Abductive planning with event calculus". Iclp/SLP: 562–579.
↑ Miller, Rob; Shanahan, Murray (2002), "Some Alternative Formulations of the Event Calculus", in Kakas, Antonis C.; Sadri, Fariba (eds.), Computational Logic: Logic Programming and Beyond: Essays in Honour of Robert A. Kowalski Part II, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, pp. 452–490, doi:10.1007/3-540-45632-5_17, ISBN 978-3-540-45632-2, retrieved 2020-10-05
↑ Lambalgen, Hamm (2005). The proper treatment of events. Malden, MA: Blackwell Pub. ISBN 978-0-470-75925-7. OCLC 212129657.
↑ J. McCarthy and P. Hayes (1969). Some philosophical problems from the standpoint of artificial intelligence. In B. Meltzer and D. Michie, editors, Machine Intelligence, 4:463–502. Edinburgh University Press, 1969.
↑ R. Reiter (1991). The frame problem in the situation calculus: a simple solution (sometimes) and a completeness result for goal regression. In Vladimir Lifshitz, editor, Artificial intelligence and mathematical theory of computation: papers in honour of John McCarthy, pages 359–380, San Diego, CA, USA. Academic Press Professional, Inc. 1991.
↑ Shanahan, M. (1997) Solving the frame problem: A mathematical investigation of the common sense law of inertia. MIT Press.
↑ Gelfond, M.; Przymusinska, H.; Przymusinski, T. (1989). "On the relationship between circumscription and negation as failure". Artificial Intelligence. 38 (1): 75–94. doi:10.1016/0004-3702(89)90068-4.
↑ Clark, K.L. (1977). "Negation as Failure". Logic and Data Bases. Boston, MA: Springer US. pp. 293–322. doi:10.1007/978-1-4684-3384-5_11. ISBN 978-1-4684-3386-9.
↑ D'Asaro, Fabio Aurelio; Bikakis, Antonis; Dickens, Luke; Miller, Rob (2024). "An answer set programming-based implementation of epistemic probabilistic event calculus". International Journal of Approximate Reasoning. 165 109101. doi:10.1016/j.ijar.2023.109101. ISSN 0888-613X.
↑ Skarlatidis, Anastasios; Paliouras, Georgios; Artikis, Alexander; Vouros, George A. (2015-02-17). "Probabilistic Event Calculus for Event Recognition". ACM Transactions on Computational Logic. 16 (2): 11:1–11:37. arXiv:1207.3270. doi:10.1145/2699916. ISSN 1529-3785. S2CID 6389629.
↑ Skarlatidis, Anastasios; Artikis, Alexander; Filippou, Jason; Paliouras, Georgios (March 2015). "A probabilistic logic programming event calculus". Theory and Practice of Logic Programming. 15 (2): 213–245. arXiv:1204.1851. doi:10.1017/S1471068413000690. ISSN 1471-0684. S2CID 5701272.
↑ Ma, Jiefei; Miller, Rob; Morgenstern, Leora; Patkos, Theodore (2014-07-28). "An Epistemic Event Calculus for ASP-based Reasoning About Knowledge of the Past, Present and Future". EPiC Series in Computing. 26. EasyChair: 75–87. doi:10.29007/zswj.
↑ D'Asaro, Fabio Aurelio; Bikakis, Antonis; Dickens, Luke; Miller, Rob (2020-10-01). "Probabilistic reasoning about epistemic action narratives". Artificial Intelligence. 287 103352. doi:10.1016/j.artint.2020.103352. ISSN 0004-3702. S2CID 221521535.

Notes

↑ For example:

before(Time1, Time2) :-
   timeline(Eternity), 
   append(Before, [Time2 | After], Eternity), 
   member(Time1, Before).

timeline([0, 1, 2, 3, 4, 5]).

[EC-1] 1 2 Kowalski, Robert; Sergot, Marek (1986-03-01). "A logic-based calculus of events". New Generation Computing. 4 (1): 67–95. doi:10.1007/BF03037383. ISSN 1882-7055. S2CID 7584513.

[2] Kowalski, Robert (1992-01-01). "Database updates in the event calculus". The Journal of Logic Programming. 12 (1): 121–146. doi:10.1016/0743-1066(92)90041-Z. ISSN 0743-1066.

[3] Eshghi, Kave (1988). "Abductive planning with event calculus". Iclp/SLP: 562–579.

[4] Miller, Rob; Shanahan, Murray (2002), "Some Alternative Formulations of the Event Calculus", in Kakas, Antonis C.; Sadri, Fariba (eds.), Computational Logic: Logic Programming and Beyond: Essays in Honour of Robert A. Kowalski Part II, Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, pp. 452–490, doi:10.1007/3-540-45632-5_17, ISBN 978-3-540-45632-2, retrieved 2020-10-05

[5] Lambalgen, Hamm (2005). The proper treatment of events. Malden, MA: Blackwell Pub. ISBN 978-0-470-75925-7. OCLC 212129657.

[6] J. McCarthy and P. Hayes (1969). Some philosophical problems from the standpoint of artificial intelligence. In B. Meltzer and D. Michie, editors, Machine Intelligence, 4:463–502. Edinburgh University Press, 1969.

[7] R. Reiter (1991). The frame problem in the situation calculus: a simple solution (sometimes) and a completeness result for goal regression. In Vladimir Lifshitz, editor, Artificial intelligence and mathematical theory of computation: papers in honour of John McCarthy, pages 359–380, San Diego, CA, USA. Academic Press Professional, Inc. 1991.

[8] Shanahan, M. (1997) Solving the frame problem: A mathematical investigation of the common sense law of inertia. MIT Press.

[9] Gelfond, M.; Przymusinska, H.; Przymusinski, T. (1989). "On the relationship between circumscription and negation as failure". Artificial Intelligence. 38 (1): 75–94. doi:10.1016/0004-3702(89)90068-4.

[10] Clark, K.L. (1977). "Negation as Failure". Logic and Data Bases. Boston, MA: Springer US. pp. 293–322. doi:10.1007/978-1-4684-3384-5_11. ISBN 978-1-4684-3386-9.

[12] D'Asaro, Fabio Aurelio; Bikakis, Antonis; Dickens, Luke; Miller, Rob (2024). "An answer set programming-based implementation of epistemic probabilistic event calculus". International Journal of Approximate Reasoning. 165 109101. doi:10.1016/j.ijar.2023.109101. ISSN 0888-613X.

[13] Skarlatidis, Anastasios; Paliouras, Georgios; Artikis, Alexander; Vouros, George A. (2015-02-17). "Probabilistic Event Calculus for Event Recognition". ACM Transactions on Computational Logic. 16 (2): 11:1–11:37. arXiv:1207.3270. doi:10.1145/2699916. ISSN 1529-3785. S2CID 6389629.

[14] Skarlatidis, Anastasios; Artikis, Alexander; Filippou, Jason; Paliouras, Georgios (March 2015). "A probabilistic logic programming event calculus". Theory and Practice of Logic Programming. 15 (2): 213–245. arXiv:1204.1851. doi:10.1017/S1471068413000690. ISSN 1471-0684. S2CID 5701272.

[15] Ma, Jiefei; Miller, Rob; Morgenstern, Leora; Patkos, Theodore (2014-07-28). "An Epistemic Event Calculus for ASP-based Reasoning About Knowledge of the Past, Present and Future". EPiC Series in Computing. 26. EasyChair: 75–87. doi:10.29007/zswj.

[16] D'Asaro, Fabio Aurelio; Bikakis, Antonis; Dickens, Luke; Miller, Rob (2020-10-01). "Probabilistic reasoning about epistemic action narratives". Artificial Intelligence. 287 103352. doi:10.1016/j.artint.2020.103352. ISSN 0004-3702. S2CID 221521535.

[11] For example:
before(Time1, Time2) :- timeline(Eternity), append(Before, [Time2 | After], Eternity), member(Time1, Before). timeline([0, 1, 2, 3, 4, 5]).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[note 1]

[11]

[12]

[13]

[14]

[15]

Event calculus

Fluents and events

Domain-independent axiom

Domain-dependent axioms

Problem-dependent axioms

A Prolog implementation

Reasoning tools

Extensions

See also

References

Further reading

Notes