Parallel Path Planning for Multi-Robot Coordination
Jorge Ribeiro, Marina Brilhante, Diogo Miguel Matos, Carlos A. Silva, Héber Sobreira, Pedro Costa · 2025
Multi-robot coordination aims to synchronize robots for optimized, collision-free paths in shared environments, addressing task allocation, collision avoidance, and path planning challenges. The Time Enhanced A* (TEA*) algorithm addresses multi-robot pathfinding offering a centralized and sequential approach. However, its sequential nature can lead to order-dependent variability in solutions. This study enhances TEA* through multi-threading, using thread pooling and parallelization techniques via OpenMP, and a sensitivity analysis enabling parallel exploration of robot-solving orders to improve robustness and the likelihood of finding efficient, feasible paths in complex environments. The results show that this approach improved coordination efficiency, reducing replanning needs and simulation time. Additionally, the sensitivity analysis assesses TEA*'s scalability across various graph sizes and number of robots, providing insights into how these factors influence the efficiency and performance of the algorithm.