An Efficient Method for Managing Disjunctions in Qualitative Temporal Reasoning

We provide an efficient method for consistency checking of temporal relations in the Point Algebra (PA-relations) extended by binary disjunctions of PA-relations. Such disjunctions add a great deal of expressive power, including the ability to stipulate disjointness of temporal intervals, which is important in planning applications. The method is basede on two main steps: the first preprocesses the initial set of disjunctions reducing it to a logically equivalent subset, while the second performs a search which uses a form of selective backtracking and a "forward propagation" technique to greatly enhance efficiency. The preprocessing phase is worst-case polynomial, and in principle is strong enough ti subsume consistency checking for Nebel and Bürckert's ORD-Horn class of interval relations. Experimental results using a specialized algorithm for binary disjunctions of inequalities show that our method is very efficient especially when the number of disjunctions is limited relative to the number of PA-relations, and that although consistency testing is NP-complete, in practice our algorithms tend to perform polynomially