基于GWM的多AGV路徑沖突處理算法

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

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

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.

關鍵詞：自動導引車;路徑沖突處理;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 引言

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

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

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

1 問題闡述

1.1 車間環境下的地圖模型

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

1.2 路徑沖突類型

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

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

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

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

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

終點障礙是指有其他AGV停靠在運行AGV的目標節點上，阻止了運行AGV進入目標節點，其原因可能是重復任務的執行時間沒有錯開.這種情形只能采用等待法，等待障礙AGV執行完任務離開目標節點.

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

2 GWM方法的工作流程

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

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

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

3 OCWG算法設計與實現

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

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

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

首先，定義4種AGV的工作模式，即空閑模式（IM）、運行模式（RM）、等待模式（WM）和GWM模式（GM）.IM表示AGV沒有任務安排且在節點處停靠;RM表示AGV具有任務目標且在規劃路線上正常運行;WM表示AGV具有任務目標但需要在當前節點停靠以等待解決沖突問題;GM表示AGV正在運行到空閑節點以讓位給其他AGV.

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

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

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

4 實踐驗證與應用

本文的實踐應用平臺是SIMATIC WinCC，它是西門子經典的過程監控系統，可以在工業領域提供完整的監控和數據采集功能，并且可以作為上位機控制多AGV系統.

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

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

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

5 結語

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

參考文獻：

[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] 過金超，趙海洋，蔣正軻，等.雙向重載智能自主導航車系統設計[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] 過金超，劉征，崔光照.基于人工免疫網絡理論的移動機器人路徑規劃[J].鄭州輕工業學院學報（自然科學版），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].鄭州輕工業學院學報（自然科學版），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 調度系統中的兩階段動態路徑規劃[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.