高密集度AGV快遞包裹分揀系統的路徑規劃①

賀學成,呂淑靜,呂 岳

(華東師范大學 上海市多維度信息處理重點實驗室,上海 200062)

1 引言

隨著電子商務的迅猛發展,快遞包裹數量的急劇增加,傳統的人工分揀已不能滿足要求,交叉帶分揀機等自動分揀系統雖然分揀效率較高,但占地面積大,一次性投入成本高,而且一旦建成就不可改變,柔性和靈活性差,能耗高.自動引導小車(AGV)高度的靈活性和低能耗可較好的適應現代物流“多品種、小批量、相對集中”的特點[1].因此基于AGV 的快遞包裹分揀系統成為智能物流近年來的熱點之一,其研究具有重要的實用價值.

早期的AGV 運行時只能單向行駛,因而適用環境受到局限,主要應用于倉儲、制造、港口碼頭、機場等領域完成物料搬運.在這些行業中,AGV 的應用大多表現出工作獨立,固定軌道,行駛速度慢以及密集度低等特點[2,3].隨著AGV 技術的發展和成熟,AGV 的運用也越來越廣泛,在物流領域,輕小型的AGV 被用于快遞分揀近幾年成為自動化分揀的熱點.不同于傳統的AGV 應用場景,在快遞分揀系統中,為了滿足分揀效率的要求,通常會設幾個甚至十幾個上包點,同時進行任務分發,這就要求增加場地中AGV 的數量以便及時處理這些任務.在固定大小的場地中,AGV 數量的增加會使得場地內AGV 密集度增加,這就使得基于AGV 的快遞包裹分揀場地中AGV 數量較多、密集度較高.

我們定義密集度為可行走區域內單位面積內AGV 小車的數量.在實際系統中,通常密集度超過0.05 輛/單位面積,就可稱為高密集度,低于或者等于0.05 輛/單位面積稱為低密集度.基于AGV 的快遞包裹分揀是比較典型的高密集度AGV 應用場景.

傳統的路徑搜索算法根據對環境信息掌握的程度分為兩種[4]：基于傳感器信息的局部路徑規劃和基于環境先驗信息的全局路徑規劃.局部路徑規劃主要方法有人工勢場法[5]、蟻群優化算法[6]、粒子群算法[7]、A*算法[8]等.全局路徑規劃主要方法有可視圖法[9]、自由空間法[10]、柵格法[11]等.人工勢場法容易產生死鎖,適應能力較差,不能夠滿足AGV 動態環境中實時規劃路徑的要求.粒子群算法容易陷入局部極值點,而且若參數選擇不當,會導致尋優過程中粒子的多樣性迅速消失,造成算法“早熟收斂”.蟻群優化算法計算量大、收斂速度慢、求解所需時間較長,不適合實時規劃.自由空間法和可視圖法建立拓撲網絡的過程相當復雜.最重要的是這些路徑規劃算法都僅考慮了AGV 自身因素,忽略了其他AGV 移動對其產生的影響,在高密集度、AGV 可自由行走的情況下,容易造成擁堵.通常情況下,AGV 密集度越高,場地的利用率也就越高,分揀效率也就越高,但是場地中AGV 的密集度增加到一定程度后,會導致擁擠,甚至堵塞,使得分揀效率下降.針對這種情況本文提出CAA*(Congestion-Avoidable A*)算法,算法以動態環境模型為基礎,對各個節點擁堵情況進行預測,在路徑規劃時規避潛在的擁擠節點,避免擁堵情況的發生.為了驗證本文算法避免擁堵的有效性,本文分別使用CAA*算法和A*算法進行了一系列仿真實驗.實驗表明,本文算法在高密集度AGV 場景下確實能避免擁堵,增加場地AGV 的密集度,提高場地的分揀效率.

2 動態環境模型

路徑規劃包含兩個方面,一是建立環境模型,即對AGV 工作空間(環境信息)進行有效表達,是AGV 導航定位的基礎[12].二是進行路徑搜索,即尋找從起點到終點符合條件約束的路徑.以往的路徑規劃中環境模型往往是靜態的,一旦確定,就不可更改,AGV 僅考慮自身因素,忽略了其他AGV 移動對其產生的影響,在高密集的場景下,AGV 可能相互擁擠,造成堵塞,降低整個系統的效率.因此,本文采用柵格法建立動態環境模型,柵格節點引入動態屬性,AGV 在進行路徑規劃和移動時,其對周圍的影響會實時的反映在地圖上,其他AGV 在進行路徑規劃時通過對地圖節點擁擠情況的判斷,規避擁擠節點和潛在的擁擠節點.

2.1 場地柵格化

常見的建立環境模型的方法可概括為柵格地圖法(grid map)[13]、幾何特征地圖法(geometric feature map)[14]、拓撲地圖法(topologic map)[15]三種基本地圖表示法.

柵格地圖法是目前研究最廣泛的方法之一.該方法將機器人的工作空間分解為多個簡單的區域,這些區域稱為柵格.由這些柵格構成一個顯式的連通圖,或在搜索過程中形成隱式的連通圖,然后在圖上搜索一條從起始柵格到目標柵格的路徑.柵格地圖信息直接與環境區域對應,容易創建和維護,方便AGV 進行定位.本文采用柵格法來建立環境模型.以AGV 小車尺寸為基礎確定柵格的大小,將場地映射成一系列規則的網格.

可通行的柵格被稱為自由柵格；不可通行的柵格,稱為障礙柵格.柵格的節點分為有方向和無方向兩種,無方向即可以任意方向行走.有方向又分為八鄰域方向和四鄰域方向.根據快遞包裹分揀AGV 的運動特性,AGV 只能水平和垂直方向行駛,不可斜向行駛,故本文柵格節點采用的是有方向的、四鄰域的模型.

2.2 柵格節點的動態屬性表示

給每個柵格節點增加一個將要經過該節點的小車信息集合,記為V,集合V中存儲二元組＜I,T＞,I代表將要經過該節點的小車編號,T表示將要經過該節點的時間點.因為在實際運行時地面平整度、小車自身硬件、小車路徑沖突等因素,所以很難準確的控制和預測AGV 小車到達每個節點的精確時間點,所以這個T是一個理想的估計值,允許一定的誤差.

假設當前節點為n,則用Vn表 示節點n的小車信息集合,初始狀態Vn為 空集,如果小車i將 要經過節點n,并且距離節點n為j格,根據距離我們可以計算出小車i經過節點n的理想時間ti,然后將二元組vi=＜i,ti＞加入Vn集 合,則Vn={vi} ,其他以此類推.每次小車i向前移動一格,則需將vi的 值更新為vi=＜i,ti-t′＞,t′為小車移動當前柵格所用的時間,如果ti-t′≤0,說明小車i已經過了節點n,則需將vi從Vn集合中移除.

3 可避免擁擠的路徑搜索算法

傳統的A*算法僅考慮了靜態環境信息和當前AGV 的信息,而沒有考慮場地中其他AGV 對當前AGV 的影響,規劃出來的路徑可能造成擁堵,尤其是高密集度AGV 場景中,擁堵嚴重時可能造成某塊區域完全堵塞,使得系統效率急劇下降.本文在A*算法的基礎上引入潛在擁擠節點的概念,對可能發生的擁擠情況進行預測,在路徑規劃過程中繞過擁堵節點或潛在的擁堵節點,避免擁堵.

3.1 A*算法

A*算法是Nilsson NJ[16]在Dijkstra算法基礎上提出的,是靜態路網中最有效的直接搜索方法之一.A*加入了當前節點到目標結點的估計代價,根據起始點經過當前結點到達目標點的代價決定搜索的方向,大大提高了Dijkstra 算法的效率.定義估價函數為：

其中,n代表當前搜索的節點,G(n)是 起始點到節點n的實際代價,H(n)是從節點n到目標節點的估計代價.路徑規劃通常使用距離作為代價,所以常用的估計代價有曼哈頓距離、切比雪夫距離、歐幾里得距離[17,18]等.

假設當前搜索的節點為n(xn,yn),n的父節點是m(xm,ym)( 搜索到了m節 點,再往下搜索到了n,即稱m是n的父節點),終點坐標為(xend,yend),

本文采用曼哈頓距離,所以實際代價：

因為本文采用的柵格節點模型是四鄰域方向.所以n和m是 四連通的,故|xn-xm|+|yn-ym|=1,即

估計代價為當前點n到終點的曼哈頓距離：

由式(3)和式(4)可知當前節點n的最終估計函數為：

3.2 CAA*算法

本文提出的CAA*算法在路徑規劃時通過增加潛在擁擠節點的通行代價,從而避開潛在的擁擠節點,所以算法的關鍵在于潛在擁擠節點的預測,這需要借助于節點的動態屬性集合V,V中記錄了要經過當前節點的小車及其經過的時間點,根據集合V中小車經過當前節點的時間信息,可以統計當前節點某一時間范圍內小車的數量,當小車數量超過擁擠閾值,就判定當前節點為潛在擁擠節點.集合V中的二元組通過增加、更新、刪除三種操作來維持集合中動態屬性信息的時效性.

(1)節點動態屬性的更新

對于節點動態屬性的更新,不是每次更新整個地圖所有節點的動態屬性,而是只更新節點動態屬性有變化的節點,引起節點動態屬性變化的原因有兩個：一是小車路徑變化,小車路徑變化之后,小車未來要經過的節點發生改變,從而引起路徑上節點的動態屬性的變化；二是小車按照規劃好的路徑移動時,引起小車路徑上節點動態屬性集合中二元組信息的更新或刪除.

1)二元組的增加

① 假設小車i規劃出來的路徑為(x1,y1),(x2,y2),···,(xi,yi),i代表的是節點編號,則依次計算起點到節點1,節點2,…,節點i的理想時間,記為t1,t2,···,ti；

② 將二元組 ＜i,t1＞,＜i,t2＞,···,＜i,ti＞加入到各個節點的動態屬性集合V1,V2,···,Vi中.

2)二元組的更新

① 小車i沿著規劃好的路徑前進,每經過一個節點,計算其經過當前節點所用的時間,記為t′；

② 對于小車i路徑上節點的動態屬性集合V中值為＜i,ti＞ 的 二元組,更新為＜i,ti-t′＞.

3)二元組的刪除

小車i沿著規劃好的路徑前進,假設當前經過的節點為n(xn,yn),則把二元組＜i,tn＞從 節點n(xn,yn)的動態屬性集合V中刪除.

(2)潛在擁擠節點判斷

假設當前搜索的節點為n,判斷節點n對于當前搜索路徑的AGV 是否是潛在擁擠節點的依據是節點n動態屬性集合V中符合下面時間約束的AGV 數量是否大于擁擠閾值.

時間約束為：

其中,t為當前搜索路徑的AGV 從起始點到達節點n的時間,ti為 其他已經規劃好路徑的AGV 經過節點n的時間,ti的 值可查詢節點n的 動態屬性集合V,e代表統計小車數量的時間范圍.

記V中滿足上述約束條件的小車數量為Vcount.

對于節點n,如果Vcount＞P(P節點的擁堵閾值),則說明節點n將在經過時間t后發生擁擠,即節點n是潛在擁擠節點,當前搜索路徑的小車應該規避節點n；如果Vcount≤P,則說明節點n不是潛在的擁擠節點,當前搜索路徑的小車可以從節點n通過.

(3)估計代價計算

假設小車i的 起點為(xstart,ystart),終點為(xend,yend),

則對節點n(xn,yn)的 估計代價H(n)為：

其中,λ 表示節點n是 否會發生擁擠,λ =1,表示將會發生擁堵或已經擁堵,λ =0,表示不會發生擁堵.b是代價系數,表示發生擁堵時經過節點n的代價.

則最終節點n的代價函數為：

(4)CAA*算法具體流程

算法具體的搜索過程如下：

1)初始化,創建開啟列表(open 表)和關閉列表(close 表),開啟列表存儲的是待搜索的候選節點,關閉列表存儲的是已經搜索過的節點.

2)把起點加入open 表中.

3)檢查open 表,假如為空,則轉到步驟7).假如不為空,則執行步驟4).

4)選擇open 表中代價最小的點作為當前點,檢查當前點是否是終點,假如是則轉到步驟5),否則將當前點的子節點加入open 表中,其中子節點需滿足以下約束：① 子節點可達；② 子節點不在open 表中；③ 子節點不在close 表中(子節點沒有被搜索過).并記錄子節點的父節點為當前點,最后將當前點加入close 表中.轉到步驟3).

5)將終點加入path 表中,并沿著父節點移動,將其加入path 表中,得到的就是最短路徑,將path 表反向輸出即得到了最終的最短路徑.

6)計算當前小車理想狀態下經過各節點的時間,組成二元組,加入到路徑上的各個節點的動態屬性集合V中.

7)結束搜索.

(5)性能分析

本文算法是在A*的基礎上改進而來的,和A*一樣,都是一種啟發式的Dijkstra 算法,大大減少搜索的柵格節點數量,從而減少了搜索時間,當然,代價是有可能搜索到的路徑不是最優解,是次優解,但是在AGV 快遞分揀這種不要求最優解的場景,次優解也是可以接受的.

本文算法和A*算法的時間性能大致相當,是毫秒級的,并且算法穩定,滿足實時路徑規劃的要求.

4 實驗結果及分析

4.1 實驗設計

結合某實際場地的設計,仿真實驗的場地大小柵格化后為91 格×62 格.整個場地共有34 個上包點(左邊16 個,右邊18 個),中間是投放口,共270 個.任務的起點是上包點,終點是投放口,小車到達終點后,將貨物倒下,則當前任務完成,然后回到某一個上包點等待下一個任務.

實驗中任務的終點(投放口)是隨機生成的,每次實驗A*算法和CAA*使用相同的隨機種子,生成偽隨機數列,保證了實驗生成的任務序列是一樣的.

節點的擁擠閾值P定義為某一時間范圍內(文中e的值)通過該節點而不引起堵塞的最大小車數量.節點的擁擠閾值除了和時間范圍的大小有關外,還和該節點及其周圍節點的設計、經過該節點和周圍節點的小車的運動速度等因素有關,所以節點的實際擁擠閾值是很難準確計算出來的,但是,根據這些因素可以大致的估計出擁擠閾值的范圍.為了確定最佳擁擠閾值,本文使用不同的擁擠閾值P進行實驗,實驗中的e取固定值,為AGV 小車走過4 個節點距離所用的時間.結合擁擠閾值的定義可以看出,P的值必定不會太大(如果e取值大一點,相應的P也會大一點),所以實驗中P的值從0 開始取,然后每間隔4 進行一次實驗.

為了確定算法能提高場地AGV 密集度和系統分揀效率,使用CAA*算法和A*算法進行仿真實驗,每次增加25 輛AGV 小車,然后統計整個場地的分揀效率.

4.2 結果與分析

實驗結果如圖1所示,橫坐標為密集度(輛/柵格),縱坐標為分揀效率(件/時).A*算法其實是CAA*在擁擠閾值P設置為正無窮時的特例,因為當擁擠閾值P設為正無窮時,Vcount≤P是永遠成立的,即節點永遠不是潛在的擁擠節點.從圖中可以看出,在低密集度(密集度＜0.05)的情況下,擁擠閾值P設置的越大,分揀效率越高,這是因為低密集度時發生堵塞的可能性低,在不堵塞的情況下,小車繞行會導致效率有一定程度的下降；在高密集度(密集度＞0.05)的情況下,發生堵塞的可能性高,規避堵塞節點帶來的效率提升大于繞行帶來的效率下降.

圖1 不同擁擠閾值和AGV 密集度下的分揀效率

表1是CAA*不同擁擠閾值下與A*峰值性能對比,可以看到,當擁擠閾值P設置為4 時,分揀效率最高,相比A*算法,場地AGV 密集度提升了28.57%,峰值分揀效率提升24.29%.

由上述分析可知,本文提出的CAA*算法在高密集度的情況下能有效減少擁堵,提高場地的峰值分揀量和場地AGV 密集度.

表1 CAA*不同擁擠閾值下與A*峰值性能對比

5 總結與展望

本文著眼于快遞包裹分揀系統的路徑規劃,提出了一種能進行擁擠預測的CAA*路徑規劃算法,解決在高密集度和較大規模的AGV 場景中AGV 相互擁擠而導致的效率下降問題.該算法在傳統A*路徑搜索算法的基礎上,引入潛在擁擠節點的概念,對柵格節點進行動態屬性表示,建立動態地圖模型,對節點未來的擁擠情況進行預測,以規避潛在擁擠節點.本文在實際場地上進行仿真,通過實驗可以看出,本文算法在高密集度、AGV 數量較多的情況下確實可以有效的避免擁擠,提升場地AGV 密集度和分揀效率.本文算法仿真峰值分揀效率比A*提升了24.29%,AGV 密集度提升了28.57%.

本文算法也存在一些不足,從實驗結果可以看到,在同一個場地,當密集度較低時,本文算法CAA*比A*分揀效率要低,這是由于潛在擁擠節點預測有偏差導致的,潛在擁擠節點預測有所偏差主要有以下兩個方面的原因,一是本文對潛在擁擠節點預測結果的粒度分得較粗,預測的結果只有是和否；二是采用的是全局擁擠閾值,實際上不同地圖節點會發生擁堵的閾值應該是不同的.因此,下一步的工作,我將從這兩個方面入手,一是可以嘗試將預測結果用概率表示,代表擁擠的程度,對預測結果的粒度進行細分；二是使用局部動態擁擠閾值,使得節點設置的擁擠閾值更接近實際的擁擠閾值.