蝴蝶优化算法的移动机器人全局路径规划研究

马小陆; 梅宏; 谭毅波; 龚瑞; 王兵

doi:10.13433/j.cnki.1003-8728.20220160

蝴蝶优化算法的移动机器人全局路径规划研究

doi: 10.13433/j.cnki.1003-8728.20220160

安徽工业大学电气与信息工程学院，安徽马鞍山　243002

基金项目: 国家自然科学基金项目(61472282)、安徽省科技重大专项(202003a05020028)、安徽高校自然科学研究重点项目(KJ2019A0065)、安徽省重点研究开发计划项目(202004a0502001)及特种重载机器人安徽省重点实验室开放课题(TZJQR004-2020)

详细信息

作者简介:
马小陆（1979−），副教授，硕士生导师，博士后，研究方向为嵌入式、车联网和服务机器人，77578249@qq.com

中图分类号: TP242.6
计量
- 文章访问数: 88
- HTML全文浏览量: 35
- PDF下载量: 14
- 被引次数: 0
出版历程
- 收稿日期: 2021-09-13
- 刊出日期: 2023-12-25

Research on Global Path Planning for Mobile Robot with Improved Butterfly Optimization Algorithm

School of Electrical and Information Engineering, Anhui University of Technology, Maanshan 243002,Anhui, China

摘要

摘要: 针对移动机器人路径规划问题提出了一种改进的蝴蝶优化算法。将蝴蝶优化算法与栅格法相结合，并对两种方法结合后的算法进行了具体说明；引入了禁忌表和回溯法,解决了算法在路径寻优中无后续扩展节点的问题；结合三次B样条曲线将路径规划中的最优节点作为控制点进行平滑输出，使移动机器人实际运动路径更加平滑。通过仿真实验，将改进算法与蚁群算法、遗传算法进行比较，证实了改进算法能够有效解决路径规划问题。将改进算法应用到实际的基于ROS的移动机器人上，实验结果证明了改进算法的有效性和可行性。
- 移动机器人 /
- 路径规划 /
- 蝴蝶优化算法 /
- 栅格法 /
- 三次B样条曲线
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.
- mobile robot /
- path planning /
- butterfly optimization algorithm /
- grid method /
- cubic B-spline curve

HTML全文

图 1 栅格法建立的环境

Figure 1. Environment established with the grid method

下载: 全尺寸图片幻灯片

图 2 回溯法解决蝴蝶陷入“假死”状态

Figure 2. Backtracking to solve the deadlock of a butterfly

下载: 全尺寸图片幻灯片

图 3 简单环境下3种算法路径规划仿真结果

Figure 3. Simulation results of three algorithms path planning under simple environment

下载: 全尺寸图片幻灯片

图 4 简单环境下3种算法最短路径长度变化曲线

Figure 4. Change curve of the shortest path length of three algorithms under simple environment

下载: 全尺寸图片幻灯片

图 5 一般环境下3种算法路径规划仿真结果

Figure 5. Path planning simulation data of three algorithms under general environment

下载: 全尺寸图片幻灯片

图 6 一般环境下3种算法最短路径长度变化曲线

Figure 6. Change curve of the shortest path length of three algorithms under general environment

下载: 全尺寸图片幻灯片

图 7 复杂环境下3种算法路径规划仿真结果

Figure 7. Path planning simulation results of three algorithms under complicated environment

下载: 全尺寸图片幻灯片

图 8 复杂环境下3种算法最短路径长度变化曲线

Figure 8. Change curve of the shortest path length of three algorithms under complex environment

下载: 全尺寸图片幻灯片

图 9 移动机器人实物图

Figure 9. Mobile robot's physical drawing

下载: 全尺寸图片幻灯片

图 10 ROS导航系统框架

Figure 10. Framework of ROS navigation system

下载: 全尺寸图片幻灯片

图 11 不同目标点下BOSA的路径规划

Figure 11. Path planning of BOSA under different target points

下载: 全尺寸图片幻灯片

表 1 ACO参数设置

Table 1. ACO parameter settings

参数	数值
信息启发式因子α	1
期望启发式因子β	7
信息素挥发系数ρ	0.3
初始信息素浓度Q	1

下载: 导出CSV

表 2 GA参数设置

Table 2. GA parameter settings

参数	数值
交叉概率p_c	0.65
变异概率p_m	0.01

下载: 导出CSV

表 3 BOSA参数设置

Table 3. BOSA parameter settings

参数	数值
转换概率P	0.8
蝴蝶感官形态c₀	0.01
幂指数a	0.1

下载: 导出CSV

表 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

下载: 导出CSV

表 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

下载: 导出CSV

表 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

下载: 导出CSV

表 7 两个目标点的路径长度和寻路时间

Table 7. Path lengths and search time of two target points

参数	目标点1	目标点2
路径长度/m	4.18	7.42
寻路时间/ms	352.7	617.3

下载: 导出CSV

参考文献(17)

[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.009 WEI 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-0043 LI 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.202004018 MA 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.0274 GAO 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.0611 SUN 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.202007008 WANG 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.042 HE 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.150267 WANG 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.003 CUI 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.040 LI 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