Temporal reasoning is an essential part of many artificial intelligence tasks. It is desirable, therefore, to develop a temporal reasoning component that is useful across applications. Some applications, such as planning and scheduling, can rely heavily on a temporal reasoning component and the success of the application can depend on the efficiency of the underlying temporal reasoning component. In this paper, we discuss the design and empirical analysis of two algorithms for a temporal reasoning system based on Allen's [2] influential interval-based framework for representing temporal information. The two algorithms, a path consistency algorithm and a backtracking algorithm, are important for two fundamental tasks: determining whether the temporal information is consistent, and, if so, finding one or more scenarios that are consistent with the temporal information.

Our stress is on designing algorithms that are robust and efficient in practice. 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. As well, we show that a previously suggested reformulation of the backtracking search problem [25] can reduce the time and space requirements of the backtracking search. Taken together, the techniques we develop allow a temporal reasoning component to solve problems that are of realistic size. As part of the evidence to support this claim, we evaluate the techniques for improving the algorithms on a large problem that arises in molecular biology.

The software discussed in this paper is available from the authors. The algorithms were implemented in C on a Sun/Unix platform.