自動(dòng)化立體倉(cāng)庫(kù)中智能AGV群體的靜態(tài)路徑規(guī)劃與動(dòng)態(tài)避障決策研究

房殿軍，周 濤

（同濟(jì)大學(xué) 中德學(xué)院，上海 201804）

自動(dòng)化立體倉(cāng)庫(kù)中智能AGV群體的靜態(tài)路徑規(guī)劃與動(dòng)態(tài)避障決策研究

房殿軍，周 濤

（同濟(jì)大學(xué) 中德學(xué)院，上海 201804）

針對(duì)自動(dòng)化立體倉(cāng)庫(kù)出入庫(kù)搬運(yùn)作業(yè)區(qū)域自動(dòng)化水平低的現(xiàn)狀，結(jié)合智能物流的發(fā)展趨勢(shì)，闡述以智能AGV群體替代叉車作業(yè)進(jìn)行托盤搬運(yùn)的工作模式，并對(duì)其靜態(tài)路徑規(guī)劃與動(dòng)態(tài)避障決策進(jìn)行了研究。以此工作模式下的AGV為特定對(duì)象，在A-star算法的基礎(chǔ)上考慮了時(shí)間因子的影響，進(jìn)行了路徑規(guī)劃的算法設(shè)計(jì)；同時(shí)根據(jù)柵格圖下AGV碰撞的路徑特點(diǎn)，系統(tǒng)地闡述了AGV群體的碰撞類型及避障策略，并對(duì)智能AGV群體的路徑規(guī)劃、動(dòng)態(tài)避障和路徑再規(guī)劃進(jìn)行了算例分析。

智能AGV群體；路徑規(guī)劃；碰撞類型；動(dòng)態(tài)避障

1 引言

近年來，電子商務(wù)發(fā)展非常迅速。相對(duì)于傳統(tǒng)零售行業(yè)，電子商務(wù)企業(yè)的物流作業(yè)不僅工作量巨大，還對(duì)時(shí)效性和準(zhǔn)確性提出了非常嚴(yán)苛的要求。與此同時(shí)，傳感器技術(shù)、RFID技術(shù)、嵌入式系統(tǒng)技術(shù)等物聯(lián)網(wǎng)技術(shù)的發(fā)展，為智能物流提供了強(qiáng)有力的支撐。智能化物流系統(tǒng)是解決目前電商物流問題切實(shí)可行的方案，也是未來的發(fā)展趨勢(shì)。

自動(dòng)化立體倉(cāng)庫(kù)（AS/RS）作為智能物流倉(cāng)儲(chǔ)系統(tǒng)的核心組成部分，被廣泛應(yīng)用于各行各業(yè)。自動(dòng)化立體倉(cāng)庫(kù)的巷道堆垛機(jī)與立體貨架可高效且準(zhǔn)確地實(shí)現(xiàn)托盤在貨架上的存取?？墒窃谧詣?dòng)化立體倉(cāng)庫(kù)的出入庫(kù)搬運(yùn)作業(yè)區(qū)域中，往往需要人駕駛叉車進(jìn)行托盤的搬運(yùn)。這不僅影響了整個(gè)物流倉(cāng)儲(chǔ)系統(tǒng)的自動(dòng)化程度，也易導(dǎo)致錯(cuò)誤作業(yè)甚至無效作業(yè)，降低物流系統(tǒng)整體的效率。

隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展，AGV作為柔性單元，可替代人工操作叉車進(jìn)行托盤搬運(yùn)工作，從而使得整個(gè)倉(cāng)儲(chǔ)系統(tǒng)自動(dòng)、智能的運(yùn)轉(zhuǎn)，并可通過AGV數(shù)量的增減及時(shí)響應(yīng)作業(yè)量的波動(dòng)?；谖锫?lián)網(wǎng)技術(shù)的自動(dòng)化立體倉(cāng)庫(kù)示意圖如圖1所示，在出入庫(kù)區(qū)域，使用多個(gè)AGV進(jìn)行托盤搬運(yùn)作業(yè)。

圖1 基于物聯(lián)網(wǎng)技術(shù)的立體倉(cāng)庫(kù)示意圖[1]

區(qū)別于傳統(tǒng)的多AGV系統(tǒng)，智能AGV群體更強(qiáng)調(diào)“智能群體”的理念?！爸悄堋币馕吨篈GV可通過傳感器獲取環(huán)境信息，通過RFID技術(shù)與其他設(shè)備（其他AGV、堆垛機(jī)、位置標(biāo)簽等）進(jìn)行信息交互，最后AGV自身通過數(shù)據(jù)運(yùn)算做出路徑和避障等決策。群體則代表著：系統(tǒng)中每輛AGV都是平等獨(dú)立的個(gè)體，每輛AGV分別進(jìn)行運(yùn)算，分別對(duì)自身的運(yùn)動(dòng)進(jìn)行決策，而不依托于其他AGV或中央控制器的指令。在物聯(lián)網(wǎng)技術(shù)的支持下，智能AGV群體進(jìn)行搬運(yùn)工作是未來的趨勢(shì)。

傳統(tǒng)的AGV系統(tǒng)大多通過上層的中央控制器進(jìn)行多AGV的調(diào)度，如：基于時(shí)間窗的多AGV路徑規(guī)劃[2]，通過蟻群算法求多AGV系統(tǒng)總路徑的全局最優(yōu)解[3]，基于有向圖的AGV路徑規(guī)劃和系統(tǒng)任務(wù)調(diào)度的AGV管理系統(tǒng)[4]。此種多AGV調(diào)度系統(tǒng)在路徑規(guī)劃時(shí)直接考慮了避障，綜合已知的任務(wù)序列，規(guī)劃所有AGV的路徑，可得整個(gè)系統(tǒng)的最優(yōu)解?？墒沁@種模式比較適用于小型的AGV系統(tǒng)，如果AGV數(shù)量不斷增多，那么中央控制器的計(jì)算量將成指數(shù)增長(zhǎng)，運(yùn)算耗時(shí)長(zhǎng)，導(dǎo)致AGV的實(shí)時(shí)規(guī)劃和避障難以實(shí)現(xiàn)。近年來隨著智能物流的發(fā)展，眾多學(xué)者紛紛將目光從集中式控制AGV系統(tǒng)轉(zhuǎn)向分布式AGV系統(tǒng)，如：?jiǎn)诬囀褂酶倪M(jìn)的Dijkstra算法規(guī)劃路徑，基于沖突協(xié)商策略實(shí)現(xiàn)多AGV自主控制[5]。分布式AGV系統(tǒng)將冗雜的集中式計(jì)算轉(zhuǎn)化為各個(gè)AGV的分布式計(jì)算，響應(yīng)速度快，具有更高的柔性和魯棒性，更適用于大型電商等訂單多且難預(yù)測(cè)的情況。

在目前分布式AGV系統(tǒng)的研究中，大多以路徑長(zhǎng)度作為評(píng)判指標(biāo)進(jìn)行路徑規(guī)劃，未考慮AGV轉(zhuǎn)向時(shí)間以及轉(zhuǎn)向前后加減速階段時(shí)間因素的影響。而在實(shí)際應(yīng)用中，AGV在兩點(diǎn)間選取不同的路徑所需要的轉(zhuǎn)向及加減速次數(shù)是不一樣的。而頻繁的轉(zhuǎn)向與加減速，不僅僅影響了AGV的作業(yè)時(shí)間，同時(shí)增加了AGV系統(tǒng)運(yùn)作的能耗。而且，復(fù)雜動(dòng)作對(duì)于AGV的機(jī)構(gòu)也會(huì)造成一定的損耗，導(dǎo)致AGV后期的維護(hù)保養(yǎng)成本增高。因此在實(shí)際應(yīng)用中，距離最短的路徑并不是最優(yōu)的，而是需綜合轉(zhuǎn)向次數(shù)，考慮時(shí)間因素的影響，進(jìn)行路徑規(guī)劃和避障決策。

本文針對(duì)實(shí)際自動(dòng)化立體倉(cāng)庫(kù)的運(yùn)作情況，基于時(shí)間因子來設(shè)計(jì)立體倉(cāng)庫(kù)中出入庫(kù)搬運(yùn)區(qū)域的AGV路徑規(guī)劃算法，同時(shí)針對(duì)此對(duì)象，定義AGV群體的動(dòng)態(tài)避障決策機(jī)制，框架如圖2所示。

圖2 本文框架圖

以最短運(yùn)行時(shí)間作為評(píng)判指標(biāo)，設(shè)計(jì)AGV路徑全局規(guī)劃算法，實(shí)現(xiàn)路徑的靜態(tài)規(guī)劃與再規(guī)劃。在AGV運(yùn)動(dòng)過程中，通過碰撞類型判定、優(yōu)先級(jí)排序以及避障策略選取來決策AGV群體的動(dòng)態(tài)避障，并在避障的基礎(chǔ)上進(jìn)行路徑再規(guī)劃。針對(duì)時(shí)間因子的影響，本文系統(tǒng)地闡述了此對(duì)象中AGV群體的碰撞類型和避障策略，并進(jìn)行了算例驗(yàn)證。

2 問題描述

本文所考慮的是自動(dòng)化立體倉(cāng)庫(kù)出入庫(kù)托盤搬運(yùn)作業(yè)區(qū)域AGV群體運(yùn)動(dòng)規(guī)則的問題。某立體倉(cāng)庫(kù)作業(yè)區(qū)域?yàn)榫匦?，長(zhǎng)22.5m，寬15m，作業(yè)對(duì)象為標(biāo)準(zhǔn)化托盤，作業(yè)主體為AGV。故而，本文采用柵格圖法搭建地圖模型。

常用托盤尺寸為：1.1m×1.1m，0.8m×1.2m，1m×1.2m。不同生產(chǎn)廠商AGV外觀尺寸各不相同，且AGV外觀尺寸的會(huì)根據(jù)額定載荷變化，額定載荷越高，尺寸就會(huì)設(shè)計(jì)得越大。通常長(zhǎng)為0.9m-1.3m，寬為0.6m-1.0m，高為0.2m-0.4m。綜合考慮運(yùn)行時(shí)的干涉以及作業(yè)區(qū)域的空間利用率，設(shè)定柵格尺寸為1.5m×1.5m，柵格尺寸略大于AGV與托盤尺寸。

圖3 某倉(cāng)庫(kù)托盤搬運(yùn)區(qū)域柵格圖

圖3為某立體倉(cāng)庫(kù)托盤搬運(yùn)作業(yè)區(qū)域的柵格地圖模型。粗實(shí)線為自動(dòng)立體倉(cāng)庫(kù)各區(qū)域邊界以及柵格邊界，每個(gè)柵格中心點(diǎn)為AGV小車在柵格內(nèi)的位置點(diǎn)，也是整個(gè)電子地圖的坐標(biāo)點(diǎn)，細(xì)實(shí)線為各中心點(diǎn)的連線，也即是AGV的實(shí)際行走路徑。左下角第一個(gè)柵格坐標(biāo)定為（0,0），整個(gè)地圖坐標(biāo)從（0,0）到（14,9）。

倉(cāng)庫(kù)共設(shè)5扇門，門寬3m左右，門外停放車裝卸貨物。立體貨架共設(shè)5條巷道，對(duì)應(yīng)圖2中橫坐標(biāo)1，4，7，10，13的位置。在柵格和立體貨架連接處，巷道兩側(cè)分別設(shè)有出入庫(kù)工作臺(tái)，以便堆垛機(jī)存取托盤。結(jié)合上述特點(diǎn)設(shè)定搬運(yùn)任務(wù)起點(diǎn)與搬運(yùn)任務(wù)終點(diǎn)（如圖3所示）。門側(cè)任務(wù)起點(diǎn)連接卡車卸貨區(qū)，任務(wù)終點(diǎn)連接卡車裝貨區(qū)；貨架側(cè)的任務(wù)起點(diǎn)連接貨架出庫(kù)臺(tái)，任務(wù)終點(diǎn)連接貨架入庫(kù)臺(tái)。AGV小車在立體貨架和倉(cāng)庫(kù)門間雙向行駛完成出入庫(kù)搬運(yùn)作業(yè)。本文將從靜態(tài)路徑規(guī)劃以及動(dòng)態(tài)避障兩個(gè)角度展開，邏輯流程如圖4所示。

圖4 邏輯流程圖

根據(jù)現(xiàn)有主流物流設(shè)備的額定參數(shù)，結(jié)合本文研究對(duì)象的特點(diǎn)，考慮到模型的可實(shí)現(xiàn)性與現(xiàn)實(shí)意義，現(xiàn)對(duì)本文模型作如下假設(shè)。

（1）AGV小車具有4個(gè)可移動(dòng)方向，只能在不為對(duì)角的兩相鄰柵格間移動(dòng)；

（2）為了簡(jiǎn)化模型，將AGV加減速時(shí)間進(jìn)行折算，小車在相鄰柵格間的移動(dòng)時(shí)間需1s；

（3）考慮AGV的轉(zhuǎn)向影響，設(shè)置AGV小車轉(zhuǎn)向方式為原地自旋，且轉(zhuǎn)向需要固定時(shí)間為1s；

（4）鑒于目前的電池技術(shù)，AGV小車?yán)m(xù)航可達(dá)24h，故在本文中不考慮充電問題；

（5）障礙檢測(cè)頻率為1次/s；

（6）障礙檢測(cè)半徑為6m；

（7）AGV小車抬起和放下托盤的工作時(shí)間為1s；

（8）安全距離為1.5m。當(dāng)AGV小車檢測(cè)到與另外小車距離（兩AGV中心點(diǎn)的距離）小于1.5m（一個(gè)柵格）時(shí)，此AGV急停1s。

3 基于時(shí)間因子的AGV靜態(tài)路徑規(guī)劃

AGV路徑規(guī)劃問題是典型的車輛路徑問題（Vehicle Routing Problem，VRP）。VRP問題一般可定義為：對(duì)于一系列裝貨點(diǎn)和（或）卸貨點(diǎn)，組織合適的行車線路，使載貨車輛有序地通過節(jié)點(diǎn)，在滿足一定的約束條件（如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量限制、行駛里程限制、時(shí)間限制等）下，達(dá)到一定的目標(biāo)（如路程最短、費(fèi)時(shí)最少、時(shí)間盡量少、使用車輛數(shù)量盡量少等）[6]。在常規(guī)柵格圖路徑靜態(tài)規(guī)劃中，通常假設(shè)AGV速度恒定，將路程最短與時(shí)間最短劃等號(hào)，忽略了AGV轉(zhuǎn)向與加減速所導(dǎo)致的時(shí)間影響。本文基于時(shí)間因子進(jìn)行AGV靜態(tài)路徑規(guī)劃，實(shí)現(xiàn)了路徑規(guī)劃目標(biāo)由最短路徑向最短時(shí)間的轉(zhuǎn)變。

3.1 基于時(shí)間因子的A-star算法設(shè)計(jì)

3.1.1 A-star算法流程。當(dāng)AGV接收到一個(gè)任務(wù)，則此次任務(wù)的初始結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)已給定，屬于啟發(fā)式搜索的解決范疇[7]?；跂鸥竦貓D的啟發(fā)式搜索算法中，A-star算法具有計(jì)算量小、搜索空間小等特征。它在搜索下一節(jié)點(diǎn)時(shí)，只搜索其相鄰的柵格，而不是盲目搜索。

A-star算法的代價(jià)函數(shù)為：

G表示從初始結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的代價(jià)，H表示當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的代價(jià)估值。F則為總移動(dòng)代價(jià)。每次都選F值最小的結(jié)點(diǎn)進(jìn)行搜索，就可以得到一條到終點(diǎn)消耗最少的路徑。

在A-star算法中還有兩個(gè)很重要的概念：開放列表（open list）和關(guān)閉列表（close list）。列表中存放著路徑結(jié)點(diǎn)組成的數(shù)組。開放列表記錄了路徑規(guī)劃過程中待搜索結(jié)點(diǎn)列表，即可能要走的區(qū)域；關(guān)閉列表記錄了不需再次搜索的結(jié)點(diǎn)列表，即不會(huì)再考慮的區(qū)域，算法具體流程如圖5所示。

圖5 A-star算法流程圖

步驟1：將初始結(jié)點(diǎn)記錄為當(dāng)前搜索點(diǎn)P；

步驟2：將當(dāng)前點(diǎn)P放入關(guān)閉列表；

步驟3：搜索點(diǎn)P所有相鄰結(jié)點(diǎn)，假如某結(jié)點(diǎn)沒有在兩列表里，則計(jì)算出該結(jié)點(diǎn)的F值，并設(shè)其父節(jié)點(diǎn)為P，然后將其放入開放列表；

步驟4：判斷開放列表是否已經(jīng)為空，若是，則說明在達(dá)到目標(biāo)結(jié)點(diǎn)前已經(jīng)找完了所有可能的路徑結(jié)點(diǎn)，路徑規(guī)劃失敗，算法結(jié)束；否則繼續(xù)；

步驟5：從開放列表取出任意一個(gè)F值最小的結(jié)點(diǎn)，將該結(jié)點(diǎn)設(shè)為當(dāng)前結(jié)點(diǎn)P，返回步驟3；

步驟6：當(dāng)目標(biāo)結(jié)點(diǎn)進(jìn)入開放列表，算法結(jié)束。

此時(shí)由目標(biāo)結(jié)點(diǎn)開始逐級(jí)追溯父結(jié)點(diǎn)，直至初始結(jié)點(diǎn)，此時(shí)各結(jié)點(diǎn)相連即為路徑。

3.1.2 基于時(shí)間因子的算法設(shè)計(jì)。A-star算法是種啟發(fā)式搜索算法，那么代價(jià)函數(shù)中G與H的準(zhǔn)確性決定了路徑規(guī)劃結(jié)果的有效性。很顯然通常選取的距離評(píng)判指標(biāo)（曼哈頓距離和歐式距離）都不適用于本文的研究對(duì)象。考慮到AGV的轉(zhuǎn)彎時(shí)間以及行駛距離與行駛時(shí)間的關(guān)系。設(shè)定行駛最短時(shí)間為路徑規(guī)劃的評(píng)判指標(biāo)，并基于時(shí)間因子進(jìn)行算法設(shè)計(jì)。

設(shè)初始結(jié)點(diǎn)為(x1,y1)，AGV在初始結(jié)點(diǎn)方向?yàn)?a1,b1)，當(dāng)前結(jié)點(diǎn)坐標(biāo)為(x2,y2)，當(dāng)前結(jié)點(diǎn)相對(duì)于父結(jié)點(diǎn)方向?yàn)?a2,b2)，目標(biāo)結(jié)點(diǎn)為(x3,y3)，則：

|x2-x1|+|y2-y1|和|x3-x2|+|y3-y2|，分別為當(dāng)前結(jié)點(diǎn)與初始結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)曼哈頓距離。

i與k變量是判別x軸方向是否需要轉(zhuǎn)向，代表轉(zhuǎn)向所需的時(shí)間。

j與l變量是判別y軸方向是否需要轉(zhuǎn)向，代表轉(zhuǎn)向所需的時(shí)間。

m與n變量則是為了補(bǔ)償直線行走的估值誤差。

因?yàn)橐肓藭r(shí)間因子，在搜索計(jì)算F值時(shí)需要當(dāng)前結(jié)點(diǎn)相對(duì)于父結(jié)點(diǎn)方向。在不同搜索路徑的情況下，當(dāng)前結(jié)點(diǎn)F值會(huì)因不同的父結(jié)點(diǎn)而不同。針對(duì)本文基于時(shí)間因子的A-star算法，在搜索時(shí)不但需要搜索不在關(guān)閉列表與開放列表的結(jié)點(diǎn)，同時(shí)也需要搜索當(dāng)前結(jié)點(diǎn)周圍開放列表內(nèi)的結(jié)點(diǎn)，再次計(jì)算總代價(jià)值F，并更新開放列表?；跁r(shí)間因子的A-star算法流程圖如圖6所示。

圖6 基于時(shí)間因子的A-star算法流程

3.2 靜態(tài)路徑規(guī)劃算例分析

給定初始結(jié)點(diǎn)、初始方向和目標(biāo)節(jié)點(diǎn)進(jìn)行規(guī)劃，是靜態(tài)路徑規(guī)劃問題最理想的情況，此種情況搜索范圍最小，路徑規(guī)劃速度最快。然而在實(shí)際的生產(chǎn)實(shí)踐中，作業(yè)區(qū)域可能會(huì)有很多物理約束，比如在地圖中某些區(qū)域會(huì)放置固定設(shè)備，AGV在行駛過程中突然死機(jī)等情況。在A-star算法中，考慮實(shí)際物理約束時(shí)，只需要將約束點(diǎn)在路徑規(guī)劃階段放入關(guān)閉列表，那么在規(guī)劃時(shí)，就不再考慮通過約束結(jié)點(diǎn)的路徑，從而達(dá)到避開靜態(tài)障礙物的目的。在動(dòng)態(tài)避障后的路徑再規(guī)劃階段，只需要將碰撞結(jié)點(diǎn)放入關(guān)閉列表，即可在AGV運(yùn)行過程中，有效地實(shí)現(xiàn)路徑再規(guī)劃。

現(xiàn)分別針對(duì)無靜態(tài)物理約束和有靜態(tài)物理約束這兩種情況，進(jìn)行基于時(shí)間因子的A-star算法的算例分析。算例1對(duì)應(yīng)無物理約束的情況，已知初始結(jié)點(diǎn)(2,0)，初始方向(1,0)，目標(biāo)結(jié)點(diǎn)(11,9),路徑規(guī)劃結(jié)果如圖7。這是一個(gè)比較理想的情況，在計(jì)算過程中，代價(jià)估值最小值唯一，所以關(guān)閉列表中所有結(jié)點(diǎn)構(gòu)成了最優(yōu)路徑，沒有進(jìn)行多余的運(yùn)算。

圖7 路徑規(guī)劃算例1

算例2和算例3計(jì)算的是有靜態(tài)物理約束的情況。算例2在算例1的基礎(chǔ)上引入靜態(tài)障礙物(11,8)，路徑規(guī)劃結(jié)果如圖8。算例3在算例2的基礎(chǔ)上引入靜態(tài)障礙物(10,9)，路徑規(guī)劃結(jié)果如圖9。有靜態(tài)約束時(shí)，關(guān)閉列表中搜索過的結(jié)點(diǎn)明顯增多，計(jì)算量增大，特別算例3這一極端情況中，目標(biāo)結(jié)點(diǎn)只有一個(gè)遠(yuǎn)離初始結(jié)點(diǎn)的可接近點(diǎn)時(shí)，算法搜索了整個(gè)地圖的大部分區(qū)域，不過最后算法仍然得出了最優(yōu)路徑。

圖8 路徑規(guī)劃算例2

圖9 路徑規(guī)劃算例3

算例分析表明此算法針對(duì)本文的特定對(duì)象，不僅能實(shí)現(xiàn)理想狀態(tài)下的路徑規(guī)劃，在引入靜態(tài)物理約束時(shí)，也可有效解決AGV靜態(tài)路徑全局規(guī)劃問題，從而可實(shí)現(xiàn)AGV的靜態(tài)路徑規(guī)劃以及動(dòng)態(tài)避障后的路徑再規(guī)劃。

4 AGV群體的動(dòng)態(tài)避障

4.1 障礙檢測(cè)和碰撞類型

如章節(jié)2中的模型假設(shè)，AGV在每個(gè)柵格間移動(dòng)時(shí)間為1s，在結(jié)點(diǎn)上轉(zhuǎn)向時(shí)間為1s，抬起和放下貨物時(shí)間為1s。AGV上傳感器檢測(cè)頻率為1次/s，檢測(cè)半徑為6m，即為4個(gè)柵格的尺寸大小。為了減少每輛小車的計(jì)算量，同時(shí)減少傳感器數(shù)量降低成本，我們?cè)贏GV上只放置一個(gè)傳感器，檢測(cè)AGV運(yùn)行方向前方的狀態(tài)，檢測(cè)結(jié)點(diǎn)如圖10所示。

圖10 檢測(cè)區(qū)域內(nèi)結(jié)點(diǎn)

在此區(qū)域內(nèi)，檢測(cè)到障礙物，最快也需2s后才會(huì)碰撞。設(shè)定小車在每個(gè)結(jié)點(diǎn)上進(jìn)行一次檢測(cè)，檢測(cè)到障礙物后，小車間進(jìn)行通信，交互自己當(dāng)前時(shí)刻以及未來2s的坐標(biāo)及方向，見表1，并在1s內(nèi)完成計(jì)算，決策AGV在下一時(shí)間點(diǎn)的動(dòng)作，完成動(dòng)態(tài)避障。

表1 不同時(shí)刻的AGV狀態(tài)

以A1為例，分別與其他車輛兩兩比較3個(gè)時(shí)間點(diǎn)坐標(biāo)。設(shè)兩車路徑重合點(diǎn)個(gè)數(shù)為參數(shù)c。

若c=0，路徑不相交，小車不經(jīng)過同一結(jié)點(diǎn)，不會(huì)發(fā)生碰撞。

若c=1，有且只有一個(gè)重合點(diǎn)，則比較經(jīng)過此路徑結(jié)點(diǎn)的時(shí)間。兩車經(jīng)過相同點(diǎn)時(shí)間集合分別為Ti=(ti1,…,tin)，Tj=(tj1,…,tjn)，設(shè)集合P,參數(shù)p，ti，tj，p'，ti'，tj'，tk，

因?yàn)锳GV本身尺寸問題，兩車不僅僅在相同時(shí)間點(diǎn)通過同一節(jié)點(diǎn)會(huì)發(fā)生碰撞，在相鄰時(shí)間點(diǎn)通過也會(huì)發(fā)生干涉。所以在碰撞判定時(shí)會(huì)有以下幾種情況。

（1）p=2，則兩車不碰撞。如圖11中a，b兩種情況；

（2）p=0，則ti=tj，在此時(shí)刻兩車發(fā)生碰撞，定義此種碰撞類型為定點(diǎn)碰撞，如圖11中c，d兩種情況；

（3）p=1，tk時(shí)刻兩車方向不相同，則發(fā)生碰撞，定義此種碰撞類型為阻斷碰撞，如圖11中f情況。

若c=2，有兩個(gè)重合點(diǎn)，則需判定兩車是否是跟隨狀態(tài)，此時(shí)有兩種情況。

（1）若tk時(shí)刻兩車的方向相同，則為跟隨狀態(tài)，不發(fā)生碰撞，如圖11中e情況。

（2）若tk時(shí)刻兩車方向不同，因有兩重合點(diǎn)，則兩AGV定相向行駛，軌跡有重疊部分，如圖11中g(shù)情況，必然發(fā)生碰撞。定義此種類型為特殊碰撞（非定點(diǎn)，非阻斷）。

圖11 碰撞判定

4.2 避障策略與優(yōu)先級(jí)

在本研究對(duì)象中，每個(gè)AGV都是單獨(dú)的個(gè)體，在同一時(shí)刻，分別會(huì)對(duì)檢測(cè)范圍內(nèi)的AGV進(jìn)行碰撞判定。在確定小車間會(huì)碰撞之后，每個(gè)小車只需判定碰撞類型，選取避障策略，同時(shí)根據(jù)優(yōu)先級(jí)對(duì)AGV在下一結(jié)點(diǎn)的動(dòng)作進(jìn)行決策，完成整個(gè)動(dòng)態(tài)避障過程。

4.2.1 避障策略選取。在AGV動(dòng)態(tài)避障中，有等待策略和路徑再規(guī)劃策略兩種方式。

（1）等待策略：優(yōu)先級(jí)低的等待，優(yōu)先級(jí)高按原路徑行走；

（2）路徑再規(guī)劃策略：優(yōu)先級(jí)低的重新規(guī)劃路徑，優(yōu)先級(jí)高的等待。

這兩種避障策略中，涉及三種動(dòng)作決策：原路徑行駛、等待、路徑再規(guī)劃。AGV在避障決策為路徑再規(guī)劃時(shí)，將原路徑的下個(gè)結(jié)點(diǎn)加入關(guān)閉列表，再次應(yīng)用基于時(shí)間因子的A-star算法，生成新的路徑。

AGV在結(jié)點(diǎn)等待只需花費(fèi)1s，而路徑再規(guī)劃，會(huì)至少額外增加1次轉(zhuǎn)向，至少需要1s。所以在避障策略選取時(shí)，優(yōu)先應(yīng)用等待策略。在避障策略選取時(shí)，我們將其分為4種情況。

（1）阻斷碰撞時(shí)，選取等待策略即可實(shí)現(xiàn)避障。

（2）定點(diǎn)碰撞時(shí)，如若為圖11中c情況，兩AGV非相向行駛，選取等待策略即可實(shí)現(xiàn)避障。

（3）定點(diǎn)碰撞時(shí)，如若為圖11中d情況，兩AGV相向行駛，則必須進(jìn)行路徑再規(guī)劃才可實(shí)現(xiàn)避障。

（4）特殊碰撞時(shí)，兩AGV相向行駛，選取路徑再規(guī)劃策略。

碰撞類型和避障策略關(guān)系見表2。

表2 碰撞類型與避障策略

4.2.2 優(yōu)先級(jí)比較。在避障策略中，需要基于優(yōu)先級(jí)，進(jìn)行碰撞AGV的動(dòng)作決策。所以在系統(tǒng)初始階段，人為地給系統(tǒng)內(nèi)所有AGV小車從高到低設(shè)定默認(rèn)優(yōu)先級(jí)就顯得尤為必要，其中默認(rèn)優(yōu)先級(jí)不存在平級(jí)?？墒窃趯?shí)際運(yùn)作中，如果僅僅根據(jù)默認(rèn)優(yōu)先級(jí)進(jìn)行判斷，會(huì)導(dǎo)致某些AGV小車長(zhǎng)期占用，而某些小車卻利用率低，同時(shí)簡(jiǎn)單地應(yīng)用默認(rèn)優(yōu)先級(jí)，容易出現(xiàn)AGV為了避障而繞路多花時(shí)間的情況，效率不高。為了提高資源利用率以及系統(tǒng)整體運(yùn)行效率，結(jié)合路徑特點(diǎn)，規(guī)定以下優(yōu)先級(jí)規(guī)則。

在阻斷碰撞的情況下，如圖11的f，如果A2優(yōu)先級(jí)低導(dǎo)致等待，則因?yàn)锳1觸發(fā)急停設(shè)定，導(dǎo)致兩AGV的無限等待，所以在阻斷碰撞時(shí)，比較公式5中ti和tj，先經(jīng)過相同點(diǎn)的AGV優(yōu)先級(jí)更高。

在非阻斷碰撞的情況下，如果從AGV所在結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路徑不需要轉(zhuǎn)向，那么在進(jìn)行路徑再規(guī)劃時(shí)，則需要多轉(zhuǎn)向3次，多走2個(gè)柵格，即多花5s，如圖12中a情況。而原路徑需要轉(zhuǎn)向時(shí)，只需要多花1s，如圖12中b情況。

所以在定點(diǎn)碰撞和特殊碰撞的情況下，考慮到研究對(duì)象特點(diǎn)，AGV從當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路徑不需要轉(zhuǎn)向時(shí)，此AGV優(yōu)先級(jí)更高。

設(shè)AGV當(dāng)前結(jié)點(diǎn)為(x1,y1)，當(dāng)前方向?yàn)?a1,b1)，目標(biāo)結(jié)點(diǎn)為(x2,y2)，當(dāng)(x2-x1,y2-y1)的單位向量與(a1,b1)相同時(shí)，此AGV至目標(biāo)結(jié)點(diǎn)的路徑不需轉(zhuǎn)向，如下式。

在優(yōu)先級(jí)判斷過程中，如若存在相同優(yōu)先級(jí)，則根據(jù)默認(rèn)優(yōu)先級(jí)進(jìn)行選取。

4.2.3 動(dòng)態(tài)避障決策流程。在避障策略與優(yōu)先級(jí)確認(rèn)的基礎(chǔ)上，AGV可以根據(jù)避障策略來決策AGV在下一路徑結(jié)點(diǎn)的動(dòng)作：等待、原路徑行駛或是路徑再規(guī)劃。在檢測(cè)區(qū)域內(nèi)有多輛AGV時(shí)，則分別與其他AGV進(jìn)行兩兩避障決策，最后進(jìn)行綜合避障決策。綜合避障決策規(guī)則為：路徑再規(guī)劃〉等待〉原路徑。即多個(gè)避障決策中如果有路徑再規(guī)劃，則總避障決策為路徑再規(guī)劃；如果沒有路徑再規(guī)劃，有等待，則總避障決策為等待；否則按照原路徑行駛。動(dòng)態(tài)避障決策流程如圖13所示。

圖12 路徑再規(guī)劃

圖13 動(dòng)態(tài)避障決策流程圖

步驟1：判定AGV碰撞類型；

步驟2：選取AGV避障策略；

步驟3：判定優(yōu)先級(jí)，決策AGV動(dòng)作，實(shí)現(xiàn)兩車間的動(dòng)態(tài)避障；

步驟4：分別與檢測(cè)區(qū)域內(nèi)所有AGV兩兩進(jìn)行步驟1至步驟3；

步驟5：進(jìn)行綜合避障決策。

4.3 動(dòng)態(tài)避障算例分析

在AGV群體中，能否避免和解決死鎖狀態(tài)，是整個(gè)系統(tǒng)魯棒性的標(biāo)志之一。同時(shí)在本文中，為了降低成本，減少計(jì)算量，只在AGV前方放置感應(yīng)器，在動(dòng)態(tài)避障中對(duì)于后方移動(dòng)物體并不做考慮。所以本文所提運(yùn)動(dòng)規(guī)則能否有效避免后車的追擊碰撞也是衡量本文運(yùn)動(dòng)規(guī)則是否有效的指標(biāo)之一。

為了驗(yàn)證智能AGV群體的運(yùn)動(dòng)規(guī)則是否有效，現(xiàn)對(duì)其進(jìn)行算例分析。算例中共有5輛AGV，初始路徑規(guī)劃如圖14所示。A1、A2、A3、A4的初始路徑會(huì)在結(jié)點(diǎn)(5,4)處產(chǎn)生死鎖，同時(shí)A2、A5為跟隨狀態(tài)。

圖14 初始狀態(tài)

設(shè)圖14的當(dāng)前時(shí)刻為0s。AGV群體運(yùn)行期間，通過避障以及路徑再規(guī)劃，至7s時(shí)，完全解開死鎖狀態(tài)，且全程未出現(xiàn)AGV互相干涉的現(xiàn)象。7s時(shí)系統(tǒng)狀態(tài)如圖15。

7s內(nèi)所有AGV的位置方向數(shù)據(jù)見表3。

算例表明，針對(duì)本文的特定對(duì)象，結(jié)合基于時(shí)間因子的AGV路徑規(guī)劃算法以及AGV群體動(dòng)態(tài)避障，可有效實(shí)現(xiàn)AGV群體在電子地圖內(nèi)的靜態(tài)路徑規(guī)劃、動(dòng)態(tài)避障以及避障后的路徑再規(guī)劃。

圖15 運(yùn)行7s后狀態(tài)

表3 AGV位置方向數(shù)據(jù)

5 結(jié)語(yǔ)

AGV群體的協(xié)作并行，是提高搬運(yùn)效率的重要手段之一。隨著物聯(lián)網(wǎng)和離散控制技術(shù)的發(fā)展，AGV群體運(yùn)作模式成為智能物流技術(shù)領(lǐng)域的一個(gè)重要研究方向，受到眾多企業(yè)和學(xué)者的關(guān)注和研究。本文結(jié)合靜態(tài)路徑規(guī)劃與再規(guī)劃、動(dòng)態(tài)避障兩部分研究?jī)?nèi)容，提出了一種針對(duì)自動(dòng)化立體倉(cāng)庫(kù)托盤出入庫(kù)搬運(yùn)區(qū)域的智能AGV群體的運(yùn)動(dòng)機(jī)制，并通過算例分析，驗(yàn)證了這種運(yùn)動(dòng)機(jī)制的有效性。

[1]Christian Prasse,Andreas Nettstraeter,Michael ten Hompel.How IOT will change the design and operation of logistics systems[C].Internet of Things(IOT)IEEE,2014：55-60．

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

[3]夏田,王娜.改進(jìn)蟻群算法在多AGV作業(yè)調(diào)度中的應(yīng)用[J].物流技術(shù),2015,(23)：87-89．

[4]馮海雙.AGV自動(dòng)運(yùn)輸系統(tǒng)調(diào)度及路徑規(guī)劃的研究[D].哈爾濱：哈爾濱工業(yè)大學(xué),2013．

[5]經(jīng)建峰.基于智能體的多AGV自主控制系統(tǒng)研發(fā)[D].南京：南京航空航天大學(xué),2014.

[6]李軍,郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法[M].北京：中國(guó)物資出版社,2001．

[7]歐陽(yáng)圣,胡望宇.幾種經(jīng)典搜索算法研究與應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2011,(5)：243-247．

Study on Decision-making in Static Route Planning and Dynamic Barrier Avoidance of Intelligent AGV Group in AS/RS

Fang Dianjun,Zhou Tao
(Chinesisch Deutsches Hochschulkolleg,Tongji University,Shanghai 201804,China)

In this paper,in light of the low automation level of the inbound and outbound handling operations of the AS/RS,and in connection with the development trend of the intelligent logistics industry,we elaborated on the working mode where the forklift truck was replaced by the intelligent AGV group to handle the pallet,and then studied the static route planning and dynamic barrier avoidance decision-making of the AGV group.Next,with the AGV under such working mode as the object,we considered the influence of the time factor on the basis of the A-star algorithm to design the route planning algorithm,next,according to the characteristics of the routing of the AGV on the grid map,presented systematically the collision type and barrier avoidance strategy of the AGV group,and at the end,had a numerical analysis of the route planning,dynamic barrier avoidance and route re-planning of the intelligent AGV group.

intelligent AGV group;route planning;collision type;dynamic barrier avoidance

F253;F253.9

A

1005-152X(2017)06-0170-09

10.3969/j.issn.1005-152X.2017.06.040

2017-04-25

房殿軍（1961-），男，山東人，博士，教授，主要研究方向：物流系統(tǒng)規(guī)劃、供應(yīng)鏈管理。