Time Structures for AI

I Introduction

Temporal logic has been studied by temporal logicians for a long time. The classical approach to temporal logic takes instants and relation of temporal precedence as primitive. Recently. interest has been shown in event­ based temporal logics (e.g. [18][12][8][9]).

On the other hand. temporal reasoning is becoming more and more important in AI. It is diflicult to reason with time but not to talk about the time structures that we are using. Two of the best known models of ~ime are Allen & Hayes" [4] and McDermott's [10]. Allen & Hayes' logic is based on intervals (we shall argue that they are "events") and McDermott's logic is based on points. Both of them have been demonstrated to be useful for AI (e.g. [1][2][3][10][11][6]). This gives us motivation to link them to formal temporal logics.

Event-based logic arises because of the intuition that mental experience is based on events rather than instances - even the shortest event (like switching the light from on to off) has duration. In this paper. we start with Allen & Hayes' logic. which we shall refer to as A). because it takes interval,s (events) as primitives. Then we shall P!e&ent a new time structure. which we shall refer to as E*. which is equivalent to A. and relate it with interval-based and point-based structures.

By giving Allen & Hayes' logic a new axiomatization. we hope to have better understanding and control of our systems which are built on it. We are not satisfied with Allen & Hayes' axiomatization because their axioms are not primitive enough for extensions. For example one might want to ~emove linearity in order to talk about disjunctive sets of. mterva~ ~ for applications like planning under uncertamty ( whtch mcludes the issue of branching nme in [10]. see [1.5]). But it is diflicult to see which axiom in Allen & Hayes' axiom set entails linearity. Limited by

n Allen & Hayea' logic, A

In this section. we shall summarize Allen's Temporal Logic. This summary is based on the logic presented in Allen and Hayes' paper [4].

In [1][2] Allen presents. a logic in which there are 13 possible primitive relations between any two intervals . These temporal relations are before(<). meet(m). overlap(o). start(s). during(d). finish(f) equal(-) and their inverse (see [1][2] for their detail definition). In [4]. Allen and Hayes show that all the other 12 relations can be defined in terms of Meet. and provide an axiomatization of Meet. Intuitively. interval A meets interval B means B starts immediately after A ends - A and B have no common· subintervals and there is no gap between them. We shall call their interval structure A:

A- <E. Meet>

where E is a nonempty set of intervals and Meet is an operator which takes two intervals (of E) as its arguments. There are five axioms which describe the structure A : .

(M1) (V i,j) ((3 k) (i Meet k & j Meet k) -> (V 1) (i Meet 1 <-> j Meet 1))

(M2) (V i.j) ((3 k) (k Meet i & k Meet j) -> (V 1) (1 Meet i <-> 1 Meet j))

(M3) (V i.j.k.l) (i Meet j & k Meet 1) -> (1) (i Meet 1); XOR

(2) (3 m) (i Meet m & m Meet 1): XOR

(3) (3 n) (k Meet n & n Meet j)

(M4) (V i) (3 j. k) (j Meet i & i Meet k)

(M.5) (V i.j) (i Meet j ->

(3 (i+j)) (3 a.b) (a Meet i & i Meet j &

j Meet b & a Meet (i+j) & (i+j) Meet b))

Axioms (M1) and (M2) state that every interval has a unique start and end point. The meaning of (M3) is a little bit vague. It defines all the possible relations between any two meeting places. (M4) makes every interval have at least one neighbouring interval preceding it, and another succeeding it. Interval i+j in (M.5) is only defined if i Meets j. i+j is the interval which contains exactly both intervals i and j. (M.5) is an axiom on E. which states that for any two neighbouring intervals. one can find an interval in E which contains both of them.

This interval will also share the starting point of the first interval. and the ending point of the second interval.

To satisfy our intuition of time, we want to prove the following two lemmas under A:

Lemma (i) states that Meet is irreflexive. which satisfies our intuition that no interval can meet itself. Lemma (ii) states that if e1 Meet e2. then there is no interval between e1 and e2. (This satisfies our intuition of Meet). Proof of these lemmas can be found in [15].

m E*, an event structure

An interval can be seen as a "chunk of time". Interval-based logic takes intervals as primitive temporal · items. In event-based logic. events are taken as primitive. Intuitively. more than one event can occur in one interval. But if two intervals start and end at the same time, they are the same interval. Based on this. we argue that A is more an event-based logic rather than an interval-based one. (Formal analysis of the distinction between interval and event structures will be postponed after our discussion on points. when we have a better understanding of our logic). This can be seen by the fact that A allows the situation in figure 1:

Interval P

Interval Q

Interval R

Interval S

Figure 1 - A possible situation in A

In figure 1 both intervals Q and R are met by P and meet S. But A does not insist Q and R be the same element in its domain E.

In this section. we shall present an event-based logic which is equivalent to A. Since events occupy time intervals. properties of intervals and events are very alike. Therefore. most of the results in this section applies to both intervals and events. Let us start with the event structure E. which is used in [18]. [12]. [8]. [9] and [16]. and see what extra characteristics E must have (if any) to make it equivalent to A. E is defined as:

where E is a nonempty set of events, < and 0 being binary operators on E's elements. < is 'J!receding" and 0 is "overlapping". Consider the axioms in .h :

(El) and (E2) together state that < is a strict partial order. (E3) and (E4) state that 0 is symmetric and reflexive. (E5) states that if e1 < e2 then they are separate events. (E6) relates < and 0. (E7) states linearity of time. Properties of E have been thoroughly studied in [18][12][8][9].

Within E. we can define Meet:

We now set out to find the extension of E. which we call E*. which is equivalent to A. A little reflection should convince the reader that (E1) to (E7) do not allow us to derive (M4) in A. which states that there are no first and last events. and every event has neighbouring events on both sides of it. To obtain (M4) we need two additional axioms:

(E8) states that there is no first event. and (E9) states that there is no last event in E. In addition. they state that for each event. there are two events adjacent to it. one on each side.

To help us in our discussion that follows. we shall define the notion of subevents and equival.ena here. We define x in y. "x is a subevent of y". as:

As one might expect. in is reflexive and transitive (see proof in [15]). Following our definition of in, we have:

which states that if x is a subevent of y. then x overlaps y. (This can be proved trivially: by definition. any z such that z 0 x is also such that z 0 y. x 0 x. and therefore x 0 y.)

We define equivalence (::) as follows:

where e1 and e2 are elements in E. In an event logic. e1 is equivalent to e2 means intuitively that they "occupy the same time". In an interval structure. that means they are the same element in the domain of the structure. This will be elaborated later.

In order to obtain (M1) and (M2) in A. we need to be able to talk about intenection of events [15]. Let us follow Allen and Hayes' notation by using e - xl~ for "e is the intersection of x and y". We can define in b*:

If x 0 y is false. then xly is undefined. Intuitively. the intersection of two events is defined as the longest (in terms of its duration) event which takes place inside both of them. We find that Allen & Hayes' model of time has the following underlying feature:

(E10) is an axiom in E. It states that whenever x and y are in E. then if x 0 y their intersection is in E. After introduction of (E10). we can derive (E6) from (E2), (E5), (E7) and (E10), and therefore (E6) can be discarded [15].

To obtain (M3) and (M5), we need to be able to talk about both intersection and union. We define "e is the union of x and y" (e - xUy) as follow [note 1]:

Allen & Hayes' logic implies that given any two intervals, their union always exists. The additional axiom that we need for obtaining (M3) is:

(Ell) (V x.y E E)(xUy E E)

UNION

which is again a restriction on E. From the definition of Union, we can prove:

Le1711714 ( 2)

Lemma (2) states that if event z is before (after) the union of events x and y. then z is before (afte~ both x and y. We can prove the following results in E :

Le1711714 ( 3)

(V x.y)(x 0 y -> (V z)((z<x V z<y) <-> z<xly)))

(V x.y)(x 0 y -> (V z)((x<z V y<z) <-> xly<z)))

which states that if x overlaps y. then any event z which is before (after) x or y must be before (after) this intersection.

Le1711714 ( 4)

(V i.j)((3 k)(i < k & k < j) ->

(3 l)(i Meet 1 & 1 Meet j))

where Meet is defined as above. Lemma (4) states that if there exists an event which is between i and j. where i < j, then there exists an event which meets j and is met by i. We can further prove lemma (5), which satisfies our intuition that if events e1 and e2 both satisfy the definition of xUy, then they are equivalent.

Le1711714 ( 5) e1·xUy & e2-xUy -> e1 = e2

With the help of these lemmas. we can prove the following theorem:

Theorem 1:

(Mt) to (M5) of A can be derived from a.xioDUI (Et) to (Ell) in E*.

On the other hand. we can define < and 0 in A as follows:

e1 < e2 <-> 44 e1 Meet e2 V

1 (3 e)(e1 Meet e & e Meet e2)

e1 0 e2 <-> 441 .., (e1<e2) & .., (e2<el)

Under these definitions. we can prove Theorem ll:

Theorem D:

(Et) to (EU) of E* can be derived from axioDUI <Mt> to oo> in A.

The proof of these lemmas and theorems are quite lengthy and therefore will not be presented here (see [15]).

IV T, the equivalent Point Structure

As pointed out in [16]. any attempt to model time with an interval-based model must show how the concept of points can be formulated. Similarly. we must show how the concept of interVals can be constructed in a point­ based model. Therefore it is not only interesting. but important. to see how a point structure can be constructed from (and used to construct) the event structure E*. In this section. we shall explore what such a point-based structure should look like.

We shall follow Kamp [9] and Turner [16] and define a point i as the maximal set of overlapping events which satisfies the following properties:

1. for all e1 and e2 in i. e1 0 e2
2. for all el in the set E - i, there exists e2 in i such that .., e1 0 e2

Now we can define:

as a point structure where T is a nonempty set of points (which are primitives in this time structure) and E; is a binary wrator (precedence) on T's elements. In order to match ,h·, T should have the following axioms:

where tl < t2 is defined as tl E; t2 & .., t2 E; tl. In T. we can define (p.q) as an htterval. which is a convex set of points bounded by the pair of points p and q :

(p.q) <-> 44 { t E T I p < t & t E; q } Under this definition! (p.q) has open begins and closed ends. (One can also define intervals in T which have closed begins and open ends). Since (p.q) is a convex set, we have :

We can now define an .interval structure in T:

where I · { (p.q) I p E T & q E T & p<q }. In INTCT). < and 0 are defined as follows:

By: defining INT<T) in this way. we can prove that INT(T) has all the properties of INT(E*) [15]. We can also prove that the p<1int structure defined by E" (which we shall call POINT(E")) has all the properties of T. The proof of strict linear order of a point structure constructed from E has been given by [8][9] (and abstracted in [16]). The only U!!£roved property is (P5), which follows (E8) and (E9) of .h* trivially.

When points are taken as primitive temporal items. one question that we often ask is whether time is Diacrete or Denae. Intuitively, a point structure has dense property if . given any two points. there exists a third point which lies between them. If a point-structure is discrete, we can name the neighbours of any given point (when they exist). When intervals are taken as primitives. the choice between discrete and dense disappears. It is replaced by the choice between Atomicity or Endlea De8cent [5]. An atomic interval is defined as an interval which cannot be decomposed. E* has the property of atomicity if we add the following axiom to it:

(E12) (V x)(3 y)(y in x & (V z)(z in y -> z = y))

An interval structure has the property of Endless Descent if every interval has at least one subinterval which is not the same as itself. E* has Endless Descent if we add the following axiom to it:

In our definition of intervals (using (p,q)), atomic intervals exist in INT(T) only if T is discrete - when q is the point that is following p. (p.q) is an atomic interval. If T is dense, there are infinite number of points between any two distinct points p and q. Therefore any interval (p,q) can be decomposed.

It must be pointed out that it is also possible to define for a dense point structure an interval structure which has the atomicity property. This can be done by defining intervals as "any convex set of points" instead of our definition above. Then for any point q, (q) is an atomic interval. Notice that (q) cannot be represented by any (p.q) in a dense time model under our definition.

In [4], Allen and Hayes suggest different ways to capture the concept of "points" in their interval-based logic. To capture the concep,_t of points in discrete point-based models. they define MOMENTs in terms of atomic intervals. To satisfy dense (which they call continuous) point-based models. they define NESTs, which have the form BEGIN(I) or END(I) for some interval I. Basically. if I, J are intervals where I Meets J, then BEGIN(J) is the set of all intervals X such that

1. X Meets J: or
2. I Meets X: or
3. X 0 I & X 0 J

(where 0 is defined in terms of Meet as shown in [4]). Allen & Hayes argue that under this definition, NESTs have the desired feature of having END(I) - BEGIN(J) for all intervals I and J such that I Meets J. NESTs also have the feature of strict linear ordering. In fact it has all the properties of T.

V Relation between Event and Interval Structurea

Intuitively, intervals are "chunks of time" in which events can occur. If intervals A and B start and end at the same time, they are the same interval. On the other hand, if events X and Y start and end at the same time, they need not be the same event. From E* we can define an interval structure

by making I the set (with unique elements) of all equivalent events:

where e. e' are events in E. In INT(E*). we can define:

Meet can be defined in terms of < and 0 as discussed above.

As we have said before, all the axioms in E* apply to intervals. For example < is irreftexive, asymmetric and transitive. intersections and unions exist, etc. The only difference between an interval structure and an event structure lies in the definition of ·-·. We define e1 - e2 in E* if e1 and e2 are the same element of E. Similarly i1 - i2 in INT(E*) if i1 and i2 are the same element of I.

In the event structure E*, el-e2 implies e1:=e2. but not the converse. If we define equivalence in INT<E*) as:

then we shall have :

[e1] - [e2] <-> [el] = [e2]

which satisfies our above mentioned intuition (see proof in [15]).

In an interval structure, there exists a unique interval which satisfies the definition of xUy for all intervals x and y. This can be seen by comparing lemma (5) and the definition of equivalence above. This result also satisfies our intuition.

INT(T) is an interval structure if we define that the elements in its domain are unique. If we consider figure 1 above, we can see why we argue that A is an event structure more than an interval structure. In figure 1. we have

P Meet Q & P Meet R & Q Meet S & R Meet S But A does not insist that Q and R be the same "interval" (Allen & Hayes do not explicitly talk about the domain of their structure).

However. it is arguable that Allen & Koomen [1] use an interval-based logic for planning. There if proposition P holds in both intervals T1 and T2. then if T1 and T2 are not before or after one another, they must be the same interval.

VI lntervala Ts Points in Temporal Reasoning

Whether points, events or intervals are primitive time entities is an ontological qu~ion. But since, as we have shown above, that they can be constructed from one another, point-based, event-based and interval-based structures should be able to represent similar knowledge.

We do not agree with the argument that interval-based logics are better than point-based logics because the "dividing instant" puzzle exists in the 1atter. One instance of this puzzle is:

The light is switched from on to off. Exactly what happened at the intermediate instant between the two successive states of on and off?

Some argue that in a dense point structure. we either have the light both on and off (which is contradictory) or the existence of some time where the light is neither on nor off (which violates the Law of Excluded Middle) (e.g. [7]). In an interval structure. there is no such problem because all we need to say is: interval ON meets interval OFF. where the light is on in ON and it is off in OFF. Van Benthem has made it clear that "one only has this problem if one insists on having it!" [.5] (p . .5): In a discrete time model. there is a last point of ON and a first point of OFF. In a dense time model. we can stipulate that "individual event either stops at some definite point. or its aftermath begins at some definite point". The structure T that we have shown above has open begins and closed ends.

Though point-based and event-based logic can both be used to represent similar knowledge. we argue that Allen's formalism in [1][2] provides an effective way to handle disjunctive temporal relations with his logic. For example "X finishes Y or X starts Y" (where finishes and starts are defined according to Allen's logic [1]) can be represented by X [f s] Y. If we represent this expression by using start and end points of X and Y. then we have:

(start(Y)<start(X) and end(X) - end(Y))

or (start(X) - start(Y) and end(X) < end(Y)) The more disjunctive primitive binary relations are allowed between two events. the more cumbersome this point-based representation would be. As the number of events grows. the number of conjunctive combinations will grow exponentially. For example to represent:

X [o f] Y & Y [m o] Z

in Allen's logic (which means X overlaps or finishes Y and Y meets or overlaps Z) with relation among start and end points. we need to represent each element of the cartesian set:

X [o] Y & Y [m] Z

X [o] Y & Y [o] Z

X [f] Y & Y [m] Z

X [f] Y & Y [o] Z

with inequalities.

However. we argue that point-based representation can be used to reason certain disjunctive temporal relations without needing to use disjunctive inequalities. (Similar view has been expressed in [17]). The exhaustive set of temporal relations between points is [ < - > ]. Each of these relations between two start/end points represent a subset of temporal relations in Allen's interval-based representation. They are summarized in Table 1.

From table 1. we can see that a point-based representation can represent limited subsets of temporal relations between intervals. The subsets that they can represent are the sets (represented by lists) on the second note: s(X). e(X) are start/end points of X

column of table 1. or their conjunctives. For example start(A) < start(B) & start(B) < end(A)

represents the subset of relations A [o fi di] B. This expressive power may be sufficient in applications where we are only informed of the relation between start and end points rather than more complicated temporal relations among intervals. But in a point-based representation. we cannot represent arbitrary relations like A [ < >] B without using disjunctive inequalities. Therefore it would not be very favourable if we are often told constraints like "A and B must be separate intervals".

VD Summary and Dl.acussion

Recently. interest in modeling time in AI has increased. and so as interest in event-based logics. In this paper. we have studied Allen & Hayes' logic. which has received great attention in AI. and locate it in the spectrum of the logics developed by logicians. By giving a new set of axioms to Allen & Hayes' logic (which we call A). we hope to have a better control of the systems built up it. In [1.5]. we present one interesting development. which is to remove linearity ((E7) in E*) in order to talk about planning under uncertainty.

We have presented an event-based structure E* which is equivalent to A. We have also defined a point-based structure T which corresponds to E*. We have shown how point-. event- and interval-based structures can be related to one another. Figure 2 below summarizes the relationship among the dilferent time structures mentioned in this paper. We conclude that these structures can all represent similar knowledge. and their fundamental dilference is a question of ontology. But as a tool for AI. we argue that Allen's formalism in [112] allows us to represent disjunctive temporal relations more neatly.

In this paper. we have not discussed the trade off between expressive power and complexity of the di1rerent representations. One such discussion can be found in [17]. Also. we have not suggested how such time structures can be used for AI applications (Shoham's work fills part of this gap [13][14]). This paper only aims at providing a solid study of di1rerent time structures for temporal reasoning. Limited by space and our focus in this paper. we have not studied McDermott's time logic [10]. which also has an important place in AI.

[note 1] An alternative way of defining xUy can be found in [5]:

However. this definition will allow the domain E to have just 4 intervals which have the following relation:

If Union is defined in this way. our (Ell) will not be strong enough for proving (M3) of A.

1. Allen. J.P. & Koomen. J.A.. "Planning using a temporal world model". UCAI-83, 741-747
2. Allen, J.P .. "Maintaining Knowledge about Temporal Intervals". CACM vol.26. no.U. November. 1983, 832-843
3. Allen, J.P .· ~owards a General Theory of Actions and Time". AI 23(1984) 123-154
4. Allen. J.P. & Hayes. P.J .· "A common-sense theory of time". UCAI-85. 528-531
5. Van Benthem. J.. ~ logic of time", D Reidel Publishing Co. 1983
6. Dean. T.. ~emporal Imagery: An Approach to Reasoning with Time for Planning and Problem Solving", Ph D Dissertation. Yale University, October 1985
7. Grant, T.. ~emporal logic8 for planning". Alvey workshop on Planning. July 1985
8. Kamp. H.. "Instants and temporal reference". Von Stechow (ed.) Semantics from di1rerent points of view Springer Series in Language and Communication 6. Springer Verlag, 1979. 376-417
9. Kamp. H .· "Some remarks on the logic of change, Part r. Guenthner F (ed.). Proc. Stuttgart Conference on the Logic of Tense and Quanti1ication. North Holland, 1980. 135-179
10. McDermott. D .· · A temporal logic for reasoning about processes and plans". Cognitive Science 6, p101-155, 1982
11. McDermott. D.. "Generalizing problem reduction : a logical analysis". UCAI-83. 302-308
12. Russel, B.. "On Order in Time". in Marsh R C (ed) Rrussel 8: Logic and Knowledge (essays 1901-1950). London 1956
13. Shoham. Y .· "Rei1ied Temporal Logic, Semantical and ontological considerations". 7th ECAI. July 1986. 390397
14. Shoham. Y.. "Chronological Ignorance: Time. nonmonotonicity. necessity and causal theories". AAAI86. 389-393
15. Tsan~. E.P.K.. "The Interval Structure of Allen's Logic · Technical Report CSCM-24. University of Essex. April. 1986
16. Turner. R .· "Logics for Ar. Ellis Horwood series in Artificial Intelligence. 1984
17. Vilain. M. & Kautz. H.. "Constraint propagation algorithms for temporal reasoning". AAAI86,377-382
18. Whitehead. A. N.. "Process and Reality: an essay in cosmology". Cambridge 1929

AckTwwledgements

Professor Ray Turner, Jim Doran, S4m Steel and Tony Lawson have given me valuable opinions on tM content and presentation of this paper. Anthony CMTI.g Mlped in preparing tM camera copy. This project ts supported by tM studentship fund of tM Department of Computer Science, University of Essex, c:olcMster, EngUur.d.