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

,，，,

(西安工程大学机电工程学院，陕西 西安710048)

0 引言

移动机器人在仓储物流中作用日益增大，而最重要的就是让机器人自主路径规划来代替人工进行作业，路径规划的目的是寻找从起点到目标点的最优路径或者近似最优路径[1-3]。路径质量对机器人工作稳定性和仓库运行效率起着至关重要的作用。

国内外学者对通过改进算法来解决路径规划问题做了大量的研究，而蚁群算法被认为是解决路径规划算法有效算法之一，基本蚁群算法在解决路径规划问题时还存在一定的缺陷，近些年来众多学者对其进行了一定的改进，取得了不错的效果。万逸飞等[4]引进A*算法确定蚁群的初始信息，加入了算子，并对算法的信息素更新公式和启发函数进行了改进，虽全局寻优能力增强，但收敛速度还略慢。曹新亮等[5]构造新的数学模型对初始信息素进行差异化设置，提高了算法收敛速度，但在路径寻优上还有待改进。李任江等[6]在对启发函数进行改进时引入了方向系数，融合了局部和全局信息素的更新方式，考虑到安全距离的影响，仿真结果提高了算法收敛速度且路径距离更短，但存在搜索结果不稳定问题。张苏英等[7]采用自适应调整伪随机状态转移策略改变参数值避免算法早熟，其次，改进信息素更新方式加快算法收敛速度，但最优路径长度还需改进。王苏彧等[8]提出一种信息素挥发因子自适应策略，改进启发信息的距离评价函数以达到搜索速率快，迭代次数更少的目标，但寻优路径长度未能得到改善。

机器人路径规划属于非确定性复杂问题[9]，本文针对蚁群算法在路径规划时易陷入局部最优，搜索效率不高的问题，提出一种基于方向夹角的启发因子，在对启发函数改进时结合了A*算法估价函数思想，同时让信息素挥发系数满足拉普拉斯概率分布变化。

1 环境建模

本文采用栅格地图进行建模，如图1所示。其中黑色栅格表示有障碍物，白色栅格表示无障碍物，考虑到机器人体积，障碍物形状等问题对环境中的障碍物栅格进行膨化处理，即对于障碍物大小不足1个栅格当作1个栅格处理。

图1 环境建模

2 基本蚁群算法

蚂蚁在觅食过程中受到信息素浓度和距离启发函数的影响[10]，t时刻，蚂蚁k从1个栅格移动到另一栅格的转移概率为

(1)

Α和β分别为信息素重要程度因子和启发函数重要程度因子；Ak为蚂蚁下一步所能访问所有节点的集合；τij(t)为t时刻路径中信息素浓度；ηij(t)为距离启发函数。

(2)

(3)

蚂蚁在完成1次路径循环后会对其信息素进行1次更新，根据式(4)～式(6)调整信息素。

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

(4)

(5)

(6)

3 改进蚁群算法

3.1 建立基于转角启发因子

在基本的蚁群算法基础上引入方向系数ε，来增加路径选择的指向性，避免了算法在搜索路径过程中因转弯角度过大而浪费时间。假设某时刻机器人在搜索过程中状态如图2所示，机器人先后经过a点、b点、c点和d点，当前机器人运行节点为a到b，c和d为下一过程的起点和终点，机器人处于节点b时与x轴所形成的角度为θ1，机器人处于节点c时与x轴所形成的夹角为θ2。由图2可知，当Δθ越大时机器人运行方向越靠近终点，期望值越大，设转角启发因子ζij为

(7)

图2 机器人路径搜索原理

ε为方向系数；θ1和θ2分别为机器人在节点b和节点c时与x轴所形成的夹角。

3.2 改进启发函数

基本蚁群算法并未考虑下一节点和目标点之间的距离[11]，这在一定程度上降低了算法的搜索效率，因此，本文引入A*算法的估价函数思想，当遇到自锁时可跳出。A*算法优点就是通过估计路径中当前节点与目标点代价来进行下一步选择，从而缩小搜索范围，提高搜索效率。估价函数表达式为

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

(8)

g(n)为起点到当前节点距离表示实际代价；h(n)为下一节点到目标点间距离表示估计代价。

改进后启发函数为

(9)

dij表示起点到当前节点的距离，相当于式(8)中的g(n)；djE表示当前节点到目标点的距离，相当于式(8)中的h(n)。

3.3 信息素挥发因子更新策略改进

传统蚁群算法中信息素常采用固定值，比较单一且并不适合蚂蚁寻路过程中信息素的分配量，前期由于路径中信息素含量低，加大了蚂蚁搜索的盲目性，后期路径中信息素含量积累太多降低了路径的选择性，因此采用固定的信息素值并不能满足最优路径搜索要求。基于以上分析，本文提出一种信息素挥发因子自适应调整策略[12-13]，使之满足拉普拉斯概率密度函数变化，如式(10)所示，信息素挥发因子拉普拉斯概率分布如图3所示。

(10)

μ为位置参数；b为尺度参数；当ρ=μ时取最大值。

图3 信息素挥发因子拉普拉斯概率分布曲线

由图3可知，前期选择信息素挥发因子较小，利于信息素积累，增加蚂蚁寻路的导向性，中期挥发因子较大加快算法的迭代速率，后期信息素挥发因子小，加快收敛。改进后蚂蚁t时刻从节点i到节点j的概率为

(11)

3.4 算法步骤

本文算法流程如图4所示，具体步骤如下：

a.栅格法建模。

b.设置算法参数，设置起始点和终止点位置。

c.将蚂蚁放置起始点开始寻路。

d.根据概率公式选择蚂蚁下一节点。

e.判断所有蚂蚁是否到终点，若到达执行下一步，否则返回步骤d。

f.根据改进后的更新规则进行信息素更新。

g.保存每只蚂蚁的路径长度，选择当前蚂蚁最优路径并与历史最优路径比较输出全局最优解。

h.判断是否达到迭代次数，若达到输出最优解，否则返回步骤c,继续寻路。

图4 算法流程

4 实验和结果分析

本文基于MATLAB软件，选择不同的环境地图进行仿真实验，设置蚂蚁个数为50，最大迭代次数为100，α=1,β=6，Q=1,ρ=0.3,分别选取2种不同的地图环境进行仿真，每种环境各运行30次。环境1中，机器人某次运行最优路径如图5所示，最优路径收敛曲线如图6所示。

图5 环境1下2种算法最优路径对比

图6 环境1最优路径收敛曲线对比

由图5和图6可知，在相对简单的环境中，基本蚁群算法在第7代得到路径最优解，此时路径长度为32.04，而本文算法在迭代第4次所得到的路径长度为29.21，且此时本文算法所得到的路径转折次数明显优于基本蚁群算法得到的路径。30次仿真实验取均值得到的结果如表1所示。

表1 环境1下2种算法仿真结果对比

由表1可以看出，本文在引入方向夹角启发因子和信息素自适应挥发策略后，不管是最优路径长度还是平均路径长度均优于基本蚁群算法所得到的路径,且在运算时间上提前了2.47 s。环境2情况下2种算法得到的结果分别如图7和图8所示。

图7 环境2下2种算法最优路径对比

图8 环境2最优路径收敛曲线

比较图7和图8可知，基本蚁群算法在第8代得到最优路径,此时长度为32.04，而本文算法在第6代得到最优路径长度为30.04，且本文算法所得路径更加平滑。环境2下2种算法在30次仿真所得结果的平均值如表2所示。

表2 环境2下2种算法仿真结果对比

由表2可以看出，在障碍物较多的环境中本文算法相对基本蚁群算法可快速收敛，最优路径长度29.81优于基本蚁群算法的34.73，减少了14.17%，平均路径长度减少17.17%，并且在运算时间上也提前了2.27 s。

5 结束语

为了加快算法的收敛速度和寻优能力，本文提出了一种改进的蚁群算法，主要体现在以下3个方面：

a.通过引入方向夹角启发因子，增加路径选择的指向性，避免了算法在搜索路径过程中因转弯角度过大而浪费时间。

b.引入A*算法的估价函数思想来改进启发函数，在基本蚁群算法的基础上考虑了当前节点与下一节点之间的距离，这在一定程度上降低了算法的搜索效率。

c.提出基于拉普拉斯变化的信息素挥发策略，加快了算法迭代速率。

仿真结果表明,本文改进的算法在路径寻优性能方面优于基本蚁群算法，证明了该算法的有效性和可行性。