RE-Formation: Resilient and Efficient Formation Planning in Large-Scale Distributed Aerial Swarms (I)
Yuan Zhou, Lun Quan, Guangtong Xu, Chao Xu, Fei Gao
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 (mathbf{RE}-mathbf{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 {}{underline{G}}lobal {}{underline{R}}igidity for uniquely corresponding to a geometric shape and {}{underline{P}}reserve the main {}{underline{F}}eatures of complete graphs, {}{denoted as the mathbf{GRPF} sparse graph}. To prevent the impact of abnormal agents, the problem of eliminating 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