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

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

摘要/Abstract

摘要：

针对小型无人机在区域信息采集中的优势, 考虑到复杂多变的应用情景, 提出一种面向大面积多区域覆盖扫描任务的车载多无人机协同模式。该模式中, 车辆可作为无人机的移动基站, 与多架无人机协同完成多个大面积区域的覆盖扫描任务。充分分析新问题特点后, 建立了优化车辆地面行驶路径和多无人机协同空中飞行路径的0-1整数规划模型, 提出了一种基于三阶段的智能优化算法, 先后对多无人机区域覆盖路径以及车辆协同路径进行规划, 快速构造可行解, 而后基于自适应大规模邻域搜索算法对可行解进行优化。本文设计了包含8个目标区域的实际案例, 验证了车载多无人机协同模式的优势和算法有效性, 并进一步通过10个随机案例验证了算法性能。对比实验证明, 车载多无人机协同模式在执行多个大面积区域覆盖任务上, 相比车载单无人机模式能够显著缩短任务时间。

关键词: 多无人机协同, 路径规划, 区域覆盖, 启发式算法

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

中图分类号:

刘瑶, 夏阳升, 石建迈, 陈超, 黄金才. 车载多无人机协同多区域覆盖路径规划方法[J]. 系统工程与电子技术, 2023, 45(5): 1380-1390.

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.

图/表 13

图1

表1

图2

图3

图4

图5

图6

图7

表2

表3

图8

图9

表4

参考文献 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]	韩维, 刘子玄, 苏析超, 崔凯凯, 刘洁. 结合启发式与最优控制的舰载机甲板路径规划算法[J]. 系统工程与电子技术, 2023, 45(4): 1098-1110.
[2]	张浩杰, 张玉东, 梁荣敏, 杨甜甜. 改进A^*算法的机器人能耗最优路径规划方法[J]. 系统工程与电子技术, 2023, 45(2): 513-520.
[3]	冯豪博, 胡桥, 赵振轶. 基于精英族系遗传算法的AUV集群路径规划[J]. 系统工程与电子技术, 2022, 44(7): 2251-2262.
[4]	杨少龙, 黄金, 向先波, 李伟超. 基于置信椭圆的无人艇区域覆盖搜寻规划优化[J]. 系统工程与电子技术, 2022, 44(7): 2263-2269.
[5]	张佳唯, 钱凤臣, 杨俊强, 赵骞, 张峥嵘. 弹性光网络中路由与频谱分配算法综述[J]. 系统工程与电子技术, 2022, 44(6): 2001-2010.
[6]	赵长啸, 李二帅, 何锋, 王鹏. TSN时间敏感流量带宽分配与优化[J]. 系统工程与电子技术, 2022, 44(6): 2027-2034.
[7]	辛立强, 张超, 赵灵芝, 刘建平. 面向复杂关联测控需求的冲突规避调度算法[J]. 系统工程与电子技术, 2022, 44(5): 1581-1588.
[8]	李洪瑶, 李小强, 韩心中, 谢学立, 席建祥. 基于决策融合的多无人机协同目标检测识别算法[J]. 系统工程与电子技术, 2022, 44(3): 746-754.
[9]	尹洋, 杨全顺, 王征, 刘洋. 通信距离约束下的无人船集群覆盖搜索方法[J]. 系统工程与电子技术, 2022, 44(12): 3821-3828.
[10]	杨清清, 高盈盈, 郭玙, 夏博远, 杨克巍. 基于深度强化学习的海战场目标搜寻路径规划[J]. 系统工程与电子技术, 2022, 44(11): 3486-3495.
[11]	马威强, 高永琪, 赵苗. 基于全局最优和差分变异的头脑风暴优化算法[J]. 系统工程与电子技术, 2022, 44(1): 270-278.
[12]	焦志强, 张杰勇, 姚佩阳, 王勋, 何宜超. 基于分层结构的C4ISR服务部署分布式演化方法[J]. 系统工程与电子技术, 2021, 43(6): 1572-1585.
[13]	王文明, 杜佳璐. 基于正六边形栅格JPS算法的智能体路径规划[J]. 系统工程与电子技术, 2021, 43(12): 3635-3642.
[14]	李亚南, 黄海滨, 陈亮名, 庄宇飞, 王晓丽. 变化海流环境下AUV能量最优三维路径规划[J]. 系统工程与电子技术, 2021, 43(12): 3667-3674.
[15]	李文刚, 汪流江, 方德翔, 李玉玮, 黄郡. 联合A^*与动态窗口法的路径规划算法[J]. 系统工程与电子技术, 2021, 43(12): 3694-3702.