Incremental forward checking for the disjunctive temporal problem

This paper studies algorithms for the Disjunctive Temporal Problem (DTP) a quite general temporal reasoning problem introduced in [12]. This problem involves the satisfaction of a set of constraints represented by disjunctive formulas of the form x(1)-y(1) less than or equal to r(1) boolean OR x(2) - y(2) less than or equal to r(2) boolean OR ... boolean OR x(k) - y(k) less than or equal to r(k). The paper starts sketching why DTPs are potentially very useful in plan management applications, then analyzes the current solutions to DTP, and introduces a constraint-satisfaction problem solving algorithm where different aspects of current DTP's literature are integrated. This basic algorithm is then improved exploiting the quantitative temporal information in the ``distance graph''. Using this knowledge an incremental version of the forward checking is obtained and shown to be competitive with current best results. The whole approach allows to understand pros and cons of the current algorithms for the DTP and suggests further future developments as discussed in the final part of the paper.