基于單向?qū)б窂骄W(wǎng)絡(luò)的AGVS自主路徑規(guī)劃及交通管理方法研究

郭大宏

（江蘇天奇物流系統(tǒng)工程股份有限公司，無(wú)錫 214187）

（江蘇天奇物流系統(tǒng)工程股份有限公司，無(wú)錫 214187）

基于單向?qū)б窂骄W(wǎng)絡(luò)的AGVS自主路徑規(guī)劃及交通管理方法研究

郭大宏

（江蘇天奇物流系統(tǒng)工程股份有限公司，無(wú)錫 214187）

（江蘇天奇物流系統(tǒng)工程股份有限公司，無(wú)錫 214187）

0 引言

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

圖1 基于單向?qū)б窂骄W(wǎng)絡(luò)的AGVS

實(shí)驗(yàn)證明此方法能夠保證AGVS無(wú)碰撞運(yùn)行。

1 問(wèn)題描述

AGVS由單向?qū)б窂骄W(wǎng)絡(luò)和若干輛AGV組成，某AGVS單向?qū)б窂骄W(wǎng)絡(luò)如圖1所示，路徑段上的方向表示AGV在當(dāng)前路徑段上允許的運(yùn)行方向，路徑段上的數(shù)字表示路徑段長(zhǎng)度。節(jié)點(diǎn)由路徑交叉點(diǎn)和工位點(diǎn)組成。所謂AGVS路徑規(guī)劃及交通管理問(wèn)題是指：當(dāng)AGV收到一搬運(yùn)任務(wù)需要規(guī)劃一條從自身當(dāng)前位置到達(dá)搬運(yùn)任務(wù)工位點(diǎn)的最優(yōu)路徑，同時(shí)還要避免與其他AGV或環(huán)境障礙發(fā)生碰撞。對(duì)于基于單向路徑網(wǎng)絡(luò)的AGVS而言，可能引起AGV之間發(fā)生碰撞的沖突如圖2所示。

圖2 AGV運(yùn)行過(guò)程中可能出現(xiàn)的三種沖突

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

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

2.1.1 圖論法

圖論通過(guò)由點(diǎn)和邊組成的圖形來(lái)描述具有某種二元關(guān)系的系統(tǒng)，并根據(jù)圖的性質(zhì)進(jìn)行分析，提供研究各種系統(tǒng)的巧妙方法[1]。在本文中，將各個(gè)裝卸點(diǎn)、充電站等看作圖中的點(diǎn)，連線表示兩個(gè)點(diǎn)之間相互聯(lián)通。可以用一個(gè)有序三元組G= (V,E,φ)表示一個(gè)圖，其中V={v1,v2,…,vn}是有窮非空集，表示的是點(diǎn)集；E=(e1,e2,…,en)也是有窮非空集，表示的是邊集；φ是從邊集E到點(diǎn)集V的有序或是無(wú)序的元素偶對(duì)的集合的映射，稱為關(guān)聯(lián)函數(shù)。

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

本文中采用帶有權(quán)值的有向圖，其中權(quán)值表示頂點(diǎn)間的實(shí)際距離，方向表示AGV行駛只能從起點(diǎn)到終點(diǎn)。

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

點(diǎn)和線是圖的基本元素，本文中將點(diǎn)和線組合作為路徑段，以路徑段作為電子地圖的基本單元。本文將路徑段的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)成如表1所示。

表1 路徑段數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)中的各個(gè)數(shù)據(jù)的含義如表2所示。

表2 數(shù)據(jù)含義

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

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

2.2 路徑規(guī)劃方法

采用Dijkstra算法來(lái)求解這個(gè)問(wèn)題, Dijkstra算法的基本思想是生長(zhǎng)一顆以0v為根的最短路徑樹(shù)，在樹(shù)上的每一個(gè)頂點(diǎn)與根之間的路徑皆為最短路徑[10]。由于網(wǎng)絡(luò)中不存在負(fù)權(quán)，最短路徑樹(shù)的生長(zhǎng)過(guò)程中每個(gè)頂點(diǎn)將按照距0v的遠(yuǎn)近以及頂點(diǎn)的相鄰關(guān)系，逐次長(zhǎng)入樹(shù)中，先近后遠(yuǎn)，直至所有頂點(diǎn)都已在樹(shù)中。

3 基于單向?qū)б窂骄W(wǎng)絡(luò)的AGVS交通管理方法研究

對(duì)于基于單向路徑網(wǎng)絡(luò)的AGVS而言，可能引起AGV之間發(fā)生碰撞的沖突如圖2所示。各種沖突處理方法如下：

如圖2(a)所示沖突屬于趕超沖突。在一條路徑上有兩輛AGV同向行駛，后面的AGV行駛速度大于前面的AGV行駛速度產(chǎn)生這樣的沖突?？赏ㄟ^(guò)在AGV前方安裝必要的避碰傳感器，車載控制器利用避碰傳感器反饋回來(lái)的信號(hào)來(lái)判斷與前方車輛的距離，當(dāng)車輛之間的距離過(guò)近，則AGV立即減速直至停車，避免兩車相撞。

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

如圖2(c)所示由于即將進(jìn)入的路徑段無(wú)剩余容量，AGV#1會(huì)較長(zhǎng)時(shí)間占用交叉路口，這導(dǎo)致AGV#4較長(zhǎng)時(shí)間被阻塞，降低了系統(tǒng)的運(yùn)行效率，因此當(dāng)AGV進(jìn)入交叉路口時(shí)除了檢測(cè)此路口是否被占用以外，還需檢測(cè)即將進(jìn)入的路徑段是否有剩余容量。路徑段eij的剩余容量R(eij)定義如下：

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

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

4 仿真驗(yàn)證

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

圖3 淋雨車間仿真界面

仿真結(jié)果表明：6輛AGV有序運(yùn)行，不會(huì)發(fā)生相互碰撞的情況，證明了本文所提自主路徑規(guī)劃及交通管理方法的有效性。同時(shí)也證明了基于單向路徑網(wǎng)絡(luò)的AGV自主路徑規(guī)劃方法切實(shí)可行。

5 結(jié)論

本文針對(duì)基于單向?qū)б窂骄W(wǎng)絡(luò)的AGVS提出了一種自主路徑規(guī)劃與交通管理方法，各AGV根據(jù)電子地圖負(fù)責(zé)自身的路徑規(guī)劃，針對(duì)AGV運(yùn)行過(guò)程中可能出現(xiàn)的幾種沖突，提出了對(duì)應(yīng)的避碰策略，最后結(jié)合一AGVS在某汽車淋雨測(cè)試測(cè)試車間的應(yīng)用，通過(guò)仿真實(shí)驗(yàn)證明這種交通管理策略可以保證AGVS無(wú)碰撞運(yùn)行。

[1]肖海寧,樓佩煌,錢曉明,等.一種柔性作業(yè)車間中單向?qū)б窂骄W(wǎng)絡(luò)設(shè)計(jì)方法[J].機(jī)械工程學(xué)報(bào),2013,49(3):122-129.

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

[3]肖海寧,樓佩煌,滿增光,等.自動(dòng)導(dǎo)引車系統(tǒng)實(shí)時(shí)多屬性任務(wù)調(diào)度方法[J].計(jì)算機(jī)集成制造系統(tǒng),2012,18(10):2224-2230.

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

[5]喬巖,錢曉明,樓佩煌.基于改進(jìn)時(shí)間窗的AGVS避碰路徑規(guī)劃[J].計(jì)算機(jī)集成制造系統(tǒng),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]龔劬.圖論與網(wǎng)絡(luò)最優(yōu)化算法[M].重慶:重慶大學(xué)出版社,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

以基于單向?qū)б窂骄W(wǎng)絡(luò)的自動(dòng)導(dǎo)引車系統(tǒng)為研究對(duì)象，提出了一種AGV自主路徑規(guī)劃與交通管理方法。各AGV采用Dijkstra算法實(shí)現(xiàn)基于全局地圖的最優(yōu)路徑規(guī)劃；提出了一種交通管理方法,針對(duì)AGVS在運(yùn)行過(guò)程中的出現(xiàn)的幾種沖突，提出了對(duì)應(yīng)的避碰策略。以含有6臺(tái)自動(dòng)導(dǎo)引車的淋雨線車間為應(yīng)用案例進(jìn)行仿真實(shí)驗(yàn)，仿真結(jié)果證明了所提方法的有效性。

自動(dòng)導(dǎo)引車系統(tǒng)；路徑規(guī)劃；交通管理

郭大宏（1969 -），男，高級(jí)工程師，研究方向?yàn)楦咝嵝晕锪髯詣?dòng)化裝備系統(tǒng)和柔性制造系統(tǒng)。

TP27

A

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

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

2013-04-03