A method for metric temporal reasoning
Mathias Broxvall · 2002
Several methods for temporal reasoning with metric time have been suggested—for instance, Horn Disjunctive Lin-ear 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 aug-ments Allen’s interval algebra with a Simple Temporal Prob-lem (STP) has been suggested (Condotta, 2000). In this pa-per, we present a new point-based approach STP ∗ for reason-ing about metric temporal constraints. STP ∗ subsumes the tractable preconvex fragment of the augmented interval alge-bra and can be viewed as a slightly restricted version of Horn DLRs. We give an easily implementable algorithm for de-ciding satisfiability of STP ∗ and demonstrate experimentally its efficiency. We also give a method for finding solutions to consistent STP ∗ problem instances.