In this paper, we discuss the design and empirical analysis of algorithms for a temporal reasoning system based on Allen's influential interval-based framework for representing temporal information. At the core of the system are algorithms for determining whether the temporal information is consistent, and, if so, finding one or more scenarios that are consistent with the temporal information. Two important algorithms for these tasks are a path consistency algorithm and a backtracking algorithm. For the path consistency algorithm, we develop techniques that can result in up to a ten-fold speedup over an already highly optimized implementation. For the backtracking algorithm, we develop variable and value ordering heuristics that are shown empirically to dramatically improve the performance of the algorithm.
Reasoning about space and time is a major field of interest in many areas of theoretical and applied AI, especially in the theory and application of temporal and spatial models in planning, high-level navigation of autonomous mobile robots, natural language understanding, temporal databases, and concurrent and distributed programming. The special track on spatiotemporal reasoning focuses on research and development aspects in the area of reasoning about models of space and time. It has a long history at the FLAIRS conferences, starting with an initiative of the late Frank Anger in 1999. Over the years, the track has received a steady interest from researchers around the world. Recent years have witnessed remarkable advances in some of the longstanding problems of the field of spatiotemporal reasoning.
Welcome to the Workshop on Spatial and Temporal Reasoning at AAAI-08 in Chicago, Illinois. This workshop continues in the spirit of a series of activities that started with the Workshop on Spatial and Temporal Reasoning at IJCAI-93 in Chambéry, France. These activities have led to numerous publications over the last fifteen years, spanning related communities of researchers that study representing and reasoning about either space or time or both. Various basic representational problems in space (direction, location, proximity, geometry, intersection) and in time (coincidence, order, concurrency, overlap, granularity) attract repeated attention due to their fundamental and difficult nature. Beyond that, however, the richness of different ontologies, different applications, and different objectives assures that no small collection of solutions will serve to satisfy all needs.