Journal of Artificial Intelligence Research 4 (1996) 1-18
Submitted 9/95; published 1/96
(c) 1996 AI Access Foundation and Morgan Kaufmann Publishers.
All rights reserved.
The Design and Experimental Analysis of Algorithms for
Peter van Beek,
Dennis W. Manchak,
Department of Computing Science, University of Alberta
Edmonton, Alberta, Canada T6G 2H1
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
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.
Table of Contents