Crean algoritmo para empacar eficientemente

En el MIT acaban de dar con una fórmula para llenar su 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.

¿Cómo puedo meter esto ahí? La pregunta quizás parezca simple. La respuesta, no.

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“, “Dense, intelocking-free and Scalable Spectral Packing“.

“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 computador 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.

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 indica Bedrich Benes, profesor de informática en la Universidad Purdue.

Además, las soluciones sin interbloqueo son adecuadas para entornos controlados por computador“. No son sus únicas aplicaciones.

El método del MIT puede resultar útil en almacenes y empresas de transporte o impresión 3D.

Fuente: MIT News