A Method for Metric Temporal Reasoning

Abstract

Several methods for temporal reasoning with metric time have been suggested--for instance, Horn Disjunctive Linear Relations (Horn DLRs). However, it has been noted that implementing this algorithm is non-trivial since it builds on fairly complicated polynomial-time algorithms for linear Perogramming. Instead, an alternative approach which augments Allen's interval algebra with a Simple Temporal Problem (STP) has been suggested (Condotta, 2000). In this paper, we present a new point-based approach STP* for reasoning about metric temporal constraints. STP* subsumes the tractable preconvex fragment of the augmented interval algebra and can be viewed as a slightly restricted version of Horn DLRs. We give an easily implementable algorithm for deciding satisfiability of STP* and demonstrate experimentally its efficiency. We also give a method for finding solutions to consistent STP* problem instances.