AVS/RS系統(tǒng)沖突與死鎖控制策略

方彥軍，唐 猛

（武漢大學 自動化系，武漢 430072）

在自動小車存取系統(tǒng)AVS/RS的調度中，包括動態(tài)和靜態(tài)2種。靜態(tài)調度側重于路徑的空間維度（確定路徑的空間域），動態(tài)調度則同時考慮路徑在時間與空間上的可行性[1]。

關于軌道引導小車RGVs的沖突及死鎖問題，文獻[2]通過自主車輛管理系統(tǒng)將小車作業(yè)空間進行分區(qū)來解決系統(tǒng)的死鎖問題，稱為區(qū)域控制。文獻[3]建立了2種自動引導小車AGVs的Petri網模型。文獻[4]在無人搬運車系統(tǒng)中運用Petri網將底層控制邏輯與上層規(guī)劃進行分離。文獻[5]運用Banker算法解決沖突與死鎖問題，但其缺點是系統(tǒng)的資源利用率較低同時不能解決潛在的死鎖問題。

本文運用動態(tài)銀行家Banker算法在提高小車作業(yè)路徑靈活性的同時能夠避免系統(tǒng)發(fā)生沖突和死鎖。首先根據各RGV的任務分配情況，運用Dijkstra算法[6]離線計算出各RGV的最短作業(yè)路徑（不考慮是否存在沖突或死鎖情況）；然后使用改進的Bnaker算法來檢查RGV的路徑是否存在死鎖或沖突；最后，運用改進的迭代時間窗法來消除系統(tǒng)在作業(yè)過程中所出現的沖突與死鎖現象，從而保證系統(tǒng)運行的安全性。

1 多小車多升降級AVS/RS系統(tǒng)布局

一個任務的路徑是由弧（節(jié)點）的集合來表示ρA={aj|aj∈A}或 ρN={nj|nj∈N}，路徑弧 ρA的權重等于終點弧 d的釋放時間，即 ε（ρ）=，則任務 M起ρi點 Oi與終點 di的路徑為 Φi={，，…，}，則任務Mi可定義為

式中：Φi為任務的路徑節(jié)點集合；Rk為承擔該任務的RGV小車編號；Pi（t）為小車Ri的時間運行路徑長度動態(tài)優(yōu)先級，值越大表示優(yōu)先級越高，可表示為

式中：Ldi為完成任務Mi的路徑長度；L為理想路徑長度；ρi為任務的預計完成時間；Pio為任務的初始優(yōu)先級。

2 基于Banker算法的系統(tǒng)沖突與死鎖檢測

2.1 基本Banker算法

在基本Banker算法中，系統(tǒng)會對指定路徑的安全性進行評估，若有檢測到不安全的狀態(tài)，算法需要其它備選路徑，由于作業(yè)情景是動態(tài)變化的，一旦所有的備選路徑都檢測失敗，算法則需返回重新找出可行性路徑，所以無法滿足多小車多升降機系統(tǒng)的靈活性要求。

2.2 改進的Banker算法

在AVS/RS系統(tǒng)中，向量t、h，矩陣T為系統(tǒng)的資源矩陣，Ni為第i個RGV的路徑矩陣，Hi為第i個RGV的占用矩陣，A為系統(tǒng)的資源可用矩陣。上述矩陣中的元素均用二進制表示，其中行數等于智能立庫的層數，列數為每層包含的弧（節(jié)點）的數量，對于被占用的弧（節(jié)點）用1表示，反之則為0。

如圖1所示，系統(tǒng)的每一層包含23個有向弧及78個節(jié)點，例如：假設小車R1位于第一層，要從A13到達 A9，其路徑為 ρ1=｛13，16，17，8，9｝，則其路徑矩陣N1的第一行為 ［0 0 0 0 0 0 0 1 1 0|0 0 1 0 0 1 1 0 0 0|0 0 0］，其它元素均為 0；其當前位置的占用矩陣H1的第一行為［0 0 0 0 0 0 0 0 0 0|0 0 1 0 0 1 0 0 0 0|0 0 0］。上述算法，可以判斷某一作業(yè)階段在同一段弧中是否會出現沖突，但是，無法對節(jié)點沖突進行判斷。

圖1 AVS/RS系統(tǒng)單層平面圖Fig.1 Single floor plan of AVS/RS

因此，本文引入節(jié)點矩陣n，路徑長度優(yōu)先級較高的RGV優(yōu)先占有該節(jié)點。對于同一臺RGV的路徑弧（節(jié)點）矩陣Ni按照其任務特征分為2個階段，一是取貨（裝載），即從當前位置至貨物位置；二是送貨（卸載），即從貨物位置到達任務目標位置。當某小車需要使用的弧或節(jié)點已被其它小車占用，若前者使用該弧（節(jié)點）的時間內，系統(tǒng)仍然安全，則該小車仍然可以使用該弧（節(jié)點）。

上述算法中，運用改進的Banker算法分別對小車的作業(yè)過程進行了分階段的沖突檢測，因此減少了算法的在線計算量。

2.3 沖突與死鎖類型的判斷

由于本文所述系統(tǒng)在發(fā)生沖突與死鎖的情況為2個以上的小車在同一層上的路徑發(fā)生重疊，因此沖突與死鎖類型主要可分為4種：

1）路口沖突：含有相同節(jié)點的數量為1；

2）單弧沖突：含有相同節(jié)點的數量大于1（重復節(jié)點次序相同或相反）且含有相同弧數量為1；

3）多弧同向沖突：含有相同弧數量大于1且相同節(jié)點順序相同；

4）多弧反向沖突：含有相同弧數量大于1且相同節(jié)點順序相反。

3 基于迭代時間窗法的沖突與死鎖消除

本文采用基于迭代時間窗的動態(tài)調度策略，因此運用RGV的通過時間來表示每段弧（2個節(jié)點之間路徑）的權重，假設RGV均為勻速運動，則第h層弧j（節(jié)點j和k之間）的權重為

式中：Lhi為第h層弧j（節(jié)點j和k之間）的長度；VR為RGV的運行速度；t0為緩沖時間0.05Lhj/VR。

由于每個RGV同一時間只能占用一段弧，同時同一段弧同一時間只能被一臺RGV占用，則小車Ri占用弧ahj的時間窗Wihj可表示為

每段弧ahj的時間窗可用時間向量的形式來表示：

向量中的第一個元素對應優(yōu)先級最高的任務，第n個元素對應優(yōu)先級最低的任務。所有向量的維度等于任務數n（RGV數量）。由式（5）可以看出，向量無法表示任務訪問弧的順序，因此定義向量X=［Xi］。

3.1 初始時間向量

運用Dijkstra算法[6]可得出各RGV在不考慮沖突或死鎖情況下的最短路徑ρ，然后通過式（3）可以得到各RGV所需路徑的初始時間窗分布，則每一段弧ahj的初始時間向量可由式（5）得到。

3.2 沖突與死鎖解決方案

3.2.1 延伸時間窗

若2個或多個RGV在同一段時間內請求一段弧，即該段弧的時間窗會出現重疊，則需對該段弧的時間窗進行調整，該段弧的釋放時間為

3.2.2 解決方案

路口沖突 由于只含有一個相同的節(jié)點，則原則上延伸路徑長度優(yōu)先級較低小車的上一節(jié)點的時間窗，延長時間為通過兩節(jié)間弧權重的2倍；

單弧沖突 由于含有相同節(jié)點的數量大于1且含有相同弧數量為1，則原則上即延伸路徑長度優(yōu)先級較低小車在第一個沖突節(jié)點的前一節(jié)點時間窗，延長時間為通過此段重疊弧的時間（因為一段弧同一時間只能被一個小車占用）；

多弧同向沖突 由于含有相同弧數量大于1且相同節(jié)點順序相同，則原則上延伸路徑長度優(yōu)先級較低小車在第一個沖突節(jié)點的前一節(jié)點時間窗，延長時間為通過所有重疊節(jié)點的時間；

多弧反向沖突 由于含有相同弧數量大于1且相同節(jié)點順序相反。若某小車的所有路徑節(jié)點為另一小車路徑節(jié)點的一部分，則應讓后者先通過，即延伸前者在其第一個沖突節(jié)點的前一節(jié)點時間窗，延長時間為后者通過所有重疊節(jié)點的時間；若只是部分路徑節(jié)點重疊，則原則上延伸路徑長度優(yōu)先級較低小車在其第一個沖突節(jié)點的前一節(jié)點時間窗，延長時間為通過所有重疊節(jié)點的時間。

對于所有節(jié)點時間窗的延長，本文采用的是不改變小車的運行速度，而是讓小車在節(jié)點處等待的策略。當某RGV路徑中某段弧（2個節(jié)點）的釋放時間進行調整后，需要改變其后續(xù)路徑節(jié)點的時間窗向量，因此需要重新檢測各RGV的路徑時間窗是否出現重疊。

4 系統(tǒng)沖突與死鎖控制策略

由上節(jié)分析可知，當給出系統(tǒng)的作業(yè)方案后，需進行沖突與死鎖檢測并給出相應的解決方案。

4.1 沖突與死鎖控制策略

步驟1 根據系統(tǒng)給出的作業(yè)方案，按照2.2節(jié)所述的改進Banker算法得出各小車2個階段的路徑弧矩陣和節(jié)點矩陣，完成初始化。

步驟2 將小車的路徑弧矩陣和節(jié)點矩陣進行兩兩比較，若出現同一階段的弧矩陣和節(jié)點矩陣有重疊的情況，則按照2.3節(jié)所述方法進行沖突與死鎖類型預判斷；若否，則退出程序。

步驟3 根據找到的可能發(fā)生的沖突與死鎖節(jié)點，按照3.1節(jié)所述方法完成沖突與死鎖預發(fā)生節(jié)點的前一節(jié)點及所有后續(xù)節(jié)點的時間窗初始化。

步驟4 若任意兩小車的初始時間窗有重疊發(fā)生，則按照3.2節(jié)所述方法對相應的沖突與死鎖類型來調整節(jié)點時間窗，直到所有路徑節(jié)點無重疊發(fā)生為止，若無重疊，則退出程序。

4.2 算法實例驗證

本文針對2.3節(jié)給出的系統(tǒng)可能出現的4種沖突與死鎖類型，分別給出實例，并按照3.2節(jié)所述方法進行消除。

本文首先按照圖1所示的單層平面路徑圖對系統(tǒng)中的4個小車進行任務分配及路徑規(guī)劃。則4個小車的任務參數分別為

任務M1是2號小車將目標貨物從n1023（裝載點，代表其所在位置為第10層23號節(jié)點）運至出庫口n0115，小車當前所在位置為n0511，其任務優(yōu)先級第一階段為1，第二階段為2。

根據4.1節(jié)所述完成各小車的路徑矩陣初始化后，發(fā)現系統(tǒng)存在預沖突現象，需要給出沖突路徑節(jié)點的時間窗，如圖2所示。

圖2 基于時間窗沖突與死鎖判斷Fig.2 Conflicts and deadlocks judgment based on time window

如圖2中的（a）可以看出，小車1與小車2在節(jié)點n0520處會發(fā)生節(jié)點沖突，根據3.2.2需對小車2的n0519→n0520段時間窗延長2 s（小車1通過此節(jié)點時間的2倍）。

從（b）可以看出，小車2與小車3在n0142→n0157段發(fā)生單弧沖突，所以應該將小車3在n0141→n0142段時間窗延長4 s（小車2通過該弧的時間），同時更新小車3的后續(xù)路徑n0157→n0158段時間窗。

從（c）可以看出，小車1與小車4在n1050→n1035段及n1035→n1020段發(fā)生沖突，屬于多弧同向沖突，所以應該將小車4在n1051→n1050段時間窗延長8 s（小車1通過該弧的時間），同時更新小車4的后續(xù)路徑n1020→n1018段時間窗。

從（d）可以看出，小車2與小車4雖然只在n0142→n0157段的時間窗有重疊，但兩者在n0127→n0142段及n0142→n0157段發(fā)生向相沖突，屬于多弧反向沖突，所以應該將小車4在n0177→n0127段時間窗延長8 s（小車2通過該弧的時間），同時更新小車4的后續(xù)路徑n0157→n0183段時間窗。

上述4種類型的沖突與死鎖問題的消除結果如圖3所示。

圖3可以看出本文提出的基于時間窗的沖突與死鎖消除策略能夠有效解決AVS/RS系統(tǒng)中的沖突與死鎖問題。

圖3 基于時間窗的沖突與死鎖消除結果Fig.3 Conflicts and deadlocks eliminate results based on the time window

5 結語

本文提出了一種基于迭代時間窗法的多小車多升降機AVS/RS系統(tǒng)沖突與死鎖控制策略。首先，運用改進的Banker算法使每個RGV小車的執(zhí)行路徑最短；其次，將作業(yè)過程分為2個階段，對2個階段分別運用改進Banker算法來進行沖突與死鎖預判斷；最后，運用改進的時間窗算法來消除沖突及死鎖，從而在提高RGV的使用率的同時，增強了系統(tǒng)的安全性。

[1] Nenad S R，I F A.Time windows based dynamic routing in multi-AGV systems[J].IEEE Transactions on Automation Science and Engineering，2010，7（1）：151-155.

[2] M P Fanti，B Turchiano.Deadlock avoidance in automated guided vehicle systems//[C]2001 IEEE/ASMEInt.Conf.Adv.Intell.Mechatron.，Italy，2001：1017-1022.

[3] C-C Lee，J T Lin.Deadlock prediction and avoidance based on Petri nets for zone-control automated guided vehicle systems[J].Int.J.Production Res.，2005（33）：3249-3265.

[4] Wu N Q，Zhou M C.Deadlock modeling and control of automated guided vehicle systems[J].IEEE/ASME Trans.Mechatron.，2004，9（1）：50-57.

[5] M-S Yeh，W-C Yeh.Deadlock prediction and avoidance for zonecontrol AGVS[J].Int.J.Production Res.，1998，36（10）：2879-2889.

[6] N Q Wu，W Q Zeng.Deadlock avoidance in AGV system using colored Petri net model[J].Int.J.Production Res.，2002，40（1）：223-238.

[7] 胡彬，王冰，王春香，等.一種基于時間窗的自動導引車動態(tài)路徑規(guī)劃方法[J].上海交通大學學報，2012，46（6）：133-137.

[8] 賀麗娜，樓佩煌，錢曉明，等.基于時間窗的自動導引車無碰撞路徑規(guī)劃[J].計算機集成制造系統(tǒng)，2010，16（12）：88-92. ■