一种多无人机协同优先覆盖搜索算法

作者：余翔; 邓千锐^*; 段思睿; 姜陈

来源：系统仿真学报, 2023, 1-11.

DOI：10.16182/j.issn1004731x.joss.22-1476

• 多无人机
• K-means++
• 区域划分
• 协同搜索
• 改进贪心算法
• A*算法

针对应急救援行动当中存在的受灾区域大、重点区域分布不均匀、救援时间有限等问题，提出了一种多无人机协同区域优先覆盖搜索算法。首先，对搜索区域进行离散栅格化处理，并根据灾情预估信息对搜索区域中的每个网格进行概率标记。然后，通过K-means++聚类算法将搜索区域划分成大小相似、个数与无人机数量相等的子区域，并依据聚类中心确定每个子区域的搜索起点，使多架无人机分区协同搜索整个区域。最后，根据网格概率和当前距离之间的平衡关系计算出每个网格的分数，改进贪心算法以此分数为基准在子区域中进行优先搜索和减少重复路径，同时引入A*算法解决网格分数冗余问题。从路径长度、搜索时间和相同时间内的权值比这三个方面对所提算法进行分析，并将其与目前的三种搜索算法进行对比。仿真结果表明，所提算法在保证优先搜索的同时有效地缩短了路径长度和搜索时间，为应急救援中的搜索难题提供了一种有效的解决办法。

• 单位
  重庆邮电大学; 通信与信息工程学院