/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 11RESEARCH 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.