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

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

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

0 引言

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

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

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

1 問題描述

1.1 環(huán)境地圖

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

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

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

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

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

圖1 倉儲環(huán)境下拓撲地圖

1.2 目標函數(shù)

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

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

(1)

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

(2)

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

1.3 任務調度

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

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

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

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

1.4 避障要素

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

圖2 相向沖突示意圖

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

圖3 垂直相遇沖突示意圖

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

圖4 占位沖突1示意圖

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

圖5 占位沖突2示意圖

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

圖6 追尾沖突示意圖

2 基于時間窗的避障路線規(guī)劃法

2.1 時間窗定義

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

(3)

圖7 節(jié)點保留時間窗模型圖

2.2 時間窗計算

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

(4)

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

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

(5)

其中，vst是小車統(tǒng)一默認的直行速度。

圖8 自動導引車通過節(jié)點i示意圖

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

(6)

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

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

2.3 AGV最優(yōu)路徑規(guī)劃算法

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

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

(7)

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

(8)

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

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

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

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

圖10 三叉堆優(yōu)先級隊列示意圖

體現(xiàn)在沖突一：后續(xù)的長任務需要不斷地尋找次優(yōu)路線；體現(xiàn)在沖突二：后續(xù)的長任務需要不斷地負載等待。二者都容易造成任務饑餓，會降低調度系統(tǒng)的效率。

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

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

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

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

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

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

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

圖11 AGV路徑規(guī)劃算法流程圖

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

3 算法仿真驗證

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

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

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

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

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

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

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

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

圖12 無時間窗加鎖含優(yōu)先級路徑尋優(yōu)結果

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

圖13 含時間窗加鎖含優(yōu)先級路徑尋優(yōu)結果

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

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

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

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

算法執(zhí)行過程如圖14所示。

圖14 含時間窗加鎖不含優(yōu)先級路徑尋優(yōu)結果

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

表1 不含優(yōu)先級隊列的調度算法執(zhí)行分析

表2 含優(yōu)先級隊列的調度算法執(zhí)行分析

4 結論

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