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

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

Abstract

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

CLC Number:

TP242

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.

Figures/Tables 18

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Table 1

Fig.8

Table 2

Table 3

Fig.9

Table 4

Fig.10

Fig.11

Table 5

Fig.12

Table 6

References 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

AUV swarm path planning based on elite family genetic algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 18

References 30

Related Articles 15

Recommended Articles

Metrics

Comments

参数		AUV集群路径规划
参数		无编队	三机编队	六机编队
平均原始路径长度/m	路径-1	29.384	31.715	32.200
	路径-2	30.164	32.637	—
	路径-3	31.114	—	—
平均当量路径长度/m	路径-1	34.294	37.259	39.664
	路径-2	34.164	38.021	—
	路径-3	34.204	—	—
平均行进耗时/s		33.554	36.101	37.664
平均算法运行总耗时/s		9.776	12.807	11.291

[1]	Tiansu LUO, Lingfeng ZHAO, Yunwen FENG, Xiaofeng XUE, Cheng LU. Super large-scale satellite constellation multi-level backup strategy based on METRIC theory [J]. Systems Engineering and Electronics, 2022, 44(7): 2181-2190.
[2]	Yunwen FENG, Junyu CHEN, Cheng LU. Research on civil aircraft spare parts multi-region support network model [J]. Systems Engineering and Electronics, 2022, 44(5): 1553-1561.
[3]	Yuan GUO, Zhiyong SUO, Tingting WANG, Zhiqiang LIAO. Parameter optimization design method of missile-borne SAR system [J]. Systems Engineering and Electronics, 2020, 42(7): 1478-1483.
[4]	Chen LI, Jun'an YANG, Hui LIU. Modulation recognition algorithm based on information entropy and GA-ELM [J]. Systems Engineering and Electronics, 2020, 42(1): 223-229.
[5]	WANG Zhangang, WANG Daming, BA Bin, ZHANG Yankui. Direction finding algorithm of correlated interferometer based on genetic algorithm with high degree of stretching#br# [J]. Systems Engineering and Electronics, 2018, 40(1): 39-44.
[6]	LEI Xiaoyun, ZHANG Zhian. Intercepting performance analysis of a neotype active protection system based on particle swarm algorithm#br# [J]. Systems Engineering and Electronics, 2017, 39(12): 2772-2781.
[7]	WANG Minle, FAN Yangtao. Intelligent solving algorithm for effectsbased firepower allocation model of conventional missiles [J]. Systems Engineering and Electronics, 2017, 39(11): 2509-2514.
[8]	HAN Yulong, YAN Jiangang, YANG Shifeng, PAN Changpeng, WANG Lei. Path planning for ship-based UAV air-to-sea attack with threat netting [J]. Systems Engineering and Electronics, 2017, 39(1): 101-106.
[9]	HU Youtao, FAN Jinsuo, HU Changhua. Modeling degradation path using v-support vector regression [J]. Systems Engineering and Electronics, 2017, 39(1): 231-236.
[10]	ZHANG Tian-jiao, LI Ji-sheng, LI Jing, YANG Yi-kang, DU Wei-bing. Space ground integrated scheduling based on the hybrid ant colony optimization [J]. Systems Engineering and Electronics, 2016, 38(7): 1555-1562.
[11]	LI An-da, HE Zhen, HE Shu-guang. Critical to quality characteristics identification for complex products using GSA [J]. Systems Engineering and Electronics, 2015, 37(9): 2073-2079.
[12]	YAO Ying-biao, WANG Xuan. Modified hybrid genetic algorithm for parallel task scheduling of multiprocessors [J]. Systems Engineering and Electronics, 2015, 37(8): 1928-1935.
[13]	ZHANG Yang-rui, LI Yun-jie, GAO Mei-guo. Optimal assignment model and solution of cooperative jamming resources [J]. Systems Engineering and Electronics, 2014, 36(9): 1744-1749.
[14]	HE Xiao-liang, BI Yi-ming. Modeling and optimization of formation air-to-ground attack fire distribution based on simulated annealing genetic algorithm [J]. Systems Engineering and Electronics, 2014, 36(5): 900-904.
[15]	ZHAO Yong-bo, LI Hui, QIN Chun-miao. DFCW-LFM waveform design based on GASA algorithm [J]. Systems Engineering and Electronics, 2014, 36(11): 2186-2191.