基于改进蚁狮算法的仓储机器人路径规划

周 晟，郦佳燕

(武警士官学校a.基层后勤管理系；b.基础部，杭州 310000)

0 引言

近年来，高速发展下的物流行业对仓储机器人的高效工作性能需求日益突显，在库房内迅速找寻物资并移动至出库工位或操作工位的时间节制了物流工作的整体效率，因此，仓储机器人路径规划研究具有十分重要的意义，亦是现代机器人研究的重要方向。

赵克新等[1]引入混沌算子改良算法中蚂蚁的随机游走后，有效结合蚁狮构造全局搜索和局部搜索并行的双线模式，面对复杂环境下的航线最优化设计具有良好的应用，有效提升算法寻优能力。张焕龙等[2]将模拟退火算法与蚁狮优化算法有机结合，合理利用边界收缩机制和蚂蚁与蚁狮之间的联系，以提升图像匹配效率、匹配精度。后采用局部嵌入准则进行评估，切换搜索策略，实验验证，改进算法优化效率高、匹配速度快、匹配精度高。赵小国等[3]采用动态随机搜索策略并改良搜索半径的收缩机制后，应用于T-S模糊辨识中含噪声的非线性系统问题，仿真验证时噪声被有效抑制，改进方法具优良效用。

针对物流行业仓储机器人工作效率问题，文中提出一种改进蚁狮算法，将传统的时间最优化设计转换为仓储机器人运行中，路径最短且转弯次数最少的多目标路径规划问题，以保证工作运行效率的同时，使得仓储机器人运行更加平稳[4-5]。文中采用栅格法划分工作环境，合理设定目标函数、约束条件后，通过优化算法实现路径规划，结合MATLAB进行仿真分析，验证算法的有效性，为后续研究提供理论支撑。

1 问题描述与模型构建

1.1 问题描述

设定在智能库房中，仓储机器人在接受任务后，从初始点出发规避障碍物后到达任务点完成工作任务，在完成过程中要求行径路线实现路径最短且转弯次数最少，并假定：

(1)智能库房平面地图已知；

(2)栅格分为可通过栅格和不可通过栅格；

(3)仓储机器人工况良好；

(4)任务初始点和结束点位置已知。

1.2 模型构建

文中设定库房内工作环境为静态，障碍物静止不动不存在外界干扰，以仓储机器人在库房工作时，转弯次数最少和路径最短为目标，结合栅格法构建工作环境模型和多目标路径规划求解函数式。

1.2.1 环境模型构建

栅格法可以将路径规划问题转变为路径途径点的集合，利用相应算法在栅格中找寻最优解的方法。由于栅格法建模简单，能够最大程度地反映库房内实际障碍物情况，因此文中采用栅格法构建工作环境模型示意图，如图1所示。

图1 工作环境模型示意图

仓储机器人在栅格中的运行方向如图2所示。

图2 仓储机器人运行方向示意图

为降低计算量、优化栅格模型，设定栅格的每一个长度为一个单位长度，黑色栅格为障碍栅格，白色栅格为可通过栅格，S为栅格序号，L为栅格边长，栅格序号与栅格中心坐标对应关系如式(1)：

(1)

1.2.2 转弯次数最少目标函数

设dn表示第n个节点上的转弯次数，N(d)表示路径转弯次数的求和，k为斜率，n为路径途径的栅格中心坐标顺序序列号，(xn,yn)，(xn+1,yn+1)分别为路径通过的相邻栅格中心点的坐标[6-7]。仓储机器人运行稳定性由转弯次数决定，转弯次数越少，运行越平稳，目标函数如式(2)所示。

(2)

1.2.3 路径最短目标函数

仓储机器人运行路径的距离决定工作效率的高低，为提升物流工作的整体效率，设定起、止点条件下，求解最短行进路径，其目标函数如式(3)：

(3)

式中，L(P)表示最短路径之和，L(Pi,Pi+1)为点Pi至Pi+1之间的距离，(xi,yi)，(xi+1,yi+1)分别为转向点在空间中，当前栅格中心点的坐标和下一个点的坐标，N(d)为转向的次数。

1.2.4 效用函数

文中通过线性加权与效用函数Z(L,N)将转弯次数最少目标函数与路径最短目标函数建立联系，转换为传统的多目标求解问题，使得求解结果同时满足路径最短和转弯次数最少。其中，效用函数公式如式(4)：

Z(L,N)=ω1L(P)+ω2N(d)

(4)

式中，ω1是路径长度权重系数，ω2是转弯次数权重系数，L(P)表示最短路径的求和，N(d)为转向次数的求和。

2 蚁狮算法

蚁狮优化算法是通过观察自然界中蚁狮的捕猎行为所提出的一种新型智能优化算法，算法中包含蚁狮、精英蚁狮和蚂蚁3个个体[8-11]。首先，蚁狮和蚂蚁的位置以随机方式初始化，再通过轮盘赌和随机游走的策略确定蚂蚁的位置，算法优化过程中，蚂蚁的游走会受到边界和蚁狮陷阱的影响并采用适应度函数对所有的游走蚂蚁进行评估、迭代。设定每一轮迭代中最优解的蚁狮称为精英蚁狮，优化过程中将精英蚁狮不断与最优解的蚁狮进行比较，循环计算求解最优个体。

文中采用式(5)模拟蚂蚁的随机游走。

X(t)=[0，cs(2r(t1)-1)，…，cs(2r(tn)-1)]

(5)

式中，cs表示计算累计和，n表示最大迭代次数，t表示随机游走的步骤，r(t)表示随机函数。

算法优化中，蚂蚁依据随机游走更新迭代位置参数，但是搜索空间存在边界限制，所以式(5)无法直接更新蚂蚁的位置参数，需采用式(6)对其进行归一化处理。

(6)

文中采用式(7)和式(8)计算蚁狮陷阱对蚂蚁随机游走状态的影响。

(7)

(8)

为规避局部最优解，在优化过程中，蚁狮算法采用轮盘赌算子和适应度函数相结合进行蚁狮选择，精英蚁狮的设定是算法优化的重要设定，确保优化的任意阶段均可获取最优解。鉴于精英蚁狮对蚂蚁迭代时随机游走的干扰，文中假定任意一只蚂蚁在选定蚁狮周围随机地通过轮盘赌或随机游走进行行走，如式(9)所示。

(9)

当蚂蚁陷入陷阱时，蚁狮将自主减少陷阱，此时蚂蚁随机游走搜索半径将自适应地缩小，随着迭代次数的持续增加，蚁狮陷阱和精英蚁狮的设定将不断收缩边界条件，逐渐求解全局最优解。

(10)

(11)

式中，I随迭代次数的增加分线段性递增。

(12)

式中，t表示当前迭代次数，T表示最大迭代次数，w取决于当前代数。

最后阶段，当蚂蚁具有更优位置参数时，蚁狮捕获蚂蚁并依据等式(13)进行位置参数更新。

(13)

3 改进的蚁狮算法

针对传统算法的局限性，文中引入混沌序列增强种群的均匀性和遍历性，依据蚂蚁的游走行为采用随机分形搜索策略，增强算法探索能力，采用自适应边界策略改善蚂蚁游走时边界趋同情况，提高算法开发能力。

3.1 混沌序列种群初始化

蚂蚁的位置信息保存在位置矩阵MAnt中，Ai,j表示第i个蚂蚁第j维的位置值，适度值fi保存在矩阵MOA中，蚁狮的位置信息保存在矩阵MAntlion中，ALi,j为第i个蚁狮第j维的位置值，蚁狮的适应度fLi保存在矩阵MOAL中。

(14)

(15)

(16)

(17)

算法优化设计时考虑到立方映射产生混沌变量的均匀性优良，为规避算法陷入早熟获取结果为局部最优，文中采用立方映射方法进行蚂蚁和蚁狮的初始位置信息设置。初期阶段，先产生一个随机初始序列x，元素范围均在[0,1]之间，代入立方映射式(18)生成混沌序列。

(18)

式(18)在初始值不为零时求解序列真实有效，且既能求解蚂蚁位置信息Ai,j，又可以求解蚁狮的位置信息ALi,j，求解计算后由式(19)映射返回求解空间。

(19)

式中，x*表示返回求解空间后赋给蚂蚁或蚁狮个体的数值；ub、lb表示求解空间的上、下边界。

随机游走更新目标数值时，以当前最优个体与全局最优个体为目标进行求解，计算公式如式(20)所示。

(20)

(21)

(22)

3.2 随机分形搜索方程

莱维飞行是服从莱维分布的随机搜索方法，其位置更新如式(23)所示。

(23)

式中，Levy(λ)表示服从莱维分布的路径，1<λ≤3；xi(t)表示第t代的第i个解；l表示控制步长的权重，xb表示当前的最优解。

目前常采用Mantegan算法模拟求解过程，降低莱维分布计算难度，步长计算公式如式(24)所示，仿真结果如图3所示。

(24)

图3 莱维飞行仿真结果示意图

文中将莱维飞行与蚂蚁的搜索策略相结合，构建随机分形搜索方程，如式(25)所示。

(25)

式中，q表示种群数量；a表示比例因子；Ai表示最初的蚂蚁位置。

3.3 自适应边界策略

结合式(10)～式(12)可知，蚂蚁围绕蚁狮的边界由I值决定且同一轮迭代时趋同的边界降低了算法的多样性，不利于全局最优解的获取，文中提出自适应边界策略用以提升蚂蚁围绕蚁狮游走的多样性，计算公式如式(26)所示。

(26)

式中，rand为(0,1)内均匀分布的随机数。

3.4 改进的蚁狮算法流程

步骤1：设定最大迭代次数为M；蚂蚁个体数目与蚁狮个体数目均为N，维数为D；求解空间的上界为ub与下界为lb；

步骤2：根据式(18)～式(20)混沌初始化蚂蚁和蚁狮的位置数值，由矩阵MAnt和MAntlion分别储存，矩阵MOA和MOAL分别储存蚂蚁与蚁狮的适应度值；

步骤3：排序适应度值，选取初代精英蚁狮；

步骤4：根据式(10)、式(11)更新当前迭代次数中，所有蚂蚁随机游走的最大值和最小值ci、di；

步骤6：根据式(9)、式(25)采用随机分形搜索策略更新蚂蚁个体位移数值并求出所有个体的适应度值；

步骤7：判断是否达到最大迭代次数，若达到，则循环结束并输出精英个体，若未达到，返回步骤3。

改进的蚁狮算法流程图如图4所示。

图4 改进算法流程图

4 仿真验证

为测试算法的寻优性能，文中设定蚂蚁和蚁狮的种群规模数均为50，最大迭代次数为200，搜索维度D=10,20，c1=0.4，c2=0.6，起始点、终止点等初始参数值后，对多个障碍物位置不同的库房环境进行仿真验证，其结果如图5所示。

(a) 狭小空间路径规划 (b) 有一定空间的路径规划

(c) 收敛曲线变化趋势图5 仓储机器人路径规划仿真

图5a中仓储机器人能够穿过狭小的轨迹空间找寻目的地，其收敛曲线趋于平稳的迭代次数少，均表明改进蚁狮算法具有良好的优化性能，适用于库房内的狭小空间，高效地完成物资堆垛工作。图5b中仓储机器人能够避免在上部区域内以较长的路径轨迹运行到目的地，有效在下部区域通过较短的路径轨迹，找寻目的地完成物资堆垛工作，其收敛变化曲线在初始阶段经过一定的震荡后，能够迅速稳定趋于一定的空间范围，表明改进算法具有迅速的判断、寻优能力，迅速找寻路径运行方向，有效节约时间，提高算法的工作效率。

5 结论

文中以仓储机器人物资堆垛为例，借助MATLAB软件结合栅格法，构造物资堆垛运行轨迹示意图，提出一种改进蚁狮算法，以转弯次数最少、路径最短为目标函数，得到结论如下：

文中根据蚂蚁的游走行为，采用随机分形自适应搜索策略，增强算法的探索能力。根据蚂蚁游走的边界都完全相同，降低了算法的多样性，不利于算法寻找全局最优解，提出自适应边界策略，提高游走的随机性和多样性，增强算法的开发能力和全局搜索能力，有利于找到全局最优解。