Un nuevo método de cálculo facilita la colocación densa de objetos en un contenedor rígido

En 1611, Johannes Kepler, famoso por sus leyes del movimiento planetario, propuso una solución al problema de la disposición más densa posible de esferas de igual tamaño. El célebre astrónomo abordó este problema cuando le preguntaron cómo disponer las balas de cañón para que ocuparan el menor espacio posible. Kepler concluyó que la mejor configuración era lo que se conoce como una cuadrícula cúbica centrada en las caras, un enfoque comúnmente utilizado en las tiendas de comestibles para exhibir naranjas: cada bala de cañón debe descansar en la cavidad dejada por cuatro balas de cañón (dispuestas en un cuadrado apretado de dos) acostado directamente debajo de él. Sin embargo, esto fue solo una conjetura que no fue probada hasta casi 400 años después por un matemático de la Universidad de Michigan.

Si bien esto resolvió el problema de empaquetar esferas de manera uniforme, el problema más general de cómo colocar de manera óptima objetos 3D de diferentes tamaños y formas sigue sin resolverse. De hecho, este problema se clasifica como NP-difícil, lo que significa que no se puede resolver exactamente, ni siquiera con un alto grado de precisión, sin requerir tiempos de cálculo ridículamente largos, que pueden llevar años o décadas, dependiendo de la cantidad de problemas. elementos que deben caber en un espacio limitado.

Sin embargo, ha habido un progreso significativo, no en la forma de una prueba matemática, sino a través de una nueva metodología computacional que hace que esta tarea que antes era difícil de manejar sea más fácil de lograr. Un equipo de investigadores del MIT e Inkbit (una empresa derivada del MIT con sede en Medford, Massachusetts), dirigido por el Dr. Wojciech Matusik. ’03, profesor del MIT y cofundador de Inkbit, presenta esta técnica, a la que denominan “empaquetamiento espectral denso, libre de bloqueos y escalable” o SSP, este agosto en SIGGRAPH 2023, la conferencia más grande del mundo sobre gráficos por computadora y tecnologías interactivas. Artículo complementario, escrito por Qiaodong Cui de Inkbit, el estudiante graduado del MIT Victor Rong SM ’23, el Dr. Desai Chen. ’17 (también con Inkbit) y Matusik—sera publicado el próximo mes en el diario Gráficos Transacciones ACM.

El primer paso en SSP es ordenar los objetos 3D sólidos para llenar el contenedor fijo. Un enfoque posible es, por ejemplo, comenzar con los objetos más grandes y terminar con los más pequeños. El siguiente paso es colocar cada elemento en un contenedor. Para facilitar este proceso, el contenedor está “voxelado”, lo que significa que está representado por una cuadrícula tridimensional de pequeños cubos o vóxeles, cada uno de los cuales puede ser tan pequeño como un milímetro cúbico. La cuadrícula muestra qué partes del contenedor, o qué vóxeles, ya están llenos y cuáles están vacíos.

El artículo que se empaqueta también se voxeliza, nuevamente representado por un grupo de cubos del mismo tamaño que los del contenedor. Para determinar el espacio disponible para este objeto, el algoritmo calcula una cantidad llamada métrica de colisión para cada vóxel. Funciona colocando el centro del objeto en cada vóxel en el contenedor, luego cuenta la cantidad de vóxeles ocupados con los que el objeto se superpone o “choca”. Solo puede colocar un objeto donde no haya superposición, en otras palabras, donde no haya colisiones.

El siguiente paso es revisar todas las ubicaciones posibles y determinar la mejor posición disponible para colocar el objeto. Para hacer esto, los investigadores calculan una métrica diferente para cada vóxel que apunta a maximizar localmente la densidad de empaquetamiento. Esta métrica mide el espacio entre un objeto y la pared del contenedor, o entre un objeto que se mueve y los objetos que ya están dentro del contenedor. Por ejemplo, si un objeto se coloca en el medio, es probable que la métrica asigne un valor alto.

Sin embargo, el objetivo es minimizar los espacios entre los objetos, lo que se puede lograr colocando el objeto donde el valor métrico es más bajo. “Es un poco como jugar Tetris”, explica Matusik. “Quieres dejar el menor espacio vacío posible”.

Sin embargo, esta no es toda la historia, ya que la discusión anterior se trata de un objeto que se ha movido o “movido” a un contenedor mientras mantiene una orientación fija en el espacio. La computadora puede pasar por todo este proceso con muchas orientaciones diferentes del mismo objeto hasta encontrar la orientación que mejor se adapte al espacio.

El último paso del algoritmo SSP es asegurarse de que en un arreglo aparentemente deseable, cada objeto pueda realmente entrar en su lugar asignado, o de manera equivalente, que cada objeto pueda separarse de otros objetos al desempacar el contenedor. Esto significa que el empaque debe estar “libre de obstrucciones”, un requisito previo para evitar configuraciones como anillos entrelazados.

Por supuesto, determinar la mejor ubicación para cada objeto a medida que se llena el contenedor requiere muchos cálculos. Sin embargo, el equipo utilizó una técnica matemática, la Transformada Rápida de Fourier (FFT), que nunca antes se había aplicado a un problema de empaquetamiento. Usando FFT, los problemas de minimizar la superposición de vóxeles y minimizar los espacios para todos los vóxeles en un contenedor se pueden resolver con un conjunto relativamente limitado de cálculos, como la simple multiplicación, a diferencia de la alternativa poco práctica de probar todas las ubicaciones posibles de los objetos que se colocarán dentro. . Y eso hace que empaquetar pedidos de gran magnitud sea más rápido.

En una demostración, el nuevo algoritmo colocó con éxito 670 objetos en solo 40 segundos, logrando una densidad de empaquetamiento de alrededor del 36 %. La disposición de 6596 objetos a una densidad de empaquetamiento del 37,30 % tomó dos horas. “Las densidades que conseguimos, cercanas al 40%, son mucho mejores que las obtenidas con los algoritmos tradicionales”, dice Matusik, “y además son más rápidas”.

Este trabajo representa una “solución innovadora al problema de larga data de organizar de manera eficiente los objetos 3D”, comenta Bedrich Benes, profesor de informática en la Universidad de Purdue. “La solución propuesta maximiza la densidad de empaque y se puede utilizar en muchas áreas prácticas, desde la robótica hasta la fabricación. Además, las soluciones sin bloqueo son adecuadas para entornos controlados por computadora”.

Por supuesto, el enfoque puede ser útil en las empresas de almacenamiento y envío donde los diferentes artículos se empaquetan de forma rutinaria en cajas de diferentes tamaños, según Matusik. Sin embargo, él y sus colegas están especialmente interesados ​​en aplicaciones de impresión 3D, también conocida como fabricación aditiva. Las piezas generalmente se producen en lotes y se colocan en bandejas. Sin embargo, los enfoques actuales, dice Matusik, “tienen un uso muy limitado [container] volumen” – generalmente alrededor del 20%. “Si podemos aumentar la densidad del empaque”, agrega, “podemos aumentar la eficiencia general del proceso de impresión, reduciendo así el costo total de las piezas producidas”.

Si bien el papel SIGGRAPH ofrece procedimientos nuevos y mejorados para la impresión 3D, así como para el embalaje de objetos rígidos, el problema de la mejor disposición de objetos deformables u objetos articulados, que consisten en más de una parte rígida conectada por bisagras, aún está abierto, y puede ser abordado en futuros trabajos. Mientras tanto, si las personas pueden meter más de 6.000 objetos en un contenedor en solo dos horas, no hay razón para desesperarse. La ayuda solo puede ser un algoritmo.

Esta historia ha sido republicada por cortesía de MIT News (web.mit.edu/newsoffice/), un popular sitio de noticias sobre investigación, innovación y enseñanza del MIT.