賀學(xué)成,呂淑靜,呂 岳

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

1 引言

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

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

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

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

2 動態(tài)環(huán)境模型

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

2.1 場地柵格化

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

柵格地圖法是目前研究最廣泛的方法之一.該方法將機(jī)器人的工作空間分解為多個簡單的區(qū)域,這些區(qū)域稱為柵格.由這些柵格構(gòu)成一個顯式的連通圖,或在搜索過程中形成隱式的連通圖,然后在圖上搜索一條從起始柵格到目標(biāo)柵格的路徑.柵格地圖信息直接與環(huán)境區(qū)域?qū)?yīng),容易創(chuàng)建和維護(hù),方便AGV 進(jìn)行定位.本文采用柵格法來建立環(huán)境模型.以AGV 小車尺寸為基礎(chǔ)確定柵格的大小,將場地映射成一系列規(guī)則的網(wǎng)格.

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

2.2 柵格節(jié)點(diǎn)的動態(tài)屬性表示

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

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

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

傳統(tǒng)的A*算法僅考慮了靜態(tài)環(huán)境信息和當(dāng)前AGV 的信息,而沒有考慮場地中其他AGV 對當(dāng)前AGV 的影響,規(guī)劃出來的路徑可能造成擁堵,尤其是高密集度AGV 場景中,擁堵嚴(yán)重時可能造成某塊區(qū)域完全堵塞,使得系統(tǒng)效率急劇下降.本文在A*算法的基礎(chǔ)上引入潛在擁擠節(jié)點(diǎn)的概念,對可能發(fā)生的擁擠情況進(jìn)行預(yù)測,在路徑規(guī)劃過程中繞過擁堵節(jié)點(diǎn)或潛在的擁堵節(jié)點(diǎn),避免擁堵.

3.1 A*算法

A*算法是Nilsson NJ[16]在Dijkstra算法基礎(chǔ)上提出的,是靜態(tài)路網(wǎng)中最有效的直接搜索方法之一.A*加入了當(dāng)前節(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的估計代價,根據(jù)起始點(diǎn)經(jīng)過當(dāng)前結(jié)點(diǎn)到達(dá)目標(biāo)點(diǎn)的代價決定搜索的方向,大大提高了Dijkstra 算法的效率.定義估價函數(shù)為：

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

假設(shè)當(dāng)前搜索的節(jié)點(diǎn)為n(xn,yn),n的父節(jié)點(diǎn)是m(xm,ym)( 搜索到了m節(jié) 點(diǎn),再往下搜索到了n,即稱m是n的父節(jié)點(diǎn)),終點(diǎn)坐標(biāo)為(xend,yend),

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

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

估計代價為當(dāng)前點(diǎn)n到終點(diǎn)的曼哈頓距離：

由式(3)和式(4)可知當(dāng)前節(jié)點(diǎn)n的最終估計函數(shù)為：

3.2 CAA*算法

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

(1)節(jié)點(diǎn)動態(tài)屬性的更新

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

1)二元組的增加

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

② 將二元組 ＜i,t1＞,＜i,t2＞,···,＜i,ti＞加入到各個節(jié)點(diǎn)的動態(tài)屬性集合V1,V2,···,Vi中.

2)二元組的更新

① 小車i沿著規(guī)劃好的路徑前進(jìn),每經(jīng)過一個節(jié)點(diǎn),計算其經(jīng)過當(dāng)前節(jié)點(diǎn)所用的時間,記為t′；

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

3)二元組的刪除

小車i沿著規(guī)劃好的路徑前進(jìn),假設(shè)當(dāng)前經(jīng)過的節(jié)點(diǎn)為n(xn,yn),則把二元組＜i,tn＞從 節(jié)點(diǎn)n(xn,yn)的動態(tài)屬性集合V中刪除.

(2)潛在擁擠節(jié)點(diǎn)判斷

假設(shè)當(dāng)前搜索的節(jié)點(diǎn)為n,判斷節(jié)點(diǎn)n對于當(dāng)前搜索路徑的AGV 是否是潛在擁擠節(jié)點(diǎn)的依據(jù)是節(jié)點(diǎn)n動態(tài)屬性集合V中符合下面時間約束的AGV 數(shù)量是否大于擁擠閾值.

時間約束為：

其中,t為當(dāng)前搜索路徑的AGV 從起始點(diǎn)到達(dá)節(jié)點(diǎn)n的時間,ti為 其他已經(jīng)規(guī)劃好路徑的AGV 經(jīng)過節(jié)點(diǎn)n的時間,ti的 值可查詢節(jié)點(diǎn)n的 動態(tài)屬性集合V,e代表統(tǒng)計小車數(shù)量的時間范圍.

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

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

(3)估計代價計算

假設(shè)小車i的 起點(diǎn)為(xstart,ystart),終點(diǎn)為(xend,yend),

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

其中,λ 表示節(jié)點(diǎn)n是 否會發(fā)生擁擠,λ =1,表示將會發(fā)生擁堵或已經(jīng)擁堵,λ =0,表示不會發(fā)生擁堵.b是代價系數(shù),表示發(fā)生擁堵時經(jīng)過節(jié)點(diǎn)n的代價.

則最終節(jié)點(diǎn)n的代價函數(shù)為：

(4)CAA*算法具體流程

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

1)初始化,創(chuàng)建開啟列表(open 表)和關(guān)閉列表(close 表),開啟列表存儲的是待搜索的候選節(jié)點(diǎn),關(guān)閉列表存儲的是已經(jīng)搜索過的節(jié)點(diǎn).

2)把起點(diǎn)加入open 表中.

3)檢查open 表,假如為空,則轉(zhuǎn)到步驟7).假如不為空,則執(zhí)行步驟4).

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

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

6)計算當(dāng)前小車?yán)硐霠顟B(tài)下經(jīng)過各節(jié)點(diǎn)的時間,組成二元組,加入到路徑上的各個節(jié)點(diǎn)的動態(tài)屬性集合V中.

7)結(jié)束搜索.

(5)性能分析

本文算法是在A*的基礎(chǔ)上改進(jìn)而來的,和A*一樣,都是一種啟發(fā)式的Dijkstra 算法,大大減少搜索的柵格節(jié)點(diǎn)數(shù)量,從而減少了搜索時間,當(dāng)然,代價是有可能搜索到的路徑不是最優(yōu)解,是次優(yōu)解,但是在AGV 快遞分揀這種不要求最優(yōu)解的場景,次優(yōu)解也是可以接受的.

本文算法和A*算法的時間性能大致相當(dāng),是毫秒級的,并且算法穩(wěn)定,滿足實時路徑規(guī)劃的要求.

4 實驗結(jié)果及分析

4.1 實驗設(shè)計

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

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

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

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

4.2 結(jié)果與分析

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

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

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

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

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

5 總結(jié)與展望

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

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