高新浩 陳曉華 王占山
摘 要:本文針對(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ī)電控制方面研究。