文｜陈浩1、王光林2、郝询1
1为机科发展科技股份有限公司
2为英轩重工有限公司
移动机器人技术是近年来的研究热点，在工业、农业、医疗等行业广泛应用。路径规划技术作为自主移动机器人技术研究中的一个核心内容，是要实现移动机器人在未知环境下自主路径规划决策，具备实时、自主并识别高风险区域的能力，标志着移动机器人的智能化水平。本文重点分别从全局路径规划和局部路径规划角度对移动机器人路径规划的研究方法进行了分析与总结，同时也分析了移动机器人路径规划算法的未来发展趋势。
自主移动机器人属于智能型机器人范畴，是集环境感知、动态决策与规划、行为控制与执行等多种功能于一体的综合系统。近年来，自主移动机器人技术在工业、农业、医学、航空航天等许多领域发挥了重要作用，显示了其广泛的应用前景。
在移动机器人相关技术研究中，路径规划是一个重要的环节和组成部分。根据机器人对环境信息掌握的程度，将路径规划分为全局路径规划和局部路径规划。本文重点对全局路径规划和局部路径规划进行分析与总结，最后对移动机器人路径规划的未来发展趋势进行了展望。
一、路径规划的问题概述
路径规划是指移动机器人按照某一性能指标（如距离、时间等）搜索一条从起始状态到目标状态的最优或次优路径。根据对环境信息的把握程度可把路径规划分为基于先验信息的全局路径规划和基于传感器信息的局部路径规划。其中，从获取障碍物信息是静态或是动态的角度看，全局路径规划属于静态规划（又称离线规划）。全局路径规划需要掌握所有的环境信息，根据环境地图的所有信息进行路径规划；局部路径规划只需要有传感器实时采集环境信息，了解环境地图信息，然后确定出所在地图的位置及其障碍物分布情况，从而可以选出从当前节点到某一子目标的最优路径。
二、全局路径规划
1.环境建模方法
（1）自由空间法
自由空间法是用提前定义好的例如凸多边形等常用的几何形状表示机器人工作空间，然后再转换为拓扑结构上的连通图。如图1。
（2）栅格法
栅格法是将移动机器人的工作空间分解为许多网格状的单元，这些单元一般用0、1两个数值来表示，工作环境中的障碍物的形状和大小是一致的，而且移动机器人在行走的过程中，障碍物的位置、形状和大小是固定不变化的。对于移动机器人的工作环境用大小相同的栅格进行划分，栅格大小一般根据机器人的尺寸来确定。如图2。
（3）拓扑法
拓扑法是根据拓扑结构上的一些特征将工作环境分成许多小空间，再由小空间之间连通还是不连通的关系建立一个有拓扑结构关系的网络。如图3。
2.基于搜索的路径规划方法
（1）Dijkstra算法
Dijkstra算法从物体所在的初始点开始，访问图中的节点。它迭代检查节点集中的结点，并将和该节点最靠近的尚未检查的结点加入待检查点集。该结点集从初始结点向外扩展，直到到达目标节点。Dijkstra算法保证能够找到一条从初始点到目标点的最短路径。
Dijkstra算法是一种经典的广度优先的状态空间搜索算法，算法会搜索整个空间直到到达目标点，这就导致了Dijkstra算法计算时间和数据量很大，而且搜索得到的大量数据对于移动机器人的运动是无用的。
（2）A*算法
A*算法在Dijkstra算法的基础上增加了启发式特性，搜索的效率大大提升。A*算法按照Dijkstra算法类似的流程运行，不同的是它能够评估任意结点到达目标节点的代价。与Dijkstra算法选择离初始结点最近的结点不同，它根据启发式函数选择离目标最近的节点。A*算法无法保证找到最优路径，但是速度比Dijkstra速度快很多。如图4。
3.基于采样的规划方法
（1）概率路图法
概率路图法，是一种基于图搜索的方法，它利用随机采样技术将连续空间转换为离散空间，再利用A*等搜索算法在路线图上寻找路径，以提高搜索效率。
这种方法能够用相对较少的随机采样点来找到一个解，对多数问题而言，相对少的样本足以覆盖大部分可行空间，并且找到路径的概率为1。但是，当采样点太少，或者分布不合理时概率路图法是不完备的。如图5。
（2）快速搜索随机树法
快速搜索随机树算法是一种增量式采样的搜索方法，该方法在应用中不需要任何参数整定，拥有良好的使用性能。
基于快速扩展随机树的路径规划算法，通过对状态空间中的采样点进行碰撞检测，避免了对空间的建模，能够有效的解决高维空间和复杂约束的路径规划问题。
它以一个初始点作为根结点，通过随机采样增加叶子结点的方式，生成一个随机扩展树，当随机树中的叶子结点包含了目标结点或进入了目标区域，便可以在随机树中找到一条由初始点到目标点的路径。该方法的特点是能够快速有效地搜索高维空间，通过状态空间的随机采样点，把搜索导向空白区域，从而寻找到一条从起始点到目标点的规划路径，适合解决多移动机器人在复杂环境中的路径规划问题。如图6。
三、局部路径规划
1.人工势场法
人工势场法是由哈提卜提出的一种虚拟的力场法。假设移动机器人在空间中运动的时候受到了引力和斥力的共同作用，这是人工势场法的基本思想。其中障碍物具有排斥势场，对移动机器人产生斥力，移动机器人离障碍物越近，斥力越大。目标具有吸引势场，对移动机器人产生引力，移动机器人离目标越近引力越小。
引力和斥力的合力根据牛顿定律会对移动机器人产生加速度，从而控制移动机器人的运动方向和速度等。在移动机器人上选择一些用来测试的点，计算这些测试点与各个障碍物之间的排斥势和目标之间的吸引势，对获得的这些排斥势和吸引势相加。最后，通过计算势函数梯度下降的方向来找到一条无碰路径。如图7。
人工势场法适合应用在环境不断变化的情况。这种方法有利于底层的、在线的控制移动机器人的运动，而且构造起来简单，在运动路线的平滑控制方面和在线避免与障碍物相撞方面应用越来越广。
2.动态窗口法
动态窗口法DWA是在曲率速度法基础上提出的，将移动机器人的位置控制转化为速度控制，将避障问题描述为速度空间带约束的优化问题。该算法在速度空间中采样多组速度，将有限的速度和加速度的运动约束考虑到动态窗口的设计中，模拟移动机器人以一定的速度在一定时间内的运动轨迹。
在得到运动轨迹后，通过一个评价函数对这些轨迹打分，选取最优轨迹对应的速度来驱动移动机器人的运动。
动态窗口法和A*算法进行融合，构造一种估计全局最优路径评价函数，可实时避障，路径更加平滑，曲率变化的连续性以及可输出的运动控制参数更符合移动机器人动力学控制。动态窗口法充分考虑了移动机器人的物理限制、环境约束以及当前速度等因素，得到的路径安全可靠，适用于局部路径规划。如图8。
四、自主路径规划的发展趋势
随着科学技术的不断发展，自主路径规划技术面对的环境将更为复杂多变。这就要求路径规划算法具有迅速响应复杂环境变化的能力。这不是目前单个或单方面算法所能解决的问题，因此在未来的路径规划技术中，除了研究发现新的路径规划算法外，还有以下几个方面值得关注：
1.局部路径规划与全局路径规划相结合
全局路径规划一般是建立在已知环境信息的基础上，适应范围相对有限。局部路径规划能适应未知环境，但有时反应速度不快，对局部路径规划系统品质要求较高，因此，如果把两者结合即可达到更好的规划效果。
2.传统路径规划方法与新的智能方法相结合
近年来，一些新的智能技术逐渐被引入到自主路径规划中来，也促使了各种方法的融合发展，例如：人工势场法与神经网络、模糊控制的结合，以及模糊控制与人工神经网络、遗传算法及行为控制之间的结合等。
3.多传感器信息融合用于局部路径规划
移动机器人在动态环境中进行路径规划所需的信息都是从传感器获得，单一传感器难以保证输入信息的准确性与可靠性，多传感器所获得的信息具有冗余性、互补性、实时性，且可快速并行分析现场环境。目前的方法有：采用概率方法表示信息的加权平均法、贝叶斯估计法、卡尔曼滤波法、统计决策理论法、仿效生物神经网络的信息处理方法、人工神经网络法等。
4.局部路径规划与动态环境路径规划相结合
类似足球机器人比赛，需要考虑目标点情况。这类规划由于要考虑机器人及目标点状态，使得规划问题更为复杂，同时也赋予移动机器人更高的自主性以及智能水平。
5.多智能移动机器人协调规划
该智能技术正在逐渐成为新的研究热点，受到业内人士的广泛关注。由于障碍物与移动机器人数目的增加，极大地提高了自主路径规划的难度，这将是一个更加贴近现实的研究课题，也是移动机器人技术亟需拓展的领域。
