by JF ALLEN · 1983 · Cited by 11568 — natural language processing and the representation of knowledge. Author’s Present Address: James F. Allen, Computer. Science Department,. University of
12 pages
188 KB – 12 Pages
PAGE – 1 ============
/ESEARCH COKrNBlmONS Maintaining Knowledge about Temporal Intervals JAMES F. ALLEN The University of Rochester lames F. Allen’s main interests are in artificial intelligence in particular natural language processing and the representation of knowledge. Author’s Present Address: James F. Allen, Computer Science Department, University of Rochester. Rochester. NY 14627. The research described in this paper was supported in part by the National Science Foundation under Grants IST-g0-12418 and IST-82-10564. and in part by the Office of Naval Research under Grant N00014-80-C-0197. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. © 1983 ACM 0001-0782/83/1100.0832 75¢ 1. INTRODUCTION The problem of representing temporal knowledge and tem- poral reasoning arises in a wide range of disciplines, including computer science, philosophy, psychology, and linguistics. In computer science, it is a core problem of information systems, program verification, artificial intelligence, and other areas involving process modeling. (For a recent survey of work in temporal representation, see the special sections in the April 1982 issues of the ACM SIGART and SIGMOD Newsletters.) Information systems, for example, must deal with the p~b- lem of outdated data. One approach to this is simply to delete outdated data; however, this eliminates the possibility of ac- cessing any information except that which involves facts that are presently true. In order to consider queries such as, “Which employees worked for us last year and made over $15,000/’ we need to represent temporal information. In some applications, such as keeping medical records, the time course of events becomes a critical part of the data. In artificial intelligence, models of problem solving require sophisticated world models that can capture change. In plan- ning the activities of a robot, for instance, one must model the effects of the robot’s actions on the world to ensure that a plan will be effective. In natural language processing re- searchers are concerned with extracting and capturing tem- poral and tense information in sentences. This knowledge is necessary to be able to answer queries about the sentences later. Further progress in these areas requires more powerful representations of temporal knowledge than have previously been available. This paper addresses the problem from the perspective of artificial intelligence. It describes a temporal representation that takes the notion of a temporal interval as primitive. It then describes a method of representing the relationships be- tween temporal intervals in a hierarchical manner using con- straint propagation techniques. By using reference intervals, ABSTRACT: An interval-based temporal logic is introduced, together with a computationally effective reasoning algorithm based on constraint propagation. This system is notable in offering a delicate balance between expressive power and the efficiency of its deductive engine. A notion of reference intervals is introduced which captu~s the temporal hierarchy implicit in many domains, and which can be used to precisely control the amount of deduction performed automatically by the system. Examples are provided for a database containing historical data, a database used for modeling processes and proce~ interaction, and a database for an interactive system where the present moment is continually being updated. 832 Communications of the ACM November 1983 Volume 26 Number 11
PAGE – 2 ============
RESEARCH CONTRIBUTIONS the amount of computation involved when adding a fact can be controlled in a predictable manner. This representation is designed explicitly to deal with the problem that much of our temporal knowledge is relative, and hence cannot be de- scribed by a date (or even a “fuzzy” date). We start with a survey of current techniques for modeling time, and point out various problems that need to be ado dressed. After a discussion of the relative merits of interval- based systems versus point-based systems in Section 3, a sim- ple interval-based deduction technique based on constraint propagation is introduced in Section 4. This scheme is then augmented in Section 5 with reference intervals, and exam- ples in three different domains are presented. In the final sections of the paper, extensions to the basic system are pro- posed in some detail. These would extend the representation to include reasoning about the duration of intervals, reasoning about dates when they are available, and reasoning about the future given knowledge of what is true at the present. The system as described in Section 5 has been imple- mented and is being used in a variety of research projects which are briefly described in Section 6. Of the extensions, the duration reasoner is fully implemented and incorporated into the system, whereas the date reasoner has been designed but not implemented. 2. BACKGROUND Before we consider some previous approaches to temporal representation, let us summarize some important characteris- tics that are relevant to our work: Ł The representation should allow significant imprecision. Much temporal knowledge is strictly relative (e.g., A is before B) and has little relation to absolute dates. Ł The representation should allow uncertainty of informa- tion. Often, the exact relationship between two times is not known, but some contraints on how they could be related are known. Ł The representation should allow one to vary the grain of reasoning. For example, when modeling knowledge of history, one may only need to consider time in terms of days, or even years. When modeling knowledge of com- puter design, one may need to consider times on the order of nanoseconds or less. Ł The model should support persistence. It should facili- tate default reasoning of the type, “If I parked my car in lot A this morning, it should still be there now,” even though proof is not possible (the car may have been towed or stolen). This does not exhaust all the issues, and others will come up as they become relevant. It provides us with a starting criteria, however, for examining previous approaches. Pre- vious work can be divided roughly into four categories: state space approaches, date line systems, before/after chaining, and formal models. State space approaches (e.g., [7, 17]) provide a crude sense of time that is useful in simple problem-solving tasks. A state is a description of the world (i.e., a database of facts) at an instantaneous point in time. Actions are modeled in such systems as functions mapping between states. For example, if an action occurs that causes P to become true and causes fact Q to be no longer true, its effect is simulated by simply adding fact P to the current state and deleting fact Q. If the previous states are retained, we have a representation of time as a series of databases describing the world in successive states. In general, however, it is too expensive to maintain all the pre- vious states, so most systems only maintain the present state. While this technique is useful in some applications, it does not address many of the issues that concern us. Note that such systems do provide a notion of persistence, however. Once a fact is asserted, it remains true until it is explicitly deleted. In datebase systems (e.g., [4, 5, 12, 13]), each fact is indexed by a date. A date is a representation of a time such that the temporal ordering between two dates can be computed by fairly simple operations. For example, we could use the inte- gers as dates, and then temporal ordering could be computed using a simple numeric comparison. Of course, more compli- cated schemes based on calendar dates and times are typi- cally more useful. Because of the nice computational proper- ties, this is the approach of choice if one can assign dates for every event. Unfortunately, in the applications we are consid- ering, this is not a valid assumption. Many events simply cannot be assigned a precise date. There are methods of geno eralizing this scheme to include ranges of dates in which the event must occur, but even this scheme cannot capture some relative temporal information. For instance, the fact that two events, A and B, did not happen at the same time cannot be represented using fuzzy dates for A and B. Either we must decide that A was before B, or B was before A, or we must assign date ranges that allow A and B to overlap. This prob- lem becomes even more severe if we are dealing with time intervals rather than time points. We then need fuzzy date ranges for both ends of the interval plus a range for the minimum and maximum duration of the interval. The next scheme is to represent temporal information us- ing before/after chains. This approach allows us to capture relative temporal information quite directly. This technique has been used successfully in many systems (e.g., [4, 13]). As the amount of temporal information grows, however, it suffers from either difficult search problems (searching long chains) or space problems (if all possible relationships are precom- puted). This problem can be alleviated somewhat by using a notion of reference intervals [13], which will be discussed in detail later. Note that a fact such as “events A and B are disjoint” cannot be captured in such systems unless disjunc- tions can be represented. The approach discussed in this pa- per can be viewed as an extension of this type of approach that overcomes many of its difficulties. Finally, there is a wide range of work in formal models of time. The work in philosophy is excellently summarized in a textbook by Rescher and Urrquhart [16]. Notable formal models in artificial intelligence include the situation calculus [14], which motivates much of the state space based work in problem solving, and the more recent work by McDermott [15]. In the situation calculus, knowledge is represented as a series of situations, each being a description of the world at an instantaneous point of time. Actions and events are functions from one situation to another. This theory is viable only in domains where only one event can occur at a time. Also, there is no concept of an event taking time; the transforma- tion between the situations cannot be reasoned about or de- composed. The situation calculus has the reverse notion of persistence: a fact that is true at one instance needs to be explicitly reproven to be true at succeeding instants. Most of the work in philosophy, and both the situation calculus and the work by McDermott, are essentially point- based theories. Time intervals can be constructed out of points, but points are the foundation of the reasoning system. This approach will be challenged in the upcoming section. One other formal approach, currently under development, that is compatible with an interval-based temporal representa- November 1983 Volume 26 Number 11 Communications of the ACM 833
PAGE – 3 ============
RESEARCH CONTRIBUTIONS tion is found in the Naive Physics work of Hayes [10, 11]. He proposes the notion of a history, which is a contiguous block of space-time upon which reasoning can be organized. By viewing each temporal interval as one dimension of a history, this work can be seen as describing a reasoning mechanism for the temporal component of Naive Physics. 3. TIME POINTS VS. TIME INTERVALS In English, we can refer to times as points or as intervals. Thus we can say the sentences: We found the letter at twelve noon. We found the letter yesterday. In the first, “at twelve noon” appears to refer to a precise point in time at which the finding event occurred (or was occur- ring). In the second, “yesterday” refers to an interval in which the finding event occurred. Of course, these two examples both refer to a date system where we are capable of some temporal precision. In general, though, the references to temporal relations in English are both implicit and vague. In particular, the majority of tem- poral references are implicitly introduced by tense and by the description of how events are related to other events. Thus we have We found the letter while John was away. We found the letter after we made the decision. These sentences introduce temporal relations between the times (intervals) at which the events occurred. In the first sentence, the temporal connective “while” indicates that the time when the find event occurred is during the time when John was away. The tense indicates that John being away occurred in the past (i.e., before now). Although some events appear to be instantaneous (e.g., one might argue that the event “finding the letter” is instanta- neous), it also appears that such events could be decomposed if we examine them more closely. For example, the “finding the letter” might be composed of “looking at spot X where the letter was” and “realizing that it was the letter you were looking at.” Similarly, we might further decompose the “real- izing that it was the letter” into a series of inferences that the agent made. There seems to be a strong intuition that, given an event, we can always “turn up the magnification” and look at its structure. This has certainly been the experience so far in physics. Since the only times we consider will be times of events, it appears that we can always decompose times into subparts. Thus the formal notion of a time point, which would not be decomposable, is not useful. An informal notion of time points as very small intervals, however, can be useful and will be discussed later. There are examples which provide counterintuitive results if we allow zero-width time points. For instance, consider the situation where a light is turned on. To describe the world changing we need to have an interval of time during which the light was off, followed by an interval during which it was on. The question arises as to whether these intervals are open or closed. If they are open, then there exists a time (point) between the two where the light is neither on nor off. Such a situation would provide serious semantic difficulties in a tem- poral logic. On the other hand, if intervals are closed, then there is a time point at which the light is both on and off. This presents even more semantic difficulties than the former case. One solution to this would be to adopt a convention that intervals are closed in their lower end and open on their upper end. The intervals could then meet as required, but each interval would have only one endpoint. The artificiality of this solution merely emphasizes that a model of time based on points on the real line does not correspond to our intuitive notion of time. As a consequence, we shall develop a repre- sentation that takes temporal intervals as primitive. If we allowed time points, intervals could be represented by modeling their endpoints (e.g., [4]) as follows: Assuming a model consisting of a fully ordered set of points of time, an interval is an ordered pair of points with the first point less than the second. We then can define the relations in Figure 1 between intervals, assuming for any interval t, the lesser end- point is denoted by t- and the greater by t+. We could implement intervals with this approach, even given the above argument about time points, as long as we assume for an interval t that t- < t+, and each assertion made is in a form corresponding to one of the interval rela- tions. There are reasons why this is still inconvenient, how- ever. In particular, the representation is too uniform and does not facilitate structuring the knowledge in a way which is convenient for typical temporal reasoning tasks. To see this, consider the importance of the during relation. Temporal knowledge is often of the form event E' occurred during event E. A key fact used in testing whether some condition P holds during an interval t is that if t is during an interval T, and P holds during T, then P holds during t. Thus during relation- ships can be used to define a hierarchy of intervals in which propositions can be "inherited." Furthermore, such a during hierarchy allows reasoning processes to be localized so that irrelevant facts are never considered. For instance, if one is concerned with what is true "today," one need consider only those intervals that are dur- "today," or above "today" in the during hierarchy. If a fact is indexed by an interval wholly contained by an interval representing "yesterday," then it cannot affect what is true now. It is not clear how to take advantage of these properties using the point-based representation above. 4. MAINTAINING TEMPORAL RELATIONS 4.1. The Basic Algorithm The inference technique described in this section is an at- tempt to characterize the inferences about time that appear to be made automatically or effortlessly during a dialogue, story comprehension, or simple problem-solving. Thus it should provide us with enough temporal reasoning to participate in these tasks. It does not, however, need to be able to account for arbitrarily complex chains of reasoning that could be done, say, when solving a puzzle involving time. We saw above five relations that can hold between inter- vals. Further subdividing the during relation, however, pro- Interval Relation Equivalent Relations on Endpoints t s-) & (t+ < s+) t meets s t+ = s- t durings ((t- > s-) & (t+ =(s+)) or ((t- >= s-) & (t+ < s+)) FIGURE 1. Interval Relation Defined by Endpoints. 834 Communicatimls of the ACM November 1983 Volume 26 Number 11
PAGE - 4 ============
RESEARCH CONTRIBUTIONS vides a better computational model? Considering the inverses of these relations, there are a total of thirteen ways in which an ordered pair of intervals can be related. These are shown in Figure 2. Sometimes it is convenient to collapse the three during relations (d, s, f) into one relationship called dur, and the three containment relations (di, si, fi) into one relationship called con. After a quick inspection, it is easy to see that these thirteen relationships can be used to express any relationship that can hold between two intervals. The relationships between intervals are maintained in a network where the nodes represent individual intervals. Each arc is labeled to indicate the possible relationship between the two intervals represented by its nodes. In cases where there is uncertainty about the relationship, all possible cases are en- tered on the arc. Note that since the thirteen possible relation- ships are mutually exclusive, there is no ambiguity in this notation. Figure 3 contains some examples of the notation. Throughout, let Ni be the node representing interval i. Notice that the third set of conditions describes disjoint intervals. Throughout this paper, both the above notations will be used for the sake of readability. In general, if the arc asserts more than one possible relationship, the network form will be used, and in the case where only one relationship is possible, the relation form will be used. For the present, we shall assume that the network always maintains complete information about how its intervals could be related. When a new interval relation is entered, all conse- quences are computed. This is done by computing the transi- tive closure of the temporal relations as follows: the new fact adds a constraint about how its two intervals could be related, which may in turn introduce new constraints between other intervals through the transitivity rules governing the temporal relationships. For instance, if the fact that i is during j is added, and j is before k, then it is inferred that i must be before k. This new fact is then added to the network in an identical fashion, possibly introducing further constraints on the relationship between other intervals. The transitivity rela- tions are summarized in Figure 4. The precise algorithm is as follows: assume for any tem- peral relation names rl and r2 that T(rl, r2) is the entry in the transitivity table in Figure 4. Let R1 and R2 be arc labels, assume the usual set operations (N for intersection, U for union, C for proper subset), and let e be the empty set. Then constraints (R 1, R2) is the transitivity function for lists of rela- tion names (i.e., arc labels), and is defined by: Constraints (R1, R2 ) C~--e; For each rl in R1 For each r2 in R2 C ~ C U T(rl, r2); Return C; Assume we have a queue data structure named ToDo with the appropriate queue operations defined. For any two inter- vals i, j, let N(i, j) be the relations on the arc between i and j in the network, and let R(i, j) be the new relation between i and j to be added to the network. Then we have the follow- ing algorithm for updating the temporal network: To Add R(i, I') Add (i, j) to queue ToDo; While ToDo is not empty do 1 This fact was pointed out to me by Marc Vilain and was first utilized in his system [18]. Relation Symbol Symbol for Inverse X before Y < > X equal Y = = X meets Y m mi X overlaps Y o oi X during Y d di X starts Y s si X finishes Y f fi Pictoral Example XXX YYY XXX YYY XXXYYY XXX YYY XXX YYYYYY XXX YYYYY XXX YYYYY FIGURE 2. The Thirteen Possible Relationships. Relation Network Representation 1. i duringj N i –(d)~ Nj 2. i during j or N i –(< d di)--, Nj i before j or j during i 3. (i
PAGE – 5 ============
RESEARCH COJffRIBUllONS B r2 C < > d di o oi m mi s si f fi Arl B “before” < < "after" no > info “during” d no