Learning-guided Guided Tetris Beam for efficient robotic bin packing

The origins of logistics come from the needs of ancient civilizations of procurement and transport of goods in order to survive. In recent years, logistics has become a formal research area. Within the field of logistics, thanks to the rapid growth in robotic manipulation in the last decades, there has been an increased demand for automation applied to the so called Bin Packing Problem (BPP), which arises to cope with the efficient packing of items into a finite number of containers. There exist different types of Bin Packing Problems and each of them is characterized by a multitude of solution algorithms which differ mainly in the heuristic method chosen to find a placement for each item. One of the most efficient methods is the Tetris Beam Search (TBS) algorithm, which deals with the loading of a highly heterogeneous set of cuboidal items into a series of identical pallets, by combining a Beam Search (BS) algorithm with a constructive heuristic called Tetris Heuristic (TH). This thesis focuses on the integration of a Machine Learning model to the TBS algorithm in order to improve its performance. This was achieved by introducing the Learning Beam Search (LBS) algorithm into the original TBS one: the key idea of LBS is to use a Machine Learning model, and more specifically an Artificial Neural Network (ANN), as a guidance function in the Beam Search algorithm, with the aim of approximating the maximum further length to go from a current node to reach a target one. Key problems addressed include the implementation of the TBS algorithm’s code starting from its pseudocode, the development of a Nested Beam Search with the aim of collecting training dataset for the ANN, and the training of the latter by finding the correct hyperparameters. Experimental results showcase the improvement introduced by the application of the LBS principle to the original TBS algorithm. Furthermore, the real-world process of packing an order placed via an e-commerce platform has been recreated by making use of the improved version of the TBS algorithm to determine the products’ arrangement in the box, combined with a robotic manipulator for the physical packing of the items.

Le origini della logistica risalgono all’esigenza delle civiltà antiche di approvvigionamento e trasporto delle merci per sopravvivere. In epoca recente, la logistica è diventata un’area di ricerca formale. Nel campo della logistica, data la rapida crescita della robotica negli ultimi decenni, l’applicazione dell’automazione al cosiddetto Bin Packing Problem è in aumento. Per "Bin Packing Problem" (BPP) si intende un problema di ottimizzazione il cui obiettivo è l’imballaggio efficiente di un insieme di oggetti in un numero minimo di contenitori. Esistono diverse versioni di BPP e ciascuna di esse è caratterizzata da una moltitudine di algoritmi risolutivi che differiscono tra loro principalmente per il metodo euristico scelto per trovare una collocazione a ciascun elemento. Uno dei più efficienti è l’algoritmo Tetris Beam Search (TBS), che si occupa del posizionamento di un insieme altamente eterogeneo di oggetti dalla forma cuboidale in una serie di pallet identici tramite la combinazione dell’algoritmo di Beam Search (BS) con un’euristica costruttiva chiamata Tetris Heuristic (TH). Questa tesi si incentra sull’integrazione di un modello di Machine Learning all’algoritmo TBS al fine di migliorarne le prestazioni. Ciò è stato eseguito tramite l’applicazione dell’algoritmo Learning Beam Search (LBS), la cui idea chiave è quella di utilizzare un modello di Machine Learning, e più specificamente una Rete Neurale Artificiale (RNA), come funzione guida nell’algoritmo Beam Search. I problemi chiave affrontati includono l’implementazione del codice dell’algoritmo TBS a partire dal suo pseudocodice, lo sviluppo di una Nested Beam Search con l’obiettivo di raccogliere il set di dati di addestramento per l’RNA e l’addestramento di quest’ultima trovandone gli iperparametri corretti. I risultati sperimentali mostrano il miglioramento introdotto dall’applicazione del principio LBS all’algoritmo TBS originale. Inoltre, è stato ricreato il processo reale di imballaggio di un ordine effettuato tramite una piattaforma di e-commerce utilizzando la versione migliorata dell’algoritmo TBS per determinare la disposizione dei prodotti nella scatola, facendo uso di un robot per effettuare l’imballaggio fisico degli articoli.