Computer Science

Computer Science ›› 2021, Vol. 48 ›› Issue (10): 19-29.doi: 10.11896/jsjkx.200700114

• Artificial Intelligence • Previous Articles     Next Articles

Overview of Global Path Planning Algorithms for Mobile Robots

WANG Zi-qiang1, HU Xiao-guang2, LI Xiao-xiao1, DU Zhuo-qun1   

  1. 1 School of Information and Network Security,People's Public Security University of China,Beijing 100038,China
    2 School of Investigation,People's Public Security University of China,Beijing 100038,China
  • Received:2020-07-19 Revised:2021-01-26 Online:2021-10-15 Published:2021-10-18
  • About author:WANG Zi-qiang,born in 1996,master.His main research interests include autonomous navigation of mobile robot.
    HU Xiao-guang,born in 1980,Ph.D,lecturer.His main research interests include application of intelligent technology in artificial intelligence and computer vision.
  • Supported by:
    Special Project of People's Public Security University of China(2020JWCX08),Opening Project of Shanghai Key Laboratory of Crime Scene Evidence(2020XCWZK05) and National Key Research and Development Program of China.

PDF (PC)

4773

Abstract: Global path planning is the key technology of mobile robot outdoor work,and global path planning algorithm is mainly used in geographical scenarios to predict the outdoor environment.In the face of the complex outdoor environment,the robot optimizes the algorithm to improve real-time obstacle avoidance of robot path planning,path smoothness,planning effectiveness,which has become the core content in the research of global path planning algorithm.Depending on the degree of intelligent algorithm,the global path planning algorithm for mobile robot is divided into traditional global path planning algorithm and the bionic intelligent global path planning algorithm.Then,this paper further expounds the current practical multi-objective path planning algorithm,introduces several typical optimizations of each algorithm,and summarizes and analyzes the advantages and disadvantages of the improved algorithm.Finally,this paper discusses the future development trend of global path algorithm,and points out four aspects of future research and development,which are optimizing the performance of the conventional algorithm for path planning,various existing algorithms advantage integration,complex environment dynamic obstacle avoidance and improving map representation methods adapting to diverse environment.

Key words: Bionic intelligent algorithm, Global path planning, Mobile robot, Multi-objective path planning, Traditional algorithm

CLC Number: 

  • TP242
[1]KIM S,JIN H,SEO M,et al.Optimal Path Planning of Automated Guided Vehicle using Dijkstra Algorithm under Dynamic Conditions[C]//2019 7th International Conference on Robot Intelligence Technology and Applications (RiTA).doi:10.1109/ritapp.2019.8932804.
[2]LI J,YANG F.Uav field spraying track planning based on IGWO-A* Algorithm[J].Journal of Shenyang Agricultural University,2020,51(2):231-237.
[3]PU H H,HUANG H B.Research on global path planningmethod of unmanned surface vehicle[J].Marine Science,2018,42(1):93-105.
[4]SUN Y S,WANG L F,WU J,et al.Overview of path planning methods for intelligent underwater robots[J].Ship Science and Technology,2020,42(4):1-7.
[5]MAAREF M,KASSAS Z M.Optimal GPS Integrity-Constrai-ned Path Planning for Ground Vehicles[C]//2020 IEEE/ION Position,Location and Navigation Symposium (PLANS).2020.
[6]SONG X R,REN Y Y,GAO S,et al.Overview of path planning for mobile robots[J].Computer Measurement and Control,2019,27(4):1-5,17.
[7]HUO F C,CHI J,HUANG Z J,et al.Overview of Path Planning Algorithms for Mobile Robots[J].Journal of Jilin University (Information Science Edition),2018,36(6):639-647.
[8]LIU L M,WU T,FANG Y Q,et al.A smart map representation for autonomous vehicle navigation[C]//2015 12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD).2015.
[9]GRITSENKO P.Plane object-based high-level map representation for SLAM.Lecture Notes in Computer Science[C]//Computer Vision and Graphics-International Conference(ICCVG 2018).2018.
[10]LU T Z,ZHAO C X,XIA P P.Global Path Planning based on Synchronous Viewable Construction and A* Algorithm[J].Journal of Nanjing University of Science and Technology (Natural Science Edition),2017,41(3):313-321.
[11]CHEN J,QIN X,LI X,et al.Multi-robot Collaborative Obstacle Avoidance Based on Artificial Potential Field Method[J].Computer Science,2020,47(11):220-225.
[12]GUNAWAN S A,PRATAMAG N P,CAHYADI A I,et al.Smoothed A-star Algorithm for Nonholonomic Mobile Robot Path Planning[C]//2019 International Conference on Information and Communications Technology (ICOIACT).2019.
[13]WANG Z Y,ZENG G H,HUANG B,et al.Global optimal path planning for robots with improved A* algorithm[J].Computer application,2019,39(9):2517-2522.
[14]ZHOU T,ZHAO J,HU Q X,et al.Global path planning and tracking of mobile robots in complex environments[J].Compu-ter Engineering,2018,44(12):208-214.
[15]GURUJI A K,AGARWAL H,PARSEDIYA D K.Time-Efficient A Algorithm for Robot Path Planning[J].Procedia Technology,2016,23:144-149.
[16]ZHENG T,XU Y,ZHENG D.AGV Path Planning based on Improved A-star Algorithm[C]//2019 IEEE 3rd Advanced Information Management,Communicates,Electronic and Automation Control Conference(IMCEC).2019.
[17]CHENG C Q,HAO X Y,LI J S,et al.Global dynamic pathplanning based on improved A* algorithm and dynamic window method[J].Journal of Xi'an Jiaotong University,2017,51(11):137-143.
[18]CHEN J,LI M,YUAN Z,et al.An Improved A* Algorithm for UAV Path Planning Problems[C]//2020 IEEE 4th Information Technology,Networking,Electronic and Automation Control Conference (ITNEC).2020.
[19]WU X,XU L,ZHEN R,et al.Bi-Directional Adaptive A* Algorithm Toward Optimal Path Planning for Large-Scale UAV Under Multi-Constraints[J].IEEE Access,2020(99):1.
[20]ZHANG X,CHENG C Q,HAO X Y,et al.A dynamic path planning algorithm for robots with both global and local characteristics[J].Journal of Surveying and Mapping Science and Technology,2018,35(3):315-320.
[21]ZAMMIT C,VAN K E J.Comparison between A* and RRT Algorithms for UAV Path Planning[C]//2018 AIAA Gui-dance,Navigation,and Control Conference.2018.
[22]KIM D H,CHOI Y S,KIM S H,et al.Adaptive rapidly-exploring random tree for efficient path planning of high-degree-of-freedom articulated robots[C]//Proceedings of the Institution of Mechanical Engineers,Part C:Journal of Mechanical Engineering Science.2015.
[23]SCHMID L,PANTIC M,KHANNA R,et al.An Efficient Sampling-Based Method for Online Informative Path Planning in Unknown Environments[C]//IEEE Robotics and Automation Letters.2020,5(2):1.
[24]HU X,LIANG T,WANG M,et al.Path planning for a new tree heuristic search algorithm[J].Computer Engineering and application,2020,56(11):164-171.
[25]MASHAYEKHI R,IDRIS M,ANISI M H,et al.InformedRRT*-Connect:An Asymptotically Optimal Single-Query Path Planning Method[J].IEEE Access,2020,8:1.
[26]ZIVOJEVIC D,VELAGIC J.Path Planning for Mobile Robotusing Dubins-curve based RRT Algorithm with Differential Constraints[C]//2019 International Symposium ELMAR.2019.
[27]DING S,CHEN M,WANG M,et al.Global Path Planningmethod for Underwater Robots based on RRT* Algorithm[J].Ship Science and Technology,2019,41(9):66-73.
[28]LIU Z,ZHANG J.Path Planning of Indoor Mobile Robot based on Improved RRT Algorithm[J].Computer Engineering and Application,2020,56(9):190-197.
[29]MCCOURT M,TON C T,MEHTA S S.Adaptive Step-length RRT Algorithm for Improved Coverage[C]//AIAA Guidance,Navigation,and Control Conference.2016.
[30]WANG J,CHI W,LI C,et al.Neural RRT*:Learning-Based Optimal Path Planning[C]//IEEE Transactions on Automation Science and Engineering.2020.
[31]SUN B,JIANG P,ZHOU G,et al.AGV path planning based on improved genetic algorithm[J].Computer Engineering and Design,2020,41(2):550-556.
[32]LI S,SONG Q,LI Z,et al.Research review of genetic algorithm in robot path planning[J].Science,Technology and Enginee-ring,2020,20(2):423-431.
[33]SONG Y,WANG Z M.Path planning of mobile robot based on improved Genetic Algorithm[J].Modern Electronic technology,2019,42(24):172-175.
[34]LI M,WANG C,CHEN Z,et al.Path planning of mobile robot based on genetic algorithm and gene rearrangement[C]//2017 Chinese Automation Congress (CAC).2017.
[35]WEI T,LONG C.Path planning of mobile robot based on improved Genetic Algorithm[J].Journal of Beijing University of Aeronautics and Astronautics,2020,46(4):703-711.
[36]GE Y,DU M,NIU C,et al.Path planning of mobile robot based on genetic algorithm with predictive operator and dynamic parameters[C]//2017 13th International Conference on Natural Computation,Fuzzy Systems and Knowledge Discovery (ICNC-FSKD).2017.
[37]YI X,GUO W S,ZHAO L.A robot path planning method using adaptive selection operator combined with genetic algorithm[J].Computer Application Research,2020,37(6):1745-1749.
[38]KE C Y,AN S.Research on UAV Global Path Planning Algorithm[J].Information Technology,2019(5):33-35,40.
[39]VICMUDO M P,DADIOS E P,VICERRA R R P.Path planning of underwater swarm robots using genetic algorithm[C]//2014 International Conference on Humanoid,Nanotechnology,Information Technology,Communication and Control,Environment and Management (HNICEM).2014.
[40]HU Z,SUN L,ZHANG Y,et al.A Robot Path Planning Algorithm Based on Improved QPSO[J].Computer Engineering,2019,45(4):281-287.
[41]YANG P,ZHAO Z,ZHENG H X.Research on global pathplanning method of mobile robot based on improved ant colony algorithm[J].Machinery Manufacturing and Automation,2017,46(6):155-157,192.
[42]CHEN Y,LI T,YU S,et al.Robot global path planning based on potential field ant colony algorithm[J].Journal of Dalian University of Technology,2019,59(3):316-322.
[43]LI G,LI H,ZHANG S,et al.Optimal path planning and para-meter research based on ant colony algorithm[J].Chinese Science and Technology Paper,2018,13(16):1909-1914.
[44]LEE M G,YU K M.Dynamic Path Planning Based on an Improved Ant Colony Optimization with Genetic Algorithm[C]//2018 IEEE Asia-Pacific Conference on Antennas and Propagation (APCAP).2018.
[45]HU Q,WANG T,ZHANG R.Research on improved ant colony algorithm in AGV Global Path Planning[J].Information Technology and Informatization,2019(3):116-118.
[46]QIAN W,ZHOU L.An Improved Ant Colony Algorithm ofThree Dimensional Path Planning[C]//2017 10th International Symposium on Computational Intelligence and Design (ISCID).2017.
[47]SONG Q,ZHAO Q,WANG S,et al.Dynamic Path Planning for Unmanned Vehicles Based on Fuzzy Logic and Improved Ant Colony Optimization[J].IEEE Access,2020,8:62107-62115.
[48]CAO X,WANG Z,FENG J,et al.Research on robot global path planning based on improved ant colony algorithm[J].Computer Engineering and Science,2020,42(3):564-570.
[49]ZHAN W,QU J,LU X,et al.Global path planning for mobile robots based on improved ant colony algorithm[J].Modern Electronic Technology,2018,41(24):170-173.
[50]ZHAO H.Optimal Path Planning for Robot Based on Ant Colony Algorithm[C]//2020 International Wireless Communications and Mobile Computing (IWCMC).2020.
[51]YEN C T,CHENG M F.A study of fuzzy control with ant colony algorithm used in mobile robot for shortest path planning and obstacle avoidance[J].Microsystem Technologies,2018,24(1):125-135.
[52]WANG X,SHI H,ZHANG C.Path Planning for IntelligentParking System Based on Improved Ant Colony Optimization[J].IEEE Access,2020,8:65267-65273.
[53]TAN J,WANG C,WANG Y,et al.Three-dimensional pathplanning based on ant colony algorithm with potential field For rotary-wing flying robot[C]//2015 IEEE International Confe-rence on Information and Automation.2015.
[54]SHI X,XIE F.Global path Planning of manned submersiblebased on improved ant colony algorithm[J].Journal of Marine Technology,2019,38(2):14-20.
[55]JIA H Q,WEI Z H,HE X,et al.Path planning based on improved particle swarm optimization[J].Chinese Journal of Agricultural Machinery,2018,49(12):371-377.
[56]LIU Y,CHEN T,ZHANG F.Path Planning for Mobile Robots based on Improved Particle Swarm Optimization[J].Journal of Zhengzhou University (Science Edition),2020,52(1):114-119.
[57]HAN M,LIU J,WU S,et al.Path planning algorithm for mobile robots with particle swarm optimization[J].Computer Application,2017,37(8):2258-2263.
[58]YU W,LOW K H,CHEN L.Cooperative Path Planning forHeterogeneous Unmanned Vehicles in a Search-and-Track Mission Aiming at an Underwater Target[J].IEEE Transactions on Vehicular Technology,2020,69(6):6782-6787.
[59]ZHI J,HUANG J,GUO J,et al.Path planning based on improved particle swarm optimization algorithm[J].Automation and Instrumentation,2020,35(4):34-38.
[60]ZENG N,ZHANG H,CHEN Y,et al.Path planning for intelligent robot based on switching local evolutionary PSO algorithm[J].Assembly Automation,2016,36(2):120-126.
[61]CHEN J,WEI G,TIAN X.Improved particle swarm optimization for Mobile Robot smooth path Planning[J].Miniature Microcomputer System,2019,40(12):2550-2555.
[62]HAN Y,XU Y,ZHOU J.Robot path planning for particleswarm optimization[J].Modular Machine Tool and Automatic Processing Technology,2020(2):47-50.
[63]PATLEY A,BHATT A,MAITY A,et al.Modified ParticleSwarm Optimization based Path Planning for Multi-Uav Formation[C]//AIAA Scitech 2019 Forum.2019.
[64]ZHAO X,JI K,LIN H,et al.Emergency resource allocationmodel based on multi-objective path planning[J].Journal of South China Universityof Technology (Natural Science Edition),2019,47(4):76-82.
[65]ZHANG L,LIU J,TAN S.Multi objective planning of evacuation path in complex building fire[J].Journal of Northeast University (Natural Science Edition),2020,41(6):761-766.
[66]WANG X,XIA Z,GU X.Multi objective path planning of wel-ding robot based on dmoea / d-et algorithm[J].Journal of South China University of Technology (Natural Science Edition),2019,47(4):99-106.
[67]GUL F.Meta-heuristic approach for solving multi-objective path planning for autonomous guided robot using PSO-GWO optimization algorithm with evolutionary programming[J].Journal of Ambient Intelligence and Humanized Computing,2021:12(7):3.
[68]AJEIL F H,IBRAHEEM I K,SAHIB M A,et al.Multi-objective path planning of an autonomous mobile robot using hybrid PSO-MFB optimization algorithm[J/OL].Applied Soft Computing,2018.https://arxiv.org/abs/1805.00224v3.
[69]YU J,WANG Y,RUAN X,et al.AGV multi-objective pathplanning method based on improved cuckoo algorithm[C]//2019 IEEE 4th Advanced Information Technology,Electronic and Automation Control Conference (IAEAC).IEEE,2019.
[70]ZHAO D,YU H,FANG X,et al.A Path Planning MethodBased on Multi-Objective Cauchy Mutation Cat Swarm Optimization Algorithm for Navigation System of Intelligent Patrol Car[J].IEEE Access,2020(99):1.
[71]REN Q.Multi-objective path planning for UAV in the urban environment based on CDNSGA-II[C]// Proceedings -13th IEEE International Conference on Service-Oriented System Enginee-ring.2019.
[72]CARLOS M L,HERNANDEZ -SOSA D,GREINER D,et al.An Approach to Multi-Objective Path Planning Optimization for Underwater Gliders[J].Sensors (Basel,Switzerland),2019,19(24).
[73]KOZIOL S.Multi-Objective Path Planning for Autonomous Robots Using Reconfigurable Analog VLSI[J].IEEE Access,2020(99):1.
[74]GABBASSOVA Z.Robot path planning for multiple robots con-sidering safest and shortest path[C]//Proceedings of the 1st In-ternational Conference of Information Systems and Design-v 2570.2019.
[75]TANG K,FU H,JIANG T H,et al.Reinforcement Learning for Robots Path Planning with Rule-based Shallow-trial[C]//2019 IEEE 16th International Conference on Networking,Sensing and Control (ICNSC).2019
[76]WEI M,WANG S,ZHENG J,et al.UGV Navigation Optimiza-tion aided by Reinforcement Learning-based Path Tracking[J].IEEE Access,2018,PP(99):1.
[77]NI J,ZHANG Z,SU B,et al.A bio-inspired neural networkbased PSO method for robot path planning[C]//2017 13th International Conference on Natural Computation,Fuzzy Systems and Knowledge Discovery (ICNC-FSKD).2017.
[78]LIU X,ZHANG D,YAN H,et al.A New Algorithm of the Best Path Selection based on Machine Learning[J].IEEE Access,2019,7:126913-126928.
[79]CAO F K,ZHUANG Y,YAN F,et al.Research progress and Prospect of long-term autonomous environment adaptation of mobile robots [J/OL].Acta Automatica Sinica,2020.https://d.wanfangdata.com.cn/periodical/ChlQZXJpb2RpY2FsQ0hJTmV3UzIwMjEwNjA4Eg56ZGh4YjIwMjAwMjAwMRoIYm1jM2Z2MXQ%3D.
[1] 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.
[2] MA Hong. Fusion Localization Algorithm of Visual Aided BDS Mobile Robot Based on 5G [J]. Computer Science, 2020, 47(6A): 631-633.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] . Research on Dynamic Obstacle Avoidance and Path [J]. Computer Science, 2012, 39(3): 223-227.
[10] . Mobile Robot Middleware Supporting Self-adaptive Programming [J]. Computer Science, 2012, 39(10): 119-124.
[11] ZHUANG Jia-yuan, WAN Lei , I_IAO Yu-lei , SUN Han bing. Global Path Planning of Unmanned Surface Vehicle Based on Electronic Chart [J]. Computer Science, 2011, 38(9): 211-214.
[12] LIAO Zhuo-fan,WANG Jian-xin,LIANG Jun-bin. Dynamic Deployment of Nodes in Wireless Sensor Networks [J]. Computer Science, 2011, 38(10): 45-50.
[13] ZHOU Jing,DAI Guan-zhong,CAI Xiao-yan. Research and Simulating of Global Optimal Path Planning of Mobile Robot Based on Ant Colony System [J]. Computer Science, 2010, 37(5): 171-174.
[14] YANG Jin-yuan,HUANG Xin-han,LI Peng. DSmT-based Mobile Robot Map Building and Sensor Management [J]. Computer Science, 2010, 37(4): 227-.
[15] KANG Liang ZHAO Chun-xia GUO Jian-hui （School of Computer Science, Nanjing University of Science and Technology, Nanjing 210094, China）. [J]. Computer Science, 2009, 36(6): 241-244.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.