An efficient consistency algorithm for the temporal constraint satisfaction problem. (English) Zbl 1098.68115

Summary: R. Dechter, I. Meiri and J. Pearl [Artif. Intell. 49, No. 1–3, 61–95 (1991; Zbl 0737.68070)] 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 \(\Delta\)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 \(\Delta\)AC as a preprocessing step to solving the meta-CSP. We show experimentally that it dramatically reduces the size of a meta-CSP and significantly enhances the performance of search for finding the minimal network of the corresponding TCSP.


68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68R10 Graph theory (including graph drawing) in computer science


Zbl 0737.68070