RE-Formation: Resilient and Efficient Formation Planning in Large-Scale Distributed Aerial Swarms
Yuan Zhou, Lun Quan, Guangtong Xu, Chao Xu, Fei Gao
AI summary
Problem
Large-scale aerial swarm formation planning suffers from computational intractability due to limited onboard resources and high vulnerability to cascading failures from abnormal agents in fully-connected networks.
Approach
The method replaces computationally heavy complete graphs with a globally rigid, feature-preserving sparse graph constructed via closed-form submatrix selection, and filters out failed agents by approximating the maximum clique using maximum k-core computation.
Key results
- Closed-form Max-Trace metric enables real-time construction of globally rigid sparse graphs
- GRPF sparse graphs preserve complete graph structural features while drastically reducing computational complexity
- Agent failures are treated as outliers and rejected via linear-complexity maximum k-core approximation
- Achieves ~10x planning speedup over baselines for 80+ drones and successfully plans 100-drone formations in simulation and real-world tests
Why it matters
Provides a scalable, fault-tolerant planning framework essential for deploying large-scale drone swarms in resource-constrained and failure-prone real-world environments.
Abstract
Due to the limited online computational resources and the inherent probability of hardware and software failures of real-world robots, large-scale formation planning faces two common challenges: computational intractability and agent failures. Based on the theory of sparse graphs and the maximum clique, we achieve a resilient and efficient formation planning (RE-Formation) to address these issues. To improve the computational efficiency of trajectory planning while ensuring flexible formation maneuvers, we introduce sparse graphs to describe connection relationships and present a sparse graph construction method with closed-form solutions. The sparse graphs ensure the Global Rigidity for uniquely corresponding to a geometric shape and Preserve the main Features of complete graphs, denoted as the GRPF sparse graph. To prevent the impact of abnormal agents, the problem of elimi- nating abnormal agents is transformed into an outlier rejection problem that can be solved by computing the maximum clique. We approximate the maximum clique by periodically triggering the calculation of the maximum k-core to meet the real-time computational demands of large-scale swarms. We validate the performance through real-world experiments and implement formation planning with 100 drones in simulation. Benchmark comparisons and ablation experiments demonstrate the effectiveness of our method. Abstract—In this paper, we address the challenges of large- scale aerial swarm formation planning, focusing on compu- tational efficiency and resilience to agent failures. Real-world swarm robots often face limitations in computational resources and are prone to hardware and software failures, which can severely impact formation coordination. Our proposed method uses sparse graphs that are globally rigid to reduce computa- tional complexity while ensuring flexible formation maneuvers, and employs outliers rejection to eliminate abnormal agents, ensuring resilient collaboration.