基于改进鲸鱼优化算法的AUV三维路径规划

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

摘要/Abstract

摘要：

自主水下机器人(autonomous underwater vehicle, AUV)已成为不同领域多种水下作业最有效的装备之一。针对其全局路径规划问题，提出了一种基于改进鲸鱼优化算法的求解方法。首先对于建模问题, 在环境模型中, 鉴于三维空间中设置路径点的复杂性, 给出了基于连接型快速扩展随机树(connected rapidly-exploring random tree, RRT-Connect)的建模方法; 在数学优化模型中, 综合了路径平滑度、下潜梯度和航行时间等3项评价准则, 并考虑了强海流及障碍物带来的相关约束。然后针对上述模型, 提出了一种改进的鲸鱼优化算法。引入了基于问题连接结构的优化思想, 据此在线构建了关键子集族和有效子集族, 用于实时发现关键度和有效度较高的连接集, 并增大其重复利用率, 以提高算法的收敛速度和精度。此外, 为更全面有效地利用历史进化信息, 设计了多学习集构造个体引领者及联合引导策略, 以进一步增强算法的整体性能。最后根据实际海底地形信息和不同海流模型, 设置了多种路径规划情形进行仿真实验。结果表明, 相对于文献中其他鲸鱼优化算法和经典算法, 所提算法在求解精度、收敛速度和稳定性等方面均表现更为出色, 可较好地满足AUV航行的路径规划需求。

关键词: 路径规划, 鲸鱼优化算法, 自主水下机器人, 环境建模

Abstract:

Autonomous underwater vehicle (AUV) have become one kind of the most effective equipment for multiple underwater operations in different fields. A solution method for AUV global path planning is proposed based on improved whale optimization algorithm. Firstly, for the modelling of the problem, in the process of environment modelling, in view of the complexity of waypoint setting in 3D space, a modelling method based on the connected rapidly-exploring random tree (RRT-Connect) is presented; in the mathematical optimization model, three evaluation criteria including the path smoothness, the diving gradient and the navigation time are integrated, and the relevant constraints caused by strong currents and obstacles are considered. Then for the above models, an improved whale optimization algorithm is proposed. The optimization idea based on the linkage structure of the problem is introduced. And families of key subsets and effective subsets are constructed online according to it, which are adopted to discover the linkage sets with high criticality and effectiveness in real time, and increase the probability of their reuse rate, so as to improve the convergence speed and accuracy of proposed algorithm. In addition, to take advantage of historical evolution information more comprehensively and effectively, the method of constructing individual leaders with multiple learning sets and the corresponding joint guidance strategies are designed to further enhance the overall performance of the algorithm. Finally, according to the practical seabed terrain information and different ocean current models, several path planning scenarios are set up for simulation experiments. The results show that compared with other whale optimization algorithms and classical intelligent algorithms presented in references, the proposed algorithm is more superior in terms of solving accuracy, stability and convergence speed, which better meet the requirements of AUV path planning.

Key words: path planning, whale optimization algorithm (WOA), autonomous underwater vehicle (AUV), environment modeling

中图分类号:

TP242

李广强, 董文超, 朱大庆, 于越, 陈浩, 于双和. 基于改进鲸鱼优化算法的AUV三维路径规划[J]. 系统工程与电子技术, 2023, 45(7): 2170-2182.

Guangqiang LI, Wenchao DONG, Daqing ZHU, Yue YU, Hao CHEN, Shuanghe YU. 3D path planning for AUV based on improved whaleoptimization algorithm[J]. Systems Engineering and Electronics, 2023, 45(7): 2170-2182.

图/表 10

图1

图2

图3

表1

表2

图4

图5

表3

表4

表5

参考文献 23

24	CENCINI M , LACORATA G , VULPIANI A , et al. Mixing in a meandering jet: a markovian approximation[J]. Journal of Physical Oceanography, 1999, 29 (10): 2578- 2594. doi: 10.1175/1520-0485(1999)029<2578:MIAMJA>2.0.CO;2
25	KALA R , WARWICK K . Multi-vehicle planning using RRT-connect[J]. Paladyn, Journal of Behavioral Robotics, 2011, 2 (3): 134- 144.
26	BOUTER A , ALDERLIESTEN T , BOSMAN P A N . Achieving highly scalable evolutionary real-valued optimization by exploiting partial evaluations[J]. Evolutionary Computation, 2021, 29 (1): 129- 155.
27	BOUTER A, ALDERLIESTEN T, WITTEVEEN C, et al. Exploiting linkage information in real-valued optimization with the real-valued gene-pool optimal mixing evolutionary algorithm[C]//Proc. of the Genetic and Evolutionary Computation Conference, 2017: 705-712.
28	OLIEMAN C , BOUTER A , BOSMAN P A N . Fitness-based linkage learning in the real-valued gene-pool optimal mixing evolutionary algorithm[J]. IEEE Trans.on Evolutionary Computation, 2021, 25 (2): 358- 370.
29	WANG Y P , LIU H Y , WEI F , et al. Cooperative coevolution with formula-based variable grouping for large-scale global optimization[J]. Evolutionary Computation, 2018, 26 (4): 569- 596.
30	LIU Y H , CAO B Y , LI H H . Improving ant colony optimization algorithm with epsilon greedy and levy flight[J]. Complex & Intelligent Systems, 2021, 7 (4): 1711- 1722.
31	LI G Q, DONG W C, WANG Y J, et al. Path planning of underwater vehicles based on improved whale optimization algorithm[C]//Proc. of the International Conference on Automation, Control and Robotics Engineering, 2021: 444-448.
32	WANG M , LUO J , WALTER U . Trajectory planning of free-floating space robot using particle swarm optimization (PSO)[J]. Acta Astronautica, 2015, 112, 77- 88.
33	ZAMUDA A , HERNÁNDEZ SOSA J D . Differential evolution and underwater glider path planning applied to the short-term opportun-nistic sampling of dynamic mesoscale ocean structures[J]. Applied Soft Computing, 2014, 24, 95- 108.
34	GEBCO Compilation Group. The GEBCO_2020 grid[EB/OL]. [2022-04-17]. https://www.gebco.net/data_and_products/gridded_bathymetry_data/gebco_2020.
1	ATAEI M , YOUSEFI-KOMA A . Three-dimensional optimal path planning for waypoint guidance of an autonomous underwater vehicle[J]. Robotics and Autonomous Systems, 2015, 67, 23- 32. doi: 10.1016/j.robot.2014.10.007
2	ZENG Z , LIAN L , SAMMUT K , et al. A survey on path planning for persistent autonomy of autonomous underwater vehicles[J]. Ocean Engineering, 2015, 110, 303- 313. doi: 10.1016/j.oceaneng.2015.10.007
3	LI Y , MA T , CHEN P Y , et al. Autonomous underwater vehicle optimal path planning method for seabed terrain matching navigation[J]. Ocean Engineering, 2017, 133, 107- 115. doi: 10.1016/j.oceaneng.2017.01.026
4	LIU X A , MA D L , YANG M Q , et al. Modified block A^* path-planning method for hybrid-driven underwater gliders[J]. IEEE Journal of Oceanic Engineering, 2021, 47 (1): 20- 31.
5	GE H Q , CHEN G B , XU G . Multi-AUV cooperative target hunting based on improved potential field in a surface-water environment[J]. Applied Sciences, 2018, 8 (6): 973. doi: 10.3390/app8060973
6	冯豪博, 胡桥, 赵振轶. 基于精英族系遗传算法的AUV集群路径规划[J]. 系统工程与电子技术, 2022, 44 (7): 2251- 2262.
	FENG H B , HU Q , ZHAO Z Y . AUV swarm path planning based on elite family genetic algorithm[J]. Systems Engineering and Electronics, 2022, 44 (7): 2251- 2262.
7	张岳星, 王轶群, 李硕, 等. 基于海图和改进粒子群优化算法的AUV全局路径规划[J]. 机器人, 2020, 42 (1): 120- 128.
	ZHANG Y X , WANG Y Q , LI S , et al. Global path planning for AUV based on charts and the improved particle swarm optimization algorithm[J]. Robot, 2020, 42 (1): 120- 128.
8	TAHERI E , FERDOWSI M H , DANESH M . Closed-loop randomized kinodynamic path planning for an autonomous underwater vehicle[J]. Applied Ocean Research, 2019, 83, 48- 64. doi: 10.1016/j.apor.2018.12.008
9	CHEN M Z , ZHU D Q . Optimal time-consuming path planning for autonomous underwater vehicles based on a dynamic neural network model in ocean current environments[J]. IEEE Trans.on Vehicular Technology, 2020, 69 (12): 14401- 14412. doi: 10.1109/TVT.2020.3034628
10	ALBARAKATI S , LIMA R M , GIRALDI L , et al. Optimal 3D trajectory planning for AUVs using ocean general circulation models[J]. Ocean Engineering, 2019, 188, 106266. doi: 10.1016/j.oceaneng.2019.106266
11	ALBARAKATI S , LIMA R M , THEUSSL T , et al. Optimal 3D time-energy trajectory planning for auvs using ocean general circulation models[J]. Ocean Engineering, 2020, 218, 108057. doi: 10.1016/j.oceaneng.2020.108057
12	MA Y N , GONG Y J , XIAO C F , et al. Path planning for autonomous underwater vehicles: an ant colony algorithm incorporating alarm pheromone[J]. IEEE Trans.on Vehicular Technology, 2019, 68 (1): 141- 154. doi: 10.1109/TVT.2018.2882130
13	ZENG Z , LAMMAS A , SAMMUT K , et al. Shell space decomposition based path planning for AUVs operating in a variable environment[J]. Ocean Engineering, 2014, 91, 181- 195. doi: 10.1016/j.oceaneng.2014.09.001
14	MIRJALILI S , LEWIS A . The whale optimization algorithm[J]. Advances in Engineering Software, 2016, 95, 51- 67. doi: 10.1016/j.advengsoft.2016.01.008
15	BUI D T , ABDULLAHI M M , GHAREH S , et al. Fine-tuning of neural computing using whale optimization algorithm for predicting compressive strength of concrete[J]. Engineering with Computers, 2021, 37 (1): 701- 712. doi: 10.1007/s00366-019-00850-w
16	PETROVIC M , MILJKOVIC Z , JOKIC A . A novel methodo-logy for optimal single mobile robot scheduling using whale optimization algorithm[J]. Applied Soft Computing, 2019, 81, 105520. doi: 10.1016/j.asoc.2019.105520
17	SAAFAN M M , EL-GENDY E M . IWOSSA: an improved whale optimization salp swarm algorithm for solving optimization problems[J]. Expert Systems with Applications, 2021, 176, 114901. doi: 10.1016/j.eswa.2021.114901
18	ZHANG X M , WEN S C . Hybrid whale optimization algorithm with gathering strategies for high-dimensional problems[J]. Expert Systems with Applications, 2021, 179, 115032. doi: 10.1016/j.eswa.2021.115032
19	褚鼎立, 陈红, 王旭光. 基于自适应权重和模拟退火的鲸鱼优化算法[J]. 电子学报, 2019, 47 (5): 992- 999.
	CHU D L , CHEN H , WANG X G . Whale optimization algorithm based on adaptive weight and simulated annealing[J]. Acta Electronica Sinica, 2019, 47 (5): 992- 999.
20	HEIDARI A A , ALJARAH I , FARIS H , et al. An enhanced associative learning-based exploratory whale optimizer for glo-bal optimization[J]. Neural Computing & Applications, 2020, 32 (9): 5185- 5211.
21	ABD ELAZIZ M , LU S F , HE S B . A multi-leader whale optimization algorithm for global optimization and image segmentation[J]. Expert Systems with Applications, 2021, 175, 114841. doi: 10.1016/j.eswa.2021.114841
22	SUN Y J , CHEN Y . Multi-population improved whale optimization algorithm for high dimensional optimization[J]. Applied Soft Computing, 2021, 112, 107854. doi: 10.1016/j.asoc.2021.107854
23	HADSELL R, BAGNELL J A, HUBER D, et al. Accurate rough terrain estimation with space-carving kernels[C]//Proc. of the Robotics: Science and Systems, 2009.

情形	地形	海流	起始点/km	目标点/km
1	a	m	(2 758.82, 415.89, -1.43)	(2 964.60, 301.25, -4.01)
2	b	n	(1 910.45, 236.25, -0.47)	(2 113.89, 351.25, -3.16)
3	a	n	(2 758.82, 415.89, -3.09)	(2 964.60, 301.25, -4.01)
4	b	m	(1 910.45, 236.25, -1.98)	(2 113.89, 351.25, -3.16)

情形	路径点数	WOA	BMWOA	IWOSSA	HWOAG	PSO	DE	IWOA
1	5	336 161.0	336 414.8	366 179.6	358 860.0	339 030.2	335 388.0	335 451.2
	10	341 506.8	336 081.4	428 444.0	395 198.4	344 247.0	335 874.2	333 080.8
	15	656 472.4	491 059.8	#	498 216.6	458 622.6	341 501.6	332 501.4
2	6	242 808.8	241 502.8	241 340.0	249 229.2	312 066.2	241 209.0	242 209.8
	12	272 312.4	267 106.2	271 696.6	268 900.2	#	239 711.4	238 370.6
	18	#	#	#	#	#	262 821.6	237 803.2
3	6	276 393.6	276 022.8	277 964.8	279 114.0	276 084.8	274 896.6	274 514.0
	12	293 664.4	292 704.6	293 966.2	291 643.0	295 763.0	268 731.4	267 984.8
	18	#	#	#	#	#	270 212.2	266 882.4
4	7	354 772.8	349 677.8	365 973.0	376 550.0	350 856.0	343 702.8	345 397.0
	14	348 429.8	383 541.2	430 427.4	419 801.8	349 842.8	345 915.6	343 171.4
	21	463 174.0	780 443.4	#	437 306.6	369 718.6	353 991.0	344 885.4

情形	路径点数	WOA	BMWOA	IWOSSA	HWOAG	PSO	DE	IWOA
1	5	37 120	34 545	89 620	93 010	34 460	34 670	23 790
2	12	53 690	51 458	95 821	91 161	#	67 350	21 555
3	12	71 522	87 215	93 630	92 012	73 345	51 180	18 185
4	21	59 583	89 338	#	12 240	23 969	24 290	15 205

情形	路径点数	性能指标	WOA	BMWOA	IWOSSA	HWOAG	PSO	DE	IWOA
1	5	成功率/%	100	100	100	100	100	100	100
	5	相关标准差	15 220.0	8 523.0	10 316.2	57 898.4	28 723.2	4 149.2	412.2
	10	成功率/%	100	100	50	100	100	100	100
	10	相关标准差	84 120.0	96 531.8	110 657.2	33 609.4	85 818.8	11 422.2	2 700.0
	15	成功率/%	90	90	0	100	50	100	100
	15	相关标准差	37 331.8	104 553.8	#	13 016.0	103 182.4	18 616.4	7 307.1
2	6	成功率/%	50	90	30	40	20	100	100
	6	相关标准差	6 953.8	1 169.4	7 935.6	9 259.2	10 552.6	881.8	385.4
	12	成功率/%	20	40	30	30	0	90	100
	12	相关标准差	79 273.2	76 167.8	106 734.6	25 870.6	#	3 844.2	457.6
	18	成功率/%	0	0	0	0	0	50	90
	18	相关标准差	#	#	#	#	#	58 781.6	4 809.2
3	6	成功率/%	30	30	40	30	20	100	100
	6	相关标准差	3 187.6	5 630.0	7 450.2	2 852.6	3 867.0	382.4	338.0
	12	成功率/%	30	20	30	30	20	100	100
	12	相关标准差	57 039.6	63 058.2	94 418.4	26 315.4	87 847.8	1 475.4	699.2
	18	成功率/%	0	0	0	0	0	60	100
	18	相关标准差	#	#	#	#	#	15 598.6	1 074.1
4	7	成功率/%	100	100	100	100	90	100	100
	7	相关标准差	15 595.6	14 198.8	9 887.6	9 218.0	8 257.4	1 740.0	1 185.2
	14	成功率/%	90	80	70	90	50	100	100
	14	相关标准差	51 063.6	90 897.0	71 124.6	11 736.0	61 446.6	6 098.2	6 858.7
	21	成功率/%	70	60	0	100	40	100	100
	21	相关标准差	109 533.2	91 635.6	#	28 546.6	55 493.0	16 471.6	13 157.1

[1]	刘瑶, 夏阳升, 石建迈, 陈超, 黄金才. 车载多无人机协同多区域覆盖路径规划方法[J]. 系统工程与电子技术, 2023, 45(5): 1380-1390.
[2]	韩维, 刘子玄, 苏析超, 崔凯凯, 刘洁. 结合启发式与最优控制的舰载机甲板路径规划算法[J]. 系统工程与电子技术, 2023, 45(4): 1098-1110.
[3]	张浩杰, 张玉东, 梁荣敏, 杨甜甜. 改进A^*算法的机器人能耗最优路径规划方法[J]. 系统工程与电子技术, 2023, 45(2): 513-520.
[4]	冯豪博, 胡桥, 赵振轶. 基于精英族系遗传算法的AUV集群路径规划[J]. 系统工程与电子技术, 2022, 44(7): 2251-2262.
[5]	尹洋, 杨全顺, 王征, 刘洋. 通信距离约束下的无人船集群覆盖搜索方法[J]. 系统工程与电子技术, 2022, 44(12): 3821-3828.
[6]	杨清清, 高盈盈, 郭玙, 夏博远, 杨克巍. 基于深度强化学习的海战场目标搜寻路径规划[J]. 系统工程与电子技术, 2022, 44(11): 3486-3495.
[7]	马威强, 高永琪, 赵苗. 基于全局最优和差分变异的头脑风暴优化算法[J]. 系统工程与电子技术, 2022, 44(1): 270-278.
[8]	焦志强, 张杰勇, 姚佩阳, 王勋, 何宜超. 基于分层结构的C4ISR服务部署分布式演化方法[J]. 系统工程与电子技术, 2021, 43(6): 1572-1585.
[9]	王文明, 杜佳璐. 基于正六边形栅格JPS算法的智能体路径规划[J]. 系统工程与电子技术, 2021, 43(12): 3635-3642.
[10]	李亚南, 黄海滨, 陈亮名, 庄宇飞, 王晓丽. 变化海流环境下AUV能量最优三维路径规划[J]. 系统工程与电子技术, 2021, 43(12): 3667-3674.
[11]	李文刚, 汪流江, 方德翔, 李玉玮, 黄郡. 联合A^*与动态窗口法的路径规划算法[J]. 系统工程与电子技术, 2021, 43(12): 3694-3702.
[12]	陈岱岱, 李玩幽. 带拖线阵的水面无人艇局部路径规划算法[J]. 系统工程与电子技术, 2020, 42(9): 1988-1994.
[13]	张泉先, 曾斌, 李厚朴. 海况影响下的分布式海战补给路径规划方法[J]. 系统工程与电子技术, 2020, 42(10): 2312-2319.
[14]	时维国, 国明. 鲸鱼优化相关向量机的网络控制系统变采样周期调度[J]. 系统工程与电子技术, 2020, 42(10): 2348-2355.
[15]	杨秀霞, 曹唯一, 张毅. 时间和角度约束下的双圆弧路径规划[J]. 系统工程与电子技术, 2019, 41(8): 1835-1843.