房殿軍，周 濤

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

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

房殿軍，周 濤

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

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

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

1 引言

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

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

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

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

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

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

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

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

圖2 本文框架圖

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

2 問題描述

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

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

圖3 某倉庫托盤搬運區(qū)域柵格圖

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

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

圖4 邏輯流程圖

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

（1）AGV小車具有4個可移動方向，只能在不為對角的兩相鄰柵格間移動；

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

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

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

（5）障礙檢測頻率為1次/s；

（6）障礙檢測半徑為6m；

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

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

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

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

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

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

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

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

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

圖5 A-star算法流程圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 障礙檢測和碰撞類型

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

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

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

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

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

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

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

因為AGV本身尺寸問題，兩車不僅僅在相同時間點通過同一節(jié)點會發(fā)生碰撞，在相鄰時間點通過也會發(fā)生干涉。所以在碰撞判定時會有以下幾種情況。

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

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

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

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

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

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

圖11 碰撞判定

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

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

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

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

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

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

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

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

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

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

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

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

表2 碰撞類型與避障策略

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

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

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

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

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

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

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

圖12 路徑再規(guī)劃

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

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

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

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

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

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

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

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

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

圖14 初始狀態(tài)

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

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

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

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

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

5 結(jié)語

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

[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)時間窗的AGVs避障路徑規(guī)劃[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自動運輸系統(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].北京：中國物資出版社,2001．

[7]歐陽圣,胡望宇.幾種經(jīng)典搜索算法研究與應(yīng)用[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)鏈管理。