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

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

CLC Number:

TP242

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.

References

[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

Comments

Recommended 0

No Suggested Reading articles found!

Review of Path Planning Algorithms for Mobile Robots

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0

[1]	WEI Shuxin, WANG Qunjing, LI Guoli, XU Jiazi, WEN Yan. Path Planning for Mobile Robots Based on Modified Adaptive Ant Colony Optimization Algorithm [J]. Computer Science, 2024, 51(6A): 230500145-9.
[2]	LIN Yegui, DAI Zhijian, HE Defeng, XING Kexin. Visual Servoing Predictive Control for Omnidirectional Mobile Robots with SuppressionofVelocity Abrupt Change [J]. Computer Science, 2024, 51(11A): 240300003-6.
[3]	AN Yang, WANG Xiuqing, ZHAO Minghua. Mobile Robots' Path Planning Method Based on Policy Fusion and Spiking Deep ReinforcementLearning [J]. Computer Science, 2024, 51(11A): 240100211-11.
[4]	LI Yawen, ZHANG Botao, ZHONG Chaoliang, LYU Qiang. Lightweight Terrain Map Building Approach Combining Laser and Vision [J]. Computer Science, 2024, 51(11A): 240400051-9.
[5]	WANG Shuaiwei, LEI Jie, FENG Zunlei, LIANG Ronghua. Review of Visual Representation Learning [J]. Computer Science, 2024, 51(11): 112-132.
[6]	CHEN Ji-qing, TAN Cheng-zhi, MO Rong-xian, WANG Zhi-kui, WU Jia-hua, ZHAO Chao-yang. Path Planning of Mobile Robot with A^* Algorithm Based on Artificial Potential Field [J]. Computer Science, 2021, 48(11): 327-333.
[7]	WANG Zi-qiang, HU Xiao-guang, LI Xiao-xiao, DU Zhuo-qun. Overview of Global Path Planning Algorithms for Mobile Robots [J]. Computer Science, 2021, 48(10): 19-29.
[8]	MA Hong. Fusion Localization Algorithm of Visual Aided BDS Mobile Robot Based on 5G [J]. Computer Science, 2020, 47(6A): 631-633.
[9]	DONG Chao-ying, XU Xin, LIU Ai-jun, CHANG Jing-hui. New Routing Methods of LEO Satellite Networks [J]. Computer Science, 2020, 47(12): 285-290.
[10]	CHEN Jun-ling, QIN Xiao-lin, LI Xing-luo, ZHOU Yang-hao, BAO Bin-guo. Multi-robot Collaborative Obstacle Avoidance Based on Artificial Potential Field Method [J]. Computer Science, 2020, 47(11): 220-225.
[11]	CHAI Hui-min, FANG Min, LV Shao-nan. Local Path Planning of Mobile Robot Based on Situation Assessment Technology [J]. Computer Science, 2019, 46(4): 210-215.
[12]	LIU Jie, ZHAO Hai-fang and ZHOU De-lian. Improved Quantum Behaved Particle Swarm Optimization Algorithm for Mobile Robot Path Planning [J]. Computer Science, 2017, 44(Z11): 123-128.
[13]	XU Teng-fei, LUO Qi and WANG Hai. Dynamic Path Planning for Mobile Robot Based on Vector Field [J]. Computer Science, 2015, 42(5): 237-244.
[14]	TANG Yi-ping, HU Da-wei, CAI Ying-mei, HUANG Ke and JIANG Rong-jian. Moving Object Detection in Omnidirectional Vision-based Mobile Robot [J]. Computer Science, 2015, 42(11): 314-319.
[15]	ZHANG He,LIU Guo-liang,LI Nan-jun and HOU Zi-feng. Submap and Adaptive Covariance Based Method for 2D Localization [J]. Computer Science, 2014, 41(10): 23-26.