A Multi-UAV Collaborative Priority Coverage Search Algorithm

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

Abstract

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

CLC Number:

TP391.9

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

Figures/Tables 9

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Table 1

Simulation parameter setting

参数	数值
单元间移动速度 $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

Table 1

Fig. 5

Table 2

Multi-UAV simulation results

算法	区域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

Table 2

Table 3

Fig. 6

References 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]	Liu Hanwen, Zhuo Zhimin, Yang Xue. Optimization of Multi-target Interception Scheme Based on Performance Simulation Modeling [J]. Journal of System Simulation, 2025, 37(9): 2366-2374.
[2]	Yu Yiran, Lai Huicheng, Gao Guxue, Zhang Guo, Peng Wangyinan, Yang Longfei, Huang Junhao. Optimization Method for Multi Agricultural Machinery Collaborative Operation Based on Genetic Algorithm and A * Algorithm [J]. Journal of System Simulation, 2025, 37(9): 2397-2408.
[3]	Yu Die, Bao Baizhong, Si Yan, Duan Jian, Zhan Xiaobin, Shi Tielin. Mobile Robot Path Planning Based on Search-step Optimized A* Algorithm [J]. Journal of System Simulation, 2025, 37(4): 1041-1050.
[4]	Lin Guijuan, Li Zihan, Wang Yu. Research on Improved A* Algorithm Path Planning Based on Global Key Point Extraction [J]. Journal of System Simulation, 2025, 37(3): 667-678.
[5]	Li Jiongyi, Li Qiang, Zhang Xinwen, Htet Zin Myo, Cai Yongbin. Improved Bidirectional A* Quadratic Path Planning Algorithm for Mobile Robots [J]. Journal of System Simulation, 2025, 37(2): 498-507.
[6]	Xing Lijing, Li Min, Zeng Xiangguang, Zhang Ping, Peng Bei. AUV Path Planning Based on Behavior Cloning and Improved DQN in Partially Unknown Environments [J]. Journal of System Simulation, 2025, 37(11): 2754-2767.
[7]	Yang Lanying, Li Chao, Zou Haifeng, Wan Jiangtao, Zhang Renqiang, Liu Hui, Lu Hong. Robot Path Planning Optimization Based on Fusion of Improved Ant Colony Algorithm and A* Algorithm [J]. Journal of System Simulation, 2025, 37(11): 2956-2965.
[8]	Xu Jianmin, Song Lei, Deng Dongdong, Chen Yaoruo, Yang Wei. Path Planning of Mobile Robot Based on the Integration of Multi-scale A* and Optimized DWA Algorithm [J]. Journal of System Simulation, 2025, 37(1): 257-270.
[9]	Ji Peng, Zhang Xinyuan, Gao Shuaixuan, Wei Shuorang. Path Planning Based on Improved A* and Dynamic Window Approach [J]. Journal of System Simulation, 2024, 36(9): 2171-2180.
[10]	Lai Rongshen, Dou Lei, Wu Zhiyong, Sun Shuai. Fusion of Improved A* and Dynamic Window Approach for Mobile Robot Path Planning [J]. Journal of System Simulation, 2024, 36(8): 1884-1894.
[11]	Yu Xiang, Jiang Chen, Duan Sirui, Deng Qianrui. Path Planning for Improvement of A* Algorithm and Artificial Potential Field Method [J]. Journal of System Simulation, 2024, 36(3): 782-794.
[12]	Zhang Guohui, Zhang Ya'nan, Gao Ang, Xu Aoyu. Reconnaissance Mission Planning Method for Air-ground Heterogeneous Unmanned Systems [J]. Journal of System Simulation, 2024, 36(2): 497-510.
[13]	Yao Dexin, San Hongjun, Wang Yaru, Sun Haijie, Chen Jiupeng, Yang Xiaoyuan. Improvement of A* Algorithm in Path Planning of Mobile Robot [J]. Journal of System Simulation, 2024, 36(11): 2684-2698.
[14]	Cheng Jie, Zheng Yuan, Li Chenglong, Jiang Bo. Multi-UAV Collaborative Trajectory Planning Algorithm for Urban Ultra-low-altitude Air Transportation Scenario [J]. Journal of System Simulation, 2024, 36(1): 50-66.
[15]	Li Wenjing, Luo Yanlin, Wang Yuhui, Zhu Li. Virtual Navigation Path Planning Based on Octree Potential Field for Endonasal Endoscope [J]. Journal of System Simulation, 2023, 35(9): 2054-2063.