Polynomial Time Near-Time-Optimal Multi-Robot Path Planning in Three Dimensions with Applications to Large-Scale UAV Coordination

Abstract

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. <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$x$</tex> asymptotic makespan optimality guarantee under high robot density. More precisely, on an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m_{1} \times m_{2} \times m_{3}$</tex> grid, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m_{1}\geq m_{2}\geq m_{3}$</tex> , our method computes solutions for routing up to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\displaystyle \frac{m_{1}m_{2}m_{3}}{3}$</tex> uniquely labeled robots with uniformly randomly distributed start and goal configurations within a makespan of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m_{1}+2m_{2}+2m_{3}+o(m_{1})$</tex> , with high probability. Because the makespan lower bound for such instances is <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m_{1}+m_{2}+m_{3}-o(m_{1})$</tex> , also with high probability, as <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m_{1}\displaystyle \rightarrow\infty, \frac{m_{1}+2m_{2}+2m_{3}}{m_{1}+m_{2}+m_{3}}$</tex> optimality guarantee is achieved. <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\displaystyle \frac{m_{1}+2 m_{2}+2m_{3}}{m_{1}+m_{2}+m_{3}}\in\left(1, \displaystyle \frac{5}{3}\right]$</tex> , yielding 1. <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$x$</tex> optimality. 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. <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$x$</tex> optimality. We demonstrate the application of our method in coordinating many quadcopters in both simulation and hardware experiments.