基于改进蚁群算法的消防机器人路径规划

王宏北，黄 民，黄小龙，郎需强

(北京信息科技大学 机电工程学院，北京 100192)

0 引言

消防机器人属于特种机器人范畴，可以作为特种装备代替消防员进入不具有先验性的环境[1]。它集全地形的移动功能、探测功能和通讯功能于一体，并且能在短时间内以最高的效率找到一条从初始点到火情点的最优无碰撞路径[2]。

目前，常见的路径规划方法有很多，根据不同的应用场景及算法基本原理可分为传统算法、启发式算法和经验算法[3]。国内外学者灵活运用这些算法来进行路径规划，比如袁佳泉等[4]运用传统算法与启发式算法的融合算法——模拟退火蚁群算法规划出相对最优路径；槐创锋等[5]运用经验算法A*算法与动态窗口法的融合算法成功规避了路径上的动态障碍物；陈秋莲等[6]运用神经网络改进的粒子群算法快速规划出无碰撞平滑路径。

从路径规划角度来看,消防机器人的路径规划可以假设为已知环境信息，同时假设环境信息为静态信息[7]，在这两个前提下，机器人能在安全范围内从初始点出发，避开障碍物，到达起火点，完成灭火或者救援的动作。

本文为了满足实际需要将实际环境的三维空间简化为合理的二维平面，提出了一种用于消防机器人路径规划的自适应改进蚁群算法。使用栅格法进行环境建模，然后引入自适应算子自适应地调整信息素的更新过程，旨在平衡算法的收敛速度和跳出局部最优解的关系。Matlab仿真实验表明所提出的改进算法能够快速且有效地得到最优解。

1 经典蚁群算法及其改进算法

1.1 蚂蚁系统

蚂蚁系统(ant system，AS)由Dorigo首次提出，是一种启发于蚁群觅食行为的仿生算法[8]。蚁群在没有先验性的条件下找寻到一条从蚁巢到食物源的最优路径。系统由路径构造和信息素更新两部分组成。

蚂蚁系统的状态转移概率为

(1)

当蚁群完成一次路径遍历后，各路径会根据式(2)进行信息素的更新：

τij=(1-ρ)·τij+Δτ

(2)

式中：ρ为信息素的挥发率；Δτ为信息素增量，更新方式为

(3)

式中：Q为常量；Lk为第k只蚂蚁构造回路的总距离。选用蚁周系统模型是因为它依托于全局信息来更新信息素，有优越的性能。

算法的收敛性与多种因素有关，包括上文提到的信息素更新、启发式信息和每代蚁群之间的合作行为。算法本身的参数也在扮演着重要角色，会影响求解性能和效率。6个重要参数的影响如下：

α为信息素启发式因子。α值过大，会减弱算法的随机性；α值过小，算法会陷入局部最优解。

β为期望启发因子。β值过大，会加快算法的收敛速度，同时会不可避免地减弱随机性，陷入局部相对最优。

m为蚁群数量。m值过大，会出现重复解，增加时间复杂度。

ρ为信息素蒸发系数。它会影响最优路径的选择，ρ值过大，会排掉有效路径，影响最优值的搜索；ρ值过小，会搜索到更多的无效路径，影响收敛速度。

Q为信息素强度。Q值影响到算法的正反馈功能，影响算法能否在正反馈的作用下有效地找到问题的最优解。

G为最大进化代数。通常以G值最大代表算法运行终止，并输出当前群体中的最佳个体作为问题的最优解。

目前，蚂蚁系统还存在搜索时间过长、算法会停滞和陷入局部最优解等不足。针对这些不足，国内外学者提出了不同的优化方法，比如精英蚂蚁系统、排序蚂蚁系统、蚁群系统等，使算法快速有效地收敛。

1.2 精英蚂蚁系统

精英蚂蚁系统(elite ant system，EAS)是Dorigo依托于蚂蚁系统的第一次改进：重视全局最优蚂蚁，视为精英蚂蚁，对这些蚂蚁进行额外的信息素更新，增强正反馈[9]。后面的蚂蚁会更倾向于选择精英蚂蚁的路径，使算法能够快速收敛。信息素更新规则为

τij=τij+e·Q/L*

(4)

式中：e为精英蚂蚁的数量；L*为当前最优解的总长度；i和j为当前最优路径上的边。

但是在每一次迭代中额外增加的信息素，降低了后面蚂蚁的解的多样性。也就是说，在保证算法原有的搜索模式不变的情况下，虽然精英蚂蚁系统增大了最优路径的反馈强度，使得最优路径上的信息素逐渐增加，加大了对最优路径的开发，但是不可避免地减小了对其他路径的探索，多样性遭受了损失[10]，意味着基本蚁群算法中种群多样性与收敛速度的矛盾依然存在，精英策略使算法过早地集中于部分最优候选解，收敛于局部最优解，不利于提高算法的全局寻优能力。

1.3 排序蚂蚁系统

Bullnheimer等借鉴遗传算法策略提出了排序蚂蚁系统(rank ant system，RAS)，它是一种针对精英蚂蚁系统的改进算法，主要针对算法多样性减小的问题。排序蚂蚁系统不仅增加了最优路径上的信息素，也按照构造的路径长度增加了较优路径上的信息素，使得较优路径上的信息素有一个阶梯似的分布，增加了多样性。改进后的信息素更新策略为

(5)

(6)

若(i,j)属于第μ只较优蚂蚁路径，则：

(7)

式中：σ为一个常数，是预设的较优蚂蚁的个数；Lμ为第μ只较优蚂蚁的路径长度。

排序策略保留了精英策略的同时考虑了较优个体的智能行为，使得后续蚂蚁的路径选自于带有权重系数的全局最优蚂蚁和较优蚂蚁的信息[11]。但是这是一种弱开发，因为算法还是仅限于蚂蚁走过的较优路径，如果算法一开始就陷入了局部最优，算法仍然无法跳出局部最优。

1.4 蚁群系统

蚁群系统(ant colony system，ACS)优于上述两种经典的改进算法，它对信息素量和信息素增量进行初始化，同时对局部和全局进行信息素更新，通过设置限制性候选列表来提高算法的收敛速度，并通过局部搜索方法来提高多样性[12]。更新策略根据式(8)～(10)计算。

1.4.1 局部信息素更新

τij=(1-∂)·τij+∂·τ0

(8)

式中：∂为局部信息素挥发率；τ0为初始信息素量。在每一代中，减少了蚂蚁经过路径上的信息素，而信息素越大的路径被选择的概率较大，因此可以认为此方法减少了最优路径上的信息素，提高了算法在每一代中的多样性，且随着蚂蚁数的增加，多样性增加的程度变大。

1.4.2 全局信息素更新

τij=(1-ρ)·τij+ρ·Δτij

(9)

1.4.3 路径构造函数

(10)

式中：s为选择的下一个节点；S为AS算法得到的下一个节点；D为当前节点的可选节点；q为随机数；q0为可设置的常数，且q0∈[0,1]。

1.4.4 局部搜索

每只蚂蚁构造好解之后，利用局部搜索进一步优化。其类似于一种变异操作，提供了跳出局部最优解的可能性，同时可提高算法的多样性。

1.4.5 限制性候选列表

选择下一节点时先从最近的n个节点中选择，减小算法在前期构造解的时间，可大大减少算法运行时间。

2 自适应改进蚁群算法

蚁群算法的主要工作就是在大量解中寻求最优解。寻求最优解可分为两部分：每个单独个体构造解与群体之间的信息交流。上文提到的算法侧重于通过小部分的子集行为来影响整个算法的收敛，不注重迭代过程中集合的智能进化[13]。倘若把这些信息进行整合，考虑周全，就可以提高种群的多样性。但在这期间也会出现收敛速度下降、算法复杂度增加的现象，这是因为没有进行筛选，直接利用了所有蚂蚁的所有信息。

为了解决以上问题，本文提出一种利用群体信息且不会影响算法的其他性能的改进算法。在统计学中，数据分布特征可以从集中趋势、离散程度还有分布形状3方面来考虑。平均数在统计学中具有重要的地位，是集中趋势的最主要测度值。本文借鉴统计学思想，不仅选取每代最优值，还提取了平均值和最差值来代表这一代的蚂蚁信息来进行信息素的更新。

本文在上文几种经典优化算法的基础上，融合了自适应算子进行局部信息素更新。局部信息素更新策略为

τij=(1-ρ)·τij+ρ·Δτij

(11)

式中：ρ为局部信息素挥发率，为可调参数；Δτij由式(12)给出：

(12)

式中：σ为精英蚂蚁的数量；Lbest为每代中最优的路径长度；Lpoor为每代中最差的路径长度；L为每代中次优蚂蚁的路径长度；Lave为每代中平均的路径长度。

全局信息素的更新方式借鉴了蚁群系统，更新策略为

τij=(1-α)·τij+α·Δτij*

(13)

3 实验结果与仿真

为了验证本文提出的自适应改进蚁群算法的有效性，在Matlab中的二维栅格图下，进行了算法的仿真实验。在栅格图内，以1表示栅格内是障碍物，以0表示栅格内为空；机器人被抽象为质点，以栅格为单位以八邻域法进行移动。

首先本文将4种经典算法和自适应改进蚁群算法运用于简单障碍环境下(栅格数20×20)进行路径规划。然后为了模拟火灾事故现场的复杂地形情况，将5种算法运用于复杂环境(栅格数50×50)。

在简单环境下先后设置了U型障碍物和E型障碍物。算法的参数设置情况如表1所示。

表1 算法的参数设置

在U型障碍物的栅格图下，将起点设置为(0,20)，终点设置为(20,0)，各算法的全局最优路径轨迹和迭代情况如图1和图2所示。自适应改进蚁群算法和4种经典算法并无大的差别，均能找到最优路径。

图1 右侧U型碍障物全局最优路径轨迹

图2 右侧U型碍障物迭代情况

不改变起始点的位置，将U型障碍物左移，此时启发式的理想路径经过了U型障碍物的内部，提升了算法解的难度。如图3和图4所示，4种经典算法在开始遇到障碍物时总是陷入局部最优的困境，而自适应改进蚁群算法能快速准确地找到最优路径。

图3 左侧U型碍障物全局最优路径轨迹

图4 左侧U型碍障物迭代情况

在E型障碍物的栅格图下，将起点设置为(20,20)，终点设置为(15,6)。如图5和图6所示，4种经典算法在起点和E型障碍物的第一个缺口总是陷入局部最优解的困境，所以这两处经典算法的多样性较差，找不到全局最优解。而自适应改进蚁群算法能很快摆脱局部最优的困境，顺利找到局部最优解。

图5 无缺口E型碍障物全局最优路径轨迹

图6 无缺口E型碍障物迭代情况

当不改变起始点的位置，在E型障碍物的中线位置开一个2×2的缺口时，如图7和图8所示，4种经典算法陷入局部最优的麻烦大大缓解，自适应改进蚁群算法的收敛速度是5种算法中最快的。

图7 有缺口E型碍障物全局最优路径轨迹

图8 有缺口E型碍障物迭代情况

为了进一步证明算法的有效性，本文设置了栅格数为50×50的复杂地形图。将起点设置为(0,50)，终点设置为(50,0)，并包含各种形状障碍物。各算法路径轨迹如图9所示。进行了10次同地形图的对比试验，比较4种经典算法和自适应改进蚁群算法的最优值、平均值、离散程度(标准差)、最优值次数，具体数据如表2所示。

图9 复杂碍障物全局最优路径轨迹

表2 算法的性能分析

从表2可以看出，自适应改进蚁群算法能得到最优路径，且最优值次数明显多于4种经典算法；RAS相比于EAS未见明显提升，与前文描述一致，这是由于RAS优化的局限性导致；ACS因为出现了停滞行为而未得到最优解，也更印证了自适应改进蚁群算法的优越性。

4 结束语

本文针对4种经典蚁群算法收敛速度慢、容易陷入局部最优解和效率低等缺陷，提出了一种自适应改进蚁群算法。算法对每一代蚁群进行数据分析，选取每代蚂蚁信息的最优值、均值和最差值来进行信息素的更新，防止算法迭代过程中欠拟合的发生，提高了算法的收敛速度。经过仿真验证，自适应改进蚁群算法得到最优路径的概率能达到90%，与其他算法相比，达到了最优，同时也具有较快的收敛速度。