2013/02/12 by Michal Čáp, Čáp, Michal, Peter Novák +5 · 6 citations
Computer Science · Engineering · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Fluid Dynamics Simulations and Interactions #Multiagent Systems (cs.MA) #Robotic Path Planning Algorithms #Robotics (cs.RO) #Robotics and Sensor-Based Localization
paper · pdf · doi:10.48550/arxiv.1302.2828
openalex publication_date 2013/02/12 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
Cooperative pathfinding is a problem of finding a set of non-conflicting trajectories for a number of mobile agents. Its applications include planning for teams of mobile robots, such as autonomous aircrafts, cars, or underwater vehicles. The state-of-the-art algorithms for cooperative pathfinding typically rely on some heuristic forward-search pathfinding technique, where A* is often the algorithm of choice. Here, we propose MA-RRT*, a novel algorithm for multi-agent path planning that builds upon a recently proposed asymptotically-optimal sampling-based algorithm for finding single-agent shortest path called RRT*. We experimentally evaluate the performance of the algorithm and show that the sampling-based approach offers better scalability than the classical forward-search approach in relatively large, but sparse environments, which are typical in real-world applications such as multi-aircraft collision avoidance.