面向智能仓储系统的多AGV运行策略优化

赵雨亭，叶 峰，赖乙宗，谢先治，洪 峥

（华南理工大学 机械与汽车工程学院，广州 510640）

面向智能仓储系统的多AGV运行策略优化

赵雨亭，叶 峰，赖乙宗，谢先治，洪 峥

（华南理工大学 机械与汽车工程学院，广州 510640）

该文研究了智能仓储中自动导向车AGV 2种运行方向模式的效率。对于局部回环运行模式，为提高AGV的运行效率，提出了基于道路复用的AGV运行策略优化方案；对于单个AGV存在潜在捷径的特定转向序列的路径，在与其他AGV无碰撞和冲突的条件下进行优化。给出了优化适用的条件和实现方法。仿真试验证明了优化的AGV运行策略的有效性和可用性。

自动导向车；自动引导搬运车；局部环路；智能仓储；运行策略；运行方向模式

智能仓储，摒弃了传统仓储系统以人力进行分拣，效率低下的缺点，转而以自动导向车AGV（automate guided vehicle）作为运载工具，辅以智能调度系统，实现了物流仓库“由人取货物”至“从货物到人”的转变，大大提高了物流分拣的速度。AGV的运行方式与智能仓储的运行效率密切相关，因此对AGV运行策略进行研究具有重要意义。

国内外已有对仓储AGV的实践和报道。国外的Kiva System在2006年实现了基于AGV的仓储系统[1]，并于2012年被Amazon收购。国内有海康威视机器人、深圳欧铠机器人等。在AGV研究方面，文献[2-3]总结了通用的AGV调度和路径规划问题及解决方案。文献[4]给出了空间运动的一般规划方法。文献[5]给出了自主运输车的现状和研究思路。截至目前，国内外对AGV的调度策略研究多集中于柔性制造系统（FMS）领域[6-7]，对智能仓储领域AGV应用和研究则寥寥可数。

在此，针对智能仓储货架区AGV运行方向的2种规定模式进行了研究，分析了这2种模式下单台AGV访问货架的距离结果。对于局部回环地图中规划出的“几”字形路径，在避免碰撞和死锁的基础上，提出了运行策略上的优化方法，通过计算机仿真，验证了所提优化后运行策略的有效性。

1 智能仓储工作方式

智能仓储系统的主要功能是货物入库和出库。无论是入库操作还是出库操作，都需要AGV从货架区将货架取出，送至入（出）库区。待工人将货物从货架上取出，AGV再将货架送回至货架区，送回的位置随AGV调度系统的制定而给定。

智能仓储的实际区域一般划分为入库区、出库区、货架区和中间区域。多以栅格法构建地图模型。以下重点研究货架区AGV的运行策略。

1.1 AGV运行方向的两种模式

为了简化AGV路径规划，AGV在路段中的运行方向一般都在设计时期给定，给定的模式通常有2种，即交叉模式（模式1）和局部环路模式（模式2），如图 1 所示。

图1 两种AGV运行方向模式Fig.1 Two AGV running patterns

在图1中，带阴影的栅格为货架，无阴影的栅格为通道；通道上标示有圆点的栅格称为交叉点；2个交叉点之间（不包含交叉点）的白色栅格连接成的区域称为路段；通道上的箭头表示该路段的方向。AGV仅能从纵向通道中访问货架，而横向通道仅供AGV通行使用。

1.2 模式比较

为了评估单个AGV在2种规定运行模式下的效率，假设1辆AGV存在于图2所示的中心位置（标有数字0），计算其访问周围4×4组货架时运行的步数。AGV只能向南向北向东或向西移动1格（称作1步），且AGV只能从纵向路段访问至相邻货架，不考虑转弯所消耗的步数。计算的结果如2所示，货架处标明的数字为AGV移动到该货架最近的步数。

图2 两种模式下AGV访问货架所需步数Fig.2 AGV steps needed in two patterns

以AGV起始位置为原点，建立笛卡尔坐标系。以象限为单元，计算AGV访问单元内货架移动步数的均值，可得表1。分析数据可知，单个AGV在访问第Ⅰ象限的货架时，模式1优于模式2；在访问第Ⅱ象限货架时，模式1与模式2持平；在访问第Ⅲ象限和第Ⅳ象限货架时，模式1劣于模式2。观察发现，模式2下规定的路段方向是关于x，y轴对称的，故单个AGV在模式2条件下访问4个象限货架的平均值是相同的。

表1 2种模式下AGV运行步数的均值Tab.1 Average of AGV steps needed in two patterns

综合考虑，模式2对于单个AGV路径规划而言更优。即使如此，模式2在多AGV路径规划下仍具有优化的空间，在此给出模式2下优化的运行策略。

2 局部回环模式下AGV运行策略优化

在模式2条件下，考虑图3所示情形，AGV在经过S访问T处货架时，根据最短路径规划的算法（如经典的Dijkstra算法或A-Star算法），可能有2种规划的结果，分别标注了数字1和2，这2种AGV移动的步数相同。由其形状，可称这种路径为“几”字形路径。当1台AGV沿此“几”字形运行而附近区域无其他AGV影响时无疑是低效的，故针对这种已经规划好的路径的情形，在多AGV运行时，考虑到AGV之间可能存在的碰撞冲突问题，通过动态调整AGV运行策略，提高运行效率。

图3 目标为T且经过S的2种“几”字形路径Fig.3 Two kinds of special path when target is T passed by S

定义函数 P（v）＝（Row（v），Col（v）），式中：v 为任一栅格；Row（v）为栅格 v 所在位置的行数；Col（v）为栅格v所在位置的列数。

设Ai为标作i的AGV。Ai正在运行的栅格序列为 Path（Ai），有式（1）成立：

对于栅格 vij和栅格 vi（j+1），有式（2）或式（3）成立，且对于任意整数不同于。Abs（）为取绝对值的函数：

式（4）中，dij（ j∈［1，n-1］∩Z）为 vij到 vi（j+1）的方向。dij有4种取值情况：

特别地，定义di0为一个数值，其与Ai在栅格vi1处的东西北朝向的关系为

式（7）给出了自变量为Ai的转向函数，Ai在vij处应进行的转向动作取值为 zij（ j∈［1，n-1］∩Z），满足

当 zij＝-1 时，Ai在 vij处左转 90°；

当 zij＝0 时，Ai在 vij处不必转向；

当 zij＝1 时，Ai在 vij处右转 90°；

当 zij＝2时，Ai在 vij处顺时针或逆时针旋转180°，且可以推断此时 j＝1。

使用记号 v（i，j）表示 vij，使用记号 z（i，j）表示zij。 可以推知，v（i，x1）（x1∈［1，n-1］∩Z）是“几”字形第 1 交叉点的充要条件，即存在整数 x1＜x2＜x3＜x4≤n-1，满足以下条件1、条件2和条件3：

条件 1v（i，xk）（k＝1，2，3，4）是交叉点。

条件 2∀x∈（x1，x2）∪（x2，x3）∪（x3，x4）∪Z，Z（i，x）＝0。

条件3“几”字形转向条件，即式（9）为恒真式，

在条件 1、条件 2、条件 3 成立时，称 v（i，xk），其中 k＝1，2，3，4 为“几”字形第 k 交叉点。

根据“几”字形道路经过的交叉点情况，将“几”字形道路分为4类，Ⅰ型，Ⅱ型，Ⅲ型和Ⅳ型，其性质如表2所示。

表2 “几”字形路径类型的交叉点转向及捷径路段方向Tab.2 Turns on crossroads and direction of shortcuts in special path

定义两栅格 a与 b的捷径 ShortCut（a，b）为 n-元组，其形式为

其中，v1=a，vn=b，元组中任意两栅格对象是不同的，且对于任意整数j∈［1，n-1］，仅满足条件4或条件5二者之一：

条件 4Abs（Col（vj）-Col（v（j+1）））＝1

且 Row（vj）＝Row（v（j+1））

条件 5Abs（Row（vj）-Row（v（j+1）））＝1

且 Col（vj）＝Col（v（j+1））

“几”字形第1交叉点存在意味着“几”字形的第2，第3，第4交叉点也是存在的，也意味着“几”字形路径存在。若Path（Ai）中存在“几”字形第1交叉点 v（i，x1），则称路径 Path（Ai）在单 AGV 条件下对于栅格v（i，x1）是可优化的。优化的方式是将Path（Ai）中的 v（i，x1），…，v（i，x4）序列替换为ShortCut（v（i，x1），v（i，x4））中所含的对象序列。 当“几”字形路径属于Ⅰ型和Ⅱ型时，对应的捷径满足条件4；当“几”字形路径属于Ⅲ型和Ⅳ型时，对应的捷径满足条件5。

假设Path（Ai）在单AGV条件下是可优化的，此时并不能称其在多AGV情况下也是可优化的。因为在优化使用的捷径方向是与规定方向相悖的，可能导致已优化AGV与其他AGV在捷径（如图3中双箭头捷径）发生冲突。在此，给出不发生冲突，即路径在单AGV条件下可优化同时在多AGV情况下也可优化的充分条件：捷径不含Ai除之外的其他AGV（路径属于Ⅰ型、Ⅱ型），或捷径和与其相邻的货架不含除Ai之外的其他AGV（路径属于Ⅲ型、Ⅳ型）。

在集中式管理的AGV系统中，优化条件的判定是通过中心控制系统进行的。当AGV经过每一个交叉点时，判断AGV所执行的路径是否是关于交叉点可优化的且满足多AGV可优化充分条件，如果不满足，则路径不变，否则执行优化。

3 仿真

为测试所提方法的优化效果，根据图4所示地图，在PC上使用Matlab进行多AGV的计算机仿真试验，PC的硬件信息为CPU Core I7-4790K@4.0 GHz，RAM 16 GB。仿真所用的货架区域大小为25×25。

图4 测试使用的货架区示意Fig.4 Illustration of shelf area for testing

AGV在货架区进行的任务有3种：①从某个外围交叉点出发取货架；②从某个货架出发至某个外围交叉点以离开货架区；③从一个货架上卸载，准备去另一个货架位置取货架。

在所述的每次仿真中，AGV的任务随机产生，即AGV任务的起始位置和终止位置在不同任务下从外围交叉点或货架上随机选取，并且不重复。为考虑不同的AGV数量对调度策略优化结果的影响，仿真试验模拟了在2～10台不同数量AGV下调度策略优化的结果。每种不同AGV数量下试验1000次。当某AGV运行到的下一个栅格存在其他AGV时，此AGV暂停运动。当多台AGV同时进入某一空交叉点时，根据AGV优先级判定进入交叉点的AGV。考虑到AGV在转弯时的时间损耗，设AGV旋转90°消耗时间与AGV在2个栅格之间移动消耗时间相同，即在时间上，AGV左转90°或右转90°相当于额外移动一步。不同数量的AGV在优化前和优化后的运行步数见表3。

表3 不同数量AGV在优化前和优化后的运行步数Tab.3 Running steps in different count of AGV before and after optimization

此外，还计算了单AGV可优化“几”字形路线在多AGV同时运行条件下的优化比例，如图5所示。

图5 路径得到优化的比例曲线Fig.5 Optimized path percentage curve

分析表3可知，所提方法对AGV运行效率具有提高作用，且提高的效果随AGV数量的增加而逐步减小。图5显示，同时运行的AGV数量越多，“几”字形路径得到优化的比例越少。这是由于随着AGV数量的增多，AGV占用待优化“几”字形路径的捷径路段和“几”字形路径的第4交叉点的比率会提高，致使优化比例下降。

4 结语

研究了局部地图下单个AGV分别在2种不同的运行方向模式下访问货架的运行步数，得出了局部环路对单个AGV访问更优的结论。针对局部环路存在的“几”字形路径会导致AGV运行效率低下的问题，提出了运行时在不存在与其他AGV碰撞的情况下动态更改当前AGV路径的运行策略。仿真试验证明，优化后的策略在多AGV仓储系统中对AGV运行效率具有提高作用，且有提高作用随AGV的增加而下降的规律。

[1] Wurman P R，D'Andrea R，Mountz M.Coordinating hundreds of cooperative，autonomous vehicles in warehouses[J].AI magazine，2008，29（1）：9.

[2] Qiu L，Hsu W J，Huang S Y，et al.Scheduling and routing algorithms for AGVs：a survey[J].International Journal of Production Research，2002，40（3）：745-760.

[3] Fazlollahtabar H，Saidi-Mehrabad M.Methodologies to optimize automated guided vehicle scheduling and routing problems：a review study[J].Journal of Intelligent&Robotic Systems，2015，77（3-4）：525.

[4] La Valle S M.Motion planning[J].IEEE Robotics&Automation Magazine，2011，18（2）：108-118.

[5] Andreasson H，Bouguerra A，Cirillo M，et al.Autonomous transportvehicles：where we are and whatismissing[J].IEEE Robotics&Automation Magazine，2015，22（1）：64-75.

[6] Zheng Y，Xiao Y，Seo Y.A tabu search algorithm for simultaneous machine/AGV scheduling problem[J].International Journal of Production Research，2014，52（19）：5748-5763.

[7]Wang C，Wang L，Qin J，et al.Path planning of automated guided vehicles based on improved A-Star algorithm[C]//IEEE International Conference on Information and Automation.IEEE，2015：2071-2076.

Multi-AGV Running Strategy Optimization for Intelligent Warehouse Systems

ZHAO Yu-ting，YE Feng，LAI Yi-zong，XIE Xian-zhi，HONG Zheng
（School of Mechanical and Automotive Engineering，South China University of Technology，Guangzhou 510640，China）

The operational efficiency of two common AGV running patterns in intelligent warehouse is studied.In order to improve the operational efficiency of AGV，AGV operation strategy optimization scheme based on road reuse is proposed for local cyclic operation mode.The path is optimized under conditions of non-collision and conflict-free with other AGV，which has a specific steering sequence with a potential shortcut for a single AGV.Applicable conditions and implementation method of the optimization are provided.Simulation results show that the optimization method is effective and feasible.

automate guided vehicle（AGV）；automate guided van；local cyclic；intelligent warehouse；running strategy；run direction mode

TP24；TH242

A

1001-9944（2017）11-0067-05

10.19557/j.cnki.1001-9944.2017.11.016

2017-04-24；

2017-08-02

广东省教育部产学研结合重大项目（2012A090300013）；广东省公益研究与能力建设专项（2016A010106005）

赵雨亭（1995—），男，硕士研究生，研究方向为移动机器人；叶峰（1972—），男，博士，副教授，研究方向为嵌入式系统设计与机器视觉。