基于任务-资源图的AGVS循环死锁搜索算法的改进研究

Improved Research on Algorithm of Finding out All Kinds of Cycle Deadlocks in AGVS Using Task-resource Graph

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

Aiming to solve the problem of low efficiency and inability of finding out all kinds of deadlock ,an improved algorithm is proposed using graph theory. The method is as follows：firstly,according to the diffirent positions and tasks of AGV in AGVS,AGVS was modelled using T-R graph, secondly,the algorithm search out all kinds of cycle deadlock using graph theory in T-R graph at any time. Once having finished searching all T-R graphs, the algorithm can find all cycle deadlocks in AGVS. The improved algorithm can overcome the disadvantage of the previous ：inability of finding out all kinds of deadlocks. The use of control law,which are delevoped by the improved algorithm,can help to avoid new cycle deadlocks effectively. Simulating results coincide with theoretical analyse. Meanwhile,all types of cycle deadlocks and non-cycle ones can be found in AGVS with the simple correction of the improved algorithm.