The Design and Experimental Analysis of Algorithms for Temporal
  Reasoning
  Many applications -- from planning and scheduling to problems in molecular
biology -- rely heavily on a temporal reasoning component. 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. As well, we show that a previously
suggested reformulation of the backtracking search problem 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 practical size.
