移动机器人路径规划算法综述

doi:10.11896/jsjkx.240900074

摘要/Abstract

摘要： 路径规划算法是移动机器人实现自主运动的关键技术之一,能够帮助机器人在复杂的环境中优化出最优或次优的路径,使机器人从起点到达目标位置。良好的路径规划算法对提高机器人的性能、适应性和可靠性有重要意义。为全面清楚地了解目前国内外移动机器人路径规划算法的研究现状,对常用的移动机器人路径规划算法进行总结综述,根据每个算法的原理及特性,首先将路径规划算法分为传统算法、基于采样的算法、智能仿生算法、人工智能算法四大类;然后对每类算法进行细分,并对每个算法的原理及优缺点进行详细介绍,同时展示了一些学者对每个算法局限性的改进;最后总结对比分析每个算法的优缺点,对移动机器人路径规划算法的发展趋势进行归纳,以期为移动机器人路径规划发展提供一定的参考。

关键词: 移动机器人, 路径规划算法, 传统算法, 基于采样的算法, 智能仿生算法, 人工智能算法

Abstract: Path planning algorithm is one of the key technologies for mobile robots to achieve autonomous motion.It can help robots to optimize the optimal or suboptimal path in complex environments,enabling them to reach the target position from the starting point.A good path planning algorithm is of great significance for improving the performance,adaptability,and reliability of robots.In order to comprehensively and clearly understand the current research status of path planning algorithms for mobile robots at home and abroad,this paper summarizes and reviews the commonly used path planning algorithms for mobile robots.Based on the principles and characteristics of each algorithm,path planning algorithms are first divided into four categories:traditional algorithms,sampling based algorithms,intelligent bionic algorithms,and artificial intelligence algorithms.Secondly,each type of algorithm is subdivided,and the principles,advantages and disadvantages of each algorithm are introduced in detail,and some scholars’ improvements to the limitations of each algorithm are shown.Finally,the advantages and disadvantages of each algorithm are summarized,compared and analyzed,and the development trends of mobile robot path planning algorithms are summarized,in the hope of providing certain reference for the development of mobile robot path planning.

Key words: Mobile robot, Path planning algorithm, Traditional algorithm, Sampling based algorithm, Intelligent bionic algorithm, Artificial intelligence algorithm

中图分类号:

TP242

刘清云, 游雄, 张欣, 左吉伟, 李佳. 移动机器人路径规划算法综述[J]. 计算机科学, 2025, 52(6A): 240900074-10. https://doi.org/10.11896/jsjkx.240900074

LIU Qingyun, YOU Xiong, ZHANG Xin, ZUO Jiwei, LI Jia. Review of Path Planning Algorithms for Mobile Robots[J]. Computer Science, 2025, 52(6A): 240900074-10. https://doi.org/10.11896/jsjkx.240900074

参考文献

[1]WANG S X,LI A Y.Mult-adjacent-vertexes and Mult-shortest-paths problem of Dijkstra algorithm [J].Computer Science,2014,41(6):217-224.
[2]LI X X,MA X L,WANG X P.A survey of path planning algorithms for mobile robots [J].Computer Measurement and Control,2022,30(7):9-19.
[3]MA X L,LI R Y,WU L H.Review on local path planning algorithms for intelligent vehicle [J].Automobile Applied Technology,2022,47(23):232-237.
[4]CHEN J,SHEN Q.Review of path planning algorithm for automated guided vehicles [J].Automation & Instrumentation,2023(9):8-15.
[5]MA X G,MA X Q.Robot path planning based on improve RRT and Dijkstra approach [J].Modular Machine Tool & Automatic Manufacturing Technique,2023(2):5-9.
[6]FENG S D,XU Q,ZHU X M,et al.Fast method for long-distance off-road path planning based on terrain data [J].Journal of Geo-information Science,2022,24(9):1742-1754.
[7]ZHOU X W,YAN J W,YAN M,et al.Path planning of Rail-Mounted logistics robots based on the improved Dijkstra algorithm [J].Appl.Sci.,2023,13:9955.
[8]BING H,LAI L.Improvement and application of Dijkstra algorithms[J].Academic Journal of Computing & Information Science,2022,5(5):97-102.
[9]GARG D.Dynamizing Dijkstra:A solution to dynamic shortestpath problem through retroactive priority queue[J].Journal of King Saud University-Computer and Information Sciences,2021,33(3):364-373.
[10]GOLD B,HARREL S.Computing the shortest path:A^* search meets graph theory:MSR-TR-2004-24 [R].Redmond:Microsoft Corporation,2003.
[11]LIU Q,YOU X,ZHANG X,et al.Unmanned vehicle off-roadpath-planning method with comprehensive constraints on multiple environmental factors[J].International Journal of Digital Earth,2024,17(1):2408453.
[12]ZHANG Y,LI L L.Development of path planning approach using improved A-star algorithm in AGV system [J].Journal of Internet Technology,2019,20(3):915-924.
[13]DUCHON F,BABINEC A,KAJAN M,et al.Path planningwith modified a star algorithm for a mobile robot [J].Procedia Engineering,2014,96(7):59-69.
[14]ZHENG Z Q,DUAN F,SONG G P,et al.Summary of research on path planning algorithm of unmanned vehicle[C]//Procee-dings of the 2022 Unmanned Systems Summit Forum.2022:5.
[15]YAN X D,CHANG T Q,GUO L B.Research on path planning of unmanned vehicle in off-road battlefield environment [J].Journal of Ordnance Equipment Engineering,2022,43(10):288-293.
[16]ZHANG J,WU J,SHEN X,et al.Autonomous land vehicle path planning algorithm based on improved heuristic function of A-Star [J].International Journal of Advanced Robotic Systems,2021,18(5):17298814211042730.
[17]YU X,LIANG H W,DU M B,et al.An improved A^* algorithm for searching infinite neighborhoods [J].Robot,2014,36(5):627-633.
[18]GONG P,LI W B,MA Q S,et al.Research on unmanned vehicle path planning based on improved A algorithm [J].Modular Machine Tool & Automatic Manufacturing Technique,2023(3):17-20,24.
[19]ZHANG X R,JU H H.Analysis of evaluation function based on D^* Lite algorithm [J].Computer Engineering,2012,38(1):154-156.
[20]SHI J G,LI K Y.Indoor path planning based on improved hierarchical D^* algorithm [J].Application Research of Computers,2015,32(12):3609-3612.
[21]LIU J,FENG S,REN J H.Directed D^* algorithm for dynamic path planning of mobile robots [J].Journal of Zhejiang University(Engineering Science),2020,54(2):291-300.
[22]ZHANG X W,XIAO B X.Improved D^* algorithm for mobile robot path planning [J].Transducer and Microsystem Techno-logies,2018,37(12):52-54,58.
[23]LIU X T,CAI Y F,WANG T C.An application of constrainedD^* algorithm based on support vector machine in automated vehicle routing [J].Computer and Digital Engineering,2017,45(9):1748-1754.
[24]KHATIB O.Real-time Obstacle Avoidance System for Manipulators and Mobile Robots [J].The International Journal of Robotics Research,1986,5(1):90-98.
[25]ZHA M,WANG Z W,FENG J,et al.Unmanned vehicle route planning based on improved artificial potential field method [J].Journal of Physics:Conference Series,2020,1453(1):012059.
[26]HOU P Q,PAN H,GUO C.Simulation research for mobile robot path planning based on improved artificial potential field method recommended by the AsiaSim [J].International Journal of Modeling,Simulation,and Scientific Computing,2017,8(2):1750046.
[27]FAN X J,GUO Y J,LIU H,et al.Improved Artificial Potential Field Method Applied for AUV Path Planning [J].Mathematical Problems in Engineering,2020,2020(4):6523158.
[28]REN Y,ZHAO H B.Robot Obstacle Avoidance and Path Planning with Improved Artificial Potential Field Method [J].Computer Simulation,2019,37(2):360-364.
[29]LIU A X,ZHOU Y L,LIU H J.Path planning of medical deli-very robot based on improved artificial potential field method [J].Application Research of Computers,2024,41(3):842-847.
[30]ZHAO M,ZHENG Z Y,ME Q F,et al.Path planning method for multiple mobile robots based on modified potential field method [J].Application Research of Computers,2020,37(S2):66-68,72.
[31]KAVRAKI L,LATOMBE J C.Randomized preprocessing ofconfiguration space for fast path planning [C]//Proc of IEEE International Conference on Robotics and Automation.1994:3020-3026.
[32]ELBANHAWI M,SIMIC M.Sampling-based Robot MotionPlanning:A Review [J].IEEE Access,2014,2(1):56-77.
[33]CHENG Q,GAO S,CAO K,et al.Path planning of mobilebased on PRM optimization algorithm [J].Computer Applications and Software,2020,37(12):254-259,296.
[34]XIA Y,SUI Y.Research on optimization of PRM path planning algorithm [J].Applied Science and Technology,2010,37(10):1-5.
[35]ZOU S X,WANG P,HAN X.Improved path planning algorithm based on PRM [J].Modular Machine Tool & Automatic Manufacturing Technique,2019(1):1-3.
[36]AARNO D,KRAGIC D,CHRISTENSEN H I.Artificial potential biased probabilistic roadmap method[C]//IEEE International Conference on Robotics and Automation,2004.IEEE,2004,1:461-466.
[37]LIU Y,ZHANG W G,LI W G.Study on path planning based on improved PRM method [J].Application Research of Compu-ters,2012,29(1):104-106,139.
[38]MA X,GONG R,TAN Y,et al.Path planning of mobile robot based on improved PRM based on cubic spline[J].Wireless Communications and Mobile Compu-ting,2022,2022(1):1632698.
[39]LI Q Q,XU Y Q,BU S Q,et al.Smart vehicle path planning based on modified PRM algorithm [J].Sensors,2022,22(17):6581.
[40]LAVALLE S.Rapidly-Exploring Random Trees:A New Toolfor Path Planning [J].Algorithmic & Computational Robotics New Directions,1999,31(2):293-308.
[41]XU X X,ZHOU Q Y,XI Y Y,et al.Path planning based on improved RRT algorithm [J].China Science and Technology Information,2023,(17):124-127.
[42]HAI Z Y,WANG J,MOU S K,et al.Overview of self-drivigpath planning algorithm [J].Agricultural Equipment & Vehicle Engineering,2022,60(11):142-146.
[43]LAVALLE S M.Rapidly-Exploring Random Trees:A New Tool for Path Planning[J].Algorithmic & Computational Robotics New Directions,1999,31(2):293-308.
[44]LIU Z Y,ZHANG J.Path planning using improved RRT algorithm for indoor mobile robot [J].Computer Engineering and Applications,2020,56(9):190-197.
[45]LI W D,LI L.Path planning of unmanned vehicle based on improved RRT algorithm [J].Computer Measurement and Control,2023,31(1):160-166.
[46]HUANG S Y.Path planning based on mixed algorithm of RRT and artificial potential field method [C]//2021 4th International Conference on Intelligent Robotics and Control Engineering(IRCE).IEEE,2021:149-155.
[47]KONG T F,GAO H B,CHEN X X.Full-coverage path planning for cleaning robot based on improved RRT[J].Computer Engineering and Applications,2024(13):311-318.
[48]MAI Z Q,XIN Z,ZHANG X Q.Research on robot path planning based on improved traditional RRT algorithm [J].Machine Building & Automation,2022,51(6):177-179.
[49]KARAMAN S,FRAZZOLI E.Sampling-based algorithms foroptimal motion planning[J].The international journal of robotics research,2011,30(7):846-894.
[50]SAMPSON J R.Adaptation in Natural and Artificial Systems [J].Society for Industrial & Applied Mathematics,1976,18(3):529-530.
[51]ZHOU J,HE Y Q.Research progress on navigation path planning of agricultural machinery [J].Transactions of the Chinese Society of Agricultural Machinery,2021,52(9):1-14.
[52]NARVYDAS G,SIMUTIS R,RAUDONIS V.Autonomous mobile robot control using IF-THEN rules and genetic algorithm [J].Information technology and control,2008,37(3).
[53]WANG H J,WANG L N.Review of path planning for robots[J].Journal of Guilin University of Technology,2023,43(1):137-147.
[54]GE C,SUSILO W,LIU Z,et al.Secure keyword search and data sharing mechanism for cloud computing [J].IEEE Transactions on Dependable and Secure Computing,2020,18(6):2787-2800.
[55]CHEN X.Summary of research on path planning of mobile robot based on genetic algorithms [J].Science Technology and Industry,2023,23(8):274-278.
[56]LI S B,SONG Q S,LI Z A,et al.Review of genetic algorithm in robot path planning [J].Science Technology and Engineering,2020,20(2):423-431.
[57]YANG B,LIU S D,LU W J,et al.Application of improved genetic algorithm in robot path planning [J].Modern Manufacturing Engineering,2022(6):9-16.
[58]CHEN G Y,SONG Y X.Application of improved genetic algorithm in mobile robot path planning [J].Computer Applications and Software,2023,40(2):302-307.
[59]LI K R,HU Q Q,LIU J P.Path planning of mobile robot based on improved multiobjective genetic algorithm [J].Wireless Communications and Mobile Computing,2021,2021:1-12.
[60]XU L,LIU Y H,WANG Q F.Application of adaptive geneticalgorithm in robot path planning [J].Computer Engineering and Applications,2020,56(18):36-41.
[61]KENNEDY J,EBERHART R.Particle swarm optimization[C]//Proc of International Conference on Neural Networks.Piscataway,NJ:IEEE Press,1995:1942-1948.
[62]EBERHART R,KENNEDY J.A new optimizer using particleswarm theory [C]//Proc of the 6th International Symposium on Micro Machine and Human Science.Piscataway,NJ:IEEE Press,1995:39-43.
[63]PATTANAYAK S,CHOUDHURY B B.Trajectory planning of an autonomous mobile robot [J].International Journal of Swarm Intelligence,2019,4(2):96-110.
[64]YU Z Z,LI Q,FAN Q G.Survey on application of bioinspired intelligent algorithms in path planning optimization of mobile robots [J].Application Research of Computers,2019,36(11):3210-3219.
[65]TANG B W,ZHAN X Z,LUO J J.A convergence-guaranteedparticle swarm optimization method for mobile robot global path planning [J].Assembly Automation,2017,37(1):114-129.
[66]WANG B F,LI S,GUO J,et al.Car-like mobile robot path planning in rough terrain using multi-objective particle swarm optimization algorithm [J].Neurocomputing,2018,282:42-51.
[67]QU X H,SHAN D,MENG G J.AGV path planning based on particle swarm optimization approaching the target [J].Journal of Hefei University of Technology(Natural Science),2022,45(1):1-6.
[68]ZHANG L,ZHANG Y J,LI Y F.Mobile robot path planning based on improved localized particle swarm optimization [J].IEEE Sensors Journal,2020,21(5):6962-6972.
[69]FENG J H,ZHANG T Y,FENG S,et al.Improved particle swarm optimization algorithm for robot path planning [J].Machinery Design & Manufacture,2021(9):291-294,298.
[70]DORIGO M.Optimization,learning and natural algorithms [D].Politecnico di Milano,1992.
[71]MULLEN R J,MONEKOSSO D,BARMAN S,et al.A review of ant algorithms[J].Expert systems with Applications,2009,36(6):9608-9617.
[72]BI J,FU M Y,ZHANG Y H.An improved ant colony algorithm for the shortest path problem [J].Computer Engineering and Applications,2003,39(3):107-109.
[73]ZHANG S C,PU J X,SI Y N,et al.Survey on application of ant colony algorithm in path planning of mobile robot [J].Computer Engineering and Applications,2020,56(8):10-19.
[74]WANG H J,WANG L N.Review of path planning for robots[J].Journal of Guilin University of Technology,2023,43(1):137-147.
[75]YU Z Z,LI Q,FAN Q G.Survey on application of bioinspired intelligent algorithms in path planning optimization of mobile robots [J].Application Research of Computers,2019,36(11):3210-3219.
[76]LIU S S,HUANG Y Q.Application of Multi-strategy ant colony algorithm in robot path planning [J].Computer Engineering and Applications,2022,58(6):278-286.
[77]WU L,HUANG X D,CUI J G,et al.Modified adaptive ant colony optimization algorithm and its application for solving path planning of mobile robot [J].Expert Systems with Applications,2023,215:119410.
[78]LIU C,WU L,XIAO W S,et al.An improved heuristic mechanism ant colony optimization algorithm for solving path planning [J].Knowledge-Based Systems,2023,271:110540.
[79]CHEN D F,LEI H,LIU J L,et al.Research on robot path planning based on reinforced ant colony optimization [J].Journal of Ordnance Equipment Engineering,2023,44(6):239-245,303.
[80]WANG X Y,HU Y H,XU J L,et al.Robot path planningmethod based on improved ant colony algorithm [J].Application of Electronic Technique,2023,49(1):75-80.
[81]FLOREANO D,MONDADA F.Evolutionary neuron-controllers for autonomous mobile robots [J].Neural Networks,1998,11(7/8):1467-1478.
[82]LIU Q,ZHAI J W,ZHANG Z C,et al.A survey on deep reinforcement learning [J].Chinese Journal of Computers,2018,41(1):1-27.
[83]LIU Y,ZHENG Z,QIN F Y,et al.A residual convolutional neu-ral network based approach for real-time path planning [J].Knowledge-Based Systems,2022,242:108400.
[84]SUNG I,CHOI B,NIELSEN P.On the training of a neural network for online path planning with offline path planning algorithms [J].International Journal of Information Management,2021,57:102142.
[85]LI J H.Research on neural network based intelligent mobile robot navigation algorithm [D].Hangzhou:Zhejiang University of Technology,2009.
[86]SONG Y,LI Y B,LI C,et al.Path planning methods of mobile robot based on neural network [J].Systems Engineering and Electronics,2008(2):316-319.
[87]LIU L,WANG Y N,KUANG F,et al.Path planning of mobile robot based on neural network and genetic algorithm [J].Application Research of Computers,2007(2):264-265,268.
[88]LIANG J,SONG K P.The application of neural network in mobile robot path planning [J].Journal of System Simulation,2010,22(S1):269-272.
[89]WANG X,WANG G D.A study of the neural-network-algo-rithm-based optimization of the routes for force projection [J].Traffic Engineering & Technology for National Defence,2021,19(2):9-14.
[90]MATSUO Y,LECUN Y,SAHANI M,et al.Deep learning,reinforcement learning,and world models [J].Neural Networks,2022,152:267-275.
[91]ZHANG N.Study on local path planning behavior for the mobile robot based on reinforcement Q learning and BP neural network [D].Zibo:Shandong University of Technology,2020.
[92]LIU Z R,JIANG S H.Review of mobile robot path planning based on reinforcement learning [J].Manufacturing Automation,2019,41(3):90-92.
[93]YAN J J,ZHANG Q S,HU X P.Review of path planning techniques based on reinforcement learning [J].Computer Enginee-ring,2021,47(10):16-25.
[94]GAO J L,YE W J,GUO J,et al.Deep reinforcement learning for indoor mobile robot path planning [J].Sensors,2020,20(19):5493.
[95]YU X Q,WANG P,ZHANG Z X.Learning-based end-to-endpath planning for lunar rovers with safety constraints[J].Sensors,2021,21(3):796.
[96]SONG L J,ZHOU Z Y,LI Y L,et al.Research on path planning algorithm based on improved Q-Learning algorithm [J].Journal of Chinese Mini-Micro Computer Systems,2024,45(4):823-829.
[97]FENG N,FAN F,XU G L,et al.Deep Reinforcement Learning Based AGV Self-navigation Obstacle Avoidance Method [J].Instrumentation,2022,9(4):11-16.
[98]JIA QI X,YANG M N,MIAO Y,et al.Path planning using deep reinforcement learning based on potential field in complex environment [C]//Journal of Physics:Conference Series.IOP Publishing,2021,1748(2):022016.
[99]YOU C X,LU J B,FILEV D,et al.Advanced planning for autonomous vehicles using reinforcement learning and deep inverse reinforcement learning [J].Robotics and Autonomous Systems,2019,114:1-18.
[100]HE X M,KUANG Y,YANG Z P,et al.Design of AGV intelligent navigation system based on deep reinforcement learning [J].Application Research of Computers,2022,39(5):1501-1504,1509.
[101]LIN G C,ZHU L X,LI J H,et al.Collision-free path planning for a guava-harvesting robot based on recurrent deep reinforcement learning [J].Computers and Electronics in Agriculture,2021,188:106350.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed