移动机器人导航路径的异构串行蚁群算法规划

蒋泽艳，郭林炀，廖 军，周正平

（1.长春金融高等专科学校信息技术学院，吉林 长春 130000；2.长春理工大学高功率半导体激光国家重点实验室，吉林 长春 130022；3.扬州工业职业技术学院智能制造学院，江苏 扬州 225000；4.江苏曙光光电有限公司，江苏 扬州 225000）

1 引言

移动机器人的应用不仅提高了生产效率、降低了生产成本，而且在危险复杂环境下提高了人类安全度。路径规划是移动机器人自主完成各项任务的基础和前提，是移动机器人真正实现智能化、自主化的关键技术［1］。移动路径质量对机器人执行任务效率、使用安全和使用寿命具有极大影响，因此研究机器人路径规划问题具有较大的使用价值。

机器人路径规划具有多种分类方法。根据移动机器人数量，可以分为单机器人路径规划和多机器人路径规划；根据环境信息掌握程度，可以分为全局路径规划和局部路径规划［2］。机器人路径规划方法可以分为传统方法、启发类方法、智能仿生方法等。传统方法包括人工势场法、模糊逻辑法等，该类方法特点是更加依赖环境信息。启发类方法是以某种特征信息为启发的规划方法，主要应用于离散的拓扑网络中，包括A*算法［3］、Dijkstra算法、D*算法［4］等。智能仿生方法是以群体智能为基础，将最优路径搜索问题转化为最优解搜索问题，包括蚁群算法、粒子群算法、鱼群算法等［5］。文献［6］研究了布谷鸟算法与蝙蝠算法混合的路径规划方法，使用蝙蝠算法确定障碍物数量和位置，基于布谷鸟算法搜索了最优路径，该方法有效降低了路径长度。文献［7］以路径最短、时间最短、无碰撞为路径规划目标，研究了粒子群与蚁群混合算法的规划方法，混合方法与两种独立算法相比具有优越性。文献［8］研究了势场-蚁群算法的路径规划方法，通过增设虚拟子目标、设置自适应挥发因子等策略，使算法在不同复杂环境下规划的全局路径质量有所提高。随着工作环境复杂性、多样性的不断增加，现存规划方法的时效性、非最优等问题日益突出，因此关于不同应用背景下的路径规划方法仍是当前研究热点。

这里针对栅格环境下的路径规划问题，以路径长度最短和拐点数量最少为优化目标，在蚁群算法中引入信息素非均匀初始化策略、角度启发因子和异构蚂蚁串行策略，并将改进算法用于路径规格，所规划路径在长度和平滑度上具有较大优势。

2 路径规划问题描述与建模

2.1 环境模型

这里研究的是移动机器人在静态环境下的全局路径规划问题，首先需要建立环境模型，将抽象的三维环境转化为机器人可以识别的数字地图。栅格法［9］具有原理简单、使用方便、适用性广等优点，因此这里使用栅格法将抽象的三维环境建模为二维数字地图。从三维空间到二维空间的建模，是一个降维的过程，常用方法是根据地面的障碍物分布确定二维环境，但是这种降维方法忽略了空间障碍物（比如顶棚的下垂物）对机器人移动的影响。将机器人高度记为H，当空间障碍物与地面距离小于H时，将与地面距离小于H的部分沿竖直方向向地面投影，将障碍物投影与地面障碍物叠加，可得到二维环境模型。栅格环境模型的建立过程可以归纳为两个膨化过程、一个编码过程。

首先是障碍物的自身膨化，为了将机器人简化为一个质点，将机器人最大外径叠加到障碍物尺寸上，如图1（a）所示。图中黑色三角形表示原始障碍物，向外膨胀尺寸为机器人最大外径。其次是栅格内障碍物的膨化过程，当障碍物没有填满栅格时，将障碍物进行膨化使其占满整个栅格［10］，此过程，如图1（b）所示。

图1 障碍物的两个膨化过程Fig.1 Two Expansion Processes of Obstacles

最后是编码过程，将障碍物栅格使用元素1表示，意味着机器人无法通过；将自由栅格使用元素0表示，意味着机器人可以自由通过。按照上述编码方式，可以得到机器人能够识别的0～1矩阵模型为：

2.2 问题描述与建模

机器人在栅格环境下进行路径规划，以路径长度最小、转弯角度最小为优化目标。

（1）路径长度模型。将机器人路径拐点数量记为G，并将起点坐标记为(x0，y0)，终点坐标记为(xG+1，yG+1)，则机器人的路径长度为：

式中：y1—机器人路径长度。

（2）转弯角度模型。根据机器人运动的实际情况，机器人的转角以前进方向的夹角作为度量。以拐点i处的转角为例，如图2所示。图中第一段路径为转弯前的前进方向，后一段路径为转弯后的前进方向，转弯前后前进方向的夹角θi即为转角i处机器人转角。

图2 转角示意图Fig.2 Corner Diagram

则机器人由起点到终点行驶过程中的转角为：

（3）约束条件。机器人路径规划的约束条件为机器人不能与障碍物发生碰撞，通过障碍物的自身膨化过程，只要机器人路径与障碍物栅格没有交集就能够保证机器人行驶时的无碰撞。

3 串行异构蚁群算法

为了在栅格环境下实现距离最短、转角最小的路径规划目标，本节在分析标准蚁群算法基础上，提出了具有两个异构品种蚂蚁串行组成的蚁群算法。

3.1 标准蚁群算法分析

蚁群算法是从蚂蚁寻找食物的过程中获得的灵感而提出的，其基本过程是蚂蚁依赖自身对食物的感知向食物方向运动，行驶过程中蚂蚁会释放信息素，其余蚂蚁在食物感知和信息素共同引导作用下移动。

将上述过程抽象为数学过程，在t时刻蚂蚁由节点i选择节点j的概率pij(t)为［11］：

式中：τij(t)—t时刻节点i与节点j之间的信息素浓度；α—信息素启发系数；ηij—节点j的启发因子，一般有，其中，djO—节点j与目标节点距离；β—距离启发系数；allowedi—栅格i邻域的自由栅格集合。

蚂蚁在寻找食物过程中，信息素更新包括信息素挥发和信息素残留两个过程，则算法完成一次迭代后的信息素更新方法为：

式中：ρ—信息素的挥发系数；Δτij(t)—蚂蚁种群在路径ij的信息素残留；M—种群中的蚂蚁数量；—蚂蚁k在路径ij上的信息素残留；dk—蚂蚁k规划的路径长度。

标准蚁群算法在栅格环境下进行路径规划存在以下不足：（1）算法初始时刻，信息素为均匀分布状态，信息素浓度启发作用极小，算法的收敛速度较慢；（2）标准蚁群算法只能用于路径最短的路径规划，对于多目标规划无法实现；（3）在八叉树或四叉树栅格环境下，蚂蚁只能沿0°、±45°、±90°、±135°等方向前进，这些方向未必是最优前进方向。为了解决上述问题，分别提出了信息素非均匀初始化、角度启发因子、异构蚂蚁串行等策略。

3.2 信息素非均匀初始化

如前文所述，标准蚁群算法中信息素的均匀化分布使得算法收敛速度极慢。针对这一问题，本节提出了信息素非均匀初始化方法。当工作环境中不存在障碍物时，则起点与终点连线为最优路径；当环境中存在障碍物时，最优路径一般紧邻起点与终点连线。按照这一常识，将与该连线距离小的栅格赋予较大信息素浓度，与该连线距离较大的栅格赋予较小信息素浓度。则根据信息素非均匀初始化方法，节点i的信息素浓度为：

式中：τi(0)—初始时刻节点i的信息素浓度；τ0—信息素浓度基础值；Δτi—信息素附加值；dSi—起点S与节点i的距离；diO—节点i与目标节点O的距离；ε—权值。一般来讲，选择点越靠近目标节点则路径越优，则ε应取较小值，使终点在信息素初始化中起主导作用，本节取ε=0.1。

分析式（5）可知，初始信息素浓度分布基本规律为：信息素沿起点与终点连线浓度最大，以此直线为对称轴，信息素浓度向外逐渐减小。

3.3 角度启发因子

标准蚁群算法中只有距离和信息素两类启发因子，路径规划时只能进行路径最短的优化，为了同时实现路径转弯最小的优化，本节引入了角度启发因子。蚂蚁当前节点记为i，下一节点记为j，终点记为O，则角度启发因子定义为：

式中：vij—角度启发因子；θij—定义的角度值。角度启发因子随角度的变化曲线，如图3所示。

图3 角度启发因子曲线Fig.3 Curve of Angle Heuristic Factor

结合式（6）和图3可知，θij∈[0，180°]，相应的vij∈[1，0]。这意味着当蚂蚁直线行驶时，θij=0，此时角度启发因子最大为1；当蚂蚁转弯角度最大时，θij=180°，此时角度启发因子最大为0；且角度启发因子随角度值的增大而减小，这一规律符合角度启发因子的设计思路。

将角度启发因子引入到式（3）中，得到改进的选择概率式为：

式中：γ—角度启发系数。

3.4 异构蚂蚁串行策略

标准蚁群算法在栅格环境下一般具有四叉树和八叉树两种情况，在四叉树情况下，蚂蚁只能沿0°、±90°、180°方向前进；在八叉树情况下，蚂蚁只能沿0°、±45°、±90°、±135°、180°方向前进。但是上述方向未必是最优前进方向，使得规划的路径未必为最优路径。

为了解决上述问题，本节提出了异构蚂蚁串行策略，其核心思想为：在蚁群中设置两个品种的异构蚂蚁，第一类蚂蚁为常规的规划蚁，按照式（7）进行栅格选择和路径规划，在蚁群中占绝大多数；第二类蚂蚁为具有全局通视能力的蚂蚁，用于路径的再次优化。两类蚂蚁按照串行方式工作，搜索蚁首先进行路径规划，而后通视蚁进行路径再优化。

在种群中通视蚁设置2只，全部放置在起点栅格。2只通视蚁工作原理不同，通视蚁1为由前向后优化，通视蚁2为由后向前优化。假设机器人路径中具有G个拐点，则通视蚁1的工作方法为：蚂蚁1立足于起点栅格，向拐点2进行通视，若中间没有障碍物则再次向拐点3进行通视，依次向下搜索，直至起点与第i+1个拐点无法通视，则起点与拐点i的直线连接为此段优化路径；蚂蚁1重新立足于拐点i，重复上述过程，直至路径优化完毕。

通视蚁2的工作方法为：蚂蚁2立足于起点栅格，向终点进行通视，若中间没有障碍物，则起点与终点连线即为最优路径，否则向拐点G-1进行通视，依次向前搜索，直至起点与第i个拐点能够通视，则起点与拐点i的直线连接为此段优化路径；蚂蚁2重新立足于拐点i，重复上述过程，直至路径优化完毕。

3.5 基于串行异构蚁群的路径规划流程

经上述分析和改进，制定基于串行异构蚁群算法的机器人路径规划流程为：

（1）三维工作环境进行降维和建模，得到二维0-1矩阵模型；

（2）进行蚁群算法参数设置，包括蚁群规模M、算法迭代次数、信息素挥发系数ρ、信息素启发系数α、距离启发系数β、角度启发系数γ；

（3）按照式（5）进行信息素浓度非均匀初始化；

（4）将所有规划蚁放置在起始点，并按照式（7）进行栅格选择；

（5）当所有规划蚁完成一次迭代，进行信息素更新，迭代次数+1；

（6）是否达到最大迭代次数，若否则返回（4）；若是则给出规划蚁得到的最优路径；

（7）通视蚁1和通视蚁2按照各自的工作原理进行路径再次优化，并比较优化结果；

（8）输出再次优化后的最优路径，算法结束。

4 仿真验证及分析

为了对串行异构蚁群算法的规划性能进行验证，在（10×10）和（20×20）两种规模的栅格环境下进行仿真和验证。仿真环境为Windows 操作系统，处理器Inter（R）Core（TM）i5-7200U，CPU 2.5GHz，内存12GB，MatlabR2018a软件。

4.1 （10×10）规模栅格

在（10×10）规模栅格环境下，起点坐标为（0.5，0.5），终点坐标为（9.5，9.5）。分别使用标准蚁群算法、文献［12］超强启发蚁群、本文串行异构蚁群等3种蚁群算法进行路径规划。算法参数设置为：蚁群规模M=60、算法迭代次数为200、信息素挥发系数ρ=0.4、信息素启发系数α=1、距离启发系数β=1、角度启发系数γ=2。为了保证公平，三种算法使用相同的参数设置，且各自独立规划10次路径。标准蚁群算法、超强启发蚁群算法规划的最优路径，如图4所示。串行异构蚁群算法规划蚁路径，如图4（c）所示，再次优化路径，如图4（d）所示。对比图4可知，在（10×10）规模栅格环境下，标准蚁群算法路径长度为14.484，拐点数量为6个；超强启发蚁群算法路径长度为14.484，拐点数量为5 个；串行异构蚁群算法路径长度为14.193，拐点数量为2个。

图4 （10×10）规模不同算法规划路径Fig.4 Path by Different Algorithm Under（10×10）

从路径场地和拐点数量的角度看，串行异构蚁群算法规划的路径质量明显优于标准蚁群算法和超强启发蚁群算法。

为了进一步进行比较，统计10次规划结果平均值结果，如表1所示。

表1 规划路径参数对比Tab.1 Path Parameters Comparison

对比表1中数据可知，串行异构蚁群算法收敛时平均迭代次数为69，远小于另外两种算法，这是因为串行异构算法的信息素使用非均匀初始化方法，极大提高了算法前期的搜索效率；串行启发算法规划的路径拐点数量远小于另外两种算法，这是因为改进算法中引入了角度启发因子，优先选择直线路径，且使用通视蚁进行了路径再次优化，有效减少了路径拐点数量，同时缩短了路径长度。

4.2 （20×20）规模栅格

在（20×20）规模栅格环境下，起点坐标为（0.5，0.5），终点坐标为（19.5，19.5）。分别使用标准蚁群算法、文献［12］超强启发蚁群、本文串行异构蚁群等3种蚁群算法进行路径规划。算法参数设置与前文一致，三种算法各自独立规划10次路径。

标准蚁群算法、超强启发蚁群算法规划的最优路径，如图5所示。串行异构蚁群算法规划蚁路径，如图5（c）所示。再次优化路径，如图5（d）所示。

图5 （20×20）规模不同算法规划路径Fig.5 Path by Different Algorithm Under（20×20）

对比图4（a）、图4（b）、图4（d）可知，在（20×20）规模栅格环境下，标准蚁群算法路径长度为36.624，拐点数量为16个；超强启发蚁群算法路径长度为36.968，拐点数量为18个；串行异构蚁群算法路径长度为33.898，拐点数量为4个。

从路径场地和拐点数量的角度看，串行异构蚁群算法规划的路径质量明显优于另外两种算法。为了进一步进行比较，统计10次规划结果平均值，结果，如表2所示。

表2 路径参数对比Tab.2 Path Parameters Comparison

对比表2中数据可知，串行异构蚁群算法收敛时平均迭代次数为73，远小于另外两种算法，这是因为串行异构算法的信息素使用非均匀初始化方法，极大提高了算法前期的搜索效率；串行启发算法规划的路径拐点数量远小于另外两种算法，这是因为改进算法中引入了角度启发因子，优先选择直线路径，且使用通视蚁进行了路径再次优化，有效减少了路径拐点数量，同时缩短了路径长度。

综合（10×10）规模和（20×20）规模栅格环境下的机器人路径规划结果，串行异构蚁群算法在栅格环境下机器人路径规划是有效的，且路径质量高于标准蚁群算法和超强启发蚁群算法。

5 结论

这里研究了机器人在栅格环境下的路径规划问题，以机器人路径最短和拐点数量最少为优化目标，提出了串行异构蚁群算法的规划方法。经仿真验证得出了以下结论：

（1）信息素非均匀初始化方法可以有效提高算法前期的搜索效率，减少算法收敛时的迭代次数；

（2）从路径长度和拐点数量的角度讲，串行异构蚁群算法在不同规模栅格环境下规划的路径质量优于标准蚁群算法和超强启发蚁群算法。