李 鑫，廖凱文，陳 薇，張曉慶

(合肥工業(yè)大學 電氣與自動化工程學院，安徽 合肥 230009)

0 引言

隨著電商、快遞和新能源等新興產(chǎn)業(yè)的高速發(fā)展，大幅帶動了倉儲自動導引小車(Automated Guided Vehicle, AGV)的全面需求，為智能倉儲系統(tǒng)的研發(fā)與應用注入了全新的活力。對于任務規(guī)?；?、貨架密集型的倉儲作業(yè)環(huán)境，路徑規(guī)劃算法對提升智能倉儲系統(tǒng)整體性能、降低各方面運營成本和提高企業(yè)利潤等都起到了關鍵的作用，而如何解決AGV之間的路徑?jīng)_突，一直是多AGV路徑規(guī)劃的關鍵問題之一[1]。

路徑?jīng)_突指同一時段多臺AGV在行駛過程中，路線出現(xiàn)交叉或重疊的現(xiàn)象，主要分為路口沖突、追趕沖突和相向沖突[2]。路徑?jīng)_突處理不當會出現(xiàn)AGV碰撞或死鎖，嚴重影響多AGV系統(tǒng)的工作效率。一般而言，解決AGV路徑?jīng)_突的方法分為兩類：

(1)全局規(guī)劃方法 即靜態(tài)路徑規(guī)劃，該方法應能夠用數(shù)學規(guī)劃為AGV在地圖中提前規(guī)劃好無沖突路徑[3-4]。雖然如此，但是由于AGV運行在一個高度動態(tài)的環(huán)境中，并不總能在規(guī)劃的時間到達指定的位置，隨著AGV數(shù)量的增加，必將出現(xiàn)路徑?jīng)_突。

(2)局部規(guī)劃方法 該類方法的AGV在行駛過程中根據(jù)系統(tǒng)實時狀態(tài)確定其行駛路徑，因此也稱動態(tài)規(guī)劃策略。例如，文獻[5-10]為了避免AGV的路徑?jīng)_突和死鎖，根據(jù)路網(wǎng)的實時狀態(tài)動態(tài)調(diào)整AGV的路徑；于赫年等[11]提出多步前瞻算法來避免沖突，AGV每行駛一步都根據(jù)系統(tǒng)的實時狀態(tài)規(guī)劃接下來前K步的路徑。動態(tài)路徑規(guī)劃能夠及時應對AGV之間的碰撞沖突，但無法得到全局最優(yōu)路徑。

綜合考慮上述兩種方法的優(yōu)缺點，很多學者提出兩階段路徑規(guī)劃策略，即離線階段采用全局路徑規(guī)劃，在線階段根據(jù)沖突類型進行局部調(diào)整。例如，王佳溶等[12]和泰應鵬等[13]采用基于時間窗的兩階段控制算法，第一階段為各AGV規(guī)劃全局最優(yōu)路徑，第二階段計算各AGV的節(jié)點時間窗，根據(jù)時間窗重疊情況偵測路徑?jīng)_突，并通過更換路徑和等待的策略來解決沖突；為進一步減輕動態(tài)階段規(guī)劃的負擔，賀麗娜等和[14]和喬巖等[15]在離線階段將Dijkstra算法和時間窗原理相結(jié)合，順序規(guī)劃各個AGV的無碰撞路徑，該方法大大降低了動態(tài)階段出現(xiàn)沖突的幾率，從而簡化在線階段復雜的路徑調(diào)整過程。上述兩階段路徑規(guī)劃策略在解決沖突時，均未綜合考慮等待和路徑更換兩種方法的代價，因此規(guī)劃出來的不一定是最優(yōu)路徑。

為了在保證路徑無沖突的基礎上規(guī)劃出用時更少的路徑，本文提出一種基于時空沖突約束的A*算法。該方法將沖突檢測與規(guī)避融入節(jié)點搜索過程中來實現(xiàn)無沖突的路徑規(guī)劃，并通過綜合評價規(guī)避后的子節(jié)點代價找出用時最少的路徑。多AGV路徑規(guī)劃過程即利用改進后的A*算法，按照優(yōu)先級順序為各個AGV規(guī)劃路徑，規(guī)劃完成一條路徑時，用mark表記錄其在時空地圖中的節(jié)點信息，再利用改進后的A*算法結(jié)合mark表搜索新路徑。

1 多AGV路徑規(guī)劃時空地圖模型

本文基于倉儲物流的應用背景進行研究。因為在倉儲物流中需要將貨物運輸?shù)街付ǖ攸c，所以在環(huán)境中需要通過設置與位置信息相互關聯(lián)的節(jié)點來為AGV指明裝載點或卸載點；同時，在進行多AGV路徑規(guī)劃時需要計算各個節(jié)點準確的占用時間，采用柵格表征節(jié)點的大小比較合適。鑒于此，本文在柵格地圖的基礎上進行拓撲建模，將關鍵柵格拓撲為路徑節(jié)點，普通柵格拓撲為維持連接性的邊，構(gòu)建拓撲柵格地圖，如圖1所示。

拓撲柵格地圖模型可以采用二維矩陣記錄每個節(jié)點的狀態(tài)，但是無法記錄每個節(jié)點的具體占用時間，而多AGV路徑規(guī)劃時，需要綜合考慮各節(jié)點的具體占用時間來規(guī)劃最優(yōu)路徑，因此本文在拓撲柵格地圖的基礎上增加時間軸來建立時空地圖模型，如圖1b所示。拓撲柵格地圖中的路徑節(jié)點s(x,y)對應時空坐標系中的節(jié)點s(x,y,tin,tout)，其中：x,y坐標表征路徑節(jié)點的空間信息；tin，tout分別為進入和離開該節(jié)點的時刻。Δt為AGV移動一個節(jié)點柵格所需的時間，

(1)

式中：LC為車身長度；L為一個柵格的長度；v為AGV速度。ΔT為AGV移動兩相鄰節(jié)點所需的時間，

(2)

式中n為相鄰節(jié)點的柵格數(shù)。通過時空柵格法建立工作環(huán)境模型后，利用二維元胞數(shù)組mark記錄各節(jié)點的占用時間段集合，其中節(jié)點(x,y)的占用時間段集合

(3)

(4)

式中i為占用節(jié)點的AGV編號。同時，基于本文的應用場景，提出如下規(guī)定：

(1)每個柵格同一時刻只允許一輛AGV占用，且AGV在邊上均可雙向行駛。

(2)每輛AGV一次只能完成一個任務，接到調(diào)度指令時不能中途返回，且AGV保持勻速行駛。

(3)任意兩個相鄰節(jié)點間的路徑均可容納AGV車身，不存在一輛AGV同時占用兩條路徑的情況。

2 基于時空沖突約束的A*算法

2.1 基于時空沖突約束的子節(jié)點擴展

傳統(tǒng)的A*算法在拓撲柵格地圖采用四子節(jié)點擴展方法，如圖2a所示；本文針對時空地圖的特點，設計新的子節(jié)點擴展方式，如圖2b所示。其中P1，P2，P3，P4表示以父節(jié)點P0為中心擴展的4個子節(jié)點，其實質(zhì)是拓撲柵格地圖上擴展的4個子節(jié)點在時空地圖上的位置。在多AGV路徑規(guī)劃過程中會因多個AGV競爭同一節(jié)點、路段而導致沖突、死鎖等問題。多AGV的碰撞沖突分為節(jié)點沖突(如圖3a)、相向沖突(如圖3b)和追擊沖突，本文假定AGV的行駛速度不變，因此不考慮多個速度不同的AGV在行駛中造成的追擊沖突。

為了在解決路徑?jīng)_突時能夠綜合考慮路徑更換和等待的時間代價，本文將沖突檢測與規(guī)避策略融入節(jié)點搜索過程，并結(jié)合mark表中的節(jié)點占用時間信息來約束子節(jié)點擴展，具體步驟如下：

步驟1在時空地圖中通過父節(jié)點P0擴展4個子節(jié)點P1，P2，P3，P4。

步驟2根據(jù)4個子節(jié)點的x，y坐標得到對應節(jié)點已占用的時間段集合mark{x,y}，結(jié)合x，y坐標以及已占用的時間信息獲得時空地圖中已占用的節(jié)點。

步驟4判斷是否潛在相向沖突。若該節(jié)點在時空地圖中與已占用的時空節(jié)點不存在重疊，則檢測是否存在相向沖突。如圖4b所示，時空地圖中父節(jié)點P0和其中一子節(jié)點P1形成的路徑與其他AGV運行路徑存在交叉，若擴展該節(jié)點，則可能與其他AGV存在相向沖突，因此P1不作為此次P0擴展的對象。

2.2 基于時空地圖改進的節(jié)點估價函數(shù)

傳統(tǒng)A*算法的估價函數(shù)

f(z)=g(z)+h(z)。

(5)

式中：g(z)為起始節(jié)點Ps到當前節(jié)點Px的實際代價；h(z)為當前節(jié)點Px到目標節(jié)點Pg的啟發(fā)函數(shù)。傳統(tǒng)柵格地圖中，啟發(fā)式函數(shù)多采用當前節(jié)點到目標節(jié)點的曼哈頓距離h(z)，

h(z)=|Px_x-Pg_x|+|Px_y-Pg_y|。

(6)

式中：Px_x，Px_y分別為當前節(jié)點Px的x，y坐標;Pg_x，Pg_y分別為目標點Pg的x，y坐標。

傳統(tǒng)A*算法在出現(xiàn)距離相同的路徑時會隨機選取一條路徑，不考慮路徑的平滑度，然而選擇平滑度高的路徑能夠降低控制難度。因此，本文在A*算法的實際代價值中加入拐點懲罰因子，并針對時空地圖的特點，將實際代價值設定為實際用時g′(z)，即

(7)

式中：Ps_tout，Px_tout分別為離開起始節(jié)點和當前節(jié)點的時刻；tα為拐點懲罰因子；m為到當前節(jié)點時總的拐點次數(shù)。將啟發(fā)函數(shù)設定為曼哈頓距離對應的時間花費h′(z)，

h′(z)=h(z)Δt。

(8)

綜上所述，基于時空柵格的節(jié)點估價函數(shù)

f′(z)=g′(z)+h′(z)。

(9)

2.3 基于時空沖突約束A*算法的流程

A*算法的規(guī)劃過程主要通過開集C和閉集O兩個節(jié)點元素集合，以及相關節(jié)點的擴展與評價得到最終結(jié)果。表1所示為傳統(tǒng)柵格地圖的A*算法和本文所提算法具體流程的對比。

表1 兩種算法主要流程的對比

3 基于時空沖突約束A*算法的多AGV路徑 規(guī)劃

3.1 多AGV靜態(tài)路徑規(guī)劃過程

假設某一時刻有K輛小車需要規(guī)劃路徑，每個小車已經(jīng)分配好任務，即給出起止點和優(yōu)先級，按照優(yōu)先級的順序依次為各AGV規(guī)劃路徑。首先，在時空地圖中為優(yōu)先級最高的AGV規(guī)劃最短路徑；然后，根據(jù)優(yōu)先級最高AGV的時間空間信息，為次優(yōu)先級AGV規(guī)劃出與最高優(yōu)先級AGV無碰撞最短路徑。重復上述過程，直到規(guī)劃完所有AGV，具體步驟如下：

步驟1初始化路徑表PATH={0}和節(jié)點占用時間記錄表mark{X,Y}={0}。

步驟2將K個任務分配給K輛AGV，根據(jù)AGV所承載任務的優(yōu)先級，從高到低對K輛AGV進行排序AGV(1)>AGV(2)>…AGV(k)…>AGV(K)，初始化預規(guī)劃的AGV編號k=1

步驟3判斷是否k≤K，是則執(zhí)行步驟4，否則轉(zhuǎn)步驟5。

步驟4利用基于時空沖突約束的A*算法結(jié)合mark表對AGV(k)進行路徑規(guī)劃，將所得路徑節(jié)點存入PATH，并用路徑節(jié)點坐標更新mark表，令k+1，轉(zhuǎn)步驟3。

步驟5將規(guī)劃好的路徑表PATH中的節(jié)點信息分別發(fā)送給各對應的AGV，判斷是否有新的任務請求，有則轉(zhuǎn)步驟2，否則繼續(xù)等待新的任務請求。

3.2 多AGV動態(tài)路徑調(diào)整過程

在實際運行過程中，由于環(huán)境不穩(wěn)定，會出現(xiàn)很多突發(fā)情況，例如避障傳感器檢測到前方移動障礙物而自動停車、斷電停車等，導致AGV不能準確按照預先規(guī)劃的時間到達和離開相應的節(jié)點，若未及時調(diào)整AGV的路徑和運行時間，則會出現(xiàn)大量沖突而造成死鎖。針對這種情況，本文設計一種動態(tài)路徑調(diào)整策略，該策略包括兩部分：

(1)mark表的更新。上位機調(diào)度系統(tǒng)根據(jù)AGV的實時狀態(tài)更新mark表：①若調(diào)度系統(tǒng)發(fā)現(xiàn)有AGV斷電停車，則將mark表中該柵格的占用時間置為無窮大；②調(diào)度系統(tǒng)根據(jù)AGV電機編碼器信息獲取其實時位置，對比mark表中的時間信息，若發(fā)現(xiàn)有延遲，則根據(jù)當前位置計算得到新的后續(xù)節(jié)點時間，更新mark表。

(2)若AGV在行駛過程中檢測到即將進入的柵格被占用時，則以當前節(jié)點和時間作為起始節(jié)點信息，結(jié)合mark表規(guī)劃出一條新的路徑，并將新的路徑信息發(fā)送給上位機調(diào)度系統(tǒng)。

3.3 多AGV路徑規(guī)劃算法評價指標

所有AGV到達終點的用時能夠反映路徑規(guī)劃算法的優(yōu)劣，故系統(tǒng)評價指標為

(10)

式中：T為所有AGV到達目標點的總體用時；n為AGV的數(shù)量；ti為第i號AGV到達目標點的時間，

ti=gi_tout-si_tin。

(11)

式中：i為AGV的編號；gi_tout為AGV到達目標點的時刻；si_tin為第i輛AGV從起始節(jié)點出發(fā)的時刻。

4 實驗仿真

4.1 仿真平臺

本文選用MATLAB 2015作為仿真工具，在仿真平臺下開發(fā)圖形用戶界面(Graphical User Inter face, GUI)用于設置地圖環(huán)境，并顯示各AGV的路徑規(guī)劃結(jié)果，仿真界面如圖5所示。為驗證本文算法能夠在保證無沖突、無死鎖的情況下規(guī)劃出總體用時較小的路徑，設計了3個算例，3個算例中均設定柵格的每條邊長L=2.4 m、AGV的速度v=0.5 m/s、AGV車身長LC=0.6 m，各算例目的如下：算例1驗證基于時空沖突約束A*算法中估價函數(shù)的拐點懲罰因子能夠使規(guī)劃的路徑更加平滑；算例2驗證本文算法中的動態(tài)調(diào)整機制能夠有效避免因AGV出現(xiàn)時間延遲和斷電停車造成路徑擁堵而導致的死鎖問題；算例3驗證基于時空沖突約束A*算法能夠綜合考慮等待和更換路徑兩種策略用時，獲得總體用時較傳統(tǒng)兩階段算法更小的路徑。

4.2 算例仿真及結(jié)果分析

4.2.1 算例1

在一個橫向通道數(shù)和縱向通道數(shù)均為30的柵格地圖中，分別采用加入拐點懲罰因子和未加入拐點懲罰因子的時空沖突約束A*算法對20，40，60，80，100輛AGV進行路徑規(guī)劃，起點和終點任意設置，出發(fā)時刻設為[0,12 s]之間的隨機數(shù)。兩種方法規(guī)劃得到路徑的總拐點數(shù)和總用時分別如圖6和圖7所示。

圖6和圖7所示分別為不同數(shù)目AGV時，采用基于時空沖突約束A*算法和未加入拐點懲罰因子的時空沖突約束A*算法的路徑總拐點、總用時。由圖6可知，基于時空沖突約束A*算法因為在估價函數(shù)中加入了拐點懲罰因子，所以使系統(tǒng)規(guī)劃出的路徑拐點更少。由圖7可見，加入拐點懲罰因子后規(guī)劃出的路徑總用時基本無變化，進一步說明基于沖突約束A*算法中加入拐點懲罰因子能夠使系統(tǒng)規(guī)劃出更優(yōu)的路徑，而且隨著AGV數(shù)量的增加，這種優(yōu)勢更加明顯。

4.2.2 算例2

算例1中的仿真結(jié)果表明，基于時空沖突約束A*算法中加入的拐點懲罰因子能在一定程度上減小時間花費，下面通過兩個算例驗證本文算法能夠通過動態(tài)調(diào)整，在一定程度上避免道路擁堵導致的死鎖。

(1)當AGVi按照預規(guī)劃的路徑行駛時，設置AGVi原規(guī)劃路徑上有一輛AGV出現(xiàn)時間延遲并造成擁堵，經(jīng)過本文算法動態(tài)調(diào)整得到的結(jié)果如圖8所示。圖中兩個大正方形分別表示AGVi的起、止節(jié)點，箭頭所指為AGVi，白色小方塊表示其他AGV，虛線為AGVi預規(guī)劃的路徑，實線為AGVi調(diào)整后的路線。AGVi行駛到箭頭所指位置時檢測到下一步要進入的柵格被占用，則以當前位置和時間為起始點，結(jié)合更新后的mark表進行路徑規(guī)劃。根據(jù)mark表中記錄的信息，綜合考慮等待和更換路徑代價后，發(fā)現(xiàn)更換路徑更節(jié)約時間，因此舍棄了等待的方式，在一定程度上避免了等待所導致的道路擁堵和死鎖。

(2)當AGVi按照預規(guī)劃好的路徑行駛時，在其預規(guī)劃好的路徑上設置一輛AGV斷電停車，得到的結(jié)果如圖9所示。圖中兩個大正方形分別表示AGVi的起、止節(jié)點，箭頭所指為AGVi，白色小方塊表示斷電停駛的AGV，虛線表示AGVi預規(guī)劃的路徑，實線表示AGVi調(diào)整后的路線。從圖中結(jié)果可知，AGVi行駛到箭頭所指位置時，接收到系統(tǒng)中存在其他AGV斷電停車的告警，立即結(jié)合更新后的mark表規(guī)劃出一條新的路徑，避免了無限等待導致的死鎖。

4.2.3 算例3

在一個橫向通道數(shù)和縱向通道數(shù)均為30的柵格地圖中，分別采用傳統(tǒng)兩階段法和基于時空沖突約束A*算法對20，40，60，80，100輛AGV進行路徑規(guī)劃，起點和終點任意設置，出發(fā)時刻設為[0,12 s]之間的隨機數(shù)。兩種方法規(guī)劃得到路徑的總等待時間、總用時分別如圖10和圖11所示。

圖10和圖11所示分別為不同數(shù)量AGV時，采用傳統(tǒng)兩階段控制策略算法和基于時空沖突約束A*算法規(guī)劃得到的路徑總等待時間和總用時。從圖10可見，基于時空沖突約束A*算法因路徑擁堵造成的等待時間較傳統(tǒng)兩階段控制策略算法大大降低。由圖11可見，基于沖突約束A*算法在避免沖突時，能夠綜合考慮等待和更換路徑的時間代價，規(guī)劃出總用時較傳統(tǒng)兩階段控制策略算法更少的路徑，而且隨著AGV數(shù)量的增加，該方法的優(yōu)勢更加明顯。

5 結(jié)束語

本文針對多AGV路徑規(guī)劃問題，提出一種基于時空沖突約束A*算法的多AGV路徑規(guī)劃方法。該算法通過將沖突約束條件加入路徑搜索過程來避免AGV之間的節(jié)點沖突和路徑?jīng)_突，從而規(guī)劃出無沖突路徑；同時，在路徑搜索過程中加入等待子節(jié)點，通過綜合考慮更換路徑和等待用時來規(guī)劃耗時最少的路徑。最后，通過實驗驗證了所提算法能夠在保證所有AGV所行路徑無沖突、無死鎖的情況下，獲得耗時最少的路徑。