Analysis of the influence of graph characteristics on MAPFW algorithm performance
More Info
expand_more
expand_more
Abstract
The Multi-Agent Path Finding (MAPF) problem is a problem in which a route must be found for multiple agents such that they do not collide. The Multi-Agent PathFinding with Waypoints problem extends this problem by adding waypoints that the agents must visit before travelling to their end location. This paper compares five algorithms for MAPF that have been extended to incorporate waypoints. It also analyzes which influence map characteristics like corridors, chokepoints, overlapping waypoints and the average degree have on the performance of these algorithms. It concludes that EMLA and WM* perform best overall with some variations per characteristic.
Files
Analysis_of_the_influence_of_g... (pdf)
(pdf | 0.664 Mb)