一种多无人机协同优先覆盖搜索算法
A Multi-UAV Collaborative Priority Coverage Search Algorithm
余翔 1邓千锐 1段思睿 1姜陈1
作者信息
- 1. 重庆邮电大学 通信与信息工程学院,重庆 400065
- 折叠
摘要
针对应急救援行动中存在的受灾区域大、重点区域分布不均匀、救援时间有限等问题,提出一种多UAV协同区域优先覆盖搜索算法.对搜索区域进行离散栅格化处理,根据灾情预估信息对搜索区域中的每个网格进行概率标记;通过K-means++聚类算法将搜索区域划分成大小相似、个数与UAV数量相等的子区域,依据聚类中心确定每个子区域的搜索起点,使多架UAV分区协同搜索整个区域;根据网格概率和当前距离之间的平衡关系计算出每个网格的分数,改进贪心算法,以此分数为基准在子区域中进行优先搜索和减少重复路径,引入A*算法解决网格分数冗余问题.仿真结果表明:所提算法在保证优先搜索的同时缩短了路径长度和搜索时间,为应急救援中的搜索难题提供了一种有效的解决办法.
Abstract
For the challenges such as large disaster area,uneven distribution of key areas and limited rescue time in emergency rescue,a multi-UAV collaborative priority coverage search algorithm is proposed.The search area is rasterized,and each grid is probabilistically labeled according to the disaster prediction information.The search area is divided into sub-regions of similar size and equal number of UAVs by K-means++ algorithm,and the search starting point of each sub-region is determined based on the clustering center,so that the multiple UAVs can carry out the partition cooperative search of the whole area.The score of each grid is calculated according to the balance between grid probability and current distance,which is used as a benchmark by the improved greedy algorithm for priority search and reducing the duplicate paths in the sub-region,while A* algorithm is introduced to solve the grid score redundancy problem.The results show that the proposed algorithm effectively reduces the path length and search time while ensuring the priority search,and provides an effective solution to the search problem in emergency rescue.
关键词
多无人机/K-means++/区域划分/协同搜索/改进贪心算法/A*算法Key words
multi-UAVs/K-means++/regional segmentation/collaborative search/improved greedy algorithm/A* algorithm引用本文复制引用
基金项目
重庆市教委科学技术研究计划(KJQN202000615)
出版年
2024
NETL
NSTL
万方数据