Implementation of algorithms for solving multi-agent path finding problems

Multi-Agent Path Finding (MAPF) is the problem of computing collision-free paths for a team of agents from their current locations to given destinations. Application examples include automated warehouse systems and video games. Several different MAPF algorithms have been presented during the last years, each of which has its pros and cons. In this thesis, we present a tool implementing some of the most used algorithms for solving the MAPF problem. The basic idea is to implement these algorithms in a common scholar programming language, such as Python, which gives the user the possibility to easily understand the key ideas behind these algorithms, allowing him/her to analyze and compare them in different environments and robots configurations. We carry out some experimental activities in order to validate our implementations and compare the different algorithms.

Multi-Agent Path Finding (MAPF) è il problema della pianificazione di percorsi senza collisioni per un team di agenti dalle loro posizioni attuali alle loro destinazioni. Esempi di applicazione includono sistemi di gestione di magazzini automatizzati e videogiochi. Diversi algoritmi MAPF sono stati presentati negli ultimi anni, ognuno dei quali ha i suoi pro e contro. In questa tesi, presentiamo uno strumento che implementa alcuni degli algoritmi più utilizzati per risolvere il problema del MAPF. L'idea di base è implementare questi algoritmi in un comune linguaggio di programmazione accademico, come Python, che offra all'utente la possibilità di comprendere facilmente le idee chiave alla base di questi algoritmi, consentendogli di analizzarli e confrontarli in diversi ambienti e configurazioni di robot. Effettuiamo alcune attività sperimentali al fine di validare le nostre implementazioni e confrontare i diversi algoritmi.