计算机科学 ›› 2021, Vol. 48 ›› Issue (10): 19-29.doi: 10.11896/jsjkx.200700114

• 人工智能* 上一篇    下一篇

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

王梓强1, 胡晓光2, 李晓筱1, 杜卓群1   

  1. 1 中国人民公安大学信息网络安全学院 北京100038
    2 中国人民公安大学侦查学院 北京100038
  • 收稿日期:2020-07-19 修回日期:2021-01-26 出版日期:2021-10-15 发布日期:2021-10-18
  • 通讯作者: 胡晓光(michael.hu.07@foxmail.com)
  • 作者简介:gadxwang2019@foxmail.com
  • 基金资助:
    中国人民公安大学专项项目(2020JWCX08);上海市现场物证重点实验室开放课题基金(2020XCWZK05);国家重点研究计划项目

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.

摘要: 全局路径规划是移动机器人室外工作的关键技术,全局路径规划相关算法主要应用于地理场景预知的室外环境中,机器人面对复杂多变的室外环境,通过对算法的优化改进来提高机器人路径规划的实时避障性、路径平滑性、规划有效性就成为了全局路径规划算法的核心研究内容。首先根据算法的智能程度,将移动机器人的全局路径规划算法分为传统全局路径规划算法和仿生智能全局路径规划算法,并深入阐述了实际应用更为广泛的多目标路径规划算法,然后介绍了当前每种算法的几种典型的优化改进方法,并对其优化改进后的算法的优缺点进行了分析总结,最后对全局路径算法的未来发展趋势进行了展望,指出全局路径规划算法将向优化已有常规算法路径规划的性能、多种算法优势融合、复杂环境中动态避障、适应多样化环境的地图表示方法这4方面发展。

关键词: 移动机器人, 全局路径规划, 传统算法, 仿生智能算法, 多目标路径规划

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: Mobile robot, Global path planning, Traditional algorithm, Bionic intelligent algorithm, Multi-objective path planning

中图分类号: 

  • 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] 马虹. 基于5G的视觉辅助BDS移动机器人融合定位算法[J]. 计算机科学, 2020, 47(6A): 631-633.
[2] 陈骏岭, 秦小麟, 李星罗, 周杨淏, 鲍斌国. 基于人工势场法的多机器人协同避障[J]. 计算机科学, 2020, 47(11): 220-225.
[3] 柴慧敏, 方敏, 吕少楠. 基于态势评估技术的移动机器人局部路径规划[J]. 计算机科学, 2019, 46(4): 210-215.
[4] 刘沛丰,王坚. 一种基于抗差EKF的移动机器人定位技术[J]. 计算机科学, 2017, 44(Z6): 115-118.
[5] 刘洁,赵海芳,周德廉. 一种改进量子行为粒子群优化算法的移动机器人路径规划[J]. 计算机科学, 2017, 44(Z11): 123-128.
[6] 徐腾飞,罗 琦,王 海. 基于向量场的移动机器人动态路径规划[J]. 计算机科学, 2015, 42(5): 237-244.
[7] 汤一平,胡大卫,蔡盈梅,黄珂,姜荣剑. 基于全景视觉的移动机器人的运动目标检测[J]. 计算机科学, 2015, 42(11): 314-319.
[8] 张贺,刘国良,李南君,侯紫峰. 基于子图分割和自适应噪音方差的2D移动机器人定位方法[J]. 计算机科学, 2014, 41(10): 23-26.
[9] 陈晋音,杨东勇,邹青华. AS-R移动机器人的动态避障与路径规划研究[J]. 计算机科学, 2012, 39(3): 223-227.
[10] 陈 昊,孙 辉,许 畅,马晓星. 一种支持自适应程序设计的移动机器人中间件[J]. 计算机科学, 2012, 39(10): 119-124.
[11] 庄佳园,万磊,廖煌雷,孙寒冰. 基于电子海图的水面无人艇全局路径规划研究[J]. 计算机科学, 2011, 38(9): 211-214.
[12] 廖卓凡,王建新,梁俊斌. 无线传感器网络中节点的动态部署[J]. 计算机科学, 2011, 38(10): 45-50.
[13] 魏唯,欧阳丹彤,吕帅. 一种实时多目标路径规划方法[J]. 计算机科学, 2010, 37(7): 236-239269.
[14] 周菁,戴冠中,蔡晓妍. 基于蚁群系统的机器人全局最优路径规划的研究与仿真[J]. 计算机科学, 2010, 37(5): 171-174.
[15] 杨锦园,黄心汉,李鹏. 基于DSmT的移动机器人地图构建及传感器管理[J]. 计算机科学, 2010, 37(4): 227-.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[2] 郑秀林,宋海燕,付伊鹏. MORUS-1280-128算法的区分分析[J]. 计算机科学, 2018, 45(4): 152 -156 .
[3] 丁舒阳,黎冰,侍洪波. 基于改进的离散PSO算法的FJSP的研究[J]. 计算机科学, 2018, 45(4): 233 -239 .
[4] 童泽平,李涛,李立杰,任亮. 基于随机需求与产能限制的供应链协同优化研究[J]. 计算机科学, 2018, 45(4): 260 -265 .
[5] 崔建京,龙军,闵尔学,于洋,殷建平. 同态加密在加密机器学习中的应用研究综述[J]. 计算机科学, 2018, 45(4): 46 -52 .
[6] 李珊,饶文碧. 基于视频的矿井中人体运动区域检测[J]. 计算机科学, 2018, 45(4): 291 -295 .
[7] 戴文静, 袁家斌. 隐含子群问题的研究现状[J]. 计算机科学, 2018, 45(6): 1 -8 .
[8] 杨沛安, 武杨, 苏莉娅, 刘宝旭. 网络空间威胁情报共享技术综述[J]. 计算机科学, 2018, 45(6): 9 -18 .
[9] 刘景玮, 刘京菊, 陆余良, 杨斌, 朱凯龙. 基于网络攻防博弈模型的最优防御策略选取方法[J]. 计算机科学, 2018, 45(6): 117 -123 .
[10] 徐健锋, 何宇凡, 刘斓. 三支决策代价目标函数的关系及推理研究[J]. 计算机科学, 2018, 45(6): 176 -182 .