REASONING ABOUT RECURRENCE

This article examines the issue of representing knowledge about recurring states and events, and develops mechanisms for reasoning about recurrence. A first-order axiomatization is developed based on the interval calculus that allows entities (events, properties, processes, etc.) to be associated, incidentally or repeatedly, with temporal intervals. The recurrence formalism permits reasoning about truth conditions of relations that occur as parts of known, recurring sequences regardless of their given initial state - their eventually reaching the appropriate state can be inferred. An extensive example is developed in the domain of planning in a world with traffic control lights, showing how the use of recurrence can enable a planner to determine that a plan to travel from a source to a destination is feasible, regardless of the state of an inervening traffic light at the time it is encountered. In order to develop this example, a novel application of the interval logic to the spatial domain is presented, which allows us to reason about trajectories and their traversal over time. The combination of paths and temporal intervals, together with the recurrence axioms and actions such as traverse, allow us to prove several theorems about the use of traffic lights, and to show how an agent can validate plans to get past them.