Distance constraints are widely used in many applications ranging from robotics to chemistry and CAD. Classical tehniques for solving such continuous constraints are based on a branch and prune algorithm which combines domain filtering techniques (local consistencies) and domain splitting. The main drawback of these methods comes from the fact that constraints are handled independently and in a blind way i.e., local consistencies do not take advantage of the specific semantic properties of the constraints. We introduce in this thesis two approaches for the design of a global constraint for distance relations. The first technique is based on the introduction of redundant constraints direcly infered from geometrical properties of the system. The second approach is a dedicated global filtering algorithm. This work led to the design of a domain decomposition technique which exploits the particular structure of the distance relations. Lastly, we generalize this splitting strategy to a larger class of numerical constraints.
Global constraints and splitting strategies for solving continuous CSP