方彥軍，唐 猛

（武漢大學(xué) 自動(dòng)化系，武漢 430072）

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

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

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

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

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

式中：Φi為任務(wù)的路徑節(jié)點(diǎn)集合；Rk為承擔(dān)該任務(wù)的RGV小車編號(hào)；Pi（t）為小車Ri的時(shí)間運(yùn)行路徑長(zhǎng)度動(dòng)態(tài)優(yōu)先級(jí)，值越大表示優(yōu)先級(jí)越高，可表示為

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

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

2.1 基本Banker算法

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

2.2 改進(jìn)的Banker算法

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

如圖1所示，系統(tǒng)的每一層包含23個(gè)有向弧及78個(gè)節(jié)點(diǎn)，例如：假設(shè)小車R1位于第一層，要從A13到達(dá) 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；其當(dāng)前位置的占用矩陣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è)階段在同一段弧中是否會(huì)出現(xiàn)沖突，但是，無(wú)法對(duì)節(jié)點(diǎn)沖突進(jìn)行判斷。

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

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

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

2.3 沖突與死鎖類型的判斷

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

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

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

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

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

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

本文采用基于迭代時(shí)間窗的動(dòng)態(tài)調(diào)度策略，因此運(yùn)用RGV的通過(guò)時(shí)間來(lái)表示每段?。?個(gè)節(jié)點(diǎn)之間路徑）的權(quán)重，假設(shè)RGV均為勻速運(yùn)動(dòng)，則第h層弧j（節(jié)點(diǎn)j和k之間）的權(quán)重為

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

由于每個(gè)RGV同一時(shí)間只能占用一段弧，同時(shí)同一段弧同一時(shí)間只能被一臺(tái)RGV占用，則小車Ri占用弧ahj的時(shí)間窗Wihj可表示為

每段弧ahj的時(shí)間窗可用時(shí)間向量的形式來(lái)表示：

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

3.1 初始時(shí)間向量

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

3.2 沖突與死鎖解決方案

3.2.1 延伸時(shí)間窗

若2個(gè)或多個(gè)RGV在同一段時(shí)間內(nèi)請(qǐng)求一段弧，即該段弧的時(shí)間窗會(huì)出現(xiàn)重疊，則需對(duì)該段弧的時(shí)間窗進(jìn)行調(diào)整，該段弧的釋放時(shí)間為

3.2.2 解決方案

路口沖突 由于只含有一個(gè)相同的節(jié)點(diǎn)，則原則上延伸路徑長(zhǎng)度優(yōu)先級(jí)較低小車的上一節(jié)點(diǎn)的時(shí)間窗，延長(zhǎng)時(shí)間為通過(guò)兩節(jié)間弧權(quán)重的2倍；

單弧沖突 由于含有相同節(jié)點(diǎn)的數(shù)量大于1且含有相同弧數(shù)量為1，則原則上即延伸路徑長(zhǎng)度優(yōu)先級(jí)較低小車在第一個(gè)沖突節(jié)點(diǎn)的前一節(jié)點(diǎn)時(shí)間窗，延長(zhǎng)時(shí)間為通過(guò)此段重疊弧的時(shí)間（因?yàn)橐欢位⊥粫r(shí)間只能被一個(gè)小車占用）；

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

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

對(duì)于所有節(jié)點(diǎn)時(shí)間窗的延長(zhǎng)，本文采用的是不改變小車的運(yùn)行速度，而是讓小車在節(jié)點(diǎn)處等待的策略。當(dāng)某RGV路徑中某段?。?個(gè)節(jié)點(diǎn)）的釋放時(shí)間進(jìn)行調(diào)整后，需要改變其后續(xù)路徑節(jié)點(diǎn)的時(shí)間窗向量，因此需要重新檢測(cè)各RGV的路徑時(shí)間窗是否出現(xiàn)重疊。

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

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

4.1 沖突與死鎖控制策略

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

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

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

步驟4 若任意兩小車的初始時(shí)間窗有重疊發(fā)生，則按照3.2節(jié)所述方法對(duì)相應(yīng)的沖突與死鎖類型來(lái)調(diào)整節(jié)點(diǎn)時(shí)間窗，直到所有路徑節(jié)點(diǎn)無(wú)重疊發(fā)生為止，若無(wú)重疊，則退出程序。

4.2 算法實(shí)例驗(yàn)證

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

本文首先按照?qǐng)D1所示的單層平面路徑圖對(duì)系統(tǒng)中的4個(gè)小車進(jìn)行任務(wù)分配及路徑規(guī)劃。則4個(gè)小車的任務(wù)參數(shù)分別為

任務(wù)M1是2號(hào)小車將目標(biāo)貨物從n1023（裝載點(diǎn)，代表其所在位置為第10層23號(hào)節(jié)點(diǎn)）運(yùn)至出庫(kù)口n0115，小車當(dāng)前所在位置為n0511，其任務(wù)優(yōu)先級(jí)第一階段為1，第二階段為2。

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

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

如圖2中的（a）可以看出，小車1與小車2在節(jié)點(diǎn)n0520處會(huì)發(fā)生節(jié)點(diǎn)沖突，根據(jù)3.2.2需對(duì)小車2的n0519→n0520段時(shí)間窗延長(zhǎng)2 s（小車1通過(guò)此節(jié)點(diǎn)時(shí)間的2倍）。

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

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

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

上述4種類型的沖突與死鎖問(wèn)題的消除結(jié)果如圖3所示。

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

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

5 結(jié)語(yǔ)

本文提出了一種基于迭代時(shí)間窗法的多小車多升降機(jī)AVS/RS系統(tǒng)沖突與死鎖控制策略。首先，運(yùn)用改進(jìn)的Banker算法使每個(gè)RGV小車的執(zhí)行路徑最短；其次，將作業(yè)過(guò)程分為2個(gè)階段，對(duì)2個(gè)階段分別運(yùn)用改進(jìn)Banker算法來(lái)進(jìn)行沖突與死鎖預(yù)判斷；最后，運(yùn)用改進(jìn)的時(shí)間窗算法來(lái)消除沖突及死鎖，從而在提高RGV的使用率的同時(shí)，增強(qiáng)了系統(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] 胡彬，王冰，王春香，等.一種基于時(shí)間窗的自動(dòng)導(dǎo)引車動(dòng)態(tài)路徑規(guī)劃方法[J].上海交通大學(xué)學(xué)報(bào)，2012，46（6）：133-137.

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