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

doi:10.16182/j.issn1004731x.joss.22-1476

摘要/Abstract

摘要：

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

关键词: 多无人机, K-means++, 区域划分, 协同搜索, 改进贪心算法, 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.

Key words: multi-UAVs, K-means++, regional segmentation, collaborative search, improved greedy algorithm, A* algorithm

中图分类号:

TP391.9

余翔,邓千锐,段思睿等 . 一种多无人机协同优先覆盖搜索算法[J]. 系统仿真学报, 2024, 36(4): 991-1000.

Yu Xiang,Deng Qianrui,Duan Sirui,et al . A Multi-UAV Collaborative Priority Coverage Search Algorithm[J]. Journal of System Simulation, 2024, 36(4): 991-1000.

图/表 9

图1

图2

图3

图4

表 1

仿真参数设置

参数	数值
单元间移动速度 $v m$ / $(m / s)$	10
悬停时间 $t s$ / $s$	3
无人机离地高度 $h$ / $m$	60
机载摄像机角度 $α$ /(°)	18
机载摄像机焦距 $f$ / $m m$	35
机载摄像头像素 $S p i x e l$	640×512

表 1

图5

表 2

多无人机仿真结果

算法	区域I		区域II		区域III		区域IV		区域V
算法	t/s	$σ$	t/s	$σ$	t/s	$σ$	t/s	$σ$	t/s	$σ$
本文	250.507	0.749	309.703	0.765	375.329	0.744	447.392	0.758	525.389	0.781
文献[12]	252.710	0.733	312.263	0.757	378.520	0.748	450.259	0.761	530.122	0.782
文献[10]	252.914	0.742	313.847	0.754	379.856	0.738	451.168	0.741	531.941	0.776
文献[8]	254.745	0.750	315.286	0.755	381.955	0.743	454.335	0.746	535.854	0.763

表 2

表 3

图6

参考文献 19

1	韩宇波. 无人机航摄系统及其在地质灾害应急救援中的应用[J]. 科技创新与应用, 2022, 12(29): 193-196.
2	Jiang Xiangyu, Naiyuan Pa, Wang Wenchang, et al. Site Selection and Layout of Earthquake Rescue Center Based on K-means Clustering and Fruit Fly Optimization Algorithm[C]//2020 IEEE International Conference on Artificial Intelligence and Computer Applications (ICAICA). Piscataway, NJ, USA: IEEE, 2020: 1381-1389.
3	Eidenbenz David, Techel Frank, Kottmann Alexandre, et al. Survival Probability in Avalanche Victims with Long Burial (≥60 min): A Retrospective Study[J]. Resuscitation, 2021, 166: 93-100.
4	Yu Xiaobing, Li Chenliang, Zhou Jiafang. A Constrained Differential Evolution Algorithm to Solve UAV Path Planning in Disaster Scenarios[J]. Knowledge-Based Systems, 2020, 204: 106209.
5	黄杰, 傅文, 罗淳, 等. 一种基于隔行扫描的凸多边形区域固定翼无人机摄影测量覆盖路径规划方法[J]. 航空航天, 2022, 9(9): 521.
	Huang Jie, Fu Wen, Luo Chun, et al. An Interlaced Scanning-based Fixed-wing UAV Photogrammetric Coverage Path Planning Method for Convex Polygonal Regions[J]. Aerospace, 2022, 9(9): 521.
6	Cabreira Tauã M, Carmelo Di Franco, Ferreira Paulo R, et al. Energy-aware Spiral Coverage Path Planning for UAV Photogrammetric Applications[J]. IEEE Robotics and Automation Letters, 2018, 3(4): 3662-3668.
7	Lin L, Goodrich M A. UAV Intelligent Path Planning for Wilderness Search and Rescue[C]//2009 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway, NJ, USA: IEEE, 2009: 709-714.
8	Shih G R, Tsai P H, Lin C L. A Speed Up Approach for Search and Rescue[C]//2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC). Piscataway, NJ, USA: IEEE, 2018: 4178-4183.
9	Collins L, Ghassemi P, Esfahani E T, et al. Scalable Coverage Path Planning of Multi-robot Teams for Monitoring Non-convex Areas[C]//2021 IEEE International Conference on Robotics and Automation (ICRA). Piscataway, NJ, USA: IEEE, 2021: 7393-7399.
10	Ai Bo, Jia Maoxin, Xu Hanwen, et al. Coverage Path Planning for Maritime Search and Rescue Using Reinforcement Learning[J]. Ocean Engineering, 2021, 241: 110098.
11	Snyder G A, Shriwastav S, Morrison D, et al. Path Planning for Optimal Coverage of Areas with Nonuniform Importance[C]//AIAA SCITECH 2022 Forum. Reston, VA, USA: AIAA, 2022: AIAA 2022-2546.
12	Song Hongyu, Yu Jincheng, Qiu Jiantao, et al. Multi-UAV Disaster Environment Coverage Planning with Limited-endurance[C]//2022 International Conference on Robotics and Automation (ICRA). Piscataway, NJ, USA: IEEE, 2022: 10760-10766.
13	王洪民, 庄育锋, 韦凌云, 等. 基于信息图的多无人机三维协同搜索动目标方法[J]. 控制与决策, 2023, 38(12): 3534-3542.
	Wang Hongmin, Zhuang Yufeng, Wei Lingyun, et al. Multi-UAV 3D Collaborative Searching for Moving Targets Based on Information Map[J]. Control and Decision, 2023, 38(12): 3534-3542.
14	王可铮, 周兴莲, 林梦婷, 等. 受限通信范围下海上目标的多无人机协同搜索算法[J]. 传感器与微系统, 2022, 41(12): 143-146, 157.
	Wang Kezheng, Zhou Xinglian, Lin Mengting, et al. Cooperative Search Algorithm of Multi-UAV for Sea Targets in Limited Communication Range[J]. Transducer and Microsystem Technologies, 2022, 41(12): 143-146, 157.
15	Huang Gao, Liu Zhuang, Laurens Van Der Maaten, et al. Densely Connected Convolutional Networks[C]//2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Piscataway, NJ, USA: IEEE, 2017: 2261-2269.
16	Chang C C, Lin C J. LIBSVM: A Library for Support Vector Machines[J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(3): 27.
17	曾建邦, 张月娅, 张壮, 等. 基于动态k值K-means++聚类的电动汽车动力电池电压不一致故障识别方法[J]. 中国科学(技术科学), 2023, 53(1): 28-40.
	Zeng Jianbang, Zhang Yueya, Zhang Zhuang, et al. Identification of Power Battery Voltage Inconsistency Faults in Electric Vehicles Based on K-means++ Clustering with Dynamic k-values[J]. Scientia Sinica(Technologica), 2023, 53(1): 28-40.
18	雷雨龙, 侯博宁, 付尧, 等. 基于贪心策略的电动车AMT换挡点实时优化方法研究[J]. 北京理工大学学报, 2022, 42(8): 784-790.
	Lei Yulong, Hou Boning, Fu Yao, et al. Research on Real-time Optimization Method of AMT Shift Point of Electric Vehicle Based on Greedy Algorithm[J]. Transactions of Beijing Institute of Technology, 2022, 42(8): 784-790.
19	Xiong Xiaoyong, Min Haitao, Yu Yuanbin, et al. Application Improvement of A^* Algorithm in Intelligent Vehicle Trajectory Planning[J]. Mathematical Biosciences and Engineering, 2021, 18(1): 1-21.

地图	路径长度/m		搜索时间/s		权值比
地图	η	φ	η	φ	η	φ
10×10	119.320	125.898	221.864	223.179	0.698	0.702
15×15	286.414	194.618	505.212	507.159	0.714	0.717
20×20	513.828	523.281	900.765	902.656	0.696	0.690
25×25	811.211	829.260	1 410.242	1 413.852	0.710	0.704
30×30	1 188.839	1 219.651	2 035.768	2 041.162	0.732	0.731

[1]	高超, 黄郑, 赵轩, 王红星, 龙涛. 基于构型优选的5G集群无人机协同导航方法[J]. 系统仿真学报, 2024, 36(4): 981-990.
[2]	余翔, 姜陈, 段思睿, 邓千锐. 改进A*算法和人工势场法的路径规划[J]. 系统仿真学报, 2024, 36(3): 782-794.
[3]	张国辉, 张雅楠, 高昂, 许奥宇. 空地异构无人系统侦察任务规划方法[J]. 系统仿真学报, 2024, 36(2): 497-510.
[4]	程洁, 郑远, 李诚龙, 江波. 面向超低空物流场景的多机协同航迹规划算法[J]. 系统仿真学报, 2024, 36(1): 50-66.
[5]	李文静, 骆岩林, 王玉辉, 朱丽. 基于八叉树势场的鼻内镜虚拟导航路径规划[J]. 系统仿真学报, 2023, 35(9): 2054-2063.
[6]	牛双诚, 晋玉强, 寇昆湖. 基于区块链的多无人机协同任务分配方法研究[J]. 系统仿真学报, 2023, 35(5): 949-956.
[7]	赵拓, 邓汉强, 高佳隆, 黄健. 基于网络节点聚类的多无人机动态目标分配[J]. 系统仿真学报, 2023, 35(4): 695-708.
[8]	李腾, 丁佩佩, 刘金芳. 货到人拣选系统多阶段可穿行多AGV路径规划[J]. 系统仿真学报, 2022, 34(7): 1512-1523.
[9]	张森, 张孟炎, 邵敬平, 普杰信. 基于随机策略搜索的多机三维路径规划方法[J]. 系统仿真学报, 2022, 34(6): 1286-1295.
[10]	蒙盾, 胡卓, 张华军. 基于改进A^*算法的多层邮轮疏散系统仿真[J]. 系统仿真学报, 2022, 34(6): 1375-1382.
[11]	田广键, 代冀阳, 应进, 王宁. 基于自适应分段势场法的多无人机航迹规划[J]. 系统仿真学报, 2022, 34(11): 2368-2376.
[12]	王宁, 代冀阳, 应进, 李叶鼎, 鲁亮亮. 基于自适应扩展势场的多无人机航迹规划仿真[J]. 系统仿真学报, 2021, 33(9): 2147-2156.
[13]	李向阳, 张志利, 张宁, 桂毅, 李嘉. 局部信息联通的多无人机协同控制过程仿真研究[J]. 系统仿真学报, 2021, 33(7): 1501-1513.
[14]	崔丽珍, 王巧利, 郭倩倩, 杨勇. 井下基于动态指纹更新的指纹定位算法研究[J]. 系统仿真学报, 2021, 33(4): 818-824.
[15]	李颀, 汪伟. 多全向轮协同分拣平台的路径规划[J]. 系统仿真学报, 2021, 33(3): 698-709.