Improved Grey Wolf Optimization Algorithm for Path Planning on Feature Grid Maps
-
摘要: 针对灰狼优化算法求解移动机器人路径规划易陷入局部最优且效率低的问题,本文提出一种改进灰狼优化算法在特征栅格地图上的路径规划方法。首先,对灰狼优化算法进行改进,引入根据具体要求调节算法的全局搜索和局部搜索的调节因子,并引入动态权重和游走策略以提高算法的收敛速度和避免局部最优的能力;其次,提出一种建立特征栅格地图的新方法,加快了特征栅格的确定;最后设置远距离特征栅格和可视步长,简化了邻接矩阵的建立。仿真实验结果表明,本文算法相比于其它算法在标准测试函数和路径规划问题中,都有更优的结果。在此基础上,通过建立特征栅格地图,有效地加快了改进算法在路径规划问题上的求解速度。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.
-
Key words:
- grey wolf optimization algorithm /
- regulator factor /
- dynamic weight /
- walking strategy /
- feature grid /
- path planning
-
表 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 表 2 标准测试函数仿真结果
Table 2. Simulation results for standard test functions
测试函数 性能 GWO PSOGWO EGWO IGWO1 IGWO2 IGWO3 IGWO f1 平均值
标准差4.2506×10−60
6.9223×10−600
01.6421×10−104
2.8262×10−1042.8630×10−65
3.2616×10−655.5788×10−99
7.1811×10−990
00
0f2 平均值
标准差8.7548×10−35
4.4219×10−352.0034×10−296
02.9283×10−61
2.0947×10−614.1016×10−37
3.4972×10−371.7305×10−57
1.6171×10−570
00
0f3 平均值
标准差3.9317×10−16
3.9508×10−163.6200×10−217
01.1131×10−28
2.1633×10−282.8009×10−17
5.5760×10−174.9248×10−24
6.9601×10−240
00
0f4 平均值
标准差27.45
0.377527.26
0.225527.36
0.346526.91
0.339126.60
0.633328.94
0.019128.90
0.0671f5 平均值
标准差−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.3381f6 平均值
标准差0
00
00
00
00
00
00
0f7 平均值
标准差1.6875×10−14
3.0765×10−142.9132×10−15
1.7567×10−153.8482×10−15
3.1868×10−158.1817×10−15
1.5382×10−158.7830×10−15
2.2330×10−153.1521×10−15
5.2366×10−152.6645×10−15
2.7134×10−15f8 平均值
标准差0
00
00
00
00
00
00
0f9 平均值
标准差−1.0316
0−1.0315
0.00005−1.0325
0.0038−1.0316
0−1.0316
0−1.0069
0.0105−1.0262
0.0065f10 平均值
标准差0.3978
4.0399×10−50.3996
0.00120.3978
0.000310.398
9.4531×10−50.3979
8.3282×10−51.9313
0.99510.4138
0.1328f11 平均值
标准差3
03.0002
0.000123.0001
8.1169×10−63
03
015.1721
16.83.0011
0.0017f12 平均值
标准差−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表 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 表 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 -
[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.201806096TENG 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-0121LI 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)