车载多无人机协同多区域覆盖路径规划方法

doi:10.12305/j.issn.1001-506X.2023.05.14

Abstract

Abstract:

Aiming at the advantages of drones in regional information collection, and considering complex application scenarios, a cooperative mode with a ground vehicle (GV) and multi-drone is proposed for multiple large area coverage. In this mode, the GV can be used as the mobile base station of the drones to cooperate with multi-drone to complete coverage scanning tasks in multiple large areas. After fully analyzing the characteristics of the new problem, a 0-1 integer programming model to optimize the GV travel path and the multi-drone cooperative air flight path is established, and a three-stage intelligent optimization algorithm is proposed. The regional coverage path of multi-drone and the GV cooperative path are planned successively to quickly construct feasible solutions, and then the feasible solutions are optimized based on the adaptive large scale domain search algorithm. An actual case involving eight target regions is designed to verify the advantages of the GV multi-drone cooperation mode and the effectiveness of the proposed algorithm, and the algorithm performance is further verified through 10 random cases. The comparative experiment proves that the GV multi-drone cooperative mode can significantly shorten the task time compared with the GV single drone mode in performing multiple large area coverage tasks.

Key words: multi-drone cooperation, path planning, area coverage, heuristic algorithm

CLC Number:

Yao LIU, Yangsheng XIA, Jianmai SHI, Chao CHEN, Jincai HUANG. Path planning method for multi-area coverage by cooperated ground vehicle multi-drone[J]. Systems Engineering and Electronics, 2023, 45(5): 1380-1390.

Figures/Tables 13

Fig.1

Table 1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Table 2

Table 3

Fig.8

Fig.9

Table 4

References 30

1	ABUALIGAH L , DIABAT A , SUMARI P , et al. Applications, deployments, and integration of internet of drones (IoD): a review[J]. IEEE Sensors Journal, 2021, 21 (22): 25532- 25546. doi: 10.1109/JSEN.2021.3114266
2	DAUD S M , YUSOF M Y , HEO C C , et al. Applications of drone in disaster management: a scoping review[J]. Science & Justice, 2021, 62 (1): 30- 42.
3	NEDJATI A , IZBIRAK G , VIZVARI B , et al. Complete cove-rage path planning for a multi-UAV response system in post-earthquake assessment[J]. Robotics, 2016, 5 (4): 26- 40. doi: 10.3390/robotics5040026
4	SHAHMORADI J , TALEBI E , ROGHANCHI P , et al. A comprehensive review of applications of Drone technology in the mining industry[J]. Drones, 2020, 4 (3): 34- 58. doi: 10.3390/drones4030034
5	MADJIDI H, NEGAHDARIPOUR S, BANDARI E. Vision-based positioning and terrain mapping by global alignment for UAVs[C]//Proc. of the IEEE Conference on Advanced Video and Signal Based Surveillance, 2003: 305-312.
6	LYU X , LI X B , DANG D L , et al. Unmanned aerial vehicle (UAV) remote sensing in grassland ecosystem monitoring: a systematic review[J]. Remote Sensing, 2022, 14 (5): 1096- 1114. doi: 10.3390/rs14051096
7	OKSANEN T , VISALA A . Coverage path planning algorithms for agricultural field machines[J]. Journal of Field Robotics, 2009, 26 (8): 651- 668. doi: 10.1002/rob.20300
8	庞强伟, 胡永江, 李文广, 等. 多无人机协同侦察任务规划方法研究综述[J]. 电讯技术, 2019, 59 (6): 741- 748.
	PANG Q W , HU Y J , LI W G , et al. Research on multi-UAV cooperative reconnaissance mission planning methods: an overview[J]. Telecommunication Engineering, 2019, 59 (6): 741- 748.
9	谢朋志, 魏晨. 单侧区域分割的多无人机扫描线搜索方法研究[J]. 航空兵器, 2020, 27 (3): 67- 72.
	XIE P Z , WEI C . Research on scanning line search method for multi-UAV based on unilateral region segmentation[J]. Aero Weaponry, 2020, 27 (3): 67- 72.
10	庞强伟, 胡永江, 李文广. 基于垂直区域宽度分解的无人机覆盖航迹规划[J]. 系统工程与电子技术, 2019, 41 (11): 2550- 2558.
	PANG Q W , HU Y J , LI W G . UAV coverage track planning based on decomposition along the direction of perpendicular to the width of the area[J]. Systems Engineering and Electronics, 2019, 41 (11): 2550- 2558.
11	王勋, 姚佩阳, 梅权. 多无人机协同运动目标搜索问题研究[J]. 电光与控制, 2016, 23 (8): 18- 22.
	WANG X , YAO P Y , MEI Q . On multi-UAV cooperation for moving target searching[J]. Electronics Optics & Control, 2016, 23 (8): 18- 22.
12	AKSHYA J , PRIYADARSINI P L K . Graph-based path planning for intelligent UAVs in area coverage applications[J]. Journal of Intelligent & Fuzzy Systems, 2020, 39 (6): 8191- 8203.
13	LI J D, LI X Q, YU L J. Multi-UAV cooperative coverage path planning in plateau and mountain environment[C]//Proc. of the 33rd Youth Academic Annual Conference of Chinese Association of Automation, 2018: 820-824.
14	XIAO S C , TAN X J , WANG J P . A simulated annealing algorithm and grid map-based UAV coverage path planning method for 3D reconstruction[J]. Electronics, 2021, 10 (7): 853- 868. doi: 10.3390/electronics10070853
15	YUAN J B , LIU Z B , LIAN Y D , et al. Global optimization of UAV area coverage path planning based on good point set and genetic algorithm[J]. Aerospace, 2022, 9 (2): 86- 104. doi: 10.3390/aerospace9020086
16	SANTIN R , ASSIS L , VIVAS A , et al. Matheuristics for multi-UAV routing and recharge station location for complete area coverage[J]. Sensors, 2021, 21 (5): 1705- 1738. doi: 10.3390/s21051705
17	MURRAY C C , CHU A G . The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery[J]. Transportation Research Part C: Emerging Technologies, 2015, (54): 86- 109.
18	MANYAM S G, CASBEER D W, SUNDAR K. Path planning for cooperative routing of air-ground vehicles[C]//Proc. of the American Control Conference, 2016: 4630-4635.
19	DENG C , WANG S W , HUANG Z , et al. Unmanned aerial vehicles for power line inspection: a cooperative way in platforms and communications[J]. Communication, 2014, 9 (9): 687- 692.
20	MOSHREF J M , WINKENBACH M . Applications and research avenues for drone-based models in logistics: a classification and review[J]. Expert Systems with Applications, 2021, 177, 114854.
21	AGATZ N , BOUMAN P , SCHMIDT M . Optimization approaches for the traveling salesman problem with drone[J]. Transportation Science, 2018, 52 (4): 965- 981.
22	LIU Y , LIU Z , SHI J M , et al. Two-echelon routing problem for parcel delivery by cooperated truck and drone[J]. IEEE Trans.on Systems, Man, Cybernetics: Systems, 2021, 51 (12): 7450- 7465.
23	GONZALEZ R P L , CANCA D , ANDRADE-PINEDA J L , et al. Truck-drone team logistics: a heuristic approach to multi-drop route planning[J]. Transportation Research Part C: Emerging Technologies, 2020, 114, 657- 680.
24	OTTO A , AGATZ N , CAMPBELL J , et al. Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: a survey[J]. Networks, 2018, 72 (4): 411- 458.
25	MACRINA G , PUGLIESE L D P , GUERRIERO F , et al. Drone-aided routing: a literature review[J]. Transportation Research Part C: Emerging Technologies, 2020, 120, 102762- 102813.
26	CHUNG S H , SAH B , LEE J . Optimization for drone and drone-truck combined operations: a review of the state of the art and future directions[J]. Computers & Operations Research, 2020, 123, 105004- 105083.
27	夏阳升, 石建迈, 陈超, 等. 车机协同多区域覆盖侦察路径规划方法[J]. 指挥与控制学报, 2020, 6 (4): 372- 380.
	XIA Y S , SHI J M , CHEN C , et al. Path planning method for multi-area reconnaissance by cooperated ground vehicle and drone[J]. Journal of Command and Control, 2020, 6 (4): 372- 380.
28	CLARKE G , WRIGHT J W . Scheduling of vehicles from a central depot to a number of delivery points[J]. Operations Research, 1964, 12 (4): 568- 581.
29	STEINBRUNN M , MOERKOTTE G , KEMPER A . Heuristic and randomized optimization for the join ordering problem[J]. The International Journal on Very Large Data Bases, 1997, 6 (3): 191- 208.
30	夏桂梅, 曾建潮. 一种基于轮盘赌选择遗传算法的随机微粒群算法[J]. 计算机工程与科学, 2007, 29 (6): 51- 54.
	XIA G M , ZENG J C . A stochastic particle swarm optimization algorithm based on the genetic algorithm of roulette wheel selection[J]. Computer Engineering & Science, 2007, 29 (6): 51- 54.

符号	含义
集合:
G	定义问题的无向图;
E	所有弧的集合;
S	S={1, 2, …, a}, 所有区域的集合;
M_n^s	区域s子区域的集合, n ={1, 2, …, m_s}, s∈S;
V	所有区域的顶点集合;
V_s	区域s的顶点集合, 其中s∈S;
N₀	N₀={0}, 基站;
N	N={1, 2, …, n}, 所有区域附近停点的集合;
N_s	区域s附近的停点集合, 其中s∈S;
f_p^s	区域s中被选中的起飞停点集合, 其中s∈S;
l_p^s	区域s中被选中的降落停点集合, 其中s∈S;
P_s	区域s中所有扫描路径的起点和终点的集合, 其中s∈S;
U_s^k	区域s中第k架无人机所有扫描路径的集合, 其中k={1, 2, …, m_s}, s∈S;
P_s^k	区域s中第k架无人机覆盖路径的起点和终点的集合, 其中k={1, 2, …, m_s}, s∈S;
P_{M_n^s}	区域s中子区域n中无人机覆盖路径的起点和终点的集合;
R	车辆可以行进的一组弧线集合;
参数:
L_ij^F	点i到点j的Floyd距离, 其中i, j∈N₀∪N;
l_s^k	侦察区域s中第k架无人机扫描路径的长度, 其中k={1, 2, …, m_s}, s∈S;
v^G	车辆的平均行驶速度;
v^D	无人机的平均飞行速度;
A_s	区域s的面积, 其中s∈S;
Z	完成侦察任务所需的总时间;
T_max	无人机的最大续航时间;
m_s	侦察区域s所需的无人机数量, 其中s∈S;
决策变量:
x_ij	如果车辆从点i行驶到点j, 则为1, 否则为0, 其中s∈S;
y_ijs^k	在区域s中, 如果第k架无人机从点i飞到点j, 则为1, 否则为0, 其中k={1, 2, …, m_s}, s∈S。

参数	设定值
T_s/(°)	100
T_e/(°)	1
cr	0.99
N	100
N_max	6
λ	0.2

区域编号	面积	周长	圆度	无人机数量
1	106.50	46.35	0.62	2
2	173.75	47.99	0.95	3
3	146.00	51.51	0.69	3
4	104.00	48.59	0.55	2
5	154.50	55.83	0.62	3
6	100.00	50.87	0.49	2
7	112.00	47.56	0.62	2
8	154.50	55.36	0.63	3

案例编号	区域数量	VPP算法/min	MAC-PO算法/min	OTOD模式/min	提升度1/%	提升度2/%
1	7	309.92	221.89	436.50	28.40	49.17
2	8	371.45	268.33	519.34	27.76	48.33
3	9	417.05	299.05	570.48	28.29	47.58
4	10	425.76	321.12	633.66	24.58	49.32
5	11	467.43	330.56	605.39	29.28	45.40
6	12	513.51	366.34	732.68	28.66	50.00
7	13	547.19	411.42	795.64	24.81	48.29
8	14	619.34	428.17	850.13	30.87	49.63
9	15	670.44	474.31	924.78	29.25	48.71
10	16	701.50	499.35	952.27	28.82	47.56

[1]	Wei HAN, Zixuan LIU, Xichao SU, Kaikai CUI, Jie LIU. Deck path planning algorithm of carrier-based aircraft based on heuristic and optimal control [J]. Systems Engineering and Electronics, 2023, 45(4): 1098-1110.
[2]	Haojie ZHANG, Yudong ZHANG, Rongmin LIANG, Tiantian YANG. Energy-efficient path planning method for robots based on improved A^* algorithm [J]. Systems Engineering and Electronics, 2023, 45(2): 513-520.
[3]	Zhi REN, Dong ZHANG, Shuo TANG. Improved three-dimensional A^* algorithm of real-time path planning based on reinforcement learning [J]. Systems Engineering and Electronics, 2023, 45(1): 193-201.
[4]	Haobo FENG, Qiao HU, Zhenyi ZHAO. AUV swarm path planning based on elite family genetic algorithm [J]. Systems Engineering and Electronics, 2022, 44(7): 2251-2262.
[5]	Shaolong YANG, Jin HUANG, Xianbo XIANG, Weichao LI. Optimization of USV area coverage path planning based on confidence ellipsoid [J]. Systems Engineering and Electronics, 2022, 44(7): 2263-2269.
[6]	Jiawei ZHANG, Fengchen QIAN, Junqiang YANG, Qian ZHAO, Zhengrong ZHANG. Survey on routing and spectrum allocation algorithm in elastic optical networks [J]. Systems Engineering and Electronics, 2022, 44(6): 2001-2010.
[7]	Changxiao ZHAO, Ershuai LI, Feng HE, Peng WANG. Bandwidth allocation and optimization of time-sensitive traffic in TSN [J]. Systems Engineering and Electronics, 2022, 44(6): 2027-2034.
[8]	Liqiang XIN, Chao ZHANG, Lingzhi ZHAO, Jianping LIU. Conflict avoidance scheduling algorithm for complex associated TT & C requirements [J]. Systems Engineering and Electronics, 2022, 44(5): 1581-1588.
[9]	Dou CHEN, Xiuyun MENG. UAV offline path planning based on self-adaptive coyote optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(2): 603-611.
[10]	Yang YIN, Quanshun YANG, Zheng WANG, Yang LIU. USV cluster coverage search method with communication distance constraint [J]. Systems Engineering and Electronics, 2022, 44(12): 3821-3828.
[11]	Qingqing YANG, Yingying GAO, Yu GUO, Boyuan XIA, Kewei YANG. Target search path planning for naval battle field based on deep reinforcement learning [J]. Systems Engineering and Electronics, 2022, 44(11): 3486-3495.
[12]	Tong HAN, Andi TANG, Huan ZHOU, Dengwu XU, Lei XIE. Multiple UAV cooperative path planning based on LASSA method [J]. Systems Engineering and Electronics, 2022, 44(1): 233-241.
[13]	Weiqiang MA, Yongqi GAO, Miao ZHAO. Global-best difference-mutation brain storm optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(1): 270-278.
[14]	Lei LAI, Kun ZOU, Dewei WU, Baozhong LI. Multi-UAV cooperative path planning based on improved MOFA evolution of interactive strategy [J]. Systems Engineering and Electronics, 2021, 43(8): 2282-2289.
[15]	Zhiqiang JIAO, Jieyong ZHANG, Peiyang YAO, Xun WANG, Yichao HE. Distributed evolution method of C4ISR service deployment based on hierarchical structure [J]. Systems Engineering and Electronics, 2021, 43(6): 1572-1585.

Path planning method for multi-area coverage by cooperated ground vehicle multi-drone

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 30

Related Articles 15

Recommended Articles

Metrics

Comments