Research on Global Path Planning for Mobile Robot with Improved Butterfly Optimization Algorithm
-
摘要: 针对移动机器人路径规划问题提出了一种改进的蝴蝶优化算法。将蝴蝶优化算法与栅格法相结合,并对两种方法结合后的算法进行了具体说明;引入了禁忌表和回溯法,解决了算法在路径寻优中无后续扩展节点的问题;结合三次B样条曲线将路径规划中的最优节点作为控制点进行平滑输出,使移动机器人实际运动路径更加平滑。通过仿真实验,将改进算法与蚁群算法、遗传算法进行比较,证实了改进算法能够有效解决路径规划问题。将改进算法应用到实际的基于ROS的移动机器人上,实验结果证明了改进算法的有效性和可行性。Abstract: An improved butterfly optimization algorithm is proposed for mobile robot path planning. Firstly, the butterfly optimization algorithm is combined with the grid method, and the combined algorithm is explained in detail. Secondly, the tabu list and backtracking method are introduced to solve the problem that the algorithm has no subsequent extension nodes in the path optimization. Finally, combined with cubic B-spline curve, the optimal node in the path planning is taken as the control point for smooth output, which makes the actual motion path of mobile robot smoother. Through the simulation experiment, the improved algorithm is compared with ant colony algorithm and genetic algorithm, theresult proves that the improved algorithm can effectively solve the path planning problem, and is an effective and feasible optimization algorithm.Finally, the improved algorithm is applied to the actual mobile robot based on ROS. The experimental results also prove the effectiveness and feasibility of the improved algorithm.
-
Key words:
- mobile robot /
- path planning /
- butterfly optimization algorithm /
- grid method /
- cubic B-spline curve
-
表 1 ACO参数设置
Table 1. ACO parameter settings
参数 数值 信息启发式因子α 1 期望启发式因子β 7 信息素挥发系数ρ 0.3 初始信息素浓度Q 1 表 2 GA参数设置
Table 2. GA parameter settings
参数 数值 交叉概率pc 0.65 变异概率pm 0.01 表 3 BOSA参数设置
Table 3. BOSA parameter settings
参数 数值 转换概率P 0.8 蝴蝶感官形态c0 0.01 幂指数a 0.1 表 4 简单环境下3种算法仿真数据对比
Table 4. Comparison of simulation data of three algorithms under simple environment
算法 最小值 最大值 平均值 收敛迭代次数 ACO 30.38 46.04 33.25 56 GA 30.38 75.70 34.66 36 BOSA 29.64 45.11 31.86 32 表 5 一般环境下3种算法仿真数据对比
Table 5. Comparison of simulation data of three algorithms under general environment
算法 最小值 最大值 平均值 收敛迭代次数 ACO 29.80 45.70 33.10 72 GA 29.80 102.28 39.72 37 BOSA 28.48 47.94 30.95 29 表 6 复杂环境下3种算法仿真数据对比
Table 6. Comparison of simulation data of three algorithms under complex environment
算法 最小值 最大值 平均值 迭代次数 ACO 30.97 50.04 34.21 66 GA 31.56 106.28 40.92 45 BOSA 28.82 51.11 32.38 39 表 7 两个目标点的路径长度和寻路时间
Table 7. Path lengths and search time of two target points
参数 目标点1 目标点2 路径长度/m 4.18 7.42 寻路时间/ms 352.7 617.3 -
[1] SALOMON R. Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. A survey of some theoretical and practical aspects of genetic algorithms[J]. Biosystems, 1996, 39(3): 263-278. doi: 10.1016/0303-2647(96)01621-8 [2] 魏勇, 赵开新, 王东署. 改进粒子群算法在移动机器人路径规划中的应用[J]. 火力与指挥控制, 2018, 43(2): 41-43. doi: 10.3969/j.issn.1002-0640.2018.02.009WEI Y, ZHAO K X, WANG D S. Application of improved particle swarm optimization algorithm in path planning of mobile robot[J]. Fire Control & Command Control, 2018, 43(2): 41-43. (in Chinese) doi: 10.3969/j.issn.1002-0640.2018.02.009 [3] KARABOGA D, BASTURK B. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm[J]. Journal of Global Optimization, 2007, 39(3): 459-471. doi: 10.1007/s10898-007-9149-x [4] 李丽娜, 郭永强, 张晓东, 等. 萤火虫算法结合人工势场法的机器人路径规划[J]. 计算机工程与应用, 2018, 54(20): 104-109. doi: 10.3778/j.issn.1002-8331.1801-0043LI L N, GUO Y Q, ZHANG X D, et al. Path planning algorithm for robot based on firefly algorithm combined with artificial potential field method[J]. Computer Engineering and Applications, 2018, 54(20): 104-109. (in Chinese) doi: 10.3778/j.issn.1002-8331.1801-0043 [5] 马小铭, 靳伍银. 基于改进蚁群算法的多目标路径规划研究[J]. 计算技术与自动化, 2020, 39(4): 100-105. doi: 10.16339/j.cnki.jsjsyzdh.202004018MA X M, JIN W Y. Mulit-objcctive path planning based on improved and colony algorithm[J]. Computing Technology and Automation, 2020, 39(4): 100-105. (in Chinese) doi: 10.16339/j.cnki.jsjsyzdh.202004018 [6] ARORA S, SINGH S. Butterfly optimization algorithm: a novel approach for global optimization[J]. Soft Computing, 2019, 23(3): 715-734. doi: 10.1007/s00500-018-3102-4 [7] ARORA S, SINGH S. An effective hybrid butterfly optimization algorithm with artificial bee colony for numerical optimization[J]. International Journal of Interactive Multimedia and Artificial Intelligence, 2017, 4(4): 14-21. doi: 10.9781/ijimai.2017.442 [8] ARORA S, SINGH S. An improved butterfly optimization algorithm for global optimization[J]. Advanced Science, Engineering and Medicine, 2016, 8(9): 711-717. doi: 10.1166/asem.2016.1904 [9] ARORA S, SINGH S. Butterfly algorithm with Lèvy flights for global optimization[C]//Proceedings of 2015 International Conference on Signal Processing, Computing and Control. Waknaghat: IEEE, 2015: 220-224. [10] 高文欣, 刘升, 肖子雅, 等. 全局优化的蝴蝶优化算法[J]. 计算机应用研究, 2020, 37(10): 2966-2970. doi: 10.19734/j.issn.1001-3695.2019.07.0274GAO W X, LIU S, XIAO Z Y, et al. Butterfly optimization algorithm for global optimization[J]. Application Research of Computers, 2020, 37(10): 2966-2970. (in Chinese) doi: 10.19734/j.issn.1001-3695.2019.07.0274 [11] 孙林, 陈岁岁, 徐久成, 等. 基于交叉迁移和共享调整的改进蝴蝶优化算法[J]. 计算机应用研究, 2020, 37(3): 799-804. doi: 10.19734/j.issn.1001-3695.2018.07.0611SUN L, CHEN S S, XU J C, et al. Improved monarch butterfly optimization algorithm based on cross migration and sharing adjustment[J]. Application Research of Computers, 2020, 37(3): 799-804. (in Chinese) doi: 10.19734/j.issn.1001-3695.2018.07.0611 [12] 谢聪, 封宇. 一种改进的蝴蝶优化算法[J]. 数学的实践与认识, 2020, 50(13): 105-115.XIE C, FENG Y. An improved butterfly optimization algorithm[J]. Mathematics in Practice and Theory, 2020, 50(13): 105-115. (in Chinese) [13] 王依柔, 张达敏. 融合正弦余弦和无限折叠迭代混沌映射的蝴蝶优化算法[J]. 模式识别与人工智能, 2020, 33(7): 660-669. doi: 10.16451/j.cnki.issn1003-6059.202007008WANG Y R, ZHANG D M. Butterfly optimization algorithm combining sine cosine and iterative chaotic map with infinite collapses[J]. Pattern Recognition and Artificial Intelligence, 2020, 33(7): 660-669. (in Chinese) doi: 10.16451/j.cnki.issn1003-6059.202007008 [14] 何娟, 涂中英, 牛玉刚. 一种遗传蚁群算法的机器人路径规划方法[J]. 计算机仿真, 2010, 27(3): 170-174. doi: 10.3969/j.issn.1006-9348.2010.03.042HE J, TU Z Y, NIU Y G. A method of mobile robotic path planning based on integrating of GA and ACO[J]. Computer Simulation, 2010, 27(3): 170-174. (in Chinese) doi: 10.3969/j.issn.1006-9348.2010.03.042 [15] 王仲民, 井平安, 朱博. 基于神经元激励的移动机器人遍历路径规划[J]. 控制工程, 2017, 24(2): 283-286. doi: 10.14107/j.cnki.kzgc.150267WANG Z M, JING P A, ZHU B. Coverage path planning of mobile robot based on neuronal excitation[J]. Control Engineering of China, 2017, 24(2): 283-286. (in Chinese) doi: 10.14107/j.cnki.kzgc.150267 [16] 崔东文. 改进蝴蝶优化算法-投影寻踪模型在区域河长制考核评价中的应用[J]. 三峡大学学报(自然科学版), 2019, 41(5): 12-18. doi: 10.13393/j.cnki.issn.1672-948x.2019.05.003CUI D W. Application of improved butterfly optimization algorithm-projection pursuit model to regional river chief system[J]. Journal of China Three Gorges University (Natural Sciences), 2019, 41(5): 12-18. (in Chinese) doi: 10.13393/j.cnki.issn.1672-948x.2019.05.003 [17] 李田来, 刘方爱. 带混沌映射的WSN蝴蝶优化定位算法[J]. 计算机工程与设计, 2019, 40(6): 1729-1733. doi: 10.16208/j.issn1000-7024.2019.06.040LI T L, LIU F A. Butterfly optimization localization algorithm with chaotic map in wireless sensor networks[J]. Computer Engineering and Design, 2019, 40(6): 1729-1733. (in Chinese) doi: 10.16208/j.issn1000-7024.2019.06.040