en fr Global constraints and splitting strategies for solving continuous CSP Contraintes globales et heuristiques de recherche pour les CSPs continus Report as inadecuate




en fr Global constraints and splitting strategies for solving continuous CSP Contraintes globales et heuristiques de recherche pour les CSPs continus - Download this document for free, or read online. Document in PDF available to download.

1 I3S - Laboratoire d-Informatique, Signaux, et Systèmes de Sophia Antipolis

Abstract : 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.

Résumé : Les systèmes de contraintes de distance euclidienne apparaissent dans de nombreux domaines d-applications, comme en robotique, en biochimiemoléculaire ou en CAO. Les techniques issues de la programmation par contraintes permettent de résoudre ces problèmes en combinant une technique de bissection avec des méthodes de réduction des domaines consistances locales ou partielles. Or, ces consistances sont des méthodes systématiques qui ne prennent pas en compte les propriétés spécifiques des contraintes.Nous présentons dans cette thèse deux approches pour la conception d-une contrainte globale pour la résolution de systèmes de contraintes de distance. La première approche est basée sur l-inférence de contraintesredondantes directement issues de propriétés géométriques du système.La deuxième approche est basée sur l-introduction d-un algorithme de filtrage global dédié aux systèmes d-équations de distance.Ces travaux ont débouché sur la conception d-unetechnique de décomposition de domaines qui exploite la structure particulière des contraintes de distance. Enfin, nous présentons une généralisation de cette heuristique de recherche à des contraintes numériques quelconques.

Mots-clés : Constraint programming continuous CSPs globalconstraints splitting techniques interval analysis distance constraints Programmation par contraintes CSP continus contraintes globales heuristiques de recherche analyse par intervalles contraintes de distance





Author: Heikel Batnini -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents