移动机器人路径规划技术综述

邵伟伟，吴玉秀，范冬冬

（安徽工业大学，安徽 马鞍山 243002）

随着机器人技术的发展，机器人已经不再是只会机械的执行指令的传统机器人，其正朝着智能化、多样化和大众化的方向发展。智能机器人运用了多学科前沿的研究理论与成果，进入新世纪以来机器人技术得到飞速的提升，因其具有高效性、精准性、实用性等，它们已经被广泛的运用到工业生产、军事领域等各行业中。机器人技术是国家科技实力的体现，以机器人为代表的人工智能将引领着下一代的产业革命，因此各国政府纷纷增加它们对机器人行业的投入。

智能化的移动机器人将代表着机器人今后的发展趋势，作为研究者重点研究的对象——移动机器人路径规划技术[1]，也随着机器人技术快速的发展而发展，本文简要的论述几种常用的路径规划方法。

1 路径规划技术的简介

移动机器人通过视觉传感器、声呐传感器等装置感知工作环境以及移动机器人的状态，使它能在存在障碍物的工作环境中快速搜寻出一条从设定的起点到目标点的最优无碰路径，该技术即为路径规划技术[2]。路径规划不是纯粹性的追求一条距离最短的路径，而是根据具体的环境和人们的要求做出合理的决策，从而规划出一条最优路线[3]。目前人们对路径规划技术的研究主要是如下三个方面：（1）移动机器人在给定的全局环境中行走，必须避开各种静态（或动态）的障碍物，一路无碰撞的到达目标点；（2）机器人在向目标行进的过程中，运用传感器等装置探测出前方路径存在的不确定因素，能在短时间之内应对由各种原因所造成的误差并予以修正；（3）根据人们的具体要求，搜索出一条最优行走路线。现阶段研究者按照不同标准对路径规划技术算法进行归类，使之分成不同模型，本文采取最常用的以规划目标为分类标准的规划方式对路径规划技术进行论述。

2 全局路径规划的方法

研究者按照机器人在移动之前是否完感知机器人的工作环境，将路径规划分为全局路径规划与局部路径规划，全局路径规划的工作环境已知，局部路径规划的工作环境未知或只知道一部分的工作环境，但是这两种模型之间却无实质区别，它们之间的规划方法在经过改进后可以相互转换[4]。

全局路径规划常用的方法如下:道路图规划方法、图搜索法以及快速扩展随机树算法等。

2.1 道路图规划方法

道路图规划方法是一种比较直观的路径规划方法，它可以根据障碍物的形状对机器人前进的空间实施分解从而进行最优无碰规划，通过把分解得到的路径连接起来，通过算法寻找出一条最优的无碰平滑曲线，常用的道路图规划方法有可视图法、Voronoi图法等[5]。

可视图法：把机器人看成一个大小、形状可以忽略的质点，把移动机器人的起点、每个障碍物的顶点以及目标点通过直线连接在一起，而连接在一起的直线不能穿越障碍物，由此可以获得一张无碰撞的路径图，即为可视图[6]。利用可视图可以清晰明了的得到一些无碰路径，通常采用优化算法可以淘汰一些没必要的直线从而使可视图法搜索路径的时间变的短一些，路径规划器从可视图中选取一条最优路径作为移动机器人的规划路径。图1为可视图。

图1 可视图

因可视图法简单明了，易于操作，通常在离散空间中，移动机器人在路径规划时常采用可视图法。虽然可视图法性能优异，但它有以下缺点制约着它的使用：（1）随着障碍物数量增加，尤其是在环境空间中增加复杂的多边形障碍物，其顶点较多，使可视图法的连线增多，加大了其复杂性，致使其优点丧失；（2）任何机器人都不可能是大小不计的质点，当机器人行走在利用可视图法规划的路径中，因为规划的模型中把机器人看成质点，所以当机器人靠近障碍物时就有可能碰撞障碍物，通常的解决方法是把障碍物体积适当的膨化或者修改路径离障碍物的距离，这会使规划出的路径不是最优路径[7]。

Voronoi图法：Voronoi图法与可视图法的不同，它的规划理念是让机器人与障碍物的间距最大，从而使机器人远离障碍物[8]。采用Voronoi图时，路径规划器通过算法选取自由空间中的点，计算它们距离障碍物最近的距离，根据障碍物的形状，画出与障碍物等距离的直线或曲线，经过多次取点画线，所得到的完整封闭曲线图即为Voronoi图，通过算法在Voronoi图中选取一条最优路径即为规划的路径。虽然Voronoi图法规划出的路径不是最短路径，但它所规划出的路径不会有碰撞现象，其安全性强。

图2 Voronoi图

2.2 图搜索法

基于图搜索法的路径规划规划技术也常常被人采用，它与可视图法一样简单清晰，常用的图搜索法有栅格法等。

栅格法：栅格法是将移动机器人工作的空间划分成多个相互连接的规则栅格，栅格通常分为自由栅格与障碍栅格，没有障碍物的栅格称为自由栅格，而有障碍物的栅格称为障碍栅格。栅格通常采用直角坐标法或标号法进行标识，常采用四叉树表示，根据障碍栅格积累值CV(certainly Value)的大小，采用控制算法计算，避开CV值较大的障碍栅格，从而得到一条无碰的最优路径[9]，其中积累值CV表示栅格中存在障碍物的可信度。

栅格法在构造栅格的过程中，会有一定的局限性，如果栅格构建的过大，其精准性就会下降，虽然路径规划的时间短，但极有可能找不到路径；如果栅格构建的过小，导致模型的分辨率过高，这样就会加大了路径规划器的计算量，使路径规划的时间过长，这些都是不允许的。现阶段的一种解决办法是采用适当放大的栅格进行规划，如果在栅格里发现障碍物则再把该栅格给细分成多个小栅格，再进行路径规划，如果在栅格里没发现障碍物则对此栅格不做细分，进行正常的路径规划，这就很好的解决了栅格的分辨率问题。

2.3 快速扩展随机树算法

快速扩展随机树算法 （RRT算法）：在自由空间中，把机器人的初始出发点看成随机树的根节点，在约束条件限制下采用随机函数生成新节点，使新节点与上一个节点之间的连线不穿过障碍物，该连线作为树干，新节点作为父节点继续产生新的节点，并构造出新的树干，直至产生的新节点与目标点相重合时，随机树的构造结束，在此过程中产生的从出发点到目标点的树干即为规划的路径[10]。图3为快速扩展随机树的构造过程。

RRT算法采用了最优控制理论使其相比于其它搜索方法具有较强的搜索特性，能够合理的规划出一条无碰路径，RRT算法运用在复杂的高维空间中的优势更为明显。RRT算法同其它算法一样，也有一些缺点：（1）因为由RRT算法所规划的路径具有一定的随机性，所以由它规划的路径常常会出现不平滑的现象，因此在实际应用中采用了非完整性约束的机器人则不能使用RRT算法进行规划；（2）由RRT算法规划出的路径通常都具有随机性，因此会导致规划出的路径往往不是最优的路径；（3）RRT算法一般运用在已知的全局环境模型中，它不适用于动态环境的规划。针对上述缺点，现在有许多研究者采用不同的算法对RRT算法进行改进，或采用RRT算法与其它算法合用，从而让它更加适用于路径规划。

图3 快速扩展随机树的构造过程

3 局部路径规划的方法

局部路径规划常用的方法如下:遗传算法、人工势场法与滚动窗口法等。

3.1 遗传算法

在上世纪60年代提出遗传算法后，人们不断的对遗传算法进行改进，现阶段遗传算法已经应用到许多学科，它在路径规划中的应用也日趋成熟[11]。遗传算法采用模拟自然界的遗传机制，在进化过程中寻找最优解，从而找到最优路径，其原理如下：在自由空间中，生成多条路径，将路径中的一些点采用二进制编码法或采用积木块编码法对其进行编码，编码完成后形成群体，再通过遗传操作进行计算，常用的遗传算子有：选择算子、交叉算子、复制算子和变异算子，采用适应函数进行筛选所得到的值，产生新的节点，构成子路径。在群体多次进化后，便可得到最优解，即得到平滑的最优路径，遗传算法的流程图如图4。

图4 遗传算法流程图

遗传算法与大多数采用单点搜索的控制算法不同，它采用多点搜索从而使遗传算法能解决一些算法不能解决的问题，使遗传算法能得到近似全局最优解，进而避免陷入局部最优解。同其它的算法一样，遗传算法也存在着缺陷，遗传算法容易过早的收敛导致 “早熟”，使路径规划失败[12]；另外，遗传算法所用时间比其它算法普遍偏长，而且它的效率偏低也是一个不能忽略的问题。

3.2 人工势场法

人工势场法是通过在机器人工作的空间里构造一种虚拟的力场，使目标点与障碍物分别对移动的机器人产引斥力和斥力。在构造人工势场时，通常把机器人看作一个大小不计的质点，在引力场与斥力场的共同影响下使机器人以平滑路径走向目标点[13]。人工势场法的原理如下：在机器人行进过程中，机器人搜索到附近有障碍物时，倘若机器人和障碍物的距离R大于障碍物的影响距离r，斥力可以忽略不计；若R小于r时，F与r成反比，当R→0时，则F→∞，所以机器人在运动的过程中不会出现碰撞现象。机器人在引力场和斥力场的共同作用下，最终走向目标点，由此规划出的路径则是一条无碰的最优路径。

虽然人工势场法所得到的路径是一条无碰路径，但它自身也存在着一些局限性，例如因为对周围的感知能力有限会产生局部极小值，有时甚至在一些凹形障碍物附近，呈现出振荡现象，产生“死锁”效应。针对以上人工势场法产生的缺陷，人们在出现上述局部空间中，通常会增加一个虚拟的障碍物使之产生斥力场，与之前形成的合力场形成新的合力场，使机器人逃脱“陷阱”，从而减少“死锁”对路径规划所产生的不良影响。

3.3 滚动窗口法

如果机器人工作在未知的动态环境中，滚动窗口法相比于一般的局部规划算法适应性更强[14]。通常机器人在前进过程中，每前行一步就不断的通过传感器检测去周围障碍物信息，然后在机器人的滚窗中实时更新障碍物信息，并在滚窗中设置一个子目标，采用一些算法实时的规划机器人在窗口中的路径，使之能够无碰的到达子目标，到达子目标后，根据新的滚窗信息，再设置下一个子目标，并完成路径规划，直至到达目标点，这一过程即为滚动窗口法[15]。

滚动窗口法对动态的障碍物常常采用场景预测的方法进行预判，从而找出一片安全区域供机器人行走，所以该方法的实时性很强，这也是滚动窗口法优于其它算法的地方。一般情况下，滚动窗口法常和其它算法一起运用到路径规划中，从而使机器人能够规划出最佳路径。

4 总结与展望

现阶段传感器性能的提升以及人们对各种新型算法的开发，使得机器人路径规划技术的精度越来越高，技术越来越成熟。上述的全局路径规划算法和局部路径规划算法虽然取得了较多的成果，但它们自身却存在这各种各样的缺点亟待解决。对于它们的缺点，可针对其自身的算法进行更改，或者在同一路径规划中，采用多种路径规划的方法相互结合进行路径规划，这样就可以扬长避短，把误差控制在最小。

现阶段人们对智能算法的研究逐渐深入，随着模拟退火算法、免疫克隆选择算法、禁忌搜索等智能算法在路径规划中应用的深入，使得路径规划技术更加高效化、智能化，智能算法将代表着未来路径规划技术的发展方向，它对路径规划技术的快速发展将起到推动作用。

机器人在完成路径规划后，通常会得到一些不规则的曲线，这对机器人前行来说，会产生一些不利的影响，例如：机器人需要停车转向，甚至有时得倒车转向才能完整的贴合路径行走，既耽误了机器人的前行时间，又会让机器人因来回停车转向而危害机器人的电动机，这一点是需要注意的。虽然通过一定的环境模型能规划出移动机器人的行走路径，但在规划完路径后需要再通过一些算法把机器人的路径变的平滑起来，使之满足应用要求。