EFFICIENT ALGORITHMS FOR QUALITATIVE REASONING ABOUT TIME

Reasoning about temporal information is an important task in many area s of Artificial Intelligence. In this paper we address the problem of scalability in temporal reasoning by providing a collection of new alg orithms for efficiently managing large sets of qualitative temporal re lations. We focus on the class of relations forming the Point Algebra (PA-relations) and on a major extension to include binary disjunctions of PA-relations (PA-disjunctions). Such disjunctions add a great deal of expressive power, including the ability to stipulate disjointness of temporal intervals, which is important in planning applications. Ou r representation of time is based on timegraphs, graphs partitioned in to a set of chains on which the search is supported by a metagraph dat a structure. The approach is an extension of the time representation p roposed by Schubert, Taugher and Miller in the context of story compre hension. The algorithms herein enable construction of a timegraph from a given set of PA-relations, querying a timegraph, and efficiently ch ecking the consistency of a timegraph augmented by a set of PA-disjunc tions. Experimental results illustrate the efficiency of the proposed approach.