于赫年，白 樺，李 超

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

AGV作業(yè)區(qū)內(nèi)含有貨架存儲站位、AGV?？空?、充電站和分揀站等主要功能站點，構(gòu)成包括貨架存儲、AGV?？砍潆姾统鋈霂旆謷笞鳂I(yè)單元。各單元內(nèi)部設(shè)置有供AGV 通行的巷道，各大單元間并由高速通道連接。AGV除?？砍潆妴卧獠豢稍谄渌疚婚L時間停靠，通道內(nèi)不設(shè)置靜態(tài)障礙物以保障AGV順暢通行。

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

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

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

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

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

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

2.2 任務(wù)類型

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

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

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

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

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

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

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

2.3 沖突類型

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

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

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

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

圖3 幾種碰撞沖突類型

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

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

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

3.1.1 轉(zhuǎn)向修正

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

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

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

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

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

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

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

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

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

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

3.1.2 優(yōu)先級自動調(diào)優(yōu)

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

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

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

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

3.1.3 算法流程

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

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

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

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

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

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

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

圖8 被動式自調(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)向的實現(xiàn)，并不會增加系統(tǒng)硬件層面上的困難程度，因此轉(zhuǎn)向修正更多考慮的是實施必要性。由于只需對代價相同的備選節(jié)點進(jìn)行修正，計算時間的增加極少，遠(yuǎn)遠(yuǎn)小于拓?fù)涞貓D中相鄰節(jié)點的奔赴代價，減少多次轉(zhuǎn)向的路徑時間代價反而更優(yōu)，縮短了任務(wù)完成時間，提升了系統(tǒng)整體效率。

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

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

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

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

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

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

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

圖10 位置信息地圖鏈表

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

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

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

3.2.3 算法流程

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

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

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

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

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

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

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

3.2.4 算法總結(jié)

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

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

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

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

4 仿真結(jié)果分析

4.1 仿真環(huán)境

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

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

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

為了直觀比較不同算法效果，利用3 輛AGV 隨機分配普通移位任務(wù)進(jìn)行對比，并給出任務(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在忽略其他動態(tài)車輛下的路徑規(guī)劃。多AGV若采取此種規(guī)劃路徑行駛，AGV1 與AGV2 將在（10，7）處由于同時占位發(fā)生碰撞，AGV2 與AGV3 將在（13，7）與（5，4）兩處碰撞。

圖14 單AGV理論路徑

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

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

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

4.3 性能評價

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

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

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

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

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

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

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

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

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

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

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

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

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

圖19 兩種算法效率對比

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

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

5 結(jié)束語

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