Packing Curved Objects

Ignacio Salas 1, 2, * Gilles Chabert 2, 1
* Auteur correspondant
2 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
Abstract : This paper deals with the problem of packing two-dimensional objects of quite arbitrary shapes including in particular curved shapes (like ellipses) and assemblies of them. This problem arises in industry for the packaging and transport of bulky objects which are not individually packed into boxes, like car spare parts. There has been considerable work on packing curved objects but, most of the time, with specific shapes; one famous example being the circle packing problem. There is much less algorithm for the general case where different shapes can be mixed together. A successful approach has been proposed recently in [Martinez et al., 2013] and the algorithm we propose here is an extension of their work. Mar-tinez et al. use a stochastic optimization algorithm with a fitness function that gives a violation cost and equals zero when objects are all packed. Their main idea is to define this function as a sum of n!/(2!*(n-2)!) elementary functions that measure the overlapping between each pair of different objects. However, these functions are ad-hoc formulas. Designing ad-hoc formulas for every possible combination of object shapes can be a very tedious task, which dramatically limits the applicability of their approach. The aim of this paper is to generalize the approach by replacing the ad-hoc formulas with a numerical algorithm that automatically measures the overlapping between two objects. Then, we come up with a fully black-box packing algorithm that accept any kind of objects. [Martinez et al., 2013] T. Martinez, L. Vitorino, F. Fages, and A. Aggoun. On Solving Mixed Shapes Packing Problems by Continuous Optimization with the CMA Evolution Strategy. In Proceedings of the first BRICS countries congress on Computational Intelligence, 2013.
Type de document :
Communication dans un congrès
Twenty-Fourth International Joint Conference on Artificial Intelligence, Jul 2015, Buenos Aires, Argentina. pp.396, 2015, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. <http://ijcai.org/papers15/contents.php>
Liste complète des métadonnées


https://hal.archives-ouvertes.fr/hal-01148155
Contributeur : Ignacio Salas <>
Soumis le : lundi 4 mai 2015 - 10:50:47
Dernière modification le : mardi 26 janvier 2016 - 01:07:42
Document(s) archivé(s) le : mercredi 19 avril 2017 - 12:50:37

Fichier

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

Identifiants

  • HAL Id : hal-01148155, version 1

Collections

Citation

Ignacio Salas, Gilles Chabert. Packing Curved Objects. Twenty-Fourth International Joint Conference on Artificial Intelligence, Jul 2015, Buenos Aires, Argentina. pp.396, 2015, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. <http://ijcai.org/papers15/contents.php>. <hal-01148155>

Partager

Métriques

Consultations de
la notice

291

Téléchargements du document

156