Une nouvelle méthode de calcul facilite le placement dense d’objets à l’intérieur d’un conteneur rigide.
Il est souvent difficile d’emballer de manière uniforme des objets 3D de tailles et de formes variées. En fait, ce problème est classé dans la catégorie NP-hard, ce qui signifie qu’il ne peut être résolu exactement – ou même approximativement, avec un haut degré de précision – sans nécessiter des temps de calcul absurdes qui peuvent prendre des années ou des décennies, et ce sans parler du nombre de pièces qui doivent être placées dans un espace confiné.
Une équipe de chercheurs du MIT et d’Inkbit (une entreprise dérivée du MIT basée à Medford, dans le Massachusetts) travaille sur une nouvelle méthode de calcul qui pourrait simplifier cette tâche.
La technique appelée « dense, interlocking-free and Scalable Spectral Packing » (SSP) consiste en trois étapes principales :
- La première étape du SSP consiste à élaborer un ordre d’objets solides en 3D pour remplir un conteneur fixe. Une approche possible, par exemple, consiste à commencer par les objets les plus grands et à terminer par les plus petits. L’étape suivante consiste à placer chaque objet dans le conteneur. Pour faciliter ce processus, le conteneur est « voxélisé », c’est-à-dire qu’il est représenté par une grille 3D composée de minuscules cubes ou voxels, dont chacun peut avoir une taille d’à peine un millimètre cube. La grille indique les parties du conteneur – ou les voxels – qui sont déjà remplies et celles qui sont vacantes.
- L’étape suivante consiste à passer au crible tous les emplacements possibles et à déterminer la meilleure position disponible pour placer l’objet. Pour ce faire, les chercheurs calculent une autre métrique à chaque voxel, conçue pour maximiser localement la densité d’empaquetage. Cette métrique mesure les écarts entre l’objet et la paroi du conteneur – ou entre l’objet qui est déplacé et les objets déjà situés dans le conteneur. Si l’objet est placé en plein centre, par exemple, la métrique lui attribuera probablement une valeur élevée. L’objectif est toutefois de minimiser les écarts entre les objets, ce qui peut être réalisé en plaçant l’objet à l’endroit où la valeur métrique est la plus faible. « C’est un peu comme le jeu Tetris», explique Matusik. « Il faut laisser le moins d’espace vide possible. »
- La dernière étape de l’algorithme SSP consiste à s’assurer que, pour un arrangement apparemment souhaitable, chaque objet peut effectivement être placé dans l’emplacement qui lui a été attribué, ou, de manière équivalente, que chaque objet peut être séparé des autres objets lors du déballage du conteneur. En d’autres termes, l’emballage doit être « sans emboîtement », ce qui permet d’éviter les configurations telles que les anneaux emboîtés.
Déterminer les meilleurs emplacements pour chaque objet au fur et à mesure que le conteneur se remplit nécessite évidemment de nombreux calculs. Mais l’équipe a utilisé une technique mathématique, la transformation de Fourier rapide (FFT = fast Fourier transform), qui n’avait jamais été appliquée au problème de l’empaquetage auparavant. Grâce à la FFT, les problèmes de minimisation du chevauchement des voxels et de minimisation des écarts pour tous les voxels du conteneur peuvent être résolus par un ensemble relativement limité de calculs, tels que de simples multiplications, contrairement à l’alternative peu pratique consistant à tester tous les emplacements possibles pour les objets à placer à l’intérieur du conteneur. L’emballage est ainsi plus rapide de plusieurs ordres de grandeur.
Quel est le rapport avec l’impression 3D ?
Cette approche peut bien sûr être utile aux entreprises d’entreposage et d’expédition qui emballent régulièrement des objets divers dans des boîtes de tailles différentes. Cependant, l’équipe de recherche s’intéresse particulièrement aux applications de l’impression 3D. Les pièces sont normalement fabriquées par lots et placées sur des plateaux. Cependant, les approches actuelles, selon Matusik, le chercheur en chef, « n’utilisent que très peu le volume [du conteneur] » – généralement autour de 20 %. « Si nous parvenons à augmenter la densité d’emballage, nous pourrons accroître l’efficacité globale du processus d’impression et réduire ainsi le coût total des pièces fabriquées, », l’un des chercheurs explique.
Si cette recherche propose des procédures nouvelles et améliorées pour l’impression 3D, ainsi que pour l’emballage d’objets rigides, le problème de la meilleure façon d’agencer des objets déformables ou articulés – ces derniers étant constitués de plusieurs pièces rigides reliées par des articulations – reste ouvert et pourrait être abordé dans de futurs travaux. En attendant, si quelqu’un se retrouve un jour avec seulement deux heures pour ranger plus de 6 000 objets dans un bac de stockage, il n’y a pas lieu de désespérer. Il suffit d’un algorithme pour obtenir de l’aide.
N’oubliez pas que vous pouvez poster gratuitement les offres d’emploi de l’industrie de la FA sur 3D ADEPT Media ou rechercher un emploi via notre tableau d’offres d’emploi. N’hésitez pas à nous suivre sur nos réseaux sociaux et à vous inscrire à notre newsletter hebdomadaire : Facebook, Twitter, LinkedIn & Instagram !