Polynomial Time Near-Time-Optimal Multi-Robot Path Planning in Three Dimensions with Applications to Large-Scale UAV Coordination
Teng Guo,Si Wei Feng,Jingjin Yu,Teng Guo,Si Wei Feng,Jingjin Yu
For enabling efficient, large-scale coordination of unmanned aerial vehicles (UAV s) 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. More precisely, on an $m_{1} \times m_{2} \times m_{3}$ grid, $m...
