In recent years Multi-Agent Path Finding (MAPF) has become one of the most challenging and interesting fields in robotics and artificial intelligence. MAPF consists in the computation of collision-free paths for a group of agents from their location to an assigned goal. Many algorithms exist in the literature, solving this problem with a centralized approach. However, these models are well-suited for simple problems, with a few agents, and they are not capable of scaling up to complex scenarios with hundreds or thousands of agents. The results achieved in the field of Deep Reinforcement Learning (DRL) opens up the possibility of applying these techniques to MAPF. Despite requiring extensive training, the learning-based approach scales better than traditional models in complex environments, thanks to their decentralized execution. This thesis proposes a comparison between these two different classes of methods, trying to extrapolate the real strengths and weaknesses of the algorithms. Different from previous comparisons made into simple random environments, our tests are performed in three realistic warehouse environments, that evaluate the behavior of the models in typical realistic MAPF challenges. We carefully adapted both centralized and learning-based MAPF algorithms for these environments. Our analysis evaluates key performance metrics such as success rate, computational efficiency, path quality, and collisions. We found that some learning-based models could nearly match the performance of centralized methods, proving their potential as a viable option for future applications. By highlighting the differences between centralized and learning-based methods, we hope to make a step forward towards more adaptable and efficient multi-agent coordination solutions.

Negli ultimi anni, la ricerca sulla pianificazione di percorsi multi-agente in ambienti fisici (Multi-Agent Path Finding or MAPF) è diventata uno dei campi più stimolanti e interessanti della robotica e dell'intelligenza artificiale. Risolvere un problema MAPF, consiste nel calcolare percorsi senza collisioni per un gruppo di agenti, dalla loro posizione a un obiettivo assegnato. Esistono molti algoritmi in letteratura che risolvono questo problema con un approccio centralizzato. Tuttavia, questi modelli sono adatti a problemi semplici, con pochi agenti, e non sono in grado di scalare bene a scenari più complessi con centinaia o migliaia di agenti. I risultati ottenuti nel campo del Deep Reinforcement Learning (DRL) aprono la possibilità di applicare questo tipo di tecniche ai problemi MAPF. Sebbene richieda un addestramento intensivo, l'approccio basato sull'apprendimento consente una migliore scalabilità rispetto ai modelli tradizionali grazie alla sua esecuzione decentralizzata. Questo lavoro di tesi propone un confronto tra questi due diversi approcci, cercando di estrapolare i reali punti di forza e di debolezza degli algoritmi proposti. A differenza dei precedenti confronti effettuati in semplici ambienti generati casualmente, i nostri test vengono eseguiti in tre mappe realistiche di magazzini, al fine di valutare il comportamento dei modelli in tipici contesti MAPF. Abbiamo adattato con attenzione sia gli algoritmi MAPF centralizzati che quelli basati sull'apprendimento per questi ambienti. La nostra analisi valuta metriche chiave delle prestazioni come tasso di successo, efficienza computazionale, qualità del percorso e collisioni. Abbiamo scoperto che alcuni modelli basati sull'apprendimento automatico sono stati in grado quasi di eguagliare le prestazioni dei metodi centralizzati, candidandosi come valida opzione per applicazioni future. Evidenziando le differenze tra i metodi centralizzati e quelli basati sull'apprendimento, speriamo di compiere un passo avanti verso soluzioni di coordinamento multi-agente più adattabili ed efficienti.