過金超 張飛航 蘭東軍 曹宏 王普杰

摘要：針對(duì)AGV現(xiàn)有的路徑規(guī)劃方法無法解決對(duì)發(fā)任務(wù)、死鎖問題等，提出了一種新的AGV路徑?jīng)_突處理方法GWM，以解決更為復(fù)雜的路徑?jīng)_突問題.但GWM在部分沖突場(chǎng)景中的處理效率不高，在此基礎(chǔ)上又提出了基于GWM的路徑?jīng)_突處理算法OCWG.該算法融合了等待法、重新規(guī)劃法和GWM 3種路徑處理方法，在AGV位置刷新的時(shí)候，檢測(cè)其在安全距離內(nèi)是否會(huì)與其他AGV發(fā)生沖突，并且能根據(jù)實(shí)時(shí)的系統(tǒng)狀態(tài)選擇合適的路徑?jīng)_突處理方法，使其中一輛AGV行駛到空閑點(diǎn)進(jìn)行讓路.測(cè)試結(jié)果表明，OCWG算法的總花費(fèi)時(shí)間較少，也能滿足包括重復(fù)任務(wù)和對(duì)發(fā)任務(wù)在內(nèi)的所有需求，而且不會(huì)出現(xiàn)觸發(fā)碰撞警告和死鎖問題.

Abstract：In view of the fact that the existing path planning methods of AGV are unable to solve the problem of dispatching task and deadlock， a new path conflict processing method named GWM was proposed to solve more complex path conflict problems. However， GWM was not efficient in some conflict scenarios. On this basis， a GWM|based path conflict processing algorithm named OCWG was proposed. This algorithm combined three path processing methods： waiting method， rerouting method and GWM. When the AGV position was refreshed， it detected whether it would conflict with other AGVs in the safe distance， and chose an appropriate path conflict processing method according to the real|time system state. The test results showed that OCWG algorithmtook less time and satisfied all the requirements including repetitive tasks and dispatching tasks， without triggering collision warning and deadlock problems.

關(guān)鍵詞：自動(dòng)導(dǎo)引車;路徑?jīng)_突處理;GWM;OCWG算法

Key words：AGV;path conflict processing;GWM;OCWG algorithm

中圖分類號(hào)：TP242文獻(xiàn)標(biāo)識(shí)碼：ADOI：10.3969/j.issn.2096-1553.2019.04.011

文章編號(hào)：2096-1553（2019）04-0074-07

0 引言

自動(dòng)導(dǎo)引車（AGV）是指安裝有自動(dòng)導(dǎo)引系統(tǒng)、可沿著導(dǎo)引線或通過視覺導(dǎo)航等方式運(yùn)動(dòng)、具有搬運(yùn)貨物等功能、無人駕駛的運(yùn)輸小車[1-2].近年來，AGV在汽車工業(yè)和港口運(yùn)輸?shù)阮I(lǐng)域?qū)崿F(xiàn)跨越式發(fā)展，尤其是在電商物流行業(yè)給人們帶來了方便與快捷[3-4].由多個(gè)AGV組成的多AGV系統(tǒng)可以輕松地在路徑足夠豐富的地圖上進(jìn)行無沖突路徑運(yùn)動(dòng).然而在大多數(shù)制造車間，受到空間和場(chǎng)地的影響，實(shí)際路徑不能像快遞業(yè)那樣自由鋪設(shè)，因此車間環(huán)境對(duì)多AGV系統(tǒng)路徑規(guī)劃是一個(gè)挑戰(zhàn)[5-6].

在企業(yè)物流自動(dòng)化生產(chǎn)線上，單個(gè)AGV的路徑規(guī)劃是最短路徑搜索的過程，然而如果多個(gè)AGV同時(shí)運(yùn)行在一個(gè)地圖上，仍采用最短路徑搜索，勢(shì)必會(huì)造成路徑?jīng)_突和道路阻塞[7-8].很多學(xué)者都傾向于在路徑規(guī)劃階段把路徑?jīng)_突的問題考慮進(jìn)去，提前預(yù)知并通過等待法解決路徑?jīng)_突問題，例如時(shí)間窗法[9]、兩階段規(guī)劃法[10]等.但在實(shí)際運(yùn)行中，AGV不可避免地會(huì)發(fā)生各種各樣的問題，例如速度估計(jì)誤差、機(jī)械故障等[11-12].因此，在多AGV系統(tǒng)中，對(duì)路徑?jīng)_突處理算法的研究是必不可少的.傳統(tǒng)的路徑?jīng)_突處理方法只有等待法和重新規(guī)劃法，這兩種方法針對(duì)路徑足夠豐富的地圖可以解決多數(shù)沖突問題，但應(yīng)用于車間環(huán)境下的地圖有可能出現(xiàn)對(duì)發(fā)任務(wù)、死鎖等問題.

本文擬提出基于GWM的路徑?jīng)_突處理算法OCWG（obstacle， conflict， waiting， giving|way），以解決車間環(huán)境下多AGV系統(tǒng)路徑?jīng)_突問題，并通過實(shí)踐應(yīng)用來驗(yàn)證算法的穩(wěn)定性與魯棒性，以滿足企業(yè)物流自動(dòng)化的要求.

1 問題闡述

1.1 車間環(huán)境下的地圖模型

車間環(huán)境下的多AGV路徑規(guī)劃之所以難度較大，主要是因?yàn)槠涞貓D模型的獨(dú)特性.地圖模型可分為閉環(huán)地圖和開環(huán)地圖.閉環(huán)地圖是指地圖上的每個(gè)節(jié)點(diǎn)至少連接兩條線路，因此AGV不容易出現(xiàn)擁堵問題.網(wǎng)格圖是典型的閉環(huán)地圖（見圖1），具有豐富的路徑資源，在電商物流行業(yè)被大量使用.開環(huán)地圖是指不能構(gòu)成閉環(huán)的地圖，地圖中存在許多只連接了一條線路的節(jié)點(diǎn)，常見的車間地圖（見圖2）不能構(gòu)成閉環(huán)地圖或僅包含少數(shù)閉環(huán)線路，通常只有一條或兩條主干道，在這樣的地圖上極易發(fā)生路徑?jīng)_突和死鎖問題.

1.2 路徑?jīng)_突類型

多AGV系統(tǒng)中路徑?jīng)_突問題可分為6種類型，即追及沖突、對(duì)向沖突、路口沖突、路徑障礙、終點(diǎn)障礙和死鎖問題，其示意圖如圖3—圖8所示.這6種類型又可歸結(jié)為沖突型問題、障礙型問題和死鎖問題3類.

追及沖突是指兩輛AGV以相同的方向行駛，其中落后的AGV因?yàn)槟撤N原因會(huì)以較快的速度行駛，可能會(huì)追上靠前的AGV并發(fā)生碰撞事故，其速度差可能是由于載貨重量不同而引起的.這種情形可通過等待法解決，即后車在前一節(jié)點(diǎn)停車，等待前車通過后再行駛.

對(duì)向沖突是指兩輛AGV以相反的方向行駛，若不采取相應(yīng)的措施，會(huì)在一定時(shí)間內(nèi)發(fā)生碰撞事故.造成碰撞事故的原因往往是在路徑規(guī)劃階段沒有解決好兩輛AGV對(duì)相同路徑資源爭(zhēng)奪的問題.這種情形一旦發(fā)生，如果沒有備用路徑，會(huì)造成死鎖問題.

路口沖突是指兩輛AGV在競(jìng)爭(zhēng)路口資源時(shí)發(fā)生沖突，其原因依然是路徑規(guī)劃階段沒有解決資源競(jìng)爭(zhēng)問題.出現(xiàn)這種情況，如果雙方在路口節(jié)點(diǎn)之后的路徑不是對(duì)方所在的線路，則可通過等待法解決;若雙方恰好處在對(duì)方的線路上且沒有備用路徑可取時(shí)，會(huì)造成死鎖問題.

路徑障礙是指有其他AGV?？吭谶\(yùn)行中的AGV的路徑上，阻礙了AGV的前進(jìn).該障礙AGV通常是在執(zhí)行任務(wù)或發(fā)生機(jī)械故障，無法主動(dòng)對(duì)運(yùn)行AGV進(jìn)行避讓，這種情形下如果沒有備用路徑可取，只能通過等待法解決.

終點(diǎn)障礙是指有其他AGV?？吭谶\(yùn)行AGV的目標(biāo)節(jié)點(diǎn)上，阻止了運(yùn)行AGV進(jìn)入目標(biāo)節(jié)點(diǎn)，其原因可能是重復(fù)任務(wù)的執(zhí)行時(shí)間沒有錯(cuò)開.這種情形只能采用等待法，等待障礙AGV執(zhí)行完任務(wù)離開目標(biāo)節(jié)點(diǎn).

死鎖問題是指多個(gè)AGV互相阻礙了對(duì)方的路徑，卡死在一個(gè)區(qū)域中，無法通過常規(guī)方法解決.這種情況常常是在上述其他問題沒有解決時(shí)產(chǎn)生的，也是在路徑規(guī)劃階段就需要避免的問題.

2 GWM方法的工作流程

車間工作中常見的是重復(fù)任務(wù)和對(duì)發(fā)任務(wù).重復(fù)任務(wù)通常有多個(gè)AGV在同一路徑上不斷往復(fù)行駛，對(duì)發(fā)任務(wù)類似于兩輛AGV互換位置的過程.雖然等待法和重新規(guī)劃法在大多數(shù)情況下都能很好地解決此類路徑?jīng)_突問題，但是在車間環(huán)境下仍然存在一些無法克服的困難.GWM的靈感來源于駕駛員的良好習(xí)慣：當(dāng)兩輛汽車在一個(gè)狹窄的十字路口相遇時(shí)，其中一輛車會(huì)先退后到相對(duì)寬裕的場(chǎng)地給另外一輛車讓行，等到可以通過時(shí)再繼續(xù)行駛.GWM是對(duì)這一傳統(tǒng)方法的補(bǔ)充，可使路徑?jīng)_突處理方法更加完善.GWM方法的工作流程如圖9所示.

GWM通常使用優(yōu)先級(jí)比較的方法來確定哪輛AGV讓路，或者通過比較兩輛AGV的讓路成本來確定哪輛AGV讓路.讓路時(shí)，GWM根據(jù)不同的情況選擇合適的自由節(jié)點(diǎn).廣義自由節(jié)點(diǎn)指所有AGV都不會(huì)通過或占用的節(jié)點(diǎn)，狹義自由節(jié)點(diǎn)指與之沖突的AGV不會(huì)通過或占用的節(jié)點(diǎn);選擇廣義自由節(jié)點(diǎn)不會(huì)引起連鎖反應(yīng)，選擇狹義自由節(jié)點(diǎn)則效率會(huì)更高.當(dāng)讓路AGV到達(dá)自由節(jié)點(diǎn)時(shí)，沖突AGV沿著初始路徑行駛，當(dāng)沖突AGV到達(dá)合適的節(jié)點(diǎn)時(shí)，讓路AGV重新搜索最優(yōu)路徑繼續(xù)前進(jìn).由此，沖突問題得以解決.與傳統(tǒng)的等待法和重新規(guī)劃法相比，GWM方法略顯復(fù)雜，但可有效解決傳統(tǒng)方法無法解決的難題.

圖10模擬了GWM處理路徑?jīng)_突的過程，其中N2分別連接到N1，N3和N4.1#AGV的初始節(jié)點(diǎn)是N2，目標(biāo)節(jié)點(diǎn)是N1，理想路徑是N2—N1.同時(shí)2#AGV的初始節(jié)點(diǎn)是N1，目標(biāo)節(jié)點(diǎn)是N4，理想路徑是N1—N2—N4.此時(shí)，2#AGV占據(jù)著1#AGV的目標(biāo)節(jié)點(diǎn)，同時(shí)1#AGV阻礙了2#AGV的路徑，所以1#AGV采用GWM，先行駛到一個(gè)不在2#AGV路徑的空閑節(jié)點(diǎn)，即N3，然后2#AGV沿著理想路徑行駛，當(dāng)2#AGV到達(dá)N4并不再占據(jù)N2時(shí)，1#AGV再次搜索最佳路徑，即N3—N2—N1.

3 OCWG算法設(shè)計(jì)與實(shí)現(xiàn)

GWM理論上可以很好地解決多AGV系統(tǒng)的路徑?jīng)_突問題，而在實(shí)際應(yīng)用中，其在部分沖突場(chǎng)景的處理效率不如等待法和重新規(guī)劃法.因此，筆者基于GWM提出了OCWG算法.

該算法融合了等待法、重新規(guī)劃法和GWM 3種路徑處理方法，可以基于不同情形采取相應(yīng)的方法，從而解決多AGV系統(tǒng)中的路徑?jīng)_突問題，防止碰撞事故和死鎖問題的發(fā)生.

OCWG算法包括兩個(gè)模塊，即檢測(cè)模塊和處理模塊.檢測(cè)模塊負(fù)責(zé)檢測(cè)AGV是否會(huì)在安全距離內(nèi)與其他AGV發(fā)生沖突，當(dāng)檢測(cè)到?jīng)_突時(shí)，處理模塊負(fù)責(zé)不同情況的沖突處理工作.基于GWM的OCWG算法可以保證在任何情況下都能很好地處理沖突而不會(huì)發(fā)生碰撞或死鎖.

首先，定義4種AGV的工作模式，即空閑模式（IM）、運(yùn)行模式（RM）、等待模式（WM）和GWM模式（GM）.IM表示AGV沒有任務(wù)安排且在節(jié)點(diǎn)處?？?RM表示AGV具有任務(wù)目標(biāo)且在規(guī)劃路線上正常運(yùn)行;WM表示AGV具有任務(wù)目標(biāo)但需要在當(dāng)前節(jié)點(diǎn)停靠以等待解決沖突問題;GM表示AGV正在運(yùn)行到空閑節(jié)點(diǎn)以讓位給其他AGV.

所有在拓?fù)涞貓D上運(yùn)行的AGV 遇到的沖突只有兩種情形，即障礙和沖突.

障礙是指在AGV運(yùn)行的路線上有另一輛AGV停放或運(yùn)行，分為固定障礙和移動(dòng)障礙.考慮到安全距離的限制，無論雙方處于何種模式，運(yùn)行AGV必須先停止前進(jìn)再進(jìn)行后續(xù)處理.固定障礙是指處于IM或WM的障礙AGV?？吭谶\(yùn)行AGV的規(guī)劃路線上，在障礙AGV完成其任務(wù)之前，控制系統(tǒng)無權(quán)移動(dòng)該障礙AGV，因此，當(dāng)前AGV將重新規(guī)劃路線并避開障礙AGV.移動(dòng)障礙是指處于RM或GM的障礙AGV行駛在運(yùn)行AGV的規(guī)劃路線上，對(duì)于處于RM的障礙AGV，運(yùn)行AGV需要通過對(duì)比優(yōu)先級(jí)來判斷接下來的處理工作.若運(yùn)行AGV具有更高的優(yōu)先級(jí)，則切換到WM并等待障礙AGV通過，否則進(jìn)行讓路判斷.如果運(yùn)行AGV在障礙AGV的規(guī)劃路線上，則采用GWM，否則切換到WM并等待障礙AGV的通過.對(duì)于處于GM的障礙AGV，如果運(yùn)行AGV處于GM模式，則先進(jìn)行優(yōu)先級(jí)比較，如果運(yùn)行AGV處于RM，則以優(yōu)先級(jí)低的結(jié)果進(jìn)行后續(xù)操作.不同模式的優(yōu)先級(jí)關(guān)系為IM>WM>GM>RM.

沖突是指多個(gè)AGV的規(guī)劃路線具有重疊部分，并且可能在未來的時(shí)間內(nèi)發(fā)生追及沖突、對(duì)向沖突或路口沖突.沖突分為準(zhǔn)障礙和未來沖突.準(zhǔn)障礙是指沖突AGV的下一個(gè)節(jié)點(diǎn)在運(yùn)行AGV的規(guī)劃路線上，此時(shí)運(yùn)行AGV采用與遇到移動(dòng)障礙時(shí)相同的處理方法.未來沖突是指運(yùn)行AGV安全距離內(nèi)的規(guī)劃路線節(jié)點(diǎn)與沖突AGV的規(guī)劃路線節(jié)點(diǎn)有重疊部分，運(yùn)行AGV需要與沖突AGV進(jìn)行優(yōu)先級(jí)比較，如果運(yùn)行AGV的優(yōu)先級(jí)更高，則繼續(xù)行駛，否則判斷是否需要為沖突AGV讓路，如果運(yùn)行AGV正處于沖突AGV的規(guī)劃路線上，則采用GWM，否則切換到WM并等待沖突AGV的通過.處理模塊中的障礙處理流程如圖11所示，沖突處理流程如圖12所示.

4 實(shí)踐驗(yàn)證與應(yīng)用

本文的實(shí)踐應(yīng)用平臺(tái)是SIMATIC WinCC，它是西門子經(jīng)典的過程監(jiān)控系統(tǒng)，可以在工業(yè)領(lǐng)域提供完整的監(jiān)控和數(shù)據(jù)采集功能，并且可以作為上位機(jī)控制多AGV系統(tǒng).

實(shí)踐應(yīng)用在河南森源電氣股份有限公司的車間進(jìn)行.實(shí)驗(yàn)所用AGV是由河南森源自主研發(fā)的雙向重載AGV，其控制系統(tǒng)展示的車間地圖及控制按鈕如圖13所示.車間地圖是一個(gè)不規(guī)則的拓?fù)溟_環(huán)地圖，這為基于GWM的OCWG算法提供了充分的測(cè)試環(huán)境.

在相同任務(wù)下，時(shí)間窗法和OCWG算法完成任務(wù)所需時(shí)間的對(duì)比結(jié)果如圖14所示，縱坐標(biāo)表示所有AGV到達(dá)各自目標(biāo)節(jié)點(diǎn)的距離之和，橫坐標(biāo)表示花費(fèi)的時(shí)間.由圖14可以看出，時(shí)間窗法在任務(wù)中使用了等待法，其中一輛AGV處于停車狀態(tài)，導(dǎo)致任務(wù)時(shí)間延長(zhǎng).而在OCWG算法執(zhí)行中，發(fā)現(xiàn)途中有總距離不降反升的過程，這一過程就是在執(zhí)行GWM，系統(tǒng)提前預(yù)測(cè)到有沖突行為，進(jìn)行了讓路操作.雖然總距離有上升的過程，但OCWG算法為后續(xù)的AGV運(yùn)行提供了更加順暢的路徑，所以O(shè)CWG算法的總花費(fèi)時(shí)間比時(shí)間窗法少.另外，當(dāng)任務(wù)復(fù)雜度逐漸升高時(shí)，僅僅依靠等待法的時(shí)間窗法顯然不能完成任務(wù)，而基于GWM的OCWG算法依然可以確保完成任務(wù).

在基于車間實(shí)際需求的測(cè)試過程中，OCWG算法可以滿足包括重復(fù)任務(wù)和對(duì)發(fā)任務(wù)在內(nèi)的所有需求，并且從未出現(xiàn)碰撞警告和死鎖問題，從而驗(yàn)證了OCWG算法的可行性和穩(wěn)定性.

5 結(jié)語(yǔ)

本文提出了一種新的AGV路徑?jīng)_突處理方法GWM，與傳統(tǒng)的等待法和重新規(guī)劃法不同，GWM可以解決更為復(fù)雜的路徑?jīng)_突問題，但對(duì)部分沖突場(chǎng)景的處理效率不高.在此基礎(chǔ)上提出了一種新的路徑?jīng)_突處理算法OCWG，與合適的路徑搜索算法配合，可高效率地解決各種路徑規(guī)劃和路徑?jīng)_突問題.實(shí)際測(cè)試驗(yàn)證了OCWG算法的魯棒性和穩(wěn)定性.后續(xù)將繼續(xù)深入研究該算法可支持的AGV數(shù)量與地圖規(guī)模的關(guān)系，從而進(jìn)一步優(yōu)化算法性能.

參考文獻(xiàn)：

[1] LE|ANH T，DE KOSTER M B M.A review of design and control of automated guided vehicle systems[J].European Journal of Operational Research，2006，171（1）：1.

[2] 過金超，趙海洋，蔣正軻，等.雙向重載智能自主導(dǎo)航車系統(tǒng)設(shè)計(jì)[J].輕工學(xué)報(bào)，2017，32（2）：97.

[3] ROODBERGEN K J，VIS I F A.A survey of literature on automated storage and retrieval systems[J].European Journal of Operational research，2009，194（2）：343.

[4] 過金超，劉征，崔光照.基于人工免疫網(wǎng)絡(luò)理論的移動(dòng)機(jī)器人路徑規(guī)劃[J].鄭州輕工業(yè)學(xué)院學(xué)報(bào)（自然科學(xué)版），2012，27（4）：1.

[5] FANTI M P，MANGINI A M，PEDRONCELLI G，et al.A decentralized control strategy for the coordination of AGV systems[J].Control Engineering Practice，2018，70：86.

[6] SHI Y，WANG X，SUN X，et al.A two|phase strategy with micro genetic algorithm for scheduling Multiple AGVs[C]∥2016 IEEE International Conference on Systems，Man，and Cybernetics （SMC）.Piscataway：IEEE，2016：003101.

[7] 高瑜，過金超，崔光照.一種改進(jìn)的多機(jī)器人路徑規(guī)劃自適應(yīng)人工勢(shì)場(chǎng)法[J].鄭州輕工業(yè)學(xué)院學(xué)報(bào)（自然科學(xué)版），2013，28（6）：77.

[8] GHASEMZADEH H，BEHRANGI E，AZGOMI M A.Conflict|free scheduling and routing of automatedguided vehicles in mesh topologies[J].Robotics and Autonomous Systems，2009，57（6/7）：738.

[9] 劉國(guó)棟，曲道奎，張雷.多AGV 調(diào)度系統(tǒng)中的兩階段動(dòng)態(tài)路徑規(guī)劃[J].機(jī)器人，2005，27（3）：210.

[10]SMOLIC|ROCAK N，BOGDAN S，KOVACIC Z，et al.Time windows based dynamic routing in multi|agvsystems[J].IEEE Transactions on AutomationScience and Engineering，2010，7（1）：151.

[11]WADHWA S，DUCQ Y，ALI M，et al.Performance analysis of a flexible manufacturing system[J].Global Journal of Flexible Systems Management，2009，10（3）：23.

[12]MIYAMOTO T，INOUE K.Local and random searches for dispatch and conflict|free routing problem of capacitated AGV systems[J].Computers & Industrial Engineering，2016，91：1.