language: en

[Computational Intelligence, Volume 12, Number 3, 1996]

LOCALIZED TEMPORAL REASONING USING SUBGOALS AND ABSTRACT EVENTS

Shieu-Hong Lin, Thomas Dean 1
Department of Computer Science, Brown University,
Providence, RI 02912

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 paper, 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 a solid evidence of the usefulness of localized reasoning in exploiting locality.

Key words: Dynamical Systems, Temporal Reasoning, Planning, Locality, Localized Reasoning, Subgoals, Abstract Events

1. INTRODUCTION