R30  
Coping With Disjunctions
in Temporal Constraint Satisfaction Problems
Eddie Shwalb (eschwalb@ics.uci.edu)&
Rina Dechter (dechter@ics.uci.edu)

Abstract Pathconsistency 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 pathconsistency in Temporal Constraint Satisfaction Problems (TCSPs). We compare ULT empirically to pathconsistency and directional pathconsistency algorithms. When used as a preprocessing to backtracking, ULT is shown to be 10 times more effective then either DPC or PC2. [ps] [pdf] 