Contrainte de non-chevauchement entre objets décrits par des inégalités non-linéaires

Ignacio Salas 1 Gilles Chabert 1 Alexandre Goldsztejn 2
1 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
Résumé : Le placement d'objets 2D dans un espace limité est un problème omniprésent aussi bien sur le plan académique qu'industriel. Quel que soit le contexte, la résolution de ce problème exige la capacité de pouvoir déterminer où un premier objet peu être placé de telle façon qu'il ne chevauche pas un second objet, précédemment placé. Ce sous-problème s'appelle la contrainte de non-chevauchement. La complexité de cette contrainte de non-chevauchement dépend du type d'objets considérés. Elle est simple dans le cas de rectangles. Elle a également été étudiée dans le cas de polygones. Cet article propose une approche numérique pour la classe générale des objets décrits par des inégalités non-linéaires. Notre objectif ici est de calculer la contrainte de non-chevauchement, c'est à dire, de décrire l'ensemble de toutes les positions et orientations qui peuvent être attribuées au premier objet de telle sorte que l'intersection avec le second soit vide. Nous nous basons sur un algorithme de branch & prune dédié. Nous montrons d'abord que la contrainte de non-chevauchement, équivaut à une somme de Minkowski, même lorsque l'orientation est prise en compte. Nous en déduisons un contracteur intérieur, c'est à dire, un opérateur qui élimine du domaine courant un sous-ensemble de positions et orientations qui violent nécessairement la contrainte de non-chevauchement. Ce contracteur intérieur est intégré dans une boucle de sweep, une technique utilisée jusqu'ici uniquement pour les domaines discrets. Nous aboutissons ainsi à un algorithme de branch & prune présentant de bien meilleures performances que Rsolver, outil de référence pour la résolution de contraintes quantifiées en domaines continus.
Type de document :
Communication dans un congrès
Journées Francophones de Programmation par Contraintes (JFPC), Jun 2014, Angers, France. Actes Dixièmes Journées Francophones de Programmation par Contraintes (JFPC) 2014
Liste complète des métadonnées


https://hal.archives-ouvertes.fr/hal-01079579
Contributeur : Ignacio Salas <>
Soumis le : lundi 3 novembre 2014 - 11:23:49
Dernière modification le : lundi 5 octobre 2015 - 17:00:51
Document(s) archivé(s) le : mercredi 4 février 2015 - 10:20:53

Fichier

jfpc2014_submission_28.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01079579, version 1

Collections

Citation

Ignacio Salas, Gilles Chabert, Alexandre Goldsztejn. Contrainte de non-chevauchement entre objets décrits par des inégalités non-linéaires. Journées Francophones de Programmation par Contraintes (JFPC), Jun 2014, Angers, France. Actes Dixièmes Journées Francophones de Programmation par Contraintes (JFPC) 2014. <hal-01079579>

Partager

Métriques

Consultations de
la notice

160

Téléchargements du document

153