机器人导航的路径规划算法研究综述

doi:10.3778/j.issn.1002-8331.2301-0088

摘要/Abstract

摘要： 路径规划算法是机器人导航的关键技术之一，优良的路径规划算法能够快速找出最佳无碰撞行走路径，提高运行效率。大多数现有的分类方法难以表述清楚算法间的区别与联系，根据机器人路径规划算法的设计原理，将其分为基于图搜索、基于仿生、基于势场、基于速度空间和基于采样的规划算法以更清晰地区分不同的路径规划算法。阐述了每类算法的概念、特点和发展现状，并从单查询算法和多查询算法的角度重点分析了应用更为广泛的基于采样的算法，对比总结了不同类型路径规划算法的优缺点，从多机器人协作、多算法融合和自适应规划等方面展望了机器人路径规划算法的未来发展趋势。

关键词: 机器人, 路径规划, 启发式算法, 避障算法, 采样算法

Abstract: Path planning is one of the key technologies for robot navigation. An excellent path planning algorithm can quickly find the best collision-free path and improve operational efficiency. Most existing classification methods have difficulty in expressing the differences and connections between algorithms. To distinguish different path planning algorithms more clearly, they are divided into graph-based search, bionic-based, potential field-based, velocity space-based and sampling-based algorithms based on their principle and nature. This paper introduces the concept, characteristics, and development status of each type of algorithm, analyzes the more widely used sample-based algorithms from the perspective of single-query and multi-query algorithms, and the advantages and problems of different types of path planning algorithms are compared and summarized. Finally, the future development trend of robot path planning algorithms in terms of multi-robot collaboration, multi-algorithm fusion and adaptive planning is prospected.

Key words: robot, path planning, heuristic algorithms, obstacle avoidance algorithms, sampling-based algorithms

崔炜, 朱发证. 机器人导航的路径规划算法研究综述[J]. 计算机工程与应用, 2023, 59(19): 10-20.

CUI Wei, ZHU Fazheng. Review of Path Planning Algorithms for Robot Navigation[J]. Computer Engineering and Applications, 2023, 59(19): 10-20.

参考文献

[1] WANG K，XU J，SONG K，et al.Informed anytime Bi-directional fast marching tree for optimal motion planning in complex cluttered environments[J].Expert Systems with Applications，2023，215：119263.
[2] TOUZANI H，HADJ-ABDELKADER H，SéGUY N，et al.Multi-robot task sequencing & automatic path planning for cycle time optimization：application for car production line[J].IEEE Robotics and Automation Letters，2021，6（2）：1335-1342.
[3] SUH J，GONG J，OH S.Fast sampling-based cost-aware path planning with nonmyopic extensions using cross entropy[J].IEEE Transactions on Robotics，2017，33（6）：1313-1326.
[4] ZHANG Z，WU L，ZHANG W，et al.Energy-efficient path planning for a single-load automated guided vehicle in a manufacturing workshop[J].Computers & Industrial Engineering，2021，158：107397.
[5] PHUNG M D，HA Q P.Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization[J].Applied Soft Computing，2021，107：107376.
[6] 林韩熙，向丹，欧阳剑，等.移动机器人路径规划算法的研究综述[J].计算机工程与应用，2021，57（18）：38-48.
LIN H X，XIANG D，OUYANG J，et al.Review of path planning algorithms for mobile robots[J].Computer Engineering and Applications，2021，57（18）：38-48.
[7] GONZALEZ D，PEREZ J，MILANES V，et al.A review of motion planning techniques for automated vehicles[J].IEEE Transactions on Intelligent Transportation Systems，2016，17（4）：1135-1145.
[8] GAMMELL J D，BARFOOT T D，SRINIVASA S S.Batch Informed Trees（BIT*）：informed asymptotically optimal anytime search[J].The International Journal of Robotics Research，2020，39（5）：543-567.
[9] 王梓强，胡晓光，李晓筱，等.移动机器人全局路径规划算法综述[J].计算机科学，2021，48（10）：19-29.
WANG X Q，HU X G，LI X X，et al.Overview of global path planning algorithms for mobile robots[J].Computer Science，2021，48（10）：19-29.
[10] DIJKSTRA E W.A note on two problems in connexion with graphs[J].Numerische Mathematik，1959，1（1）：269-271.
[11] 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（T-SSC），1968，4（2）：100-107.
[12] LI C，HUANG X，DING J，et al.Global path planning based on a bidirectional alternating search A* algorithm for mobile robots[J].Computers & Industrial Engineering，2022，168：108123.
[13] LIKHACHEV M，GORDON G，THRUN S.ARA*：anytime A* with provable bounds on sub-optimality[C]// Advances in Neural Information Processing Systems，2003.
[14] STENTZ A.Optimal and efficient path planning for partially-known environments[C]//Proccedings of the IEEE International Conference on Robotics and Automation，1994：3310-3317.
[15] KOENIG S，LIKHACHEV M，FURCY D.Lifelong planning A*[J].Artificial Intelligence，2004，155（1/2）：93-146.
[16] KOENIG S，LIKHACHEV M.D* lite[C]//Proccedings of the Eighteenth National Conference on Artificial Intelligence，2002：476-483.
[17] LIKHACHEV M，FERGUSON D I，GORDON G J，et al.Anytime dynamic A*：an anytime，replanning algorithm[C]//Proccedings of the Fifteenth International Conference on Automated Planning and Scheduling（ICAPS），2005：262-271.
[18] HOLLAND，JOHN H.Outline for a logical theory of adaptive systems[J].Journal of the ACM，1962，9（3）：297-314.
[19] 徐力，刘云华，王启富.自适应遗传算法在机器人路径规划的应用[J].计算机工程与应用，2020，56（18）：36-41.
   XU L，LIU Y H，WANG Q F.Application of adaptive genetic algorithm in robot path planning[J].Computer Engineering and Applications，2020，56（18）：36-41.
[20] PEHLIVANOGLU Y V，PEHLIVANOGLU P.An enhanced genetic algorithm for path planning of autonomous UAV in target coverage problems[J].Applied Soft Computing，2021，112：107796.
[21] HAO K，ZHAO J，WANG B，et al.The application of an adaptive genetic algorithm based on collision detection in path planning of mobile robots[J].Computational Intelligence and Neuroscience，2021（5）：1-20.
[22] DORIGO M，MANIEZZO V，COLORNI A.The ant system：an autocatalytic optimizing process：Technical Report 91-016[R].1991.
[23] LUO Q，WANG H，ZHENG Y，et al.Research on path planning of mobile robot based on improved ant colony algorithm[J].Neural Computing and Applications，2020，32（6）：1555-1566.
[24] MIAO C，CHEN G，YAN C，et al.Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm[J].Computers & Industrial Engineering，2021，156：107230.
[25] LIU J，ANAVATTI S，GARRATT M，et al.Modified continuous ant colony optimisation for multiple unmanned ground vehicle path planning[J].Expert Systems with Applications，2022，196：116605.
[26] KENNEDY J，EBERHART R.Particle swarm optimization[C]//Proccedings of the International Conference on Neural Networks，1995：1942-1948.
[27] 杨旭，王锐，张涛.面向无人机集群路径规划的智能优化算法综述[J].控制理论与应用，2020，37（11）：2291-302.
YANG X，WANG R，ZHANG T.Review of unmanned aerial vehicle swarm path planning based on intelligent optimization[J].Control Theory & Applications，2020，37（11）：2291-2302.
[28] YU Z，SI Z，LI X，et al.A novel hybrid particle swarm optimization algorithm for path planning of UAVs[J].IEEE Internet of Things Journal，2022，9（22）：22547-22558.
[29] FERNANDES P B，OLIVEIRA R，NETO J F.Trajectory planning of autonomous mobile robots applying a particle swarm optimization algorithm with peaks of diversity[J].Applied Soft Computing，2022，116：108108.
[30] YANG X S.Nature-inspired metaheuristic algorithms[M].UK：Luniver Press，2010.
[31] KUMAR V，KUMAR D.A systematic review on firefly algorithm：past，present，and future[J].Archives of Computational Methods in Engineering，2021，28（4）：3269-3291.
[32] LI J，WEI X，LI B，et al.A survey on firefly algorithms[J].Neurocomputing，2022，500：662-678.
[33] PATLE B，PANDEY A，JAGADEESH A，et al.Path planning in uncertain environment by using firefly algorithm[J].Defence Technology，2018，14（6）：691-701.
[34] XU G，ZHANG T W，LAI Q，et al.A new path planning method of mobile robot based on adaptive dynamic firefly algorithm[J].Modern Physics Letters B，2020，34：2050322.
[35] LI F，FAN X，HOU Z.A firefly algorithm with self-adaptive population size for global path planning of mobile robot[J].IEEE Access，2020，8：168951-168964.
[36] ZHANG T W，XU G H，ZHAN X S，et al.A new hybrid algorithm for path planning of mobile robot[J].The Journal of Supercomputing，2022，78（3）：4158-4181.
[37] MIRJALILI S，MIRJALILI S M，LEWIS A.Grey wolf optimizer[J].Advances in Engineering Software，2014，69：46-61.
[38] MIRJALILI S，SAREMI S，MIRJALILI S M，et al.Multi-objective grey wolf optimizer：a novel algorithm for multi-criterion optimization[J].Expert Systems with Applications，2016，47：106-119.
[39] GUPTA S，DEEP K.A novel random walk grey wolf optimizer[J].Swarm and evolutionary Computation，2019，44：101-112.
[40] NADIMI-SHAHRAKI M H，TAGHIAN S，MIRJALILI S.An improved grey wolf optimizer for solving engineering problems[J].Expert Systems with Applications，2021，166：113917.
[41] FARAMARZI A，HEIDARINEJAD M，MIRJALILI S，et al.Marine predators algorithm：a nature-inspired metaheuristic[J].Expert Systems with Applications，2020，152：113377.
[42] SHABANI A，ASGARIAN B，SALIDO M，et al.Search and rescue optimization algorithm：a new optimization method for solving constrained engineering optimization problems[J].Expert Systems with Applications，2020，161：113698.
[43] 张贝，闵华松，张新明.改进海洋捕食者算法和插值平滑的机器人路径规划[J].计算机应用研究，2023（7）：2082-2089.
   ZHANG B，MIN H S，ZHANG X M.Robot path planning based on improved marine predators algorithm and interpolation smoothing[J].Application Research of Computers，2023（7）：2082-2089.
[44] 周文娟，张超群，汤卫东，等.一种新的基于强化学习改进SAR的无人机路径规划[J/OL].控制与决策（2023-02-07）[2023-03-18].https：//doi.org/10.13195/j.kzyjc.2022.1209.
   ZHOU W J，ZHANG C Q，TANG W D，et al.A novel modified search and rescue optimization algorithm based on reinforcement learning for UAV path planning[J/OL].Control and Decision（2023-02-07）[2023-03-18].https：//doi.org/10.13195/j.kzyjc.2022.1209.
[45] ZHANG C，ZHOU W，QIN W，et al.A novel UAV path planning approach：Heuristic crossing search and rescue optimization algorithm[J].Expert Systems with Applications，2023，215：119243.
[46] AKBARI M A，ZARE M，AZIZIPANAH-ABARGHOOEE R，et al.The cheetah optimizer：a nature-inspired metaheuristic algorithm for large-scale optimization problems[J].Scientific Reports，2022，12（1）：10953.
[47] 郭启程，杜晓玉，张延宇，等.基于改进鲸鱼算法的无人机三维路径规划[J].计算机科学，2021，48（12）：304-311.
   GUO Q C，DU X Y，ZHANG Y Y，et al.Three-dimensional path planning of UAV based on improved whale optimization algorithm[J].Computer Science，2021，48（12）：304-311.
[48] 李丹.改进群智能优化算法的海上物流配送路径优化方法[J].舰船科学技术，2020，42（16）：184-186.
   LI D.Optimization method of marine logistics distribution path based on improved swarm intelligence optimization algorithm[J].Ship Science and Technology，2020，42（16）：184-186.
[49] 李珺，段钰蓉，郝丽艳，等.混合优化算法求解同时送取货车辆路径问题[J].计算机科学与探索，2022，16（7）：1623-1632.
   LI J，DUAN Y R，HAO L Y，et al.Hybrid optimization algorithm for vehicle routing problem with simultaneous delivery-pickup[J].Journal of Frontiers of Computer Science and Technology，2022，16（7）：1623-1632.
[50] MOHANAN M，SALGOANKAR A.A survey of robotic motion planning in dynamic environments[J].Robotics and Autonomous Systems，2018，100：171-185.
[51] KHATIB O.Real-time obstacle avoidance for manipulators and mobile robots[J].The International Journal of Robotics Research，1986，5（1）：90-98.
[52] DUHE J F，VICTOR S，MELCHIOR P.Contributions on artificial potential field method for effective obstacle avoidance[J].Fractional Calculus and Applied Analysis，2021，24（2）：421-446.
[53] TIAN Y，ZHU X，MENG D，et al.An overall configuration planning method of continuum hyper-redundant manipulators based on improved artificial potential field method[J].IEEE Robotics and Automation Letters，2021，6（3）：4867-4874.
[54] SANG H，YOU Y，SUN X，et al.The hybrid path planning algorithm based on improved A* and artificial potential field for unmanned surface vehicle formations[J].Ocean Engineering，2021，223：108709.
[55] SOUZA R M J A，LIMA G V，MORAIS A S，et al.Modified artificial potential field for the path planning of aircraft swarms in three-dimensional environments[J].Sensors，2022，22（4）：1558.
[56] KASHYAP A K，PARHI D R，MUNI M K，et al.A hybrid technique for path planning of humanoid robot NAO in static and dynamic terrains[J].Applied Soft Computing，2020，96：106581.
[57] FOX D，BURGARD W，THRUN S.The dynamic window approach to collision avoidance[J].IEEE Robotics & Automation Magazine，1997，4（1）：23-33.
[58] JIN Q B，TANG C N，CAI W.Research on dynamic path planning based on the fusion algorithm of improved ant colony optimization and rolling window method[J].IEEE Access，2022，10：28322-28332.
[59] OGREN P，LEONARD N E.A convergent dynamic window approach to obstacle avoidance[J].IEEE Transactions on Robotics，2005，21（2）：188-195.
[60] LEE D H，LEE S S，AHN C K，et al.Finite distribution estimation-based dynamic window approach to reliable obstacle avoidance of mobile robot[J].IEEE Transactions on Industrial Electronics，2021，68（10）：9998-10006.
[61] MOLINOS E J，LLAMAZARES á，OCA?A M.Dynamic window based approaches for avoiding obstacles in moving[J].Robotics and Autonomous Systems，2019，118：112-130.
[62] CHANG L，SHAN L，JIANG C，et al.Reinforcement based mobile robot path planning with improved dynamic window approach in unknown environment[J].Autonomous Robots，2021，45（1）：51-76.
[63] WANG X，MA X，LI X，et al.Target-biased informed trees：sampling-based method for optimal motion planning in complex environments[J].Journal of Computational Design and Engineering，2022，9（2）：755-771.
[64] LAVALLE S M，KUFFNER J J.Randomized kinodynamic planning[J].The International Journal of Robotics Research，2001，20（5）：378-400.
[65] KARAMAN S，FRAZZOLI E.Sampling-based algorithms for optimal motion planning[J].The International Journal of Robotics Research，2011，30（7）：846-894.
[66] JANSON L，SCHMERLING E，CLARK A，et al.Fast marching tree：a fast marching sampling-based method for optimal motion planning in many dimensions[J].The International Journal of Robotics Research，2015，34（7）：883-921.
[67] GAMMELL J D，SRINIVASA S S，BARFOOT T D.Batch informed trees（BIT*）：sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs[C]//Proceedings of the IEEE International Conference on Robotics and Automation，2015：3067-3074.
[68] WANG J K，MENG M Q H，KHATIB O.EB-RRT：optimal motion planning for mobile robots[J].IEEE Transactions on Automation Science and Engineering，2020，17（4）：2063-2073.
[69] CHI W Z，DING Z Y，WANG J K，et al.A generalized voronoi diagram-based efficient heuristic path planning method for rrts in mobile robots[J].IEEE Transactions on Industrial Electronics，2022，69（5）：4926-4937.
[70] 曹凯，陈阳泉，高嵩，等.涡流人工势场引导下的RRT*移动机器人路径规划[J].计算机科学与探索，2021，15（4）：723-732.
CAO K，CHEN Y Q，GAO S，et al.Vortex artificial-potential-field guided RRT* for path planning of mobile robot[J].Journal of Frontiers of Computer Science and Technology，2021，15（4）：723-732.
[71] ARSLAN O，TSIOTRAS P.Dynamic programming guided exploration for sampling-based motion planning algorithms[C]//Proceedings of the IEEE International Conference on Robotics and Automation（ICRA），2015：4819-4826.
[72] OTTE M，FRAZZOLI E.RRTX：asymptotically optimal single-query sampling-based motion planning with quick replanning[J].The International Journal of Robotics Research，2016，35（7）：797-822.
[73] LIAO B，WAN F Y，HUA Y，et al.F-RRT*：an improved path planning algorithm with improved initial solution and convergence rate[J].Expert Systems with Applications，2021，184：115457.
[74] KUFFNER J J，LAVALLE S M.RRT-connect：an efficient approach to single-query path planning[C]//Proceedings of the IEEE International Conference on Robotics and Automation Symposia Proceedings（Cat No00CH37065），2000：995-1001.
[75] WANG J K，CHI W Z，LI C M，et al.Efficient robot motion planning using bidirectional-unidirectional rrt extend function[J].IEEE Transactions on Automation Science and Engineering，2021，19（3）：1859-1868.
[76] GAMMELL J D，SRINIVASA S S，BARFOOT T D.Informed RRT*：optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]//Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems，2014：2997-3004.
[77] ZHONG C，LIU H.A region-specific hybrid sampling method for optimal path planning[J].International Journal of Advanced Robotic Systems，2016，13（2）：71.
[78] SALZMAN O，HALPERIN D.Asymptotically-optimal motion planning using lower bounds on cost[C]//Proceedings of the IEEE International Conference on Robotics and Automation（ICRA），2015：4167-4172.
[79] STAREK J，SCHMERLING E，JANSON L，et al.Bidirectional fast marching trees：an optimal sampling-based algorithm for bidirectional motion planning[C]//Proceedings of the Workshop on Algorithmic Foundations of Robotics，2015.
[80] REID W，FITCH R，G?KTO?AN A H，et al.Sampling-based hierarchical motion planning for a reconfigurable wheel-on-leg planetary analogue exploration rover[J].Journal of Field Robotics，2020，37（5）：786-811.
[81] XU J，SONG K，DONG H，et al.A batch informed sampling-based algorithm for fast anytime asymptotically-optimal motion planning in cluttered environments[J].Expert Systems with Applications，2020，144：113124.
[82] XU J，SONG K，ZHANG D，et al.Informed anytime fast marching tree for asymptotically optimal motion planning[J].IEEE Transactions on Industrial Electronics，2021，68（6）：5068-5077.
[83] WU Z，CHEN Y，LIANG J，et al.ST-FMT*：a fast optimal global motion planning for mobile robot[J].IEEE Transactions on Industrial Electronics，2022，69（4）：3854-3864.
[84] PENROSE M.Random geometric graphs[M].Oxford：Oxford University Press，2003.
[85] AINE S，LIKHACHEV M.Truncated incremental search[J].Artificial Intelligence，2016，234：49-77.
[86] HOLSTON A C，KIM D H，KIM J H.Fast-BIT：modified heuristic for sampling-based optimal planning with a faster first solution and convergence in implicit random geometric graphs[C]//Proceedings of the IEEE International Conference on Robotics and Biomimetics（ROBIO），2017：1892-1899.
[87] STRUB M P，GAMMELL J D.Advanced BIT（ABIT）：sampling-based planning with advanced graph-search techniques[C]//Proceedings of the IEEE International Conference on Robotics and Automation（ICRA），2020：130-136.
[88] KYAW P T，ANH VU L，VEERAJAGADHESWAR P，et al.Energy-efficient path planning of reconfigurable robots in complex environments[J].IEEE Transactions on Robotics，2022：2481-2494.
[89] STRUB M P，GAMMELL J D.Adaptively informed trees（AIT*）：fast asymptotically optimal path planning through adaptive heuristics[C]//Proceedings of the IEEE International Conference on Robotics and Automation（ICRA），2020：3191-3198.
[90] STRUB M P，GAMMELL J D.AIT* and EIT*：asymmetric bidirectional sampling-based path planning[J].arXiv：2111.01877，2021.
[91] HARTMANN V N，M.P.STRUB M T，GAMMELL J D.Effort informed roadmaps（EIRM*）：efficient asymptotically optimal multiquery planning by actively reusing validation effort[C]//Proceedings of the International Symposium on Robotics Research（ISRR），2022：555-571.
[92] KAVRAKI L E，SVESTKA P，LATOMBE J C，et al.Probabilistic roadmaps for path planning in high-dimensional configuration spaces[J].IEEE Transactions on Robotics and Automation，1996，12（4）：566-580.
[93] BOHLIN R，KAVRAKI L E.Path planning using lazy PRM[C]//Proceedings of the IEEE International Conference on Robotics and Automation（ICRA），2000：521-528.
[94] HAUSER K.Lazy collision checking in asymptotically-optimal motion planning[C]//Proceedings of the IEEE International Conference on Robotics and Automation（ICRA），2015：2951-2957.
[95] DOBSON A，BEKRIS K E.Sparse roadmap spanners for asymptotically near-optimal motion planning[J].The International Journal of Robotics Research，2014，33（1）：18-47.
[96] LAI T，RAMOS F，FRANCIS G.Balancing global exploration and local-connectivity exploitation with rapidly-exploring random disjointed-trees[C]//Proceedings of the IEEE International Conference on Robotics and Automation（ICRA），2019：5537-5543.
[97] LAI T，MORERE P，RAMOS F，et al.Bayesian local sampling-based planning[J].IEEE Robotics and Automation Letters，2020，5（2）：1954-1961.