Distributed Swarm Trajectory Optimization for Formation Flight in Dense Environments

Lun Quan, Longji Yin, Chao Xu, Fei Gao

TL;DR

Researchers from Zhejiang University have developed a new optimization-based method that allows drone swarms to maintain complex formations while navigating through dense, obstacle-filled environments. By using a novel, differentiable "formation similarity metric" based on graph theory, the swarm can autonomously scale, rotate, and deform its shape to squeeze through tight spaces without losing its overall structure.

What Problem Does This Paper Address?

Navigating a swarm of drones in a specific formation (like a hexagon or a heart shape) is easy in open skies but incredibly difficult in "cluttered" environments like forests or narrow corridors.

Current approaches usually fall into two traps:

  1. Rigidity: They treat the formation as a rigid cage. If an obstacle is in the way, the drones either hit it or the formation "breaks" as drones scatter to save themselves.
  2. Local Minima: Many methods use "potential fields" (think of drones and obstacles as magnets repelling each other), which often causes drones to get stuck in "deadlocks" when trying to pass through narrow gaps.

The challenge is finding a mathematical way to tell a swarm: "Keep this shape, but feel free to shrink or turn it if that helps you get through the gap safely."

Methods

The core innovation is a Differentiable Formation Similarity Metric.

  • Graph-Based Modeling: The authors model the swarm as an undirected graph where drones are vertices and the distances between them are edges.
  • The Laplacian Matrix: They use a "Symmetric Normalized Laplacian" matrix to represent the formation. The beauty of this mathematical tool is that it captures the shape of the formation while remaining invariant to translation, rotation, and scaling.
  • Trajectory Optimization: This metric is plugged into a spatial-temporal optimization framework called MINCO. The system minimizes a joint cost function that balances:
  • Formation Similarity: Staying close to the desired shape.
  • Obstacle Avoidance: Staying away from objects (using Euclidean Signed Distance Fields).
  • Swarm Reciprocal Avoidance: Ensuring drones don't hit each other.
  • Dynamic Feasibility: Ensuring the planned path doesn't exceed the drone's physical limits (speed/acceleration).

Because the metric is differentiable, the researchers can use efficient solvers (like L-BFGS) to generate smooth, collision-free trajectories in just milliseconds.

Datasets

As a robotics paper, the evaluation relies on custom simulation environments and real-world flight tests rather than standard static datasets:

  • Simulated Environments: A 30x15m area with varying obstacle densities (Sparse, Medium, Dense) containing up to 300 cylinder and 80 circular obstacles.
  • Real-World Testing: Conducted using a fleet of quadrotors equipped with Intel RealSense depth cameras and onboard Nvidia Jetson Xavier NX computers.

Key Insights and Ideas

  • Shape over Position: Traditional methods penalize drones for deviating from a specific coordinate. This paper penalizes deviation from a graph structure. This allows the entire swarm to "drift" or "shrink" as a unit, which is much more natural for fluid navigation.
  • The Power of Invariance: Because the metric doesn't care if the swarm is upside down or half its original size, the optimizer can find "sneaky" solutions—like a tetrahedron formation rotating 45 degrees to fit through a narrow vertical slit—that rigid methods would never consider.
  • Distributed Intelligence: Each drone plans its own path based on broadcasted information from its neighbors, making the system resilient to single-point failures.

Key Results

The method was benchmarked against two state-of-the-art approaches (Zhou et al. and Turpin et al.):

  • Success Rate: In "Dense" environments, the proposed method achieved a 95% success rate, while baselines dropped to 0% and 60% respectively.
  • Accuracy: The method maintained significantly lower "Position Error" ($e_{dist}$) and "Similarity Error" ($e_{sim}$) compared to Turpin’s method, which often saw drones taking wildly different routes to avoid obstacles, effectively destroying the formation.
  • Real-World Robustness: The team successfully flew a 7-drone hexagonal formation through a forest of pillars and a 4-drone tetrahedron through a narrow corridor, demonstrating real-time adaptation.

Limitations and Future Work

While the results are impressive, the authors note a few areas for improvement:

  • Communication Constraints: The system currently assumes drones can reliably broadcast their trajectories to one another. In environments with heavy interference or long distances, this could fail.
  • Extreme Deadlocks: In "hyper-dense" environments, the swarm might still encounter deadlocks. The authors suggest that task reassignment (letting drones swap positions in the formation) could be a necessary next step.
  • Narrowing Bandwidth: Future work will look at how to maintain these formations when the communication range between robots is unpredictably restricted.

Summary updated

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 surroundings11https://www.youtube.com/watch?v=lFumtOrJci4. We will release the source code for the reference of the community22https://github.com/ZJU-FAST-Lab/Swarm-Formation.
BibTeX
@inproceedings{quan2022distributed,
  author = {Lun Quan and Longji Yin and Chao Xu and Fei Gao},
  title = {{Distributed Swarm Trajectory Optimization for Formation Flight in Dense Environments}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2022},
  url = {https://openreview.net/forum?id=dPyKlbl4tj},
}

Loading related content...

Figure