Abstract
For aerial swarms, navigation in a prescribed formation is widely practiced in various scenarios. However, the associated planning strategies typically lack the capability of avoiding obstacles in cluttered environments. To address this deficiency, we present an optimization-based method that ensures collision-free trajectory generation for formation flight. In this paper, a novel differentiable metric is proposed to quantify the overall similarity distance between formations. We then formulate this metric into an optimization framework, which achieves spatial-temporal planning using polynomial trajectories. Minimization over collision penalty is also incorporated into the framework, so that formation preservation and obstacle avoidance can be handled simultaneously. To validate the efficiency of our method, we conduct benchmark comparisons with other cutting-edge works. Integrated with an autonomous distributed aerial swarm system, the proposed method demonstrates its efficiency and robustness in real-world experiments with obstacle-rich surroundings. We will release the source code for the reference of the community.
Introduction
Navigating a swarm of Unmanned Aerial Vehicles (UAVs) in a specific formation is a fundamental capability for many applications, ranging from surveillance to artistic displays. However, maintaining these formations in "cluttered" environments—such as dense forests or narrow corridors—presents significant challenges. Traditional planning strategies often treat formations as rigid structures, which can lead to collisions or complete formation breakage when obstacles are encountered. Furthermore, common potential field-based methods frequently suffer from local minima, causing "deadlocks" where drones get stuck in narrow passages. This paper addresses these deficiencies by proposing an optimization-based method for collision-free formation flight that allows for autonomous scaling, rotation, and deformation.
Differentiable Formation Similarity Metric
The core innovation of this research is a Differentiable Formation Similarity Metric. Rather than penalizing drones for deviating from specific global coordinates, this metric focuses on the underlying graph structure of the swarm. The swarm is modeled as an undirected graph where drones are vertices and the inter-drone distances are edges.
By utilizing a Symmetric Normalized Laplacian matrix, the formation's shape is represented in a way that is invariant to translation, rotation, and scaling. This metric is integrated into the MINCO (Minimum Control) spatial-temporal optimization framework. The joint cost function balances several critical factors:
- Formation Similarity: Maintaining the desired relative shape.
- Obstacle Avoidance: Utilizing Euclidean Signed Distance Fields to stay clear of objects.
- Swarm Reciprocal Avoidance: Ensuring drones do not collide with one another.
- Dynamic Feasibility: Respecting the physical limits of the UAVs (velocity and acceleration).
Because the metric is differentiable, efficient solvers like L-BFGS can generate smooth, collision-free trajectories in milliseconds, enabling real-time adaptation to complex surroundings.
Experimental Results
The proposed method was rigorously evaluated in both simulated and real-world environments. In simulations featuring dense obstacle configurations (up to 300 cylinders), the method achieved a 95% success rate, significantly outperforming state-of-the-art baselines which often dropped to 0% success in similar conditions.
Real-world experiments utilized a fleet of quadrotors equipped with depth cameras and onboard computing. The swarm successfully navigated a 7-drone hexagonal formation through a pillar forest and a 4-drone tetrahedron through a narrow corridor. These tests demonstrated the system's ability to autonomously "squeeze" through tight spaces by scaling or rotating the formation as a unit, maintaining structural integrity where rigid methods would fail.
Conclusion
This work presents a robust framework for distributed swarm formation flight in dense environments. By prioritizing formation similarity over rigid positioning and leveraging a differentiable graph-based metric, the system achieves high success rates and fluid navigation in cluttered spaces. Future work will focus on addressing communication constraints in high-interference environments and exploring task reassignment strategies to further mitigate extreme deadlock scenarios in hyper-dense surroundings.
Summary updated