栅格图特征提取下的路径规划建模与应用

赵 江，王晓博，郝崇清，刘慧贤，薛文艳，王昭雷

1.河北科技大学 电气工程学院，石家庄 050018

2.国网河北省电力有限公司，石家庄 050051

1 引言

移动机器人逐渐代替人进行工作，并具有高精度和高效率的优点[1]。机器人综合了机器视觉、机器人导航与定位、模式识别、多传感器融合和人机接口等多种研究领域[2]。自动导引车辆（Automated Guided Vehicle，AGV）作为一种新型的智能移动机器人，具有自动化程度高、灵活性强、抗干扰能力强、安全性好等优点。路径规划作为AGV 运动中的关键问题之一，成为目前的研究热点。根据已知的环境信息，路径规划问题可分为两类：一类是全局路径规划问题[3]，即在规划之前已经知道所有的环境信息。另一类是局部路径规划问题[4]，机器人必须自己收集环境信息。本文研究的是全局路径规划问题。

全局路径规划问题有两种常用方法：一种是穷举搜索方法，如 Dijkstra[5]、A*算法[6]和图论[7]。该类方法搜索的是整个空间，这意味着它一定可以找到最优解，但执行时间会随着问题的大小成指数增长。为解决上述问题，Akshay 等在文献[1]中提出了机器人路径规划的时效A*算法，它不确定每个节点的启发式函数值，只在碰撞阶段之前确定该值，从而缩短了A*算法的执行时间。Song等[8]认为A*算法仅限于生成分段线性路径，既不平滑也不连续，使得节点过多不利于智能体的运行，为此提出了一种改进的基于路径点的A*算法，来平滑A*算法规划出的路径，减少不必要的节点，使路径更加连续，其本质是在规划出路径后再对路径进行平滑处理，然而在进行路径规划时，往往会增加算法的计算量，影响算法的实时性。

另一种解决全局路径规划的方法是利用启发式算法，它是解决优化问题的一种常用方法。由于路径应该是无碰撞的，并且应该满足一组优化准则，因此路径规划也被认为是优化问题。常用的启发式算法有禁忌搜索法[9]、蚁群算法[10]、遗传算法[11]、粒子群算法[12]等。但这些算法容易陷入局部最优，且计算量较大。为此，Mo等[13]将生物地理学与粒子群算法相结合，增加了种群的多样性，避免了局部最优；Lee等[14]改变了遗传算法初始种群的生成方式，缩短了寻找最优解所需的时间，加快了算法的收敛速度；Yakoubi 等[15]考虑到转弯次数对智能体的影响，利用遗传算法规划出了一条路径较短、转弯次数较少的路径，并说明了这样的路径更有助于智能体的高效运行。

蚁群优化算法（Ant Colony Optimization，ACO）是一种经典的仿生最优路径规划算法，具有易于与其他算法融合、易于分布式并行计算、全局优化性能好等优点[16]。已有的研究结果表明，蚁群算法在求解复杂优化问题，尤其是离散优化问题方面具有一定的优势。王晓燕等[17]结合人工势场法与蚁群算法，将人工势场法求得的初始路径与节点间的距离综合构成新的启发信息，并引入启发信息递减系数，避免了因启发信息误导而造成的局部最优问题。Lee[18]提出了一种基于异构蚂蚁的路径规划方法，通过改进蚂蚁的转移概率函数和信息素更新规则来直接找到一个节点较少的最佳路径，无需进行后续的平滑处理。

规划节点，即在路径规划过程中算法所需规划的节点，传统的路径规划方法存在着规划节点过多的问题。节点可以分为换向节点和非换向节点。AGV在实际运行中，由于所规划的路径通常是分段线性路径，AGV必须停在每个换向节点，根据下一段路径改变其方向，然后再重新启动[19]，因此换向节点的多少对提高AGV 的运行效率、减少AGV 的磨损起着重要作用。而当非换向节点过多时，由于在每一个节点处都要对其要到达的节点重新进行计算，算法的计算量会过大，减少路径规划时非换向节点的数目，可以缩小搜索范围，提高搜索效率。

然而，上述文献虽然考虑了节点过多对算法计算量和AGV 运行效率的影响，但是其改进方法往往是对一般算法规划出路径后再对路径进行平滑处理，这样会使路径规划的过程相对繁琐，不利于使用。为此，卜新苹等[20]利用四叉树法对传统的均匀栅格图进行分割，重新确定栅格之间的连接关系，减少栅格数目。结果表明，减少栅格点能在不影响求解质量的同时，缩小搜索范围，从而提高了算法的收敛速度，减少了规划出的路径中节点的数量。Han[21]提出了提取临界障碍物和周围点集的方法，该方法根据障碍物对路径规划的重要程度，找到相对重要的障碍物，并在环境中找到包含这些障碍物的栅格点子集，减少了需要考虑的栅格点的数目，从而降低了三维路径规划的复杂性。在不同的障碍物环境下进行的仿真实验表明，该方法提高了三维路径规划的效率，也减少了规划出的换向节点的个数，提高了智能体的运行效率。

利用四叉树法非均匀分割栅格图时针对不同的环境会有不同的四分原则，而且重新确立连接关系时要频繁进行入栈出栈操作，可能会造成数据量过于庞大。而提取临界障碍物和周围点集的方法只适用于一条路径被频繁修改的情况，当要寻找完全不同的另一条路径时，之前非临界障碍物有可能会成为新的临界障碍物，进而影响求解过程。为了能够在减少规划节点的同时不失去算法的广泛适应性，将障碍物的顶点作为节点特征进行提取，并将其作为新的备选点来规划路径，然后采用蚁群算法在新的栅格环境下进行路径规划，以期减少蚁群算法搜索过程中的节点数目，提高算法的收敛速度。

2 问题背景与栅格法建模

2.1 问题背景

全方位移动AGV 作为自动搬运车辆，可完成移动加工、装配的任务。基于麦克纳姆轮的全方位移动AGV有着卓越的全方位性能，AGV实物图如图1所示，其结构如图2所示。

AGV的速度公式如下所示：

图1 自动导引车

图2 AGV的结构

其中，Rω是车轮的半径；θ1、θ2、θ3、θ4分别是4个轮子的速度；L、W分别是AGV长和宽的一半；Vx、Vy分别是AGV的横向和纵向速度；ωz是AGV的角速度。

2.2 栅格法建模

在全局环境已知且障碍物为静态障碍物的环境下。用栅格划分出AGV的工作区域，并用只包含0和1的矩阵生成栅格图，障碍栅格由黑色表示，自由栅格由白色表示，如图3所示。

图3 栅格法环境建模

由于实际运行时，AGV并不是一个质点，如果规划出的路径距离障碍物过近，会影响AGV 运行时的安全性。因此，在使用栅格法进行环境建模时，会首先对障碍物进行膨胀化，即只要该栅格中有障碍物，直接扩展为整个黑色栅格，障碍物膨胀化前后规划的路径图如图 4（a）、（b）所示。

图4 障碍物膨胀化前后规划的路径图

由图可知，在进行膨胀化后，障碍物的实际大小小于黑色障碍物栅格，因此，规划出的路径可以与障碍物保持一定的安全距离。

3 新环境模型下的蚁群算法

3.1 问题描述

针对传统栅格法建模规划的路径节点过多，导致车辆的运行效率降低、损耗增加的问题，本文提出了一种新的环境建模方法。该方法将障碍物的顶点从原有栅格图中提取出来，并作为蚁群算法中新的备选点用于规划路径。新环境模型下蚁群算法的数学描述如下。

（2）所有障碍物顶点的集合：C={c1,c2,…,cNc}。

（3）一个最优解的非空集合S*，用于保存可以避开障碍物的最短路径。

3.2 节点选择策略

当蚂蚁位于某一节点时，为了从备选点中选出一个点作为下一节点，需要对节点进行选择，节点选择策略如式（1）。

其中，ci是当前节点，ci+1是ci的下一个可行点。是两个点之间的信息素，是两个点之间的启发式信息，α和β分别是信息素和启发式信息的重要程度。

3.3 信息素更新

每当完成一次路径的搜索，蚁群算法会对路径上的信息素做出更新，其更新法则如式（2）～（5）所示。

其中，Q是常数，PLk,m是第k代第m只蚂蚁从起点到终点的路径长度，ρ是信息素衰减系数，是信息素初值。

3.4 顶点提取与可视性判断

为了解决传统栅格法备选点过多、算法计算量过大的问题，提取如图5所示的顶点作为蚁群算法的备选点。

图5 栅格图中的顶点提取

由图可知，在进行了顶点提取之后，在30×30 的环境中提取出80个顶点。之后运用蚁群算法进行路径规划时，只需从这80 个顶点中找到最短路径即可。该方法使问题的维数从900下降到80，极大地提高了算法搜索的效率。然而在提取了顶点之后，原有栅格之间的连接关系被打破，因此需要确定每个顶点的邻域，重新构造邻接矩阵。

当判断两个顶点之间是否存在无障碍物路径时，仅需判断这两个顶点之间是否存在障碍物的边即可，即判断两条线段是否相交，如图6所示。

图6 顶点可视性判断

栅格a和b的连接线l1没有通过障碍物的边缘，因此定义栅格a和b是可见的，并在邻接矩阵中记录栅格a和b之间的距离；然而，栅格a和c的连接线l2与障碍物的两个边缘x=3 和x=7 相交于点（3，28）和点（7，24），因此定义栅格a和c是不可见的，并且在邻接矩阵中记录两点之间的距离为0。

该算法实际上是通过建立新的候选列表，减少蚁群算法要搜索的节点个数，从而大大降低搜索空间的维度，使系统的计算时间保持在合理的范围内。

3.5 算法的流程步骤

新的栅格法建模能够减少蚁群算法中要搜索的节点数目，基于该栅格方法的蚁群算法流程如下。

步骤1 采用栅格法对AGV行驶的二维工作环境进行建模；

步骤2 提取障碍物顶点，进行可视性判断，生成新的邻接矩阵；

步骤3 初始化α、β、ρ、M、N等参数，M为每代蚂蚁的数量，N为迭代次数；

步骤4 将蚂蚁置于起点，并准备开始进行路径搜寻；

步骤5 通过式（1）选择下一个节点；

步骤6 更新禁忌表；

步骤7 判断是否所有蚂蚁都完成了搜索，如果没有，返回步骤4，否则，继续到下一步；

步骤8 根据式（2）～（5）更新信息素；

步骤9 判断是否达到最大迭代次数，如果是，则输出最佳路径，否则，转到步骤4，直到满足最大迭代次数。

3.6 收敛性证明

为了验证算法的可行性，本文对算法的收敛性进行以下证明。

引理两点间的信息素满足式（6）。

其中，Q(S*)是信息素的最大增量。

证明每次迭代之后，信息素的增量最多是Q(S*)。因此可以得出在第一代之后，信息素的最大值为(1-ρ)。是信息素的初值。第二代之后，信息素再次更新，信息素的最大值为

(1-ρ)Q(S*)+Q(S*)。由于信息素的蒸发，第k代信息素应为：

由于0<ρ<1，式（7）收敛到：

假设从起始点到终点至少有一条路径，Ek表示蚂蚁在第k代第一次找到了最短路径，则应该满足式（8）：

证明代表最短路径第i次选择的栅格。由式（1）和节点的选择相互独立，可以得到第m'只蚂蚁在第k代找到了最短路径的概率为：

由式（5）可知第k代信息素的最小值为：

并且由引理可知，第k代信息素的最大值为：

而Nc(k,m',(ci,ci+1))的最大值可以被定义为：

其中，Nc(k,m',(ci,ci+1))是可选择的节点个数，将式（11）、（12）、（13）代入式（10）可得：

令

将式（15）代入式（14）可表示为：

通过式（16）可得：

对上式取对数可得：

即

4 仿真结果与评价指标

4.1 仿真结果

为了验证新栅格法建模的优点，本文利用新的栅格法对环境进行建模并进行路径规划，并与传统栅格法规划出的路径进行比较，每个栅格的边长设定为1。将起点设置为（0.5，8.5），终点设置为（25.5，28.5），结果如图7所示。

从图中可以看出，基于新栅格法建模的蚁群算法规划出的路径中的节点数量与旧路径中的节点数量相比显著减少，从而提高了车辆的运行效率，同时保证了车辆与障碍物的安全距离。

除此之外，新的栅格法建模由于减少了蚁群算法要搜索的节点数量，从而减少了蚁群算法的计算量，提高了蚁群算法的收敛速度，如图8所示。

由结果可知，使用基于特征提取的栅格法建模的改进蚁群算法可以更快地收敛到最短路径，保持了改进蚁群算法的收敛速度。最短路径长度较改进前略有增加，这是由于在本算法中顶点的可见性判断时，如果障碍物的顶点刚好在两个栅格的连线上，为了安全起见，这两个栅格设为不可见，而在原有的蚁群算法构建邻接矩阵时，若两个栅格间的连线刚好经过障碍物顶点，则这两个栅格可见，但很明显这种方法是不可取的。

图7 不同算法规划出的路径对比

4.2 评价指标

在评价传统的路径规划算法时，主要包含以下几个评价指标：路径长度、迭代次数、路径的节点个数、路径的总转弯角、拐点数、每段路径和最近障碍物点之间的安全距离。本文将这些评价因素提取出来，与传统蚁群算法以及改进蚁群算法进行比较，如表1所示。

图8 不同算法的迭代次数

由表1可知，改进栅格法建模在保持了改进蚁群算法路径长度的同时，算法的迭代次数、路径的节点个数、总偏转角、拐点数以及安全距离都有了明显的改善。其中，减少迭代次数意味着增强了算法的寻优能力，减少节点个数意味着AGV 提高了运行时的效率，减少偏转角和拐点数意味着减少了AGV 运行时的磨损，加大安全距离意味着AGV运行时的安全性得到了保证。综上所述，在考虑多个评价因素后，基于改进的栅格法建模的路径规划具有明显的优势。

表1 评价指标的对比

5 结束语

针对传统路径规划问题中规划出的节点过多、算法计算量大的问题，本文提出了一种基于特征提取的栅格建模方法。通过提取障碍物的顶点，并且重新构造邻接矩阵，减少了规划出的路径的节点个数。该方法不仅降低了蚁群算法的复杂度，而且提高了规划路径的性能，保证了AGV的高效可靠运行。同时因为新的栅格法规划出的路径不会直接经过障碍物栅格的顶点，所以路径的安全性也得到了保证。为了验证算法的收敛性，对其进行了数学证明，并对算法进行了仿真。结果表明，改进后的算法明显优于传统的蚁群算法，解决了传统路径规划算法中由于换向节点过多而导致车辆行驶效率低，损耗大，以及非换向节点过多而导致的算法计算量庞大的问题，为AGV 路径规划中环境模型的建立提供了新的思路。