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

王学忠，徐丽萍，李美莲

(安徽三联学院，安徽 合肥 230601)

随着信息和AI技术的飞速发展，各种用于家政服务的智能产品应运而生，如各种用于娱乐的机器人、协助主人做饭的烹调机器人和用于室内打扫卫生的机器人等。目前，家庭智能机器人的两个主要研究方向就是目标定位和路径优化问题，所谓路径优化就是机器人能够在复杂的家庭环境里，在起点与终点之间的无数条行走路径的方案中，能智能地选择一条路程最短或行走的时间最短的路线，并且能很好地避开障碍物。目前，用于路径优化的方法很多，譬如：蚁群优化算法(ant colony optimization, ACO)、A*算法[1]、经验图法、遗传法和APF算法[2]等。由于ACO具有速度快，鲁棒性好以及能在较短的时间内给出一个合理的运算结果，因此，ACO算法在机器人路径优化方法中获得人们普遍的青睐。左大利，聂清彬，张丽萍等同志通过引入死锁处理技术以及改进信息素更新方法等以达到提高收敛速度和收敛精度的目的[3]；王志中同志通过引入蚂蚁相遇策略和蚂蚁回退技术达到提高搜索最优路径的效率并且有效地避免陷入U形陷阱[4]；屈鸿，黄利伟，柯星等同志提出改进启发式栅格算法达到路径优化的目的[5]。

本文针对ACO算法在家庭机器人的路径优化中存在的易早熟、效率不高、路径的最优值不够准确等问题，提出了一种改进的蚁群算法(Improved ant colony optimization，IACO)。主要是在二维二值网格坐标地图上，通过动态地调整信息素启发因子α和 信息素增强系数Q值、调整信息素和转移概率的计算方法等实现了算法的优化。从仿真数据看出，改进后的IACO较好地缩短了收敛的间，效率得到了提高、避免了早熟，能够在有限时间内快速地找到最优的规划路径，获得的最优路径的值更准确稳定。

1 家庭机器人路径规划ACO算法

1.1 ACO算法的基本原理

ACO是一种模拟蚂蚁寻找食物食的算法，最早是由莫瑞希奥·多里戈(Maurizio Dorigo)

博士于1992年在他的博士论文中首先提出的。他在长期观察蚂蚁觅食的过程中发现单个蚂蚁觅食的行为表现的非常简单，但是群体蚂蚁的觅食行为则表现得非常睿智，蚁群则可以在任何复杂的环境下，都能快速地寻到一条从洞穴通向觅食地点的最短道路。经过专家的多年的观察发现，蚁群在其活动时会在其经过的道路上分泌出一定量的信息素物质，蚂蚁能敏锐地嗅到这种物质，并通过这种物质指引它的前进的方向。譬如某路径距离较短时，就会引来更多的同伴行走该路线，那么该道路上获得这种化学物质将更多，其他同伴嗅到这条路径上的浓烈的化学物质，因此选择该道路的概率就会更高，这是一个正向反馈的过程，从而逐渐接近最优路径[6]。

1.2 基于ACO算法的二维二值网格坐标地图法步骤

1)输入由0和1组成的矩形表示机器人需要寻找最优的网格地图，如图1所示。其中，0表示此处机器人可以通过，1表示此处为障碍物。由此可以得到图1所示的矩阵如图2所示。

图1 室内环境分布图

图2 室内环境0、1矩阵图

2)输入初始的信息素矩阵，选择初始点和终止点并且设置各种参数，设置所有位置的初始信息素相等。

3)计算出即将允许被访问地点的概率，根据计算的结果并结合轮盘法挑选出将要被访问的新地点。

(1)

公式中，τij(t)——地图中两点i,j间的道路上蚂蚁分泌的信息素的浓度；

ηij(t)——与地图中两点i,j之间的路径相关的期望值(启发函数)；

α——信息启发因子；

β——期望启发因子；

αk——K蚂蚁被允许访问的地点集合。

4)更新路径和路程长度。

5)重复3)、4)运算过程，一直到所有蚂蚁回到目的地为止。

6)更新信息素，对于没有到达目的地的蚂蚁采取放弃策略。

(2)

公式中，ρ—— 信息素挥发系数(0≤ρ≤1)。

(3)

Q—— 信息素增强系数。

7)重复3)—6)，直至蚂蚁迭代结束。

2 家庭机器人路径规划IACO算法

2.1 设置信息素阈值、改进信息素的计算方式

ACO的核心就是蚁群通过信息素这种物质相互之间进行的交流的，蚂蚁将在所经过的道路上分泌出一定量的信息素来告知其他同伴来选择即将行走的道路。通常是道路越短，蚁群通过后剩余的信息素的浓度会更高，将招来更多的同伴选择该道路，从而形成最优的路径。问题的关键是算法运算到一定的迭代次数后，有的路径上的信息素很高，而有的路径上则可能接近于0，这样就会造成大量的蚂蚁会集中在某一最优的路径上形成堵塞，使算法出现早熟、导致获得的结果不是最优的路径。本文在传统信息素更新方式的基础上进行局部改进，通过设置信息素的最大阈值τmax，采用信息素动态调整的方式[7]，目的是减小最优道路上的信息素与最差道路上信息素的差值，使蚂蚁不至于过多的聚集在某一条道路上，这样有效地避免算法的早熟。改进后的信息素计算公式如下：

(4)

2.2 改进算法部分代码描述

While(不满足算法终止条件)

{for (i=1,i

for(j=0;j

{for(i=0;i

根据转移公式(1)来算出的概率来选择蚂蚁下一步所要行走的路径；

end

}

计算出最优的结果，并付给蚂蚁i；

end

{

If(最优值达到前面多次循环的最优值)

更新 信息素值τ并进行下一循环；

end

}

end

}

输出最优值

End

2.3 动态调整信息素增强系数Q值

信息素增强系数Q值的高低对算法的搜索范围和算法收敛时长以及搜索的最佳路径值都会产生一定的影响。Q值越大，能够较好地提高蚂蚁的搜索能力但容易陷入早熟；Q值越低，延长了收敛的时长、使算法的效率变低。本文采取动态调整Q值的方法，即在算法初期(迭代次数小于50次)适当增加Q的值(Q=2)，以扩大算法的搜索范围，避免早熟；在算法的中后期(迭代次数大于50次)适当减小Q的值(Q=1)，以缩短算法的收敛时长和运算效率等。

2.4 改进概率转移的计算方法和引入随机机制

为了更好地提高算法的搜索范围和寻优解的多样性，在传统蚁群算法的基础上进行了算法的改进，加入了路径选择的随机性变化。在算法中事先设置一个选择参数δ0(0≤δ0≤1)，再由随机函数rand( )产生一个随机的数δ，当δ≤δ0时，从当前蚂蚁所允许的所有路径中随机选择一条路径作为下一行走的目标；当δ>δ0时，则需要根据算法转移计算公式(6)计算出下一步将要行走的路径。新的选取方式如下：

(5)

公式中，ak为下一次可以被蚂蚁访问的所有路径的集合。为了更好地提高全局的搜索能力，得到最优的搜索结果，对算法的转移公式进行改进如下：

(6)

公式中，Sj为当前位置I到目标位置J两点间的长度，Cj为目标位置J被访问的累加和。转移概率与Sj、Cj近似成反比，这样有利于提高全局搜索能力、避免早熟。同时，对信息素启发因子α进行动态调整，在算法搜索的前期(迭代次数小于等于30)，为了扩大搜索路径的范围，提高全局的搜索能力，适当减小信息素启发因子α在概率转移公式中的作用，把α的大小设置为1/2，在搜索的中后期，这时搜索的大致方向基本明确后，为了加快算法的收敛，提高算法的效率而适当增加了信息素启发因子α的值，把α的值由1/2增加到1。

3 实验结果分析

3.1 实验仿真建模

为了测试改进后IACO算法在最优路径、运行效率、收敛速度等方面要比基本的ACO算法具有一定的优越性，利用MATLAB 2014A软件、在WIN7操作系统下进行路径优化仿真模拟实验。本实验采用20X20网格的二维二值的坐标地图，黑色方格为1，表示道路有障碍，行走不通；白色方格为0，表示道路畅通无阻。障碍物的大小可以通过黑色方格的不同组合而得到，方格的边长设为1 cm。出发点的起始位置S(0,20)，即地图的左上角；完成路径的终点位置E(20,0)，即地图的右下角。两种算法的初始条件相同，设蚂蚁M=50(个)，α=0.5，β=5，ρ=0.3，Q=2,迭代次数为200。

3.2 实验数据分析

图3 环境1的收敛曲线和机器人行走路线

图4 环境2的收敛曲线和机器人行走路线

图3、图4分别是在模拟两种不一样的室内环境，两种环境下障碍物的分布也不完全一样，得到了两组ACO和IACO的收敛变化趋势图和行走路线图。从图3所示环境1的仿真数据中可看出，基本ACO的迭代次数为130次，最优路径的长度为39.078 cm；改进后的IACO的迭代次数为67次，最优路径的长度为38.186 cm，改进后的算法(IACO)明显优于基本算法(ACO)。图4的环境2要比图3的环境1复杂，从图4所示环境2的仿真数据中看出，基本ACO的迭代次数为92次，最优路径的长度为33.907 cm；改进后算法(IACO)的迭代次数为48次，最优路径的长度为31.056 cm，改进后的算法(IACO)也明显优于基本算法(ACO)。为了较全面地测试改进后的蚁群算法(IACO)的性能，分别采用用5组不同的环境(环境设置从简单到复杂)进行对比测试，测试的初始条件都一样，测试五组环境下的迭代次数M、最优路径长度L、算法时长T的对比数据如表1所示。

表1 五种环境下、ACO与IACO两种算法的数据对比

从表1中测试的数据可以看出，调整后的IACO计算方法无论是在收敛时间、最优路径值、运算的效率都要好于基本ACO计算方法。

4 结论

从实验数据可以看出，将二维二值网格坐标地图法与蚁群算法相结合，通过调整基本ACO公式中信息素的计算方法和设置信息素的阈值等措施能有效避免算法的早熟，提高全局搜索能力；通过动态调整信息素增强系数Q值，扩大算法的搜索范围，避免了早熟，缩短了算法的收敛时间和提高效率；通过改进转移概率的计算方法，在算法的早期适当减小启发因子α、引入路径选择的随机性机制等方法扩大了算法的全局搜索能力，使获得的最优路径的值更稳定、更精确。