高新浩 陳曉華 王占山

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

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

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

1 引言

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

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

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

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

2.1 離線規(guī)劃

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

對該拓撲地圖做如下定義：

（1）地圖為有向圖，AGV在地圖中可雙向運動；

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

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

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

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

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

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

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

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

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

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

（1）

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

（2）

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

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

2.2 在線規(guī)劃

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

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

（3）

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

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

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

（4）

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

（5）

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

（6）

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

3 實驗驗證

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

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

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

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

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

4 結(jié)論

針對多AGV動態(tài)交通調(diào)度中出現(xiàn)的沖突和死鎖問題，提出了一種改進的基于時間窗的兩階段動態(tài)路徑規(guī)劃算法。該算法通過構(gòu)建離線環(huán)境拓撲地圖，結(jié)合A*算法實現(xiàn)離線路徑規(guī)劃，在AGV任務(wù)執(zhí)行過程構(gòu)建動態(tài)信息反饋機制，利用動態(tài)環(huán)境拓撲地圖，通過BP神經(jīng)網(wǎng)絡(luò)實現(xiàn)動態(tài)路徑調(diào)度規(guī)劃，減少沖突和死鎖問題的發(fā)生。改變發(fā)生故障的AGV在節(jié)點的優(yōu)先級減少AGV的沖突死鎖，經(jīng)仿真實驗驗證，該算法實時性好，可有效解決沖突和死鎖問題，但是隨著AGV任務(wù)隊列的增大，該算法存在計算延遲現(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]徐勝華，宋樹祥，佘果.一種掃地機器人路徑規(guī)劃的改進算法[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ōu)化技術(shù)研究[D].南京：南京航空航天大學(xué)，2011.

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

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

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

[10]王薇，魏世民，楊月巧，姜運芳，李端玲.基于神經(jīng)網(wǎng)絡(luò)的移動機器人路徑規(guī)劃[J].北京工業(yè)大學(xué)學(xué)報，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]項宏峰，曹少中，徐長波，李新佩.基于神經(jīng)網(wǎng)絡(luò)的AGV智能車路徑規(guī)劃的仿真研究[J].北京印刷學(xué)院學(xué)報，2017，25（07）：128-130.

蘇州市科技項目（編號：SYG201654）

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