融合蚁群-A*算法的移动机器人路径规划

马 军,宋栓军,韩军政,熊继淙,张周强,阎文利

(1.西安工程大学 机电工程学院， 陕西 西安 710048；2.航空工业西安飞机工业(集团)有限责任公司 工具管理中心，陕西 西安 710089)

0 引 言

智能机器人是无人工厂中不可或缺的一部分,而其中最重要的就是能让机器人对已知的环境自主进行路径规划。现阶段有多种算法可用于机器人路径规划,比如传统算法中的RRT算法[1-3]、D*算法[4-5]和动态规划算法等[6]。上述算法虽然能找到最终路径,但是也存在各种缺点。RRT算法进行搜索时,只要起点到终点可以连线,就会生成路径,所以不能保证输出结果为最优路径;D*算法只考虑相邻两点的距离,极容易陷入局部最优;动态规划算法进行搜索时,会占据大量的空间,不适合较短的路径规划。为了让算法能更好适应于路径规划,也产生了多种改进的算法,如Nazarahari等[7]通过融合势场和遗传算法寻求最优解,该方法可以跳出局部最小值,但是在实际应用中还要考虑路径规划的实时性,因此还需要进一步的研究;滕儒民等[8]通过对A*算法的改进来寻找最优解,该方法得到的搜索点较少,能够快速得到最优路径;易欣等[9]通过对遗传算法的选择算子进行改进来求解,提出的方法能够较为有效地避免陷入局部最优,但是收敛速度较慢;而在路径规划求解的问题上,蚁群算法是最成功的[10],因此众多有关路径规划方面的问题都用此算法来进行求解,梁嘉俊等[11]提出使用双蚁群搜索,可以降低陷入局部搜索的概率来进行求解;Hocaoglu等[12]通过改进蚁群算法信息素更新方式，快速求得最优解;李二超等[13]提出将模拟退火和遗传算法等多种智能算法的融合来求解最优路径,此种方法是对NSGA-Ⅱ算法进行改进,根据给定约束条件,将所有的解集合分为可行性和非可行性解,引导可行性解变为更好的解,可大大减少搜索的时间；刘俊等[14]提出PSO-ACO融合的算法应用于室内路径规划,此种改进的方法虽然对蚁群算法有时陷入“自锁”的问题有所改进,但是当数据量增大,路径的复杂程度增高,其性能也会有所降低。

文中提出了一种融合蚁群-A*算法来进行求解,引入A*算法的估价函数,对蚁群算法的启发函数和信息素更新方式进行改进调整,增加了算法搜索时的指向性,降低了其陷入“自锁”的概率,提高了其搜索的速度和精度,以便于其在数据量较大时也可快速寻找最优路径。

1 环境建模

在路径规划的环境地图构建中,大多是应用栅格法进行建模,因此本文也利用栅格法建立了2种不同环境模型下的仿真地图,如图1，2所示。

在Matlab中利用栅格法建立20×20的方格,大小为1 m×1 m,其中黑色为不可通行路段,白色为可通行路段,左上角S(0.5,19.5)处为起点,右下角T(19.5,0.5)处为终点。

2 融合蚁群-A*算法

2.1 蚁群算法的数学模型

蚁群算法用来解决路径规划等方面问题时,基本的思想就是用蚂蚁行走过的路径集合来表示要寻求解决问题的可行性方案的集合[15-17]。蚂蚁寻优过程在正反馈的作用下,逐渐聚集到最优的路径上,也就是最佳的解决方案,而其中的路径转移概率为[18]

(1)

(2)

整个循环中蚂蚁会不断的释放信息素,同时先前蚂蚁释放的也会不断消失,可以设定一个参数ρ(0<ρ<1)表示信息素的挥发程度。循环完成后,需要对其进行实时的更新,更新方式如式(3)所示:

(3)

2.2 算法改进

2.2.1 启发函数的改进 蚁群算法虽然可用于求解最优路径,但是其启发函数ηij(t)并未考虑到下一个节点和目标节点之间的距离,这在一定的程度上会使得算法的搜索速度和效率降低。因此,在蚁群算法的基础上,融合A*算法,使其遇到自锁时可进行局部规划,从而提高算法的效率。估价函数的表达式为

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

(4)

式中:f(n)为当前节点的估价函数;g(n)为当前节点到下一节点的实际代价,取值为当前节点到下一节点之间的距离;h(n)为下一节点到目标节点之间的估计代价,取值为下一节点到目标节点之间距离[19-20]。从而使得改进后的蚁群算法的启发函数变为

(5)

式中:dij相当于估计函数中的g(n);diT则相当于h(n)。

2.2.2 信息素更新策略的改进 蚁群算法中信息素更新方式容易出现“自锁”的现象,很难寻得最优解。因此在每次更新后计算出平均路径,并且记录最优路径和最长路径,如果此次路径长度没有上次短,则将其引入信息素更新策略中,从而降低陷入局部最优的可能,并且又能保证快速求解的能力,新的信息素更新方式为

(6)

式中:da为平均路径;dm为最长路径;dl为最优路径；k为迭代次数。

改进后的算法步骤如下:

1) 栅格地图的构建, 建立对应的描述矩阵用于存储障碍物情况。

2) 对算法的参数的初始化。

3) 将蚂蚁放置出发点。

4) 根据转移概率公式选择下一节点。

5) 更新运动节点禁忌表并判断蚂蚁是否运动至目标节点, 如若蚂蚁无路可走判定该蚂蚁已陷入自锁,进入步骤6)。

6) 随机选择是否进行操作, 若未被选择, 则此蚂蚁彻底自锁。若被选择, 借助 A*算法进行局部路径规划,并将局部路线与已经探索路线进融合拼接。

7) 对全局信息素进行更新。并将当前迭代次数的平均路径,最优和最长路径进行记录。

8) 判断当前最优路径和上代最优路径的大小,如果当前路径较小,则进行下一步,否则输出最优路径的同时将平均路径,最优和最长路径引入信息素更新策略中进行下次迭代。

9) 判断是否迭代到200次,如果是,则输出最优路径,否则执行步骤2)。

3 实验与结果分析

为了验证文中的算法,在Matlab仿真软件上进行实验,先后采用2种不同环境对其进行仿真实验,初始参数设定:蚂蚁代数为200代,蚂蚁个数为50只,α=3,β=7,ρ=0.3,Q=1,每种环境各仿真100次。

在环境模型1中进行仿真实验, 实验的收敛曲线和最优路径轨迹对比图如图3和图4所示。 表1为环境1仿真结果对比, 表2为环境2仿真结果对比。

表 1 环境1仿真结果对比Tab.1 Comparison of environment 1 simulation results

表 2 环境2仿真结果对比Tab.2 Comparison of environment 2 simulation results

图 3 环境1收敛曲线对比Fig.3 Comparison of environment 1convergence curve

从图3可知,本文算法在前期搜索时,有一定的波动,但是随着搜索的进行,慢慢趋于平稳,搜索的路径越来越短。从表1可知，蚁群算法从17代进行收敛,本文算法从13代开始收敛,且收敛速度也快于蚁群算法。

图 4 环境1最优路径对比Fig.4 Comparison of environment 1optimal path

从图4可知本文算法的路径明显优于蚁群算法,而表1中数据也显示,将最优和最长路径引入信息素更新策略中进行下次迭代,无论是最优路径长度还是平均路径长度以及算法的平均耗时都明显优于蚁群算法,并且最优解出现的次数比蚁群算法多。

在环境模型2中进行仿真实验,实验的收敛曲线和最优路径轨迹对比如图5和图6所示。

图 5 环境2收敛曲线对比Fig.5 Comparison of environment 2convergence curve

图 6 环境2最优路径对比Fig.6 Comparison of environment 2optimal path

从图5和图6可知,在相对复杂的环境模型2中,本文算法相对于蚁群算法可以相对快速的进行收敛。而从表2的数据中可以具体看出相对复杂的环境下本文的算法最优路径长度为29.799 0 m,优于蚁群算法的32.213 2 m;最优解出现的次数为63次,远远大于蚁群算法的31次,并且程序的耗时较蚁群算法减少了2 s。

综上，当环境变得相对复杂时,本文的算法也可快速进行收敛,并且在最优路径上明显优于蚁群算法,这表明改进后的算法是有效的,并且能够适用于不同的复杂环境。

4 结 语

蚁群算法在路径规划时收敛速度比较慢,并且容易陷入“自锁”等问题,本文提出了一种改进的方法,将A*算法的估价函数思想引入蚁群算法的信息素更新方式中,给蚂蚁的搜索添加一个指向性,以便快速的寻找出最优的路径。在Matlab上进行仿真,实验结果表明本文算法在收敛速度上优先于蚁群算法4～6代,在最优路径上也优于蚁群算法2～3 m,程序的运行速度上也较之快了2～3 s,且在最优解出现的次数上远远大于蚁群算法,证明本文算法有效、实用。