A Method for Metric Temporal Reasoning

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Actions and Temporal Reasoning

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. 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.