Implementation and optimization of conflict-based search algorithms for 3D multi-agent drone navigation

This thesis addresses the critical problem of multi-agent pathfinding (MAPF) in 3D urban environments, specifically focusing on autonomous drone navigation in densely populated areas. MAPF is essential in scenarios where multiple agents, such as delivery drones, must navigate efficiently and safely while avoiding conflicts. Given the rising demand for autonomous delivery systems in urban spaces, efficient and reliable pathfinding solutions are increasingly relevant. The core of this work is the implementation and optimization of Conflict-Based Search (CBS) algorithms, with a particular focus on the Meta-agent CBS (MA-CBS) variant. CBS resolves conflicts between agents through constraint-based strategies, while MA-CBS extends this approach by merging agents with high conflict potential into meta-agents, thus improving overall coordination efficiency. A novel contribution of this thesis is the integration of the B-manager, a dynamic parameter that adaptively controls the threshold for merging agents, enhancing MA-CBS performance in high-density scenarios. \\ The research methodology involves deploying CBS and MA-CBS within a MATLAB-based 3D grid environment that replicates real-world urban layouts. The results show a significant improvement in success rates when employing MA-CBS over the classic CBS, particularly in environments characterized by high agent density and constrained navigation spaces. However, performance was impacted by a strict 60-second time constraint, highlighting the trade-off between computational efficiency and solution quality. These findings confirm the theoretical robustness of MA-CBS and underscore its potential applicability in real-world multi-agent navigation tasks, such as autonomous delivery in urban areas.

Questa tesi affronta il problema cruciale del pathfinding multi-agente (MAPF) in ambienti urbani 3D, concentrandosi specificamente sulla navigazione autonoma di droni in aree densamente popolate. Il MAPF è essenziale in scenari in cui più agenti, come i droni per le consegne, devono navigare in modo efficiente e sicuro evitando conflitti. Data la crescente domanda di sistemi di consegna autonomi negli spazi urbani, soluzioni di pathfinding efficienti e affidabili risultano sempre più rilevanti. Il nucleo di questo lavoro è l'implementazione e l'ottimizzazione di algoritmi di Conflict-Based Search (CBS), con particolare attenzione alla variante Meta-agent CBS (MA-CBS). CBS risolve i conflitti tra agenti attraverso strategie basate su vincoli, mentre MA-CBS estende questo approccio unendo agenti con alto potenziale di conflitto in meta-agenti, migliorando così l'efficienza della coordinazione complessiva. Un contributo innovativo di questa tesi è l'integrazione del B-manager, un parametro dinamico che controlla in modo adattivo la soglia per l'unione degli agenti, migliorando le prestazioni di MA-CBS in scenari ad alta densità. La metodologia di ricerca prevede il dispiegamento di CBS e MA-CBS all'interno di un ambiente a griglia 3D in MATLAB che replica layout urbani realistici. I risultati mostrano un miglioramento significativo dei tassi di successo utilizzando MA-CBS rispetto al CBS classico, in particolare in ambienti caratterizzati da alta densità di agenti e spazi di navigazione limitati. Tuttavia, le prestazioni sono state influenzate da un rigoroso limite di tempo di 60 secondi, evidenziando il compromesso tra efficienza computazionale e qualità della soluzione. Questi risultati confermano la robustezza teorica di MA-CBS e ne evidenziano la potenziale applicabilità in compiti di navigazione multi-agente nel mondo reale, come le consegne autonome in aree urbane.