Coping With Disjunctions in Temporal Constraint Satisfaction Problems

Eddie Schwalb, Rina Dechter

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.