Event calculus
   HOME

TheInfoList



OR:

The event calculus is a
logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...
al language for representing and reasoning about events and their effects first presented by
Robert Kowalski Robert Anthony Kowalski (born 15 May 1941) is an American-British logician and computer scientist, whose research is concerned with developing both human-oriented models of computing and computational models of human thinking. He has spent mo ...
and Marek Sergot in 1986. It was extended by Murray Shanahan and Rob Miller in the 1990s. Similar to other languages for reasoning about change, the event calculus represents the effects of
action Action may refer to: * Action (narrative), a literary mode * Action fiction, a type of genre fiction * Action game, a genre of video game Film * Action film, a genre of film * ''Action'' (1921 film), a film by John Ford * ''Action'' (1980 fil ...
s on fluents. However,
event Event may refer to: Gatherings of people * Ceremony, an event of ritual significance, performed on a special occasion * Convention (meeting), a gathering of individuals engaged in some common interest * Event management, the organization of e ...
s can also be external to the system. In the event calculus, one can specify the value of fluents at some given time points, the events that take place at given time points, and their effects.


Fluents and events

In the event calculus, fluents are reified. This means that they are not formalized by means of
predicate Predicate or predication may refer to: * Predicate (grammar), in linguistics * Predication (philosophy) * several closely related uses in mathematics and formal logic: **Predicate (mathematical logic) **Propositional function **Finitary relation, o ...
s but by means of
function Function or functionality may refer to: Computing * Function key, a type of key on computer keyboards * Function model, a structured representation of processes in a system * Function object or functor or functionoid, a concept of object-oriente ...
s. A separate predicate is used to tell which fluents hold at a given time point. For example, \mathit(on(box,table),t) means that the box is on the table at time ; in this formula, is a predicate while is a function. Events are also represented as terms. The effects of events are given using the predicates and . In particular, \mathit(e,f,t) means that, if the event represented by the term is executed at time , then the fluent will be true after . The predicate has a similar meaning, with the only difference being that will be false after .


Domain-independent axioms

Like other languages for representing actions, the event calculus formalizes the correct evolution of the fluent via formulae telling the value of each fluent after an arbitrary action has been performed. The event calculus solves the
frame problem In artificial intelligence, the frame problem describes an issue with using first-order logic (FOL) to express facts about a robot in the world. Representing the state of a robot with traditional FOL requires the use of many axioms that simply impl ...
in a way that is similar to the successor state axioms of the
situation calculus The situation calculus is a logic formalism designed for representing and reasoning about dynamical domains. It was first introduced by John McCarthy in 1963. The main version of the situational calculus that is presented in this article is based o ...
: a fluent is true at time if and only if it has been made true in the past and has not been made false in the meantime. :\mathit(f,t) \leftarrow mathit(e,t_1) \wedge \mathit(e,f,t_1) \wedge (t_1/math> This formula means that the fluent represented by the term is true at time if: # an event has taken place: \mathit(e,t_1); # this took place in the past: \mathit_1; # this event has the fluent as an effect: \mathit(e,f,t_1); # the fluent has not been made false in the meantime: \mathit(t_1,f,t) A similar formula is used to formalize the opposite case in which a fluent is false at a given time. Other formulae are also needed for correctly formalizing fluents before they have been effects of an event. These formulae are similar to the above, but \mathit(e,t_1) \wedge \mathit(e,f,t_1) is replaced by \mathit(f,t_1). The predicate, stating that a fluent has been made false during an interval, can be axiomatized, or simply taken as a shorthand, as follows: :\mathit(t_1,f,t_2) \equiv \exists e,t mathit(e,t) \wedge (t_1 \leq t < t_2) \wedge \mathit(e,f,t)/math>


Domain-dependent axioms

The axioms above relate the value of the predicates , and , but do not specify which fluents are known to be true and which events actually make fluents true or false. This is done by using a set of domain-dependent axioms. The known values of fluents are stated as simple literals \mathit(f,t). The effects of events are stated by formulae relating the effects of events with their preconditions. For example, if the event makes the fluent true, but only if is currently true, the corresponding formula in the event calculus is: :\mathit(e,f,t) \equiv e=open \wedge f=isopen \wedge \mathit(haskey, t)\vee \cdots The right-hand expression of this equivalence is composed of a disjunction: for each event and fluent that can be made true by the event, there is a disjunct saying that is actually that event, that is actually that fluent, and that the precondition of the event is met. The formula above specifies the
truth value In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth, which in classical logic has only two possible values (''true'' or '' false''). Computing In some progr ...
of \mathit(e,f,t) for every possible event and fluent. As a result, all effects of all events have to be combined in a single formulae. This is a problem, because the addition of a new event requires modifying an existing formula rather than adding new ones. This problem can be solved by the application of
circumscription Circumscription may refer to: *Circumscribed circle *Circumscription (logic) *Circumscription (taxonomy) * Circumscription theory, a theory about the origins of the political state in the history of human evolution proposed by the American anthrop ...
to a set of formulae each specifying one effect of one event: : \mathit(open, isopen, t) \leftarrow \mathit(haskey, t) : \mathit(break, isopen, t) \leftarrow \mathit(hashammer, t) : \mathit(break, broken, t) \leftarrow \mathit(hashammer, t) These formulae are simpler than the formula above, because each effect of each event can be specified separately. The single formula telling which events and fluents make \mathit(e,f,t) true has been replaced by a set of smaller formulae, each one telling the effect of an event on a fluent. However, these formulae are not equivalent to the formula above. Indeed, they only specify sufficient conditions for \mathit(e,f,t) to be true, which should be completed by the fact that is false in all other cases. This fact can be formalized by simply circumscribing the predicate in the formula above. It is important to note that this circumscription is done only on the formulae specifying and not on the domain-independent axioms. The predicate can be specified in the same way is. A similar approach can be taken for the predicate. The evaluation of this predicate can be enforced by formulae specifying not only when it is true and when it is false: :\mathit(e,t) \equiv (e=open \wedge t=0) \vee (e=exit \wedge t=1) \vee \cdots Circumscription can simplify this specification, as only necessary conditions can be specified: :\mathit(open, 0) :\mathit(exit, 1) Circumscribing the predicate , this predicate will be false at all points in which it is not explicitly specified to be true. This circumscription has to be done separately from the circumscription of the other formulae. In other words, if is the set of formulae of the kind \mathit(e,f,t) \leftarrow \cdots, is the set of formulae \mathit(e, t), and are the domain independent axioms, the correct formulation of the domain is: :\mathit(F; \mathit, \mathit) \wedge Circ(G; Happens) \wedge H


The event calculus as a logic program

The event calculus was originally formulated as a set of
Horn clauses In mathematical logic and logic programming, a Horn clause is a logical formula of a particular rule-like form which gives it useful properties for use in logic programming, formal specification, and model theory. Horn clauses are named for the log ...
augmented with
negation as failure Negation as failure (NAF, for short) is a non-monotonic inference rule in logic programming, used to derive \mathrm~p (i.e. that ~p is assumed not to hold) from failure to derive ~p. Note that \mathrm ~p can be different from the statement \neg p ...
and could be run as a
Prolog Prolog is a logic programming language associated with artificial intelligence and computational linguistics. Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primarily ...
program. In fact, circumscription is one of the several semantics that can be given to negation as failure, and is closely related to the completion semantics (in which "if" is interpreted as "if and only if" — see
logic programming Logic programming is a programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic prog ...
).


Extensions and applications

The original event calculus paper of Kowalski and Sergot focused on applications to database updates and narratives. Extensions of the event calculus can also formalize non-deterministic actions, concurrent actions, actions with delayed effects, gradual changes, actions with duration, continuous change, and non-inertial fluents. Kave Eshghi showed how the event calculus can be used for planning, using abduction to generate hypothetical events in abductive logic programming. Van Lambalgen and Hamm showed how the event calculus can also be used to give an algorithmic semantics to tense and aspect in natural language using
constraint logic programming Constraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. A constraint logic program is a logic program that contains constraints in the body of clau ...
. Other notable extensions of the Event Calculus include Markov Logic Networks-based,
probabilistic Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...
, epistemic variants and their combinations.


Reasoning tools

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

Discrete Event Calculus Reasoner

Event Calculus Answer Set Programming



Run-Time Event Calculus (RTEC)


See also

*
First-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
*
Frame problem In artificial intelligence, the frame problem describes an issue with using first-order logic (FOL) to express facts about a robot in the world. Representing the state of a robot with traditional FOL requires the use of many axioms that simply impl ...
*
Situation calculus The situation calculus is a logic formalism designed for representing and reasoning about dynamical domains. It was first introduced by John McCarthy in 1963. The main version of the situational calculus that is presented in this article is based o ...


References


Further reading

* Brandano, S. (2001)
The Event Calculus Assessed
" ''IEEE TIME Symposium'': 7-12. * R. Kowalski and F. Sadri (1995)
Variants of the Event Calculus
" ''ICLP'': 67-81. * Mueller, Erik T. (2015). ''Commonsense Reasoning: An Event Calculus Based Approach (2nd Ed.)''. Waltham, MA: Morgan Kaufmann/Elsevier. {{ISBN, 978-0128014165. (Guide to using the event calculus) * Shanahan, M. (1997)
Solving the frame problem: A mathematical investigation of the common sense law of inertia
'. MIT Press. * Shanahan, M. (1999)
The Event Calculus Explained
Springer Verlag, LNAI (1600): 409-30. 1986 introductions Logic in computer science Logic programming Knowledge representation Logical calculi