RE-Formation: Resilient and Efficient Formation Planning in Large-Scale Distributed Aerial Swarms

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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">G</i>lobal <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</i>igidity for uniquely corresponding to a geometric shape and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P</i>reserve the main <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">F</i>eatures of complete graphs, denoted as the 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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k-core</i> 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.