摘  要： 在传统蚁群算法基础上，采用随机选择和惯性保持相结合的方式搜寻节点，在获得不同路径的同时提高算法收敛速度。从已获得的路径两端沿惯性方向逼近优化，将无障碍中间节点剔除，减少机器人在最短路径上转弯次数的同时增强算法的搜索性能。通过自适应方式动态调整信息素，改善算法适应能力。仿真结果表明，通过以上改进能有效提升路径质量，可有效降低灭火机器人在室内环境中寻找火源的时间，提高灭火效率。

　　关键词： 蚁群算法；惯性方向；逼近优化；自适应

　　灭火机器人路径优化技术能够使机器人更加智能，从而可以代替消防员在火灾危险环境下进行救援工作[1]。对于灭火机器人而言，以最高效率找到一条从起始位置到目标位置（起火点）的最优无碰撞路径，是其可靠的基础。智能体路径规划问题[2]一直是机器人研究领域的一个重要组成部分，其由环境构建和规划方法两个方面构成。由于在日常生活中火灾发生具有不确定性，导致灭火机器人寻找火源的过程变得复杂，本文为了问题的简化将创建全局栅格地图，为灭火机器人路径规划提供静态环境模型。

　　目前基于栅格模型的路径规划有许多方法，如：蚁群算法、粒子群算法、A*、遗传算法等[3]。蚁群算法是一种仿生学算法，是模仿蚂蚁寻找食物过程中的行为，利用留在地面上信息素的释放和挥发，给后面的蚂蚁提供一定指向，当大群蚂蚁反复行走后，最终找到一条通往食物的最优路径[4]。同时，蚁群还能适应环境的变化，当蚁群运动路径上突然出现障碍物时，蚂蚁也能很快地重新找到最优路径。作为一种智能算法蚁群算法有其突出的优点：（1）蚁群算法具有自组织性，系统能在没有外界特定干预的情况下实现从无序到有序的变化；（2）作为并行算法，它具有空间多点同时进行独立解搜索的能力，不仅具有较高的可靠性，也具有较强的全局搜索能力；（3）具有较强的鲁棒性；（4）参数数目少，设置简单，易于实现其他组合优化问题的求解。传统的蚁群算法也存在其不足，如收敛速度较慢、求解的精度不高、容易陷入局部最优等问题[5]。为此，许多改进方案被提出，如最大最小蚂蚁系统MMAS（Max-Min Ant System）算法[6]、带有变异策略的蚁群算法和多蚁群算法等，但仍无法避免陷入死锁状态。

　　本文立足室内灭火机器人路径规划，主要从路径搜索策略、优化方法和信息素更新三个方面对蚁群算法进行改进，并通过仿真实验验证该算法的可行性和有效性。

　　1 算法设计

　　首先，以栅格法建立机器人工作环境，构建一个全局静态环境模型。其次，将算法分为两步施行。第一步实现路径搜索，采用随机选择和惯性保持相结合的策略，搜索过程不释放信息素。第二步进行路径优化，对已获得的所有路径采取端点逼近惯性优化，并对优化后的路径实现信息素动态更新。

　　1.1 构建工作环境

　　栅格法[7]是环境构建过程中被广泛使用的方法之一，它将智能体的工作空间转化为对应的栅格模型。用大小相同的栅格划分工作空间，灰色栅格代表障碍物，其他栅格代表自由空间。栅格法的特点是简单、易于实现，为路径规划带来很大方便，而且具有表示不规则障碍物的能力，适合于大规模并行处理机的实现。

　　本文采用栅格法构建工作环境，将一个平面空间等分成许多小格，一个小格就代表一个小区域，区域长宽为1个单位，任意两个节点的距离为两栅格中心点上的连线距离，并将小格按从左至右、从上到下的顺序编号。环境地图建完后，里面的颜色就代表空间的状况，如白色（0）代表可行，灰色（1）代表障碍物，绿色代表起始点，红色代表目标点。图1为栅格法表示的工作环境。

　　智能体在栅格空间节点的运行方向及节点距离由矩阵D表示，G为环境模型矩阵。

　　h=size（G，1）//矩阵行数

　　l=size（G，2）//矩阵列数

　　D=zeros（h*l，h*l）；

　　for i=1：h

　　for j=1：l

　　if G（i，j）==0

　　for m=1：h

　　for n=1：l

　　if G（m，n）==0//自由空间

　　im=abs（i-m）；jn=abs（j-n）；

　　if im+jn==1||（im==1&&jn==1）

　　D（（i-1）*h+j，（m-1）*l+n）=（im+jn）^0.5；

　　//可选节编号及距离

　　end

　　end

　　end

　　end

　　end

　　end

　　1.2 路径搜索

　　第一步以式（1）选择节点：

　　其中，Pij表示智能体在位置i时下一步选择节点j的概率；τij为节点i、j之间的信息素浓度；启发因子?浊jo为节点j到目标位置o之间距离的倒数，以引导智能体向距离目标最短的方向移动；?琢为信息素的重要程度；?茁为启发因子的重要程度；D为下一步可选择目标的集合；q为（0，1]的随机值；q0为[0.7-0.8]之间的阈值。

　　采用此方式能使智能体以较大的概率q0向信息素和启发因子乘积最大的目标位置移动，而以较小的概率（1-q0）使用随机比例原则选择目标位置[8]。这样既保证了智能体选择的方向性，又增加了智能体搜索的多样性，在避免搜索过程陷入死循环的同时，有效地提升了搜索时间。

　　1.3 端点逼近惯性优化

　　当M只蚂蚁完成一轮搜索后，将形成M条从起点到终点的路径，这些路径杂乱无序，传统的蚁群算法由于信息素更新模式的问题容易造成局部最优解，一般的解决方法在解决局部最优解的过程中容易导致运算时间延长。采用端点逼近惯性优化方法能进一步优化最短路径，把一些曲折的地方变成直线，减少转弯次数，同时增强算法的搜索性能。

　　端点逼近惯性优化的原理是：每次循环结束后，只对本轮搜寻的最短路径进行优化，从起始点（S）和目标点（O）开始同时相向遍历每个节点，当路径中有中间节点满足惯性条件时删除此节点，添加优化后的节点，继续优化，直到S逼近O且O逼近S，优化结束后将获得至少一条优化路径。惯性条件是指从保持原有运动且无障碍的行进线路方向。采用双向逼近优化可以获得多重解，为智能体回到出发点提供路线参考，有助于进一步提升算法的适应性。

　　设pi-1（xi-1，yj-1）为上一个节点，当前节点为pi（xi，yj），pi+1（xi+1，yj+1）为pi周围可选取的8个节点，pi+1为惯性点的条件为满足式（2）或式（3）：

　　为防止惯性过于突出而找不到最优路径，惯性优化方法可以在寻找过程中自动调整方向，但最多只能调整一次，也就是优化后最多存在1个转折点。由于前期在节点选择上具有较强的方向性（按照到目标点位置最短），因而惯性优化能在降低转弯次数的同时确保路径最短，对于降低智能体整体运行时间具有实际意义。惯性优化流程（以S到O为例）如图2所示。

　　1.4 信息素动态调整

　　每次迭代结束后，对当前最优路径进行信息素全局动态更新：

　　其中，?驻τij为此次循环的信息素增量，lmin表示当前最短路径的长度，ltmin为此次迭代最短路径的长度。?驻τij越大说明路径越短（新的更短路径已经产生），应当将后面的蚂蚁引向此路径上，因此应当增加信息素浓度。当找到最短路径时，信息素以一个较小的量增加，避免陷入死循环。

　　1.5 算法求解过程

　　根据以上描述，本算法步骤如下：

　　（1）栅格法建立工作环境，参数初始化，构造启发式信息。

　　（2）每只蚂蚁根据式（1）选择下一节点，记录已走过的节点位置和路径长度，更新禁忌表。

　　（3）循环执行步骤（2），直到所有蚂蚁都搜寻完毕。

　　（4）对最短的路径进行端点逼近惯性优化，并保存更新后的节点位置和路径长度。

　　（5）根据式（4）和（5）对全局进行信息素更新。

　　（6）循环执行步骤（2）~步骤（5），直到迭代结束。

　　2 仿真分析与参数测试

　　为验证此算法的可行性，在MATLAB7.11平台上进行仿真测试，所选参数设置如下：蚂蚁数M=50，最大迭代次数K=100，q为（0，1]的随机值，q0=0.7~0.8，?琢=1，?茁=10，ρ=0.3。实验结果如图3、图4所示。

　　由图3可知，虽然在路径长度上优化前后并没有发生变化，仍然为29.799，但可以看到优化后的路径质量明显优于优化前，在转弯次数上由14次降为4次。图4的横坐标代表迭代次数，纵坐标代表每轮迭代的最短路径，由图4可知优化后的算法在收敛性上要优于前者。不同环境下的测试表明，改进后的蚁群算法表现出较强的优越性，尤其在转弯次数和收敛性方面。仿真结果表明改进后的蚁群算法在降低转弯次数和运算时间方面有显著提高，从而证明了此算法的有效性和可行性。

　　在节点选择上采用方向性和随机选择相结合的方式既节约了收敛时间又可避免陷入死循环。采用端点逼近惯性优化对最短路径进行进一步优化，可以有效降低转弯次数，提高线路质量，降低灭火机器人在运动过程中的时间，同时为机器人回到出发点提供了路线参考。通过自适应方式动态调整信息素，改善算法适应能力。仿真结果表明，相比传统的蚁算法，通过以上改进能有效提升路径质量，可有效降低灭火机器人在室内环境中寻找火源的时间，提高灭火效率。

　　参考文献

　　[1] 贾翠玲，李卫国，郭文霞.改进蚁群算法在灭火机器人路径规划中的应用[J].内蒙古工业大学学报，2013，32（1）：50-55.

　　[2] 陈晋音，杨东勇，邹青华．AS－R移动机器人的动态避障与路径规划研究[J]．计算机科学，2012，39（3）：222-226．

　　[3] BENNET D J， MCINNES C R. Distributed control of multiro-bot systems using bifurcating potential fields[J]. Robotics and Autonomous Systems， 2010，58（3）：256-264.

　　[4] 何少佳，刘子扬.基于惯性蚁群算法的机器人路径规划[J].计算机工程与应用，2012，48（15）：245-248.

　　[5] 周明秀，程科，汪正霞.动态路径规划中的改进蚁群算法[J].计算机科学，2013，40（1）：314-316.

　　[6] 许瑞.基于蚁群优化算法的批调度问题研究[D].合肥：中国科学技术大学，2011.

　　[7] 赖智铭，郭躬德.基于自适应阈值蚁群算法的路径规划算法[J].计算机系统应用，2014，23（2）：113-119.

　　[8] 王沛栋.改进蚁群算法及在路径规划问题的应用研究[D].青岛：中国海洋大学，2012.

　　（收稿日期：2014-03-12）