倉儲(chǔ)式多AGV系統(tǒng)的路徑規(guī)劃研究及仿真

于赫年，白 樺，李 超

1.哈爾濱工業(yè)大學(xué) 機(jī)電工程學(xué)院，哈爾濱150001

2.蕪湖哈特機(jī)器人產(chǎn)業(yè)技術(shù)研究院有限公司 前瞻技術(shù)研究中心，安徽 蕪湖241000

1 引言

隨著電商、快遞和新能源等新興產(chǎn)業(yè)的高速發(fā)展，大幅帶動(dòng)了倉儲(chǔ)AGV 的全面需求，為智能倉儲(chǔ)系統(tǒng)的研發(fā)與應(yīng)用注入了全新活力。加之制造業(yè)、商貿(mào)流通等領(lǐng)域的持續(xù)促進(jìn)，智能倉儲(chǔ)系統(tǒng)的發(fā)展具備更廣闊的市場前景。對(duì)于任務(wù)規(guī)?；?、貨架密集型的倉儲(chǔ)作業(yè)環(huán)境而言，路徑規(guī)劃算法對(duì)于提升智能倉儲(chǔ)系統(tǒng)整體性能、降低各方面運(yùn)營成本和提高企業(yè)利潤等方面都起到了關(guān)鍵作用。

路徑規(guī)劃問題屬于NPH問題[1]，這類問題的大型應(yīng)用通常只能利用有效的近似算法求解。路徑規(guī)劃算法作為當(dāng)今移動(dòng)機(jī)器人領(lǐng)域的一大研究熱點(diǎn)[2]，主要可劃分為基于采樣的和完備的兩大類算法，基于采樣的算法包括RRT[3]等算法，通常計(jì)算速度較快，被廣泛應(yīng)用于高維規(guī)劃問題，但可行解的代價(jià)比完備算法高，也會(huì)存在有解求不出的問題；完備的算法的規(guī)劃通常在已構(gòu)建的網(wǎng)絡(luò)圖上進(jìn)行，高維規(guī)劃時(shí)代價(jià)較大，但在低維尺度上幾乎無影響，尤其適用于預(yù)先構(gòu)建了二維地圖的倉儲(chǔ)物流系統(tǒng)。已被證明比較有效的算法包括Dijkstra 算法、A*算法、蟻群算法等[4-7]，但這些算法對(duì)全局信息要求嚴(yán)格，動(dòng)態(tài)適應(yīng)性差，無法滿足多AGV動(dòng)態(tài)路徑規(guī)劃作業(yè)需求。

因此，Desaulniers G 等人[8]在貪心算法基礎(chǔ)上進(jìn)行改進(jìn)，實(shí)現(xiàn)少量AGV的路徑規(guī)劃，但無法解決擁堵問題而非最優(yōu)，Boada B L等人[9]通過動(dòng)態(tài)調(diào)節(jié)AGV優(yōu)先級(jí)的方式優(yōu)化路徑，Dakulovic M等人[10]提出一種雙向D*算法，Guemane R 等人[11]對(duì)A*算法進(jìn)行改進(jìn)并提出Lazy A*算法，諸如遺傳算法[12]等智能算法的改進(jìn)也被提出。然而這些算法很少考慮動(dòng)態(tài)環(huán)境下的實(shí)時(shí)響應(yīng)和交通擁堵問題。

近年來的研究多集中在將路徑規(guī)劃算法與空間布置結(jié)合，來避免交通擁堵和死鎖等問題。Digani V 等人[13]提出了一種基于兩層控制架構(gòu)的自動(dòng)算法集成方法，巷道間布置多條方向不同通路，Yuan R等人[14]結(jié)合擁堵程度及交管規(guī)則對(duì)A*算法進(jìn)行改進(jìn)，同一巷道設(shè)置兩條方向相同單行通道，Mark B[15]研究了不同通行方式對(duì)系統(tǒng)效率的影響。這些研究多以犧牲倉儲(chǔ)空間、降低空間利用率或增加繞行的方式去解決擁堵問題。

為了不犧牲空間利用率，有研究者也提出增加時(shí)間維的算法，其中Bogdan S 等人[16]提出一種基于時(shí)間窗的智能AGV 動(dòng)態(tài)路徑規(guī)劃算法；泰應(yīng)鵬等人[17]也結(jié)合A*算法，增加時(shí)間窗對(duì)路徑規(guī)劃方法進(jìn)行了改進(jìn)，增加了實(shí)時(shí)避障功能?；跁r(shí)間窗的算法一定程度上保證路徑相對(duì)最優(yōu)，但算法實(shí)現(xiàn)復(fù)雜，對(duì)系統(tǒng)時(shí)序要求嚴(yán)格，延遲難以確定[18]，路徑易受系統(tǒng)擾動(dòng)批量失效，無法滿足復(fù)雜系統(tǒng)要求。

路徑規(guī)劃算法要保證多AGV系統(tǒng)發(fā)揮全部工作能力，實(shí)現(xiàn)有序、規(guī)范和準(zhǔn)確作業(yè)，以期最短時(shí)間內(nèi)高效完成全部作業(yè)。為了實(shí)現(xiàn)這種目標(biāo)，本文首先利用現(xiàn)有優(yōu)秀靜態(tài)算法對(duì)該領(lǐng)域存在的一些現(xiàn)有問題進(jìn)行改進(jìn)，以滿足多AGV 動(dòng)態(tài)作業(yè)需求，并以此作為分析的對(duì)比參照，提出一種具有多步前瞻性的增量式路徑規(guī)劃算法，通過主動(dòng)性的迭代擬合方法，提早獲取路況信息，避開擁堵路段，減少發(fā)生沖突的可能，實(shí)現(xiàn)實(shí)時(shí)避障。

2 倉儲(chǔ)系統(tǒng)模型構(gòu)建

2.1 倉儲(chǔ)環(huán)境描述

基于“貨到人”的作業(yè)理念，AGV 需要根據(jù)訂單需求主動(dòng)將貨架搬運(yùn)到操作工位由人工完成分揀，因此首先要對(duì)智能倉儲(chǔ)物流系統(tǒng)的作業(yè)環(huán)境進(jìn)行構(gòu)建，將倉儲(chǔ)空間劃分為兩大功能區(qū)：

（1）AGV作業(yè)區(qū)

AGV作業(yè)區(qū)內(nèi)含有貨架存儲(chǔ)站位、AGV?？空尽⒊潆娬竞头謷镜戎饕δ苷军c(diǎn)，構(gòu)成包括貨架存儲(chǔ)、AGV?？砍潆姾统鋈霂旆謷笞鳂I(yè)單元。各單元內(nèi)部設(shè)置有供AGV 通行的巷道，各大單元間并由高速通道連接。AGV除?？砍潆妴卧獠豢稍谄渌疚婚L時(shí)間停靠，通道內(nèi)不設(shè)置靜態(tài)障礙物以保障AGV順暢通行。

（2）人工作業(yè)區(qū)

人工作業(yè)區(qū)與AGV 分揀單元相鄰，人員在分揀單元以外取送分揀臺(tái)上貨物而不直接進(jìn)入AGV 作業(yè)區(qū)，實(shí)現(xiàn)人機(jī)分離。避免AGV 取送貨物過程中人工干擾，并保障了人員安全。

利用拓?fù)浞▽?duì)AGV 作業(yè)區(qū)進(jìn)行電子地圖的構(gòu)建，圖1 為AGV 作業(yè)區(qū)拓?fù)涞貓D，其中深綠色區(qū)域?yàn)橥？砍潆妴卧?，灰色區(qū)域?yàn)樨浖軘[放單元，淺綠色為分揀作業(yè)單元。AGV 的整體尺寸小于貨架，因此電子地圖中相鄰站點(diǎn)之間的距離取決于貨架的尺寸，需要保障移動(dòng)貨架過程中既不會(huì)發(fā)生干涉又不會(huì)使間隙過大降低空間利用率。

圖1 AGV作業(yè)區(qū)拓?fù)涞貓D

對(duì)于任意一個(gè)不在地圖邊界上的站位，其相鄰的理論可達(dá)站位如圖2 所示共有8 個(gè)。AGV 可利用差速轉(zhuǎn)向原理實(shí)現(xiàn)原地轉(zhuǎn)向，考慮到站位間距及AGV 行進(jìn)方向，最終確定AGV相鄰可達(dá)位置為前后左右四個(gè)方向，AGV 可前后方向直接行進(jìn)，左右兩個(gè)方向的移動(dòng)需要配合原地轉(zhuǎn)向?qū)崿F(xiàn)。

圖2 AGV理論可達(dá)站點(diǎn)

2.2 任務(wù)類型

完成電子地圖構(gòu)建后，需要對(duì)智能倉儲(chǔ)系統(tǒng)的不同任務(wù)類型進(jìn)行劃分，以滿足不同需求的作業(yè)，簡單來說就是實(shí)現(xiàn)AGV從規(guī)定起始站點(diǎn)調(diào)度到目標(biāo)終點(diǎn)站位的過程。按任務(wù)的不同啟動(dòng)方式可劃分為自啟動(dòng)與訂單任務(wù)兩種方式。自啟動(dòng)任務(wù)實(shí)現(xiàn)低電充電、自動(dòng)泊車的作業(yè)需求，訂單任務(wù)滿足出入庫分揀作業(yè)需求。倉儲(chǔ)系統(tǒng)中按照一個(gè)任務(wù)最少需要規(guī)劃的路徑的次數(shù)可以分為以下幾種類型：

（1）普通移位任務(wù)

規(guī)定起點(diǎn)到目標(biāo)站點(diǎn)的單次路徑規(guī)劃尋訪作業(yè)任務(wù)類型，可用于實(shí)現(xiàn)車輛調(diào)試、出庫檢修、移位移庫、泊車及充電等功能。

（2）貨架布置任務(wù)

兩次路徑規(guī)劃尋訪作業(yè)。首先指派一輛空閑AGV取得貨架，然后將此貨架運(yùn)送至規(guī)定站位?？蓪?shí)現(xiàn)倉儲(chǔ)空間貨架擺放或按出入庫熱度進(jìn)行貨架調(diào)整。

（3）出/入庫任務(wù)

三次路徑規(guī)劃尋訪作業(yè)。有貨物需要出入庫時(shí)，由訂單下達(dá)作業(yè)指令，智能倉儲(chǔ)貨物管理系統(tǒng)自動(dòng)生成調(diào)度任務(wù)。由系統(tǒng)指派空閑AGV到達(dá)指定貨架站位取得貨架，運(yùn)送貨架至人工操作站位，由人工對(duì)貨物處理，完成操作后將貨架運(yùn)送回原站位。

2.3 沖突類型

任務(wù)的執(zhí)行過程中，AGV間相互競爭系統(tǒng)資源，可能會(huì)發(fā)生碰撞沖突。如圖3所示為倉儲(chǔ)式多AGV間的三種沖突類型[19]：側(cè)向沖突、同向沖突和對(duì)向沖突，貨架區(qū)只有AGV臨近目標(biāo)點(diǎn)，需要取送貨物時(shí)才允許訪問。

（1）側(cè)向沖突，如圖3（a）所示。兩輛交叉方向的AGV 同時(shí)預(yù)約同一個(gè)節(jié)點(diǎn)，主要發(fā)生在十字路口，各AGV 到達(dá)節(jié)點(diǎn)后可能暫停、直行或轉(zhuǎn)向，情況較為復(fù)雜，會(huì)產(chǎn)生沖突造成碰撞。

（2）同向沖突，如圖3（b）所示。一般情況下AGV速度一致，同向行駛AGV 不會(huì)發(fā)生碰撞，但是當(dāng)靠前AGV1 因避障、路口轉(zhuǎn)向或訪問貨架轉(zhuǎn)向而臨時(shí)暫停，靠后AGV2預(yù)約站點(diǎn)又恰好被AGV1占用時(shí)，同樣會(huì)發(fā)生碰撞。

（3）對(duì)向沖突，如圖3（c）所示。貨架間巷道采用單通道布置方式，AGV雖可雙向行駛，但同一通道對(duì)向駛來的AGV，由于無處避障必然會(huì)產(chǎn)生沖突。

圖3 幾種碰撞沖突類型

3 AGV路徑規(guī)劃算法研究

對(duì)于靜態(tài)路網(wǎng)路徑規(guī)劃問題，全局信息已知，站位及障礙信息不隨時(shí)間變化，單AGV進(jìn)行路徑規(guī)劃時(shí)，不存在其他AGV 干擾，可以較好地獲得理論最優(yōu)路徑。而對(duì)于多AGV 的動(dòng)態(tài)路網(wǎng)路徑規(guī)劃問題，地圖信息動(dòng)態(tài)變化，多AGV 間相互影響，很難獲得系統(tǒng)全局信息。A*算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法[20]，存在應(yīng)用價(jià)值及意義，但是它卻不能有效解決多AGV的動(dòng)態(tài)路徑規(guī)劃問題，因此有必要對(duì)其進(jìn)行改進(jìn)。同時(shí)本文提出一種具備多步預(yù)測功能的主動(dòng)式尋路算法，將其與A*算法的改進(jìn)算法比較，在有效解決沖突的基礎(chǔ)上，驗(yàn)證新算法的可靠性和優(yōu)異性。

3.1 被動(dòng)式自調(diào)優(yōu)A＊路徑規(guī)劃算法

3.1.1 轉(zhuǎn)向修正

多數(shù)路徑規(guī)劃算法主要考慮路徑距離最小化，很少考慮轉(zhuǎn)向增加的時(shí)間成本，所規(guī)劃的理論路徑（圖4 中路徑2或路徑3）帶有多處轉(zhuǎn)向點(diǎn)，規(guī)劃路徑理論距離最優(yōu)而時(shí)間非最優(yōu)（圖4中路徑1）。

轉(zhuǎn)向修正的必要性體現(xiàn)在以下正反兩個(gè)方面：

一方面，不考慮轉(zhuǎn)向修正的路徑規(guī)劃算法[21]多應(yīng)用于復(fù)雜空間環(huán)境下的單臺(tái)移動(dòng)機(jī)器人，側(cè)重于減少無效路徑。由于空間的不規(guī)律布置，路徑必要轉(zhuǎn)向次數(shù)較多，很難存在大段連續(xù)路徑。即使考慮轉(zhuǎn)向修正，效果并不顯著，同時(shí)也會(huì)增加算法自身復(fù)雜性，整體性能提升不明顯。

圖4 規(guī)劃路徑對(duì)比圖

另一方面，任務(wù)完成時(shí)間直接影響對(duì)系統(tǒng)效率要嚴(yán)格的多AGV 智能倉儲(chǔ)系統(tǒng)。該系統(tǒng)空間布置規(guī)律，滿足大段光滑路徑的存在條件。單次任務(wù)路徑一般較短，轉(zhuǎn)向次數(shù)的增加會(huì)顯著提高AGV 任務(wù)運(yùn)行時(shí)間，而且頻繁的轉(zhuǎn)彎會(huì)使AGV 耗能增加[22]，有必要在路徑規(guī)劃過程中就考慮轉(zhuǎn)向代價(jià)，得到時(shí)間最優(yōu)路徑。

利用當(dāng)前點(diǎn)(xm,ym)、父節(jié)點(diǎn)(xm-1,ym-1)和子節(jié)點(diǎn)(xm+1,ym+1) 、目標(biāo)終點(diǎn)(xend,yend) 的位置關(guān)系，通過公式（1）與公式（2）可判定AGV行駛方向。

當(dāng)公式（1）與公式（2）計(jì)算數(shù)值相等時(shí)，AGV直行，否則發(fā)生轉(zhuǎn)向。根據(jù)行進(jìn)方向修證：

其中，k 為轉(zhuǎn)向修正系數(shù)，確保AGV優(yōu)先選擇直行。

將轉(zhuǎn)向修正后的理論路徑儲(chǔ)存到走位路徑容器Q(s1,s2,…,send)中，并建立如圖5 所示存儲(chǔ)AGV 父站位sm-1、當(dāng)前站位sm和子站位sm+1的動(dòng)態(tài)走位表P(sm-1,sm,sm+1)實(shí)時(shí)更新AGV 實(shí)際行駛路徑。判定AGV 預(yù)計(jì)行駛方向時(shí)將容器Q 首位站點(diǎn)傳入sm+1，若預(yù)計(jì)行駛方向不變則sm+1為初始傳入值，并移除容器Q 首位站點(diǎn)；否則sm+1更新為sm值，AGV 原地轉(zhuǎn)向或暫停，容器Q暫不改變。

圖5 動(dòng)態(tài)滑移表

3.1.2 優(yōu)先級(jí)自動(dòng)調(diào)優(yōu)

對(duì)于兩輛AGV間的相互作用關(guān)系可以較容易判斷出如圖3的三種狀態(tài)。但實(shí)際作業(yè)環(huán)境中隨著AGV數(shù)量的增加，很難進(jìn)行沖突的有效劃分，以圖6多AGV間相互作用關(guān)系為例。預(yù)計(jì)AGV3 與AGV4 將會(huì)發(fā)生沖突，若AGV3 的優(yōu)先級(jí)高則只需AGV4 重新規(guī)劃路徑，而若AGV4 的優(yōu)先級(jí)高則AGV1～AGV3 都需要重新尋路，AGV的優(yōu)先級(jí)順序?qū)⒅苯佑绊懻w的路徑規(guī)劃代價(jià)。

圖6 多AGV間相互作用關(guān)系

因此建立一個(gè)初始狀態(tài)只存儲(chǔ)當(dāng)前AGV序號(hào)的鏈表L(vcurr)，通過如圖7 所示AGV 指向鏈表判定規(guī)則完成鏈表L(vcurr→vnext1→…→vend)的更新，并通過鏈表自動(dòng)調(diào)節(jié)AGV執(zhí)行任務(wù)優(yōu)先級(jí)，使解決沖突代價(jià)最小。

圖7 AGV指向鏈表判定規(guī)則

3.1.3 算法流程

被動(dòng)式自調(diào)優(yōu)A*路徑規(guī)劃算法的流程如圖8所示，具體步驟如下：

步驟1 分配調(diào)度任務(wù)，并啟動(dòng)調(diào)度系統(tǒng)。

步驟2 系統(tǒng)根據(jù)制定規(guī)則，有選擇地將任務(wù)分配給空閑AGV，各AGV獲得需要執(zhí)行任務(wù)的始末站點(diǎn)位置及類型的信息。

步驟3 根據(jù)任務(wù)信息及地圖實(shí)時(shí)位置信息規(guī)劃路徑為空的執(zhí)行狀態(tài)AGV 的理論最優(yōu)路徑，并將規(guī)劃后路徑存入預(yù)約走位路徑容器Q 內(nèi)。

步驟4 根據(jù)行進(jìn)方向規(guī)則與各AGV的走位路徑容器內(nèi)的路徑信息，更新走位表P 的實(shí)時(shí)信息。

步驟5 按鏈表L 規(guī)則調(diào)節(jié)AGV 優(yōu)先級(jí)，優(yōu)先更新可走無礙AGV 操作狀態(tài)為已完成，并清空存在沖突的AGV預(yù)約走位路徑容器Q 內(nèi)位置信息，跳轉(zhuǎn)到步驟3，直至所有AGV狀態(tài)信息為已操作。

步驟6 各AGV 根據(jù)對(duì)應(yīng)走位表P 信息完成相關(guān)行駛操作，并更新各預(yù)約走位路徑容器Q 內(nèi)信息，重置所有AGV為未操作狀態(tài)。

圖8 被動(dòng)式自調(diào)優(yōu)A*路徑規(guī)劃算法

步驟7 判斷各AGV 任務(wù)完成狀態(tài)，完成當(dāng)前任務(wù)的AGV 標(biāo)記為空閑狀態(tài)，等待分配新任務(wù)。存在未完成任務(wù)的AGV 或系統(tǒng)內(nèi)有未分配的任務(wù)存在則從步驟2開始重復(fù)執(zhí)行操作，直至所有AGV完成任務(wù)，且系統(tǒng)內(nèi)無新調(diào)度任務(wù)，終止所有調(diào)度。

3.2 多步前瞻算法

3.2.1 啟發(fā)函數(shù)確定

路徑規(guī)劃算法層面上，無論是否考慮了轉(zhuǎn)向修正，工程中都要考慮轉(zhuǎn)向的實(shí)現(xiàn)，并不會(huì)增加系統(tǒng)硬件層面上的困難程度，因此轉(zhuǎn)向修正更多考慮的是實(shí)施必要性。由于只需對(duì)代價(jià)相同的備選節(jié)點(diǎn)進(jìn)行修正，計(jì)算時(shí)間的增加極少，遠(yuǎn)遠(yuǎn)小于拓?fù)涞貓D中相鄰節(jié)點(diǎn)的奔赴代價(jià)，減少多次轉(zhuǎn)向的路徑時(shí)間代價(jià)反而更優(yōu)，縮短了任務(wù)完成時(shí)間，提升了系統(tǒng)整體效率。

一般來說，啟發(fā)函數(shù)常采用曼哈頓距離、對(duì)角線距離、歐幾里德距離和平方后的歐幾里德距離等方法[23]。這些方法各有優(yōu)缺點(diǎn)，針對(duì)具體模型，本文是在考慮了轉(zhuǎn)向修正基礎(chǔ)上進(jìn)一步研究。

在考慮轉(zhuǎn)向修正后，利用曼哈頓距離法一般可獲得較少轉(zhuǎn)向的路徑，但當(dāng)臨近目標(biāo)終點(diǎn)時(shí)，如圖9（a）所示，AGV從右側(cè)駛?cè)肼房?，預(yù)測上、左兩節(jié)點(diǎn)代價(jià)相同，進(jìn)行修正后選擇直行，可能導(dǎo)致局部繞行；其他方法如圖9（b）所示歐式距離法，在鄰近目標(biāo)點(diǎn)時(shí)，不需要修正或修正后最優(yōu)路徑代價(jià)依然最小，可避免繞行，但需要更長的求解時(shí)間，且在遠(yuǎn)離目標(biāo)點(diǎn)時(shí)，修正系數(shù)過小而常起不到修正作用，雖仍優(yōu)于一般算法，但轉(zhuǎn)向次數(shù)依然有所增加。

圖9 不同啟發(fā)函數(shù)搜索路徑

針對(duì)以上問題，提出了考慮轉(zhuǎn)向代價(jià)修正的曼哈頓距離與歐幾里德距離融合方法，在遠(yuǎn)離目標(biāo)站點(diǎn)的位置采用曼哈頓距離方式提高運(yùn)算效率減少轉(zhuǎn)向次數(shù)，在臨近目標(biāo)終點(diǎn)位置采用歐幾里德距離方式避免繞行。

其中，k為方向修正系數(shù)。當(dāng)|xend-xm+1|＜4 或|yend-ym+1|＜3 時(shí)，H(m+1)計(jì)算方法為公式（4），其他情況通過公式（5）計(jì)算。

3.2.2 沖突預(yù)測及路徑擬合

由于動(dòng)態(tài)路網(wǎng)全局信息實(shí)時(shí)變化，搜索出的理論最優(yōu)路徑會(huì)由于擾動(dòng)而失效。此方法在尋路過程中不需要獲得完整路徑，只需補(bǔ)算前k 步路徑，儲(chǔ)存在多步位置信息地圖鏈表M(m0,m1,…,mk-1,mk) 中用于判定AGV間位置關(guān)系，如圖10所示除m0表用于存放當(dāng)前地圖AGV 位置及站位信息外，其他各表用于存儲(chǔ)前瞻k步的趨勢位置信息。

圖10 位置信息地圖鏈表

沖突預(yù)測及路徑擬合以圖11 為例，隨機(jī)生成一段普通移位任務(wù)，初始狀態(tài)時(shí)（圖11（a））預(yù)計(jì)無沖突，隨著AGV 行進(jìn)在預(yù)測步內(nèi)突然出現(xiàn)故障AGV（圖11（b）），選擇不增加代價(jià)的無沖突路徑（圖11（c））繼續(xù)行駛，通過逐步迭代擬合方式（圖11（d）至圖11（f））得到完整路徑。

圖11 沖突預(yù)測及路徑擬合過程

所謂不增加代價(jià)的無沖突路徑選擇，并非路徑整體擬合后相比無沖突路徑代價(jià)不增，而是基于當(dāng)前路況信息進(jìn)行計(jì)算，體現(xiàn)在三方面：第一，優(yōu)先選擇不增加路徑代價(jià)或少量增加轉(zhuǎn)向次數(shù)的趨向目標(biāo)的通暢路徑；第二，無通暢路徑時(shí)選擇少繞行或等待時(shí)間最少路徑；第三，從概率的角度對(duì)同代價(jià)路徑進(jìn)行判別，選擇后續(xù)更少出現(xiàn)沖突的路徑。

3.2.3 算法流程

其操作方法如圖12所示，并給出相應(yīng)操作方法：

步驟1 啟動(dòng)系統(tǒng)并加入調(diào)度任務(wù)。

步驟2 分配任務(wù)給空閑AGV。

步驟3 針對(duì)未操作狀態(tài)的AGV根據(jù)地圖鏈表信息及其不可訪問站點(diǎn)狀態(tài)按搜索規(guī)則補(bǔ)齊路表中站位點(diǎn)數(shù)量少于k 步的缺失點(diǎn)位。

步驟4 順序訪問未操作狀態(tài)的AGV，判斷對(duì)應(yīng)路徑表走位的可通行狀態(tài)。更新可通行AGV對(duì)應(yīng)位置信息地圖鏈表上位置信息并標(biāo)記已操作狀態(tài)，對(duì)于出現(xiàn)障礙的AGV，回溯路徑至無沖突長度并設(shè)置該AGV不可訪問的站點(diǎn)并返回步驟3。

步驟5 全部AGV 狀態(tài)都為已操作狀態(tài)后，發(fā)送信號(hào)，傳遞給各AGV 行進(jìn)站位信息，并重置其操作狀態(tài)；否則返回步驟4重復(fù)執(zhí)行。

步驟6 標(biāo)記到達(dá)目標(biāo)終點(diǎn)AGV 為空閑狀態(tài)，對(duì)于無空閑AGV的情況，返回步驟4重復(fù)執(zhí)行，出現(xiàn)空閑車輛并有未分配任務(wù)存在則返回步驟2重復(fù)執(zhí)行，AGV全部空閑并無閑置任務(wù)則停止調(diào)度系統(tǒng)。

3.2.4 算法總結(jié)

被動(dòng)式自調(diào)優(yōu)A*路徑規(guī)劃算法，屬于被動(dòng)式?jīng)_突解決方案，在運(yùn)行過程中，由于意外路徑可能會(huì)失效。因避障而重新規(guī)劃路徑容易導(dǎo)致非必要繞行，并且會(huì)造成未達(dá)路徑的計(jì)算量浪費(fèi)。

對(duì)于提出的趨向終點(diǎn)的主動(dòng)式多步前瞻算法，這是一種增量式的路徑規(guī)劃算法，通過迭代方式逐步擬合出完整路徑，由于事先不需要規(guī)劃全部路徑，重新尋路時(shí)減少了計(jì)算損失。

前瞻步數(shù)被確定為至少可以預(yù)測兩個(gè)直行路口或半個(gè)貨架回環(huán)，可防止死鎖或陷入局部最優(yōu)解，又不至于過多增加計(jì)算量。在不發(fā)生沖突的情況下，擬合路徑與最優(yōu)靜態(tài)算法一致，保證了完整路徑的最優(yōu)性。預(yù)測沖突或擁堵時(shí)，主動(dòng)選擇代價(jià)較小和更通暢路徑。

由于該算法綜合考慮多AGV 協(xié)同工作，因此路徑規(guī)劃的前提是整體最優(yōu)而非某幾輛AGV局部最優(yōu)。增量尋路過程中結(jié)合實(shí)時(shí)信息和前序路況信息，在不過多增加路徑代價(jià)的前提下，主動(dòng)選擇更小可能重新尋路的路徑。

4 仿真結(jié)果分析

4.1 仿真環(huán)境

采用QT 圖形化工具作為開發(fā)環(huán)境，利用C++語言開發(fā)出一種用于倉儲(chǔ)多AGV路徑規(guī)劃的仿真平臺(tái)。用戶可根據(jù)需要自由添加任務(wù)，選擇路徑規(guī)劃算法，配置AGV 數(shù)量，實(shí)時(shí)顯示行程狀態(tài)，可查任務(wù)執(zhí)行日志，仿真界面如圖13所示。

圖13 路徑規(guī)劃仿真平臺(tái)

4.2 路徑規(guī)劃算法分析

為了直觀比較不同算法效果，利用3 輛AGV 隨機(jī)分配普通移位任務(wù)進(jìn)行對(duì)比，并給出任務(wù)信息如下：

T{s1,e1}，其中s1=(4,7),e1=(18,7)

T{s2,e2}，其中s2=(16,7),e2=(2,4)

T{s3,e3}，其中s3=(13,10),e3=(5,2)

圖14為單AGV理論路徑，換言之就是各AGV在忽略其他動(dòng)態(tài)車輛下的路徑規(guī)劃。多AGV若采取此種規(guī)劃路徑行駛，AGV1 與AGV2 將在（10，7）處由于同時(shí)占位發(fā)生碰撞，AGV2 與AGV3 將在（13，7）與（5，4）兩處碰撞。

圖14 單AGV理論路徑

圖15 為多AGV 動(dòng)態(tài)路徑規(guī)劃算法。自調(diào)優(yōu)A*算法預(yù)測AGV1與AGV2在（10，7）位置產(chǎn)生沖突，動(dòng)態(tài)調(diào)整優(yōu)先級(jí)，使AGV1保持直行而AGV2掉頭，AGV2增加了一定繞行距離；AGV2與AGV3預(yù)計(jì)在（13，7）處發(fā)生沖突，AGV2 獲取更高優(yōu)先級(jí)而率先通過，AGV3 等待AGV2 通過后繼續(xù)行駛。多步前瞻算法提前k 步進(jìn)行前瞻性預(yù)測，針對(duì)（10，7）處可能發(fā)生沖突，AGV2 在上一路口提前轉(zhuǎn)向，避免繞行，AGV3 預(yù)測到左行路段繁忙，改為上行避開擁堵路段。

圖15 防止沖突的多AGV路徑規(guī)劃

各種算法的對(duì)比分析如表1，可以發(fā)現(xiàn)單獨(dú)應(yīng)用靜態(tài)算法無法解決沖突問題，而兩種動(dòng)態(tài)算法都實(shí)現(xiàn)了無沖突的路徑規(guī)劃，多步前瞻算法無論是單項(xiàng)指標(biāo)還是總體代價(jià)都優(yōu)于自調(diào)優(yōu)A*算法，接近或優(yōu)于單AGV理論最優(yōu)路徑。

4.3 性能評(píng)價(jià)

AGV系統(tǒng)的研究并沒有統(tǒng)一的評(píng)價(jià)標(biāo)準(zhǔn)。多數(shù)研究者在研究AGV 數(shù)量配置時(shí)會(huì)引入AGV 的利用率進(jìn)行評(píng)價(jià)，對(duì)于本文所涉及倉儲(chǔ)系統(tǒng)而言，任務(wù)類型多樣，隨著AGV 數(shù)量的增多系統(tǒng)愈發(fā)復(fù)雜，規(guī)劃路徑長度動(dòng)態(tài)可變，單獨(dú)運(yùn)用AGV 利用率評(píng)價(jià)并不客觀。故針對(duì)倉儲(chǔ)系統(tǒng)抽象后，提出如下評(píng)價(jià)指標(biāo)：

表1 不同路徑規(guī)劃算法對(duì)比

（1）空行比：AGV 總空載代價(jià)與AGV 總行進(jìn)代價(jià)之比，空行比的數(shù)值越小，額外代價(jià)也就越小，效率越高。

（2）平均行進(jìn)時(shí)間：AGV完成所有任務(wù)的平均行進(jìn)耗時(shí)。

（3）任務(wù)總耗時(shí)：系統(tǒng)完成全部任務(wù)的最大系統(tǒng)耗時(shí)。

（4）總運(yùn)算次：各AGV每同時(shí)完成一次站位更新視為一步，完成全部任務(wù)時(shí)的計(jì)算步長為總運(yùn)算次。

隨機(jī)生成150 組離散的出/入庫任務(wù)，并選取最多32 輛AGV，采用順序分配任務(wù)方式對(duì)兩種路徑規(guī)劃算法進(jìn)行仿真。

AGV執(zhí)行任務(wù)的先后順序會(huì)對(duì)系統(tǒng)的整體性能造成影響，圖16 為150 個(gè)任務(wù)下，兩種算法的空行比關(guān)系對(duì)比，根據(jù)仿真結(jié)果不同數(shù)量AGV 兩種算法的空行比趨于穩(wěn)定，波動(dòng)不大，用以衡量任務(wù)對(duì)AGV 分配的均衡性。

圖16 空行比關(guān)系

圖17為AGV完成每個(gè)任務(wù)的平均時(shí)間，隨著AGV數(shù)量的增多，交通狀況繁忙而導(dǎo)致平均任務(wù)完成時(shí)間呈上升趨勢。圖18為兩種算法任務(wù)總耗時(shí)與總計(jì)算次的關(guān)系，它們的總體趨勢相同。

圖17 平均任務(wù)完成時(shí)間關(guān)系

圖18 任務(wù)總耗時(shí)與總計(jì)算次關(guān)系

圖19 為兩種算法效率對(duì)比，從任務(wù)的平均計(jì)算時(shí)間上來看，由于多步前瞻算法引入了沖突提前判斷機(jī)制，在計(jì)算時(shí)間上有所增加，但最多僅增加54.3 ms，在非擁堵路段計(jì)算時(shí)間甚至有所降低。但是從任務(wù)的總耗時(shí)的角度來看，多步前瞻算法極大節(jié)省了任務(wù)完成時(shí)間，最大提前完成率甚至達(dá)到41.63%。

圖19 兩種算法效率對(duì)比

對(duì)比自調(diào)優(yōu)A*算法與多步前瞻算法。將無沖突時(shí)理論最優(yōu)路徑的平均任務(wù)完成時(shí)間視為基值，前者的基值不僅要略高于后者7.96%，而且平均任務(wù)完成時(shí)間的增速是后者的2.47 倍。同一倉儲(chǔ)環(huán)境，隨AGV 的數(shù)量增多，系統(tǒng)的全部任務(wù)的完成時(shí)間會(huì)隨AGV 增多逐漸減少至最小值后平緩上揚(yáng)，后者最小完成任務(wù)耗時(shí)僅相當(dāng)于前者54.40%。

AGV 系統(tǒng)的小車數(shù)量配置是綜合了AGV 系統(tǒng)的投入成本以及生產(chǎn)系統(tǒng)因?yàn)锳GV 系統(tǒng)服務(wù)水平下降造成生產(chǎn)損失成本所綜合后產(chǎn)生的最優(yōu)解[24]。本文僅從整體總耗時(shí)角度分析，自調(diào)優(yōu)A*算法在19輛AGV時(shí)達(dá)到完成耗時(shí)最小，而多步前瞻算法可以持續(xù)增加AGV數(shù)量提高系統(tǒng)性能，在30輛AGV時(shí)達(dá)到最優(yōu)。關(guān)于本系統(tǒng)理論上的全局最優(yōu)AGV數(shù)量配置還要結(jié)合實(shí)際系統(tǒng)各方面成本綜合考慮。

5 結(jié)束語

針對(duì)倉儲(chǔ)系統(tǒng)多AGV 路徑規(guī)劃問題，結(jié)合實(shí)際需求，提出了兩種路徑規(guī)劃算法。自調(diào)優(yōu)A*算法在滿足系統(tǒng)實(shí)時(shí)動(dòng)態(tài)規(guī)劃需求及解決AGV可能存在沖突的前提下，在路徑規(guī)劃方面考慮了轉(zhuǎn)向代價(jià)，所規(guī)劃理論路徑減少了AGV不必要轉(zhuǎn)向，不僅距離最優(yōu)，而且時(shí)間開銷更小；預(yù)測啟發(fā)式算法在路徑規(guī)劃方面性能更好，且具備前瞻性沖突判斷功能，可提前預(yù)測可能發(fā)生沖突，提前選擇非擁堵路段通行，極大減少了繞行距離，使多AGV整體性能最優(yōu)。