Sparse-Graph-Enabled Formation Planning for Large-Scale Aerial Swarms

本文提出了一种稀疏图构建方法来实现更好的效率-性能平衡，以解决使用完全图模拟协作约束的编队轨迹规划在无人机数量增加时计算复杂度难以处理的问题。首先，设计了一种完全图的稀疏化机制，以确保稀疏图的全局刚度，这是唯一对应几何形状的必要条件。其次，构建了一个良好的稀疏图，以充分保留完全图的主要结构特征。由于基于图的编队约束是由拉普拉斯矩阵描述的，因此稀疏图构建问题等价于子矩阵选择，具有组合时间复杂度并需要评分指标。通过比较模拟，最大迹矩阵揭示指标显示出有希望的性能。稀疏图被整合到编队规划中。在复杂环境中使用72架无人机进行的模拟结果表明，当保留30％的连接边时，我们的方法具有与完全图相比的编队误差和恢复性能。同时，规划效率提高了约一个数量级。进行了基准比较和消融研究，以充分验证我们方法的优点。

本论文旨在解决使用完全图来建模协作约束的编队轨迹规划在无人机数量增加时计算复杂度过高的问题，提出了一种稀疏图构建方法以实现更好的效率-性能权衡。

论文提出了一种完整图的稀疏化机制，以确保稀疏图的全局刚度，从而唯一地对应于几何形状。其次，构造了一个好的稀疏图来充分保留完全图的主要结构特征。通过子矩阵选择来解决稀疏图构建问题，使用Max-Trace矩阵评分指标，将稀疏图集成到编队规划中。

通过72个无人机的复杂环境模拟，当保留30％的连接边时，该方法具有与完全图相当的编队误差和恢复性能，同时规划效率提高了近一个数量级。实验结果表明该方法的优点。论文还进行了基准比较和消融研究。

在该领域的相关研究包括：1.《A Comprehensive Survey on Formation Control of Multi-Agent Systems》；2.《A survey of multi-robot formation control》；3.《Formation control of multi-agent systems: A review and a new direction》。