Backtracking algorithms for disjunctions of temporal constraints

We extend the framework of simple temporal problems studied originally by Dechter, Meiri and Pearl to con-sider constraints of the form xl- yl < rl V... v xn-yn < _ rn, where xl... xn, yl... yn are variables rang-ing over the real numbers, rl... rn are real constants, and n> 1. We have implemented four progressively more efficient algorithms for the consistency checking problem for this class of temporal constraints. We have partially ordered those algorithms according to the number of visited search nodes and the number of performed consistency checks. Finally, we have car-ried out a series of experiments on the location of the hard region. The results show that hard problems oc-cur at a critical value of the ratio of disjunctions to variables. This value is between 6 and 7