倉儲物流中自動導引車的路徑規劃研究*

劉敬一，孫維堂，劉 閩，董君陶

(1.中國科學院大學，北京 100049；2.中國科學院 沈陽計算技術研究所 智能控制與裝備部,沈陽 110168；3.沈陽市環境監測中心站 沈陽 110000；4沈陽市第二十七中學 沈陽 110011)

0 引言

隨著柔性制造系統的廣泛應用，國內對自動導引車的需求量也漸漸增長。在整個自動化倉儲物流中，AGV運輸成本占總成本比重較高，倉儲任務的精準調度以及AGV良好的路徑規劃策略，對提高物流作業效率、降低運輸成本有重要意義。

針對多AGV的路徑尋優問題，劉國棟等[1]提出了一種兩階段的交通控制方法來解決AGV路徑沖突問題,王佳溶[2]提出改進型的兩階段控制策略，他們針對任務的優先級未做詳細描述，當任務和車輛非常多時，容易產生任務饑餓；胡彬等[3]提出一種基于時間窗的動態路徑規劃方法，先搜索出備選路徑，然后通過計算和排布時間窗來規避沖突，但提出的時間窗是基于邊的，也就是一條較長車道只能被一臺AGV保留，效率比節點時間窗低。

對AGV路徑規劃中路徑成本最優化以及調度效率問題，提出一種基于優先級隊列和時間窗動態排序的路徑規劃方法。首先構建任務優先級隊列，然后用A-Star算法啟發式搜索路徑，通過對節點時間窗進行精確計算和加鎖，實現了多AGV的路徑實時規劃和動態調優，在無碰撞沖突條件下保證了倉儲物流路徑成本最低，而且提高了系統運行效率。

1 問題描述

1.1 環境地圖

本文所考慮的是自動化倉儲物流中AGV群體運動規則問題，根據其所在的倉儲環境采用拓撲建模法構建地圖，并作以下假設：

(1)相鄰節點間的路線為單行道可雙向行駛。

(2)AGV在4個方向上以同一速度勻速行駛，且轉向速度固定；

(3)AGV間安全制動距離為0.8m；

(4)AGV共有4種狀態：無任務靜止狀態(包括充電狀態)，有任務待負載行駛狀態，負載搬運狀態，臨時等待狀態。

圖1 倉儲環境下拓撲地圖

1.2 目標函數

針對AGV倉儲物流環境，建立拓撲地圖，如圖1所示，在有向連接網絡G=中，V代表網絡中節點的集合V={v1,v2,…,vn},E代表網絡中邊的集合E={e1,e2,…,em}， 且每條邊可以用相鄰節點有序對來表示：

ey={vp→vq：vp，vq∈V}

(1)

多AGV路徑規劃的目的是規劃出一條時間代價最小的路徑。AGV在倉儲環境中的耗時分為到達裝載點時間，搬運狀態時間和避障等待時間，分別設為的tk、carrytk和Ωk。因此所有AGV的時間代價之和可由以下公式得到：

(2)

其中，k為倉儲任務的編號。

1.3 任務調度

(1)亟待充電且攜帶任務，將已分配的任務作為高優先級重新分配，然后將充電任務作為中優先級重新分配；

(2)亟待充電且無任務無負載，將充電任務作為中優先級重新分配；

(3)一般性實時任務作為低優先級分配；

(4)同一優先級按照FCFS方法分配。

1.4 避障要素

(1)相向相遇沖突。如圖2所示，相向行駛的兩輛車相遇；

圖2 相向沖突示意圖

(2)垂直相遇沖突。如圖3所示，垂直方向的兩輛車在節點相遇；

圖3 垂直相遇沖突示意圖

(3)占位沖突(車輛空閑)。如圖4所示，前方因AGV空閑停車阻止了其他車的前進。

圖4 占位沖突1示意圖

(4)占位沖突(故障)。如圖5所示，前方因故障停車阻止了其他車的前進。

圖5 占位沖突2示意圖

(5)追尾沖突(超速)。如圖6所示,即將趕超。

圖6 追尾沖突示意圖

2 基于時間窗的避障路線規劃法

2.1 時間窗定義

如圖1所示，在有向連接網絡G=(V，E)中，假設有x輛車參與任務執行，那么任務的AGV集合為A={a1，a2,…，ax}。所有任務的起點、終點都不同，那么任務的起點集合和終點的集合分別記為S和D,且S?V，D?V。那么自動導引車所經過節點的時間窗可以定義為：

(3)

圖7 節點保留時間窗模型圖

2.2 時間窗計算

為了保障倉儲物流過程的安全性，需要對時間窗進行精準計算，如圖7所示。設AGV到達節點i的時間為ti,則有公式：

(4)

其中，tb為車輛安全制動時間，te為允許最大誤差時間，包括在節點處突發斷電及故障引起的制動誤差。

如圖8所示，設AGV車身的長度為l，AGV直行通過節點時，則有公式：

(5)

其中，vst是小車統一默認的直行速度。

圖8 自動導引車通過節點i示意圖

如圖9所示，當AGV在節點處轉彎時，則有：

(6)

其中，vtu是小車轉彎通過節點的速度。

圖9 自動導引車轉彎通過節點i示意圖

2.3 AGV最優路徑規劃算法

在進行多AGV路徑尋優時，采用拓撲建模法構建倉儲電子地圖，且攜帶任務的AGV在運行過程中可雙向行駛。將一個倉儲搬運任務定義為：

carryk(t)={PQk(t),btk,Sk,Dk,LBk(t)}

(7)

其中，PQk表示第k個任務的實時優先級，參數越大優先級越低；btk表示第k個任務的開始時間；Sk和Dk分別表示第k個任務的裝載點和卸載點，且Sk∈V、Dk∈V；枚舉類型的參數LBk(t)表示第k個任務的搬運狀態,如公式(8)所示。

(8)

給任務分配不同的優先級PQ：如圖10所示，將任務隊列劃分為高中低三個優先級隊列，分別用PQh、PQm和PQl來表示。

(1)當LBk(t)=0時，小車正在去裝載點的路途中，即當有任務無負載的AGV小車亟待充電或突發斷電等故障時，已安排的任務的需要重新分配，將該任務carryk(t)放入高優先級隊列，將充電或維修任務放入中優先級隊列；

(2)當LBk(t)=1時，AGV在裝載點Sk和目的地Dk之間，即有任務有負載的AGV亟待充電或突發斷電等故障時，已安排的任務的需要重新初始化，因為裝載點Sk已經改變，然后將新任務carryk(t)放入高優先級隊列，將充電或維修任務放入中優先級隊列；

(3) 把一般性實時任務放入低優先級隊列。

圖10 三叉堆優先級隊列示意圖

體現在沖突一：后續的長任務需要不斷地尋找次優路線；體現在沖突二：后續的長任務需要不斷地負載等待。二者都容易造成任務饑餓，會降低調度系統的效率。

我們有了任務的優先級分配和時間窗的計算，下面來介紹路徑規劃算法的具體實現步驟，如圖11所示。

(1)根據上位機系統管理員輸入倉儲物流參數，將任務劃分優先級，插入優先級隊列，并初始化多個運輸任務，carryk(t)={PQk(t),btk,Sk,Dk,LBk(t)}。

(2)按照任務的優先級順序進行車輛調度：選用離裝載點[6]最近的空閑AGV來執行任務。

(3)用A-Star算法對路徑進行啟發式搜索，得到臨時的最短行駛路徑。

(5)初始化節點時間窗Wk，如果存在任務p和q使Wp∩Wq≠?，說明節點時間窗因尚未加鎖而出現重疊現象，即在的某個保留時間窗內出現了其他車輛[7]。

(6)根據重疊時間窗和拓撲地圖，來確定將會發生哪種節點沖突，然后對每個節點的時間窗加鎖。如果存在如圖2所示的沖突一相向相遇沖突[8]，選擇PQk(t)較大的任務重新調度，由于根據啟發式算法規劃的臨時最優路線會出現碰撞[9]，因此需要繼續搜索次優路徑，返回執行步驟(3)，若最后所有路線都會出現沖突一，那么返回執行步驟(2)更換AGV車輛；如果沖突類型只剩沖突二垂直相遇沖突[10]，那么攜帶低優先級任務的AGV原地等待一個節點時間窗的時間，直到重疊窗口消失；如果兩種沖突都存在，則先按照相向相遇沖突處理。

(7)生成可執行任務(指定AGV，明確路線)，AGV執行完任務空閑后，由于該AGV可能成為其他任務的障礙，所以要優先派發該車輛。重復執行步驟(1)等待管理員動態分發新需求。

圖11 AGV路徑規劃算法流程圖

考慮其他三種沖突，任務執行過程中，對于沖突三,那么將更改此空閑AGV所占有的節點周圍四條邊的權重為無窮大,修改任務的起始點，執行算法中的步驟(3)；對于沖突四，可能為突發斷電(非亟待充電提醒)或機械老化等故障，需要人工維修或清除，然后更新可用AGV信息；對于沖突五，由于環境中假設AGV速度相同，所以不會出現趕超沖突，即使在前面的AGV制動減速的時候也不會出現趕超沖突，因為在計算時間窗時，AGV制動時間tb已經被保留在時間窗內。

3 算法仿真驗證

使用 Visual Studio 2015作為仿真開發平臺，編寫調度程序對提出的路徑尋優算法進行驗證。選取某倉儲物流中心如圖1拓撲地圖所示，倉儲區域長30m，寬30m，倉儲節點36(不包括充電區域)，144個貨架，14條車道縱橫交錯,AGV直行速度為0.5m/s。轉向時間固定為2s。

設計兩組仿真對比實驗：一組是無時間窗加鎖和有時間窗加鎖的路徑尋優結果，另一組是不含優先級隊列和含優先級隊列的路徑尋優結果。從兩個維度來驗證所提出算法的可行性和高效性。

(1)針對第一種仿真對比實驗，我們分別初始化三個任務：

carry1(t)={1,0,a1,c5, -1}。

carry2(t)={2,0,g3,b3, -1}。

carry3(t)={3,0,e1,b2, -1}。

首先根據任務的預估時間來初始化優先級，時間越長，PQk(t)數字越小，優先級越高。

無時間窗加鎖的情況如圖12所示，執行任務carry1(t)的車輛將會與執行carry3(t)的車輛在b1到c1路段發生相向相遇沖突，執行任務carry1(t)的車輛將會與執行carry2(t)的車輛在c3節點發生垂直相遇沖突[11]；

圖12 無時間窗加鎖含優先級路徑尋優結果

含時間窗加鎖的情況如圖13所示，由于經過時間窗的重新排布，任務carry3(t)已經重新規劃路線，有效避免與任務carry1(t)相向相遇沖突，且在節點c2進行等待規避，避免垂直相遇沖突，任務carry3(t)將會在節點c3處進行規避等待，有效避免死鎖和碰撞[12]。

圖13 含時間窗加鎖含優先級路徑尋優結果

(2)針對第二種仿真對比實驗，在不含優先級的算法中我們分別初始化三個任務，這里PQk(t)均為1，即：

carry1(t)={1,0,a1,c5, -1}。

carry2(t)={1,0,g3,b3, -1}。

carry3(t)={1,0,e1,b2, -1}。

算法執行過程如圖14所示。

圖14 含時間窗加鎖不含優先級路徑尋優結果

考慮圖13和圖14所示的兩種仿真執行過程，對不含優先級和含優先級的兩種調度算法進行路徑代價對比，如表1和表2所示。根據目標函數公式計算出：含優先級的調度算法路徑成本Cost小于不含優先級的調度算法。

表1 不含優先級隊列的調度算法執行分析

表2 含優先級隊列的調度算法執行分析

4 結論

對多AGV路徑尋優和調度效率問題，提出基于優先級隊列和時間窗模型的調度算法。在多AGV動態路徑尋優中，解決了多AGV的碰撞沖突問題，而且通過構建任務優先級隊列優先級優化了調度順序，不僅保證了路徑最優，而且可以避免任務饑餓與死鎖。最后通過仿真實驗得出，算法在保證車輛無碰撞的條件下可使AGV路徑成本最低，同時提高了任務和車輛調度的效率。