李维维，李建东

（唐山工业职业技术学院自动化工程系，河北唐山 063299）

1 引言

当前，移动机器人广泛应用于工业生产、军事侦查、医疗保健等诸多领域，导航是实现移动机器人智能化的关键技术之一。路径规划是机器人导航的基础，主要内容是根据已知的工作环境设计一条从起始点到目标点的安全路径[1]。导航路径的优劣决定了机器人的工作效率和安全性，具有极大的研究价值。

根据研究重点的不同，机器人路径规划的研究可分为两个阶段。前一阶段的研究重点为环境建模方法，研究成果包括可视图法[2]、Voronoi图、栅格法等。可视图法在1979年提出，由于此方法安全性不高，因此出现了Voronoi图法，此方法要求路径与障碍物保持一定距离，因此安全性得到了较大提高[3]。栅格法是环境建模简单而有效的方法[4]，其缺点在于障碍物膨胀时损失了部分自由行驶空间。路径规划后一阶段的研究重点为智能算法，以前一阶段建立的环境模型为基础，尝试将不同的智能算法应用于路径规划中。文献[5]针对遗传算法在路径规划时初始种群具有盲目性和随机性的问题，对初始化方法进行了改进，在不同环境下均得到了较优路径；文献[6]以农田用机器人为研究对象，提出自适应蚁群算法的最短路径规划方法，实现了在作物种植区的路径优化；文献[7]将路径最短和转弯次数最少同时作为规划目标，将两者融入到目标函数中，使用遗传算法进行求解，得到了转弯次数较少的平滑路径。针对不同使用环境、使用背景和任务要求，机器人路径规划目标和所用算法差别较大，因此机器人路径规划在较长时间内仍是研究的热点问题。

研究了移动机器人在栅格环境下的导航路径规划问题，提出了启发式信息素交流异构双种群蚁群算法，使用启发式信息素交流方式将蚁群系统和精英蚂蚁系统进行有效融合，实现优势互补，将融合算法命名为启发式信息素交流双种群蚁群算法，使用此算法进行栅格环境下路径规划，缩短了机器人的工作路径，同时提高了规划稳定性。

2 两种基础算法与优势互补分析

2.1 精英蚂蚁系统

精英蚂蚁系统（Elite Ant System，EAS）依据启发因子和信息素浓度构造选择概率，算法每完成一次迭代则对最优路径进行额外信息素奖励。状态转移概率为[8]：

式中：p kij(t)—蚂蚁k迭代t次时由城市i转移到j的概率；τij(t)—城市ij间的信息素浓度；α—信息素因子；ηij(t)—城市ij间的启发信息；β—启发信息因子；allowed i—城市i的可选城市。

完成一次迭代后，对最优路径的信息素浓度进行额外奖励，更新方法为[9]：

式中：m—蚂蚁数量，Δτk

ij—蚂蚁k留下的信息素浓度，e—最优路径奖励因子，Δτbs

ij—最优路径奖励的信息素浓度，C bs—最优路径长度，T bs—最优路径。

2.2 蚁群系统

蚁群系统（Ant Colony System，ACS）与精英蚂蚁系统的区别体现在三个方面：一是城市选择规则不同，二是全局信息素更新规则不同，三是增加了局部信息素更新。

在蚁群算法中，下一城市选择规则为[10]：

式中：q0∈(0,1)—一个常数，用于调节选择规则；q—［0，1］间随机数；j—选择的下一城市；J—使用轮盘赌（即式（1））选择的下一城市。

蚁群算法的信息素全局更新方法为：

式中：ρ—信息素挥发率。

全局信息素更新在所有蚂蚁完成一次迭代后实施，而局部信息素更新实时完成，蚂蚁每走一步则进行一次信息素更新。局部信息素更新为：

式中：τ0—信息素浓度初值。

局部信息素更新可以有效降低不同路径上的信息素浓度差异，对种群多样性的保持具有重要意义。

2.3 算法优势分析与优势互补

分析精英蚂蚁系统和蚁群系统可以看出，精英蚂蚁系统使用的全局信息素更新方法，可以使蚂蚁迅速聚集在当前最优路径附近，具有极快的收敛速度。其缺点是蚂蚁的多样性下降较快，且容易陷入局部最优路径。

蚁群系统信息素更新方法为全局更新与局部更新的叠加，局部信息素使用实时更新方法，可以有效降低不同路径的信息素浓度差别，可以有效保持蚂蚁的路径多样性。其缺点是算法的收敛速度慢。

由精英蚂蚁系统和蚁群系统的优缺点分析可以看出，两种算法在优势上具有极强的互补性，因此可以将这两种算法进行融合，通过信息交流实现优势共享。

3 启发式信息素交流双种群蚁群算法

为了实现精英蚂蚁系统与蚁群系统的优势互补，使用启发式信息素交流方式构造了异构双种群蚁群算法。算法前期降低两个种群间的交流频率，使两种算法各自进行搜索，可以有效提高路径多样性，扩大算法对搜索空间的覆盖率；算法后期提高种群交流频率，对路径上的信息素浓度分布进行交流，强化公共最优路径上的信息素浓度，可以提高算法在后期的收敛性。

3.1 路径偏离度

算法每完成一步迭代，精英蚂蚁系统与蚁群系统都会产生各自的解集，记精英蚂蚁系统搜索到的路径集合为m1=，蚁群系统搜索到的路径集合为m2=。路径偏离度定义为当前路径集合的聚合程度或偏离程度，用于衡量每次迭代完成后路径与最优路径的偏离程度，即：

式中：σ—路径偏离度；Cexp—期望路径长度，在测试函数中定义为测试库的最优路径标准值，在路径规划中定义为当前最优路径长度C bs；C i—蚂蚁i的路径长度。

分析式（6）可知，当蚂蚁搜索的路径集中在当前最优路径附近时，路径聚集程度高，此时σ值较小。当蚂蚁搜索的路径分散度较大，也即路径多样性较好时σ值较大。因此可以使用路径偏离度σ描述路径的分散程度。算法运行初期，路径的多样性好，相对于最优路径的分散程度较高，因此σ值较大；随着算法运行，当前最优路径上的信息素浓度不断提高，蚂蚁搜索路径向当前最优路径附近集中，路径多样性下降，同时路径分散程度降低，此时σ值不断减小且趋于稳定。

3.2 种群间启发式交流频率

种群间信息交流频率对算法性能影响较大，若每完成一步迭代就进行一次信息交流，不仅增加了算法复杂度，也会造成公共最优路径上信息素浓度的过快积累，极易使算法陷入局部最优。

算法前期，两种算法迭代次数较少，各自的最优路径参考价值不高，因此应该适当降低交流频率，保持两个种群各自的多样性；随着算法运行，两种算法均经过较为充分的搜索，各自的最优路径具有较大的参考价值，此时应适当提高种群间的交流频率，通过公共最优路径的叠加作用，使算法快速收敛。基于以上考虑，本文提出了启发式算法用于调节种群间的交流频率，达到降低算法复杂度和提高算法性能的目的。启发式函数为：

式中：T—要执行的操作；Q—种群间进行信息交流；Qˉ—种群间不进行信息交流；q—（0，1）间随机数；k—待定常数，当优化问题规模较小时，偏离度σ的下降趋势明显，此时应当设置较大的k值，当优化问题规模较大时，偏离度σ的下降趋势缓慢，此时应设置较小的k值调节Q的发生概率。

分析式（7）可以看出，算法前期路径分散程度较大，偏离度σ值较大，信息交流发生的概率较小，两种算法各自按照自身模式搜索，使更多路径被蚂蚁探索，非常有利于路径多样性的保持和算法复杂度的降低。随着算法运行，两种算法各自搜索的路径价值较高，σ值不断减小，信息交流频率增加，具有价值的路径信息在种群间进行交流，公共最优路径的信息素浓度叠加，对算法收敛具有重要作用。

3.3 种群间信息交流方式

种群间信息交流方式多种多样，本文为了充分发挥精英蚂蚁系统和蚁群系统各自的优势，实现两种算法之间的优势互补，设计了种群间信息素交流方式为：

根据前文的分析，精英蚂蚁系统在算法前期的搜索性能较强，且算法的收敛速度较快，式（8）将这两个优势有效融入到了蚁群系统中。分析式（8）可知，算法前期σ值较大，因此大概率地使用精英蚂蚁系统的最优路径信息素浓度替换蚁群系统的一个随机路径浓度，使精英蚁群算法的优质解给蚁群系统提供参考。随着算法迭代，两个算法的最优路径重合度越来越高，σ值也逐渐减小，大概率地使用精英蚂蚁系统的最优解替换蚁群系统的最差解，实现了公共最优路径的信息素浓度叠加，可以有效加快算法收敛。因此式（8）有效的将精英蚂蚁系统的优势融入到了蚁群系统中。

3.4 启发式信息素交流双种群蚁群算法流程

结合精英蚂蚁算法与蚁群算法的运行原理，将启发式信息素交流方式融入其中，得到启发式信息素交流双种群蚁群算法（Heuristic Pheromone Communication Two Population Ant Colony Algorithm，HEC—TPAC）流程为：

Step1：初始化算法参数，包括种群规模m、最大迭代次数tmax、信息素因子α、启发信息因子β、挥发系数ρ、常数q0；

Step2：精英蚂蚁系统和蚁群系统根据自身规则进行路径搜索，每完成一次迭代则计算路径偏离度，而后根据式（7）判断是否执行信息素交流，若需要进行信息素交流则进入Step3，否则转至

Step4；

Step3：根据式（8）确定进行信息素交流的方式；

Step4：判断是否达到最大迭代次数，若否则转至Step2；若是则输出最优路径，算法结束。

4 双种群蚁群算法性能分析与测试

4.1 测试集确定及参数设置

为了检验启发式信息素交流双种群蚁群算法的性能，使用标准TSP测试集的函数对算法性能进行检验。性能测试实验环境为：Windows 7操作系统，Intel酷睿i5处理器，2.5Hz主频，4G内存，仿真软件为Matlab R2018a。

从标准TSP测试集中随机选择3个中小规模城市作为测试案例，分别为KroA100、D198、KroB200。为了形成对比效果，分别使用双种群蚁群算法（HEC—TPAC）、精英蚂蚁系统（EAS）、蚁群系统（ACS）进行旅行商路径规划。为了防止随机性影响，三种算法对三个测试案例分别进行15次路径规划。三种算法的参数设置，如表1所示。

表1 算法参数Tab.1 Algorithm Parameters

4.2 测试结果分析

首先将三种算法对三个测试案例的最优规划结果迭代过程以图片形式给出，如图1所示。

从图1中三种测试案例的路径规划结果可以得出以下结论：（1）三种算法中，精英蚂蚁系统在算法前期的收敛速度最快，且算法极易陷入局部最优，这是因为精英蚂蚁系统对全局最优路径额外的信息素奖励，使算法具有较快的收敛速度，但是也容易陷入局部最优；（2）蚁群系统的规划质量一般优于精英蚂蚁系统，但是收敛速度差于精英蚂蚁系统，这是因为蚂蚁系统的信息素局部更新方法有利于保持路径多样性，但是也导致了收敛速度较慢；（3）三种测试案例中，双种群蚁群算法规划的路径最短，从收敛速度看，接近于精英蚁群算法，从这个角度讲，双种群蚁群算法有效融合了精英蚂蚁系统和蚁群系统的优势。

图1 测试案例规划结果Fig.1 Planning Result of Testing Case

为了进一步分析双种群蚁群算法的性能，统计三种算法对三种测试案例的最优解、平均解、平均迭代次数，如表2所示。在此给出三个测试案例的路径最优解实际值，KroA100最优路径长度实际值为21282，D198最优路径长度为15780，KroB200最优路径长度为29437。

分析表2中数据，从最优解误差看，HEC—TPAC算法规划的路径质量最高，与最优路径实际值的误差最小；从路径平均值看，HEC—TPAC算法规划的路径长度平均值最接近最优路径实际值，说明HEC—TPAC算法的路径规划稳定性最高；从平均迭代次数看，三种算法的收敛迭代次数相差不大，精英蚂蚁系统收敛次数最少，双种群蚁群算法与其几乎相当，蚂蚁系统平均收敛次数最大。以上分析结果表明，HEC—TPAC算法有效融合了精英蚂蚁系统和蚁群系统的优势，不仅具有最高的规划路径质量，而且算法稳定性最高。

表2 三种测试案例规划统计Tab.2 Planning Result Statics of Three Testing Case

5 移动机器人路径规划

5.1 栅格环境模型

首先建立机器人能够识别的环境模型，而后使用双种群蚁群算法进行路径规划。栅格环境模型原理简单、易于实现。使用一定大小的栅格对工作环境进行分割，当栅格中具有障碍物时则将栅格属性赋值为1，不存在障碍物的栅格属性赋值为0。当栅格中存在障碍物但未充满时，使用膨胀法使其占满一个栅格。此方法可将抽象的工作环境转化为机器人可识别的0—1矩阵。

如图2所示的某一工作环境，图中黑色区域为障碍物分布区域，使用栅格法得到的0—1矩阵模型为：

图2 真实工作环境Fig.2 Real Working Environment

使用双种群蚁群算法进行路径规划时，将所有蚂蚁放置于起始点，使用式（1）或式（3）计算选择周围相邻“0”属性栅格的概率，并依据各自规则确定最终选择的0属性栅格；而后立足于当前栅格，再次依据式（1）或式（3）选择周围相邻“0”属性栅格，直至到达目标点。在此需要强调的是，在旅行商问题中，式（1）和式（3）中的ηij(t)表示城市i j间距离的倒数，但是在机器人路径规划中表示城市j与目标点间距离的倒数，从而使目标点对蚂蚁的移动具有引力作用。

5.2 路径规划性能验证

为了检验启发式信息素交流双种群蚁群算法在栅格环境中的路径规划性能，设计了两种20×20栅格规模下的工作环境，两种工作环境主要区别体现在障碍物形状方面。由前文分析可知，精英蚁群系统极易陷入局部最优，规划能力最弱，因此本节使用蚁群系统和双种群蚁群算法两种算法进行规划并比较。两种算法对两种工作环境各自独立规划10次，选择两个算法规划的最优路径进行展示结果，如图3所示。

图3 两种工作环境下的规划结果Fig.3 Planning Result under the Two Environments

从图3中可以直观地看出，启发式信息素交流双种群蚁群算法规划的路径优于蚁群系统，为了进一步比较算法稳定性和收敛速度，统计两种算法在两种工作环境下的最优解、平均解、路径方差、收敛次数（搜索到最优解时的迭代次数），如表3所示。

表3 路径规划统计结果Tab.3 Path Planning Statistics Result

从表3中数据可以看出，在环境一中，HEC—TPAC算法的最优路径比ACS算法的最优路径缩短了5.57%；在环境二中，HEC—TPAC算法的最优路径比ACS算法的最优路径缩短了3.34%，说明HEC—TPAC算法的规划能力明显优于ACS算法。从路径方差看，HEC—TPAC算法在两种环境下的方差均远小于ACS算法，说明HEC—TPAC算法的规划稳定性极好。从收敛次数看，HEC—TPAC算法与ACS算法相差不大，但是HEC—TPAC算法略有优势，说明HEC—TPAC算法收敛速度略优于ACS算法。

综合以上分析可以看出，HEC—TPAC算法的规划质量、规划稳定性远优于ACS算法，收敛速度略优于ACS算法。

6 结论

研究了栅格环境下移动机器人的导航路径规划问题，提出了启发式信息素交流异构双种群蚁群算法，构造了基于此算法的路径规划方法。经性能测试和路径规划性能检验，得出了以下结论：（1）启发式信息素交流方式可以有效融合蚁群系统和精英蚂蚁系统的优势；（2）启发式信息素交流异构双种群蚁群算法的规划能力、规划稳定性优于蚁群系统和精英蚂蚁系统。