Exploiting Domain Structure to Achieve Efficient Temporal Reasoning

Abstract

We take temporal reasoning to be the problem of maintaining a set of constraints between time points and/or intervals, and responding to queries about the temporal separation between those individuals. Formal investigations of this constraint-satisfaction problem have demonstrated tradeoffs between the expressive power of the constraint language and the time required to answer queries. A simple constraint language admits an algorithm cubic in the number of individuals; allowing unrestricted disjunctive constraints makes the algorithm exponential. The problem is that applications of temporal reasoning, e.g. plan projection, need both disjunctive constraints and an algorithm much faster than O(n³). It is significant, however, that the nature of the constraints added by and the queries posed by an application tend to be structured and predictable. Our solution to the problem is to exploit the structure of the application domain to provide fast responses to typical...