多AGV动态交通调度算法设计

    高新浩 陈晓华 王占山

    摘 要：本文针对多AGV系统的动态交通调度过程中容易出现的路径规划冲突和死锁问题，设计基于时间窗的改进两阶段动态交通调度算法，搭建多AGV动态交通调度系统。实现多AGV的最优动态交通调度，利用改进后的动态交通调度算法可降低路径冲突和死锁出现频率30%以上，提高多AGV系统的运行效率。

    关键词：多AGV；动态调度；路径规划

    DOI：10.16640/j.cnki.37-1222/t.2019.09.127

    1 引言

    多AGV动态调度常常需要面对多任务分配、多路径冲突问题及突发故障状况的解决，要求调度算法的求解速度快、效率高，并能够满足实际生产过程中实时变化的多任务调度。常用地调度原则主要有：规划路径最短原则、等待时间最短原则、AGV工作队列最优原则等单一指标调度原则，此外，还有基于多种调度指标的复合指标调度原则。

    如何规划出一条从起点到终点间畅通的最短路径，避免规划的路径出现阻塞、冲突或死锁现象，保证规划的路径为全局最优的结果，实现最优的系统运行效果是国内外众多学者长期以来研究的热点和难点。自Maxwell等[1]最早提出AGV的路径规划问题开始，国内外众多学者针对多AGV动态调度问题进行了长期的深入研究。早期Kazuo等[2]基于遗传算法进行了路径规划问题的分析。徐胜华等人[3] 针对扫地机器人的路径规划问题提出了一种改进算法；Kim等人[4]采用conservative myopic策略来寻求无冲突的路径， 但是该方法效率低、易发生阻塞、不适应AGV较多的环境；Fanti [5]给出了一个将赋时着色Petri网（Coloured Timed Petri Net，CTPN）转化为强连通Petri网（Petri Net，PN） 的方法，从而侧重于X才碰撞和死锁的预防入手，减少AGV的碰撞和死锁，对于实时的情况却显得有些不足；贺丽娜[6]提出将时间窗原理和Dijkstra算法结合的方法来解决多AGV碰撞问题， 但是该方法未证明在数量较多的情况下的有效性；乔岩等人[7]提出了一种基于改进时间窗的AGV避碰方法，该方法虽在一定程度上解决了实时性问题，但是只能应用于双向导引路径；刘国栋等人[8]针对多AGV交通故障问题提出了一种两阶段动态路径规划策略，但是路径复杂度的增大也会带来实时性的问题；王佳溶等人[9]提出了一种改进后的两阶段控制策略，但是策略只考虑速度调节没有考虑优先级问题，具有一定的局限性。因此需要一种不仅可以避免碰撞，而且实时性好，适用于AGV数量较多的情况的方法。

    本文针对动态交通规划中的阻塞和死锁现象，提出一种改进的基于时间窗的两阶段动态路径规划方法。该方法通过将时间窗原理和A*算法相结合，第一阶段构建基于时间窗的静态环境拓扑地图，根据任务队列中各任务的优先级开展离线规划，并对各AGV规划路径进行冲突检验，对冲突的任务的优先级进行实时改变；第二阶段构建路径实时反馈系统，将AGV实时运行情况与环境拓扑地图相结合，采用BP神经网络算法[10-12]构建动态环境拓扑地图，实现对多AGV的动态路径规划。

    2 调度算法设计

    2.1 离线规划

    为更好对调度规划算法进行说明，基于图论构建如图1所示静态环境拓扑地图模型。

    对该拓扑地图做如下定义：

    （1）地图为有向图，AGV在地图中可双向运动；

    （2）表示地图中路径间节点集合，定义；

    （3）表示地图中连接节点的边的集合，定义L，则有：

    （4）地图中每条边的长度权值相同，均为2；

    （5）地图中设定3个仓储点2、3、4作为初始节点；

    （6）地图中设定3个工位点19、21和23作为目标点。

    为减少AGV本身因素对规划调度算法影响，做以下假定：

    （1）设定AGV本身长度为1，边的长度大于AGV本身长度，AGV通行每条边的时间为2；

    （2）AGV以恒定速度在地图中运行，不考虑AGV转弯的速度变化；

    （3）每条边在同一时间段内仅允许一辆AGV进入。

    在离线规划调度算法设计中，首先对AGV分配的任务根据各自优先级高低进行排序并构建任务队列；基于时间窗原理，采用启发式A*算法对任务队列中的AGV路径顺序开展静态最优路径搜索。以图1中仓储点2和4为初始节点，按照启发函数对周围节点进行搜索，并选取其中最优的一个节点进行扩展，经过迭代计算搜索获取目标点，最后由目标点回溯到起始节点形成全局的规划轨迹。A*算法估计函数如公式（1）所示：

    （1）

    其中，表示估计函数，是AGV从起始点到目标点的评价估计值；为代价函数，表示初始點到当前节点的实际估计值；h为启发函数，表示当前节点到目标点的估计代价值。在搜索节点较少的情况下，h包含启发信息越多，寻找全局最优路径的效果越好。与传统A*算法的8邻域或16邻域搜索不同，由于环境拓扑地图限定了AGV的运动路径方向为4个，因此在算法设计中向上下左右四个方向邻域进行路径搜索，同时启发函数采用曼哈顿距离进行计算，启发函数如公式（2）所示：

    （2）

    其中，表示相邻节点之间路径的代价权值，表示当前节点，表示目标点。

    基于启发A*算法，设计离线规划算法如图2所示。首先根据离线拓扑地图和任务队列中任务内容，利用A*算法进行相关任务的路径规划，然后结合时间窗原理，对规划路径进行时间段划分，根据各规划路径的优先级进行占用时间分配统计，生成基于时间窗的任务执行队列。

    2.2 在线规划

    AGV在线动态调度规划的主要目标和分为两个目标：一是根据时间窗原理防止AGV之间出现路径冲突和死锁，二是调度路径尽可能短。在完成离线规划后，每个AGV规划路径中的相关节点序列被保存在任务执行队列中。在AGV运动过程中，通过对AGV在环境拓扑地图中的位置及状态进行在线监测，并采用BP神经网络描述运行环境基于时间窗的位置约束，构建AGV运动路径的目标能量函数和路径长度能量函数，通过迭代计算能量函数对AGV的在线调度路径进行最优化处理，最终使调度路径的迭代趋向于最优规划路径。在线规划算法设计中选取双隐层神经网络以获取更好的迭代逼近和泛化能力。

    AGV在线路径规划总能量函数如式（3）所示：

    （3）

    其中，表示目标冲突能量函数，目标能量函数越小表示出现路径冲突和死锁的概率越小；表示路径长度能量函数，路径长度能量函数越小，路径长度越小；和分别为和的加权。通过每一次迭代极值点，利用总能量函数为动态规划路径寻找最优值，即可在避免路径冲突和死锁的同时引导AGV选择最优路径，最终完成路径规划任务。

    为获取函数值，设计双隐层神经网络结构如图3所示：

    激发函数采用阶跃函数可检测AGV运动路径在到时间窗内是否与其他调度路径存在冲突或死锁，采用Sigmoid函数作为激发函数，即：

    （4）

    則通过双隐层神经网络输出值为0～1内的连续变化值，该值反应该时间窗内该路径段出现冲突或死锁的概率程度，输出数值越大则说明出现冲突或死锁的概率越大。将目标冲突能量函数定义为所有路径的冲突概率之和。

    （5）

    路径长度能量函数定义为起始点到当前节点路径长度值与当前节点到目标点估计值之和。

    （6）

    式中，表示起始点与当前节点路径长度值，表示当前节点到目标点估计值。

    3 实验验证

    采用C++设计开发AGV交通调度系统开展多AGV动态交通调度仿真研究，交通调度系统设计架构如图4所示。

    设定3辆AGV分别从仓储点1（节点1）、仓储点2（节点2）和仓储点3（节点3）出发，分别到达工位3（节点23）、工位1（节点19）和工位2（节点21），在离线规划阶段，利用A*算法结合静态环境拓扑地图获取三辆AGV路径节点集合分别为{1，6，15，14，13，12，23}，{7，6，15，16，19}，{8，13，22，21}。各节点通行顺序如图5所示。

    在AGV运动过程中，在AGV1离开仓储1（节点1）后，增加AGV4从仓储1（节点1）出发到工位2（节点21）的任务到任务队列，节点6在AGV4出发第一段路径将与AGV2的第二段路径发生冲突，此时采用基于BP神经网络的在线调度算法进行路径的重新规划优化，优化后的节点通行顺序如图6所示。

    为更贴合实际生产调度状况，在测试时随机添加出发节点与目标点不同的路径规划任务，针对现有的基于时间窗的路径规划算法与本文所改进的算法进行实际运行时间对比，测试结果如表1所示。

    通过实验数据对比，随着AGV并发数数量的增长，在冲突出现次数、路径运行时间和规划路径长度三项数据上比较，改进后的两阶段路径规划算法在各项数据指标上都有较为明显的提高。

    4 结论

    针对多AGV动态交通调度中出现的冲突和死锁问题，提出了一种改进的基于时间窗的两阶段动态路径规划算法。该算法通过构建离线环境拓扑地图，结合A*算法实现离线路径规划，在AGV任务执行过程构建动态信息反馈机制，利用动态环境拓扑地图，通过BP神经网络实现动态路径调度规划，减少冲突和死锁问题的发生。改变发生故障的AGV在节点的优先级减少AGV的冲突死锁，经仿真实验验证，该算法实时性好，可有效解决冲突和死锁问题，但是随着AGV任务队列的增大，该算法存在计算延迟现象，针对该算法的实时性问题，有待进一步研究改进。

    参考文献：

    [1]Maxwell W L，Tanehoco J M A.Design and automatic guieded vehiele system[J].IEEE Tranctions，1982（14）：113-124.

    [2]Kazuo S，John S.Genetic algorithms for adaptive motion planning of all autonomous mobile Robert[J].Problems IEEE transaction SMC，1997（18）：46-49.

    [3]徐胜华，宋树祥，佘果.一种扫地机器人路径规划的改进算法[J].测控技术，2017，36（02）：120-123.

    [4]Kim C W，Tanchoco J M A.Operational control of a bidirectional automated vehicle systems[J].Interational Jouanal of Production Research，1993，31（09）：2123-2138.

    [5]Fanti M P.A deadlock avoidance strategy for AGV system modeled coloured Petri nets[C].Proceedings of the 6th International Workshop on Discrete Event Systems，2002.

    [6]何丽娜.AGV系统运行路径优化技术研究[D].南京：南京航空航天大学，2011.

    [7]乔岩，钱晓明，楼佩煌.基于改进时间窗的AGVs避碰路径规划[J].计算机集成制造系统，2012，18（12）：2683-2688.

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

    [9]王佳溶，楼佩煌，王晓勇.基于改进的两阶段控制策略的AGV路径优化调度研究[J]. 机械科学与技术，2008，27（09）：1211-1216.

    [10]王薇，魏世民，杨月巧，姜运芳，李端玲.基于神经网络的移动机器人路径规划[J].北京工业大学学报，2010，36（09）：1287-1291.

    [11]Path Planning of MultiAgent Systems in Unknown Environmentwith Neural Kernel Smoothing and Reinforcement Learning.David luviano cruz，Wen-Yu.Neurocomputing，2016.

    [12]项宏峰，曹少中，徐长波，李新佩.基于神经网络的AGV智能车路径规划的仿真研究[J].北京印刷学院学报，2017，25（07）：128-130.

    苏州市科技项目（编号：SYG201654）

    作者简介：高新浩（1985-），男，河北石家庄人，博士，讲师，主要从事机电控制方面研究。