
Global Consistency for Continuous Constraints1
Djamila Haroud, Boi Faltings
Artificial Intelligence Laboratory (LIA)
Swiss Federal Institute of Technology (EPFL)
INEcublens, 1015 Lausanne, Switzerland
FAX: +41216935225, email: haroud@lia.di.epfl.ch
Abstract
This paper provides a framework for solving general constraint satisfaction problems (CSPs) with continuous variables. Constraints are represented by a hierarchical binary decomposition of the space of feasible values. We propose algorithms for path and higher degrees of consistency based on logical operations defined on the constraint representation mentioned above and we demonstrate that this algorithms terminate in polynomial time. We show that, in analogy to convex temporal problems and discrete rowconvex problems, convexity properties of the solution spaces can be exploited to compute minimal and decomposable networks using path consistency algorithms. Based on this properties, we also show that a certain class of non binary CSPs can be solved using strong 5consistency.
1 Introduction
In the general case, constraint satisfaction problems (CSPs) are NPcomplete. Trying to solve them by search algorithms, even if theoretically feasible, often results in prohibitive computational cost. One approach to overcome this complexity consists of preprocessing the initial problem using propagation algorithms. These algorithms establish various degrees of local consistency which narrow the initial feasible domain of the variables, thus reducing the subsequent search effort. Traditional consistency techniques and propagation algorithms  such as the Waltz propagation algorithm provide relatively poor results when applied to continuous CSPs: they ensure neither completeness nor convergence in the general case (a good insight of the problems encountered can be found in [1]). However, Faltings [5] has shown that some undesirable features of propagation algorithms with interval labels must be attributed to the inadequacy of the propagation rule and to a lack of precision in the solution space description. He has also demonstrated that the problem with local propagation could be resolved by using total constraints on pairs of variables. Lhomme [11] has identified similar problems and proposed an interval propagation formalism based on bound propagation.
Van Beek's work on temporal reasoning [15] using Helly's theorem has shown the importance
of pathconsistency for achieving globally consistent labellings. In certain cases, pathconsistency
algorithms are difficult to implement in continuous domains because they require intersection
and composition operations on constraints. We propose a constraint representation by recursive
decomposition similar to the one described by Tanimoto in [14] which allows to implement these
operations. This allows us to apply Helly's theorem to general continuous constraint satisfaction
problems. The results obtained for temporal CSPs could therefore be generalized to less specific
classes of continuous CSPs.
1A version of this paper will be published in ECAI'94