Ni las horas de carretera, ni las colas para comprar un refresco, ni siquiera las peleas para hacerse con una parcelita de arena en la que plantar la sombrilla y extender la toalla. Si hay un desafío realmente duro en las escapadas de verano a la playa es apañárselas para que la nevera, palas, cubos y demás equipaje veraniego entren en el maletero del coche. O así era hasta ahora. En el MIT acaban de dar con una fórmula para llenar tu maletero o cualquier otro lugar, por más reducido que sea su espacio y voluminosa la carga, con la pericia de un maestro del Tetris.
De juego, eso sí, tiene muy poco.
¿Cómo puedo meter esto ahí? La pregunta quizás parezca simple. La respuesta, no. Lo de buscar la forma más eficiente de almacenar objetos en un espacio limitado es algo que te planteas tú al trastear con los cajones de la cocina, el frutero cada vez que apila manzanas y naranjas y los domingueros cuando tienen que llenar sus mochilas, pero eso no significa que sea una cuestión sencilla. Ni mucho menos. Hace ya bastante tiempo, en 1611, el mismísimo Johannes Kepler le daba vueltas a cuál era la forma más inteligente de apilar bolas de cañón.
Han pasado de aquello más de cuatro siglos y si bien ya sabemos cómo agrupar esferas de forma uniforme, lo de apilar de manera óptima objetos tridimensionales de diferentes tamaños y formas sigue siendo todo un reto. Tanto, de hecho, que el MIT recuerda que en teoría de la complejidad computacional se considera un "NP-hard", es decir, un problema que no podemos resolver ni siquiera de forma aproximada sin pasarnos años o décadas haciendo cálculos.
¿Y cómo solucionarlo? Esa es la pregunta que se han hecho un grupo de investigadores del MIT e Inkbit, una compañía de Massachusetts que trabaja con visión artificial. Para solucionarlo desarrollaron un método computacional, una técnica que han bautizado "SSP" —del inglés "Dense, intelocking-free and Scalable Spectral Packing"— y prevén presentar el mes que viene durante la conferencia internacional SIGGRAPH 2023. Antes y a modo de anticipo han preparado un artículo que puede consultarse ya a través de las webs de Inkbit y el MIT.
"Es como el Tetris". La expresión es de Wojciech Matusik, profesor del MIT y cofundador de Inkbit, y capta bastante bien la filosofía del método que acaban de desarrollar. El "SSP" trabaja básicamente con una lista de objetos tridimensionales y un contenedor que se encarga de dividir en vóxeles, cubos que se representan en una cuadrícula 3D y ayudan a visibilizar con exactitud qué partes están ocupadas y cuáles vacías. "Cada uno puede tener un tamaño de apenas un milímetro cúbico", apunta el MIT. Con las piezas que hay que apilar se sigue un proceso similar.
"Para conocer el espacio disponible, el algoritmo calcula una cantidad llamada métrica de colisión en cada vóxel. Para ello, coloca el centro del objeto en cada vóxel del contenedor y cuenta el número de vóxeles ocupados con los que el objeto se solapa o 'colisiona'. El objeto solo puede colocarse en lugares donde el solapamiento sea cero, es decir, donde no haya colisiones", señala.
¿Y el siguiente paso? Consiste en cribar las diferentes ubicaciones posibles y decidir cuál es la mejor posición para el objeto. El proceso, claro está, no se deja al azar ni la intuición. Los investigadores calculan una nueva métrica para cada vóxel que se encarga de "maximizar la densidad de empaquetamiento". Básicamente, se encarga de medir los huecos entre el objeto y la pared del contenedor o el resto de las piezas apiladas. El objetivo es muy sencillo: minimizar los huecos que quedan libres, igual que en el popular juego lanzado en los años 80 por Pajitnov.
El proceso es algo más enrevesado, ya que el ordenador juega con múltiples orientaciones para un mismo objeto. Cuando al fin ha dado con la mejor posición el algoritmo SSP se encarga de confirmar luego que el objeto entra en el lugar que se le asigna y podrá separarse del resto una vez se desempaquete. "El embalaje debe estar 'libre de enclavamientos', una condición para evitar configuraciones como los anillos entrelazados", señala el MIT. Con el propósito de facilitar los cálculos, el equipo usó la transformada rápida de Fourier (FFT), una técnica matemática que asegura que no se había utilizado antes en embalajes.
¿Y cuánto tarda? Un tiempo digno de un maestro del Tetris. Durante una demostración el algoritmo logró apilar de forma eficiente 670 piezas en solo 40 segundos. Para colocar 6.596 fueron necesarias dos horas. En el primer caso la densidad de empaquetamiento fue del 36% y en el segundo de poco más del 37%. "Las densidades, cercanas al 40%, son significativamente mejores que las logradas por los algoritmos tradicionales y también son más rápidas", reivindica Matusik.
"La solución que se propone maximiza la densidad de empaquetamiento y tiene potencial para encontrar aplicaciones en muchas áreas prácticas, desde la robótica a la fabricación —abunda Bedrich Benes, profesor de informática en la Universidad Purdue—. Además, las soluciones sin interbloqueo son adecuadas para entornos controlados por ordenador". No son sus únicas aplicaciones. El método del MIT puede resultar útil en almacenes y empresas de transporte o impresión 3D.
Imágenes: MIT
Ver 2 comentarios