ESEARCH COKrNBlmONS Maintaining Knowledge about Temporal Intervals JAMES F ALLEN lames F Allen smain interests are in artificial intelligence in particular natural language processing and the representationof knowledge Author s Present Address James F Allen Computer Science Department Universityof Rochester Rochester NY 14627 The research described in this paper was supported in part by the NationalScience Foundationunder Grants IST g0 12418and IST 82 10564 and in part by the Office of Naval Research under Grant N00014 80 C 0197 Permissionto 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 permissionof the Associationfor Computing Machinery To copy otherwise or to republish requires a fee and or specific permission 1983 ACM 0001 0782 83 1100 0832 75 832 Communications of the ACM The University of Rochester 1 INTRODUCTION The problem of representing temporal knowledge and temporal 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 accessing 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 planning 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 researchers are concerned with extracting and capturing temporal and tense information in sentences This knowledge is necessary to be able to answer queries about the s e n t e n c e s 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 between temporal intervals in a hierarchical manner using constraint 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 November 1983 Volume 26 Number 11 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 described 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 intervalbased systems versus point based systems in Section 3 a simple 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 examples in three different domains are presented In the final sections of the paper extensions to the basic system are proposed 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 implemented 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 characteristics 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 information 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 computer design one may need to consider times on the order of nanoseconds or less The model should support persistence It should facilitate 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 Previous 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