基于GWM的多AGV路径冲突处理算法

过金超 张飞航 兰东军 曹宏 王普杰

摘要：针对AGV现有的路径规划方法无法解决对发任务、死锁问题等，提出了一种新的AGV路径冲突处理方法GWM，以解决更为复杂的路径冲突问题.但GWM在部分冲突场景中的处理效率不高，在此基础上又提出了基于GWM的路径冲突处理算法OCWG.该算法融合了等待法、重新规划法和GWM 3种路径处理方法，在AGV位置刷新的时候，检测其在安全距离内是否会与其他AGV发生冲突，并且能根据实时的系统状态选择合适的路径冲突处理方法，使其中一辆AGV行驶到空闲点进行让路.测试结果表明，OCWG算法的总花费时间较少，也能满足包括重复任务和对发任务在内的所有需求，而且不会出现触发碰撞警告和死锁问题.

Abstract：In view of the fact that the existing path planning methods of AGV are unable to solve the problem of dispatching task and deadlock， a new path conflict processing method named GWM was proposed to solve more complex path conflict problems. However， GWM was not efficient in some conflict scenarios. On this basis， a GWM|based path conflict processing algorithm named OCWG was proposed. This algorithm combined three path processing methods： waiting method， rerouting method and GWM. When the AGV position was refreshed， it detected whether it would conflict with other AGVs in the safe distance， and chose an appropriate path conflict processing method according to the real|time system state. The test results showed that OCWG algorithmtook less time and satisfied all the requirements including repetitive tasks and dispatching tasks， without triggering collision warning and deadlock problems.

关键词：自动导引车;路径冲突处理;GWM;OCWG算法

Key words：AGV;path conflict processing;GWM;OCWG algorithm

中图分类号：TP242文獻标识码：ADOI：10.3969/j.issn.2096-1553.2019.04.011

文章编号：2096-1553（2019）04-0074-07

0 引言

自动导引车（AGV）是指安装有自动导引系统、可沿着导引线或通过视觉导航等方式运动、具有搬运货物等功能、无人驾驶的运输小车[1-2].近年来，AGV在汽车工业和港口运输等领域实现跨越式发展，尤其是在电商物流行业给人们带来了方便与快捷[3-4].由多个AGV组成的多AGV系统可以轻松地在路径足够丰富的地图上进行无冲突路径运动.然而在大多数制造车间，受到空间和场地的影响，实际路径不能像快递业那样自由铺设，因此车间环境对多AGV系统路径规划是一个挑战[5-6].

在企业物流自动化生产线上，单个AGV的路径规划是最短路径搜索的过程，然而如果多个AGV同时运行在一个地图上，仍采用最短路径搜索，势必会造成路径冲突和道路阻塞[7-8].很多学者都倾向于在路径规划阶段把路径冲突的问题考虑进去，提前预知并通过等待法解决路径冲突问题，例如时间窗法[9]、两阶段规划法[10]等.但在实际运行中，AGV不可避免地会发生各种各样的问题，例如速度估计误差、机械故障等[11-12].因此，在多AGV系统中，对路径冲突处理算法的研究是必不可少的.传统的路径冲突处理方法只有等待法和重新规划法，这两种方法针对路径足够丰富的地图可以解决多数冲突问题，但应用于车间环境下的地图有可能出现对发任务、死锁等问题.

本文拟提出基于GWM的路径冲突处理算法OCWG（obstacle， conflict， waiting， giving|way），以解决车间环境下多AGV系统路径冲突问题，并通过实践应用来验证算法的稳定性与鲁棒性，以满足企业物流自动化的要求.

1 问题阐述

1.1 车间环境下的地图模型

车间环境下的多AGV路径规划之所以难度较大，主要是因为其地图模型的独特性.地图模型可分为闭环地图和开环地图.闭环地图是指地图上的每个节点至少连接两条线路，因此AGV不容易出现拥堵问题.网格图是典型的闭环地图（见图1），具有丰富的路径资源，在电商物流行业被大量使用.开环地图是指不能构成闭环的地图，地图中存在许多只连接了一条线路的节点，常见的车间地图（见图2）不能构成闭环地图或仅包含少数闭环线路，通常只有一条或两条主干道，在这样的地图上极易发生路径冲突和死锁问题.

1.2 路径冲突类型

多AGV系统中路径冲突问题可分为6种类型，即追及冲突、对向冲突、路口冲突、路径障碍、终点障碍和死锁问题，其示意图如图3—图8所示.这6种类型又可归结为冲突型问题、障碍型问题和死锁问题3类.

追及冲突是指两辆AGV以相同的方向行驶，其中落后的AGV因为某种原因会以较快的速度行驶，可能会追上靠前的AGV并发生碰撞事故，其速度差可能是由于载货重量不同而引起的.这种情形可通过等待法解决，即后车在前一节点停车，等待前车通过后再行驶.

对向冲突是指两辆AGV以相反的方向行驶，若不采取相应的措施，会在一定时间内发生碰撞事故.造成碰撞事故的原因往往是在路径规划阶段没有解决好两辆AGV对相同路径资源争夺的问题.这种情形一旦发生，如果没有备用路径，会造成死锁问题.

路口冲突是指两辆AGV在竞争路口资源时发生冲突，其原因依然是路径规划阶段没有解决资源竞争问题.出现这种情况，如果双方在路口节点之后的路径不是对方所在的线路，则可通过等待法解决;若双方恰好处在对方的线路上且没有备用路径可取时，会造成死锁问题.

路径障碍是指有其他AGV停靠在运行中的AGV的路径上，阻碍了AGV的前进.该障碍AGV通常是在执行任务或发生机械故障，无法主动对运行AGV进行避让，这种情形下如果没有备用路径可取，只能通过等待法解决.

终点障碍是指有其他AGV停靠在运行AGV的目标节点上，阻止了运行AGV进入目标节点，其原因可能是重复任务的执行时间没有错开.这种情形只能采用等待法，等待障碍AGV执行完任务离开目标节点.

死锁问题是指多个AGV互相阻碍了对方的路径，卡死在一个区域中，无法通过常规方法解决.这种情况常常是在上述其他问题没有解决时产生的，也是在路径规划阶段就需要避免的问题.

2 GWM方法的工作流程

车间工作中常见的是重复任务和对发任务.重复任务通常有多个AGV在同一路径上不断往复行驶，对发任务类似于两辆AGV互换位置的过程.虽然等待法和重新规划法在大多数情况下都能很好地解决此类路径冲突问题，但是在车间环境下仍然存在一些无法克服的困难.GWM的灵感来源于驾驶员的良好习惯：当两辆汽车在一个狭窄的十字路口相遇时，其中一辆车会先退后到相对宽裕的场地给另外一辆车让行，等到可以通过时再继续行驶.GWM是对这一传统方法的补充，可使路径冲突处理方法更加完善.GWM方法的工作流程如图9所示.

GWM通常使用优先级比较的方法来确定哪辆AGV让路，或者通过比较两辆AGV的让路成本来确定哪辆AGV让路.让路时，GWM根据不同的情况选择合适的自由节点.广义自由节点指所有AGV都不会通过或占用的节点，狭义自由节点指与之冲突的AGV不会通过或占用的节点;选择广义自由节点不会引起连锁反应，选择狭义自由节点则效率会更高.当让路AGV到达自由节点时，冲突AGV沿着初始路径行驶，当冲突AGV到达合适的节点时，让路AGV重新搜索最优路径继续前进.由此，冲突问题得以解决.与传统的等待法和重新规划法相比，GWM方法略显复杂，但可有效解决传统方法无法解决的难题.

图10模拟了GWM处理路径冲突的过程，其中N2分别连接到N1，N3和N4.1#AGV的初始节点是N2，目标节点是N1，理想路径是N2—N1.同时2#AGV的初始节点是N1，目标节点是N4，理想路径是N1—N2—N4.此时，2#AGV占据着1#AGV的目标节点，同时1#AGV阻碍了2#AGV的路径，所以1#AGV采用GWM，先行驶到一个不在2#AGV路径的空闲节点，即N3，然后2#AGV沿着理想路径行驶，当2#AGV到达N4并不再占据N2时，1#AGV再次搜索最佳路径，即N3—N2—N1.

3 OCWG算法设计与实现

GWM理论上可以很好地解决多AGV系统的路径冲突问题，而在实际应用中，其在部分冲突场景的处理效率不如等待法和重新规划法.因此，笔者基于GWM提出了OCWG算法.

该算法融合了等待法、重新规划法和GWM 3种路径处理方法，可以基于不同情形采取相应的方法，从而解决多AGV系统中的路径冲突问题，防止碰撞事故和死锁问题的发生.

OCWG算法包括两个模块，即检测模块和处理模块.检测模块负责检测AGV是否会在安全距离内与其他AGV发生冲突，当检测到冲突时，处理模块负责不同情况的冲突处理工作.基于GWM的OCWG算法可以保证在任何情况下都能很好地处理冲突而不会发生碰撞或死锁.

首先，定义4种AGV的工作模式，即空闲模式（IM）、运行模式（RM）、等待模式（WM）和GWM模式（GM）.IM表示AGV没有任务安排且在节点处停靠;RM表示AGV具有任务目标且在规划路线上正常运行;WM表示AGV具有任务目标但需要在当前节点停靠以等待解决冲突问题;GM表示AGV正在运行到空闲节点以让位给其他AGV.

所有在拓扑地图上运行的AGV 遇到的冲突只有两种情形，即障碍和冲突.

障碍是指在AGV运行的路线上有另一辆AGV停放或运行，分为固定障碍和移动障碍.考虑到安全距离的限制，无论双方处于何种模式，运行AGV必须先停止前进再进行后续处理.固定障碍是指处于IM或WM的障碍AGV停靠在运行AGV的规划路线上，在障碍AGV完成其任务之前，控制系统无权移动该障碍AGV，因此，当前AGV將重新规划路线并避开障碍AGV.移动障碍是指处于RM或GM的障碍AGV行驶在运行AGV的规划路线上，对于处于RM的障碍AGV，运行AGV需要通过对比优先级来判断接下来的处理工作.若运行AGV具有更高的优先级，则切换到WM并等待障碍AGV通过，否则进行让路判断.如果运行AGV在障碍AGV的规划路线上，则采用GWM，否则切换到WM并等待障碍AGV的通过.对于处于GM的障碍AGV，如果运行AGV处于GM模式，则先进行优先级比较，如果运行AGV处于RM，则以优先级低的结果进行后续操作.不同模式的优先级关系为IM>WM>GM>RM.

沖突是指多个AGV的规划路线具有重叠部分，并且可能在未来的时间内发生追及冲突、对向冲突或路口冲突.冲突分为准障碍和未来冲突.准障碍是指冲突AGV的下一个节点在运行AGV的规划路线上，此时运行AGV采用与遇到移动障碍时相同的处理方法.未来冲突是指运行AGV安全距离内的规划路线节点与冲突AGV的规划路线节点有重叠部分，运行AGV需要与冲突AGV进行优先级比较，如果运行AGV的优先级更高，则继续行驶，否则判断是否需要为冲突AGV让路，如果运行AGV正处于冲突AGV的规划路线上，则采用GWM，否则切换到WM并等待冲突AGV的通过.处理模块中的障碍处理流程如图11所示，冲突处理流程如图12所示.

4 实践验证与应用

本文的实践应用平台是SIMATIC WinCC，它是西门子经典的过程监控系统，可以在工业领域提供完整的监控和数据采集功能，并且可以作为上位机控制多AGV系统.

实践应用在河南森源电气股份有限公司的车间进行.实验所用AGV是由河南森源自主研发的双向重载AGV，其控制系统展示的车间地图及控制按钮如图13所示.车间地图是一个不规则的拓扑开环地图，这为基于GWM的OCWG算法提供了充分的测试环境.

在相同任务下，时间窗法和OCWG算法完成任务所需时间的对比结果如图14所示，纵坐标表示所有AGV到达各自目标节点的距离之和，横坐标表示花费的时间.由图14可以看出，时间窗法在任务中使用了等待法，其中一辆AGV处于停车状态，导致任务时间延长.而在OCWG算法执行中，发现途中有总距离不降反升的过程，这一过程就是在执行GWM，系统提前预测到有冲突行为，进行了让路操作.虽然总距离有上升的过程，但OCWG算法为后续的AGV运行提供了更加顺畅的路径，所以OCWG算法的总花费时间比时间窗法少.另外，当任务复杂度逐渐升高时，仅仅依靠等待法的时间窗法显然不能完成任务，而基于GWM的OCWG算法依然可以确保完成任务.

在基于车间实际需求的测试过程中，OCWG算法可以满足包括重复任务和对发任务在内的所有需求，并且从未出现碰撞警告和死锁问题，从而验证了OCWG算法的可行性和稳定性.

5 结语

本文提出了一种新的AGV路径冲突处理方法GWM，与传统的等待法和重新规划法不同，GWM可以解决更为复杂的路径冲突问题，但对部分冲突场景的处理效率不高.在此基础上提出了一种新的路径冲突处理算法OCWG，与合适的路径搜索算法配合，可高效率地解决各种路径规划和路径冲突问题.实际测试验证了OCWG算法的鲁棒性和稳定性.后续将继续深入研究该算法可支持的AGV数量与地图规模的关系，从而进一步优化算法性能.

参考文献：

[1] LE|ANH T，DE KOSTER M B M.A review of design and control of automated guided vehicle systems[J].European Journal of Operational Research，2006，171（1）：1.

[2] 过金超，赵海洋，蒋正轲，等.双向重载智能自主导航车系统设计[J].轻工学报，2017，32（2）：97.

[3] ROODBERGEN K J，VIS I F A.A survey of literature on automated storage and retrieval systems[J].European Journal of Operational research，2009，194（2）：343.

[4] 过金超，刘征，崔光照.基于人工免疫网络理论的移动机器人路径规划[J].郑州轻工业学院学报（自然科学版），2012，27（4）：1.

[5] FANTI M P，MANGINI A M，PEDRONCELLI G，et al.A decentralized control strategy for the coordination of AGV systems[J].Control Engineering Practice，2018，70：86.

[6] SHI Y，WANG X，SUN X，et al.A two|phase strategy with micro genetic algorithm for scheduling Multiple AGVs[C]∥2016 IEEE International Conference on Systems，Man，and Cybernetics （SMC）.Piscataway：IEEE，2016：003101.

[7] 高瑜，过金超，崔光照.一种改进的多机器人路径规划自适应人工势场法[J].郑州轻工业学院学报（自然科学版），2013，28（6）：77.

[8] GHASEMZADEH H，BEHRANGI E，AZGOMI M A.Conflict|free scheduling and routing of automatedguided vehicles in mesh topologies[J].Robotics and Autonomous Systems，2009，57（6/7）：738.

[9] 刘国栋，曲道奎，张雷.多AGV 调度系统中的两阶段动态路径规划[J].机器人，2005，27（3）：210.

[10]SMOLIC|ROCAK N，BOGDAN S，KOVACIC Z，et al.Time windows based dynamic routing in multi|agvsystems[J].IEEE Transactions on AutomationScience and Engineering，2010，7（1）：151.

[11]WADHWA S，DUCQ Y，ALI M，et al.Performance analysis of a flexible manufacturing system[J].Global Journal of Flexible Systems Management，2009，10（3）：23.

[12]MIYAMOTO T，INOUE K.Local and random searches for dispatch and conflict|free routing problem of capacitated AGV systems[J].Computers & Industrial Engineering，2016，91：1.