Real-time multi-quadrotor trajectory generation via distributed receding architecture and hierarchical planning in complex environments

Abstract

Generation of multi-quadrotor trajectories in real-time in complex three-dimensional environments remains a grand challenge. Trajectory planning becomes computationally prohibitive as the number of quadrotors and obstacles increases. This paper proposes the distributed receding architecture-based hierarchical trajectory planning method (drHTP) to tackle this issue. The distributed receding architecture is established to formulate and solve a series of single-quadrotor short-horizon planning problems for reducing the computation complexity. In distributed planning, the time-heuristic priority mechanism is devised to assign a reasonable planning sequence to enhance the convergence performance. The hierarchical planning, including front-end initial trajectory generation and back-end trajectory optimization, is introduced for the single-quadrotor in each short horizon to further reduce the computation time. The sparse A* search algorithm is modified to only consider adjacent obstacles for obtaining the initial trajectory rapidly. The convergence of drHTP is analyzed theoretically. Numerical simulations with moving and dense obstacle scenarios are carried out to verify the effectiveness of drHTP. The comparative simulation results demonstrate that drHTP outperforms the state-of-the-art distributed sequential convex programming and distributed model predictive control methods in terms of computational efficiency. drHTP is also validated by the physical experiment in an indoor testbed.

Keywords: Distributed receding architecture; Geometric path planning; Inequality-constrained quadratic programming; Multiple quadrotors; Real-time trajectory generation.