Please wait a minute...
工程设计学报
Chinese Journal of Engineering Design  2007, Vol. 14 Issue (2): 165-169    DOI:
    
Improved design and its implementation on algorithm of seeking cycle deadlocks in AGVS
SUN  Liang
School of Transportation and Vehicle Engineering, Shandong University of Technology, Zibo 255049, China
Download: HTML     PDF(138KB)
Export: BibTeX | EndNote (RIS)      

Abstract  To solve the problem that domestic AGVS cycle deadlock seeking algorithms’ insufficiency in discovering all kinds of deadlock, an improved algorithm using taskresource (T-R) graph is proposed. The improved algorithm is as follows: firstly, according to relative position change and situation of task execution, AGVS is modeled by R-Tgraph; then, in light of the T-R graph characteristics of cycle deadlock, all kinds of cycle deadlocks are found at any time. Once finishing searching all T-Rgraphs, the algorithm can find all cycle deadlocks in AGVS. Examples’ validation and theoretic analysis both indicate that this algorithm manages to find all deadlocks and solve the shortages of previous algorithms. According to the improved algorithm’s control rules, generation of new deadlocks can be effectively avoided. Moreover, after small revision, this algorithm can find both the cycle deadlocks and the non-cycle ones.

Key words： automatic guided vehicle system      task-resource graph      cycle deadlock     
Published: 28 April 2007
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Cite this article:

SUN Liang. Improved design and its implementation on algorithm of seeking cycle deadlocks in AGVS. Chinese Journal of Engineering Design, 2007, 14(2): 165-169.

URL:

https://www.zjujournals.com/gcsjxb/     OR     https://www.zjujournals.com/gcsjxb/Y2007/V14/I2/165


AGVS循环死锁搜索算法的改进设计及其实现

为了解决国内AGVS在循环死锁搜索算法研究中存在的搜索循环死锁类型不全的问题，利用任务\|资源图(task-resource graph, T-R图)提出一个改进算法。改进算法如下：首先，根据AGV的相对位置变化和执行任务的情况，利用T-R图对AGVS进行建模，然后根据循环死锁的T-R图特征，在每一个状态时刻下，使用图的强连通分支理论搜索循环死锁。当访问完所有状态时刻下的T-R图，也就找到了AGVS中的所有循环死锁。算例验证与理论分析均说明改进算法可以搜索到全部类型的循环死锁，解决了原算法存在的不足。根据改进算法开发的控制规则，可以有效避免新循环死锁的产生。同时指出，对改进算法稍加修改，可以找到AGVS中所有的循环死锁和非循环死锁。

关键词： 自动导引小车系统,  任务-资源图,  循环死锁 
No related articles found!