基于單向導引路徑網絡的AGVS自主路徑規劃及交通管理方法研究

郭大宏

（江蘇天奇物流系統工程股份有限公司，無錫 214187）

（江蘇天奇物流系統工程股份有限公司，無錫 214187）

基于單向導引路徑網絡的AGVS自主路徑規劃及交通管理方法研究

郭大宏

（江蘇天奇物流系統工程股份有限公司，無錫 214187）

（江蘇天奇物流系統工程股份有限公司，無錫 214187）

0 引言

由多臺自動導引車（automated guided vehicle,AGV）組成的自動導引車系統（automated guided vehicle system, AGVS）廣泛運用于多個行業的物流自動化[1]。在AGVS的設計過程中需要解決的問題很多，如導引路徑網絡的設計[2]、搬運任務分配和AGV調度[3]、AGV路徑規劃及避碰問題[4,5]等等。其中AGVS的路徑規劃與避碰問題是AGVS研究領域的一個難點，為了回避此問題，可以采用基于單循環導引路徑布局或基于“串級配置”導引路徑布局的AGVS。雖然此類系統控制簡單，可靠，然而運行效率低。為了提高AGVS的運行效率，可以采用雙向導引路徑網絡[6]，然而實現這樣一個系統難度較大，一般只適用于小型AGVS[7]。為了降低系統控制的難度，可以采用基于單向路徑網絡的AGVS，與雙向路徑網絡不同，單向路徑網絡在任意時刻每條路徑上面允許的運行方向確定不變，使得路徑規劃和交通管理算法的難度顯著降低，同時系統的可集成性和擴展性也很好，成為實施AGVS的最佳選擇，因此本文以基于單向路徑網絡的AGVS作為研究對象，提出了一種AGV自主路徑規劃及交通管理方法，通過仿真和

圖1 基于單向導引路徑網絡的AGVS

實驗證明此方法能夠保證AGVS無碰撞運行。

1 問題描述

AGVS由單向導引路徑網絡和若干輛AGV組成，某AGVS單向導引路徑網絡如圖1所示，路徑段上的方向表示AGV在當前路徑段上允許的運行方向，路徑段上的數字表示路徑段長度。節點由路徑交叉點和工位點組成。所謂AGVS路徑規劃及交通管理問題是指：當AGV收到一搬運任務需要規劃一條從自身當前位置到達搬運任務工位點的最優路徑，同時還要避免與其他AGV或環境障礙發生碰撞。對于基于單向路徑網絡的AGVS而言，可能引起AGV之間發生碰撞的沖突如圖2所示。

圖2 AGV運行過程中可能出現的三種沖突

2 基于電子地圖的自主路徑規劃方法

2.1 基于圖論的電子地圖建立方法

2.1.1 圖論法

圖論通過由點和邊組成的圖形來描述具有某種二元關系的系統，并根據圖的性質進行分析，提供研究各種系統的巧妙方法[1]。在本文中，將各個裝卸點、充電站等看作圖中的點，連線表示兩個點之間相互聯通?？梢杂靡粋€有序三元組G= (V,E,φ)表示一個圖，其中V={v1,v2,…,vn}是有窮非空集，表示的是點集；E=(e1,e2,…,en)也是有窮非空集，表示的是邊集；φ是從邊集E到點集V的有序或是無序的元素偶對的集合的映射，稱為關聯函數。

在圖中，與V中的有序偶對對應的邊e(φ(e)=(vi,vj))，稱為圖的有向邊，而與無序偶對vivj相對應的邊稱為圖的無向邊。如果圖中的每條邊都是有向邊則該圖稱為有向圖；反之，該圖稱為無向圖；如果圖中既有有向邊又有無向邊則稱圖為混合圖。我們將每條邊都帶有權值的圖叫做有權圖，沒有帶有權值的圖叫做無權圖。

本文中采用帶有權值的有向圖，其中權值表示頂點間的實際距離，方向表示AGV行駛只能從起點到終點。

2.1.2 基于圖論的電子地圖建模

點和線是圖的基本元素，本文中將點和線組合作為路徑段，以路徑段作為電子地圖的基本單元。本文將路徑段的數據結構設計成如表1所示。

表1 路徑段數據結構

數據結構中的各個數據的含義如表2所示。

表2 數據含義

根據本文設計的路徑段的數據結構，通過文檔串行化可以方便的將電子地圖數據信息保存成一個二進制數據文件，而且這樣的文件有良好的保密性，不易遭到惡意的修改破壞，只能通過本文開發的專用軟件才能安全打開和修改。

為了后期能夠有效的利用計算機進行處理，本文利用鄰接矩陣來表示電子地圖。對于一個加權有向圖G=(V,E,φ)可以用帶權鄰接矩陣A= (aij)n×n表示，其中aij值如式1所示。

2.2 路徑規劃方法

采用Dijkstra算法來求解這個問題, Dijkstra算法的基本思想是生長一顆以0v為根的最短路徑樹，在樹上的每一個頂點與根之間的路徑皆為最短路徑[10]。由于網絡中不存在負權，最短路徑樹的生長過程中每個頂點將按照距0v的遠近以及頂點的相鄰關系，逐次長入樹中，先近后遠，直至所有頂點都已在樹中。

3 基于單向導引路徑網絡的AGVS交通管理方法研究

對于基于單向路徑網絡的AGVS而言，可能引起AGV之間發生碰撞的沖突如圖2所示。各種沖突處理方法如下：

如圖2(a)所示沖突屬于趕超沖突。在一條路徑上有兩輛AGV同向行駛，后面的AGV行駛速度大于前面的AGV行駛速度產生這樣的沖突。可通過在AGV前方安裝必要的避碰傳感器，車載控制器利用避碰傳感器反饋回來的信號來判斷與前方車輛的距離，當車輛之間的距離過近，則AGV立即減速直至停車，避免兩車相撞。

如圖2(b)所示由于兩AGV爭搶同一個十字路口引起的，也是本文重點要解決的沖突。為每個路口定義一把鎖，并在交叉路口入口和出口分別設置加鎖和解鎖標簽（電子標簽），各AGV通過射頻讀卡設備拾取電子標簽信息來確定自身位置信息。當AGV獲取到加鎖標簽信息時，說明此時位于交叉路口入口，立即查詢此路口鎖信息，若已加鎖說明另一輛AGV已經占用此路口，此時應在加鎖標簽點等待，直至此路口鎖解鎖。若路口未加鎖則立即以廣播的形式主動向系統內的AGV發送此十字路口加鎖信息，確認所有AGV均收到信息后進入交叉路口，繼續運行，當獲取到解鎖標簽信息時說明此時已安全離開交叉路口，再次以廣播的形式向系統內所有AGV發送路口解鎖信息，確保所有AGV均收到路口解鎖信息。

如圖2(c)所示由于即將進入的路徑段無剩余容量，AGV#1會較長時間占用交叉路口，這導致AGV#4較長時間被阻塞，降低了系統的運行效率，因此當AGV進入交叉路口時除了檢測此路口是否被占用以外，還需檢測即將進入的路徑段是否有剩余容量。路徑段eij的剩余容量R(eij)定義如下：

式中：I(eij)表示已經處于路徑段eij上的AGV數量， C(eij)表示路徑段eij所能容納AGV的數目，定義如下：

式中：Round()表示向下取整函數；Wij為路徑段eij的長度；L為AGV長度，D為AGV之間的最小安全距離。

4 仿真驗證

為了驗證所提死鎖搜索與避免算法，針對某實際應用設計了仿真實驗，如圖1所示為某汽車公司淋雨測試車間，此車間有兩種車型，共有4條生產線，每種車型兩條生產線，每個淋雨間可同時測試兩輛車。A型車只能在淋雨間1測試，測試時間為3min，B型車只能在淋雨間2測試，測試時間為5min，每種車的生產節拍與淋雨測試時間相同，系統中共有6輛AGV運行。仿真軟件采用西門子公司的Plant Simulation 9.0，AGV和導引路徑分別使用Transporter和Track對象表示，AGVS所涉及的各種控制算法均可以通過在Method對象中編制SimTalk仿真語言實現。對應的仿真界面如圖3所示，根據生產節拍實時產生搬運任務。

圖3 淋雨車間仿真界面

仿真結果表明：6輛AGV有序運行，不會發生相互碰撞的情況，證明了本文所提自主路徑規劃及交通管理方法的有效性。同時也證明了基于單向路徑網絡的AGV自主路徑規劃方法切實可行。

5 結論

本文針對基于單向導引路徑網絡的AGVS提出了一種自主路徑規劃與交通管理方法，各AGV根據電子地圖負責自身的路徑規劃，針對AGV運行過程中可能出現的幾種沖突，提出了對應的避碰策略，最后結合一AGVS在某汽車淋雨測試測試車間的應用，通過仿真實驗證明這種交通管理策略可以保證AGVS無碰撞運行。

[1]肖海寧,樓佩煌,錢曉明,等.一種柔性作業車間中單向導引路徑網絡設計方法[J].機械工程學報,2013,49(3):122-129.

[2]肖海寧,樓佩煌,武星,等.基于混合遺傳算法的單向路徑網絡設計方法[J].計算機集成制造系統,2012,18(5):1031-1037.

[3]肖海寧,樓佩煌,滿增光,等.自動導引車系統實時多屬性任務調度方法[J].計算機集成制造系統,2012,18(10):2224-2230.

[4]賀麗娜,樓佩煌,錢曉明,等.基于時間窗的自動導引車無碰撞路徑規劃[J].計算機集成制造系統,2010,16(12):2630-2634.

[5]喬巖,錢曉明,樓佩煌.基于改進時間窗的AGVS避碰路徑規劃[J].計算機集成制造系統,2012,18(12):2683-2688.

[6]Vis I F A.Survey of research in the design and control of automated guided vehicle systems [J]. European Journal of Operational Research,2006,170(3):677-709.

[7]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-23.

[8]龔劬.圖論與網絡最優化算法[M].重慶:重慶大學出版社,2009.

[9]Dijkstra E W.An appraisal of some shortest path algorithms.Operations Research,1959,17:395-412.

Self path planning and traffi c management method for unidirectional guided-path based automated guided vehicle system

GUO Da-hong

以基于單向導引路徑網絡的自動導引車系統為研究對象，提出了一種AGV自主路徑規劃與交通管理方法。各AGV采用Dijkstra算法實現基于全局地圖的最優路徑規劃；提出了一種交通管理方法,針對AGVS在運行過程中的出現的幾種沖突，提出了對應的避碰策略。以含有6臺自動導引車的淋雨線車間為應用案例進行仿真實驗，仿真結果證明了所提方法的有效性。

自動導引車系統；路徑規劃；交通管理

郭大宏（1969 -），男，高級工程師，研究方向為高效柔性物流自動化裝備系統和柔性制造系統。

TP27

A

1009-0134(2013)06(上)-0098-03

10.3969/j.issn.1009-0134.2013.06(上).29

2013-04-03