基于精英族系遗传算法的AUV集群路径规划

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

摘要/Abstract

摘要：

针对传统路径规划算法仅能规划单一最短路径且不能调节路径宽度而难以适用于自主式水下航行器(autonomous underwater vehicle, AUV)集群航路规划的缺陷, 提出了精英族系遗传算法(elite family genetic algorithm, EFGA)。该算法将基因适应度加入适应度评价函数中, 同时在进化过程中标记精英个体作为多路径规划结果, 并在该算法基础上针对AUV集群路径规划问题设计了一种多智能体路径规划(multi-agent path planning, MAPP)方法。仿真结果表明, 该算法可以求解无冲突路径集合实现MAPP, 通过实现AUV集群的最优多路径航行方案减少集群的航行耗时, 且能够满足不同AUV编队规模对可调路径宽度的需求。

关键词: 自主式水下航行器集群, 多路径规划, 多智能体路径规划, 遗传算法, 精英族系策略

Abstract:

Aiming at the defect that the traditional path planning algorithm can only plan a single shortest path and can not adjust the path width, which is difficult to apply to the cluster route planning of autonomous underwater vehicle (AUV), a genetic algorithm based on elite family (EFGA) is proposed. In this algorithm, gene fitness is added to the fitness evaluation function, and elite individuals are marked as the result of multi-path planning in the process of evolution. Based on this algorithm, a multi-agent path planning (MAPP) method is designed for AUV cluster path planning. Simulation results show that the algorithm can solve the conflict free path set, realize MAPP, reduce the navigation time of underwater vehicle cluster by realizing the optimal multi-path navigation scheme of AUV cluster, and meet the requirements of adjustable path width for different AUV formation sizes.

Key words: autonomous underwater vehicle (AUV) swarm, multi-path planning, multi-agent path planning (MAPP), genetic algorithm (GA), elite family strategy

中图分类号:

TP242

冯豪博, 胡桥, 赵振轶. 基于精英族系遗传算法的AUV集群路径规划[J]. 系统工程与电子技术, 2022, 44(7): 2251-2262.

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.

图/表 18

图1

图2

图3

图4

图5

图6

图7

表1

图8

表2

表3

图9

表4

图10

图11

表5

图12

表6

参考文献 30

1	WEI T, MIAO Y, XIAO B Q, et al. Research on autonomous control technology of underwater unmanned swarm based on center transfer[C]//Proc. of the 5th International Conference on Automation, Control and Robotics Engineering, 2020: 430-434.
2	陶伟, 张晓霜. 国外水下无人集群应用及关键技术研究[J]. 舰船电子工程, 2021, 41 (2): 9- 13, 54. doi: 10.3969/j.issn.1672-9730.2021.02.003
	TAO W , ZHANG X S . Research on application and key technology of underwater unmanned cluster abroad[J]. Ship Electronic Engineering, 2021, 41 (2): 9- 13, 54. doi: 10.3969/j.issn.1672-9730.2021.02.003
3	MAGNUSON S . DARPA pushes "Mosaic Warfare" concept[J]. National Defense, 2018, 103 (780): 18- 19.
4	黄琰, 李岩, 俞建成, 等. AUV智能化现状与发展趋势[J]. 机器人, 2020, 42 (2): 215- 231.
	HUANG Y , LI Y , YU J C , et al. State-of-the-art and development trends of AUV intelligence[J]. Jiqiren/Robot, 2020, 42 (2): 215- 231.
5	CAO X , SUN H B , JAN G E . Multi-AUV cooperative target search and tracking in unknown underwater environment[J]. Ocean Engineering, 2018, 150, 1- 11. doi: 10.1016/j.oceaneng.2017.12.037
6	ZHU D Q , ZHOU B , YANG S X . A novel algorithm of multi-AUVs task assignment and path planning based on biologically inspired neural network map[J]. IEEE Trans.on Intelligent Vehicles, 2021, 6 (2): 333- 342. doi: 10.1109/TIV.2020.3029369
7	YAN Z P , ZHANG J Z , ZENG J , et al. Water wave optimization algorithm for autonomous underwater vehicle path planning problem[J]. Journal of Intelligent & Fuzzy Systems, 2021, 40 (5): 9127- 9141.
8	刘庆周, 吴锋. 多智能体路径规划研究进展[J]. 计算机工程, 2020, 46 (4): 1- 10.
	LIU Q Z , WU F . Research progress of multi-agent path planning[J]. Computer Engineering, 2020, 46 (4): 1- 10.
9	BABEL L . Coordinated target assignment and UAV path planning with timing constraints[J]. Journal of Intelligent & Robotic Systems, 2019, 94 (3/4): 857- 869.
10	LIU M Y , XU B G , PENG X G . Cooperative path planning for multi-AUV in time-varying ocean flows[J]. Journal of Systems Engineering and Electronics, 2016, 27 (3): 612- 618. doi: 10.1109/JSEE.2016.00065
11	CAI L, ZHOU G F, ZHANG S J. Multi-AUV collaborative hunting method for the non-cooperative target in underwater environment[C]//Proc. of the 3rd International Conference on Advanced Robotics and Mechatronics, 2019: 72-76.
12	YU X , CHEN W N , HU X M , et al. Path planning in multiple-AUV systems for difficult target traveling missions: a hybrid metaheuristic approach[J]. IEEE Trans.on Cognitive and Developmental Systems, 2020, 12 (3): 561- 574. doi: 10.1109/TCDS.2019.2944945
13	SANG H Q , YOU Y S , SUN X J , et al. The hybrid path planning algorithm based on improved A^* and artificial potential field for unmanned surface vehicle formations[J]. Ocean Engineering, 2021, 223 (3/4): 108709- 108724.
14	王乐乐, 眭泽智, 蒲志强, 等. 一种改进RRT的多机器人编队路径规划算法[J]. 电子学报, 2020, 48 (11): 2138- 2145.
	WANG L L , SUI Z Z , PU Z Q , et al. An improved RRT algorithm for multi-robot formation path planning[J]. Acta Electronica Sinica, 2020, 48 (11): 2138- 2145.
15	LIMA J , BELO E M , MARQUES V . Multi-agent path planning with nonlinear restrictions[J]. Evolutionary Intelligence, 2021, 14 (1): 191- 201. doi: 10.1007/s12065-020-00534-1
16	李征, 陈建伟, 彭博. 基于伪谱法的无人机集群飞行路径规划[J]. 空天防御, 2021, 4 (1): 52- 59. doi: 10.3969/j.issn.2096-4641.2021.01.009
	LI Z , CHEN J W , PENG B . UAV cluster path planning based on pseudospectral method[J]. Air & Space Defense, 2021, 4 (1): 52- 59. doi: 10.3969/j.issn.2096-4641.2021.01.009
17	丁佳宇, 王茂森, 戴劲松. 基于前馈控制人工势场法的无人机群系统设计[J]. 传感器与微系统, 2021, 40 (5): 114- 117, 120.
	DING J Y , WANG M S , DAI J S . Design of UAV group system based on feedforward control artificial potential field method[J]. Transducer and Microsystem Technologies, 2021, 40 (5): 114- 117, 120.
18	HAN J . An efficient approach to 3D path planning[J]. Information Sciences, 2019, 478, 318- 330. doi: 10.1016/j.ins.2018.11.045
19	BLASI L , D'AMATO E , MATTEI M , et al. Path planning and real-time collision avoidance based on the essential visibility graph[J]. Applied Sciences, 2020, 10 (16): 5613- 5635. doi: 10.3390/app10165613
20	ZHANG J D , WANG W , QI X Y , et al. Social and robust navigation for indoor robots based on object semantic grid and topological map[J]. Applied Sciences, 2020, 10 (24): 8991- 9010. doi: 10.3390/app10248991
21	WANG P L , ZHANG T , XIAO Y J . Emergency evacuation path planning of passenger ship based on cellular ant optimization model[J]. Journal of Shanghai Jiaotong University (Science), 2020, 25 (6): 721- 726. doi: 10.1007/s12204-020-2215-y
22	李文刚, 汪流江, 方德翔, 等. 联合A^*与动态窗口法的路径规划算法[J]. 系统工程与电子技术, 2021, 43 (12): 3694- 3702. doi: 10.12305/j.issn.1001-506X.2021.12.33
	LI W G , WANG L J , FANG D X , et al. Path planning algorithm combining A^* with DWA[J]. Systems Engineering and Electronics, 2021, 43 (12): 3694- 3702. doi: 10.12305/j.issn.1001-506X.2021.12.33
23	SAMPSON J R . Adaptation in natural and artificial systems[J]. SIAM Review, 1976, 18 (3): 529- 530. doi: 10.1137/1018105
24	MA J W , LIU Y , ZANG S F , et al. Robot path planning based on genetic algorithm fused with continuous bezier optimization[J]. Computational Intelligence and Neuroscience, 2020, 9813040.
25	LI L, GU Q, LIU L. Research on path planning algorithm for multi-UAV maritime targets search based on genetic algorithm[C]//Proc. of the IEEE International Conference on Information Technology, Big Data and Artificial Intelligence, 2020: 840-843.
26	CAO Y , WEI W Y , BAI Y , et al. Multi-base multi-UAV cooperative reconnaissance path planning with genetic algorithm[J]. Cluster Computing, 2019, 22 (S3): 5175- 5184. doi: 10.1007/s10586-017-1132-9
27	ZHAO H, ZHAN Z H, CHEN W N, et al. An improved selection operator for multi-objective optimization[C]//Proc. of the 16th International Symposium on Neural Networks, 2019: 379-388.
28	CHEN X N , GAO P J . Path planning and control of soccer robot based on genetic algorithm[J]. Ambient Intelligence and Humanized Computing, 2020, 11 (12): 6177- 6186. doi: 10.1007/s12652-019-01635-1
29	KIRAZ B, BIDGOLI A, EBRAHIMPOUR-KOMLEH H, et al. A novel collective crossover operator for genetic algorithms[C]//Proc. of the IEEE International Conference on Systems, Man, and Cybernetics, 2020: 4204-4209.
30	MANZONI L , MARIOT L , TUBA E . Balanced crossover operators in genetic algorithms[J]. Swarm and Evolutionary Computation, 2020, 54, 100646. doi: 10.1016/j.swevo.2020.100646

算法	参数
算法	精英个体数	P_r	P_e	P_m	P_c	C_xcoef	C_ycoef	k_x	k_y	m_e
EFGA-1	1
EFGA-2	2	[0.1, 0.2]	[0.1, 0.3]	0.15	0.1	2×n	0	1	0	20
EFGA-3	3
EFGA-4						1
EFGA-5	3	[0.1, 0.2]	[0.1, 0.3]	0.15	0.1	2×n	0	1	0	20
EFGA-6						18×n
EFGA-7	1					2×n	2×n			20
EFGA-8	2	[0.1, 0.2]	[0.1, 0.3]	0.3	0.1	2×n	2×n	0.5	0.5	15
EFGA-9	3					18×n	18×n			10
EFGA-10	1
EFGA-11	2	[0.1, 0.2]	[0.1, 0.3]	0.15	0.1	∞	0	1	0	20
EFGA-12	3
EFGA-13	3									10
EFGA-14	2	[0.1, 0.2]	[0.1, 0.3]	0.15	0.1	∞	∞	0.5	0.5	15
EFGA-15	1									20

参数		算法
参数		EFGA-1	EFGA-2	EFGA-3
平均收敛代数		66.47	118.80	211.96
平均收敛耗时/s		0.653	1.023	1.651
平均各路径长度/m	路径-1	30.044	29.662	29.416
	路径-2	—	30.540	30.204
	路径-3	—	—	30.984
平均路径长度/m		30.044	30.101	30.201
平均路径重合度/%		—	0.19	0.78

参数		算法
参数		EFGA-4	EFGA-5	EFGA-6
平均收敛代数		199.38	206.19	207.56
平均收敛耗时/s		1.573	1.608	1.626
平均各路径长度/m	路径-1	29.638	29.364	29.520
	路径-2	29.674	30.174	30.426
	路径-3	30.468	30.872	31.538
平均路径长度/m		29.927	30.137	30.495
平均路径重合度/%		1.72	0.82	0.52

参数		算法
参数		EFGA-7	EFGA-8	EFGA-9
平均收敛代数		77.56	217.54	341.60
平均收敛耗时/s		17.089	21.079	24.862
平均各路径长度/m	路径-1	76.090	75.910	75.688
	路径-2	—	79.700	80.080
	路径-3	—	—	84.116
平均路径长度/m		76.090	77.805	79.961
平均路径重合度/%		—	6.45	14.30

参数		算法
参数		EFGA-10	EFGA-11	EFGA-12
平均原始路径长度/m	路径-1	29.980	29.544	29.512
	路径-2	—	30.678	30.256
	路径-3	—	—	31.364
平均当量路径长度/m	路径-1	39.980	34.984	33.772
	路径-2	—	35.238	33.686
	路径-3	—	—	33.674
平均行进耗时/s		38.980	34.380	33.044
平均算法运行总耗时/s		3.935	4.260	9.056