Model category: Difference between revisions

Revision as of 21:51, 18 November 2013

The event calculus is a logical language for representing and reasoning about actions and their effects first presented by Robert Kowalski and Marek Sergot in 1986. It was extended by Murray Shanahan and Rob Miller in the 1990s. The basic components of the event calculus, as with other similar languages for reasoning about actions and change are fluents and actions. In the event calculus, one can specify the value of fluents at some given time points, the actions that took place at given time points, and their effects.

Fluents and actions

In the event calculus, fluents are reified. This means that statements are not formalized as predicates but as functions. A separate predicate $H o l d s A t$ is used to tell which fluents hold at a given time point. For example, $H o l d s A t (o n (b o x, t a b l e), t)$ means that the box is on the table at time $t$ ; in this formula, $H o l d s A t$ is a predicate while $o n$ is a function.

Actions are also represented as terms. The effects of actions are given using the predicates $I n i t i a t e s$ and $T e r m i n a t e s$ . In particular, $I n i t i a t e s (a, f, t)$ means that, if the action represented by the term $a$ is executed at time $t$ , then the fluent $f$ will be true after $t$ . The $T e r m i n a t e s$ predicate has a similar meaning, with the only difference being that $f$ will be false and not true after $t$ .

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 a way that is similar to the successor state axioms of the situation calculus: a fluent is true at time $t$ if and only if it has been made true in the past and has not been made false in the meantime.

H o l d s A t (f, t) \leftarrow [H a p p e n s (a, t_{1}) \land I n i t i a t e s (a, f, t_{1}) \land (t_{1} < t) \land \neg C l i p p e d (t_{1}, f, t)]

This formula means that the fluent represented by the term $f$ is true at time $t$ if:

an action $a$ has taken place: $H a p p e n s (a, t_{1})$ ;
this took place in the past: $t_{1} < t$ ;
this action has the fluent as an effect: $I n i t i a t e s (a, f, t_{1})$ ;
the fluent has not been made false in the meantime: $C l i p p e d (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 action. These formulae are similar to the above, but $H a p p e n s (a, t_{1}) \land I n i t i a t e s (a, f, t_{1})$ is replaced by $H o l d s A t (f, t_{1})$ .

The $C l i p p e d$ predicate, stating that a fluent has been made false during an interval, can be axiomatized, or simply taken as a shorthand, as follows:

C l i p p e d (t_{1}, f, t_{2}) \equiv \exists a, t [H a p p e n s (a, t) \land (t_{1} \leq t < t_{2}) \land T e r m i n a t e s (a, f, t)]

Domain-dependent axioms

The axioms above relate the value of the predicates $H o l d s A t$ , $I n i t i a t e s$ and $T e r m i n a t e s$ , but do not specify which fluents are known to be true and which actions 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 $H o l d s A t (f, t)$ . The effects of actions are stated by formulae relating the effects of actions with their preconditions. For example, if the action $o p e n$ makes the fluent $i s o p e n$ true, but only if $h a s k e y$ is currently true, the corresponding formula in the event calculus is:

I n i t i a t e s (a, f, t) \equiv [a = o p e n \land f = i s o p e n \land H o l d s A t (h a s k e y, t)] \lor \dots

The right-hand expression of this equivalence is composed of a disjunction: for each action and fluent that can be made true by the action, there is a disjunct saying that $a$ is actually that action, that $f$ is actually that fluent, and that the precondition of the action is met.

The formula above specifies the truth value of $I n i t i a t e s (a, f, t)$ for every possible action and fluent. As a result, all effects of all actions have to be combined in a single formulae. This is a problem, because the addition of a new action requires modifying an existing formula rather than adding new ones. This problem can be solved by the application of circumscription to a set of formulae each specifying one effect of one action:

I n i t i a t e s (o p e n, i s o p e n, t) \leftarrow H o l d s A t (h a s k e y, t)

I n i t i a t e s (b r e a k, i s o p e n, t) \leftarrow H o l d s A t (h a s h a m m e r, t)

I n i t i a t e s (b r e a k, b r o k e n, t) \leftarrow H o l d s A t (h a s h a m m e r, t)

These formulae are simpler than the formula above, because each effect of each action can be specified separately. The single formula telling which actions $a$ and fluents $f$ make $I n i t i a t e s (a, f, t)$ true has been replaced by a set of smaller formulae, each one telling the effect of an action to a fluent.

However, these formulae are not equivalent to the formula above. Indeed, they only specify sufficient conditions for $I n i t i a t e s (a, f, t)$ to be true, which should be completed by the fact that $I n i t i a t e s$ is false in all other cases. This fact can be formalized by simply circumscribing the predicate $I n i t i a t e s$ in the formula above. It is important to note that this circumscription is done only on the formulae specifying $I n i t i a t e s$ and not on the domain-independent axioms. The predicate $T e r m i n a t e s$ can be specified in the same way $I n i t i a t e s$ is.

A similar approach can be taken for the $H a p p e n s$ predicate. The evaluation of this predicate can be enforced by formulae specifying not only when it is true and when it is false:

H a p p e n s (a, t) \equiv (a = o p e n \land t = 0) \lor (a = e x i t \land t = 1) \lor \dots

Circumscription can simplify this specification, as only necessary conditions can be specified:

H a p p e n s (o p e n, 0)

H a p p e n s (e x i t, 1)

Circumscribing the predicate $H a p p e n s$ , this predicate will be false in 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 $F$ is the set of formulae of the kind $I n i t i a t e s (a, f, t) \leftarrow \dots$ , $G$ is the set of formulae $H a p p e n s (a, t)$ , and $H$ are the domain independent axioms, the correct formulation of the domain is:

C i r c (F; I n i t i a t e s, T e r m i n a t e s) \land C i r c (G; H a p p e n s) \land H

The event calculus as a logic program

The event calculus was originally formulated as a set of Horn clauses augmented with negation as failure and could be run as a Prolog 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).

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.

Reasoning tools

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

References

Brandano, S. (2001) "The Event Calculus Assessed," IEEE TIME Symposium: 7-12.
Eshghi, K. (1988) "Abductive Planning with Event Calculus," ICLP/SLP: 562-79.
Kowalski, R. (1992) "Database updates in the event calculus," Journal of Logic Programming 12 (162): 121-46.
-------- and M. Sergot (1986) "A Logic-Based Calculus of Events," New Generation Computing 4: 67–95.
-------- and F. Sadri (1995) "Variants of the Event Calculus," ICLP: 67-81.
Miller, R., and M. Shanahan (1999) "The event-calculus in classical logic — alternative axiomatizations," Electronic Transactions on Artificial Intelligence 3(1): 77-105.
Mueller, E. T. (2006) Commonsense Reasoning. Morgan Kaufmann. ISBN 0-12-369388-8 (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.
-------- (1999) "The Event Calculus Explained," Springer Verlag, LNAI (1600): 409-30.
Van Lambalgen, M., and F. Hamm (2005) The proper treatment of events. Oxford and Boston: Blackwell Publishing.

@@ Line 1: / Line 1: @@
-Let me initial begin by [http://www.Dermnet.com/images/Herpes-Type-2-Primary introducing] myself. My name is Boyd Butts although it is not the name on my beginning certificate. Bookkeeping is what I do. One of the very best things in the world for me is to do [http://www.sciencedaily.com/releases/2013/10/131030185930.htm aerobics] and now I'm attempting to make money   [http://www.videokeren.com/user/FJWW home std test kit] std testing at  over the counter std test home with it.  home std test kit  [http://telekomxchange.com/groups/prevent-infections-before-hand-using-these-tips/ std home test] North Dakota is her beginning location but she will have to transfer 1 working day or an additional.<br><br>Here is my website ... [http://Www.Neweracinema.com/tube/user/KOPR neweracinema.com]
+The '''event calculus''' is a [[logic]]al language for representing and reasoning about actions and their effects first presented by [[Robert Kowalski]] and Marek Sergot in 1986.
+It was extended by Murray Shanahan and Rob Miller in the 1990s.
+The basic components of the event calculus, as with other similar languages for reasoning about actions and change are [[fluent (artificial intelligence)|fluent]]s and [[Action (artificial intelligence)|action]]s. In the event calculus, one can specify the value of fluents at some given time points, the actions that took place at given time points, and  their effects.
+==Fluents and actions==
+In the event calculus, fluents are reified. This means that statements are not formalized as [[Predicate (mathematics)|predicate]]s but as [[function (mathematics)|function]]s. A separate predicate <math>HoldsAt</math> is used to tell which fluents hold at a given time point. For example, <math>HoldsAt(on(box,table),t)</math> means that the box is on the table at time <math>t</math>; in this formula, <math>HoldsAt</math> is a predicate while <math>on</math> is a function.
+Actions are also represented as terms. The effects of actions are given using the predicates <math>Initiates</math> and <math>Terminates</math>. In particular, <math>Initiates(a,f,t)</math> means that,
+if the action represented by the term <math>a</math> is executed at time <math>t</math>,
+then the fluent <math>f</math> will be true after <math>t</math>.
+The <math>Terminates</math> predicate has a similar meaning, with the only difference
+being that <math>f</math> will be false and not true after <math>t</math>.
+==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 a way that is similar to the [[successor state axiom]]s of the [[situation calculus]]: a fluent is true at time <math>t</math> if and only if it has been made true in the past and has not been made false in the meantime.
+:<math>HoldsAt(f,t) \leftarrow
+[Happens(a,t_1) \wedge Initiates(a,f,t_1)
+\wedge (t_1<t) \wedge \neg Clipped(t_1,f,t)]</math>
+This formula means that the fluent represented by the term <math>f</math> is true at time <math>t</math> if:
+# an action <math>a</math> has taken place: <math>Happens(a,t_1)</math>;
+# this took place in the past: <math>t_1<t</math>;
+# this action has the fluent as an effect: <math>Initiates(a,f,t_1)</math>;
+# the fluent has not been made false in the meantime: <math>Clipped(t_1,f,t)</math>
+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 action. These formulae are similar to the above, but <math>Happens(a,t_1) \wedge Initiates(a,f,t_1)</math> is replaced by <math>HoldsAt(f,t_1)</math>.
+The <math>Clipped</math> predicate, stating that a fluent has been made false during an interval, can be axiomatized, or simply taken as a shorthand, as follows:
+:<math>Clipped(t_1,f,t_2) \equiv
+\exists a,t
+[Happens(a,t) \wedge (t_1 \leq t < t_2) \wedge Terminates(a,f,t)]</math>
+==Domain-dependent axioms==
+The axioms above relate the value of the predicates <math>HoldsAt</math>, <math>Initiates</math> and <math>Terminates</math>, but do not specify which fluents are known to be true and which actions 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 <math>HoldsAt(f,t)</math>. The effects of actions are stated by formulae relating the effects of actions with their preconditions. For example, if the action <math>open</math> makes the fluent <math>isopen</math> true, but only if <math>haskey</math> is currently true, the corresponding formula in the event calculus is:
+:<math>Initiates(a,f,t) \equiv
+[ a=open \wedge f=isopen \wedge HoldsAt(haskey, t)] \vee \cdots
+</math>
+The right-hand expression of this equivalence is composed of a disjunction: for each action and fluent that can be made true by the action, there is a disjunct saying that <math>a</math> is actually that action, that <math>f</math> is actually that fluent, and that the precondition of the action is met.
+The formula above specifies the [[truth value]] of <math>Initiates(a,f,t)</math> for every possible action and fluent. As a result, all effects of all actions have to be combined in a single formulae. This is a problem, because the addition of a new action requires modifying an existing formula rather than adding new ones. This problem can be solved by the application of [[Circumscription (logic)|circumscription]] to a set of formulae each specifying one effect of one action:
+: <math>Initiates(open, isopen, t) \leftarrow HoldsAt(haskey, t)</math>
+: <math>Initiates(break, isopen, t) \leftarrow HoldsAt(hashammer, t)</math>
+: <math>Initiates(break, broken, t) \leftarrow HoldsAt(hashammer, t)</math>
+These formulae are simpler than the formula above, because each effect of each action can be specified separately. The single formula telling which actions <math>a</math> and fluents <math>f</math> make <math>Initiates(a,f,t)</math> true has been replaced by a set of smaller formulae, each one telling the effect of an action to a fluent.
+However, these formulae are not equivalent to the formula above. Indeed, they only specify sufficient conditions for <math>Initiates(a,f,t)</math> to be true, which should be completed by the fact that <math>Initiates</math> is false in all other cases. This fact can be formalized by simply circumscribing the predicate <math>Initiates</math> in the formula above. It is important to note that this circumscription is done only on the formulae specifying <math>Initiates</math> and not on the domain-independent axioms. The predicate <math>Terminates</math> can be specified in the same way <math>Initiates</math> is.
+A similar approach can be taken for the <math>Happens</math> predicate. The evaluation of this predicate can be enforced by formulae specifying not only when it is true and when it is false:
+:<math>Happens(a,t) \equiv
+(a=open \wedge t=0) \vee (a=exit \wedge t=1) \vee \cdots</math>
+Circumscription can simplify this specification, as only necessary conditions can be specified:
+:<math>Happens(open, 0)</math>
+:<math>Happens(exit, 1)</math>
+Circumscribing the predicate <math>Happens</math>, this predicate will be false in 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 <math>F</math> is the set of formulae of the kind <math>Initiates(a,f,t) \leftarrow \cdots</math>, <math>G</math> is the set of formulae <math>Happens(a, t)</math>, and <math>H</math> are the domain independent axioms, the correct formulation of the domain is:
+:<math>Circ(F; Initiates, Terminates) \wedge
+Circ(G; Happens) \wedge H</math>
+==The event calculus as a logic program==
+The event calculus was originally formulated as a set of [[Horn clauses]] augmented with negation as failure and could be run as a [[Prolog]] 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" &mdash; see [[logic programming]]).
+==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 (logic)|abduction]] to generate hypothetical events in [[Abductive Logic Programming|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.
+==Reasoning tools==
+In addition to Prolog and its variants, several other tools for reasoning using the event calculus are also available:
+* [http://www.doc.ic.ac.uk/~mpsha/planners.html Abductive Event Calculus Planners]
+* [http://decreasoner.sourceforge.net/ Discrete Event Calculus Reasoner]
+* [http://reasoning.eas.asu.edu/ecasp/ Event Calculus Answer Set Programming]
+==See also==
+* [[First-order logic]]
+* [[Frame problem]]
+* [[Situation calculus]]
+==References==
+* Brandano, S. (2001) "[http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?isnumber=20130&arnumber=930691&count=35&index=2 The Event Calculus Assessed,]" ''IEEE TIME Symposium'': 7-12.
+* Eshghi, K. (1988) "Abductive Planning with Event Calculus," ''ICLP/SLP'': 562-79.
+* Kowalski, R. (1992) "Database updates in the event calculus," ''Journal of Logic Programming 12 (162)'': 121-46.
+* -------- and M. Sergot (1986) "[http://www.doc.ic.ac.uk/~rak/papers/event%20calculus.pdf A Logic-Based Calculus of Events,]" ''New Generation Computing 4'': 67–95.
+* -------- and F. Sadri (1995) "Variants of the Event Calculus," ''ICLP'': 67-81.
+* Miller, R., and M. Shanahan (1999) "[http://www.ida.liu.se/ext/epa/ej/etai/1999/016/epapage.html The event-calculus in classical logic — alternative axiomatizations,]" ''[[Electronic Transactions on Artificial Intelligence]]'' 3(1): 77-105.
+* Mueller, E. T. (2006) ''Commonsense Reasoning.'' Morgan Kaufmann. ISBN 0-12-369388-8 (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.
+* -------- (1999) "[http://www.springerlink.com/content/1bxk8gd0n6pajxbq/?p=8f3428a89bad4589a949d74b6f0ec98d&pi=0 The Event Calculus Explained,]" Springer Verlag, LNAI (1600): 409-30.
+* Van Lambalgen, M., and F. Hamm (2005) ''The proper treatment of events''. Oxford and Boston: Blackwell Publishing.
+[[Category:1986 introductions]]
+[[Category:Logic in computer science]]
+[[Category:Logic programming]]
+[[Category:Knowledge representation]]
+[[Category:Logical calculi]]

Model category: Difference between revisions

Revision as of 21:51, 18 November 2013

Contents

Fluents and actions

Domain-independent axioms

Domain-dependent axioms

The event calculus as a logic program

Extensions and applications

Reasoning tools

See also

References

Navigation menu

Model category: Difference between revisions

Revision as of 21:51, 18 November 2013

Fluents and actions

Domain-independent axioms

Domain-dependent axioms

The event calculus as a logic program

Extensions and applications

Reasoning tools

See also

References

Navigation menu

Search