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

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) 的方法，从而侧重于Ｘ才碰撞和死锁的预防入手，减少 AGV的碰撞和死锁，对于实时的情况却显得有些不足；贺丽娜 [6] 提出将时间窗原理和Dijkstra算法结合的方法来解决多AGV碰撞问题，但是该方法未证明在数量较多的情况下的有效性；乔岩等人 [7] 提出了一种基于改进时间窗的AGV避碰方法，该方法虽在一定程度上解决了实时性问题，但是只能应用于双向导引路径；刘国栋等人 [8] 针对多 AGV交通故障问题提出了一种两阶段动态路径规划策略，但是路径复杂度的增大也会带来实时性的问题；王佳溶等人 [9] 提出了一种改进后的两阶段控制策略，但是策略只考虑速度调节没有考虑优先级问题，具有一定的局限性。因此需要一种不仅可以避免碰撞，而且实时性好，适用于AGV数量较多的情况的方法。

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