基于改进蚁群算法的AGV多目标路径规划*

李传奇，黄卫华,b,c，章 政 ,b,c，金 震，张子然

(武汉科技大学 a.机器人与智能系统研究院；b.冶金自动化与检测技术教育部工程研究中心；c.信息科学与工程学院，湖北 武汉 430081)

0 引言

自动导引车(Automated Guided Vehicle，AGV)作为一种自动化程度高、灵活性好、抗干扰能力强的移动机器人，广泛应用于现代工业自动化物流仓储系统[1]。路径规划[2]是AGV调度系统研究和应用的关键问题之一。一般而言，物流仓储系统具有高效快速的运输需求，合理的路径规划方法对AGV能够实现有效、安全的自动行驶具有重要作用。

常规AGV路径规划大多是以单个目标作为寻优目标，如：时间最少、路径最短、拐点最少或者目标点全遍历等。文献[3]以路径长度为优化目标，改进蚁群算法的启发因子及全局信息素分布方式，规划AGV行驶路径；而文献[4]以最少转折点为目标，采用多方位搜索法，避免路径转折点过多导致AGV配送时间增加；文献[5]以最短路径长度为首要目标进行规划，再从所得路径中选取转折点最少的作为最终路径；文献[6]则以最小化搬运完成时间为目标，定义了AGV冲突优先级，提出一种生成无路径冲突的规划算法，提高AGV的作业效率。

随着 “绿色物流”[7]的发展，基于单目标函数的路径规划方法对于描述AGV路径规划问题具有一定局限性。除常见规划目标外，运输安全性、能源消耗等因素也被视为AGV运行性能指标，实际运行时，这些因素之间相互影响、制约，存在互斥性，即一个目标的优化可能会导致其他目标的退化。例如，最短路径可能是AGV紧贴着障碍物以降低安全性为代价的路径；最安全的路径可能是拐点最多的路径，会导致AGV行驶时间和能源成本增加。因此，以多个目标作为物流仓储系统路径规划的准则，需综合考虑多种因素的共同影响，实现AGV在多个目标共同优化作用下的自主路径规划。

本文综合考虑物流仓储系统路径规划的快速性、稳定性和安全性需求，设计了一种基于改进蚁群算法的AGV多目标路径规划算法。首先，构建子目标函数，并采用熵权法确定子目标权值以构建路径评价函数，以最小化评价函数值为总目标搭建多目标路径规划模型；然后，通过改进蚁群栅格转移方式及引入非支配排序算法，提高蚁群多目标优化能力；最后，基于仿真结果，证明了本文所设计的多目标路径规划算法用于动静态地图下AGV路径规划的可行性和有效性。

1 基于熵权法的AGV多目标路径规划建模

考虑到物流仓储环境的复杂性，路径的低危险率保证AGV在行驶过程中远离障碍物，减少与障碍物碰撞的可能性；更短的避障等待时间意味着AGV能更快的完成作业。因此，本文构建AGV多目标路径规划模型，综合考虑路径长度、转角和、危险率和避障等待时间作为AGV路径规划的子目标，并采用熵权法确定子目标权重。

1.1 各子目标模型的建立

栅格法简单高效、易于实现和表达不规则障碍物，本文采用栅格法[8]对仓储环境进行建模。描述如下：将AGV工作环境等分为a行a列个栅格，栅格大小能完全容纳机器人。无障碍物栅格为可行栅格(白色表示)，有障碍物栅格为不可行栅格(黑色表示)，障碍物小于一栅格时，按一栅格处理。移动机器人在栅格间的移动可看作一个质点，并假设每次都停留在栅格的中心位置。

(1)路径长度

路径长度最短能节约AGV工作时间及运行成本。路径长度子目标函数f1如下：

(1)

式中，n表示路径经过的总节点数(包含起点和终点)；xi、yi分别表示节点i的横纵坐标；L(i,i+1)为节点i、i+1之间的距离，如图1所示。

图1 路径长度、转角示意图

(2)转角和

AGV在转弯时会减速以避免车速过大导致车体侧翻或甩落所运载的货物。当转弯较多时，AGV频繁的进行减速控制，且转角过大会增加低速运行的时间。因此选择转角和作为规划子目标之一，对转角和进行有效约束能节约工作时间、减少转弯导致的轮胎磨损等机械损耗。转角和函数f2如下：

(2)

式中，θ(i,i+1,i+2)表示路径转角，如图1所示。

(3)危险率

AGV通过车载的导航传感器实时定位并由环境传感器感知周围障碍物信息。由于传感器自身精度缺陷易导致AGV所获得的定位信息和环境信息间存在一定误差，特别是距障碍过近时，测量误差可能会造成AGV与障碍物间产生摩擦或碰撞。

AGV与障碍物距离越近，危险率越高，当AGV距离障碍物两栅格以上时，受障碍物影响较小可忽略。危险率函数f3如下：

(3)

其中，

式中，D(i)表示节点i处的危险率；obj为离节点i最近的障碍物栅格中心。

(4)避障等待时间

当AGV遇到动态障碍物时，需暂停运动并等待障碍物离开。避障等待时间函数f4如下：

(4)

式中，b代表总避障次数，T(o)代表第o次避障等待时长。

1.2 多目标路径规划模型的建立

(5)

理想值均取所有待评价路径中该子目标的最小值。

同时，采用曼哈顿距离描述各子目标函数值与理想值间的接近程度。由式(1)～式(5)构建AGV多目标路径规划评价函数F为：

(6)

由此AGV多目标路径规划模型为：

Y=minF

(7)

其中，Y为路径规划总目标,目的是求一条从起点到终点的连续无碰撞且评价函数值最低的路径。

1.3 基于熵权法的评价函数权值确定

熵权法是客观的权值计算方法，通过信息熵计算出各指标的熵权，再利用熵权对权值进行修正，与其它权值计算方法相比评价结果具有较好的客观性[9]。考虑式(1)～式(4)所示子目标对评价函数影响不完全相同，无法主观衡量子目标间的优劣、占比程度，因此选用熵权法根据实际路径信息计算式(6)中w1～w4的值，具体步骤如下：

步骤1：构建原始数据矩阵。由m个待评价路径，s(1≤s≤4)个子目标构成原始数据矩阵R′：

(8)

步骤2：标准化处理。旨在消除指标间的量纲差异，记标准化处理后的矩阵R=(ruv)m×s。因路径长度值、转角和、危险率、避障等待时间均越小越好，为负向指标，则标准化处理公式为：

(9)

步骤3：计算第v个子目标的熵值hv。

(10)

其中，

步骤4：确定各子目标的权值大小。

(11)

2 改进多目标蚁群算法

传统蚁群算法[10-12]主要对路径长度进行优化，本文对蚁群算法做出改进，将蚁群算法扩展至多目标函数优化。

2.1 改进蚂蚁择路方式

栅格地图中蚁群运动可看成从当前栅格中心向下一栅格中心转移过程的积累。蚂蚁的下一可转移栅格是与当前相邻的八个栅格，标号如图2所示，偶数栅格表示直向转移栅格，奇数栅格表示斜向转移栅格。若AGV向3号或5号栅格转移，可能出现AGV与障碍物栅格顶点摩擦或碰撞的情况，影响AGV正常运行。对下一栅格选取方式改进如下：

斜向择路时，验证AGV当前位置与下一斜向栅格中心连线的垂线上的两个最近栅格是否有障碍物，若有，则将斜向栅格标记为不可转移栅格。如图2所示，可将3号和5号栅格标记为不可转移栅格。

图2 蚁群择路栅格模型

2.2 改进信息素播撒机制

由于信息素浓度只受路径长度影响，其它子目标对蚁群指引作用较小，蚁群多目标寻优能力不足。本文利用非支配排序算法对每次迭代的可行路径分层，层数越靠前，表明该层路径至少在一个或多个子目标上很优，给予该层中的路径更多的信息素增量，从而使多个目标共同指引蚁群寻优。

非支配排序算法的核心思想便是支配比较。将路径支配的概念描述如下：路径A、B均为可行路径，若A在某个子目标上优于B，且其余子目标上均不弱于B(可以相等)，则称路径A支配路径B；否则路径A与B是非支配关系。由一系列不被其他路径所支配的路径组成最优路径集合。

利用非支配排序对路径分层，步骤如下：

步骤1：每次迭代结束后，将可行路径存入集合G中，并保存路径子目标函数值。

步骤2：对于G中的任一路径p，都与其余路径进行支配关系比较，统计支配路径p的路径数目np、被p所支配的路径集合Sp。若np=0，则表示路径p不受其它任何路径支配，将其分入T1层。

步骤3：对于T1中的路径p，将Sp集合中的每一个成员q的支配计数nq减1。若nq=0，则表示路径q除了受T1层路径支配外，不再受其它路径支配，将q分入T2层。

步骤4：依步骤3方式，将对应路径分入T3层。

步骤5：剩余路径分入T4层。

划分完毕后，有如下关系：同层路径之间相互非支配；对Tl+1(l=1,2,3)层中的任一路径，在Tl层中至少存在一条支配它的路径。

前层路径更优，应给与更多的信息素增量以加强对后续蚂蚁的指引作用，同时弱化后层路径信息素增量，改进如下：

(12)

其中，

3 多目标路径规划算法流程

综上所述，本文所设计的基于改进蚁群算法的多目标路径规划步骤如下：

步骤1：采用栅格法对物流仓储环境建模。

步骤2：确定子目标函数及多目标路径规划模型。

步骤3：初始化参数。初始化蚁群参数及最优路径集合Q，Q用于存放最优路径。

步骤4：蚁群迭代。开始此次迭代，依据改进的蚂蚁择路方式确定可行栅格，利用轮盘赌法选出下一个节点，直至终点或蚂蚁“死亡”。

步骤5：非支配排序。依据式(1)～式(4)计算可行路径子目标函数值。利用非支配排序算法对路径分层。

步骤6：信息素更新。依据式(12)更新信息素。

步骤7：更新最优路径集合Q。对于排序后T1层中的路径p，如果p对于集合Q来说是非支配的，则加入集合Q，并删除Q中被p所支配的路径。

步骤8：迭代次数更新。迭代次数d=d+1，当迭代次数最大时，结束迭代，否则返回步骤4。

步骤9：权值计算。输出最优路径集合Q，利用熵权法计算子目标权值。

步骤10：输出最终路径。依据式(6)计算路径评价函数值，取最小评价值路径为最终输出路径。

4 实验结果与分析

4.1 静态环境下实验结果与分析

物流仓储环境下货物分布较为规整，构建如图3所示的栅格地图，栅格行列数a=30；起点坐标(0.5,0.5)，终点坐标(29.5,29.5)。设置蚁群最大迭代次数Nmax=50，蚁群数量M=100。地图中无动态障碍物，暂不考虑避障等待。利用本文改进多目标蚁群算法得到最优路径集合Q，Q中的路径如图3所示，路径信息如表1所示。

图3 静态环境改进蚁群路径图

表1 静态环境改进蚁群路径信息表

由图3和表1可以看出，改进的多目标蚁群算法得到的路径1～4分布范围较广，有沿着地图中部斜向指向终点的路径1、4，也有沿着地图边缘的路径2、3，各路径之间相互非支配，优势均不相同，路径2转角和最小，路径3危险率最低，路径4长度最短，路径1性能最均衡。

路径1、4因为多斜向行走，路径长度较其它两条路径更小，但受地图中心障碍物影响，转角较多，平滑性较其它两条路径有所下降；同时，路径2前半段紧贴障碍物，危险率在4条路径中最高。

上述结果表明：静态环境下，本文改进的蚁群算法对各子目标均能有所优化，能引导蚁群多目标寻优，实现AGV多目标路径规划。

在相同的蚁群参数、栅格环境及择路方式下，利用传统蚁群算法寻路，结果如图4所示，路径信息如表2所示。

图4 静态环境传统蚁群路径图

表2 静态环境传统蚁群路径信息表

由于传统蚁群算法中路径长度对寻优起主导作用，图4中路径5斜向行驶至终点。与改进的多目标蚁群算法路径1～4相比：路径5较路径1在长度上减小了5.96%，转角和增加了35.76%，危险率增加了16.15%；较路径2在长度上减小了9.84%，转角和增加了137.5%，危险率增加了5.59%；较路径3在长度上减小了6.25%，转角和增加了90.06%，危险率增加了30.17%；较路径4在长度上增加了1.13%，转角和增加了5.59%，危险率增加了16.15%。

可以看出，路径5相比于改进的多目标蚁群算法路径1～3，小幅缩短了路径长度，但是转角和、危险率上都有所上涨，路径5在提升路径长度的同时，损失了路径的平滑性和安全性；且路径5各方面性能均比路径4差。

利用熵权法对5条路径的信息进行计算，得到各子目标权值如表3所示，最终评价函数值如表4所示。

表3 静态环境子目标权值表

表4 静态环境评价函数值表

从表4可以看出，较传统蚁群算法路径5，路径1～4的评价函数值更小，路径更优，且路径3评价函数值最小，仅为1.85，最趋近于理想值，为静态环境下的最优路径。可得出，静态环境下，本文改进的蚁群算法能进行有效的多目标路径寻优，较传统蚁群算法所得路径综合性能更优。

4.2 动态环境下实验结果与分析

物流仓储环境中可能出现人员走动、货物摆放位置临时改变等动态情况，在上述静态环境中添加动态障碍物以研究本文改进蚁群算法所得路径在动态环境中的适应能力。为方便研究，对动态障碍物作如下设计：在如图5所示的每个黄色方框内随机产生一个动态障碍物；其大小能被1栅格完全容纳；动态障碍物活动范围即为黄色方框区域；动态障碍物随机产生，沿水平方向匀速直线运动，触碰到活动边界时沿镜面反射方向折返。

图5 动态障碍物活动范围图

AGV分别沿路径1～5前进，每次避障等待时间为5 s。最终各子目标信息如表5所示。

表5 动态环境路径信息表

从表5可得，路径1、2、5均遭遇一次动态障碍物，进行了一次避障等待，路径4避障2次，路径3避障0次。权值计算如表6所示，路径评价值如表7所示。

表6 动态环境子目标权值表

表7 动态环境评价函数值表

由表7可以看出，路径3评价值为1.48，最趋近于理想值路径，为最优路径；传统蚁群算法所得的路径5评价值最大，路径综合性能最差。路径4虽然比路径5多一次避障等待，但评价值较路径5更低，路径更优。可以得出，若地图中出现了少量动态障碍物，本文改进的多目标蚁群算法所得路径仍然具有更强的适应性，且其综合性能、整体评价较传统蚁群路径更优。

5 结论

根据AGV运行需求选取子目标，提出一种基于改进蚁群算法的AGV多目标路径规划方法，该方法改变栅格选取方式、利用非支配排序算法改进信息素增量、利用熵权法确定权值。仿真结果表明动静态环境下本文设计算法能有效进行多目标路径寻优，所得路径分布广、性能高，综合评价更优。