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 programming. 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.
展开▼
