基于改进势场蚁群算法的移动机器人最优路径规划
|
摘要
首先,针对传统人工势场算法存在死锁及局部路径欠优等问题,对其进行改进。利用障碍物检测算法识别出有效障碍物和有效路径中间点,通过引力场和边界条件规划出起点到中间点的局部路径,将中间点置为新的起点进行反复迭代,直至起点与目标点重合则规划完成。其次,针对蚁群算法容易陷入局部最优以及收敛速度较慢等问题,对其进行改进。以改进人工势场算法规划出的路径启发蚁群进行路径搜索,从而避免算法早期由于盲目搜索而导致的路径交叉及收敛速度慢等问题,同时以收敛次数构建负反馈通道,使全局信息素和局部信息素的更新速率跟随收敛次数的变化自适应调节,从而保证了算法全程中收敛速度与全局搜索能力的协调与统一。最后,在Matlab中对本文算法、基本蚁群算法以及文献[23]所述算法分别进行仿真实验。结果表明:在相同的环境模型下,本文算法的收敛速度和搜索能力均优于另两种算法;在给定的简单环境模型下进行路径规划时,本文算法的迭代次数为3次,运行时间为0. 892 s,最优路径长度为28. 627 m;在给定的复杂环境模型下进行路径规划时,本文算法的迭代次数为8次,运行时间为3. 376 s,最优路径长度为31. 556 m,所寻路径对环境的覆盖率为73. 63%。
Addressing the problems of deadlock and poor local path in traditional artificial potential field algorithm,some improvement measures were put forward. The obstacle detection algorithm was used to identify one effective obstacle and one intermediate point. Then a local path from starting point to the intermediate point was planed according to the gravitational field and boundary conditions. Setting the intermediate point to a new starting point and repeating this process until each local path was planed one by one. Secondly,aiming at the disadvantage of slow convergence rate and easy to fall into local optimum in basic ant colony algorithm,some improvements were proposed. The result of artificial potential field algorithm was used to build heuristic information of ant colony,so as to avoid the problems of path crossover and slow convergence. At the same time,a negative feedback loop was built to adaptively adjust the renewal speed of global pheromone and local pheromone through the iteration number. Finally,simulation experiment on three different algorithms was conducted. The results showed that under the same environment model,the proposed algorithm had fewer iterations,shorter running time and better global search ability than other two algorithms. In the given simple environment model,the iteration times of the algorithm was 3,the running time was 0. 892 s,and the optimal path length was 28. 627 m. In the given complex environment model,the iteration was 8 times,the running time was 3. 376 s,the optimal path length was 31. 556 m,and the global coverage of paths was 73. 63%.
Addressing the problems of deadlock and poor local path in traditional artificial potential field algorithm,some improvement measures were put forward. The obstacle detection algorithm was used to identify one effective obstacle and one intermediate point. Then a local path from starting point to the intermediate point was planed according to the gravitational field and boundary conditions. Setting the intermediate point to a new starting point and repeating this process until each local path was planed one by one. Secondly,aiming at the disadvantage of slow convergence rate and easy to fall into local optimum in basic ant colony algorithm,some improvements were proposed. The result of artificial potential field algorithm was used to build heuristic information of ant colony,so as to avoid the problems of path crossover and slow convergence. At the same time,a negative feedback loop was built to adaptively adjust the renewal speed of global pheromone and local pheromone through the iteration number. Finally,simulation experiment on three different algorithms was conducted. The results showed that under the same environment model,the proposed algorithm had fewer iterations,shorter running time and better global search ability than other two algorithms. In the given simple environment model,the iteration times of the algorithm was 3,the running time was 0. 892 s,and the optimal path length was 28. 627 m. In the given complex environment model,the iteration was 8 times,the running time was 3. 376 s,the optimal path length was 31. 556 m,and the global coverage of paths was 73. 63%.
引文
[1]FAKOOR M,KOSARI A,JAFARZADEH M.Humanoid robot path planning with fuzzy markov decision processes[J].Journal of Applied Research&Technology,2016,14(5):300-310.
[2]KHATIB O.Real-time obstacle avoidance for manipulators and mobile robots[J].The International Journal of Robotics Research,1986,5(1):90-98.
[3]BARRAQUAND J,LANGLOIS B,LATOMBE J.Numerical potential field techniques for robot path planning[J].IEEETransactions on Systems,Man and Cybernetics,1992,22(2):224-241.
[4]GIUSEPPE C,MARCELLO F,GIACOMO L.A network flow based heuristic approach for optimising AGV[J].Journal of Intelligent Manufacturing,2013,24(2):405-419.
[5]王殿君.基于改进A*算法的室内移动机器人路径规划[J].清华大学学报(自然科学版),2012,52(8):1085-1089.WANG Dianjun.Indoor mobile-robot path planning based on an improved A*algorithm[J].Journal of Tsinghua University(Science and Technology),2012,52(8):1085-1089.(in Chinese)
[6]KENNEDY J,EBERHART R C.Particle swarm optimization[C]∥IEEE International Conference on Neural Networks,1995:1942-1948.
[7]ATYABI A,PHON-AMNUAISUK S,HO C K.Navigating a robotic swarm in an uncharted 2D landscape[J].Applied Soft Computing,2010,10(1):149-169.
[8]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):53-66.
[9]史恩秀,陈敏敏,李俊,等.基于蚁群算法的移动机器人全局路径规划方法研究[J/OL].农业机械学报,2014,45(6):53-57.SHI Enxiu,CHEN Minmin,LI Jun,et al.Research on method of global path-planning for mobile robot based on ant-colony algorithm[J/OL].Transactions of the Chinese Society for Agricultural Machinery,2014,45(6):53-57.http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?file_no=20140609&flag=1.DOI:10.6041/j.issn.1000-1298.2014.06.009.(in Chinese)
[10]COBANO J A,CONDE R,ALEJO D,et al.Path planning based on genetic algorithms and the Monte-Carlo method to avoid aerial vehicle collisions under uncertainties[C]∥2011 International Conference on Robotics and Automation,2011:4429-4434.
[11]朱大奇,孙兵,李利.基于生物启发模型的AUV三维自主路径规划与安全避障算法[J].控制与决策,2015,30(5):798-806.ZHU Daqi,SUN Bing,LI Li.Algorithm for AUV’s 3-D path planning and safe obstacle avoidance based on biological inspired model[J].Control and Decision,2015,30(5):798-806.(in Chinese)
[12]徐翔,梁瑞仕,杨会志.基于改进遗传算法的智能体路径规划仿真[J].计算机仿真,2014,31(6):357-361.XU Xiang,LIANG Ruishi,YANG Huizhi.Path planning for agent based on improved genetic algorithm[J].Computer Simulation,2014,31(6):357-361.(in Chinese)
[13]王耀南,潘琪,陈彦杰.改进型生物激励神经网络的路径规划方法[J].控制工程,2018,25(4):541-548.WANG Yaonan,PAN Qi,CHEN Yanjie.Path planning method based on improved biologically inspired neural network[J].Control Engineering of China,2018,25(4):541-548.(in Chinese)
[14]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,2017,30(99):1-13.
[15]NIE Z,YANG X,GAO S,et al.Research on autonomous moving robot path planning based on improved particle swarm optimization[C]∥2016 IEEE Congresson Evolutionary Computation(CEC).Vancouver,2016:2532-2536.
[16]王辉,朱龙彪,朱天成,等.基于粒子群遗传算法的泊车系统路径规划研究[J].工程设计学报,2016,23(2):195-200.WANG Hui,ZHU Longbiao,ZHU Tiancheng,et al.Research on path planning of parking system based on PSO-genetic hybrid algorithm[J].Chinese Journal of Engineering Design,2016,23(2):195-200.(in Chinese)
[17]成伟明,唐振民,赵春霞,等.基于神经网络和PSO的机器人路径规划研究[J].系统仿真学报,2008,20(3):608-611.CHENG Weiming,TANG Zhenmin,ZHAO Chunxia,et al.Path planning of robot based on neural network and PSO[J].Journal of System Simulation,2008,20(3):608-611.(in Chinese)
[18]刘建华,杨建国,刘华平.基于势场蚁群算法的移动机器人全局路径规划方法[J/OL].农业机械学报,2015,46(9):18-27.LIU Jianhua,YANG Jianguo,LIU Huaping.Robot global path planning based on ant colony optimization with artificial potential field[J/OL].Transactions of the Chinese Society for Agricultural Machinery,2015,46(9):18-27.http:∥www.jcsam.org/jcsam/ch/reader/view_abstract.aspx?file_no=20150903&flag=1.DOI:10.6041/j.issn.1000-1298.2015.09.003.(in Chinese)
[19]郑佳春,吴建华,马勇,等.混合模拟退火与粒子群优化算法的无人艇路径规划[J].中国海洋大学学报(自然科学版),2016,46(9):116-122.ZHENG Jiachun,WU Jianhua,MA Yong,et al.A hybrid optimization algorithm of simulated annealing and particle swarm for unmanned surface vessel path planning[J].Periodical of Ocean University of China(Science and Technology),2016,46(9):116-122.(in Chinese)
[20]潘昕,吴旭升,侯新国,等.基于遗传蚂蚁混合算法的AUV全局路径规划[J].华中科技大学学报(自然科学版),2017,45(5):45-49.PAN Xin,WU Xusheng,HOU Xinguo,et al.Global path planning based on genetic-ant hybrid algorithm for AUV[J].Journal of Huazhong University of Science and Technology(Natural Science Edition),2017,45(5):45-49.(in Chinese)
[21]罗德林,吴顺祥.基于势场蚁群算法的机器人路径规划[J].系统工程与电子技术,2010,32(6):1277-1280.LUO Delin,WU Shunxiang.Ant colony optimization with potential field heuristic for robot path planning[J].Systems Engineering and Electronics,2010,32(6):1277-1280.(in Chinese)
[22]曾明如,徐小勇,刘亮,等.改进的势场蚁群算法的移动机器人路径规划[J].计算机工程与应用,2015,51(22):33-37.ZENG Mingru,XU Xiaoyong,LIU Liang,et al.Improved ant colony optimization with potential field heuristic for robot path planning[J].Computer Engineering and Applications,2015,51(22):33-37.(in Chinese)
[23]王晓燕,杨乐,张宇,等.基于改进势场蚁群算法的机器人路径规划[J].控制与决策,2017,33(10):1775-1781.WANG Xiaoyan,YANG Le,ZHANG Yu,et al.Robot path planning based on improved ant colony algorithm with potential field heuristic[J].Control and Decision,2017,33(10):1775-1781.(in Chinese)
[24]徐雪松,杨胜杰,陈荣元.复杂环境移动群机器人最优路径规划方法[J].电子测量与仪器学报,2016,30(2):274-282.XU Xuesong,YANG Shengjie,CHEN Rongyuan.Dynamic differential evolution algorithm for swarm robots search path planning[J].Journal of Electronic Measurement and Instrumentation,2016,30(2):274-282.(in Chinese)
[25]屈鸿,黄利伟,柯星.动态环境下基于改进蚁群算法的机器人路径规划研究[J].电子科技大学学报,2015,44(2):260-265.QU Hong,HUANG Liwei,KE Xing.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.(in Chinese)
[26]樊征,曹其新,杨扬,等.面向移动机器人的拓扑地图自动生成[J].华中科技大学学报(自然科学版),2008,36(增刊1):163-166.FAN Zheng,CAO Qixin,YANG Yang,et al.Automatic generation of topological map for mobile robot[J].Journal of Huazhong University of Science and Technology(Science and Technology),2008,36(Supp.1):163-166.(in Chinese)
[27]KHATIB O.Real-time obstacle avoidance for manipulators and mobile robots[J].Int J Robotics Research,1986,5(1):90-98.
[28]张建英,刘暾.基于人工势场法的移动机器人最优路径规划[J].航空学报,2007,28(增刊1):183-188.ZHANG Jianying,LIU Tun.Optimized path planning of mobile robot based on artificial potential field[J].Chinese Journal of Aeronautica,2007,28(Supp.1):183-188.(in Chinese)
[29]HWANG Y K,AHUJA N.A potential field approach to path planning[J].IEEE Transaction on Robotics and Automation,1992,8(1):23-32.
[30]孟偲,王田苗.一种移动机器人全局最优路径规划算法[J].机器人,2008,27(3):217-222.MENG Si,WANG Tianmiao.A global optimal path planning algorithm for mobile robot[J].Robot,2008,27(3):217-222.(in Chinese)
[31]DORIGO M,GAMBARDELLA L M.A cooperative learning approach to the traveling salesman problem[J].IEEETransactions on Energy Conversion,Man,and Cybernetics,1996,26(1):29-41.
[32]李士勇.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社,2003.
[33]ERIN B,ABIYEV R,IBRAHIM D.Teaching robot navigation in the presence of obstacles using a computer simulation program[J].Procedia Social and Behavioral Sciences,2010,2(2):565-571.
[2]KHATIB O.Real-time obstacle avoidance for manipulators and mobile robots[J].The International Journal of Robotics Research,1986,5(1):90-98.
[3]BARRAQUAND J,LANGLOIS B,LATOMBE J.Numerical potential field techniques for robot path planning[J].IEEETransactions on Systems,Man and Cybernetics,1992,22(2):224-241.
[4]GIUSEPPE C,MARCELLO F,GIACOMO L.A network flow based heuristic approach for optimising AGV[J].Journal of Intelligent Manufacturing,2013,24(2):405-419.
[5]王殿君.基于改进A*算法的室内移动机器人路径规划[J].清华大学学报(自然科学版),2012,52(8):1085-1089.WANG Dianjun.Indoor mobile-robot path planning based on an improved A*algorithm[J].Journal of Tsinghua University(Science and Technology),2012,52(8):1085-1089.(in Chinese)
[6]KENNEDY J,EBERHART R C.Particle swarm optimization[C]∥IEEE International Conference on Neural Networks,1995:1942-1948.
[7]ATYABI A,PHON-AMNUAISUK S,HO C K.Navigating a robotic swarm in an uncharted 2D landscape[J].Applied Soft Computing,2010,10(1):149-169.
[8]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):53-66.
[9]史恩秀,陈敏敏,李俊,等.基于蚁群算法的移动机器人全局路径规划方法研究[J/OL].农业机械学报,2014,45(6):53-57.SHI Enxiu,CHEN Minmin,LI Jun,et al.Research on method of global path-planning for mobile robot based on ant-colony algorithm[J/OL].Transactions of the Chinese Society for Agricultural Machinery,2014,45(6):53-57.http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?file_no=20140609&flag=1.DOI:10.6041/j.issn.1000-1298.2014.06.009.(in Chinese)
[10]COBANO J A,CONDE R,ALEJO D,et al.Path planning based on genetic algorithms and the Monte-Carlo method to avoid aerial vehicle collisions under uncertainties[C]∥2011 International Conference on Robotics and Automation,2011:4429-4434.
[11]朱大奇,孙兵,李利.基于生物启发模型的AUV三维自主路径规划与安全避障算法[J].控制与决策,2015,30(5):798-806.ZHU Daqi,SUN Bing,LI Li.Algorithm for AUV’s 3-D path planning and safe obstacle avoidance based on biological inspired model[J].Control and Decision,2015,30(5):798-806.(in Chinese)
[12]徐翔,梁瑞仕,杨会志.基于改进遗传算法的智能体路径规划仿真[J].计算机仿真,2014,31(6):357-361.XU Xiang,LIANG Ruishi,YANG Huizhi.Path planning for agent based on improved genetic algorithm[J].Computer Simulation,2014,31(6):357-361.(in Chinese)
[13]王耀南,潘琪,陈彦杰.改进型生物激励神经网络的路径规划方法[J].控制工程,2018,25(4):541-548.WANG Yaonan,PAN Qi,CHEN Yanjie.Path planning method based on improved biologically inspired neural network[J].Control Engineering of China,2018,25(4):541-548.(in Chinese)
[14]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,2017,30(99):1-13.
[15]NIE Z,YANG X,GAO S,et al.Research on autonomous moving robot path planning based on improved particle swarm optimization[C]∥2016 IEEE Congresson Evolutionary Computation(CEC).Vancouver,2016:2532-2536.
[16]王辉,朱龙彪,朱天成,等.基于粒子群遗传算法的泊车系统路径规划研究[J].工程设计学报,2016,23(2):195-200.WANG Hui,ZHU Longbiao,ZHU Tiancheng,et al.Research on path planning of parking system based on PSO-genetic hybrid algorithm[J].Chinese Journal of Engineering Design,2016,23(2):195-200.(in Chinese)
[17]成伟明,唐振民,赵春霞,等.基于神经网络和PSO的机器人路径规划研究[J].系统仿真学报,2008,20(3):608-611.CHENG Weiming,TANG Zhenmin,ZHAO Chunxia,et al.Path planning of robot based on neural network and PSO[J].Journal of System Simulation,2008,20(3):608-611.(in Chinese)
[18]刘建华,杨建国,刘华平.基于势场蚁群算法的移动机器人全局路径规划方法[J/OL].农业机械学报,2015,46(9):18-27.LIU Jianhua,YANG Jianguo,LIU Huaping.Robot global path planning based on ant colony optimization with artificial potential field[J/OL].Transactions of the Chinese Society for Agricultural Machinery,2015,46(9):18-27.http:∥www.jcsam.org/jcsam/ch/reader/view_abstract.aspx?file_no=20150903&flag=1.DOI:10.6041/j.issn.1000-1298.2015.09.003.(in Chinese)
[19]郑佳春,吴建华,马勇,等.混合模拟退火与粒子群优化算法的无人艇路径规划[J].中国海洋大学学报(自然科学版),2016,46(9):116-122.ZHENG Jiachun,WU Jianhua,MA Yong,et al.A hybrid optimization algorithm of simulated annealing and particle swarm for unmanned surface vessel path planning[J].Periodical of Ocean University of China(Science and Technology),2016,46(9):116-122.(in Chinese)
[20]潘昕,吴旭升,侯新国,等.基于遗传蚂蚁混合算法的AUV全局路径规划[J].华中科技大学学报(自然科学版),2017,45(5):45-49.PAN Xin,WU Xusheng,HOU Xinguo,et al.Global path planning based on genetic-ant hybrid algorithm for AUV[J].Journal of Huazhong University of Science and Technology(Natural Science Edition),2017,45(5):45-49.(in Chinese)
[21]罗德林,吴顺祥.基于势场蚁群算法的机器人路径规划[J].系统工程与电子技术,2010,32(6):1277-1280.LUO Delin,WU Shunxiang.Ant colony optimization with potential field heuristic for robot path planning[J].Systems Engineering and Electronics,2010,32(6):1277-1280.(in Chinese)
[22]曾明如,徐小勇,刘亮,等.改进的势场蚁群算法的移动机器人路径规划[J].计算机工程与应用,2015,51(22):33-37.ZENG Mingru,XU Xiaoyong,LIU Liang,et al.Improved ant colony optimization with potential field heuristic for robot path planning[J].Computer Engineering and Applications,2015,51(22):33-37.(in Chinese)
[23]王晓燕,杨乐,张宇,等.基于改进势场蚁群算法的机器人路径规划[J].控制与决策,2017,33(10):1775-1781.WANG Xiaoyan,YANG Le,ZHANG Yu,et al.Robot path planning based on improved ant colony algorithm with potential field heuristic[J].Control and Decision,2017,33(10):1775-1781.(in Chinese)
[24]徐雪松,杨胜杰,陈荣元.复杂环境移动群机器人最优路径规划方法[J].电子测量与仪器学报,2016,30(2):274-282.XU Xuesong,YANG Shengjie,CHEN Rongyuan.Dynamic differential evolution algorithm for swarm robots search path planning[J].Journal of Electronic Measurement and Instrumentation,2016,30(2):274-282.(in Chinese)
[25]屈鸿,黄利伟,柯星.动态环境下基于改进蚁群算法的机器人路径规划研究[J].电子科技大学学报,2015,44(2):260-265.QU Hong,HUANG Liwei,KE Xing.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.(in Chinese)
[26]樊征,曹其新,杨扬,等.面向移动机器人的拓扑地图自动生成[J].华中科技大学学报(自然科学版),2008,36(增刊1):163-166.FAN Zheng,CAO Qixin,YANG Yang,et al.Automatic generation of topological map for mobile robot[J].Journal of Huazhong University of Science and Technology(Science and Technology),2008,36(Supp.1):163-166.(in Chinese)
[27]KHATIB O.Real-time obstacle avoidance for manipulators and mobile robots[J].Int J Robotics Research,1986,5(1):90-98.
[28]张建英,刘暾.基于人工势场法的移动机器人最优路径规划[J].航空学报,2007,28(增刊1):183-188.ZHANG Jianying,LIU Tun.Optimized path planning of mobile robot based on artificial potential field[J].Chinese Journal of Aeronautica,2007,28(Supp.1):183-188.(in Chinese)
[29]HWANG Y K,AHUJA N.A potential field approach to path planning[J].IEEE Transaction on Robotics and Automation,1992,8(1):23-32.
[30]孟偲,王田苗.一种移动机器人全局最优路径规划算法[J].机器人,2008,27(3):217-222.MENG Si,WANG Tianmiao.A global optimal path planning algorithm for mobile robot[J].Robot,2008,27(3):217-222.(in Chinese)
[31]DORIGO M,GAMBARDELLA L M.A cooperative learning approach to the traveling salesman problem[J].IEEETransactions on Energy Conversion,Man,and Cybernetics,1996,26(1):29-41.
[32]李士勇.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社,2003.
[33]ERIN B,ABIYEV R,IBRAHIM D.Teaching robot navigation in the presence of obstacles using a computer simulation program[J].Procedia Social and Behavioral Sciences,2010,2(2):565-571.