Coping with Disjunctions in Temporal Constraint Satisfaction Problems

Abstract

Path-consistency algorithms, which are polynomial for discrete problems, are exponential when applied to problems involving quantitative temporal information. The source of complexity stems from specifying relationships between pairs of time points as disjunction of intervals. We propose a polynomial algorithm, called ULT, that approximates path-consistency in Temporal Constraint Satisfaction Problems (TCSPs). We compare ULT empirically to path-consistency and directional path-consistency algorithms. When used as a preprocessing to backtracking, ULT is shown to be 10 times more effective then either DPC or PC-2. 1. Introduction Problems involving temporal constraints arise in various areas of computer science such as scheduling, circuit and program verification, parallel computation and common sense reasoning. Several formalisms for expressing and reasoning with temporal knowledge have been proposed, most notably Allen's interval algebra (Allen 83), Vilain and Kautz's point algebra (...