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 separtion between those individuals. Formal investigations of this const.raint-sat.isfaction 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 proJ. ection need both disjunctive constraints and, 3 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 queries. We consider the problem of plan projection under uncertainty and build a temporal representation-hierarchical interval constraints (HIC)-that allows appropriate disjunctive constraints. We then implement the HIC representation in a temporal-reasoning module, and test. it using a plan-projection application. Applying the HIC module to a simple temporal projection problem shows orders-of-magnitude improvement. over running the same projector using current implementations of domain-independent temporal constraint propagators.