基于改进蚁群算法的盘点型机器人路径规划

马金科，王 直

(江苏科技大学 计算机学院，江苏 镇江 212003)

0 引 言

盘点型机器人是指能够精确盘点仓库中的货品以及可以引导上架新货品的机器人。移动机器人的路径规划是移动机器人研究的重要分支之一，是机器人实现智能化移动的关键[1]。移动机器人在有障碍物的工作环境中，按照某一性能指标(如工作代价最小、行走时间最少、行走路线最短等)搜索一条从起始状态到目标状态的安全的、无碰的最优或次优路径[2]。

目前，常用于移动机器人路径规划的算法主要有人工势场法、A*算法、神经网络法、蚁群法、遗传算法等[3]。A*算法虽然对比较简单的地图搜索速度非常快，也能找到最优路径，但全局性较差，启发函数选择不当的话容易陷入死循环。神经网络法虽然能收敛到最优路径，但环境改变后必须重新学习，在环境信息不完整或环境经常改变的情况下应用起来很困难[4]。模糊推理法虽然避开了其他算法中存在的对环境信息依赖性强等缺点，但自身的适应能力比较差[5]。遗传算法虽有鲁棒性强、全局优化等优点，但计算速度不快，容易提前收敛。相对而言，蚁群算法具有分布式计算、信息正反馈和启发式搜索特征，在求解移动机器人路径规划问题时更加合适。但基本蚁群算法执行过程依赖于大量的迭代和循环，缺乏实时性;运行过程中信息素不断累积，优质路径不突出，对于最优解的求取有很大影响[6]。对此，文中重点对蚁群算法中的全局初始信息素分配、挥发系数随时间进行相应变化，信息素在迭代中更新的方式等方向提出相应的改进方法。

1 基本蚁群算法

自然界的蚁群在外出觅食时，会在它们走过的路径上散发出一类有特殊气味的信息素[7]。蚂蚁之间依靠这种化学物质实现信息的交互，并实时引导后续的运动方向。每只蚂蚁在没有预先知道食物所在地的前提下开始搜索食物，并在经过的路径上分泌信息素。而蚁群算法的核心就是：通过若干数量的蚂蚁共同寻路，在各个途径带上分泌信息素来提高食物搜索的效果，最终以最短路径找到食物。

由上可知，在整个过程中有两个因素会对得出的最优路径造成大的影响：

(1)在选择下一个目标节点时，信息素浓度对蚂蚁影响很大，浓度大的蚂蚁选择该路径的几率更高。

(2)蚂蚁在寻路过程中，节点路径上浓度高的路径，会以较高概率得到保留，相应浓度低的路径会在迭代中被舍弃。

蚁群算法的特点，决定了它在路径规划的范围较大，且在用户节点较多的情况下，能表现出更强的适应性和兼容性，同时在这种应用场景下，得到的最优路径结果也更稳定。

旅行商问题(traveling salesman problem，TSP)是在组合型优化问题中的一个典型代表。经典的TSP是这样描述的：一个推销员要在所有推销的城市推销产品，要求他能够从一个起点出发，最后遍历所有城市，并回到起点。过程中应如何选择行进路线，以使总的行程最短[8]。以TSP(旅行商问题)为背景，蚁群算法中可以将N个蚂蚁比作各个推销员，这些蚂蚁并不是在同一个起点出发，而是分布在各个节点出发。食物所在地则类比为需推销的城市，蚁穴是集散中心，所有蚂蚁对所有食物的地方访问完后，会回到集散中心。通过多次迭代，所有蚂蚁寻出的路径会收敛出一条最优的路径[9]。为量化阐述蚁群算法，路网中第k只蚂蚁选择下一个节点的规则如下：

(1)

随着时间的推移，路途上的信息素会慢慢减弱，每次各个蚂蚁访问完全部节点之后，路段上的信息素需要进行更新，更新公式为：

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

(2)

(3)

Δτij按下列公式更新：

(4)

其中，Q为常量；Lk为第k只蚂蚁在本次循环所经过的路径长度。

2 改进的蚁群算法

2.1 挥发系数ρ的优化

挥发系数ρ指信息素浓度逐渐减弱的系数值，它的设置决定着蚂蚁的搜索效果，也极大影响着算法实现的性能。若挥发系数设置太小，蚁群对蚂蚁的引导作用会过强，导致蚂蚁本身搜索的能力降低；若挥发系数设置太大，蚁群对蚂蚁引导作用会过小，再次选择已经搜索过的路径可能性会大大增加，降低了算法的全局搜索能力[10]。基于此，提出了自适应的挥发系数设置方法，即算法前期设置较小的挥发系数，减小蚂蚁间互相吸引，提高搜索效率；算法后期，挥发系数设置较大，提高算法收敛速度。

挥发系数ρ自适应公式为：

(5)

其中，ρmin为挥发系数可以取到的最小值。挥发系数随时间逐渐减小。

2.2 开始阶段信息素分配的优化

在传统算法中，开始阶段各个路径上的信息素浓度相同，为一个常数[11]。这种情况导致的结果就是算法在初期阶段搜索的速度很慢，要经过一段时间的处理，实现浓度不同对蚁群的影响。所以，文中对各个路径上的初始浓度进行调整，加大了起始点和终点连线附近的信息素浓度。这是因为，最优路径往往分布在起点和终点连线附近。其他区域出现最优路径的几率相对较小。这样在大多数情况下，改进后的算法会更快地找到最优路径，提高了搜索的整体效率。

2.3 信息素更新方式的优化

信息素浓度是蚂蚁在寻优过程中主要参照的依据[12]，所以，信息素浓度更新的方式直接影响到蚁群算法的准确性和效率。蚂蚁每移动一次称为一次搜索，经过n次搜索后，所有蚂蚁就完成了一次迭代。在传统算法中，信息素的更新只依赖于全局信息素更新，这使得算法容易陷入局部最优的陷阱[13]。将信息素浓度的更新分为实时更新和全局更新能有效改善这种情况。

蚂蚁的实时信息素更新公式为：

τij(t+1)=(1-σ)τij(t)+στ0

(6)

其中，σ为实时信息素挥发因子；τ0为信息素初始值。

全局信息素更新时，每个蚂蚁迭代完成，都会得到这个蚂蚁的路径[14]。比对这些路径，按路径长短排列，在较短路径上进行信息素加强，在较长路径上进行信息素削减。则全局更新的公式为：

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

(7)

(8)

其中，Li为本次迭代的最优路径；Lb为当前的最优路径；ε为一个可调参数，满足一次迭代后，加强接近最优路径的路径上的信息素浓度削减远离最优路径上信息素浓度。

通过实时和全局信息素更新，蚂蚁能够摆脱求得局部最优的陷阱，同时又能提高寻优的效率。

2.4 算法的实现步骤

改进算法的实现步骤如下：

(1)初始化信息素的分配及其他各种参数[15]。初始信息素分配时在起点和终点连线上设置较大的信息素浓度。对信息素重要程度因子α、能见程度因子β、最大迭代次数等参数进行初始化。

(2)初始化蚁群，构造解空间[16]。

(3)把蚂蚁放到起始点进行路径规划，按照式5进行信息素挥发因子设置。

(4)按照式1选择移动的下一个节点。

(5)当所有蚂蚁完成一次搜索后，按照式6进行实时信息素更新。

(6)判断所有蚂蚁完成一次迭代与否，完成则转步骤7，未完成转步骤4。

(7)按式7和式8完成全局信息素更新。

(8)判断是否达到最大迭代次数，若未达到，则开始下一次迭代，达到后则马上结束迭代，得到最优的路径。

算法实现流程如图1所示。

图1 改进的蚁群算法实现流程

3 仿真实验

为了验证改进算法的有效性，利用MATLAB平台对改进算法进行验证。依据改进算法的实现步骤，把对应参数初始化为:蚂蚁数目60，迭代数初始值200，信息素浓度影响因子α=1，能见度影响因子β= 4，挥发因子按前述自适应的方式设置。分别采用传统蚁群算法和改进蚁群算法在MATLAB环境下进行编程仿真，其仿真结果对比如图2和图3所示。

图2 基本蚁群算法规划出的路径

图3 改进蚁群算法规划出的路径

从以上对比可知，传统蚁群算法在搜索初期陷入了局部最优，虽然最终也找到了一条最优路径，但路径质量不如改进蚁群算法。而改进蚁群算法在改进了挥发因子自适应，初始浓度分布以及信息素更新方式后，最终规划出的最优路径明显优于传统蚁群算法。

为了更好地验证蚁群算法在收敛速度和最短路径上的优势，文中给出了传统蚁群算法和改进蚁群算法各次迭代路线的平均距离和最短距离的对比曲线，如图4和图5所示。

由图4和图5可知，在改进算法中，算法的搜索能力有所提升，最优路径得出的收敛速度也更快。对比原始算法，能以不到40次的迭代次数就得到比原算法更优的解，且后续迭代过程中，最优解未出现波动，证明该优化算法的可靠性和高效性。

4 结束语

针对盘点型机器人路径规划特点，设计了改进型蚁群算法。改进的蚁群算法通过对挥发因子自适应优化，初始路径浓度设置以及信息素更新方式的优化，有效地使传统算法避免了局部最优问题，同时提高了算法的收敛速度和最优解的质量。实验结果表明，改进的蚁群算法能更快更准确地找到最优解，具有更高的稳定性和有效性。基于这个改进效果，该算法可以应用盘点型机器人，以提高盘点型机器人盘点物品的能力。