改进灰狼优化算法在特征栅格地图上的路径规划

音凌一; 向凤红; 毛剑琳

doi:10.13433/j.cnki.1003-8728.20220098

改进灰狼优化算法在特征栅格地图上的路径规划

doi: 10.13433/j.cnki.1003-8728.20220098

昆明理工大学信息工程与自动化学院，昆明　650500

基金项目: 云南省重点研发计划项目(202002AC080001）

详细信息

作者简介:
音凌一（1996−），硕士研究生，研究方向为智能算法、移动机器人路径规划，2667675770@qq.com

通讯作者:
向凤红，教授，博士，1026279708@qq.com

中图分类号: TP242
计量
- 文章访问数: 335
- HTML全文浏览量: 174
- PDF下载量: 25
- 被引次数: 0
出版历程
- 收稿日期: 2021-08-09
- 刊出日期: 2023-09-30

Improved Grey Wolf Optimization Algorithm for Path Planning on Feature Grid Maps

Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China

摘要

摘要: 针对灰狼优化算法求解移动机器人路径规划易陷入局部最优且效率低的问题，本文提出一种改进灰狼优化算法在特征栅格地图上的路径规划方法。首先，对灰狼优化算法进行改进，引入根据具体要求调节算法的全局搜索和局部搜索的调节因子，并引入动态权重和游走策略以提高算法的收敛速度和避免局部最优的能力；其次，提出一种建立特征栅格地图的新方法，加快了特征栅格的确定；最后设置远距离特征栅格和可视步长，简化了邻接矩阵的建立。仿真实验结果表明，本文算法相比于其它算法在标准测试函数和路径规划问题中，都有更优的结果。在此基础上，通过建立特征栅格地图，有效地加快了改进算法在路径规划问题上的求解速度。
- 灰狼优化算法 /
- 调节因子 /
- 动态权重 /
- 游走策略 /
- 特征栅格 /
- 路径规划
Abstract: In order for the grey wolf optimization algorithm to solve the problem of local optimization and low efficiency in the path planning of a mobile robot, an improved grey wolf optimization algorithm for path planning on a feature grid map is proposed. First, we improve the grey wolf optimization algorithm, introduce regulation factors to regulate the global and local search of the algorithm according to specific requirements and dynamic weights and walking strategies to improve the convergence speed of the algorithm and the ability to avoid local optimization. Secondly, the new method of building a feature grid map is proposed, which speeds up the determination of feature grids. Finally, a long-distance feature grid and visible step size are proposed to simplify the establishment of an adjacency matrix. The simulation results show that the algorithm proposed in this paper has better results on standard test functions and path planning problem solutions than other algorithms. On this basis, the establishment of the feature grid map effectively speeds up the algorithm's speed for solving path planning problems.
- grey wolf optimization algorithm /
- regulator factor /
- dynamic weight /
- walking strategy /
- feature grid /
- path planning

HTML全文

图 1 收敛因子对比图

Figure 1. Convergence factor comparison

下载: 全尺寸图片幻灯片

图 2 特征栅格的判定

Figure 2. Determination of characteristic grids

下载: 全尺寸图片幻灯片

图 3 提取特征栅格

Figure 3. Extraction of feature grids

下载: 全尺寸图片幻灯片

图 4 远距离栅格的去除

Figure 4. Removal of distant grids

下载: 全尺寸图片幻灯片

图 5 可视性判断

Figure 5. Visibility determination

下载: 全尺寸图片幻灯片

图 6 收敛曲线

Figure 6. Convergence curve

下载: 全尺寸图片幻灯片

图 7 20 × 20路径规划结果

Figure 7. 20 × 20 path planning results

下载: 全尺寸图片幻灯片

图 8 50 × 50路径规划结果

Figure 8. 50 × 50 path planning results

下载: 全尺寸图片幻灯片

图 9 30 × 30路径规划结果

Figure 9. 30 × 30 path planning results

下载: 全尺寸图片幻灯片

表 1 标准测试函数

Table 1. Standard test functions

函数种类	函数表达式	维数	搜索范围	最优值
单峰	${f_1}(x) = \displaystyle\sum\limits_{i = 1}^n {x_i^2}$	30	[−100,100]	0
	${f}_{\text{2} }(x)={\displaystyle \sum _{i=1}^{n}\left\|{x}_{i}\right\|} + {\displaystyle \prod _{i=1}^{n}\left\|{x}_{i}\right\|}$	30	[−10,10]	0
	${f_3}(x) = \displaystyle\sum\limits_{i = 1}^n { { {\left(\displaystyle\sum\limits_{j = 1}^n {x_j^2}\right)}^2} }$	30	[−100,100]	0
	${f_4}(x) = \displaystyle\sum\limits_{i = 1}^{n - 1} {[100{ {({x_{i + 1} } - x_i^2)}^2} + { {({x_i} - 1)}^2}]}$	30	[−100,100]	0
多峰	${f_5}(x) = \displaystyle\sum\limits_{i = 1}^n { - {x_i}\sin (\sqrt {\|{x_i}\|} )}$	30	[−500,500]	−418.982 × 5
	${f_6}(x) = \displaystyle\sum\limits_{i = 1}^n {[x_i^2 - 10\cos (2{\text{π}} {x_i}) + 10]}$	30	[−5.12,5.12]	0
	${f_7}(x) = - 20\exp \left( - 0.2\sqrt {\dfrac{1}{n}\displaystyle\sum\limits_{i = 1}^n {x_i^2} } \right) - \exp \left[\dfrac{1}{n}\displaystyle\sum\limits_{i = 1}^n {\cos (2{\text{π}} {x_i})} \right] + 20 + e$	30	[−32,32]	0
	${f_8}(x) = \dfrac{1}{ {4000} }\displaystyle\sum\limits_{i = 1}^n {x_i^2 - \prod\limits_{i = 1}^n {\cos \left(\dfrac{ { {x_i} } }{ {\sqrt i } }\right)} } + 1$	30	[−600,600]	0
固定多峰	${f_9}(x) = 4x_1^2 - 2.1x_1^4 + \dfrac{1}{3}x_1^6 + {x_1}{x_2} - 4x_2^2 + 4x_2^4$	2	[−5,5]	−1.0316
	${f_{10} } = {\left({x_2} - \dfrac{ {5.1} }{ {4{{\text{π}} ^2} } }x_1^2 + \dfrac{5}{{\text{π}} }{x_1} - 6\right)^2} + 10\left(1 - \dfrac{1}{ {8{\text{π}} } }\right)\cos {x_1} + 10$	2	[−5,5]	0.398
	$\begin{gathered} {f_{11} }(x) = [1 + {({x_1} + {x_2} + 1)^{_2} }(19 - 14{x_1} + 3x_1^2 - 14{x_2} + 6{x_1}{x_2} + 3x_2^2)]\times \\ \qquad\quad\;\; [30 + {(2{x_1} - 3{x_2})^2} \times (18 - 32x{}_1 + 12x_1^2 + 48{x_2} - 36{x_1}{x_2} + 27x_2^2)] \\ \end{gathered}$	2	[−2,2]	3
	${f_{12} }(x) = - \displaystyle\sum\limits_{i = 1}^4 { {c_i} } \exp \left( - \displaystyle\sum\limits_{j = 3}^3 { {a_{ij} }{ {({x_j} - {p_{ij} })}^2} } \right)$	3	[0,1]	−3.86

下载: 导出CSV

表 2 标准测试函数仿真结果

Table 2. Simulation results for standard test functions

测试函数	性能	GWO	PSOGWO	EGWO	IGWO1	IGWO2	IGWO3	IGWO
f₁	平均值标准差	4.2506×10⁻⁶⁰ 6.9223×10⁻⁶⁰	0 0	1.6421×10⁻¹⁰⁴ 2.8262×10⁻¹⁰⁴	2.8630×10⁻⁶⁵ 3.2616×10⁻⁶⁵	5.5788×10⁻⁹⁹ 7.1811×10⁻⁹⁹	0 0	0 0
f₂	平均值标准差	8.7548×10⁻³⁵ 4.4219×10⁻³⁵	2.0034×10⁻²⁹⁶ 0	2.9283×10⁻⁶¹ 2.0947×10⁻⁶¹	4.1016×10⁻³⁷ 3.4972×10⁻³⁷	1.7305×10⁻⁵⁷ 1.6171×10⁻⁵⁷	0 0	0 0
f₃	平均值标准差	3.9317×10⁻¹⁶ 3.9508×10⁻¹⁶	3.6200×10⁻²¹⁷ 0	1.1131×10⁻²⁸ 2.1633×10⁻²⁸	2.8009×10⁻¹⁷ 5.5760×10⁻¹⁷	4.9248×10⁻²⁴ 6.9601×10⁻²⁴	0 0	0 0
f₄	平均值标准差	27.45 0.3775	27.26 0.2255	27.36 0.3465	26.91 0.3391	26.60 0.6333	28.94 0.0191	28.90 0.0671
f₅	平均值标准差	−5840.9922 1176.7241	−3903.6510 296.1040	−3167.73256 439.1061	−4852.3953 88.3285	−3772.8645 107.64	−2965.4925 886.2651	−2550.0054 225.3381
f₆	平均值标准差	0 0	0 0	0 0	0 0	0 0	0 0	0 0
f₇	平均值标准差	1.6875×10⁻¹⁴ 3.0765×10⁻¹⁴	2.9132×10⁻¹⁵ 1.7567×10⁻¹⁵	3.8482×10⁻¹⁵ 3.1868×10⁻¹⁵	8.1817×10⁻¹⁵ 1.5382×10⁻¹⁵	8.7830×10⁻¹⁵ 2.2330×10⁻¹⁵	3.1521×10⁻¹⁵ 5.2366×10⁻¹⁵	2.6645×10⁻¹⁵ 2.7134×10⁻¹⁵
f₈	平均值标准差	0 0	0 0	0 0	0 0	0 0	0 0	0 0
f₉	平均值标准差	−1.0316 0	−1.0315 0.00005	−1.0325 0.0038	−1.0316 0	−1.0316 0	−1.0069 0.0105	−1.0262 0.0065
f₁₀	平均值标准差	0.3978 4.0399×10⁻⁵	0.3996 0.0012	0.3978 0.00031	0.398 9.4531×10⁻⁵	0.3979 8.3282×10⁻⁵	1.9313 0.9951	0.4138 0.1328
f₁₁	平均值标准差	3 0	3.0002 0.00012	3.0001 8.1169×10⁻⁶	3 0	3 0	15.1721 16.8	3.0011 0.0017
f₁₂	平均值标准差	−3.8605 0.0033	−3.8570 0.0020	−3.8557 0.0019	−3.8602 0.0009	−3.8616 0.0010	−3.2392 0.2618	−3.8209 0.0167

下载: 导出CSV

表 3 20次仿真平均结果

Table 3. Average results from 20 simulations

地图种类	地图大小	评价标准	GA	PSO	GWO	IGWO
普通栅格地图	20 × 20	路径长度	33.72	32.70	30.86	29.79
		节点个数	13.71	8.29	9.52	9.14
		寻优时间/s	14.46	14.55	14.62	20.76
	50 × 50	路径长度	86.18	83.56	80.43	76.24
		节点个数	34.79	32.33	32.64	30.67
		寻优时间/s	112.81	148.88	144.71	208.55

特征栅格地图	20 × 20	路径长度	31.24	30.12	29.51	29.06
		节点个数	7.83	6.00	5.83	5.33
		寻优时间/s	5.94	5.53	4.43	6.83
	50 × 50	路径长度	78.97	78.21	76.93	75.83
		节点个数	17.67	17.60	14.60	11.29
		寻优时间/s	19.39	16.94	17.53	24.69

下载: 导出CSV

表 4 30 × 30地图实验结果对比

Table 4. Comparison of experimental results on 30 × 30 maps

算法	文献[19]算法	IGWO算法
路径最优长度	45.1127	46.3900
节点个数	14	9
寻优时间/s	17.6911	12.1523
与障碍物相切点	8	4

下载: 导出CSV

参考文献(19)

[1]	康亮, 赵春霞, 郭剑辉. 未知环境下改进的基于BUG算法的移动机器人路径规划[J]. 系统仿真学报, 2009, 21(17): 5414-5422. KANG L, ZHAO C X, GUO J H. Improved path planning based on bug algorithm for mobile robot in unknown environment[J]. Journal of System Simulation, 2009, 21(17): 5414-5422. (in Chinese)
[2]	LIU J H, YANG J G, LIU H P, et al. An improved ant colony algorithm for robot path planning[J]. Soft Computing, 2017, 21(19): 5829-5839. doi: 10.1007/s00500-016-2161-7
[3]	TANG B W, XIANG K, PANG M Y, et al. Multi-robot path planning using an improved self-adaptive particle swarm optimization[J]. International Journal of Advanced Robotic Systems, 2020, 17(5): 172988142093615.
[4]	FAN T H, WANG J Y, FENG M R, et al. Application of multi-objective firefly algorithm based on archive learning in robot path planning[J]. International Journal of Intelligent Information and Database Systems, 2019, 12(3): 199-211. doi: 10.1504/IJIIDS.2019.102939
[5]	MIRJALILI S, MIRJALILI S M, LEWIS A. Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69: 46-61. doi: 10.1016/j.advengsoft.2013.12.007
[6]	RASHEDI E, RASHEDI E, NEZAMABADI-POUR H. A comprehensive survey on gravitational search algorithm[J]. Swarm and Evolutionary Computation, 2018, 41: 141-158. doi: 10.1016/j.swevo.2018.02.018
[7]	TIAN M N, GAO X B. Differential evolution with neighborhood-based adaptive evolution mechanism for numerical optimization[J]. Information Sciences, 2019, 478: 422-448. doi: 10.1016/j.ins.2018.11.021
[8]	MAGHAWRY A, HODHOD R, OMAR Y, et al. An approach for optimizing multi-objective problems using hybrid genetic algorithms[J]. Soft Computing, 2021, 25: 389-405. doi: 10.1007/s00500-020-05149-3
[9]	TOLOUEI K, MOOSAVI E. Production scheduling problem and solver improvement via integration of the grey wolf optimizer into the augmented Lagrangian relaxation method[J]. SN Applied Sciences, 2020, 2(12): 1963. doi: 10.1007/s42452-020-03758-z
[10]	RODRIGUES L R. A chaotic grey wolf optimizer for constrained optimization problems[J/OL]. (2021-05-26) [2021-07-10] Expert Systems, 2021. https://onlinelibrary.wiley.com/doi/abs/10.1111/exsy.12719.
[11]	龙文, 蔡绍洪, 焦建军, 等. 求解高维优化问题的混合灰狼优化算法[J]. 控制与决策, 2016, 31(11): 1991-1997. LONG W, CAI S H, JIAO J J, et al. Hybrid grey wolf optimization algorithm for high-dimensional optimization[J]. Control and Decision, 2016, 31(11): 1991-1997. (in Chinese)
[12]	LONG W, JIAO J J, LIANG X M, et al. Inspired grey wolf optimizer for solving large-scale function optimization problems[J]. Applied Mathematical Modelling, 2018, 60: 112-126. doi: 10.1016/j.apm.2018.03.005
[13]	滕志军, 吕金玲, 郭力文, 等. 一种基于Tent映射的混合灰狼优化的改进算法[J]. 哈尔滨工业大学学报, 2018, 50(11): 40-49. doi: 10.11918/j.issn.0367-6234.201806096 TENG Z J, LYU J L, GUO L W, et al. An improved hybrid grey wolf optimization algorithm based on Tent mapping[J]. Journal of Harbin Institute of Technology, 2018, 50(11): 40-49. (in Chinese) doi: 10.11918/j.issn.0367-6234.201806096
[14]	魏政磊, 赵辉, 李牧东, 等. 控制参数值非线性调整策略的灰狼优化算法[J]. 空军工程大学学报(自然科学版), 2016, 17(3): 68-72. WEI Z L, ZHAO H, LI M D, et al. A grey wolf optimization algorithm based on nonlinear adjustment strategy of control parameter[J]. Journal of Air Force Engineering University (Natural Science Edition), 2016, 17(3): 68-72. (in Chinese)
[15]	刘二辉, 姚锡凡, 刘敏, 等. 基于改进灰狼优化算法的自动导引小车路径规划及其实现原型平台[J]. 计算机集成制造系统, 2018, 24(11): 2779-2791. LIU E H, YAO X F, LIU M, et al. AGV path planning based on improved grey wolf optimization algorithm and its implementation prototype platform[J]. Computer Integrated Manufacturing Systems, 2018, 24(11): 2779-2791. (in Chinese)
[16]	ZHANG W, ZHANG S, WU F Y, et al. Path planning of UAV based on improved adaptive grey wolf optimization algorithm[J]. IEEE Access, 2021, 9: 89400-89411. doi: 10.1109/ACCESS.2021.3090776
[17]	赵江, 孟晨阳, 王晓博, 等. 特征点提取下的AGV栅格法建模与分析[J]. 计算机工程与应用, 2022, 58(8): 156-167. ZHAO J, MENG C Y, WANG X B, et al. Modeling and analysis of AGV grid method based on feature points extraction[J]. Computer Engineering and Applications, 2022, 58(8): 156-167. (in Chinese)
[18]	黎素涵, 叶春明. 重选精英个体的非线性收敛灰狼优化算法[J]. 计算机工程与应用, 2021, 57(1): 62-68. doi: 10.3778/j.issn.1002-8331.2003-0121 LI S H, YE C M. Improved grey wolf optimizer algorithm using nonlinear convergence factor and elite re-election strategy[J]. Computer Engineering and Applications, 2021, 57(1): 62-68. (in Chinese) doi: 10.3778/j.issn.1002-8331.2003-0121
[19]	王晓燕, 杨乐, 张宇, 等. 基于改进势场蚁群算法的机器人路径规划[J]. 控制与决策, 2018, 33(10): 1775-1781. WANG X Y, YANG L, ZHANG Y, et al. Robot path planning based on improved ant colony algorithm with potential field heuristic[J]. Control and Decision, 2018, 33(10): 1775-1781. (in Chinese)