Event Calculus

I Introduction

In recent years, much attention has been given to the issue of representing temporal knowledge. Several systems, including those by Vilain [1], Allen [2], Kandrashina [3] and Malik and Binford [4] have been presented for modeling temporal information and reason­ ing in time, following earlier works by Bruce [5] and Kahn and Gorry [6]. In addition, extensive general models of time, including frame­ works for causality, belief and continuous change in quantities have been proposed by Allen [7] and McDermott [8].

Somewhat removed from this thrust, however, have been a number of efforts in "event recognition," including the works of Neu­ mann and Novak [9], Tsotsos [10], Nagel [11], Tsuji, Morizono and Kuroda [12] and Okada [13]. The representational models employed by such systems have been quite diverse, and naturally so, as physi­ cal events themselves span an entire range from simple state changes to complex interactions of subevents and alternate possibilities. The model presented here attempts to capture a good portion of this range in the complexity of physical events.

The motivation for this research originated largely in the Event Shape Diagrams of Walts [14] and the extensive treatment of time in Miller and Johnson-Laird's Language and Perception [15]. The presentation of Event Calculus in this paper is necessarily brief· a more detailed account of the model may be found in [16]. '

II GRAPHs and SYMBOLs

Processing of temporal information in the Event Calculus model revolves around the manipulation of data structures called "GRAPHs", which correspond to piecewise-constant partial functions mapping time into the elements of particular domains. This representation captures both the notion that we may not know the behavior of a quantity or condition over all time (thus, a partial b) ((BEGINNING NIL)(o FF)(3 TT)(6 FF)(10 TT)(12 NIL))

* Author's current address: Jet Propulsion Laboratory, M/S 168-514, California Institute of Technology, 4800 Oak Grove Drive, Pasadena, CA 91109.

·· This research was supported in part by the National Science Foundation under Grant No. NSF 81-17238.

Figure 1. a) Piecewise-constant partial function mapping time into boolean values; b) corresponding LISP representation (GRAPH).

A quantity or condition which does not vary in time is represented by a single value called a "SYMBOL", which is generally treated in the same manner as a GRAPH mapping all time to that value.

ill Functions Taking GRAPHs as Arguments

Given the GRAPH as a fundamental data entity, it is possible to create a class of functions, each of which takes a number of GRAPHs or SYMBOLs as arguments and returns a GRAPH or SYM­ BOL as its result (call this a "FUNCTION" ). One important res­ triction is placed on FUNCTIONs -- the resulting value at any point in time may be a function only of the values of its arguments taken at that same point in time. That is to say, a certain value at a cer­ tain time in the result may not be a function of a value at some other time in one of the arguments (this facility is reserved for OPERATORs, described below).

The Event Calculus model provides three modes for specifying an optional time argument in the application of a FUNCTION or related construct. Evaluation "at" or "just before" a point in time causes a SYMBOL to be returned, while evaluation "from" one point in time "to" a second point in time causes a GRAPH to be returned. The following examples illustrate this evaluation process, involving application of the "ADD" FUNCTION in conjunction with various arguments and time specifications.

1000

(ADD ((BEGINNING 100)(0 200)(10 300)) 500 JUSTBEFORE 10)

(ADD 200 300 FROM 3 TO 7)

((BEGINNING NIL)(3 500)(7 NIL))

(ADD ((BEGINNING NIL)(O 280)(10 140)(15 240)(20 NIL)) ((BEGINNING NIL)(5 200)(15 100)(25 NIL)))

((BEGINNING NIL)(5 480)(10 340)(20 NIL))

Note that the intervals from 10 to 15 and 15 to 20 are automaticallr joined in the result of the Jut example, u both intervals map to the value "340". When the option&! time argument is omitted, u in the Jut example, the time argument &t the next outer level is used: in this cue, a default of "FROM BEGINNING TO END".

IV CONDITIONALs, QUANTIFIERs and OPERATORs

In addition to FUNCTIONs, Event Calculus provides three related constructs, "CONDITIONALs", "QUANTIFIERs" and "OPERATORs". CONDITIONAL~ differ from FUNCTIONs in that one or more of their arguments mar remain unevaluated throughout the course or their application, dependent on the value o£ some other argument. This is similar to the operation or the "and" and "or" functions in LISP. CONDITIONALs are included primarilr Cor rea-­ sons or time-efficiencr in the evaluation of Event Calculus expres­ sions. QUANTIFIERs repeatedlr evaluate a given Event Calculus expression while binding a specified variable successivelr to each ele­ ment or a domain, accumulating a result in some manner. OPERA· TOR~ are releued from the "strict time mapping" restriction placed on FUNCTIONs, u described above, and thus the value at a particu­ lar time in the result or an OPERATOR mar be dependent on the values or its arguments at other times.

OPERATORs are the most interesting or these varieties in the context of event recognition, u ther provide a mechanism Cor expressing both cumulative properties or quantities and conditions, and interrelations or quantities and conditions in time. Following is a list describing a few or the OPERATORs provided br the imple­ mented Event Calculus interpreter. (Examples involving application the OPERATORs "STOP" and "NEXT" mar be found in Section V.)

DDT,IDT: Discrete approximations or differentiation and integra-­ tion with respect to time.

NEXT,PREVIOUS: Shift the values or a GRAPH over one time interval to the left (NEXT) or right (PREVIOUS).

SETPOINT: For each interval in a GRAPH, replace the value Cor that interval with the starting time point or that interval.

START,STOP: Search a boolean GRAPH Cor "FF" to "TT"

( "TT" to "FF" ) transitions. Return Cor each time interval the time or the Jut such transition, or "BEGINNING" i£ no such time exists.

EVER,ALWAYS: For each time interval in a boolean GRAPH, return "TT" i£ the value or the GRAPH hu ever (alwars) been "TT" between a specified starting time and the time o£ the interval in question. Otherwise, return "FF".

FLOOR,CEILING: Search a numerical GRAPH for minimum (maximum) values. Return Cor each time interval the accu­ mulated minimum (maximum) following a specified time.

V Describing Physical Events

In the implementation or the knowledge-hued srstem Cor event recognition, events are modeled u FUNCTIONs, defined br Event Calculus expressions o£ varying complexitr. The application is a "robot arm" context, with blocks-world trpe objects and robot "hands." One or the simpler events in this context is that o£ a hand holding an object. The definition or the FUNCTION "HOLD" is u follows (this is somewhat simplified-- see [16]). Variables begin with a pound sign.

(HOLD #A #B) ::=

"AND" is a CONDITIONAL: its second argument is not evaluated Cor anr time interval in which its first argument is "FF" ( "FF" is simply returned Cor such time intervals). "SURROUND", "DTOUCH" and "PART" are FUNCTIONs. In English, this definition specifies that hand #A is holding object #B iff hand #A's (two) fingers surround block #B, and each finger directly touches #B. Note that no OPERATORs are required in the definition of "HOLD", u it is possible to determine whether or not a hand is holding an object at a particular time using the values or other FUNCTIONs taken only at that same point in time.

A more complex event which does require the use or OPERA­ TORs is "GRASP", meaning "take hold or· in this context.

(GRASP #A #B) ::=

This definition is taken to mean that hand #A is in the process o£ gruping object #B iff hand #A is closing its fingers and it is also true that hand #A will be holding object #B at the end or its closing operation. The following example examines this definition in greater detail. {VIllual representations or the GRAPHs are added Cor clarity.)

Suppose that, Cor some particular hand #A and object #B, the result of evaluating "(CLOSEFINGERS #A)" is

((BEGINNING NIL)(O TT)(5 FF)(10 TT)(15 FF)(20 TT)(25 FF) (30 NIL)),

((BEGINNING NIL)(O FF)(l<l TT)(18 FF)(30 NIL)).

Application or the OPERATOR "STOP" to the result or "(CLOSEFINGERS #A)", then, generates the following GRAPH. 30 -1

((BEGINNING NIL)(O BEGINNING)(5 5)(15 15)(25 25)(30 NIL))

This GRAPH mapa time to time and apecifie1 Cor each interval the most recent time that the GRAPH Cor "(CLOSEFINGERS #A)" made a transition from "TT" to "FF" (i.e. hand #A stopped closing its fingers). A default value or "BEGINNING" is uaed over the interval from time 0 to time 5, u no 1uch transition hu yet occurred. When this GRAPH is pused to the OPERATOR "NEXT", the values are shifted over one time interval to the left, apecifying for each interval in time the next point in time at which hand #A will have atopped closing ita fingers.· The result of evaluating "(NEXT (STOP (CLOSEFINGERS #A)))" is thus

30- t

((BEGINNING NIL)(O 5)(5 15)(15 25)(30 NIL)).

· This is not entirely correct, u a fool-proof version of "GRASP" would need to check that the value for each point in time in this GRAPH is never less than the time itself.

Be£ore proceeding, it is necesa&ry to reconsider the three modes Cor specirying a time argument. The previous examples employing time specifications (Section ill) used only SYMBOLs in this capacity. When a GRAPH appears aa a time specification, this is interpreted as a request to evaluate over all time, substituting time specifications indicated by the GRAPH Cor actual intervals in time. In the case o£ "(HOLD #A #B AT (NEXT (STOP (CLOSEFINGERS #A))))" in the definition o£ "GRASP", evaluation in this manner produces the Collowing GRAPH.

((BEGINNING NIL)(O FF)(5 TT)(15 FF)(30 NIL))

For each interval in this GRAPH, the value indicated represents the result or evaluating "(HOLD #A #B)" at the point in time when, with respect to that particular interval, hand #A will next stop clos­ ing its fingen.

As a final step in the evaluation or "(GRASP #A #B)", the conjunction or the original "(CLOSEFINGERS #A)" GRAPH and the above GRAPH is taken, resulting in the Collowing.

((BEGINNING NIL)(O FF)(10 TT)(15 FF)(30 NIL))

Hand #A is seen to be grasping object #B £rom time 10 to time 15. This is because hand #A is closing its fingen over this interval, and it is true over the entire interval that hand #A will be holding object #B at the point in time in which it next stops closing its fingers. Over the intervals £rom time 0 to time 5 and £rom time 20 to time 25, hand #A is closing its fingen, but it is not true that it will be holding object #B at the end o£ this action. Likewise, £rom time 15 to time 18, hand #A is holding object #B, but no longer is it closing its fingen.

VI An Event Recognition Session

The representation scheme described above has been used to construct a knowledge-based system Cor recognising the occurrences or physical events and rorming a high-level description or changes in a scene given a relatively low·level description o£ those changes as input. The system consists or the Event Calculus expression inter­ preter, a knowledge base or defined FUNCTIONs Cor 28 events in the "robot arm" context, along with approximately 100 other "support­ ing" FUNCTIONs, and finally, a control mechanism which proceeds in a mixed bottom-up/top-down manner in identirying the occurrences or events. Events are organised in a hierarchical Cashion £rom those relating to positions and orientations or objects at the bottom to those concerning the rastening and unrastening or objects to other objects with a bolt, stacking and unstacking objects and so Corth at the top. It is envisioned that such a system could be used as one component in the construction or a "teachable robot," serving to codify the actions taking place in the demonstration or a given task.

The input to this system is aasumed to be provided by a com­ puter vision system which tracks three-dimensional objects in space, returning coordinates or these objects over time, plus a Cew other use­ Cui items auch aa contact between objects and support o£ one object by another. The example given below was run using a simulated data set or this sort, amounting to approximately 1200 lines or LISP­ coded input and specifying the low-level changes occurring over a fifteen second interval in a particular scene, with one second spacing between measurements. Figure 2 depicts the sequence analysed and includes excerpts from the actual input file Cor the session. "BOLT1", "HAND1", "PLATEC1" and "BLOCKC1", as indicated in Figure 2, are "constructions" containing several parts each, these parts corresponding to a simple geometrical shapes.

Figure 2. a) Sequence or actions used in the event recognition session; b) Excerpts from the input file Cor the session, indicating the position or one finger or the hand and contact between that finger and the shalt or the bolt.

The resultant description as produced by the event recognition system consists or the following.

(HAND1 IS STACKING BOLT1 ON BLOCKC1 FROM TIME 0 TO TIME 3)

(HAND1 IS STACKING BOLT1 ON PLATEC1 FROM TIME 0 TO TIME 3)

(HAND1 IS INSERTING BOLT1 INTO PLATEC1 FROM TIME 0 TO TIME 3)

(HAND1 IS UNGRASPING BOLT1 FROM TIME 3 TO TIME 4) (HAND1 IS PICKING BOLT1 UP FROM TIME 4 TO TIME 10)

(FINGERA1 IS ROTATING FROM TIME 5 TO TIME 6)

(FINGERB1 IS ROTATING FROM TIME 5 TO TIME 6)

(PALM1 IS ROTATING FROM TIME 5 TO TIME 6)

(HAND1 IS GRASPING BOLT1 FROM TIME 8 TO TIME 10)

(HAND1 IS TURNING BOLT1 FROM TIME 10 TO TIME 15)

(HAND1 IS FASTENING PLATEC1 TO BLOCKC1

USING BOLT1 FROM TIME 10 TO TIME 15)

(HAND1 IS HOLDING BOLT1 FROM TIME 15 TO TIME 16)

It should be noted that the goal of the knowledge-based system was not only to identify the events which had occurred in the changing scene, but also to provide a description or these changes in terms or the highest-level events, with lower-level events "peeking through" only where no higher-level events had occurred. This goal was achieved by a process of "suggestions and explanations," with lower­ level events "suggesting" the possible occurrences of related higher­ level events, and higher-level events "explaining" occurrences of lower-level events. In this manner, the "HOLD" event listed as occurring from time 15 to time 16 in the output of the above exam­ ple is the last remaining piece of an event originally identified as occurring from time 10 to time 16. The segment from time 10 to time 15 has been removed from the description following identification of the higher-level events "TURN" and "FASTEN" which have provided explanations for the "HOLD" event. AB no explanations for the "HOLD" event have been generated over the interval from time 15 to time 16, it remains in the final description covering this interval.

It may also be noted that some degree of seeming redundancy was left in the above description by the system in cases where one event was part or another event but not a necessary component in that event. For instance, it would not be necessary for "HAND1" to turn "BOLT1" in order to accomplish the fastening operation, as this could be aided by another hand turning the other objects.

Vll Concluding Remarks

The Event Calculus model is still not ironed out completely. Problems with edge effects in OPERATORs have not been handled wholly to satisfaction, and SYMBOLs cannot always be replaced by GRAPHs mapping all time to a single value. Nevertheless, the Event Calculus formalism provides a powerful tool for the manipulation of time-related information. It may be possible as well to extend the GRAPH structure in a simple manner to include variables as time coordinates. With such a scheme, a time reasoning system such as proposed by Vilain or Allen could be incorporated together with the model for maintaining the integrity of such GRAPHs and producing alternate GRAPH possibilities when no exact ordering can be deter­ mined, yet calculations are desired. Another approach would be to extend a conventional semantic network by this formalism, incor­ porating GRAPHs into the "aspect" mechanism of various attributes and including a suitable set of FUNCTIONs and OPERATORs for the manipulation of these GRAPHs.

Acknow le.dgementa

The author wishes to thank Dr. David L. Walts and the members of the Advanced Automation Research Group at the Coor­ dinated Science Laboratory for their comments and advice offered during the course of this research.