自主移动机器人路径规划方法研究综述-AGV吧

0 引言

机器人技术是现代科学理论与实践综合交又的成果。20世纪60年代末，斯坦福研究院（SRI)研制了自主移动机器人，路径规划方法是其关键核心技术。移动机器人路径规划技术，就是机器人在遵循一些优化指标(比如时间最短、路程最优和能耗最低等）前提下，在运行环境中规划出从起始点到目标点不发生碰撞的最优路径。

移动机器人路径规划实质上是满足一定约束条件的优化问题，其算法设计过程具有复杂性、随机性、多目标性和多约束性等特点。根据路径规划环境是否随时间变化，将移动机器人的路径规划分为动态规划和静态规划。根据机器人路径规划的目标范围，又可分为全局路径规划和局部路径规划。本文在移动机器人路径规划模型基础上，将路径规划方法分为传统方法和智能方法，阐述各种方法的优缺点，讨论算法的深度融合问题，并对移动机器人路径规划发展趋势进行展望。

1 移动机器人路径规划模型

在移动机器人的二维或三维工作空间中，解决路径规划问题必须定义物体（包括障碍物和机器人）的几何模型。路径规划问题最初研究的是二维空间（如地面机器人），根据能量守恒原理，利用二维空间的辐射热传导方程建模进行路径规划问题的求解。

假设在二维空间中，存在一个表现障碍物区域、一个目标点区域和一个起始点区域。为避免障碍物，通过计算三类典型方程寻求从起始点区域到目标点区域的最优路径。在二维平面直角坐标系下，有以下等式：

2 路径规划方法研究现状

本文根据机器人路径规划原理特点，将规划分为传统方法和智能方法。

2.1 传统路径规划方法

传统路径规划方法有栅格地图法、人工势场法、拓扑图法、自由空间法、可视图法等。

2.1.1 栅格地图法

栅格法（Grid Method，GM)是最常见的环境建模方法，1968年，W.E.Howden首先提出采用栅格法解决机器人路径规划问题。栅格地图法将机器人运行的环境信息划分为很多小栅格，并定义为障碍物区域、已覆盖区域和未覆盖区域。栅格地图法简单实用，易于实现，但其计算量大，运行时间久，搜索效率低，只适合简单的环境情况。如图1所示，黑色栅格代表障碍物区域，白色栅格代表自由区域，实线表示机器人行走路径。

四又树法（Quadtree Method,QM)是对栅格地图法的一种改进，该方法能有效压缩环境信息，减少寻优路径时间，提高搜索效率。如图2所示，首先将机器人的工作环境作为一个根节点0，将根节点平均分为01、02、03、04四个子节点，其中01子节点无障碍物，被称为全自由节点，02子节点全为障碍物，被称为全障碍节点。03和04子节点既有自由区域又有障碍区域，被称为混合节点，需要对其继续分割。当分割出来的子节点为全自由节点或全障碍节点时（如0331和0333节点所示），四又树分割结束。

四又树法将机器人运行环境信息进行四分化，可快速查询、删除、增加节点，即使环境中障碍物个数和位置发生变化，也可重新分割快速调整环境模型，简化了数据存储量。但当许多细小的颗粒障碍物存在于环境中时，会导致树的深度增加，计算量也将变大。

2.1.2 人工势场法

人工势场法（Artificial Potential Field，APF)实际是一种虚拟力法，由Khatib和Andrews等[]于1994年提出并用于移动机器人路径规划。该方法原理为：假设目标点和障碍物存在虚拟力场，将移动机器人看成一个质点，如图3所示。障碍物作用于虚拟力场为斥力场，斥力值F,随着机器人和障碍物间的距离增大而减少，二者成反比例关系。斥力方向与障碍物相背离。目标点周围存在引力场，机器人越靠近目标点，引力值F。越大，引力方向指向目标点位置。

利用人工势场法进行路径规划，收敛速度快，算法实时性好，计算量小，但不适用于复杂的动态环境，优化过程中会出现合力为零、机器停止移动的情况（死锁现象）。

2.1.3 拓扑图法

拓扑图法（Topological Map Method，TMM)将环境中特殊位置用节点表示，用节点间的连线表示环境路径。拓扑图法将复杂的环境转为拓扑环境，在位置误差方面具有较好的鲁棒性。但工作时间长，效率低，适合简单的作业环境，算法复杂度由障碍物数目决定，规划的路径质量不高。

2.1.4 可视图法

可视图法（Visibility Graph，VG)由Nilsson21]于1968年提出，常用于多边形障碍物的工作环境。首先，将环境中多边形或不规则障碍物分解为多个矩形，机器人视为一个质点（忽略机器人大小和外形)，然后将机器人起点和矩形组成的障碍物各顶点以及目标位置点用线段连接，连接的线段不能穿过矩形障碍物，最后得到所有的遍历路径，如图4所示。

利用可视图法构建环境地图简单方便，能够搜索到最短路径，适合障碍物较少且不发生改变的环境。当障碍物位置和个数发生变化时，就需要重新构建环境地图，且计算量随着障碍物个数的增加而变大。针对以上不足，学者提出了Voronoi图法和切线图法。

2.2 智能路径规划方法

近年来，路径规划问题在求解过程中变得复杂化，具有较强的随机性，仿生智能算法应运而生并取得了长足发展。

2.2.1 基于遗传算法的机器人路径规划

遗传算法（（Genetic Algorithm，GA)是模拟自然界生物进化提出的一种智能算法。算法核心思想是模拟生物在自然环境中不断进化时，个体之间遗传、杂交、变异和自然选择等现象。遗传算法求解路径规划是将路段描述成一系列中途点，并将其转换为二进制串。首先将路径群体初始化，其次进行遗传操作（如选择、交叉、复制、变异），最后经过若干代进化后停止进化，根据规划要求完成解空间搜索，输出当前最优个体，见图5。

遗传算法具有全局搜索能力强、鲁棒性好和操作简单等优点，但当算法编码较长时，会导致收敛速度慢、计算量大，故不适合求解复杂的路径规划问题。

2.2.2 基于人工神经网络算法的机器人路径规划

人工神经网络算法(Artificial Neural Network，ANN)在20世纪40年代后期出现。如图6所示，人工神经网络是一种非线性网络系统，模拟大脑中相互连接的神经元网络，具备并行性和分布式特点。该方法不仅用于路径规划，还应用于环境建模、传感器信息交互融合、机器人系统控制等领域。

人工神经网络算法采取分布式计算，拥有较强的实时性和学习性。求解路径规划问题时，计算量少且收敛速度快，容易实现。但由于算法初期反馈信息不足，需要经过

2.2.3 基于模糊逻辑法的机器人路径规划

模糊逻辑法（Fuzzy Logic，FL）采用反射机制模拟驾驶员的驾驶经验，利用不同类型的传感器感知障碍物和机器人状态，通过模糊规则控制机器人寻径速度和转向角度，从而实现局部路径规划。HChang等[]建立一个模糊推理模型解决机器人路径规划问题，具体步骤如图7所示。

利用模糊逻辑法进行机器人路径规划，可在动态环境中迅速规划出有效路径，即对环境有较强的适应性。但随着障碍物增多，该方法计算量也会增大，搜索效率变低。

2.3 算法融合与分析

如何将算法深度融合以提高避障效率，取得寻径的最佳效果，是当前移动机器人路径规划问题的重点。

2.3.1 传统方法结合

传统的栅格地图法、人工势场法、可视图法和拓扑图法等不适用于所有情况下的路径规划问题，每种算法都有局限性。根据传统方法特点，一些学者相继提出改进或派生算法，证明了在某些特定条件下算法的实用性，有效提高了路径规划效率。针对传统人工势场法局部极值问题和目标不可达问题，欧阳鑫玉等先在斥力势场函数中增加最小安全距离，建立改进人工势场模型，然后采用栅格法对改进的人工势场法作辅助决策，使机器人尽快脱离局部极小值并成功到达目标点。

2.3.2 智能有效方法结合

随着三维空间对移动机器人的需求增加，传统方法的实时性降低，计算量加大，一系列智能有效规划算法被提出。例如，关于遗传算法与蚁群算法的路径规划问题，单独使用的情况较少，一般利用进化计算进行优化处理，再与其它算法结合完成路径规划任务。潘昕等[]针对三维空间中水下潜航器（AUV）的全局路径规划存在时间较长、搜索效率低等问题，提出了一种基于遗传蚂蚁混合算法。王辉等针对智能停车库自动导引运输车（AGV）存取路径规划问题，提出了一种基于粒子群遗传算法的自适应混合算法，具有较好的收敛性和较强的全局搜索能力。

2.3.3 传统方法与智能方法结合

人工智能系统的日益成熟推动了传统方法与智能方法的结合，如栅格法与遗传算法、粒子群算法等的融合，人工势场法与蚁群算法、遗传算法以及ANN等的融合。卢路秋提出了基于多阶模糊系统人工势场路径规划方法，设计了冲突消解策略，减少了路径规划时间和长度。刘亮提出了势场蚁群路径规划算法，初期引入势力场启发信息影响系数，降低蚁群搜索的随机性，增强势力场函数的引导作用，后期则相反。该方法避免了早熟现象，搜索时间短，精度较高。姜英杰等利用栅格遗传算法对变电站巡检机器人进行全局路径规划。周文明等针对移动机器人局部路径规划问题，改进势力场函数，引入神经网络模糊系统，使系统速度加快、鲁棒性好。

3 算法对比与分析

目前在移动机器人路径规划领域，传统方法由于简单实用仍是首选，但传统方法在路径优化及路径搜索方面尚待完善，比如基于采样的改进算法（RRT*）。不同于其它传统方法，人工势场法在实时动态环境中易于实现，且规划效果良好，但容易出现目标不可达和局部极值问题。人工智能技术应用于路径规划，克服了传统方法的不足。基于生物智能的路径规划方法不需建立复杂的环境模型，收敛稳定且为随机搜索，大大提高了寻优效率，比如遗传算法、蚁群算法和粒子群算法等自然启发法能用于复杂环境下的路径规划问题，但自然启发法计算代价高、耗时长。神经网络法是另一种智能算法，它模拟生物的神经结构处理信息，具有信息分布式存储和并行处理特点，但实时性一般。因此，为了取得最佳路径规划效果，以上方法通常相互结合，如传统算法、智能算法和混合算法等。移动机器人路径规划方法性能比较如表1所示。

4 移动机器人路径规划发展趋势

移动机器人路径规划研究已取得显著进展，但在某些领域仍具有一定的局限性，一些核心技术如工作环境建模、导航定位和故障检测等亟需开发。根据过去的研究情况和发展趋势，笔者认为未来自主移动机器人路径规划技术发展方向有以下几个方面：

（1）多机器人协调作业。对于复杂的环境，单个机器人路径规划技术已不能满足任务需求，使用多机器人移动具有良好的安全性、可靠性和协调性。

（2）硬件系统更新换代。随着科技的发展，使用高速度处理芯片（如ARM、DSP和FPGA等）将提高规划效率，大大节省路径规划计算和检测时间。

（3）多传感器信息融合技术。通过合理利用多个传感器采集、处理信息，提高机器人路径规划的鲁棒性和精准性。如空中无人机编队飞行、足球机器人比赛和水下机器人的合作搜救与观察等。

（4）新的智能算法或混合算法。路径规划方法应拥有良好的实时性和响应速度，能够适合各种复杂场景。目前智能算法优于传统算法，具有自组织、自学习等优点，但单一的智能算法会有全局搜索能力不强、容易陷入局部最优解等不足。将多种智能算法有效结合可以取长补短，改善优化效果。探索新的智能算法是路径规划技术发展的方向之一。

（5）高维环境和复杂环境下的路径规划技术。将二维空间的大量路径规划方法推广到三维空间，但机器人在三维空间中的运动学和动力学约束及环境建模问题很复杂，部分算法难以扩展。

（6）不断提高衡量路径规划优劣的相关性能指标。这些性能指标由算法的实时性、准确性和可达性组成。移动机器人所处的环境是不断变化的，如果算法没有良好的实时性能，在遇到突然出现的障碍物时就会反应迟缓，无法完成避障。高效及准确性可使机器人快速准确到达目标点，减少搜索时间，提高路径规划算法效率。可达性是路径规划最基本的要求，如果通过算法搜索出的路径不具备可达性，则该路径毫无意义。