Large-Scale Temporal Data Bases for Planning in Complex Domains

Abstract

Planning in any realistic setting requires the management of an enormous amount of information. This information is generally temporal in nature; prediction, plan choice, and debugging all involve reasoning about time. The assertions manipulated by traditional predicate-calculus data base systems, such as Prolog, are timelessly true . In the temporal data base system described in this paper, the classical data base assertion is replaced with the notion of a time token. For any given event or fact type, the data base will typically contain a large number of time tokens of that type. These tokens correspond to different occasions when an event of that type occurred or a fact of that type was made true and remained so for some period of time. This profusion of time tokens of the same type presents a problem for systems supporting temporal deductions of the sort needed in planning. Many routine planning operations must search through the data base for tokens satisfying certain temporal constraints. To expedite these operations, this paper describes a computational framework in which common-sense strategies for organizing temporal facts are exploited to speed search.