王 雨，谢 峰，刘玉磊，朱 翔

（安徽大学 电气工程与自动化学院，合肥 230601）

0 引言

自动引导小车（Automated Guided Vehicles，简称AGV）是一种无人驾驶的智能运输车，广泛的应用于现代工业自动化物流系统中[1]。AGV是指装有诸如磁传感器、摄像机等导航装置，能够行驶在提前规划好的路径，并且在车体上安装有主控制器、定位装置、安全保护装置、通讯模块、以及各种物料运载的车辆，是一种智能轮式机器人，被广泛用于工厂自动化生产线、仓储物流、机场和港口的物料传送场景[2,3]。AGV路径规划是目前机器人领域中一个研究的热点，即在未知的环境中，寻找到一条时间最短、路径最短的安全无碰撞路径。目前解决问题的方法主要有人工势场法[4,5]、Dijkstra算法[6]、遗传算法[7]以及蚁群算法[8]等，其中每种方法都存在着自身的优点和不足之处。

蚁群算法是由意大利学者Marco Dorigo于1992年提出的，其灵感来源于蚂蚁在寻找食物过程发现路径的行为。蚂蚁在觅食的过程中会倾向于选择信息素浓度大的路径，同时更新自己的信息素，直到蚁群选择同一条且信息素浓度最大的最优路径。蚁群算法具有较强的适应性和鲁棒性，但是也存在着许多问题，如蚁群算法是以蚂蚁从当前点到目标点的距离作为启发信息，不利于蚂蚁对动、静态障碍物的规避，而且蚂蚁寻找目标是一个盲目搜索的过程，这样就会产生较多的交叉路径和蚂蚁迷失现象[9]，造成蚁群算法过早的收敛、搜索路径效率低下等情况。

人工势场法是一种局部路径规划算法，它的本质是对AGV运行环境虚拟成一个抽象的势场，在虚拟势场中AGV受到障碍物的斥力和目标的吸引力形成的合力来确定运动方向和速度。人工势场法可以保证得到一条安全的路径，但可能并不是最优的一条，而且也存在着一些不足之处，该算法易造成目标不可以到达且在目标点附近打转，或存在着局部最小区域，迫使AGV处于暂时停滞状态[10]。

本文根据蚁群算法和人工势场法两者的优缺点，提出了一种改进的势场蚁群算法。该算法利用AGV所受到人工势场力以及到目标点的距离来重新构造启发信息函数，根据动、静态障碍物构造不同的势场函数，并且引入障碍物对AGV的相对速度和方向，实时更新动态障碍物在栅格地图中的位置，可以做到以较小的代价提前规避障碍物；人工势场的加入使蚂蚁盲目搜索变成有向的搜索，减少了蚁群搜索过程中的“迷失”现象，加快了收敛速度。

1 蚁群算法和人工势场法的基本原理

为了更好地利用势场蚁群算法解决自动化车间环境下AGV路径规划问题，本文将AGV工作环境视为二维空间，并采用栅格法建立栅格地图，根据AGV小车的大小尺寸来进行栅格地图网格大小的划分，黑色表示障碍物，白色表示自由栅格，AGV作为一个质点运动，对障碍物进行膨胀处理，如占据局部栅格，按照整个栅格处理，以防止发生碰撞。AGV路径规划算法如下。

1.1 传统蚁群算法

传统的蚁群算法来决定蚂蚁在t时刻行走路径的原理是：某蚂蚁（m）在第i个节点选择下一个节点j的概率是根据栅格环境中各路径上的信息素ij(t)和当前的启发信息ij(t)的大小决定的，如式(1)所示。

蚂蚁经过的路径会留下信息素，但随着时间的流逝会挥发一定的数量，需要对其按照式(2)进行局部更新：

蚁群算法完成一次迭代后，可找出当前蚂蚁寻找到的最短、最优路径，并对信息素通过式(3)和式(4)进行全局更新。

式中：Q为常量，ρ表示信息挥发参数，Lm表示蚂蚁建立的最短路径。

1.2 人工势场法

人工势场法的实质是对机器人运行环境虚拟一个抽象势场，障碍物对机器人产生斥力Frep，目标点产生引力Fatt，合力Ftot指引机器人运动。

假设AGV在M点，目标对其引力势场函数为Uatt(i)，如式(5)所示，障碍物对其斥力势场函数为Urep(i)，如式(6)所示[11～13]。

式中：η和ξ分别是斥力势场常量、引力势场常量；d（M，O）为当前点到障碍物点的距离；d（M，G）为当前点到目标点的距离；dO表示斥场作用半径。AGV在M点所受的引力和斥力分别为式(7)、式(8)所示。

根据几何叠加原理得到所受合力为Ftot=Frep+Fatt，nMG为当前点到目标点的单位矢量。

2 势场蚁群算法的改进

2.1 改进的人工势场法

自动化车间环境经常会有人来回的进行走动，形成了动态的障碍物，人工势场对于动态障碍物的环境，存在着躲避不及的问题，因此需在人工势场法的基础上加以改进，对势场函数不仅要考虑其相对位置，还要考虑它们之间的相对速度。如图1所示，以AGV小车为参照物，通过kinect视觉传感器感知环境，得到障碍物t0到t1时间段的位置信息和移动角度，然后抽象为速度矢量三角形计算它们的相对速度大小v和方向。

图1 求取障碍物相对速度示意图

规定AGV移动逆时针为正，顺时针为负，则障碍物移动的相对角度和距离为式(9)所示：计算出安全避碰最小角度和安全距离，并据此建立新的势场函数。所改进的引力势场函数和斥力势场函数分别为式(10)和式(11)：

由此可求出障碍物和AGV的碰撞角

式中η和ξ是速度常数，v是AGV到障碍物的相对速度，vO为AGV到目标点的相对速度。

那么，AGV在此处受到的斥力和引力分别如式(12)和式(13)所示。

2.2 启发信息的改进

蚂蚁在栅格地图上移动，传统蚁群算法中蚂蚁受到信息素浓度和距离的作用，当路径短时，使蚂蚁往返一次时间短，重复频率快，每次行走都会留下信息素，吸引更多的蚂蚁，增加路径上的信息素浓度，这样越来越多的蚂蚁都聚集在最短路径上。但在路径规划初期，信息素浓度较弱时，蚂蚁搜索的随机性较大，收敛速度变慢。而在传统的人工势场法中，蚂蚁是通过所受势场合力来进行路径规划，定义的启发信息为：

式中，α为常数，θ为蚂蚁行走方向和势场合力方向的夹角。在启发信息的作用下，蚂蚁选择θ最小的边行走，有利于避免碰撞和有效的选择最接近目标点路经行走。但当势场合力为零时，AGV将会处于局部最小点，引力和斥力等价，陷入局部最优位置陷阱，为此，本文结合两种算法的优点构成算法的启发信息为：

式中，Nmax和N分别为最大迭代次数和当前迭代次数。从式(17)可以看出在势场蚁群算法初期，信息素浓度较低，主要靠势场力启发信息使蚂蚁快速找到目标点。随着迭代次数的增加，降低了势场力启发信息的作用，加强了信息素的作用，使蚂蚁主要集中在信息素浓度强的路径上，从而增强了对最优路径的搜索。最后还可以保障在人工势场合力为零的情况下仍有效的进行到目标的最优路径搜索，进而避免失去搜索方向。

2.3 路径规划步骤

步骤1：确定栅格地图长度，障碍物的位置，AGV的起始点和终点；

步骤2：初始化势场蚁群算法的参数，例如蚂蚁数量、信息启发因子、引力和斥力增益、信息素强度等；

步骤3：将蚂蚁放在起点，判断行走过程中有没有动态障碍物，如果存在动态障碍物，算出安全距离和角度，更新栅格地图中的障碍物位置，按照式(1)和势场合力方向选择下一个节点。当蚂蚁到节点j后的，按式(2)对走过的路进行局部信息素更新，并删除跟新的栅格地图；若不存在动态障碍物，按照传统势场合力方向选择下一个节点j，并将节点j加入禁忌表；

步骤4：重复步骤3，直到蚂蚁到达目标点，保存所有蚂蚁搜索到的路径长度，并选择最优路径；

步骤5：按照式(3)对最短路径进行信息素的全局更新，清空禁忌表；

步骤6：判断是否达到最大迭代次数，若达到则终结，否则重复步骤3到步骤4。

3 AGV路径规划实验验证

为了验证本文所提的路径规划算法的可行性，在Matlab环境下对该算法进行仿真，加以和常规的蚁群算法比较。本文用20×20的栅格环境和不同的障碍物设置来模拟真实环境，每个栅格的大小为一个单位长度。AGV起点设置为（1，20），终点设置为（20，1），黑色表格为障碍物，白色表格表示自由栅格。设定参数蚂蚁数量为30，迭代次数为100，信息素浓度启发因子α=1，能见度启发因子β=5，信息素挥发系数ρ=0.7，信息素强度Q=1，引力系数η=2，斥力系数ζ=2，斥力作用半径d0=2，可调参数ψ=0.1。

通过图2可以看出，在复杂的自动化车间环境下，传统蚁群算法没有搜索到一条最优的路径，而是找到了一条较长的路径，因为盲目搜索和搜到启发信息的影响，在中心复杂的环境中，蚂蚁偏向于远离障碍物，造成了较长的行走路径，由于信息素的作用，以后的蚁群也会较大几率选择此路。改进的算法在势场合力和信息素浓度的双重作用下加快算法的收敛速度，并且避免了上述问题。从收敛曲线看，蚁群算法用了56次迭代收敛到34.549，本文改进的势场蚁群算法只用了30次迭代就收敛到最优路径30.364。

图2 蚁群算法

图3 改进势场蚁群算法

图4 动态障碍物的路径规划

对于动态障碍物，改进的人工势场可以实时更新局部环境，根据计算得到的安全距离和角度来填充栅格地图障碍物的位置。从上图可以看出当运行到（8，14）时，有动态障碍物实时更新栅格地图，从（8，12）开始添加障碍物，然后根据改进人工势场算法在局部栅格地图重新计算路径。从图4可以看出路径变得更加复杂，用37次迭代收敛到31.269。

4 结论

本文针对复杂的自动化车间环境的路径规划问题，采用人工势场算法和蚁群算法融合的办法。将AGV在运动中受到的虚拟势场合力作为蚂蚁寻找目标点的部分启发信息，引导AGV感知周围障碍物，进行有效的避障和目标搜索。在感知到运动目标时，及时的在局部地图上更新障碍物，在改进的新势场函数引导下进行有效的避障，寻找到最优的安全避障距离和角度，结束后恢复原栅格地图。通过仿真结果表明，本文所提出的改进势场蚁群算法对自动化车间环境下路径规划的效果比较好，对动态障碍物也有很好的躲避效果。