Computer Sciences Commons^™

An Efficient Consistency Algorithm For The Temporal Constraint Satisfaction Problem, Berthe Y. Choueiry, Lin Xu

School of Computing: Faculty Publications

Dechter et al. [5] proposed solving the Temporal Constraint Satisfaction Problem (TCSP) by modeling it as a meta-CSP, which is a finite CSP with a unique global constraint. The size of this global constraint is exponential in the number of time points in the original TCSP, and generalized-arc consistency is equivalent to finding the minimal network of the TCSP, which is NP-hard. We introduce _AC, an efficient consistency algorithm for filtering the meta-CSP. This algorithm significantly reduces the domains of the variables of the meta-CSP without guaranteeing arc-consistency. We use _AC as a preprocessing step to solving the meta-CSP. We …