倉儲式多AGV系統的路徑規劃研究及仿真

于赫年，白 樺，李 超

1.哈爾濱工業大學 機電工程學院，哈爾濱150001

2.蕪湖哈特機器人產業技術研究院有限公司 前瞻技術研究中心，安徽 蕪湖241000

1 引言

隨著電商、快遞和新能源等新興產業的高速發展，大幅帶動了倉儲AGV 的全面需求，為智能倉儲系統的研發與應用注入了全新活力。加之制造業、商貿流通等領域的持續促進，智能倉儲系統的發展具備更廣闊的市場前景。對于任務規模化、貨架密集型的倉儲作業環境而言，路徑規劃算法對于提升智能倉儲系統整體性能、降低各方面運營成本和提高企業利潤等方面都起到了關鍵作用。

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

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

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

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

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

2 倉儲系統模型構建

2.1 倉儲環境描述

基于“貨到人”的作業理念，AGV 需要根據訂單需求主動將貨架搬運到操作工位由人工完成分揀，因此首先要對智能倉儲物流系統的作業環境進行構建，將倉儲空間劃分為兩大功能區：

（1）AGV作業區

AGV作業區內含有貨架存儲站位、AGV停靠站、充電站和分揀站等主要功能站點，構成包括貨架存儲、AGV停靠充電和出入庫分揀三大作業單元。各單元內部設置有供AGV 通行的巷道，各大單元間并由高速通道連接。AGV除停靠充電單元外不可在其他站位長時間停靠，通道內不設置靜態障礙物以保障AGV順暢通行。

（2）人工作業區

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

利用拓撲法對AGV 作業區進行電子地圖的構建，圖1 為AGV 作業區拓撲地圖，其中深綠色區域為停靠充電單元，灰色區域為貨架擺放單元，淺綠色為分揀作業單元。AGV 的整體尺寸小于貨架，因此電子地圖中相鄰站點之間的距離取決于貨架的尺寸，需要保障移動貨架過程中既不會發生干涉又不會使間隙過大降低空間利用率。

圖1 AGV作業區拓撲地圖

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

圖2 AGV理論可達站點

2.2 任務類型

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

（1）普通移位任務

規定起點到目標站點的單次路徑規劃尋訪作業任務類型，可用于實現車輛調試、出庫檢修、移位移庫、泊車及充電等功能。

（2）貨架布置任務

兩次路徑規劃尋訪作業。首先指派一輛空閑AGV取得貨架，然后將此貨架運送至規定站位。可實現倉儲空間貨架擺放或按出入庫熱度進行貨架調整。

（3）出/入庫任務

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

2.3 沖突類型

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

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

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

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

圖3 幾種碰撞沖突類型

3 AGV路徑規劃算法研究

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

3.1 被動式自調優A＊路徑規劃算法

3.1.1 轉向修正

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

轉向修正的必要性體現在以下正反兩個方面：

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

圖4 規劃路徑對比圖

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

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

當公式（1）與公式（2）計算數值相等時，AGV直行，否則發生轉向。根據行進方向修證：

其中，k 為轉向修正系數，確保AGV優先選擇直行。

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

圖5 動態滑移表

3.1.2 優先級自動調優

對于兩輛AGV間的相互作用關系可以較容易判斷出如圖3的三種狀態。但實際作業環境中隨著AGV數量的增加，很難進行沖突的有效劃分，以圖6多AGV間相互作用關系為例。預計AGV3 與AGV4 將會發生沖突，若AGV3 的優先級高則只需AGV4 重新規劃路徑，而若AGV4 的優先級高則AGV1～AGV3 都需要重新尋路，AGV的優先級順序將直接影響整體的路徑規劃代價。

圖6 多AGV間相互作用關系

因此建立一個初始狀態只存儲當前AGV序號的鏈表L(vcurr)，通過如圖7 所示AGV 指向鏈表判定規則完成鏈表L(vcurr→vnext1→…→vend)的更新，并通過鏈表自動調節AGV執行任務優先級，使解決沖突代價最小。

圖7 AGV指向鏈表判定規則

3.1.3 算法流程

被動式自調優A*路徑規劃算法的流程如圖8所示，具體步驟如下：

步驟1 分配調度任務，并啟動調度系統。

步驟2 系統根據制定規則，有選擇地將任務分配給空閑AGV，各AGV獲得需要執行任務的始末站點位置及類型的信息。

步驟3 根據任務信息及地圖實時位置信息規劃路徑為空的執行狀態AGV 的理論最優路徑，并將規劃后路徑存入預約走位路徑容器Q 內。

步驟4 根據行進方向規則與各AGV的走位路徑容器內的路徑信息，更新走位表P 的實時信息。

步驟5 按鏈表L 規則調節AGV 優先級，優先更新可走無礙AGV 操作狀態為已完成，并清空存在沖突的AGV預約走位路徑容器Q 內位置信息，跳轉到步驟3，直至所有AGV狀態信息為已操作。

步驟6 各AGV 根據對應走位表P 信息完成相關行駛操作，并更新各預約走位路徑容器Q 內信息，重置所有AGV為未操作狀態。

圖8 被動式自調優A*路徑規劃算法

步驟7 判斷各AGV 任務完成狀態，完成當前任務的AGV 標記為空閑狀態，等待分配新任務。存在未完成任務的AGV 或系統內有未分配的任務存在則從步驟2開始重復執行操作，直至所有AGV完成任務，且系統內無新調度任務，終止所有調度。

3.2 多步前瞻算法

3.2.1 啟發函數確定

路徑規劃算法層面上，無論是否考慮了轉向修正，工程中都要考慮轉向的實現，并不會增加系統硬件層面上的困難程度，因此轉向修正更多考慮的是實施必要性。由于只需對代價相同的備選節點進行修正，計算時間的增加極少，遠遠小于拓撲地圖中相鄰節點的奔赴代價，減少多次轉向的路徑時間代價反而更優，縮短了任務完成時間，提升了系統整體效率。

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

在考慮轉向修正后，利用曼哈頓距離法一般可獲得較少轉向的路徑，但當臨近目標終點時，如圖9（a）所示，AGV從右側駛入路口，預測上、左兩節點代價相同，進行修正后選擇直行，可能導致局部繞行；其他方法如圖9（b）所示歐式距離法，在鄰近目標點時，不需要修正或修正后最優路徑代價依然最小，可避免繞行，但需要更長的求解時間，且在遠離目標點時，修正系數過小而常起不到修正作用，雖仍優于一般算法，但轉向次數依然有所增加。

圖9 不同啟發函數搜索路徑

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

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

3.2.2 沖突預測及路徑擬合

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

圖10 位置信息地圖鏈表

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

圖11 沖突預測及路徑擬合過程

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

3.2.3 算法流程

其操作方法如圖12所示，并給出相應操作方法：

步驟1 啟動系統并加入調度任務。

步驟2 分配任務給空閑AGV。

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

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

步驟5 全部AGV 狀態都為已操作狀態后，發送信號，傳遞給各AGV 行進站位信息，并重置其操作狀態；否則返回步驟4重復執行。

步驟6 標記到達目標終點AGV 為空閑狀態，對于無空閑AGV的情況，返回步驟4重復執行，出現空閑車輛并有未分配任務存在則返回步驟2重復執行，AGV全部空閑并無閑置任務則停止調度系統。

3.2.4 算法總結

被動式自調優A*路徑規劃算法，屬于被動式沖突解決方案，在運行過程中，由于意外路徑可能會失效。因避障而重新規劃路徑容易導致非必要繞行，并且會造成未達路徑的計算量浪費。

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

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

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

4 仿真結果分析

4.1 仿真環境

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

圖13 路徑規劃仿真平臺

4.2 路徑規劃算法分析

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

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在忽略其他動態車輛下的路徑規劃。多AGV若采取此種規劃路徑行駛，AGV1 與AGV2 將在（10，7）處由于同時占位發生碰撞，AGV2 與AGV3 將在（13，7）與（5，4）兩處碰撞。

圖14 單AGV理論路徑

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

圖15 防止沖突的多AGV路徑規劃

各種算法的對比分析如表1，可以發現單獨應用靜態算法無法解決沖突問題，而兩種動態算法都實現了無沖突的路徑規劃，多步前瞻算法無論是單項指標還是總體代價都優于自調優A*算法，接近或優于單AGV理論最優路徑。

4.3 性能評價

AGV系統的研究并沒有統一的評價標準。多數研究者在研究AGV 數量配置時會引入AGV 的利用率進行評價，對于本文所涉及倉儲系統而言，任務類型多樣，隨著AGV 數量的增多系統愈發復雜，規劃路徑長度動態可變，單獨運用AGV 利用率評價并不客觀。故針對倉儲系統抽象后，提出如下評價指標：

表1 不同路徑規劃算法對比

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

（2）平均行進時間：AGV完成所有任務的平均行進耗時。

（3）任務總耗時：系統完成全部任務的最大系統耗時。

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

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

AGV執行任務的先后順序會對系統的整體性能造成影響，圖16 為150 個任務下，兩種算法的空行比關系對比，根據仿真結果不同數量AGV 兩種算法的空行比趨于穩定，波動不大，用以衡量任務對AGV 分配的均衡性。

圖16 空行比關系

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

圖17 平均任務完成時間關系

圖18 任務總耗時與總計算次關系

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

圖19 兩種算法效率對比

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

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

5 結束語

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