Temporal Event Conceptualization

1. Introduction

In this paper we study the problem of ~mporal Event Recog­ nition, ie . forming causal, conceptual descriptions of discrete, on­ interpreted stimuli to a system. This problem has been studied both directly and implicitly, by many researchers in Psychology [Miller&Johnson-Laird'73), Behavioral science [Newtson'73), and Ar­ tificial Intelligence [Schmidt ,Sridharan&Goodson'78) . In AI research the problems of goal based story understanding and plan recognition [Wilensky'83) and the work of !Tsuiji'77) on understanding cartoon films implicitly address this task. However, most of these systems are concerned with the specifics of the domain they seek to interpret and the management of temporal information is only peripherally ad­ dressed. in these systems.

Recent work by [McDermott'82) , [Allen'84) and others has con­ centrated on providing formal deductive representations for temporal knowledge and they have developed extensive general theories of time. [Borchardt'85) is one of the first attempts to bring these works to­ gether and the Event Calculus developed by him is directly related to the kinds of representations we try to develop in this paper. The work of !Thibadeau'86) is also similarly motivated though his work is more oriented towards simulating human performance in action perception.

Our intent is to develop a domain independent framework in which event conceptualization may be performed. The basic paradigm we consider is the following. The system is presented with a set of stimuli at discrete instants. The task is to form a conceptual description of abstract events occurring in these instants and to provide a causal interpretation of these stimuli.

The overall framework presented in this paper has been imple­ mented in an event recognihon program on a Symbolies 3670. The paper that follows is a description of the theory behind this system, which we call MUSE. The paper is or~anized as follows . Section 2. briefly discusses the temporal logics of [McDermott'82) and [Allen'84) and argues that while both of them have useful properties neither is completely adequate for the task at hand. Sections 3 to 5 then present an alternate hybrid representation and discuss its properties and de­ velop the basic structure of the event recognition system. Section 6 gives an example of the system working in the Blocks world.

A longer version of this paper [Kumar&Mukerjee'87) contains a more complete account of the motivations behind this work and the implementation details of our system. The reader is referred to that report for addition\'! information.

2. Representing Temporal Knowledge

Recent work on temporal reasoning has given rise to two basic symbolic models of time. In one approach, (for example, [McDer­ mott '82)) the basic unit of time is an atemporal entity called a &tate or an irut..nt. In the second approach [Allen'84)[Allen'85)[Ladkin'86) the basic unit is the interval, which represents a finite "chunk" on some

Temporal Event Conceptuali11ation

Krishna Kumar Amitabha Mukerjee

Department of Computer Science Texas A&M University College Station, TX 77840

time line. In the state based approach, the passage of time is repre­ sented using a partial ordering between states. Intervals of time are thus represented using sets of states in this approach. Intervals are first class entities in the second approach and here points are defined using intersections of intervals [Allen'85). The following discussions assume that the reader is familiar with the basi' e features of both these models. Space considerations preclude a detai ed analysis of the comparative merits of the two models. Below we outline briefly the motivations be­ hind our choice of representation. The reader is referred to the longer version of this paper for a detailed comparison.

We are primarily interested in representing temporal information about e11enu. In state based systems events are defined indirectly as facts that are true over sets of consecutive states. Thus temporal rela­ tions between events can be determined by examining the respective set of states. In interval based systems on the other haned, events can be directly associated with intervals and the temporal relationships between events can be directlr. expre1sed by the interval relationships (say tor example, of (Allen'84J). Thus intervals are powerful source of temporal abstraction in representing information about events. How­ ever, intervals are awkward to use for global or situational information. If, for instance, we wish to know what facts are true at a particular point in time, the interval notation is awkward to Ule since such in­ formation has to be derived by pairwise comparision of events using binary relations between them. In typical event recognition problems, the input information is usually global and consists of d~seriptions that hold at varoius points in time. Thus a direct use of the interval logic is inconvenient .

Another major problem with the interval notation is that intervals require both a starting point and ending point to be completely de­ fined. All the temporal relationships of (Allen'84) require that the two intervals be completely defined. This means that temporal relations between incomplete intervals cannot be expressed using. this notation. As we show in the longer paper none of the relationships can be au­ tomatically derived until a time when at least one of the events has terminated. This means that we cannot build an incremental temporal reasoner that deals with ongoing events using the interval Iogie.

In this paper we show that the above problems can be solved if we re-interpret the interval notation using a state based approach. In par­ ticular we show how these relationships can be automatically derived using strictly local deductions from situational information. We thus end up with a hybrid representation which uses states to encode global information and constructs intervals implicitly by deriving interval re­ lationships between facts in the states. We thus gain the advantages of the "world centered" state space approach and the "event centered" interval approach.

3. Basic Definitions

In our representation factual world knowledge is represented by two sets of propositions P,, and Pd . P, is a set of primitive propo&itioM from which all inputs to the system are drawn. Pd is a set of derived propo·itioM such that Pd n P, = A (the null set). Intuitively, the task of temporal event conceptuali1ation involves defining a mapping between the two sets such that the elements of P. may be re-expressed in terms of those in P4 · We define the set 'P = P. U P4 ·

Time is represented by a linearly ordered set of states S. A func­ tion ll(<p,<T)which ranges over the set {true false} determines the truth values of a proposition <p E 'P at a specific instant .,. E S . The set of states in S is utilized to provide a &arne of reference for describing events in a domain. We thus place a restriction on this set that it be of a sufficiently high "resolution" ie. For all <p E 'P, if <p is true over a set of instants {<T1 ... .,..} and if it becomes false at D'lo+ 1 then «T·+t E S . Similarly, if <p is false over a set { «T1 ... .,..} and becomes true at ITJo +1, then «THt E S .The above restriction places a minimal bound on the resolution of the set S required to perform event conceptualization aing our representation.

An ewent is a tuple (cp,'T)where cp E 'P and .,. C S such that U(cp, IT)is true for all IT E 1'. The set .,. is restricted to contain only consecutive elements of S, ie., if IT; E 1'1 then either ITi+t E .,., or "'l. (/. .,. br all lc > i An event is defined u a primitive event if cp E P, and a derived event if cp E P4 . An event is said start at a particular instant if the corresponding proposition becomes true at that instant . Similarly it Mid to terminate at an instant if the proposition becomes &.J.se at that inllant.

The set .,. is called the eztent of the event. We will also refer to this set !Ill the duration 9_f th~ rvent or the int<"rval usociated with the event. The events ( cp, 1\ J and l cp, 1'2) are considered distinct if Ti i= f\.

4. Deriving Temporal Assertions

Syntactically, a temporal assertion is a logical sentence of the brm 'Pt(r) 'P2,'Pto'P2 E 'P,and,r"E { = ><in mio oi C II s si d dl sa.sb ss .Pl In the enumerated relation·hips above the first thirteen are identical to Allen'· relationships. The remaining bur relatione, required to rep­ resent temporal relation1hips between incomplete events, are one of the exteneions euggeeted by our work . This is discuned further be­ low. We deftne the set N ee the set of all ponible relations of this fOrm tor all cp E 'P and the set N* 111 the cloeure of N under the logical opt!r&tione V and /\.

Although the temporal ueertion· in our representation are syn­ tactically limilar to Allen'· the interpretation is quite different. In Alkn's terminology, the primitives define relations between two com· pletely specified intervale. In our terminology the primitives are used to make statements about what is known about the temporal rela­ tionehipa between two ewenu at any inetant IT E S . They may thus be viewed as propo·itioru that hold at certain instants. The sentence characterising the relationship between two events change within the duration of the events. This 11 discussed below.

Due to dynamic changes in the world being modelled, at any instant in S, eome subset of 'P may transition &om l&lse to true thue creating events and eome other subset may transition &om true to &.l.se thus terrninatinll eome events. We use the three predicates Start., End.,Cmd to indicate the status of any event at an instant. Given an event 'I= (cp,'T) and any instant IT; E S we define

In this paper we use the literal Hold. to represent the fact that a propoeitton is true at certain instant.

In this situation, at any given instant, all the propositions which are true will correspond to events whose beginnings are known. How­ ever, this may not, in general, be true tor their endings. All of Allen's relationships require that at least one of the events have terminated. In order to express the temporal relationships between incomplete events we introduce bur more relationships to this set. Three of these are shown in figure 1.

X starts before (sb) Y I

A fOurth relationship q, (null) can be added to the set to expresa the relalionship between an event and a (fictitious) event whose propo­ llition happens to be false at that !natant. Alternatively, we may view this usertton 111 expressing the relationship between an event and an­ other, whose starting point is unknown.

With this expanded set of relationships, at any instant IT E S, there is a unique temporal usertion relating 1!11e"!! pair of events cor­ responding to the propositions in 'P. Each of these temporal assertions is computed by a strictly local deduction, depending on the truth value oC the proposition at that inatant and the instant immediately preced­ ing it. We may express theae deductions in terms of the inference rules below.

The simplest cases are derived first

The relationships ·a ·b, and u are only temporary relationships that will chanl(e when either of the two events terminate. When that happens the rdationship is completely determined. Some of the rules that guide this transition are given below.

The remaining assertions can be derived similarly. The above rules can be concisely summarized in the state transition dia11rams in

Conceptually, we may imagine that the state transition diagrams represent finite state automata that monitor the logical relationships between each pair of propositions (cp1 ,cp2 ) E 'P. At each instant, each possible logical relationship is evaluated and if any of them evaluates to true then the arc of the corresponding transition graph is traversed and the node that is reached represents the current assertion that can be made !!bout the temporal relationship between the two events corresponding to the propositions.

We define the logical prerequisite L of an assertion to be the label oC the arc that would have to be traversed in Qrder to Jeach the node representing that assertion. This concept will be use to define the notion of the scope of an assertion.

The ·cope of a temporal assertion linking two events (cp1 , rt) and (cp2 ,r2 ) is the set

and L is the logical prerequisite of the assertion.

The scope oC a conjunction of temporal assertions is the smallest complete interval that includes every point in intersection aet of the scopes of the assertions. The smallest complete interval that includes the points u;,<T~ E S,i < lc is the aet {uj :<Tj E Sandi ::; j ::; lc}. The scope of a dlsjunction of assertions is the union ~-d!eir scope.s.

The definition of the scope of tecmporal assertions is a feature that distin~uishes our interpretation of the temporal relationships from Allen s. Tn our representation, a temporal assertion between two events remains valid only as long as at least one of the events is active (ie. the corresponding proposition is true) . For example, an assertion 'It (m)'l2 will become active if tor some instant u, 'It ends and '12 starts at u. The 9cope of this assertion will include <T and all the following instants at which 112 is active. Once 112 ends, however, this assertion no longer holds.

6. Derived Events

We view temporal event conceptualization as a process of tempo­ ral abstraction. This involves aggregating a set of events that occur in a certain sequence into a single abstract event. Such abstract events are called derived events in our representation. These are events whose occurrences are totally constrained by the occurrences of other events. The temporal assertions of the previous section aefine the allowable temporal constraints between events.

Formally, we represent a derived event by a statement of the form

where A and 1/J are formulas that may contain quantified variables 1 such that some ground instance of A belongs to N" and some ground instance of 1/J belongs to Pd. Variables quantified over the entire ex­ pression are prefixed with a "?" . The previous definition of a temporal assertion as a proposition allows us to evaluate the truth value of A at any instant .

The extent T of the derived event is defined as being equal to the scope of the constraining assertion A .

The final notion that needs to be defined is the idea of 1emporal Semuntic1 for events. In deriving abstract events as shown above, we must consider not only how they are conceptualized, but also the points of time at which they are said to be occurring. So far, it has been implicitly assumed that the extent of an event is also the period of time for which the event occurs. While this holds true for primitive events, this definition is too restrictive for derived events. In many cases, simply assuming that an event occurs when the corresponding proposition becomes true and ends when the proposition becomes false leads to descriptions of events that are rather counter-intuitive. Let us consider some examples below.

Consider an event Going-from-College-Stution-to-Au·tin. The event itself is not realized until the agent has reached Austin, and yet, once it has reached Austin, the agent is no longer going from College Station to Austin. If we were to use the eztent to report the period of tim~ at which the event occurred then the event would be aetivated at the time the agent reached Austin and would end when he was no longer at Austin. This is certainly not the period for which the Agent was going from College Station to Austin! For this event we would like to use the fact that the Agent reached Austin as confirmation of the fact that it was going to Austin but would like to adjust the set of instants at which the event was presumed to occur to include only those points at which the agent was on the road from College Station to Austin.

Another case that is possible is one of Instantaneous actions. Con­ sider. !Or example the action of droppin111 a ball. We may say that someone drops a ball if he is initially holding the ball and then he opens his hand, thus releasing the ball. If we were to represent this situation using a derived event that was constrained by the events "holding" and "opening" then, the "dropping" action would, by the above scope mles, imply that the ball is being dropped at all instants that the hand remains open. However, this is not the way we perceive the dropping action. Effectively, the agent is said to drop the ball only at the instant when the hand opens.

It can be seen from the above examples that in practice the map­ pin!! to intuitive descriptions can be extremely complex and the simple not10n of extent cannot account for many types of events. Thus, we need additional mechanisms that will allow us to make these distinc­ tions. The idea of associating a descriptor with an event that will allow the computation of the period !Or which the event is active is our ap­ proach to providing a partial solution to this problem. We do not claim that this technique can account for all possible situations, but the methods outlined below are quite powerful and provide a means for "customizing" the temporal semantics of an event.

Suppose we have a function I>( 'I), and 'I= (cp, T) is an event. For any event, p returns a unique set of instants E> C S associated with the event as defined below

fl; I A is an abbreviation for "every f1; such that '1i is an event whose corresponding proposition is a subformula of A" .

For a derived event the set E> will, by the above definition, contains every instant from the starting point of the earliest primitive event that was involved in an assertion constraining that event to the termination point of the event. In effect this set maybe thought of as a universal set of all the instants which may have some relationship to this event.

For primitive events e is the same as the extent of the event .

We can now define the Action 0<-llnition set a of an event to be those instants for which the action defined by the event is said to be performed. In specifying the temporal semantics of an event we will be specifying the action definition set of the event. Let us consider some examples.

The simplest case, where the action definition set is the same M the extent may be specified by a = T . This defines the semantics of primitive events and any derived event !Or which it is appropri­ ate. Such an event is said to have Durationul semantics. The default semantics of all events in our representation is durational.

The second type of semantics, called Ab1traction semantics is ex­ tremely useful in describing events which are goals or form the ratio­ nale for performing some set of lower level events. The action defi­ nition ad includes the instant when the earliest event leading to it is activated and ends at the instant the event itself was ·started (ie. the goal was achieved). Examples of this type include the earlier event of going from College Station to Austin. We specify this type of event by a = 9 \ T, \ being the set difl'.-rence operation.

In~tuntoneoUI semantics may be defined by a = min(T) ie. the action is defined at the first instant of the extent.

The notion of defining event semantics in this way is thus a very useful one because it allows us a certain flexibility in reportin111 the occurrence of events. We have only scratched the surface of a complex problem however, and much work needs to be done in formalizing and generaliaing this principle to handle much more complex cases.

With the above framework, we can now take up a concrete ex­ ample of an event recognition system. This is considered in the next section.

6 An Event Recognition Example

In this section, we describe briefly, the basic premises behind MUSE as an event recognition system and provide some concrete ex­ amples of the ideas discussed in the previous sections. Due to space restrictions the example discussed is extremely simple. Specific imple­ mentation details can be found in the longer version of the paper. [J

MUSE takes 1111 its input low level propositional descriptions of a hypothetical ecene. In the blocks world example which will be consid­ ered here, the scene consists of a number of blocks on a table and a set of agents (hands) which are performing some actions in this world. The task given to MUSE is to provide a high level description of the · actions of the agents. The input is provided in a series of snapshots of the world at various instants. As an example consider the sequence of situational descriptions in Fig 3 that are presented to MUSE.

Each of these instantaneous descriptions naturally map on to the states in our model. The propositional descriptors primarily describe positions and motions of the agents and the blocks. Thus we have de­ ecriptions like Ontable(A) , On(B,A) , Move-right(Hand) ·· etc. Our premises here are somewhat similar to [MillerkJohnson-Laird'76] though at a slightly higher level ci abstraction in the primitives as­ sumed.

MUSE takes this set ci llituational descriptions and produces the higher level description of Fig 4.

High level descriptions are represented by derived events which are con!lrained to occur when certain sequences of low levd events occur. They include Grasp, Pick-up, Move-holding, Puton, etc. Thus an event like Grasp would be described as follows

• ··> (GRASP HAND A) at INST_2
• ··> (PICKUP HAND A) at INST_3
• ··> (MOVEHOLDING HAND A) started at INST_3
• ··> (MOVEHOLDING HAND A) ended at INST_4

··> (PUTON HAND A B) from INST 2 to INST Figure 4. - - Grasp(?x ?y) I= (Move(?x) (m) Surround(?x ?y)) 1\ (Surround(?x ?y) (sb) Closed(?x))

Here ?x ?y are variables that may be instantiated by the Hand und some Block in a specific case. This definition compactly dt"fines the fact that the hand may b· presumed to grasp the block if a motion of the hand ends with the hand surrounding the block and consequently the hand doses. Besides defining the action itself the scope and extent of the action may be determined from the above definition using the scope of the assertion on the RHS . This may be graphically described as shown below.

In figure 5, the thin boxes represent assertions and the points at which they remain valid. Since the Grtup event is defined as a conjunction of temporal assertions, it is activated when both assertions are activated, ie. at t, . The scope of the (m) assertion is the same as ~he exte~t of the surround event . The scope of the (sb) assertion is the mtersechon of the scopes of the Surround and Clo·ed events, ie, when f'ither the Surround or Clo·ed events ends the assertion becomes false and the relationship between the two events will change according t~ the rules and transition diagrams of section 3. Thus the extent of the Grtup event is the intersection of the scopes of the two assertions and this ensures that the hand is seen to be grasping the block as long as both the Surround and the Clo·ed events are active.

Presumably, if the hand is no longer surrounding the block then the block has slipped through the hand Md if it is no longer dosed then the hand may have released the block. This may be represented as

and

Thus the representation is a very expressive Md compact notation for describing fairly subtle distinctions between situations that may occur.

Temporal semantics are needed to correctly report the occurrences of the events. For example, the Puton event is described using

Puton will become tme only when the On predicate becomes true. But the action definition of Puton is the period during which the block was bein~ put on the other block. We therefore attribute Abstraction semanttcs to the Puton event which means that the set ar for this event will include the instant at which the earliest primitive event that triggered any event participating in the assertion above ie. the set {lnsL2 lnsL3 lnsL4} . Even though the Puton predicate will continue to be true for as long as the On predicate is true, the action definition set will include only these instants which is the correct interpretation.

Similarly in the above example, Pick-up is assigned Instanta­ neous semantics and Move-holding is assigned Durational seman­ tics. Pick-up is defined as

The definition for Move-holding is also similar.

7. Results & Discussion

The representation language for events is a subset of the first order predicate calculus, which is a language with known expressive adequacy [Moore'82]. Situational descriptions are naturally expressed in u .. state based representation. Since temporal reasoning is per­ formed using an interval based logic, efficient temporal abstraction is also facilitated. Moreover, since we have integrated state based and interval based representations, we can use the advantages of both. The major ad vantage of interval based logic is that it can handle imprecise temporal information elegantly. Given a set of statements about the temporal relationship of events, the inference procedures of [Ailen'83J or [Villain '82] can be used derive some implicit information in these statements. Although we do not use such procedures in our system, our derived events are created using precisely the assertions of the form that the interval logic uses. So, in deriving higher level descriptions, MUSE could very well take as its input expressions generated by a system such as Allen's. Unlike these systems however, MUSE has the additional capability of automatically deriving the temporal informa­ tion from purely situational descriptions. The syst~m was specifically designed to operate in an on-line environment and it can handle on­ going or partially defined events.

There are many areas where temporal reasoning needs to be per­ formed even before the derived events are completed. For example, in system breakdown evaluation, the events leading up to the break­ down have already started much before the actual breakdown occurs. In analysing opponent strategies, it is necessary to analyse events as they happen. In fact all temporal reasoning about the present time involves abstracting some high-level events which are yet to be com­ pleted. By using the features of state based temporal logic systems, our representation scheme can deal with situations involving incom­ plete events, while retaining the abstraction facilities of the interval hased systems. Thus we feel that this work adresses a significant issue in temporal knowledge representation and t<'mporal reasoning.

8. Bibliography

(AIIen'84 ] Allen,J. "Towards a General Model of Action and Time", Artificial Intelligence, 23, 2, July 1984.

(Allen'85J Allen,J . and Hayes, P. " A Common Sense Theory of Time", Proc. of the Ninth International Joint Conference on Artificial Intelligence, Los Angeles, Ca, 1985.

[Borchardt'85] Borchardt, G. "Event Calculus", Proc. of the Ninth International Joint Conference on Artificial Intellgence, Los Angeles, Ca, 1985.

[Drachman'83J Brachman,R." What IS-A is and isn't:An analysis of the 1axonomic Links in a Semantic Network", IEEE Computer, Special !Hue on Knowledge Repre&entation, September, 1983.

[Kumar&Mukerjee'87] Kumar, K. and Mukerjee, A. ''Temporal Event Conceptualization", Technical Report TAMU-DCS-87-003, De­ partment of Computer Science, Texas A&M University, Tx, 1987.

[Ladner'86J Ladner,P. ''Time Representation: A Taxonomy of In­ terval Relations", Proceeding· of the AAAI-86., Philadelphia,1986.

[McDermott'82] McDermott ,D. "A Temporal Logic for Reasoning About Processes and Plans", Cognitive Science 6, 1982.

[Miller&Johnson-Laird'75) Miller,G.A, and .lohnson-Laird,P.N " Language and Perception", Harvard University Press, Ma, 1975

(Moore'82] Moore,R.C " The Role of Logic in Knowledge Rep­ resentation and Common Sense Reasoning" , Proc. of the AAAI-811 Pittsburgh, Pa 1982, pp (428-433). '

(Newtson'73] Newtson,D. "Attribution and the unit of perception of behaviour", Journal of Per·onality and Social P·ychology, 28, 1973.

(Schmidt,Sridharan&Goodson '78] Schmidt, C., Sridharan,N .S, Goodson,J .L, " The plan recognition problem : An intersection of Psychology and Artificial Intelligence" Artificial Intelligence, 11, 1978.

[Thibadeau'86J Thibadeau, R. "Artificial Perception of Actions", Cognitive Science (10), 1986. 117-149

[Tsuiji'77] Tsuiji,S " Understanding a simple Cartoon Film by a Computer Vision System" , in Proc. of the Fifth international Joint Conference on Artificial Intelligence , Cambridge, Ma, 1977.

(Villain'82] Villain,M." A system for reasoning about time", Proc. of AAAI-811, Pittsburgh, Pa, 1982 . pp (832-843) .

[Wilensky'83J Wilensky,R. "Planning and Understanding", Addison­ Wesley Publications, Advanced Book Program, Reading, Mass. 1983