[译]AGV系统区域控制死锁预测与避免

讨论了区域控制单向自动导引车系统(AGVS)的死锁问题。定义了一个有向图来对车流进行建模,识别不同的车流,方便地表示状态和捕捉区域控制AGV系统的并发行为。本研究的目的是提出一种动态的方法来实现对一类AGV系统的实时预测,避免因共用导向区而造成的死锁,从而提高资源利用率和总吞吐量。所提出的算法程序,根据所获得的模型所产生的状态,可以作为区域控制AGV系统运行的功能模块,而不需要对原有的车辆控制系统进行大范围的修改。

M.-S. Yeh &W.-C. Yeh

1. 介绍

自动导向车辆系统(AGVS)是一种先进的物料搬运设备或输送系统,适用于连接各种制造设备或单元。AGVS至少包含一辆无人驾驶的自动引导车,并由非车载计算机或微处理器控制。AGV系统中的每辆车都在预先确定的引导路径上行驶;其路线可根据运输需要任意改变。因此,AGV系统比其他传统的物料搬运系统具有更大的灵活性和处理能力,特别是对于柔性制造系统(FMS)。然而,AGV系统可能会出现阻塞、冲突、死锁、碰撞等车辆管理问题。这些问题在AGV系统的运行和建设中必须认真考虑(Koff 1987,Malmberg 1990,Kim and Tanchoco 1991,Zeng et al.1991)。

具体来说,死锁是AGVS中车辆管理的一个重要问题。死锁是由系统中不同的车流争夺或共享有限的资源(如路径和缓冲区)而引起的。当AGVS发生死锁时,物料流和车流会被阻塞,工作停滞,直到执行恢复程序,导致吞吐量低,失去控制,整个系统关闭。因此,死锁预测和避免成为AGVS运行和设计的一个重要问题。

区域控制是AGVS车辆管理中应用最广泛的技术。在区域控制AGVS中,导向路径被分割成几个不相交的区域。尽管现在有许多控制形式在使用,一般的规则是一辆车可以占据一个特定的区域在同一时间。如果一辆车接近一个被占领的区域,它将停留在当前的区域,直到下一个区域未被占领。

区域控制AGV中只有Lee和Lin(1995)提出的两种死锁。这些都是从共享资源的角度来讨论的,即引导路径区域和缓冲区。如果死锁是由有限的缓冲区引起的,那么可以通过添加中央缓冲区和(或)预先检测缓冲区是否已满来消除死锁。但是,如果由于共享同一个导轨区域而导致死锁,则很难提前预测和避免死锁,因为车辆路径不是预先确定的。

解决AGVS中目前使用的这些死锁问题的一个简单方法是,当车辆已经调度并且其路线已经确定时,提前保留所有要行驶的引导路径(guide paths)。这种方法通常易于实现,但会导致较低的引导路径利用率。因此,它降低了物流的总吞吐量。

我们研究了一类区域控制AGV与单向引导路径共享引导路径所引起的死锁问题。提出了一种基于所得到的有向图模型的算法,该算法提供了预测和避免死锁的规则。分析了该算法的复杂度。最后通过一个算例说明了该算法的有效性。

2. 以前的工作

死锁问题已经从不同的角度进行了研究。人们提出了多种死锁解决方法,可分为三类:死锁预防、死锁避免和死锁检测/恢复。死锁预防包括预先定义一些规则来防止死锁。死锁避免动态地检查系统状态,并仔细地实时绕过死锁。死锁预测是避免死锁的一个初步步骤,可以预先确定死锁的位置。当死锁发生并被检测到时,死锁检测/恢复使系统恢复到正常状态。一般来说,动态路由系统需要一种算法来实时预测和避免死锁。与预防和检测/恢复相比,避免使资源更好的利用(Leung和Sheen 1993)。

第一个遇到死锁的领域是计算机系统中的数据处理。后来面临同样死锁问题的其他系统还有数据库、通信、自动化制造系统等(Murata et al.1989,Tsutsui and Fujimoto 1987,Sifakis 1980,Habermann 1969)。

一些作者已经注意到在自动化制造系统的设计和操作中的死锁问题。Banaszak和Krogh(1990)首先采用Petri网(PNs)(Peterson 1981)在FMS中,通过限制给定标记的触发集合来导出限制策略,以防止死锁。为了避免环路(circuits)中的延迟,他们使用了基于说明策略的在线死锁预防算法。

Viswanadham等人(1990)也采用PN模型来防止和避免FMS中的死锁。他们是第一个使用给定FMS的PN模型可达图来预先防止死锁的人。由于该方法对资源的利用率较低,且仅适用于小型系统,因此采用基于PN模型的前瞻方法,实现了FMS的在线设计,以避免死锁。

Wysk等人(1991)提出了一种基于有向图的柔性制造单元死锁检测算法。Viswanadham和Narahari(1992)还介绍并分析了PNs在自动化制造系统中用于解决死锁问题的方法。

Leung和Sheen(1993)也提出了两种用于检测和避免FMC中死锁的算法。他们通过仿真比较了两种算法,说明了规避算法比预测算法具有更好的性能。Lee和Lin(1995)定义并使用了一个扩展的pn类,即有属性的pn,来提供预测和避免死锁的规则。

3. AGVS的有向图模型

The directed graph model for the AGVS

有向图是图论和网络流中一个非常基本的概念。由于其简单易用,本文采用了一种特殊的有向图来表示区域控制AGV。在我们改进的有向图模型中,一个圆表示AGVS中的每个区域,一个有向弧表示每个导轨。如果入射到一个节点的有向弧的数目不少于2,则这样的节点称为关节(join node)节点,并用点圆表示。例如,节点2、3和7是图1中的关节节点,如果弧arc(i, j)在有向图中,j是关节节点,则节点i被定义为关节节点j的关键节点,arc(i, j)被称为关键弧,并用点有向弧表示。例如,节点3和5是关节节点2的关键节点,arc(3, 2)和arc(5, 2)是图1中的关键弧。黑色圆圈表示车辆占用了这样的节点(区域)。

图1. 样本区域控制AGV的有向图,每个圆、点圆、暗圆、有向弧、有向点弧分别表示一个区域、关节节点(区域)、AGV占用的区域、引导路径和关键弧。
图2. 取样区控制AGV,其中→ 表示AGVS引导路径,—— 仅表示区域边界,并且 ☐▷ 表示AGV。

上述改进的有向图不仅易于定义,便于区域控制AGV的构建,而且对实现AGV的交通状况,如车辆的位置、死锁预测等也有很大的帮助,等等。考虑图2所示的例子。这个示例问题有六个工作站(用符号WS表示),其中有负载转移站,导轨上有十个区域。为简单起见,假设在每个工作站的同一位置进行取送负荷转移操作。

对应的有向图模型(图1)表示区域及其连接方式,很容易从图2中导出。在我们的有向图模型中,节点用于表示区域,而虚线节点表示联合节点,深色节点表示区域正被车辆占用。有向弧用于表示导轨的方向,并显示两个相邻区域是如何连接的。虚线弧由键弧表示。

下面的引理讨论了节点的度(内度和外度)的性质以及度与有向圆的关系。

  • 引理1:每个节点至少属于一个有向圆。
  • 引理2:每个节点的内度和外度都至少等于1。
  • 引理3:如果一个节点的度大于2,那么至少有两个有向圆包含这个节点。

4. 死锁的必要条件

识别区域控制单向AGVS可能发生死锁的条件是必要的。Coffman等人(1971年)指出,当且仅当系统中同时存在以下四个必要条件时,才会出现死锁:
(1) 互斥:一个资源一次只被一个进程占用;
(2) 无抢占:当一个资源被使用时,直到使用它的进程完成它,它才被释放;
(3) 保持并等待:一个进程至少持有一个资源,并等待获取当前被其他进程占用的额外资源;
(4) 循环等待:一个封闭的进程链,其中每个进程都在等待链中下一个进程占用的资源。

如果不满足任何条件,则不会发生死锁。因此,我们打算打破一个条件,以消除死锁在区域控制AGVS。本文讨论的区域控制AGV中的资源是引导路径区域,过程是车流。互斥通常不能避免,因为一个区域不能同时被两辆或两辆以上的车辆使用。不能发生抢占,因为车辆只有在前一辆车释放后才能进入区域。保持和等待也是系统存在的,因为每当下一个区域繁忙时,每辆车都会被阻塞在一个区域中。因此,这三个条件在区域控制AGVS中是永久满足的。只有第四个条件(循环等待)决定是否发生死锁(Coffman等人,1972年,Lee和Lin,1995年)。因此,如果我们能够预测循环等待的发生,则预测的死锁就可以避免。因此,我们试图推导一种避免循环等待的算法。

总之,死锁仅发生在形成循环等待的引导路径区域之间。因此,车辆数量必须等于或超过具有最小区域的环路。否则,AGVS很容易被证明是一个无死锁的系统,因为不会形成循环等待。也就是说,如果AGVS是无死锁的,则不需要预测和消除死锁。如果不是这样,则需要一个死锁避免算法。

下面的定理是我们的死锁避免算法的关键。它们来自于上述引理和死锁的必要条件。
定理1:任何AGV进入任何可用的非关节节点(none-join node)都不会形成死锁。
定理2:任何AGV进入任何可用的关节节点都不会形成死锁,但前提是任意有向圆包含了此节点且该有向圆至少有另一个可用的节点。
定理3:发生死锁的必要条件是AGV进入任何可用的关节节点。

5. 死锁预测与避免算法

如第4节所述,只有循环等待条件才能确定是否发生死锁。因此,如果可以在有向图中提前找到可能发生死锁的环路(circuit),则可以避免预测的死锁。然而,检查所有这些环路是一个P-hard问题,并且很难确定哪些环路可能存在死锁。因此,该算法利用标签来表示系统的当前状态和未来的预测状态,以避免死锁。我们对算法的详细思想描述如下。

如果任何节点的标签为零,则该节点未被任何车辆占用;否则,车辆将占用它。如果两个相邻节点具有相同的非零标签,则这两个相邻节点的第二个节点中的某辆车的下一个位置是第一个节点,第一个节点中的某辆车的最后一个位置是第二个节点。例如,假设Ni,Nj是具有非零标签的两个相邻节点,并且假设有一条弧从Ni指向Nj;然后,节点Nj中车辆的下一个位置是节点Ni,节点Ni中车辆的最后一个位置是节点Nj。如果任何环路中所有节点的标签都不为零且相等,则发生环路等待。因此,我们需要实时预测并避免这种情况。

很明显,每个关节节点都属于两个或多个环路的交点。因此,在车辆进入连接节点之前,应确定不会形成环路等待。这是我们的死锁避免算法的关键点。

当一辆车从某个关键节点转移到下一个节点(即关节节点)时,必须保证一系列具有相同标签的相邻车辆不能占用一条线路;如果是,则会发生死锁。因此,每个包含该节点的环路中相同标签车辆的数量必须小于环路的长度,以避免死锁。

将AGVS中心控制器提供的车辆路径作为算法的输入数据。整个算法旨在预测死锁发生的位置,防止车辆形成循环等待,并在系统状态更新时处理被阻塞的车辆。当车辆从当前区域行驶到下一个区域时,算法只做出两个行驶决策:一个是在当前区域等待,另一个是移动到下一个区域。如果预测某辆车未来的路径没有死锁,且该车的下一个节点没有被另一辆车占用,则通知该车移动到下一个节点。但是,如果车辆进入下一个节点会导致死锁,那么该车辆必须在当前节点中等待,并附加到集合中,而不管它的下一个节点是否被阻塞。

在介绍所提出算法的详细步骤之前,定义了该过程中使用的一些符号:

  • N : 以区域控制AGVS为模型的有向图中节点总数;
  • Ni : 第i个节点;
  • V : 区域控制AGVS中车辆总数;
  • Vi : 第i个车辆;
  • pos(Vi) : 车辆Vi当前位置(节点);
  • next (Vi) : 车辆Vi在其自身路线上的下一个位置(节点);
  • last (Vi) : 车辆Vi在自身路线上的最后位置(节点);
  • waiting_set(Ni) : 包含等待节点Ni的阻塞车辆的集合;
  • time_start_to_wait(Vi) : 车辆Vi某节点开始等待的时间;
  • Key_set : 所有关键节点的集合;
  • label(Ni) : 表示节点Ni是否被车辆占用的标签;
  • earliest(waiting_set(next(Vi))) : 在waiting_set(next(Vi))中等待的最早的车辆;

根据车辆是否在关键节点和/或被阻塞,有四种可能的结果。

(1) 如果任何车辆(如Vi)被堵塞,即其label(next(Vi))!=0,然后它在当前位置等待。若其pos(Vi)!∈waiting_set(next(Vi))时,则它被附加到waiting_set(next(Vi))。

(2) 如果任何车辆(例如Vi)未被阻塞,但当前不是最早在其路由的下一位置等待节点的车辆之一,即label(next(Vi))=0且time_start_to_wait(Vi)<earliest(waiting_set(next(Vi)),则它在当前位置等待。若其pos(Vi)!∈waiting_set(next(Vi))时,则它被附加到waiting_set(next(Vi))。

(3) 假设车辆Vi未被阻塞且不在关键节点中,即label(next(Vi))=0且pos(Vi)!∈key_set。如果Vi是当前其路线的下一个位置等待节点的最早车辆之一,即earliest(waiting_set(next(Vi))=time_start_to_wait(Vi),则Vi被移动到其下一个节点。否则,Vi在其当前位置等待,并且当pos(Vi)!∈waiting_set(next(Vi))时,Vi被添加到waiting_set(next(Vi))。

(4)假设车辆Vi的label (next(Vi))=0,pos(Vi)∈key_set且time_start_to_wait(Vi)=earliest(waiting_set(next(Vi)))。如果Vi移动到它的下一个节点,它将形成一个环路,使得该环路中的所有节点都被相同的标签车辆占用,然后它在当前位置等待,并且若其pos(Vi)!∈waiting_set(next(Vi))时,则被附加到 waiting_set(next(Vi))。否则,车辆Vi进入下一位置后不会形成死锁。

死锁避免算法是通过考虑上述四种可能的结果来实现的,如图3所示。

Algorithm Deadlock-Prediction_and_Avoidance
BEGIN
    Initial();
    REPEAT
    FOR i←1 TO V DO
        IF label (next(Vi)) = 0 .AND. time_start_to_wait(Vi) = earliest(waiting_set(next (Vi))) THEN
            IF pos(Vi)key_set THEN Deadlock_Test(Vi)
            ELSE Move_to_next_node (Vi);
        ELSE Put_in_Waiting_Set_Test(Vi);
        END FOR
    UNTIL all vehicles reach their final destination;
END

PROCEDURE Deadlock_Test(Vi)
BEGIN
    IF label (next(next(Vi))) = label (pos(Vj)) .AND. next (Vi) = next (Vj), where VjVi, THEN
        Put_in_Waiting_Set_Test(Vi);
    ELSE	 
        Move_to_next_node (Vi);
    END IF
END


PROCEDURE Initial ()
BEGIN
    FOR i←1 TO N DO
        label (Ni) ←0;
        waiting_set(Ni) ←Ø;
    END FOR
    v←Ø;
    FOR i←1 TO V DO
        time_start_to_wait(Vi) ←0;
        v←v∪{i};
        IF label (next(Vi))= 0 THEN
            label (pos(Vi)) ←i;
            j ←last (pos(Vi));
            WHILE label ( j)= 0 .AND. there is a vehicle in node Nj 
                label ( j) ←i;
                Find the last position of the vehicle in node Nj and let j be this position. 
            END WHILE
        END IF
    END FOR
END

图3. 死锁预测算法。

该算法的主要复杂性来源于死锁的发生和验证每辆车的路径。V表示AGV中的车辆数量;然后,上述算法确定每个AGV的下一步(行驶还是等待)的复杂度为O(V),这比Lee和Lin(1995)提出的最著名的算法复杂度为O(NE平方)要好,其中E是总边,N是区域数。每当车辆打算从当前区域行驶到下一个区域时,就会调用该算法来执行。用伪码描述了该算法。所以,我们提出的算法很容易翻译成特定的编程语言。可以快速添加输入/输出和错误处理程序等作为材料以适应每个特定情况(的程序)。

6. 一个数值的例子

在图1所示的有向图中,所提出的算法用于说明如何实时预测和避免死锁。让Va、Vb、Vc和Vd的路由为Va:3→2.→1.→3,Vb:7→5.→2.→1.→3.→2.→4.→7,Vc:8→6.→3.→2.→4.→7.→8和Vd:10→7.→8.→9→分别是10个。如前所述,节点2、3和7是关节节点。预测了从开始到第一个死锁的详细步骤,并根据所提出的算法描述了避免过程。

  • 步骤0. 最初的步骤:
    • 设置任意关节节点的等待集为空,任意车辆的等待时间为零,任意节点的标签为零,joint_set={2,3,7}和v={1,2,3,4}。
    • 让Va、Vb、Vc和Vd的标签分别为1、2、3和2。设L={4}。
  • 步骤1. 第一次迭代:
    • 让Va:3→2(由于车辆Va进入节点2后不会形成死锁),vlabel(Va)=4,L={1}。
    • 让Vb:7→5,Vc:8→6和Vd:9→10(因为没有车辆分别进入和等待节点3、节点5和节点10)。
  • 步骤2. 第二次迭代:
    • 让Va:2→1,由于节点1 !∈ joint_set,label (next(Va)=1)=0,time_start_to_wait(Va) = earliest(waiting_set(next(Va)))。
      设label(1)为4(即v={4}中的最小数),v=v ∪{1}-{4},当Va在节点2中时,Va的当前位置(即pos(Va)=2)的下一个位置(即next(pos(Va))=3)为empty(label(next(pos(Va))=0),Va的最后一个位置被Vb占用(即 label(last(pos(Va))!=0)。
    • 让Vb:5→2,因为标label(2)=0,所以时间time_start_to_wait(Vb) = earliest(waiting_set(next(Vb)))且节点5 !∈ key_set。
      设label(2)为4,因为Vb的当前位置(节点2)的下一个位置(节点1)被Va占用(即 label(1)=0 )。
    • 尽管Vc的当前位置(节点6)的下一个位置(节点3)为空,但让Vc停留在具有相同标签3的键节点6中。否则,Vc进入节点3将导致label(3)为4,从而形成由相同标签车辆占用环路的情况,即发生死锁。
    • Vd:7→8,因为label(8)=0,time_start_to_wait(Vd) = earliest(waiting_set(next(Vd))),而且节点7 !∈ key_set。
      假设label(8)仍然是2,因为label(next(next(pos(Vd)))= 9)=label(last(pos(Vd))= 10)= 0,此时Vd在节点7中。

连续的步骤类似于上面的演示。在本例中,前八次迭代的算法执行步骤总结在表1中。为了便于识别,如果车辆的当前位置属于某个关键节点,则在表1中的节点号下划下划线,并将每个车辆的新位置的标签放在括号中。

表1. 该示例使用算法避免死锁的步骤。

7. 结论

提出了一种区域控制单向AGV中实时预测和避免死锁的算法。定义了一个有向图来表示区域控制AGV的当前状态和生成未来状态。采用模块化方法建立区域控制AGV的有向图模型。此外,模块化的模型构造使得模型能够被系统地构造并提供通用的案例。

提出了一种基于有向图的AGVS死锁预测和避免算法。每当车辆试图从当前区域行驶到下一个区域时,就会调用该算法。在该算法中,策略是预测可能导致死锁的环路。每个调度的车辆根据其给定的路线向前看将要行驶的所有未来区域,以验证这些区域中是否存在环路等待。

AGVS的中央控制器提供车辆调度和每辆车的路线。然后,利用该算法预测和避免导程区域间的死锁。所提出的算法程序可作为区域控制AGV的功能模块,并可方便地在单向区域控制AGV中实现。

鸣谢

  • BANASZAK, Z. A. and KROGH, B. H., 1990, Deadlock avoidance in ¯ exible manufacturing systems with concurrently competing process ¯ ows. IEEE Transactions on Robotics and Automation, 6, 724-734.
  • COFFMAN,E. G.,ELPHICK,M. J. and SHOSHANI, A., 1971, System deadlocks. ACMComputing Surveys., 3, 67-78.
  • HABERMANN, A. N., 1969, Prevention of system deadlocks. Communications of the ACM, 12, 373-385.
  • KIM, C. W. and TANCHOCO, J. M. A., 1991, Con¯ ict-free shortest-time bi-directional AGV routing. International Journal of Production Research, 29, 2377±2391.
  • KOFF, G, A., 1987, Automatic guided vehicle systems: application, control, and planning. Material Flows, 4, 3-16.
  • LEUNG, Y. T, and SHEEN, G. J., 1993, Resolving deadlocks in ¯ exible manufacturing cells. Journal of Manufacturing Systems, 12, 291-304.
  • LEE, C.-C. and LIN, J. T., 1995, Deadlock prediction and avoidance based on Petri nets for zone-control automated guided vehicle systems. International Journal of Production Research, 33, 3249-3265.
  • LIN, J. T. and LEE, C. C., 1992, A modular approach for the modeling of a class of zone- control conveyor system using timed Petri nets. International Journal of Computer Integrated Manufacturing, 5, 277-289.
  • MALMBORG, C. J., 1990, A model for the design of zone-control automated guided vehicle systems, International Journal of Production Research, 28, 1741-1758.
  • MURATA, T., 1989, Petri nets: properties, analysis, and application. Proceedings of the IEEE, 77, 541-579.
  • MURATA, T., SHENKER, B. and SHA TZ, S. M., 1989, Detection of a static deadlock using Petri net invariants. IEEE Transactions on Software Engineering, 15, 314-326.
  • PETERSON, J. L., 1981, Petri Net Theory and the Modeling of Systems (Englewood Cli€ s, NJ:Prentice-Hall). *SIFAKIS, J., 1980, Deadlocks and livelocks in transition systems. In P. Dembinski (ed.) Mathematical Foundations of Computer Science, Lecture Notes in Computer Science: Vol. 88, pp. 587-600.
  • TSUTSUI, S. and FUJIMOTO, Y., 1987, Deadlock prevention in process computer systems. The Computer Journal, 30, 20-26.
  • VISWANADHAM, N. and NARAHARI, Y., 1992, Performance Modeling of Automated Manufacturing Systems, (Englewood Cli€ s, NJ: Prentice-Hall) Chapter 5.
  • VISWANADHAM, N., NARAHARI, Y. and JOHNSON, T. L., 1990, Deadlock prevention and deadlock avoidance in flexible manufacturing systems using Petri net models. IEEE Transactions on Robotics and Automation, 6, 713-723.
  • WYSK, R. A., YANG, N. S. and JOSHI, S., 1991, Detection of deadlocks in flexible manufacturing cells. IEEE Transactions on Robotics and Automation, 7, 853-859.
  • ZENG, L., WANG, H.-P. and JIN, S., 1991, Con¯ ict detection of automated guided vehicles: a Petri net approach. International Journal of Production Research, 29, 865-879.

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

18 − 10 =