改进蚁群算法在物流机器人路径规划中的应用

朱永强，孙宗涛

(青岛理工大学机械与汽车工程学院，青岛 266520)

随着科技的进步，物流机器人开始频繁出现在人类生活中，其应用为人们提供了不可或缺的帮助。物流机器人的路径规划问题尤为重要，选择一条好的路线不仅可以降低机器人的使用成本，同时也节省了人们的时间。

路径规划是就是使机器人在存在着障碍物的空间内找出一条从起始位置到达目标位置的优化无碰撞路线[1]。近年来，越来越多的智能算法被应用于机器人的路径规划之中。许多研究者提出了多种有效的算法，如灰狼算法[2]、粒子群算法[3]、模拟退火算法[4]、蝙蝠算法[5]和细菌觅食算法[6]等。这些算法均取得了一定成果，但也普遍存在着收敛较慢、容易陷入局部最优解等缺点[7]。

蚁群算法是由Dorigo、Maniezzo等提出的一种仿生智能算法[8]。与其他优化算法相比，蚁群算法具有如下优势。

(1)每只蚂蚁可以通过释放信息素改变附近的环境，且每个个体能够感知附近环境的变化，蚂蚁之间可通过环境进行间接的通信。

(2)在蚁群寻优过程中，多个个体同时进行计算，在很大程度上提高了算法的计算能力和运行效率。

(3)由于蚁群算法存在着正反馈机制，可以使算法在搜索时可以持续收敛，当算法结束时可得到一个最优解。

但是传统蚁群算法也存在着如运算时间较长，路径搜索效果一般等缺陷。因此文献[9]提出自适应更新信息素的策略，提高了算法的全局搜索能力；文献[10]使用鸟群算法改进了蚁群算法中信息素的更新机制，提升了算法的寻优能力与收敛速度；文献[11]采用双反馈信息素更新策略，可以加速算法收敛同时避免陷入局部最优。

从前人对算法的改进可以看出，蚁群算法的信息素更新机制至关重要。由于传统蚁群算法中，每个节点的初始信息素皆相同，为一常量。鉴于此，结合双向搜索的A*算法对其进行改进，提高其路径寻优能力，最后使用MATLAB对其进行仿真验证。

1 栅格法环境建模

环境地图的构建是物流机器人避障与路径规划中不可缺少的部分。物流机器人现实中的工作环境为不规则的物理空间，环境建模的过程实际上就是将现实工作环境映射成为一个虚拟环境。

目前，建立环境地图的方式有很多，如可视图法、自由空间法、拓扑法和栅格法等[12]。采用栅格法来建立环境模型。栅格法在描述环境信息时，障碍物所在区域在栅格地图中呈现为黑色，地图矩阵中标为1，可自由通行区域在栅格地图中呈现为白色，地图矩阵中标为0。路径规划的目的就是在建立好的环境地图中找到一条最优的可通行路径，所以使用栅格法建立环境地图时，栅格的合理设定非常关键。

在构建栅格地图时，首先以地图左下角第一个栅格为坐标原点建立直角坐标系。因此每一个栅格可以用(x,y)的坐标形式表示，如左下角第一个栅格可以表示为(1,1)。并且从左下角开始每一个栅格进行编号N，编号从0开始。编号和坐标的转换公式为

x=int(N/Gsize)+1

(1)

y=N%Gsize+1

(2)

式中：Gsize为每行栅格数量；int为取整函数；%在此处起到取余数作用。

由栅格法构建的物流机器人所处简易环境地图如图1所示。

图1 简易栅格环境地图Fig.1 Simple raster environment map

2 传统蚁群算法基本理论

蚁群算法是通过蚂蚁分泌的信息素来引导整个搜索过程，该算法的核心在于模拟蚂蚁寻找食物的行为，即蚂蚁从巢穴出动根据以前留下的信息素选取可以找到食物的最短路径。

2.1 概率选择

在蚁群算法中，设整个蚂蚁系统中的蚂蚁数量为m，节点数量为n，节点i与节点j之间的距离为dij(i,j=1,2,…,n),t时刻节点i与节点j之间路径上的信息素浓度为τij(t)。初始时刻，各节点间路径上的信息素浓度相同，即τij(0)=τ0。

(3)

式(3)中：ηij(t)为启发函数，表示蚂蚁从节点i转移到j的期望程度；Ak(k=1,2,…,m)为蚂蚁k待访问的节点集合；α为信息启发因子，表示信息素对蚂蚁选择路径的影响程度；β为期望启发因子，反映ηij(t)的重要性。

2.2 信息素更新

当蚁群在完成了一次完整的搜索过程后，需对各个节点间路径上的信息素浓度进行更新，即

τij(t+1)=(1-ρ)τij(t)+Δτij，0<ρ<1

(4)

(5)

(6)

式(6)中：Q为常量，为蚂蚁在一次搜索过程中所释放的信息素总和；Lk为第k只蚂蚁走过的路径长度。

3 改进的蚁群算法

3.1 改变启发函数和双向搜索的A*算法

A*算法在机器人避障与路径规划领域是一种典型的启发式搜索算法。在搜索过程中，启发函数的作用是十分重要的，而传统A*算法在寻路时，普遍存在搜索时间较长、效率低下等问题。

3.1.1 启发函数优化

改进后A*算法的启发函数为

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

(7)

式(7)中：f(n)为从初始状态经由状态n到目标状态的代价估计；g(n)为状态空间中从初始状态到状态n的实际代价；h(n)为从状态n到目标状态的最佳路径的估计代价；λ为h(n)的比例系数，其取值为(0,1)。

一般来说在全局路径规划中，h(n)部分的取值大小影响着启发程度的强弱。当h(n)较小时，A*算法会按照最短路径行走，但其拓展的栅格数量会增加，导致算法运行时间变长；当h(n)较大时，算法由于拓展的栅格数量少，运行速度快，行走路径长度可能不是最短。需要根据实际情况进行权衡。

常规启发函数一般采用曼哈顿距离(Manhattan distance)来计算路径长度，但最终所得到的结果通常不够理想。相比于曼哈顿距离来讲，欧几里得距离(Euclidean distance)路径长度更短，算法运行速度稍慢。由于算法运行时间和路径长度可以通过调整比例系数λ来调整，采用欧几里得距离来求取h(n)的数值。即

(8)

式(8)中：(xn，yn)表示从出发点开始搜索的当前节点坐标;(xgoal，ygoal)表示从终点开始搜索的当前节点坐标。

3.1.2 双向搜索策略

改进A*算法相对于传统A*算法来说，其OPEN列表和CLOSED列表各增加了一个，分别标记为SOPEN、EOPEN和SCLOSED、ECLOSED表。每个子节点从当前所处栅格向周围的8个栅格进行搜索，从中搜索出f(n)函数值最小的拓展节点放入CLOSED表中。当搜索到一个h(n)函数值为零的拓展节点时，算法停止。

由于双向搜索的A*算法是头尾双向并行进行的，相比单向搜索更易找到最优解。也就可以更快地为改进蚁群的算法提供一条更优的预搜索路径。

3.2 蚁群算法信息素分布策略改进

首先通过改进的A*算法寻找到一条最短路径，并以此路径作为较优解，改变信息素矩阵。改变规则如下：以较优路径经过的节点为中心，向其四周扩散，线性递减的改变信息素，提高较优解路径附近节点的信息素浓度，这样使蚁群算法在搜索最优路径时，能更快地收敛，同时，线性地添加信息素也可以避免搜索过程中容易陷入局部最优解。

φ(d)=kd+b

(9)

式(9)中：φ(d)为距离中心节点d的节点的信息素增加浓度；k为线性递减系数(k<0);b为中心节点增加的信息素浓度。

3.3 改进蚁群算法流程

改进蚁群算法在物流机器人路径规划中的应用流程如下。

(1)首先建立好栅格地图模型，使用双向搜索的A*算法在栅格地图上预先搜索一条最短路径作为较优解，改变初始信息素浓度。

(2)将双向搜索A*算法增添的信息素与蚁群算法信息素进行融合。

(3)蚁群通过轮盘赌的方式确定要去的下一个节点。

(4)当蚁群全部搜索路径完毕，将此代蚁群产生的信息素与已有的信息素相融合，对全局信息素进行更新。

(5)开始下一次迭代，使蚁群重新回到起点开始新的搜索过程。当迭代次数到达设定值，迭代结束，找出最优路径。

4 试验仿真分析

对某仓储物流中心进行栅格法建模，物流机器人需从此仓储物流中心的左上方起点出发并到达右下方目标点。仓储物流中心布局如图2所示。

图2 仓储物流中心布局Fig.2 Warehouse logistics center layout

采用MATLAB 2018b对算法进行仿真试验，在仿真环境下设定参数如下，栅格环境地图为20 m×20 m，蚂蚁数量为50，最大迭代次数为100次，ρ为0.2，α、β分别为1和5,Q为1，仿真结果如图3～图5、表1所示。

根据图3～图5、表1所示结果可以得出结论：改进蚁群算法在同样的栅格环境中相比传统蚁群算法搜索的最小路径长度减少了0.82 m，迭代次数减少了41次；相比文献[11]算法迭代次数减少了13次，算法收敛性能有较明显提升。

表1 3种算法下物流机器人路径规划结果Table 1 Path planning results of logistics robots based on three algorithms

图3 传统蚁群算法仿真结果Fig.3 Simulation results of traditional ant colony algorithm

图4 文献[11]算法仿真结果Fig.4 Simulation results of algorithm in reference[11]

图5 改进蚁群算法仿真结果Fig.5 Improved ant colony algorithm simulation results

同时为对比3种算法的快速收敛能力，将蚁群中蚂蚁数量增加为100，算法迭代上限值减少为30次，其他参数不做改变，每种算法各进行10组试验，3种算法在第30代时仿真结果如图6、表2所示。

图6 3种算法在10次试验下对比Fig.6 The three algorithms were compared under ten trials

表2 3种算法在10次试验下路径规划结果Table 2 The path planning results of the three algorithms under ten trials

从图6、表2可以明显看出，当改变部分参数，算法迭代上限值减少为30次时，改进蚁群算法搜索到的平均最小路径长度相比传统蚁群算法和文献[11]算法分别减少了2.35、0.69 m。同时在这10次试验中，当算法迭代到30次时，改进蚁群算法搜索到最小路径次数有4次，文献[11]算法与传统蚁群算法仅有1次和0次,证明了改进蚁群算法相比其他两种算法的路径寻优能力更强。

5 结论

针对物流机器人路径规划问题，提出了一种改进蚁群算法。

(1)通过预先使用双向搜索的A*算法来线性地改变信息素，提高较优解路径附近节点的信息素浓度，对传统蚁群算法进行改进，提高了算法的收敛速度与全局搜索能力。

(2)在MATLAB软件中对此算法进行了仿真试验，结果表明，相对于传统蚁群算法与文献[11]算法来说，改进蚁群算法具有更高的路径寻优能力，具有一定的实际应用与科研价值。