Graph attentional neural network in multi-agent pickup and delivery problems

Multi Agent Path Finding problems and its lifelong versions, Multi Agent Pickup and Delivery problems, have gained a lot of attention in recent years. Their key concept is to have moving agents performing different tasks in a known environment while avoid crashing into each others. Several of their fields of application, like automated warehouses and video games, have seen an increasing demand of algorithms that could achieve real-time performance with up to hundreds or even thousands of agents. This need for scalability drove many researchers towards Machine Learning techniques, which are well-suited for handling computational by demanding tasks. However, most of the work is done towards solving MAPF problems, while MAPD has seen less interest, despite being more used in practice. This thesis is focused around developing a Deep Learning model able to solve MAPD problems in a scalable and efficient way. The main contribution is the application of a novel technology, the Graph Attention Neural Networks, in order to learn communication between agents. Using this network, agents are able to assign different importance measures to messages coming from different neighbours, effectively selecting who to listen or not when deciding where to move. In this way, information about goals and future movements are shared amongst agents improving coordination in local movement decisions, highly required for solving MAPD problems. The learning procedure is carried on using Imitation Learning over an expert algorithm: Token Passing is the algorithm of choice, a state-of-art MAPD solver which already shows scalability properties. While our results are not showing performance able to suggest any practical use, the experience provides some elements that could be useful for future lines of research on the topic.

Multi Agent Path Finding e la sua versione permanente, Multi Agent Pickup and Delivery, hanno guadagnato molto interesse negli ultimi anni. In questi problemi, diversi agenti svolgono compiti muovendosi in un ambiente noto, evitando di scontrarsi l'uno con l'altro. Molti dei loro campi di applicazione, come magazzini automatici e videogiochi, hanno visto negli ultimi anni una crescente domanda di algoritmi in grado di gestire centinaia o addirittura migliaia di agenti. Questa esigenza di scalabilità ha spinto molti gruppi di ricerca verso l'utilizzo di tecniche di Machine Learning, in quanto adatte a gestire compiti con requisiti computazionali elevati. Tuttavia, la maggior parte delle ricerche si concentrano sul risolvere i problemi MAPF, mentre MAPD riscontra meno interesse nonostante sia molto diffuso nella pratica. Per questi motivi, questa tesi è focalizzata sullo sviluppo di un modello di Deep Learning in grado di risolvere i problemi MAPD in modo scalabile ed efficiente. Il contributo principale è l'applicazione di una nuova tecnologia, chiamata Graph Attention Neural Network, al fine di apprendere la comunicazione tra agenti. Utilizzando questa rete, gli agenti sono in grado di assegnare diverse misure di importanza ai messaggi provenienti dagli agenti vicini, selezionando efficacemente chi ascoltare o meno nella scelta dell'azione da eseguire. In questo modo, le informazioni sugli obiettivi e sui movimenti futuri vengono condivise tra gli agenti migliorando il coordinamento, un fattore altamente necessario per risolvere i problemi MAPD. La procedura di apprendimento viene svolta utilizzando Imitation Learning basato su un algoritmo extit{esperto}: per questo lavoro è stato usato Token Passing, un algoritmo allo stato dell'arte per MAPD, non basato su machine learning e già relativamente scalabile. Sebbene i nostri risultati non mostrino prestazioni in grado di suggerire alcun uso pratico, l'esperienza risulta comunque utile a delineare future linee di ricerca.