多AGV動(dòng)態(tài)交通調(diào)度算法設(shè)計(jì)

高新浩 陳曉華 王占山

摘 要：本文針對(duì)多AGV系統(tǒng)的動(dòng)態(tài)交通調(diào)度過程中容易出現(xiàn)的路徑規(guī)劃沖突和死鎖問題，設(shè)計(jì)基于時(shí)間窗的改進(jìn)兩階段動(dòng)態(tài)交通調(diào)度算法，搭建多AGV動(dòng)態(tài)交通調(diào)度系統(tǒng)。實(shí)現(xiàn)多AGV的最優(yōu)動(dòng)態(tài)交通調(diào)度，利用改進(jìn)后的動(dòng)態(tài)交通調(diào)度算法可降低路徑?jīng)_突和死鎖出現(xiàn)頻率30%以上，提高多AGV系統(tǒng)的運(yùn)行效率。

關(guān)鍵詞：多AGV；動(dòng)態(tài)調(diào)度；路徑規(guī)劃

DOI：10.16640/j.cnki.37-1222/t.2019.09.127

1 引言

多AGV動(dòng)態(tài)調(diào)度常常需要面對(duì)多任務(wù)分配、多路徑?jīng)_突問題及突發(fā)故障狀況的解決，要求調(diào)度算法的求解速度快、效率高，并能夠滿足實(shí)際生產(chǎn)過程中實(shí)時(shí)變化的多任務(wù)調(diào)度。常用地調(diào)度原則主要有：規(guī)劃路徑最短原則、等待時(shí)間最短原則、AGV工作隊(duì)列最優(yōu)原則等單一指標(biāo)調(diào)度原則，此外，還有基于多種調(diào)度指標(biāo)的復(fù)合指標(biāo)調(diào)度原則。

如何規(guī)劃出一條從起點(diǎn)到終點(diǎn)間暢通的最短路徑，避免規(guī)劃的路徑出現(xiàn)阻塞、沖突或死鎖現(xiàn)象，保證規(guī)劃的路徑為全局最優(yōu)的結(jié)果，實(shí)現(xiàn)最優(yōu)的系統(tǒng)運(yùn)行效果是國內(nèi)外眾多學(xué)者長期以來研究的熱點(diǎn)和難點(diǎn)。自Maxwell等[1]最早提出AGV的路徑規(guī)劃問題開始，國內(nèi)外眾多學(xué)者針對(duì)多AGV動(dòng)態(tài)調(diào)度問題進(jìn)行了長期的深入研究。早期Kazuo等[2]基于遺傳算法進(jìn)行了路徑規(guī)劃問題的分析。徐勝華等人[3] 針對(duì)掃地機(jī)器人的路徑規(guī)劃問題提出了一種改進(jìn)算法；Kim等人[4]采用conservative myopic策略來尋求無沖突的路徑， 但是該方法效率低、易發(fā)生阻塞、不適應(yīng)AGV較多的環(huán)境；Fanti [5]給出了一個(gè)將賦時(shí)著色Petri網(wǎng)（Coloured Timed Petri Net，CTPN）轉(zhuǎn)化為強(qiáng)連通Petri網(wǎng)（Petri Net，PN） 的方法，從而側(cè)重于X才碰撞和死鎖的預(yù)防入手，減少AGV的碰撞和死鎖，對(duì)于實(shí)時(shí)的情況卻顯得有些不足；賀麗娜[6]提出將時(shí)間窗原理和Dijkstra算法結(jié)合的方法來解決多AGV碰撞問題， 但是該方法未證明在數(shù)量較多的情況下的有效性；喬巖等人[7]提出了一種基于改進(jìn)時(shí)間窗的AGV避碰方法，該方法雖在一定程度上解決了實(shí)時(shí)性問題，但是只能應(yīng)用于雙向?qū)б窂剑粍鴹澋热薣8]針對(duì)多AGV交通故障問題提出了一種兩階段動(dòng)態(tài)路徑規(guī)劃策略，但是路徑復(fù)雜度的增大也會(huì)帶來實(shí)時(shí)性的問題；王佳溶等人[9]提出了一種改進(jìn)后的兩階段控制策略，但是策略只考慮速度調(diào)節(jié)沒有考慮優(yōu)先級(jí)問題，具有一定的局限性。因此需要一種不僅可以避免碰撞，而且實(shí)時(shí)性好，適用于AGV數(shù)量較多的情況的方法。

本文針對(duì)動(dòng)態(tài)交通規(guī)劃中的阻塞和死鎖現(xiàn)象，提出一種改進(jìn)的基于時(shí)間窗的兩階段動(dòng)態(tài)路徑規(guī)劃方法。該方法通過將時(shí)間窗原理和A*算法相結(jié)合，第一階段構(gòu)建基于時(shí)間窗的靜態(tài)環(huán)境拓?fù)涞貓D，根據(jù)任務(wù)隊(duì)列中各任務(wù)的優(yōu)先級(jí)開展離線規(guī)劃，并對(duì)各AGV規(guī)劃路徑進(jìn)行沖突檢驗(yàn)，對(duì)沖突的任務(wù)的優(yōu)先級(jí)進(jìn)行實(shí)時(shí)改變；第二階段構(gòu)建路徑實(shí)時(shí)反饋系統(tǒng)，將AGV實(shí)時(shí)運(yùn)行情況與環(huán)境拓?fù)涞貓D相結(jié)合，采用BP神經(jīng)網(wǎng)絡(luò)算法[10-12]構(gòu)建動(dòng)態(tài)環(huán)境拓?fù)涞貓D，實(shí)現(xiàn)對(duì)多AGV的動(dòng)態(tài)路徑規(guī)劃。

2 調(diào)度算法設(shè)計(jì)

2.1 離線規(guī)劃

為更好對(duì)調(diào)度規(guī)劃算法進(jìn)行說明，基于圖論構(gòu)建如圖1所示靜態(tài)環(huán)境拓?fù)涞貓D模型。

對(duì)該拓?fù)涞貓D做如下定義：

（1）地圖為有向圖，AGV在地圖中可雙向運(yùn)動(dòng)；

（2）表示地圖中路徑間節(jié)點(diǎn)集合，定義；

（3）表示地圖中連接節(jié)點(diǎn)的邊的集合，定義L，則有：

（4）地圖中每條邊的長度權(quán)值相同，均為2；

（5）地圖中設(shè)定3個(gè)倉儲(chǔ)點(diǎn)2、3、4作為初始節(jié)點(diǎn)；

（6）地圖中設(shè)定3個(gè)工位點(diǎn)19、21和23作為目標(biāo)點(diǎn)。

為減少AGV本身因素對(duì)規(guī)劃調(diào)度算法影響，做以下假定：

（1）設(shè)定AGV本身長度為1，邊的長度大于AGV本身長度，AGV通行每條邊的時(shí)間為2；

（2）AGV以恒定速度在地圖中運(yùn)行，不考慮AGV轉(zhuǎn)彎的速度變化；

（3）每條邊在同一時(shí)間段內(nèi)僅允許一輛AGV進(jìn)入。

在離線規(guī)劃調(diào)度算法設(shè)計(jì)中，首先對(duì)AGV分配的任務(wù)根據(jù)各自優(yōu)先級(jí)高低進(jìn)行排序并構(gòu)建任務(wù)隊(duì)列；基于時(shí)間窗原理，采用啟發(fā)式A*算法對(duì)任務(wù)隊(duì)列中的AGV路徑順序開展靜態(tài)最優(yōu)路徑搜索。以圖1中倉儲(chǔ)點(diǎn)2和4為初始節(jié)點(diǎn)，按照啟發(fā)函數(shù)對(duì)周圍節(jié)點(diǎn)進(jìn)行搜索，并選取其中最優(yōu)的一個(gè)節(jié)點(diǎn)進(jìn)行擴(kuò)展，經(jīng)過迭代計(jì)算搜索獲取目標(biāo)點(diǎn)，最后由目標(biāo)點(diǎn)回溯到起始節(jié)點(diǎn)形成全局的規(guī)劃軌跡。A*算法估計(jì)函數(shù)如公式（1）所示：

（1）

其中，表示估計(jì)函數(shù)，是AGV從起始點(diǎn)到目標(biāo)點(diǎn)的評(píng)價(jià)估計(jì)值；為代價(jià)函數(shù)，表示初始點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際估計(jì)值；h為啟發(fā)函數(shù)，表示當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的估計(jì)代價(jià)值。在搜索節(jié)點(diǎn)較少的情況下，h包含啟發(fā)信息越多，尋找全局最優(yōu)路徑的效果越好。與傳統(tǒng)A*算法的8鄰域或16鄰域搜索不同，由于環(huán)境拓?fù)涞貓D限定了AGV的運(yùn)動(dòng)路徑方向?yàn)?個(gè)，因此在算法設(shè)計(jì)中向上下左右四個(gè)方向鄰域進(jìn)行路徑搜索，同時(shí)啟發(fā)函數(shù)采用曼哈頓距離進(jìn)行計(jì)算，啟發(fā)函數(shù)如公式（2）所示：

（2）

其中，表示相鄰節(jié)點(diǎn)之間路徑的代價(jià)權(quán)值，表示當(dāng)前節(jié)點(diǎn)，表示目標(biāo)點(diǎn)。

基于啟發(fā)A*算法，設(shè)計(jì)離線規(guī)劃算法如圖2所示。首先根據(jù)離線拓?fù)涞貓D和任務(wù)隊(duì)列中任務(wù)內(nèi)容，利用A*算法進(jìn)行相關(guān)任務(wù)的路徑規(guī)劃，然后結(jié)合時(shí)間窗原理，對(duì)規(guī)劃路徑進(jìn)行時(shí)間段劃分，根據(jù)各規(guī)劃路徑的優(yōu)先級(jí)進(jìn)行占用時(shí)間分配統(tǒng)計(jì)，生成基于時(shí)間窗的任務(wù)執(zhí)行隊(duì)列。

2.2 在線規(guī)劃

AGV在線動(dòng)態(tài)調(diào)度規(guī)劃的主要目標(biāo)和分為兩個(gè)目標(biāo)：一是根據(jù)時(shí)間窗原理防止AGV之間出現(xiàn)路徑?jīng)_突和死鎖，二是調(diào)度路徑盡可能短。在完成離線規(guī)劃后，每個(gè)AGV規(guī)劃路徑中的相關(guān)節(jié)點(diǎn)序列被保存在任務(wù)執(zhí)行隊(duì)列中。在AGV運(yùn)動(dòng)過程中，通過對(duì)AGV在環(huán)境拓?fù)涞貓D中的位置及狀態(tài)進(jìn)行在線監(jiān)測，并采用BP神經(jīng)網(wǎng)絡(luò)描述運(yùn)行環(huán)境基于時(shí)間窗的位置約束，構(gòu)建AGV運(yùn)動(dòng)路徑的目標(biāo)能量函數(shù)和路徑長度能量函數(shù)，通過迭代計(jì)算能量函數(shù)對(duì)AGV的在線調(diào)度路徑進(jìn)行最優(yōu)化處理，最終使調(diào)度路徑的迭代趨向于最優(yōu)規(guī)劃路徑。在線規(guī)劃算法設(shè)計(jì)中選取雙隱層神經(jīng)網(wǎng)絡(luò)以獲取更好的迭代逼近和泛化能力。

AGV在線路徑規(guī)劃總能量函數(shù)如式（3）所示：

（3）

其中，表示目標(biāo)沖突能量函數(shù)，目標(biāo)能量函數(shù)越小表示出現(xiàn)路徑?jīng)_突和死鎖的概率越小；表示路徑長度能量函數(shù)，路徑長度能量函數(shù)越小，路徑長度越??；和分別為和的加權(quán)。通過每一次迭代極值點(diǎn)，利用總能量函數(shù)為動(dòng)態(tài)規(guī)劃路徑尋找最優(yōu)值，即可在避免路徑?jīng)_突和死鎖的同時(shí)引導(dǎo)AGV選擇最優(yōu)路徑，最終完成路徑規(guī)劃任務(wù)。

為獲取函數(shù)值，設(shè)計(jì)雙隱層神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)如圖3所示：

激發(fā)函數(shù)采用階躍函數(shù)可檢測AGV運(yùn)動(dòng)路徑在到時(shí)間窗內(nèi)是否與其他調(diào)度路徑存在沖突或死鎖，采用Sigmoid函數(shù)作為激發(fā)函數(shù)，即：

（4）

則通過雙隱層神經(jīng)網(wǎng)絡(luò)輸出值為0～1內(nèi)的連續(xù)變化值，該值反應(yīng)該時(shí)間窗內(nèi)該路徑段出現(xiàn)沖突或死鎖的概率程度，輸出數(shù)值越大則說明出現(xiàn)沖突或死鎖的概率越大。將目標(biāo)沖突能量函數(shù)定義為所有路徑的沖突概率之和。

（5）

路徑長度能量函數(shù)定義為起始點(diǎn)到當(dāng)前節(jié)點(diǎn)路徑長度值與當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)估計(jì)值之和。

（6）

式中，表示起始點(diǎn)與當(dāng)前節(jié)點(diǎn)路徑長度值，表示當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)估計(jì)值。

3 實(shí)驗(yàn)驗(yàn)證

采用C++設(shè)計(jì)開發(fā)AGV交通調(diào)度系統(tǒng)開展多AGV動(dòng)態(tài)交通調(diào)度仿真研究，交通調(diào)度系統(tǒng)設(shè)計(jì)架構(gòu)如圖4所示。

設(shè)定3輛AGV分別從倉儲(chǔ)點(diǎn)1（節(jié)點(diǎn)1）、倉儲(chǔ)點(diǎn)2（節(jié)點(diǎn)2）和倉儲(chǔ)點(diǎn)3（節(jié)點(diǎn)3）出發(fā)，分別到達(dá)工位3（節(jié)點(diǎn)23）、工位1（節(jié)點(diǎn)19）和工位2（節(jié)點(diǎn)21），在離線規(guī)劃階段，利用A*算法結(jié)合靜態(tài)環(huán)境拓?fù)涞貓D獲取三輛AGV路徑節(jié)點(diǎn)集合分別為{1，6，15，14，13，12，23}，{7，6，15，16，19}，{8，13，22，21}。各節(jié)點(diǎn)通行順序如圖5所示。

在AGV運(yùn)動(dòng)過程中，在AGV1離開倉儲(chǔ)1（節(jié)點(diǎn)1）后，增加AGV4從倉儲(chǔ)1（節(jié)點(diǎn)1）出發(fā)到工位2（節(jié)點(diǎn)21）的任務(wù)到任務(wù)隊(duì)列，節(jié)點(diǎn)6在AGV4出發(fā)第一段路徑將與AGV2的第二段路徑發(fā)生沖突，此時(shí)采用基于BP神經(jīng)網(wǎng)絡(luò)的在線調(diào)度算法進(jìn)行路徑的重新規(guī)劃優(yōu)化，優(yōu)化后的節(jié)點(diǎn)通行順序如圖6所示。

為更貼合實(shí)際生產(chǎn)調(diào)度狀況，在測試時(shí)隨機(jī)添加出發(fā)節(jié)點(diǎn)與目標(biāo)點(diǎn)不同的路徑規(guī)劃任務(wù)，針對(duì)現(xiàn)有的基于時(shí)間窗的路徑規(guī)劃算法與本文所改進(jìn)的算法進(jìn)行實(shí)際運(yùn)行時(shí)間對(duì)比，測試結(jié)果如表1所示。

通過實(shí)驗(yàn)數(shù)據(jù)對(duì)比，隨著AGV并發(fā)數(shù)數(shù)量的增長，在沖突出現(xiàn)次數(shù)、路徑運(yùn)行時(shí)間和規(guī)劃路徑長度三項(xiàng)數(shù)據(jù)上比較，改進(jìn)后的兩階段路徑規(guī)劃算法在各項(xiàng)數(shù)據(jù)指標(biāo)上都有較為明顯的提高。

4 結(jié)論

針對(duì)多AGV動(dòng)態(tài)交通調(diào)度中出現(xiàn)的沖突和死鎖問題，提出了一種改進(jìn)的基于時(shí)間窗的兩階段動(dòng)態(tài)路徑規(guī)劃算法。該算法通過構(gòu)建離線環(huán)境拓?fù)涞貓D，結(jié)合A*算法實(shí)現(xiàn)離線路徑規(guī)劃，在AGV任務(wù)執(zhí)行過程構(gòu)建動(dòng)態(tài)信息反饋機(jī)制，利用動(dòng)態(tài)環(huán)境拓?fù)涞貓D，通過BP神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)動(dòng)態(tài)路徑調(diào)度規(guī)劃，減少?zèng)_突和死鎖問題的發(fā)生。改變發(fā)生故障的AGV在節(jié)點(diǎn)的優(yōu)先級(jí)減少AGV的沖突死鎖，經(jīng)仿真實(shí)驗(yàn)驗(yàn)證，該算法實(shí)時(shí)性好，可有效解決沖突和死鎖問題，但是隨著AGV任務(wù)隊(duì)列的增大，該算法存在計(jì)算延遲現(xiàn)象，針對(duì)該算法的實(shí)時(shí)性問題，有待進(jìn)一步研究改進(jìn)。

參考文獻(xiàn)：

[1]Maxwell W L，Tanehoco J M A.Design and automatic guieded vehiele system[J].IEEE Tranctions，1982（14）：113-124.

[2]Kazuo S，John S.Genetic algorithms for adaptive motion planning of all autonomous mobile Robert[J].Problems IEEE transaction SMC，1997（18）：46-49.

[3]徐勝華，宋樹祥，佘果.一種掃地機(jī)器人路徑規(guī)劃的改進(jìn)算法[J].測控技術(shù)，2017，36（02）：120-123.

[4]Kim C W，Tanchoco J M A.Operational control of a bidirectional automated vehicle systems[J].Interational Jouanal of Production Research，1993，31（09）：2123-2138.

[5]Fanti M P.A deadlock avoidance strategy for AGV system modeled coloured Petri nets[C].Proceedings of the 6th International Workshop on Discrete Event Systems，2002.

[6]何麗娜.AGV系統(tǒng)運(yùn)行路徑優(yōu)化技術(shù)研究[D].南京：南京航空航天大學(xué)，2011.

[7]喬巖，錢曉明，樓佩煌.基于改進(jìn)時(shí)間窗的AGVs避碰路徑規(guī)劃[J].計(jì)算機(jī)集成制造系統(tǒng)，2012，18（12）：2683-2688.

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

[9]王佳溶，樓佩煌，王曉勇.基于改進(jìn)的兩階段控制策略的AGV路徑優(yōu)化調(diào)度研究[J]. 機(jī)械科學(xué)與技術(shù)，2008，27（09）：1211-1216.

[10]王薇，魏世民，楊月巧，姜運(yùn)芳，李端玲.基于神經(jīng)網(wǎng)絡(luò)的移動(dòng)機(jī)器人路徑規(guī)劃[J].北京工業(yè)大學(xué)學(xué)報(bào)，2010，36（09）：1287-1291.

[11]Path Planning of MultiAgent Systems in Unknown Environmentwith Neural Kernel Smoothing and Reinforcement Learning.David luviano cruz，Wen-Yu.Neurocomputing，2016.

[12]項(xiàng)宏峰，曹少中，徐長波，李新佩.基于神經(jīng)網(wǎng)絡(luò)的AGV智能車路徑規(guī)劃的仿真研究[J].北京印刷學(xué)院學(xué)報(bào)，2017，25（07）：128-130.

蘇州市科技項(xiàng)目（編號(hào)：SYG201654）

作者簡介：高新浩（1985-），男，河北石家莊人，博士，講師，主要從事機(jī)電控制方面研究。