A Two-Stage Swarm Planning Framework for Efficient Multi-Drone Waypoint Traversal

Abstract

The multi-drone waypoint traversal has significant potential for aerial robot swarms in various applications. However, it still faces challenges including low time efficiency, susceptibility to local minima, poor resilience to external disturbances, high computational complexity, and high communication burden. To address these issues, we propose a two-stage swarm planning framework by integrating an offline global trajectory generator and an online distributed local trajectory planner. This approach not only ensures time-optimality but also enhances resistance to external disturbances. Specifically, a complementary progress constraint (CPC)-based global trajectory planning method is first presented to generate globally optimal reference trajectories. Then, by taking these trajectories as global guidance, a local planner is designed to guarantee collision-free traversal. In the local planner, we present a distributed local re-planning algorithm by embedding the positional constraints constructed by Voronoi diagrams into the model predictive contouring control (MPCC). The drones only exchange their position information, significantly reducing the communication load. Additionally, the Voronoi-based spatial constraints allow the swarms to eliminate the collision risk caused by asynchronous communication. To reduce onboard computational resource requirements, the local planner adopts the real-time iteration (RTI) technique, executing the optimization only once per control cycle. Both simulation and real-world experiments demonstrate that our approach outperforms state-of-the-art methods in terms of waypoint tracking accuracy, safety, and global time optimality.