Teng Guo, Si Wei Feng and Jingjin Yu

For enabling efficient, large-scale coordination of unmanned aerial vehicles (UAVs) under the labeled setting, in this work, we develop the first polynomial time algorithm for the reconfiguration of many moving bodies in three-dimensional spaces, with provable 1.x asymptotic makespan optimality guarantee under high robot density. In contrast, it is well-known that multi-robot path planning is NP-hard to optimally solve. In numerical evaluations, our method readily scales to support the motion planning of over 100, 000 robots in 3D while simultaneously achieving 1.x optimality. We demonstrate the application of our method in coordinating many quadcopters in both simulation and hardware experiments.

Published in the 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2022). This is the recorded IROS talk.

свернуть