Constraint Propagation Algorithms for Temporal Reasoning

Abstract

Abstract: This paper revises and expands upon a paper presented by two of the present authors at AAAI 1986 [Vilain & Kautz 1986]. As with the original, this revised document considers computational aspects of intervalbased and point-based temporal representations. Computing the consequences of temporal assertions is shown to be computationally intractable in the interval-based representation, but not in the point-based one. However, a fragment of the interval language can be expressed using the point language and benefits from the tractability of the latter. The present paper departs from the original primarily in correcting claims made there about the point algebra, and in presenting some closely related results of van Beek [1989]. The representation of time has been a recurring concern of Artificial Intelligence researchers. Many representation schemes have been proposed for temporal reasoning; of these, one of the most attractive is James Allen's algebra of temporal intervals [Allen 1983]. This representation scheme is particularly appealing for its simplicity and for its ease of implementation with constraint propagation algorithms. Reasoners based on