LOCALIZED TEMPORAL REASONING USING SUBGOALS AND ABSTRACT EVENTS
Shieu‐Hong Lin, Thomas Dean · Computational Intelligence · 1996
We are concerned with temporal reasoning problems where there is uncertainty about the order in which events occur. The task of temporal reasoning is to derive an event sequence consistent with a given set of ordering constraints to achieve a goal. Previous research shows that the associated decision problems are hard even for very restricted cases. In this article, we investigate locality in event ordering and causal dependencies. We present a localized temporal reasoning algorithm that uses subgoals and abstract events to exploit locality. The computational efficiency of our algorithm for a problem instance is quantified by the inherent locality in the instance. We theoretically demonstrate the substantial improvement in performance gained by exploiting locality. This work provides solid evidence of the usefulness of localized reasoning in exploiting locality.