The Non-overlapping Constraint between Objects Described by Non-linear Inequalities

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
Abstract : Packing 2D objects in a limited space is an ubiquitous problem with many academic and industrial variants. In any case, solving this problem requires the ability to determine where a first object can be placed so that it does not intersect a second, previously placed, object. This subproblem is called the non-overlapping constraint. The complexity of this non-overlapping constraint depends on the type of objects considered. It is simple in the case of rectangles. It has also been studied in the case of polygons. This paper proposes a numerical approach for the wide class of objects described by non-linear inequalities. Our goal here is to calculate the non-overlapping constraint, that is, to describe the set of all positions and orientations that can be assigned to the first object so that intersection with the second one is empty. This is done using a dedicated branch & prune approach. We first show that the non-overlapping constraint can be cast into a Minkowski sum, even if we take into account orientation. We derive from this an inner contractor, that is, an operator that removes from the current domain a subset of positions and orientations that necessarily violate the non-overlapping constraint. This inner contractor is then embedded in a sweeping loop, a pruning technique that was only used with discrete domains so far. We finally come up with a branch & prune algorithm that outperforms Rsolver, a generic state-of-the-art solver for continuous quantified constraints.
Type de document :
Communication dans un congrès
The 20th International Conference on Principles and Practice of Constraint Programming, Sep 2014, Lyon, France. Barry O'Sullivan, 8656, pp.672 - 687, 2014, Principles and Practice of Constraint Programming. 〈10.1007/978-3-319-10428-7_49〉
Liste complète des métadonnées

Littérature citée [3 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-01084612
Contributeur : Ignacio Salas <>
Soumis le : mardi 16 décembre 2014 - 13:16:12
Dernière modification le : lundi 5 octobre 2015 - 16:59:46
Document(s) archivé(s) le : samedi 15 avril 2017 - 09:11:17

Fichier

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

Identifiants

Collections

Citation

Ignacio Salas, Gilles Chabert, Alexandre Goldsztejn. The Non-overlapping Constraint between Objects Described by Non-linear Inequalities. The 20th International Conference on Principles and Practice of Constraint Programming, Sep 2014, Lyon, France. Barry O'Sullivan, 8656, pp.672 - 687, 2014, Principles and Practice of Constraint Programming. 〈10.1007/978-3-319-10428-7_49〉. 〈hal-01084612v2〉

Partager

Métriques

Consultations de
la notice

284

Téléchargements du document

101