基于GWM的多AGV路徑?jīng)_突處理算法

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

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

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

中圖分類號：TP242文獻標識碼：ADOI：10.3969/j.issn.2096-1553.2019.04.011

文章編號：2096-1553（2019）04-0074-07

0 引言

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

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

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

1 問題闡述

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

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

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

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

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

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

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

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

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

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

2 GWM方法的工作流程

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

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

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

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

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

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

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

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

所有在拓撲地圖上運行的AGV 遇到的沖突只有兩種情形，即障礙和沖突.

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

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

4 實踐驗證與應(yīng)用

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

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

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

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

5 結(jié)語

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

參考文獻：

[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].輕工學報，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ò)理論的移動機器人路徑規(guī)劃[J].鄭州輕工業(yè)學院學報（自然科學版），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] 高瑜，過金超，崔光照.一種改進的多機器人路徑規(guī)劃自適應(yīng)人工勢場法[J].鄭州輕工業(yè)學院學報（自然科學版），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] 劉國棟，曲道奎，張雷.多AGV 調(diào)度系統(tǒng)中的兩階段動態(tài)路徑規(guī)劃[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.