移动机器人路径规划综述
|
摘要
移动机器人是目前科学技术发展最活跃的领域之一,在工业、农业、医疗等行业广泛应用,还在城市安全、国防和空间探测领域得到更广的应用;要实现机器人在未知环境下自主作业,具备实时、自主、识别高风险区域和风险管理的能力,路径规划是一个重要环节,规划水平的高低,在一定程度上标志着机器人的智能水平,因此研究机器人路径规划对提高机器人的智能化水平、加快工程化应用具有重要的意义;文章重点分别从全局路径规划和局部路径规划角度对机器人路径规划的研究方法进行了分析与总结,同时分析研究了基于仿生学的智能算法的遗传算法、蚁群算法、粒子群算法,最后展望了移动机器人的未来发展趋势。
Mobile robot is one of the most active areas of scientific and technological development.It is widely used not only in industry,agriculture and medical care,but also in urban security,national defense and space exploration.To realize the autonomous operation of intelligent mobile robots in an unknown environment,with real-time,autonomous,identification of high-risk areas and risk management capabilities,robot path planning is an important link,the level of path planning indicates the level of intelligence of robots to a certain extent.Therefore,researching robot path planning technology is of great significance to improve the intelligence level of robots and accelerate the process of engineering application.It is summarized and analyzed that the research methods of robot path planning from the perspective of global path planning and local path planning in the paper.At the same time,path planning techniques based on bionics genetic algorithm,ant colony algorithm and particle swarm algorithm are introduced.Finally,the future development trend of mobile robot path planning is forecasted.
Mobile robot is one of the most active areas of scientific and technological development.It is widely used not only in industry,agriculture and medical care,but also in urban security,national defense and space exploration.To realize the autonomous operation of intelligent mobile robots in an unknown environment,with real-time,autonomous,identification of high-risk areas and risk management capabilities,robot path planning is an important link,the level of path planning indicates the level of intelligence of robots to a certain extent.Therefore,researching robot path planning technology is of great significance to improve the intelligence level of robots and accelerate the process of engineering application.It is summarized and analyzed that the research methods of robot path planning from the perspective of global path planning and local path planning in the paper.At the same time,path planning techniques based on bionics genetic algorithm,ant colony algorithm and particle swarm algorithm are introduced.Finally,the future development trend of mobile robot path planning is forecasted.
引文
[1]陆新华,张桂林.室内服务机器人导航方法研究[J].机器人,2003,25(1):80-87.
[2]李喜刚,蔡远利.基于改进蚁群算法的无人机路径规划[J].飞行力学,2017,35(1):52-56.
[3]王友钊,彭宇翔,潘芬兰.基于贪心算法和遗传算法的仓储车辆调度算法[J].传感器与微系统,2012,31(10):125-128.
[4]张禹,徐红丽,韦茵.基于数字海图的自主水下机器人路径规划研究[J].机器人,2006,28(3):321-325.
[5]曲道奎,杜振军,徐殿国,等.移动机器人路径规划方法研究[J].机器人,2008,30(2):97-101,106.
[6]Jeddisaravi K,Alitappeh R J,Pimenta L C A.Multiobjective approach for robot motion planning in search tasks[J].Applied Intelligence,2016,45(2):305-321.
[7]Eele A J,Richards A.Path-Planning with Avoidance Using Nonlinear Branch-and-Bound Optimization[J].Journal of Guidance Control&Dynamics,2015,32(2):384-394.
[8]马仁利,关正西.路径规划技术的现状与发展综述[J].现代机械,2008(3):22-25.
[9]张颖,吴成东,原宝龙.机器人路径规划方法综述[J].控制工程,2003,10(s):152-155.
[10]魏宁,刘一松.基于栅格模型的移动机器人全局路径规划研究[J].微计算机信息,2008,24(4):229-231.
[11]欧阳鑫玉,杨曙光.基于势场栅格法的移动机器人避障路径规划[J].控制工程,2014,21(1):134-137.
[12]Elfes A.Sonar-based real world mapping and navigation[J].IEEE Journal of Robotic and Automation,1987,3(3):249-265.
[13]郑秀敏,吴大鹏,刘相术.基于栅格法-模拟退火法的机器人路径规划[J].微计算机信息,2007,23(2):247-248,279.
[14]于红斌,李孝安.基于栅格法的机器人快速路径规划[J].微电子学与计算机,2005,22(6):98-100.
[15]朱磊,樊继壮,赵杰.基于栅格法的矿难搜索机器人全局路径规划与局部避障[J].中南大学学报(自然科学版),2011,42(11):3421-3428.
[16]王曙光,唐浩漾.基于实时栅格法的多机器人协作建图[J].机床与液压,2014,42(3):24-26.
[17]Korf R E.Depth-first iterative-deepening:An optimal admissible tree search[J].Artificial Intelligence,1985,27(1):97-109.
[18]Korf R E.Real-time heuristic search[J].Artificial Intelligence,1990,42(2/3):189-211.
[19]Hart P E,Nilsson N J,Raphael B.A formal basis for the heuristic determination of Minimum cost paths[J].IEEE Transactions on Systems Science and Cybernetics,1968,4(2):100-107.
[20]Stentz A.Optimal and efficient path planning for partiallyknown environments[A].IEEE International Conference on Robotics and Automation[C].Piscataway,USA;IEEE,2002:3310-3317.
[21]顾新艳,金世俊.基于A*算法的移动机器人路径规划[J].科技信息,2007,21(4):36-37,79.
[22]Klein Dan,Manning Christopher D.A*parsing:fast exact Viterbi parse selection[J].Proc.NAACL-HLT.
[23]Kagan E,Ben-Gal I.A Group-Testing Algorithm with Online Informational Learning[J].IIE Transactions,46(2):164-184.
[24]王红卫,马勇,谢勇,等.基于平滑A*算法的移动机器人路径规划[J].同济大学学报(自然科学版),2010,38(11):1647-1650.
[25]王殿君.基于改进A*算法的室内移动机器人路径规划[J].清华大学学报(自然科学版),2012,52(8):1085-1089.
[26]赵晓,王铮,黄程侃,等.基于改进A*算法的移动机器人路径规划[J].机器人,2018,40(6):1-8.
[27]王小红,叶涛.基于改进A*算法机器人路径规划研究[J].计算机测量与控制,2018,26(7):282-286.
[28]Brunato M,Battiti R.Statistical learning theory for location finger-printing in wireless LANs[J].Computer Networks,2005,47(6):825-845.
[29]Danner T,Kavraki L E.Randomized planning for short inspection paths[A].Proceedings of the IEEE International Conference on Robotics and Automation[C].San Francisco:2000,971-976.
[30]Khatib O.Real-time obstacle avoidance for manipulators and mobile robots[J].The International Journal of Robotics Research,1986,5(1):90-98.
[31]庄晓东,孟庆春,高云,等.复杂环境中基于人工势场优化算法的最优路径规划[J].机器人,2003,25(6):531-535.
[32]梁珂,陈雄.移动机器人在未知狭窄环境中的路径规划[J].机器人,2005,27(1):52-56,62.
[33]Borenstein J.The vector field histogram-fast obstacle avoidance for mobile robots[J].IEEE Transactions Robotics&Automation,2002,7(3):278-288.
[34]Ulrich I,Borenstein J.VFH+:Reliable Obstacle Avoidance for Fast Mobile Robots[A].Proceedings of the 1998IEEEInternational Conference on Robotics and Automation[C].1998,5:1572-1577.
[35]Ulrich I,Borenstein J.VFH*:Local Obstacle Avoidance with Look-Ahead Verification[A].Proceedings of the IEEEInternational Conference on Robotics and Automation[C].2000:2505-2511.
[36]章苏书,吴敏,曹卫华.一种局部动态环境下的避障算法[J].计算技术与自动化,2003,22(1):12-16.
[37]Ge S S,Cui Y J.New potential functions for mobile robot path planning[J].IEEE Transactions on robotics and automation,2000,10(5):615-620.
[38]唐志荣,冀杰,吴明阳.基于改机人工势场法的车辆路径规划与跟踪[J].西南大学学报(自然科学版),40(6):174-182.
[39]Simmons R.The Curvature-Velocity Method for Local Obstacle Avoidance[A].IEEE International Conference on Robotics and Automation[C].1996:3375-3382.
[40]Fox D,Burgard W,Thrun S,et al.The dynamic window approach to collision avoidance[J].IEEE Robotics&Automation Magazine,1997,4(1):23-33.
[41]Seder M,Petrovic I.Dynamic window based approach to mobile robot motion control in the presence of moving obstacles[A].IEEE International Conference on Robotics and Automation[C].IEEE,2007:1986-1991.
[42]Saranrittichai P,Niparnan N.Robust local obstacle avoidance for mobile robot based on dynamic Window approach[A].Proceeding of 10th International Conference on Electrical Engineering/Electronics,Computer,Telecommunication and Information Technology(EC-TI-CON)[C].2013:1-4.
[43]Choi B,Kim B,Kim E.A modified dynamic Window approach in crowded indoor environment for intelligent transport robot[A].Proceeding of 12th International Conference on Control,Automation and Systems[C].2012:1007-1009.
[44]Saranrittichai P,Niparnan N,Sudsang A.Robust local obstacle avoidance for mobile robot based on Dynamic Window approach[A].2013 10th International Conference on Electrical Engineering/Electronics,Computer,Telecommunications and Information Technology[C].2013.
[45]Pablo I B,Fernando D R,Diaz S V,et al.The shared control dynamic Window approach for non-holonomic semi-autonomous robots[A].2014,41st International Symposium on Robotics[C].2014.
[46]程传奇,郝向阳,李建胜,等.融合改进A*算法和动态窗口法的全局动态路径规划[J].西安交通大学学报,2017,51(11):137-142.
[47]Tian L,Collins C.An effective robot trajectory planning method using agenetic algorithm[J].Mechatronics,2004,14(5):455-470.
[48]朱大奇,颜明重.移动机器人路径规划技术综述[J].控制与决策,2010,25(7):961-967.
[49]黄云清,梁靓.机器人导航系统中的路径规划算法[J].微计算机信息,2006,22(7):259-261.
[50]李庆中,顾伟康.基于遗传算法的移动机器人动态避障路径规划算法[J].模式识别与人工智能,2002,15(2):161-166.
[51]Roberge V,Tarbouchi M,Labonte G.Comparison of parallel genetic algorithm and particle swarm optimization for realtime UAV path planning[J].IEEE Transactions on Industrial Informatics,2013,2(1):132-141.
[52]陈刚,沈成林.复杂环境下路径规划问题的遗传路径规划方法[J].机器人,2001,23(1):40-50.
[53]陈志军,曾蒸.基于模糊神经网络和遗传算法的机器人三维路径规划[J].重庆师范大学学报(自然科学版),2018,35(1):93-99.
[54]Colorni A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies[A].Proc of the ECAL-91[C].Paris,1991:134-142.
[55]Dorigo M,Maniezzo V,Colorni A.The ant system:Optimization by a colony of cooperating agents[J].IEEE Trans on Systems,Man&Cybernetics-B,1996,26(2):29-41.
[56]Dorigo M,Gambardella L M.Ant colony system:A cooperative learning approach to the travelling sales-man problem[J].IEEE Trans on Evolutionary Computation,1997,1(1):53-66.
[57]Taylor B,Choi A.Fuzzy ant colony algorithm for terrain following optimization[A].Procceedings-IEEE International Conference on Systems,Man and Cybernetics[C].New York,USA,2014:3834-3839.
[58]Riahi V,Kazemi M.A new hybrid ant colony algorithm for scheduling of nowait flowshop[J].2018,18(1):55-74.
[59]王辉,王景良,朱龙彪,等.基于改进蚁群算法的泊车系统路径规划[J].控制工程,2018,25(2):253-258.
[60]李龙澍,喻环.改进蚁群算法在复杂环境中机器人路径规划上的应用[J].小型微型计算机系统,2017,9:2067-2071.
[61]彭凡彬,杨俊杰,叶波.改进蚁群算法的变电站群机器人路径规划研究[J].仪表技术,2018,(3):9-13.
[62]Kennedy J,Eberhart R C.Particle swarm optimization[A].Proceedings of the IEEE International Conference on Neural Networks[C].Piscataway,New Jersey:IEEE Service Center,1995,4:1942-1948.
[63]Eberhart R C,Shi Y.Particle swarm optimization:developments applications anf resources[A].Proceedings of the Congress on Evolutionary Computation 2001[C].Piscataway,New Jersey:IEEE Press,2001:81-86.
[64]Shi Y.Krohling R A.Co-evolutionary particle swarm optimization to solve min-max problems[A].Proc of the IEEECong on Evolutionary Computation[C].Honolulu,2002:1682-1687.
[65]孙波,陈卫东,席裕庚.基于粒子群优化算法的移动机器人全局路径规划[J].控制与决策,2005,20(9):1052-1055,1060.
[66]秦元庆,孙德宝,李宁,等.基于粒子群算法的移动机器人路径规划[J].机器人,2004,26(3):222-225.
[67]Delice Y,Aydogan E K,Ozcan U,et al.A modified particle swarm optimization algorithm to mixed-model two-sided assembly line balancing[J].2017,28(1):23-36.
[68]翁理国,纪壮壮,夏旻,等.基于改进多目标粒子群算法的机器人路径规划[J].系统仿真学报,2014,26(12):2892-2898.
[69]王学武,严益鑫,顾幸生.基于莱维飞行粒子群算法的焊接机器人路径规划[J].控制与决策,2017,32(2):373-377.
[2]李喜刚,蔡远利.基于改进蚁群算法的无人机路径规划[J].飞行力学,2017,35(1):52-56.
[3]王友钊,彭宇翔,潘芬兰.基于贪心算法和遗传算法的仓储车辆调度算法[J].传感器与微系统,2012,31(10):125-128.
[4]张禹,徐红丽,韦茵.基于数字海图的自主水下机器人路径规划研究[J].机器人,2006,28(3):321-325.
[5]曲道奎,杜振军,徐殿国,等.移动机器人路径规划方法研究[J].机器人,2008,30(2):97-101,106.
[6]Jeddisaravi K,Alitappeh R J,Pimenta L C A.Multiobjective approach for robot motion planning in search tasks[J].Applied Intelligence,2016,45(2):305-321.
[7]Eele A J,Richards A.Path-Planning with Avoidance Using Nonlinear Branch-and-Bound Optimization[J].Journal of Guidance Control&Dynamics,2015,32(2):384-394.
[8]马仁利,关正西.路径规划技术的现状与发展综述[J].现代机械,2008(3):22-25.
[9]张颖,吴成东,原宝龙.机器人路径规划方法综述[J].控制工程,2003,10(s):152-155.
[10]魏宁,刘一松.基于栅格模型的移动机器人全局路径规划研究[J].微计算机信息,2008,24(4):229-231.
[11]欧阳鑫玉,杨曙光.基于势场栅格法的移动机器人避障路径规划[J].控制工程,2014,21(1):134-137.
[12]Elfes A.Sonar-based real world mapping and navigation[J].IEEE Journal of Robotic and Automation,1987,3(3):249-265.
[13]郑秀敏,吴大鹏,刘相术.基于栅格法-模拟退火法的机器人路径规划[J].微计算机信息,2007,23(2):247-248,279.
[14]于红斌,李孝安.基于栅格法的机器人快速路径规划[J].微电子学与计算机,2005,22(6):98-100.
[15]朱磊,樊继壮,赵杰.基于栅格法的矿难搜索机器人全局路径规划与局部避障[J].中南大学学报(自然科学版),2011,42(11):3421-3428.
[16]王曙光,唐浩漾.基于实时栅格法的多机器人协作建图[J].机床与液压,2014,42(3):24-26.
[17]Korf R E.Depth-first iterative-deepening:An optimal admissible tree search[J].Artificial Intelligence,1985,27(1):97-109.
[18]Korf R E.Real-time heuristic search[J].Artificial Intelligence,1990,42(2/3):189-211.
[19]Hart P E,Nilsson N J,Raphael B.A formal basis for the heuristic determination of Minimum cost paths[J].IEEE Transactions on Systems Science and Cybernetics,1968,4(2):100-107.
[20]Stentz A.Optimal and efficient path planning for partiallyknown environments[A].IEEE International Conference on Robotics and Automation[C].Piscataway,USA;IEEE,2002:3310-3317.
[21]顾新艳,金世俊.基于A*算法的移动机器人路径规划[J].科技信息,2007,21(4):36-37,79.
[22]Klein Dan,Manning Christopher D.A*parsing:fast exact Viterbi parse selection[J].Proc.NAACL-HLT.
[23]Kagan E,Ben-Gal I.A Group-Testing Algorithm with Online Informational Learning[J].IIE Transactions,46(2):164-184.
[24]王红卫,马勇,谢勇,等.基于平滑A*算法的移动机器人路径规划[J].同济大学学报(自然科学版),2010,38(11):1647-1650.
[25]王殿君.基于改进A*算法的室内移动机器人路径规划[J].清华大学学报(自然科学版),2012,52(8):1085-1089.
[26]赵晓,王铮,黄程侃,等.基于改进A*算法的移动机器人路径规划[J].机器人,2018,40(6):1-8.
[27]王小红,叶涛.基于改进A*算法机器人路径规划研究[J].计算机测量与控制,2018,26(7):282-286.
[28]Brunato M,Battiti R.Statistical learning theory for location finger-printing in wireless LANs[J].Computer Networks,2005,47(6):825-845.
[29]Danner T,Kavraki L E.Randomized planning for short inspection paths[A].Proceedings of the IEEE International Conference on Robotics and Automation[C].San Francisco:2000,971-976.
[30]Khatib O.Real-time obstacle avoidance for manipulators and mobile robots[J].The International Journal of Robotics Research,1986,5(1):90-98.
[31]庄晓东,孟庆春,高云,等.复杂环境中基于人工势场优化算法的最优路径规划[J].机器人,2003,25(6):531-535.
[32]梁珂,陈雄.移动机器人在未知狭窄环境中的路径规划[J].机器人,2005,27(1):52-56,62.
[33]Borenstein J.The vector field histogram-fast obstacle avoidance for mobile robots[J].IEEE Transactions Robotics&Automation,2002,7(3):278-288.
[34]Ulrich I,Borenstein J.VFH+:Reliable Obstacle Avoidance for Fast Mobile Robots[A].Proceedings of the 1998IEEEInternational Conference on Robotics and Automation[C].1998,5:1572-1577.
[35]Ulrich I,Borenstein J.VFH*:Local Obstacle Avoidance with Look-Ahead Verification[A].Proceedings of the IEEEInternational Conference on Robotics and Automation[C].2000:2505-2511.
[36]章苏书,吴敏,曹卫华.一种局部动态环境下的避障算法[J].计算技术与自动化,2003,22(1):12-16.
[37]Ge S S,Cui Y J.New potential functions for mobile robot path planning[J].IEEE Transactions on robotics and automation,2000,10(5):615-620.
[38]唐志荣,冀杰,吴明阳.基于改机人工势场法的车辆路径规划与跟踪[J].西南大学学报(自然科学版),40(6):174-182.
[39]Simmons R.The Curvature-Velocity Method for Local Obstacle Avoidance[A].IEEE International Conference on Robotics and Automation[C].1996:3375-3382.
[40]Fox D,Burgard W,Thrun S,et al.The dynamic window approach to collision avoidance[J].IEEE Robotics&Automation Magazine,1997,4(1):23-33.
[41]Seder M,Petrovic I.Dynamic window based approach to mobile robot motion control in the presence of moving obstacles[A].IEEE International Conference on Robotics and Automation[C].IEEE,2007:1986-1991.
[42]Saranrittichai P,Niparnan N.Robust local obstacle avoidance for mobile robot based on dynamic Window approach[A].Proceeding of 10th International Conference on Electrical Engineering/Electronics,Computer,Telecommunication and Information Technology(EC-TI-CON)[C].2013:1-4.
[43]Choi B,Kim B,Kim E.A modified dynamic Window approach in crowded indoor environment for intelligent transport robot[A].Proceeding of 12th International Conference on Control,Automation and Systems[C].2012:1007-1009.
[44]Saranrittichai P,Niparnan N,Sudsang A.Robust local obstacle avoidance for mobile robot based on Dynamic Window approach[A].2013 10th International Conference on Electrical Engineering/Electronics,Computer,Telecommunications and Information Technology[C].2013.
[45]Pablo I B,Fernando D R,Diaz S V,et al.The shared control dynamic Window approach for non-holonomic semi-autonomous robots[A].2014,41st International Symposium on Robotics[C].2014.
[46]程传奇,郝向阳,李建胜,等.融合改进A*算法和动态窗口法的全局动态路径规划[J].西安交通大学学报,2017,51(11):137-142.
[47]Tian L,Collins C.An effective robot trajectory planning method using agenetic algorithm[J].Mechatronics,2004,14(5):455-470.
[48]朱大奇,颜明重.移动机器人路径规划技术综述[J].控制与决策,2010,25(7):961-967.
[49]黄云清,梁靓.机器人导航系统中的路径规划算法[J].微计算机信息,2006,22(7):259-261.
[50]李庆中,顾伟康.基于遗传算法的移动机器人动态避障路径规划算法[J].模式识别与人工智能,2002,15(2):161-166.
[51]Roberge V,Tarbouchi M,Labonte G.Comparison of parallel genetic algorithm and particle swarm optimization for realtime UAV path planning[J].IEEE Transactions on Industrial Informatics,2013,2(1):132-141.
[52]陈刚,沈成林.复杂环境下路径规划问题的遗传路径规划方法[J].机器人,2001,23(1):40-50.
[53]陈志军,曾蒸.基于模糊神经网络和遗传算法的机器人三维路径规划[J].重庆师范大学学报(自然科学版),2018,35(1):93-99.
[54]Colorni A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies[A].Proc of the ECAL-91[C].Paris,1991:134-142.
[55]Dorigo M,Maniezzo V,Colorni A.The ant system:Optimization by a colony of cooperating agents[J].IEEE Trans on Systems,Man&Cybernetics-B,1996,26(2):29-41.
[56]Dorigo M,Gambardella L M.Ant colony system:A cooperative learning approach to the travelling sales-man problem[J].IEEE Trans on Evolutionary Computation,1997,1(1):53-66.
[57]Taylor B,Choi A.Fuzzy ant colony algorithm for terrain following optimization[A].Procceedings-IEEE International Conference on Systems,Man and Cybernetics[C].New York,USA,2014:3834-3839.
[58]Riahi V,Kazemi M.A new hybrid ant colony algorithm for scheduling of nowait flowshop[J].2018,18(1):55-74.
[59]王辉,王景良,朱龙彪,等.基于改进蚁群算法的泊车系统路径规划[J].控制工程,2018,25(2):253-258.
[60]李龙澍,喻环.改进蚁群算法在复杂环境中机器人路径规划上的应用[J].小型微型计算机系统,2017,9:2067-2071.
[61]彭凡彬,杨俊杰,叶波.改进蚁群算法的变电站群机器人路径规划研究[J].仪表技术,2018,(3):9-13.
[62]Kennedy J,Eberhart R C.Particle swarm optimization[A].Proceedings of the IEEE International Conference on Neural Networks[C].Piscataway,New Jersey:IEEE Service Center,1995,4:1942-1948.
[63]Eberhart R C,Shi Y.Particle swarm optimization:developments applications anf resources[A].Proceedings of the Congress on Evolutionary Computation 2001[C].Piscataway,New Jersey:IEEE Press,2001:81-86.
[64]Shi Y.Krohling R A.Co-evolutionary particle swarm optimization to solve min-max problems[A].Proc of the IEEECong on Evolutionary Computation[C].Honolulu,2002:1682-1687.
[65]孙波,陈卫东,席裕庚.基于粒子群优化算法的移动机器人全局路径规划[J].控制与决策,2005,20(9):1052-1055,1060.
[66]秦元庆,孙德宝,李宁,等.基于粒子群算法的移动机器人路径规划[J].机器人,2004,26(3):222-225.
[67]Delice Y,Aydogan E K,Ozcan U,et al.A modified particle swarm optimization algorithm to mixed-model two-sided assembly line balancing[J].2017,28(1):23-36.
[68]翁理国,纪壮壮,夏旻,等.基于改进多目标粒子群算法的机器人路径规划[J].系统仿真学报,2014,26(12):2892-2898.
[69]王学武,严益鑫,顾幸生.基于莱维飞行粒子群算法的焊接机器人路径规划[J].控制与决策,2017,32(2):373-377.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |