基于改进蚁群算法的移动机器人路径规划研究
|
摘要
针对蚁群算法在复杂环境下收敛速度慢且易陷入局部最优值的问题,提出一种改进的蚁群优化算法。该方法依据起始点和目标点位置信息选择全局有利区域增加初始信息素浓度,提高前期蚂蚁搜索效率;增加避障策略,避免蚂蚁盲目搜索产生大量交叉路径并有效减少蚂蚁死锁数量;采用动态参数控制的伪随机转移策略,提出优质蚂蚁信息素更新原则,自适应调整挥发系数,提高算法全局性;进行二次路径规划,优化路径并降低移动机器人能耗的损失。实验结果表明,该算法有较高的全局搜索能力,收敛速度明显加快,并且可以有效提高移动机器人工作效率,验证了该算法的有效性和优越性。
The ant colony algorithm is slow in convergence and easy to fall into local optimal value in complex environment. To solve these problems, an improved ant colony optimization algorithm is proposed. The position information of the starting point and the target point are utilized to select the global favorable region. In this way, the initial pheromone concentration is increased and the efficiency of early ant search is improved. The obstacle avoidance strategy is added to avoid ant blind search. A large number of cross paths are generated and the number of ant deadlocks is effectively reduced. Based on the pseudorandom transfer strategy of dynamic parameter control, the global performance of the algorithm is improved. The updating principle of high quality ant pheromone and adjusting the volatility coefficient adaptively are proposed. The second path planning is carried out to optimize the path and reduce the loss of energy consumption of mobile robots. Experimental results show that the algorithm has the feature of higher global searching ability, faster convergence speed and higher working efficiency of mobile robot. The proposed algorithm is verified to be effective and superior.
The ant colony algorithm is slow in convergence and easy to fall into local optimal value in complex environment. To solve these problems, an improved ant colony optimization algorithm is proposed. The position information of the starting point and the target point are utilized to select the global favorable region. In this way, the initial pheromone concentration is increased and the efficiency of early ant search is improved. The obstacle avoidance strategy is added to avoid ant blind search. A large number of cross paths are generated and the number of ant deadlocks is effectively reduced. Based on the pseudorandom transfer strategy of dynamic parameter control, the global performance of the algorithm is improved. The updating principle of high quality ant pheromone and adjusting the volatility coefficient adaptively are proposed. The second path planning is carried out to optimize the path and reduce the loss of energy consumption of mobile robots. Experimental results show that the algorithm has the feature of higher global searching ability, faster convergence speed and higher working efficiency of mobile robot. The proposed algorithm is verified to be effective and superior.
引文
[1] 陈彦杰,王耀南,谭建豪,等. 局部环境增量采样的服务机器人路径规划[J]. 仪器仪表学报,2017,38(5):1093-1100.CHEN Y J, WANG Y N, TAN J H, et al. Incremental sampling path planning for service robot based on local environments [J]. Chinese Journal of Scientific Instrument, 2017, 38(5): 1093-1100.
[2] 刘二辉,姚锡凡,蓝宏宇,等. 基于改进遗传算法的自动导引小车动态路径规划及其实现[J]. 计算机集成制造系统,2018,24(6):1455-1467.LIU E H, YAO X F, LAN H Y, et al. AGV dynamic path planning based on improved genetic algorithm and its implementation [J]. Computer Integrated Manufacturing Systems, 2018, 24(6): 1455-1467.
[3] JUANG C F, YEH Y T. Multiobjective evolution of biped robot gaits using advanced continuous ant-colony optimized recurrent neural networks [J]. IEEE Transactions on Cybernetics, 2018, 48(6): 1910-1922.
[4] 许川佩,吕莹,黄喜军,等. 基于粒子群算法的数字微流控芯片在线测试路径优化[J].电子测量与仪器学报,2017,31(8):1192-1199.XU CH P, LV Y, HUANG X J, et al. On-line test route optimization of digital microfluidic chip based on particle swarm optimization[J]. Journal of Electronic Measurement and Instrumentation, 2017, 31(8):1192-1199.
[5] 刘浩然,孙美婷,李雷,等. 基于蚁群节点寻优的贝叶斯网络结构算法研究[J].仪器仪表学报,2017,38(1): 143-150.LIU H R,SUN M T, LI L, et al. Study on Bayesian network structure learning algorithm based on ant colony node order optimization [J].Chinese Journal of Scientific Instrument, 2017, 38(1): 143-150.
[6] DORIGO M, GAMBARDELLA L M. Ant colony system: A cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1):5 3- 66.
[7] 游晓明,刘升,吕金秋. 一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J].控制与决策,2017,32(3):552- 556.YOU X M, LIU SH, LV J Q. Ant colony algorithm based on dynamic search strategy and its application on path planning of robot [J]. Control and Decision, 2017, 32(3): 552- 556.
[8] 汪杰君,刘江宽,黄喜军,等. 基于混合遗传蚁群算法的数字微流控芯片测试路径规划[J].电子测量与仪器学报,2017,31(8):1183-1191.WANG J J, LIU J K, HUANG X J, et, al. Test path scheduleing of digital microfluidic biochips based on combined genetic and ant colony algorithm [J]. Journal of Electronic Measurement and Instrumentation, 2017, 31(8): 1183-1191.
[9] 屈鸿,黄利伟,柯星. 动态环境下基于改进蚁群算法的机器人路径规划研究[J].电子科技大学学报,2015,44 (2):260- 265.QU H, HUANG L W, KE X. Research of improved ant colony based robot path planning under dynamic environment [J]. Journal of University of Electronic Science and Technology of China, 2015, 44(2): 260- 265.
[10] 张成,凌有铸,陈孟元. 改进蚁群算法求解移动机器人路径规划[J]. 电子测量与仪器学报, 2016,30(11):1758-1764.ZHANG CH, LING Y ZH, CHEN M Y. Path planning of mobile robot based on an improved ant colony algorithm [J]. Journal of Electronic Measurement and Instrumentation, 2016, 30(11): 30-37.
[11] 王晓燕,杨乐,张宇,等. 基于改进势场蚁群算法的机器人路径规划[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.
[12] SUN Y, DONG W, CHEN Y. An improved routing algorithm based on ant colony optimization in wireless sensor networks [J]. IEEE Communications Letters, 2017, 21(6): 1317-1320.
[13] 梁建刚,刘晓平,王刚,等. 基于改进蚁群算法的自动导引运输车全局路径规划方法研究[J].机电工程,2018,35(4):431- 436.LIANG J G, LIU X P, WANG G,et al. Global path planning for automated guided vehicle based on improved ant colony algorithm [J]. Journal of Mechanical & Electrical Engineering, 2018, 35(4): 431- 436.
[14] 刘建华,杨建国,刘华平,等. 基于势场蚁群算法的移动机器人全局路径规划方法[J].农业机械学报,2015, 46(9):18- 27.LIU J H, YANG J G, LIU H P, et al. Robot global path planning based on ant colony optimization with artificial potential field [J]. Journal of Agricultural Machinery, 2015, 46(9): 18- 27.
[15] 夏小云,周育人. 蚁群优化算法的理论研究进展[J]. 智能系统学报,2016,11(1):27-36.XIA X Y, ZHOU Y R. Advances in theoretical research of ant colony optimization [J]. CAAI Transactions on Intelligent Systems, 2016, 11(1): 27-36.
[16] 李龙澍,喻环. 改进蚁群算法在复杂环境中机器人路径规划上的应用[J].小型微型计算机系统,2017,38(9): 2067- 2071.LI L SH, YU H. Improved ant colony algorithm in complex environments on the robot path planning [J]. Journal of Chinese Computer Systems,2017, 38(9): 2067- 2071.
[17] JIAO Z, MA K, RONG Y, et al. A path planning method using adaptive polymorphic ant colony algorithm for smart wheelchairs [J]. Journal of Computational Science, 2018(25):50- 57.
[18] CAO J. Robot global path planning based on an improved ant colony algorithm [J]. Journal of Computer and Communications, 2016, 4(2): 11.
[19] JABBARPOUR M R, ZARRABI H, JUNG J J, et al. A green ant-based method for path planning of unmanned ground vehicles [J]. IEEE Access, 2017(5): 1820-1832.
[2] 刘二辉,姚锡凡,蓝宏宇,等. 基于改进遗传算法的自动导引小车动态路径规划及其实现[J]. 计算机集成制造系统,2018,24(6):1455-1467.LIU E H, YAO X F, LAN H Y, et al. AGV dynamic path planning based on improved genetic algorithm and its implementation [J]. Computer Integrated Manufacturing Systems, 2018, 24(6): 1455-1467.
[3] JUANG C F, YEH Y T. Multiobjective evolution of biped robot gaits using advanced continuous ant-colony optimized recurrent neural networks [J]. IEEE Transactions on Cybernetics, 2018, 48(6): 1910-1922.
[4] 许川佩,吕莹,黄喜军,等. 基于粒子群算法的数字微流控芯片在线测试路径优化[J].电子测量与仪器学报,2017,31(8):1192-1199.XU CH P, LV Y, HUANG X J, et al. On-line test route optimization of digital microfluidic chip based on particle swarm optimization[J]. Journal of Electronic Measurement and Instrumentation, 2017, 31(8):1192-1199.
[5] 刘浩然,孙美婷,李雷,等. 基于蚁群节点寻优的贝叶斯网络结构算法研究[J].仪器仪表学报,2017,38(1): 143-150.LIU H R,SUN M T, LI L, et al. Study on Bayesian network structure learning algorithm based on ant colony node order optimization [J].Chinese Journal of Scientific Instrument, 2017, 38(1): 143-150.
[6] DORIGO M, GAMBARDELLA L M. Ant colony system: A cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1):5 3- 66.
[7] 游晓明,刘升,吕金秋. 一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用[J].控制与决策,2017,32(3):552- 556.YOU X M, LIU SH, LV J Q. Ant colony algorithm based on dynamic search strategy and its application on path planning of robot [J]. Control and Decision, 2017, 32(3): 552- 556.
[8] 汪杰君,刘江宽,黄喜军,等. 基于混合遗传蚁群算法的数字微流控芯片测试路径规划[J].电子测量与仪器学报,2017,31(8):1183-1191.WANG J J, LIU J K, HUANG X J, et, al. Test path scheduleing of digital microfluidic biochips based on combined genetic and ant colony algorithm [J]. Journal of Electronic Measurement and Instrumentation, 2017, 31(8): 1183-1191.
[9] 屈鸿,黄利伟,柯星. 动态环境下基于改进蚁群算法的机器人路径规划研究[J].电子科技大学学报,2015,44 (2):260- 265.QU H, HUANG L W, KE X. Research of improved ant colony based robot path planning under dynamic environment [J]. Journal of University of Electronic Science and Technology of China, 2015, 44(2): 260- 265.
[10] 张成,凌有铸,陈孟元. 改进蚁群算法求解移动机器人路径规划[J]. 电子测量与仪器学报, 2016,30(11):1758-1764.ZHANG CH, LING Y ZH, CHEN M Y. Path planning of mobile robot based on an improved ant colony algorithm [J]. Journal of Electronic Measurement and Instrumentation, 2016, 30(11): 30-37.
[11] 王晓燕,杨乐,张宇,等. 基于改进势场蚁群算法的机器人路径规划[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.
[12] SUN Y, DONG W, CHEN Y. An improved routing algorithm based on ant colony optimization in wireless sensor networks [J]. IEEE Communications Letters, 2017, 21(6): 1317-1320.
[13] 梁建刚,刘晓平,王刚,等. 基于改进蚁群算法的自动导引运输车全局路径规划方法研究[J].机电工程,2018,35(4):431- 436.LIANG J G, LIU X P, WANG G,et al. Global path planning for automated guided vehicle based on improved ant colony algorithm [J]. Journal of Mechanical & Electrical Engineering, 2018, 35(4): 431- 436.
[14] 刘建华,杨建国,刘华平,等. 基于势场蚁群算法的移动机器人全局路径规划方法[J].农业机械学报,2015, 46(9):18- 27.LIU J H, YANG J G, LIU H P, et al. Robot global path planning based on ant colony optimization with artificial potential field [J]. Journal of Agricultural Machinery, 2015, 46(9): 18- 27.
[15] 夏小云,周育人. 蚁群优化算法的理论研究进展[J]. 智能系统学报,2016,11(1):27-36.XIA X Y, ZHOU Y R. Advances in theoretical research of ant colony optimization [J]. CAAI Transactions on Intelligent Systems, 2016, 11(1): 27-36.
[16] 李龙澍,喻环. 改进蚁群算法在复杂环境中机器人路径规划上的应用[J].小型微型计算机系统,2017,38(9): 2067- 2071.LI L SH, YU H. Improved ant colony algorithm in complex environments on the robot path planning [J]. Journal of Chinese Computer Systems,2017, 38(9): 2067- 2071.
[17] JIAO Z, MA K, RONG Y, et al. A path planning method using adaptive polymorphic ant colony algorithm for smart wheelchairs [J]. Journal of Computational Science, 2018(25):50- 57.
[18] CAO J. Robot global path planning based on an improved ant colony algorithm [J]. Journal of Computer and Communications, 2016, 4(2): 11.
[19] JABBARPOUR M R, ZARRABI H, JUNG J J, et al. A green ant-based method for path planning of unmanned ground vehicles [J]. IEEE Access, 2017(5): 1820-1832.