Experimental Evaluation of Roadmap-Based Map Generation with Continuous-Time Conflict-Based Search for Multi-Agent Pathfinding

This article presents an experimental evaluation of a Multi-Agent Pathfinding (MAPF) approach for large-scale robotic fleets operating in diverse outdoor environments. We generated three distinct types of roadmap graphs: Constrained Delaunay Triangulation (CDT), Voronoi Diagram (VD), and Grid-derived from an obstacle file, and assessed their quality using metrics obtained from graph theory. Then, the performance of the Continuous-time Conflict-Based Search (CCBS) algorithm was evaluated across three different environmental maps, considering practical performance metrics including makespan and failure rate. Subsequently, the roadmap generation methods were ranked based on CCBS performance in similar scenarios using the Friedman statistical test. The results indicate that CDT outperforms both VD and Grid maps, even though it does not exhibit the best graph metrics in many environments. CDT's superior performance is attributed to its enhanced interconnectedness and the availability of multiple pathways, as evidenced by its balanced metrics and structural properties. We show that CDT is the most efficient and reliable roadmap generation technique for multiagent systems under our experimental conditions making it a preferred choice for robust pathfinding.