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

  • 多AGV动态交通调度算法设计已关闭评论
  • 357 views
  • A+
所属分类:AGV设计资料
摘要

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

 

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

2 调度算法设计

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

图 1 静态环境拓扑地图模型

2.1 离线规划  

 

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

  

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

  

(1)地图为有向图,AGV在地图中可双向运动

抱歉,此资源仅限赞助会员下载,请先
注意:本站资源多为网络收集,如涉及版权问题请及时与站长联系QQ:2766242327,我们会在第一时间内与您协商解决。如非特殊说明,本站所有资源解压密码均为:agvba.com。
weinxin
微信公众号
agvba是一个分享AGV知识和agv案例视频的网站。