改进A*蚁群算法求解机器人路径规划问题*

万逸飞， 彭 力

(江南大学 物联网应用技术教育部工程中心，江苏 无锡 214122)

0 引 言

机器人的路径规划问题是指在有障碍物的环境中，寻找出一条从设定的起始点到目标点的无碰撞路径，并且此路径要求最短，路径搜索过程要求最快。机器人路径规划问题是导航与控制的基础，也一直是人工智能的热点问题。目前机器人路径规划的常用方法有：栅格法[1]，人工势场法[2]，A*算法[3]，神经网络[4]，遗传算法[5，6]，粒子群算法[7]等。其中神经网络算法需要频繁的调整网络权重，并且需要大量的训练样本；遗传算法计算量大，收敛太慢；粒子群算法简单，但是太容易早熟于局部最优；人工势场法[8]虽便于底层实时控制，但容易出现死锁、停滞以及陷入局部最优，并且障碍物较多时还会出现计算量过大等问题。虽然也有很多学者对它们的不足做出改进，但一直没有一个完美高效的结果。比如：朱毅等人[9]用“奔向目标”，“沿墙行走”等行为对人工势场法进行改进，避免了死锁、停滞等现象，但明显没有解决局部最优的问题。

虽然蚁群优化(ant colony optimization,ACO)算法也有一定的缺陷，但由于其具有正反馈、较强的鲁棒性、优良的分布式计算等优点，一直受广大学者关注。文献[10]将蚁群单向搜索目标方式变为双向并行搜索，加快算法的寻优速度。但是判断蚂蚁相遇的过程会消耗一定的时间，而且对于算法的寻优能力提高不大；文献[11]改变蚂蚁的搜索步长，由定步长搜索改为变步长搜索，加快蚁群算法收敛速度。但是蚁群算法前期效率低、耗时长的问题并没有解决；文献[12]将人工势场法与蚁群算法结合，并加入几何优化，从而提高算法的收敛速度与全局寻优能力。而且蚁群算法的生物机理就是蚂蚁在巢穴与食物之间找一条最短的可行路径。

本文也是基于蚁群算法进行移动机器人的路径规划。不过本文的蚁群算法结合了A*算法，加入了简化算子，并且对蚁群算法的启发函数以及信息素更新公式做出改进，从而加快了蚁群算法的收敛速度，大大提高了蚁群算法寻优能力。

1 栅格环境建模以及地图预处理

栅格法是目前环境建模方面应用最广泛的方法之一。该方法用黑白栅格分别表示不可行与可行区域。如图1所示，为了简化实际问题，确保运动的安全性，对每个障碍物进行膨胀，膨胀的宽度为机器人的半径[10]，这样机器人在仿真时就可以视为质点。

图1 障碍物栅格描述

此时路径规划问题就是从栅格地图的可行栅格中规划出一条从起点到目标点的最短路径。图2为10×10的栅格地图，假设栅格1是起始点，栅格100是目标点，对于图中的凹型障碍物，如若用人工势场法，很可能出现“死锁”现象。而用蚁群算法，部分蚂蚁也会出现“死锁”现象，或者在“死角”区域浪费较长时间。为了提高蚂蚁的效率，降低蚂蚁“死锁”的概率，本文路径规划前先对栅格地图进行处理。

图2 10×10的栅格地图

对于每个可行栅格进行判断，如果地图四边的栅格“活跃度”小于等于2，即周边的可行栅格数小于等于2，并且其周围的障碍栅格按顺时针方向，连续超过3个时，将此可行“死角”栅格视为障碍物。例如栅格71，其“活跃度”为1，并且其周围的4个障碍物按顺时针连续排列，故栅格71视为“死角”；如果中间的可行栅格“活跃度”小于等于3(最大为8)，并且周围的障碍物栅格按顺时针方向，连续超过5个时，视其为死角。例如：栅格35，5，9，都为“死角”，栅格65不是。对于“死角”栅格，如果它们不是起始点与目标点，在地图预处理时，直接将其变为障碍物栅格。

2 改进蚁群算法设计

2.1 A*算法产生初始信息素

传统的蚁群算法在初次搜索时，由于对地图信息匮乏，一般将信息素均匀分布，即每个可行栅格上的信息素都是常量，这导致蚁群初期进行“盲目”搜索。针对这一问题，本文利用A*算法决定初始信息素，从而加快算法初期的收敛速度，减少迭代次数。

A*算法为启发式路径搜索算法[13]，路径搜索主要根据一个路径评价

f(n)=g(n)+h(n)

(1)

这里g(n)为从起点s,沿着产生的路径，到方格n的移动消耗；h(n)为从方格n到终点g的预估移动消耗。

A*算法中有OPEN与CLOSED列表。其中OPEN中保存有待考查的可行相邻节点。CLOSED保存已考查过的节点。A*算法在寻路时，从起始节点开始，不断向外扩展，每次找OPEN列表中f(n)最小的节点，直到找到目标点。最终从目标点开始，沿着每一个栅格的父节点移动，直到回到起始点。本文将这条路径的初始信息素设为

τij(initial)=kc,k>1

3.设置的问题要有灵活性。同一教学方法可以解决不同的教学内容，不同的教学方法也可以解决相同的教学内容；同一教学方法面对不同的教学对象会产生不同的教学效果，不同的教学方法面对相同的教学对象也会产生不同的教学效果。因此，教学策略的运用要随着问题、目标、内容和教学对象的不同而改变。

(2)

其中k为初始信息素放大倍数，其余栅格上的信息素仍然保持常数c。

2.2 蚁群算法主体部分

(3)

(4)

式中dij为栅格i到下个一个可行栅格j的距离。传统的启发函数必将导致蚂蚁在选择下一格栅格时，更倾向于选择正方向的可行栅格。这里面并没有考虑终点栅格的位置，因此该启发信息函数还过于片面。本文对公式(5)改进

(5)

(6)

蚁群算法为了避免留下的信息素累积过多而淹没启发信息，每迭代一次，都会对信息素进行更新。但是传统信息素更新公式，对于优秀蚂蚁与劣质蚂蚁留下的信息素进行的是相同处理。这样不能充分显示出每代最优解的指导作用，同时劣质蚂蚁的信息素也相当于是一种干扰，这将降低蚁群的效率。本文为了提高蚂蚁的效率，对优秀蚂蚁与劣质蚂蚁产生的信息素进行不平等处理

τij(t+1)=(1-ρ)τij(t)+Δτij(t,t+1)

(7)

(8)

(9)

式中ρ为信息挥发系数，取值范围为[0,1]；Lk为第k只蚂蚁在本次循环中所走的路径总长度；Q是信息素强度。此处引入变量kLk，当Lk除inf外，在同一代蚂蚁中最大时，即劣质蚂蚁产生的路径，其值取0；当Lk大于同一代蚂蚁产生的路径中位值时，kLk取ka∈[0.5,0.9]；当小于中位值时，kLk取kb∈[1,1.2]；当Lk最小时，即最优蚂蚁产生的路径，其值取1.3。这样进行不平等的处理，便可拉大劣质蚂蚁与优秀蚂蚁产生的影响度，在保证路径信息素多样性的前提下，提高下一代蚂蚁寻优的效率。

2.3 简化算子

利用简化算子是为了去除冗余的拐点[14]。假设某规划路径如图3所示。

图3 原始路径图

将起始点，拐点以及终点依次标上序号：P1,P2,…,Pn，此图中n=7。接下来进行循环简化，第一次循环时，s=1。将点Ps与Pk(k=s+2,s+3,…,n)依次相连，看是否有连线不经过障碍物，即生成了新的可行路径。若存在这样的连线，则选择其中最大的k值，连接Ps与Pk，s更新为k-1；如无这样的连线，s更新为s+1。直至s为n-1,循环结束，即简化过程结束。图4是用简化算子，简化后的路径图。

图4 简化路径图

3 改进的A*蚁群算法步骤

1)初始化本文算法的参数；

2)根据初始化中的终起点位置，建立指定大小的栅格地图，并用本文中的方法对地图进行处理，去除死角；

3)用A*算法确定蚁群的初始信息素分布；

4)每只蚂蚁找到可行并且自己没有走过的栅格，用式(3)、式(5)、式(6)计算出去每个可选栅格的概率，并用轮盘赌法做最终选择。不断循环此操作，直至每只蚂蚁到达终点或者陷入“死胡同”，循环结束；

5)用改进的更新式(7)～式(9)更新上一代蚂蚁留下的信息素；

6)循环步骤(4)与步骤(5)，直至到达最大迭代次数。找出最优路径并用简化算子简化。

4 仿真对比分析

本文针对传统蚁群算法在路径规划方面应用的不足，做出了一些改进。下面在CPU为奔腾G2020的电脑上，用软件MATLAB2014b进行4组仿真验证。

首先与经典蚁群算法对比，选取20*20的地图，其障碍物覆盖率为21 %。初始化时，蚂蚁数量m=30，最大迭代次数K=200，α=1，β=16，ρ=0.15。图5(a)为基本蚁群算法(ACO)的路径规划图；图5(b)是应用本文3.1与3.2节改进的蚁群算法(improve ant colony optimization-main,IACO-M)的路径规划图，其中用A*算法形成的初始信息素放大倍数k=4；图5(c)是在图5(b)算法的基础上，加了地图预处理以及简化算子，即本文最终的IACO的路径规划图。图5(c)的地图看似与其他两个有所区别，实则是一样的，只不过经过地图预处理，将“死角”直接转化为了障碍栅格。它们路径总长度分别为33.7990，28.6274，27.6340。

图5 对比路径规划

表1 三种算法比较

为了进一步分析，将每个图对应的算法运行10次，取平均值，绘制表1，其中X为到达收敛的迭代次数。e为蚂蚁效率，随迭代次数增加，不断抖动上升的值。此处用第一次迭代能到达终点的蚂蚁数量进行衡量。由表1可证明本文算法改进的每个环节都起到了优化作用。相同参数的情况下，改进的蚁群算法，其蚂蚁搜索效率有所提高，收敛速度加快，路径长度更是大幅度缩短。

将本文算法与其他三个文献中改进的算法进行对比。文献[15]应用改进的遗传算法(简称IGA)进行路径规划。图6(a)是文献中最复杂地图的最优路径规划图，图6(b)是基于本文算法的路径规划图，它们的路径长度分别是30.384 8，29.460 1。达到收敛的迭代次数分别为20，14。

图6 IGA与IACO路径对比

文献[16]是A*算法与蚁群算法结合，并作出改进，这里简称AACO。图7(a)是文献[16]中的一张路径规划图，图7(b)是IACO基于相同地图的路径规划图。它们的路径长度分别28.627 5，28.006 0。达到收敛所耗费的迭代次数分别为15，22。

图7 AACO与IACO路径对比

文献[12]中算法是将人工势场法，几何优化与蚁群算法结合并改进，称为ACO-PDG。图8(a)是文献中的路径规划图，构建与文献中相同的栅格地图，应用本文IACO规划出来的路径如图8(b)所示。因为与文献方法不同，所以不能取一样的参数值进行对比，但可以基于相同的地图进行对比，此处参数初始化同之前的测试。图8(a)与图8(b)中地图有差别是因为本文算法将“死角”转化为障碍物，所以实则两地图是一样的。

图8 ACO-PDG与IACO路径对比

经对比，可以明显的看出本文的算法在路径长度方面是远远优于ACO-PDG的。为进一步验证算法的效果，实验10次，取平均值进行对比。其中表2中X为到达收敛的迭代次数，ACO-PDG的10次实验数据来自文献[12]。由表2可见，虽然本文算法的收敛速度没有文献[12]中的快，但路径平均长度比它短很多。而计算机的运行速度肯定比移动机器人的运动速度快很多，所以平均迭代次数多6.4所消耗的时间肯定比2.686 1的路径所消耗的时间少得多。而且本文算法规划的路径拐点更少，更方便机器人运动。

表2 ACO-PDG与IACO对比

5 结 论

仿真结果表明：本文算法相对于经典蚁群算法以及部分改进算法收敛速度加快。虽然相对于一些改进的比较好的蚁群算法，收敛速度还略慢，但是本文改进的蚁群算法全局寻优能力最强，即最终规划的路径其他算法短。