Tech Report CS-94-13

Localized Temporal Reasoning Using Subgoals and Abstraction

Sheiu-Hong Lin and Thomas Dean

March 1994


Temporal reasoning with uncertainty about the ordering of events is important in a wide variety of applications. Previous research shows that the associated decision problems are hard even for very restricted cases. In this paper, we investigate using the temporal locality of events and the spatial locality of state spaces to speed inference. We propose a new perspective for representing cause-and-effect relationships based on finite state automata. This perspective exposes the sources of complexity in temporal reasoning more clearly, and facilitates transforming rule-based temporal reasoning problems into graph reachability problems. We present both positive and negative results that provide insight into the complexity of temporal reasoning.

Content areas: Temporal Reasoning, Reasoning about Action, Planning, Scheduling

(complete text in pdf or gzipped postscript)