摘" 要：路径规划算法是移动机器人自主规划路径的关键，其性能的优劣决定了路径规划的质量，是当前移动机器人领域的一个研究热点。为系统了解移动机器人路径规划技术的研究现状，阐述了近年来国内外路径规划算法的使用和发展。依据移动机器人路径规划算法的智能程度，将其划分为传统非智规划算法、随机智能规划算法、仿生智能规划算法及人工智能规划算法。依据分类，介绍了各种算法近年来具有代表性的研究成果，对移动机器人路径规划算法的发展走向进行了展望，旨在帮助研究人员快速和全面了解该领域的发展动态。
关键词：移动机器人；路径规划；路径规划算法；综述
中图分类号：TP242" 文献标识码：A" 文章编号：2096-4706（2024）19-0184-05
Review of Path Planning Algorithms for Mobile Robots
LI Zhonglin1， LUO Shaoping1， JIA Yuting2
（1.Software Engineering Institute of Guangzhou， Guangzhou" 510990， China;
2.Guangdong Baiyun University， Guangzhou" 510450， China）
Abstract： Path planning algorithm is the key to autonomous path planning for mobile robots， and its performance determines the quality of path planning， which is a research hotspot in the field of mobile robots at present. In order to systematically understand the current research status of mobile robot path planning technology， the use and development of path planning algorithms at home and abroad in recent years are studied. Based on the intelligence degree of mobile robot path planning algorithms， they are classified into traditional non-intelligent planning algorithms， stochastic intelligent planning algorithms， bionic intelligent planning algorithms and Artificial Intelligent planning algorithms. Based on the classification， this paper introduces representative research results of various algorithms in recent years， and looks forward to the development direction of mobile robot path planning algorithms， aiming at helping researchers to quickly and comprehensively understand the development dynamics in this field.
Keywords： mobile robot; path planning; path planning algorithm; review
0" 引" 言
自20世纪中叶，Stanford研究院诞生出全球首个移动机器人Shakey后[1]，日本、欧洲等诸多国家与地区开始意识到移动机器人的重要性，纷纷开始布局并取得了发展。尤其是近年来，随着社会的不断发展及需求的增加，移动机器人在生产与生活等多领域中被广泛使用，甚至应用于抗震救灾等复杂环境中。移动机器人在自主执行任务时首要解决的问题是路径规划，路径规划的关键在于路径规划算法，其性能的优劣决定了路径规划的质量。面对具有复杂性和不确定性的工作环境，如何快速有效进行路径规划是一个技术难点[2-3]。高效的路径能提高移动机器人的工作效率，缩短任务路径，降低自身损耗，目前已成为国内外研究的热点问题[4]。
为了解移动机器人路径规划技术的研究现状，分析了近年来国内外路径规划算法的使用和发展。如图1所示，依据算法的智能程度将其划分为传统非智规划算法、随机智能规划算法、仿生智能规划算法及人工智能规划算法四类。依据分类，介绍了各种算法近年来具有代表性的研究成果，对未来移动机器人路径规划算法的发展趋势做出展望。
1" 传统非智规划算法
传统非智规划算法主要包括A*算法、Dijkstra算法、D*算法，该类算法依赖于环境的表达，使用该类算法需事先对环境进行准确建模。
1.1" Dijkstra算法
迪杰斯特拉算法（Dijkstra算法）是由Dijkstra于1956年首次提出[5]，被广泛应用于移动机器人的路径规划。算法通过迭代的方式以起始节点为中心向外寻找距离最近的节点，将其作为下一个节点，如图2所示，在每一次迭代结束后，更新起始节点与所有遍历的节点间的最短距离，最终获得所规划路径的最短距离。
Dijkstra算法因其实用性高、鲁棒性强被广泛使用，但因其无向的搜索特点，当搜索环境复杂时，搜索节点激增，计算量增大，算法效率降低，实时性差。为此，很多学者对其做出改进。董丽莎[6]为使规划路径更为准确合理，通过增加参照函数，用以评估无碰撞轨迹。左松涛等[7]为提高了算法适用范围，以综合评价代替最短路径，引入节点拥挤度，使最短路径规划转化为最优路径规划。
1.2" A*算法
A*算法是一种启发式搜索算法，于1972年由Hart等人提出[8]，被广泛应用于移动机器人的路径规划。算法以起始节点为中心向邻域节点扩展，以当前“代价”最低的节点作为下一个扩展节点进行遍历，从而完成路径规划。A*算法具有规划路线短，使用简单的优点，但易出现路径平滑度差、拐点多的问题。Li等[9]采用自适应调整步长算法和三次贝塞尔曲线优化A*算法，解决搜索路径中拐点多、拐角大、运行时间长等问题。贾明超等[10]采用更精确的搜索邻域选取策略，引入安全距离，采用一种自适应圆弧优化方法融合动态窗口法，改善了算法的搜索导向性、路径最优性及避障能力。
1.3" D*算法
D*算法由A*算法发展而来，由Stentz[11]于1994年提出，最初用于火星探测器的动态避障。D*算法能够在未知环境及动态的环境中实现路径动态规划，其原因在于：一是移动机器人在执行任务时如遇新的障碍，会把障碍信息更新至地图；二是算法具有可传递的启发函数，能将中心栅格的启发值传递至相邻节点。D*算法因源于A*算法，故存在路径曲折和平滑度低的问题，因其动态避障的特点，其对规划速度有较高的要求。Yu等[12]引入Dubins算法进行局部路径平滑处理，改进D*算法。秦旭等[13]优化了子节点的选取方式，改进代价估计函数，引入平滑度函数，解决了拐点多、效率低、路径安全度不高的问题。
2" 随机智能规划算法
随机智能搜索算法基于随机理论，无须环境模型，即可搜索最优路径并能实时调节，但规划路径不够平滑。两种常见的随机智能规划算法是概率路线图算法（Probabilistic Roadmaps， PRM）和快速探索随机树算法（Rapidly-exploring Random Tree， RRT）。
2.1" PRM算法
PRM算法是由Kavraki等[14]于1996年提出，其在寻找路径时需在构形空间通过碰撞检测确定相邻采样点是否可以连接，从而规划出有效路径。如图3所示，算法是一种基于图搜索的算法，能有效应对高维空间的路径规划，但当通道狭窄或障碍物密集时，算法效率降低，甚至无法求解。Mohanta等[15]提出了一种新的概率路线图模糊控制系统，提高算法规划效率，规划路径能够缩短了5%以上，拐点平滑度提高。薛光辉等[16]在构造阶段引入人工势场法，在查询阶段融合D*Lite算法，提高规划路径的可通过性和狭长封闭巷道规划成功率。
2.2" RRT算法
RRT算法是1998年由美国爱荷华州立大学Steven M. LaValle教授提出，可用于陌生环境的高维空间。RRT算法以生成随机扩展树的方式形成路径，初始节点是树的根节点，通过随机采样选择叶子节点，当选择的叶子节点包含目标节点时，即生成了一条有效的路径。算法效率高，但规划路径不最优及路径不够平滑。Wang等[17]给出了一种双向快速探索随机树KB-RRT*，保留了高效分支修剪策略和双向搜索的优势，生成了更短的路径。徐达等[18]采用目标偏置策略，引入概率值，利用变步长和样条曲线优化策略，改善盲目生成搜算节点、扩展无方向性和路径曲折不光滑等问题。
3" 仿生智能规划算法
仿生智能规划算法是人们通过研究仿生学而发现可用于路径规划的算法，常用算法包括蚁群算法（Ant Colony Optimization， ACO）和遗传算法（Genetic Algorithm， GA）等。
3.1" ACO算法
ACO算法是一种群智能算法，由意大利学者Dorigol于1992年提出。蚂蚁视觉并不发达，但总能在变化的环境中找到觅食的最短路径，其主要原因是蚂蚁会在经过的路径上释放信息素，一定范围的蚂蚁能够觉察。如图4所示，信息素越高的地方，经过的蚂蚁多，遗留的信息素变得更多，从而形成正反馈，而信息素最高的路径即为最短路径。
蚁群算法具有强的鲁棒性，但易陷入局部最优的陷阱。Gong等[19]为提高ACO算法的路径优化效果和搜索效率，引入终点和转折点，自适应调整信息素强度，避免了算法的盲目搜索，提高了搜索效率和避障能力。黄新林等[20]为提高家电回收效率以及降低回收成本，建立高斯概率矩阵，作用于个体基因突变，同等条件下，改进算法有效提高平均收敛速度，算法耗时明显降低。
3.2" GA算法
GA算法脱胎于遗传理论和进化理论，最早由美国的John holland于20世纪70年代提出[21]。如图5所示，算法模仿了生物的繁衍进化，通过选择、交叉、变异，逐代产生候选解，最终收敛于最优解。遗传算法具有自组织、自学习、并行、全局优化和稳健性等优点，被广泛应用于路径规划领域，但也存在不足，如算法容易出现早熟，局部搜索效率低下及收敛速度慢等。Wang等[22]设计双向交叉以增加搜索方向，设置双组变异并使用不同性质的变异算子，提高搜索效率。王雷等[23]在使用算法生成初始种群时采用一种基于终距概率的初始化方法，使用不依赖于交叉点的自由交叉算子和基于目标导向的变异算子，规划的路径质量更好，收敛速度更快。
4" 人工智能规划算法
人工智能规划算法采用人工智能算法使移动机器人在环境中自主学习，并预测出可行路径，以实现移动机器人自主规划出最优路径。
4.1" Q-learning算法
Q学习算法（Q-learning）是一种无模型的强化学习算法，如图6所示，广泛应用于人工智能和机器学习领域。近年来也被应用于移动机器人的路径规划，移动机器人通过与环境的交互来学习最优的移动策略，从而实现有效的路径规划和避障。
Tan等[24]使用强化学习方法引入了全局环境信息，在可到达路径点发生变化的位置使用Q-learning方法进行路径规划，优化了原始算法在这些障碍物附近的路径规划策略，以较低的路径重复率实现100%的覆盖率。牛奕龙等[25]采用时变动态贪婪策略，设置分段非线性奖惩函数，增加贝塞尔算法对路径作平滑处理，提高了算法的全局搜索能力和收敛速度，路径规划也更加平滑。
4.2" 深度学习
深度学习是含有多个隐含层的人工神经网络，属于机器学习的范畴。通过大量的样本训练使机器能够模仿视听和思考等人类的活动，解决了很多复杂的模式识别难题。有学者尝试将深度学习应用在移动机器人中。王凯等[26]提出基于深度学习的移动机器人全局路径控制方法，结合深度学习方法中的神经网络方法，构建机器人全局路径规划模型，利用模糊控制算法设计模糊控制器以纠正路径规划偏差，使得规划路径更短，收敛速度更快。喻凯旋等[27]针对目前基于深度强化的学习移动机器人路径规划中稀疏奖励导致的效率低、收敛慢等问题，提出一种梯度奖励政策。使用区域分割将环境分割为多区域并使奖励动态变化，结果表明所提算法搜索成功率提高，鲁棒性增加。
5" 分析比较
本文依据路径规划算法的智能程度将其划分为四类，各类算法机理不同但又各具特点，各自有其优势但也局限性，如表1所示。传统非智规划算法具有极强的环境依赖性，在使用时需对事先环境准确建模。算法相对简单，规划速度快，但当环境复杂时，其规划效率低，规划效果差，路径拐点多且规划时间长。随机智能规划算法相较于前者对环境依赖性弱，适用于高维空间，如起伏路面或山地等三维环境，算法的智能程度和适应性显著提升。仿生智能规划算法具有明显的生物智能特征，具备较强的环境适应性，但其易早熟且不易验证，因此规划路径具有不确定性。人工智能规划算法是移动机器人路径规划算法发展的新方向，其源自人工智能技术，具备甚至可能超出人类的智能，规划效果好，但对于数据和算力依赖性强，实时性差，适用于全局路径规划，局部避障能力弱。尽管其发展历程短，但有赖于强大的人工智能技术，具有发展潜力。在使用中应尝试将更多的人工智能技术应用于路径规划领域，同时注意扬其长补其短，在发挥其在路径全局规划优势的同时将算法轻量化或与其他算法相融合，弥补其在实时性差和局部避障能力弱的短板。
6" 结" 论
本文从算法的智能角度出发，将移动机器人路径规划算法划分为传统非智规划算法、随机智能规划算法、仿生智能规划算法、人工智能规划算法，根据近几年路径规划算法的发展情况，做如下总结和展望：
1）智能化程度更高。移动机器人路径规划算法的发展由完全依赖于环境模型的传统非智规划算法，到无须依赖环境模型的随机智能规划算法，到融合生物智能的仿生智能规划算法，直至具备人工智能的人工智能规划算法，智能化程度逐步升高，未来将与人工智能技术联系更为紧密。
2）改进更为多样。算法改进方式有从算法自身出发，改进算法组成中的一部分或多部分；也有从融合角度出发，将其他优秀的算法模块融入原算法中，形成混合算法，改进的方式多样，改进后算法相比较原算法性能显著提升。
3）算法更为丰富。规划算法由最初的A*算法、Dijkstra算法、D*算法等传统非智规划算法，到概率路线图算法和快速探索随机树算法等随机智能规划算法，再到ACO算法、GA算法等仿生智能规划算法，最后到Q-learning和深度学习等人工智能规划算法。算法的类别多，可用算法更丰富。
参考文献：
[1] 李磊，叶涛，谭民，等.移动机器人技术研究现状与未来 [J].机器人，2002（5）：475-480.
[2] CONTRERAS-CRUZ M A，AYALA RAMIREZ V，HERNANDEZ-BELMONTE U H. Mobile Robot Path Planning Using Artificial Bee Colony and Evolutionary Programming [J].Applied Soft Computing，2015，30：319-328.
[3] AJEIL F H，IBRAHEEM I K，AZAR A T，et al. Grid-Based Mobile Robot Path Planning Using Aging-based Ant Colony Optimization Algorithm in Static and Dynamic Environments [J].Sensors，2020，20（7）：1880.
[4] ZHANG H Y，LIN W M，CHEN A X. Path Planning for the Mobile Robot： A Review [J].Symmetry （Basel），2018，10（10）：450.
[5] DIJKSTRA E W. A Note on Two Problems in Connexion with Graphs [J].Numerische Mathematik，1959，1：269-271.
[6] 董丽莎.基于改进Dijkstra算法的轮式移动机械臂无碰撞轨迹研究 [J].制造业自动化，2022，44（8）：66-69.
[7] 左松涛，毛占利，范传刚，等.基于地铁站场景的改进型Dijkstra算法疏散路径规划研究 [J].铁道科学与工程学报，2023，20（5）：1624-1635.
[8] 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，1968，4（2）：100-107.
[9] LI Y G，JIN R C，XU X R，et al. A Mobile Robot Path Planning Algorithm Based on Improved A* Algorithm and Dynamic Window Approach [J].IEEE Access，2022（10）：57736-57747.
[10] 贾明超，冯斌，吴鹏，等.一种融合改进A*算法与改进动态窗口法的文旅服务机器人路径规划 [J].图学学报，2024，45（3）：505-515.
[11] STENTZ A. Optimal and Efficient Path Planning for Partially Known Environments [C]//Proceedings of the 1994 IEEE International Conference on Robotics and Automation.Diego：IEEE，1994：3310-3317.
[12] YU J B，YANG M，ZHAO Z Y，et al. Path Planning of Unmanned Surface Vessel in an Unknown Environment Based on Improved D*Lite Algorithm [J].Ocean Engineering，2022，266：112873.
[13] 秦旭，黄晓华，马东明，等.基于改进D*算法的巡检机器人路径规划 [J].组合机床与自动化加工技术，2022（6）：10-13.
[14] 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.
[15] MOHANTA J C，KESHARI A. A Knowledge Based Fuzzy Probabilistic Roadmap Method for Mobile Robot Navigation [J].Applied Soft Computing，2019，79：391-409.
[16] 薛光辉，刘爽，王梓杰，等.基于改进概率路线图算法的煤矿机器人路径规划方法 [J].工矿自动化，2023，49（6）：175-181.
[17] WANG J K，LI B P，MENG M Q H. Kinematic Constrained Bi-directional RRT with Efficient Branch Pruning for robot path planning [J].Expert Systems with Applications，2021，170：114541.
[18] 徐达，王兆阳，李华，等.基于改进RRT算法的弹药装填机器人路径规划 [J].兵工自动化，2023，42（11）：93-96.
[19] GONG C K，YANG Y H，YUAN L P，et al. An Improved Ant Colony Algorithm for Integrating Global Path Planning and Local Obstacle Avoidance for Mobile Robot in Dynamic Environment [J].Mathematical Biosciences and Engineering，2022，19（12）：12405-12426.
[20] 黄新林，张隆飞，唐小伟.基于改进遗传算法的家电回收车辆路径规划方法 [J].同济大学学报：自然科学版，2024，52（1）：27-34.
[21] GOLDBERG D E. Genetic algorithm in search， optimization， and machine learning [M].Boston：Addison Wesley， 1989： 36.
[22] WANG F L，XU G，WANG M. An Improved Genetic Algorithm for Constrained Optimization Problems [J].IEEE Access，2023，11：10032-10044.
[23] 王雷，王艺璇，李东东，等.基于改进遗传算法的移动机器人路径规划研究 [J].华中科技大学学报：自然科学版，2024，52（5）：158-164.
[24] TAN X Q，HAN L H，GONG H，et al. Biologically Inspired Complete Coverage Path Planning Algorithm Based on Q-Learning [J].Sensors.2023，23（10）：4647.
[25] 牛奕龙，杨仪，张凯，等.基于改进DQN算法的应召搜潜无人水面艇路径规划方法 [J].兵工学报，2024，45（9）：3204-3215.
[26] 王凯，朱慧珍，王丽君.深度学习理论下移动机器人全局路径规划方法 [J].计算机仿真，2023，40（10）：431-434+439.
[27] 喻凯旋，林富生，宋志峰，等.基于梯度奖励的深度强化学习移动机器人路径规划 [J].机床与液压，2023，51（17）：32-38.
作者简介：李忠林（1990—），男，汉族，江苏连云港人，助教，硕士研究生，研究方向：智能控制与算法。
基金项目：广州软件学院2022年度校级科研项目（ky202203）
