论移动机器人的智能路径规划算法综述

王承平

摘 要：移动机器人是现阶段科研工作的重点内容之一，并且受到社会各界人士的广泛关注。基于此，本文针对当前移动机器人的智能路径规划算法进行研究，但是移动机器人路径规划要从实际应用出发，所以很难从复杂的环境中寻找到一条最优化的路径，因此将移动机器人的常规算法进行总结分析，并阐述各种算法的优点及缺点，并提出计算机智能算法的应用路径规划的探究，希望能对移动机器人路径规划算法的科研人员提供思路。

关键词：移动机器人 路径规划 启发式搜索算法 强化学习算法

An Overview of Intelligent Path Planning Algorithms for Mobile Robots

Wang ChengPing

Abstract：Mobile robot is one of the key contents of scientific research at this stage， and has been widely concerned by people from all walks of life. Based on this， this paper studies the current intelligent path planning algorithm of mobile robot， but the path planning of mobile robot should start from the practical application， so it is difficult to find an optimal path from the complex environment. Therefore， the conventional algorithms of mobile robot are summarized and analyzed， and the advantages and disadvantages of various algorithms are described. The paper also puts forward the application of computer intelligent algorithm and the exploration of path planning， hoping to provide ideas for researchers of mobile robot path planning algorithm.

Key words：mobile robot， path planning， heuristic search algorithm， reinforcement learning algorithm

1 引文

移动机器人的路径规划主要指的是移动机器人在复杂的环境下找到一条无障碍路径。现阶段许多已知环境下的路径规划算法已经成熟，能实现无碰撞运行，但是在无知的环境中，移动机器人需要根据传感器来收集局部信息，进而运用相关算法实现路径规划，但是现阶段未知环境的路径规划算法依旧处于试验階段。而且近几年我国各大企业都在研究无人驾驶技术，而无人驾驶技术的人工智能算法也涉及路径规划，因此相关人员可以借鉴其技术，从而更好的推动移动机器人路径规划。

2 Dijkstra算法

2.1 Dijkstra基本原理

Dijkatra算法是一种图搜索算法，其由荷兰科学家Edsger wybe Dijk stra在1959年提出，主要为了解决赋权图最短路径问题，这种算法后来被改进应用在移动机器人上面，进而解决移动机器人路径规划问题。而且这种算法的基本原理是在某一个特定区域选取一点作为起始点，学术上称之为原点，在计算原点到区域某一点的所有路径，再将这些路径进行比较，进而选出最短的路径，如果中间添加其他阶段，需要计算原点到第一个节点的距离，第一个阶段到第二个阶段的距离，两个阶段的距离进行相加，如果距离更短将进行更新迭代，直到区域内所有路径全部完成。这种算法实现相对简单，复杂度相对低，在物流运输及外卖配送中应用较多。但是Dijkstra算法一直都是在选择区域内最短的路径，因此其有着很大的局限性[1]。此外，Dijkstra算法需要原点到节点的所有距离，这种算法会导致时间消耗较长，计算所占据的内存较大。

2.2 Dijkstra算法优化

Dijkstra算法有着很多的优势，但是也存在着明显的问题，即耗时长、算法占据存储空间大，因此提出相应优化方法，用来优化与解决相应的问题。第一，多节点并行优化方法，这种优化法与传统的Dijkstra算法相比有着明显的优势，他采用多节点同时进行路径规划，并采用多线程对不同的节点进行计算，在提高速度的同时还能保证多线程的安全性与精准性。经过相关的实验表明，多节点并行算法所用的时间要比传统的Dijkstra算法时间短，而且缩短的时间会随着原点区域面积的变大而变大，比较适合大范围的路径规划。第二，松弛Dijkstra优化算法，这种优化法的主要特点是将Dijkstra与A*算法进行结合，两者都是计算最短路径的常用算法，但是一种建立在抽象的图论层面，一种是建立在常用游戏地图的最短路径应用[2]。因此在建立建模后可以采用逆向搜索策略，计算节点到原点的距离，在开始时节点从常规的8个方向出发，进而选取最短的路径。在两个方向的路径距离相同时，按相同的概率选择其中任何一个展开。该方法能在障碍物密度较大的复杂环境下进行路径规划，但需进一步研究减小误差的方法，以获得最优解。Dijkstra算法的优化主要解决计算时间长、计算量大、回溯线程规划等问题，多节点并行优化方法能有效的提高计算效率，但是实际的计算量并没有变化，这种优化算法对复杂的大型地图有着明显的效果。第二种优化方法可以分层次进行规划，将规划空间层次、方向分别进行设定节点，最后整合所有的路径，可以追溯到每一层的扩展进度。

3 A*算法

3.1 A*算法基本原理

A*算法由Hart PE、NILsson、Raphael B在1968年提出的，算法的基本原理是在Dijkstra算法的基础上引入函数公式F（n）=G+H，进而形成A*算法，而且当H（n）为0时，A*算法即为Dijkstra算法。其次，在使用A*算法进行路径规划前需要了解A*算法涉及的相关概念，其中包括搜索区域、开放列表、父节点、路径排序、启发函数[3]。搜索区域指的是将简单的区域图分成二维数组，在二维数组中每个元素对应相关的小区域，这些小区域能组成不同形状的大区域，将一个单位数组的中心点称之为区域节点。开放列表（Open List）指的是在路径规划过程中，我们把要检测的节点放到开放列表中，同时将被检测到的节点存储到关闭列表中。父节点（parent）指的是在路径规划中能用来回溯的节点，在开发时可以考虑使用双向链表结构中的父节点指针，进而方便节点的回溯。路径排序（Path Sorting）指的是原点具体向那个节点移动由函数公式F（n）=G+H来确定，G表示原点生成路径到目标节点的移动，H制定估计的待测网络移动端到节点的移动。启发函数（Heuristics Function）指的是路径试探，也称为启发函数H，只要功能是在未知区域内寻找唯一的路径，所以在使用计算启发函数时要取决于实际场景[4]。在实验模型中，H采用传统的曼哈顿距离（Manhattan Distance），即原点到节点横向和纵向行走的距离之和。因此，A*算法在处理最短路径规划问题上效果显著，其函数公式能在一定程度上避免全图节点搜索，进而提高算法的应用效率。但是其在搜索时会使用父节点来估算回溯路径，这样会造成生产路径平滑性差，一旦路径存在障碍物移动机器人将无法按照规划路径进行移动，而且在规划路径时相对复杂，导致计算量加大，计算存储空间占用率增加，从而降低算法效率。

3.2 A*算法优化

A*算法在实际应用中有着明显的优势，但是也存在计算量大、计算存储空间占用率大等问题，所以对A*算法进行优化，进而适应移动机器人路径规划需求。第一种，针对A*算法基础条件的启发算法进行优化，首先通过设定距离函数和静态权值，静态权值为原点到目标节点的矢量，而且还要将节点与目标点的距离、方向、角度进行统一化处理，再用相应的函数计算其对路径的影响。其次，改进邻域搜索矩阵，根据移动机器人的大小和未知地域地圖的分辨率进行调整，使移动机器人与未知区域障碍物保持一定的距离，避免机器人在移动时碰到障碍物。最后，采用贝塞尔曲线来增加路径的可行性[5]。第二种，针对搜索法的进行优化，将跳点搜索法应用在A*算法的节点搜索中，在扩展节点的过程中，筛选出某些特殊的节点当作跳点，再将两个跳点进行连接进而实现大范围的搜索，这样做法可以不用计算两个跳点之间的路径，所以在实际应用中不需要将每个节点都进行路径规划，从而极大的减少内存消耗。第三种，双向处理A*算法，这种算法采用并行模式，这种模式和Dijkstra多节点运行有部分相似，A*并行模式是从原点和终点同时进行独立搜索，两条路径在开放列表中都有着相同的节点，这表明两条路径已经在搜索地域相遇，进而判断路径规划完成，使得相同的路径在计算时所需要的时间更短。第四种，改进A*算法估算函数，将G和H设置不同的权重，当节点距离目标点远时，要增加权重，当节点距离目标点近时，降低权重，这样将方向与距离变差较大的节点排除，进而减少搜索的节点数量，减少计算内存的消耗。因此，对A*算法的优化主要包括：启发函数改进、节点扩展改进、搜索方法改进等，这些都能有效的解决A*算法在不同环境下的运算量过大与路径规划中存在的问题。而且这种改进使得搜索过程不再需要全图节点搜索，只需要在地域扩展时对目标方向的节点进行搜索，进而减少计算量。而且技术在计算量较大的情况下，搜索方式的优化也能保证路径规划的速度和质量。

4 强化学习算法在路径规划上的应用

强化学习的算法包括：Dyna算法、Sarsa算法、时间差算法TD、Q-Learning算法、Actor-Critic算法等，其中时间差TD算法是最早的强化学习算法，之后的Sarsa算法等都是在TD算法的基础上进行改进的，区别在于迭代动作函数Q（s，a）或状态值函数V（s）。时间算法与其演变的算法主要应用在已知环境中，但是Dyna算法是建立全新的环境模型来代替真实环境，从而对虚拟样本函数值进行迭代，进而实现强化学习。其次，现阶段强化学习算法中Actor-Critic算法具备记忆功能，其收敛质量得到保证，而且能提高收敛速度，是一种具备估计值函数和策略学习方法的算法。但是强化学习算法还处于发展阶段，收敛速度和状态是目前主要研究问题，而在收敛速度问题上面Q-Learning算法的具有良好的稳定性。此外，还可以采用策略与启发函数的优化对Sarsa算法进行改良，从而提高收敛速度。

5 结束语

综上所述，目前移动机器人路径规划算法的研究虽然取得一定的研究成果，但是普遍都存在一些问题和不足，其中Dijkstra算法适用于局部地区，A*算法存储量和计算量大等，这些问题虽然都进行优化，但是仍然存在很大的局限性，在未知环境中的路劲规划存在明显缺陷，因此最好结合最新的智脑和强化学习算法，从而满足移动机器人的路径规划，而且其具有自主发展能力，通过模仿和与环境的相互作用来进行行为和计划，并通过少量的样本学习，克服强化学习中资源浪费的缺点，使机器人具有发展能力，并不断提高其智能水平。

基金项目：江苏省科技厅高校自然科学面上项目“基于树莓派控制的安全巡防小车研究”（项目编号：20KJD520006）。

参考文献：

[1]万方，周风余，尹磊，等. 基于电势场法的移动机器人全局路径规划算法[J]. 机器人，2019， v.41（06）：48-56.

[2]黄鲁， 周非同. 基于路径优化D～*Lite算法的移动机器人路径规划[J]. 控制与决策， 2020， v.35（04）：112-119.

[3]江明， 王飞， 葛愿，等. 基于改进蚁群算法的移动机器人路径规划研究[J]. 仪器仪表学报， 2019， 040（002）：113-121.

[4]徐晓苏， 袁杰. 基于改进强化学习的移动机器人路径规划方法[J]. 中国惯性技术学报， 2019（3）.

[5]王洪斌， 郝策， 张平，等. 基于A～*算法和人工势场法的移动机器人路径规划[J]. 中国机械工程， 2019.