Real-Time Multi-Robot Mission Planning in Cluttered Environment

Addressing a collision-aware multi-robot mission planning problem, which involves task allocation and path-finding, poses a significant difficulty due to the necessity for real-time computational efficiency, scalability, and the ability to manage both static and dynamic obstacles and tasks within a complex environment. This paper introduces a parallel real-time algorithm aimed at overcoming these challenges. The proposed algorithm employs an approximation-based partitioning mechanism to partition the entire unassigned task set into several subsets. This approach decomposes the original problem into a series of single-robot mission planning problems. To validate the effectiveness of the proposed method, both numerical and hardware experiments are conducted, involving dynamic obstacles and tasks. Additionally, comparisons in terms of optimality and scalability against an existing method are provided, showcasing its superior performance across both metrics. Furthermore, a computational burden analysis is conducted to demonstrate the consistency of our method with the observations derived from these comparisons. Finally, the optimality gap between the proposed method and the global optima in small-size problems is demonstrated.