A High-Quality and Efficient Trajectory Replanning Method for Quadrotor Swarms Based on Rolling-Horizon Collision Resolution

We propose a high-quality and computationally efficient trajectory replanning method for Unmanned Aerial Vehicle (UAV) swarms, termed RHCR-Opt, which is designed to continuously and efficiently generate multiple collision-free trajectories in dense obstacle environments. RHCR-Opt consists of three layers. The first two layers are the rolling-horizon collision resolution (RHCR) algorithm based on the Conflict-Based Search (CBS), while the third layer focuses on trajectory generation and optimization using Minimum Control (MINCO) trajectories. Within the two-layer RHCR framework, the improved Lifelong Planning A* (LPA*) algorithm incorporating spatiotemporal constraints is proposed and employed as the low-level solver of CBS to satisfy the frequent search requirements for feasible paths under varying spatiotemporal constraints, thereby significantly improving computational efficiency. Furthermore, the rolling-horizon collision resolution concept is adopted in the high-level CBS framework, where only the discovery of collision-free paths within a finite time window is considered. This substantially reduces the computational burden associated with trajectory generation and optimization beyond the time window. At the third layer, a MINCO-based trajectory generation scheme is designed, and a swarm trajectory joint optimization framework with a finite time window is proposed to generate dynamically feasible and collision-free trajectories. In addition, for swarm missions requiring simultaneous arrival, a two-stage temporal coordination optimization method is developed. Extensive simulation experiments demonstrate that, compared with state-of-the-art (SOTA) algorithms on the proposed benchmark, RHCR-Opt achieves significant improvements in both trajectory quality and computational efficiency. In particular, when the swarm size becomes large, the computational efficiency is improved by at least 23.7%.