×

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.

MSC:

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

Citations:

Zbl 0737.68070
PDF BibTeX XML Cite