楊 瑩，張 莉，郭瑞鴻，孟俊熙，曹 洋

(西安工程大學(xué) 電子信息學(xué)院，陜西 西安 710600)

0 引言

隨著電子商務(wù)的迅猛發(fā)展，快遞包裹數(shù)量急劇增加，傳統(tǒng)的人工分揀已不能滿足要求[1]。自動分揀系統(tǒng)[2]能有效解決人工分揀帶來的問題，該系統(tǒng)具有能連續(xù)大批量地分揀運作，分揀誤差率極低，分揀現(xiàn)場基本實現(xiàn)無人化的特點，因此被廣泛應(yīng)用于現(xiàn)代物流領(lǐng)域[3-6]。

基于智能傳送帶的快遞包裹自動分揀系統(tǒng)[7]包含及包裹分揀和路徑規(guī)劃兩個重要的組成部分。國內(nèi)外研究學(xué)者在路徑規(guī)劃問題[8-10]上做了很多研究。張丹露等[11]提出動態(tài)加權(quán)地圖與預(yù)約表改進下的A*算法解決智能倉庫中多機器人的協(xié)同問題；FEDTKE等[12]引入隨機搜索和模擬退火算法解決分揀輸送系統(tǒng)中多出入口目的地分配問題；LYU等[13]針對柔性制造系統(tǒng)中的機器和自動導(dǎo)引小車(Automatic Guided Vehicle, AGV)調(diào)度的問題，提出一種基于時間窗口的遺傳算法與Dijkstra算法相結(jié)合的方法；JERALD等[14]在柔性制造系統(tǒng)調(diào)度優(yōu)化問題上對幾種智能算法進行了對比；李軍軍等[15]通過在誘導(dǎo)蟻群粒子群狀態(tài)轉(zhuǎn)移規(guī)則中增加誘導(dǎo)因子，避免AGV擁堵。目前研究內(nèi)容多集中在AGV小車的路徑規(guī)劃上，并且只能分揀特定尺寸的包裹，對于訂單量大的物流中心，分揀機的效率高于AGV。

本文擬以快速搜索隨機樹(Rapialy-exploring Random Trees algorithm, RRT)算法為基礎(chǔ)算法來規(guī)劃快遞包裹在智能傳送帶上的輸送路線。RRT算法[16]具有對地圖無需建模的優(yōu)點，并且計算的復(fù)雜度不會隨著障礙的增加而顯著變化，可在復(fù)雜環(huán)境下找到路徑規(guī)劃的可行解，因而得到了廣泛的應(yīng)用。莫棟成等[17]提出一種變概率雙向搜索，加快了搜索效率；張煜等[18]通過改進RRT節(jié)點采樣方式和擴展方式，并結(jié)合滑動窗口法實現(xiàn)在復(fù)雜動態(tài)環(huán)境下的航跡規(guī)劃；DU等[19]提出一種基于漸進最優(yōu)的RRT*的動態(tài)環(huán)境中路徑規(guī)劃算法，其中采用了人工勢場法與Voronoi圖結(jié)合的啟發(fā)式函數(shù)來提高采樣效率。

綜上所述，RRT算法改進主要在節(jié)點擴展和路徑優(yōu)化方面，為了提高規(guī)劃路徑的速度以及路徑規(guī)劃的質(zhì)量，本文針對RRT算法全局采樣、方向隨機的問題，引入人工勢場中的引力分量，減少搜索區(qū)域，提高節(jié)點擴展的方向性；對于節(jié)點易進入故障區(qū)域需重新采樣的問題，引入局部避障策略，通過評價函數(shù)在規(guī)定的可選直線中選取最優(yōu)線段作為執(zhí)行路徑；對于規(guī)劃得到的路徑進行二次優(yōu)化，以提高路徑質(zhì)量。

1 問題描述

1.1 智能包裹分揀系統(tǒng)概述

自動分揀系統(tǒng)是先進配送中心所必需的設(shè)施條件之一。本文以蜂窩模塊化設(shè)計的分揀系統(tǒng)[20]為應(yīng)用平臺，如圖1所示。

如圖1所示，每個單元模塊中有3個萬向輪，萬向輪有正反兩個方向，萬向輪之間相互配合可實現(xiàn)包裹多向自由傳送，只需提前規(guī)劃好包裹的規(guī)劃軌跡，就可以同時將多個貨物分別傳送到不同的分揀口。

快遞包裹的路徑規(guī)劃優(yōu)化問題可描述為：某封閉區(qū)域內(nèi)包裹繞開模塊化故障范圍的路徑規(guī)劃，其中地圖建模主要來自于監(jiān)控中心采集的智能包裹分揀系統(tǒng)平面圖，提取其中的故障模塊信息，通過路徑搜索尋找從起點到終點之間符合約束的路徑。

1.2 環(huán)境建模

為了計算方便，將智能包裹分揀系統(tǒng)中的故障單元虛擬為單位圓，如圖2中黑色單位圓所示。并設(shè)置一定范圍的安全區(qū)域以便檢修人員進行處理。設(shè)定左下角為包裹入口，右上角為包裹出口。

2 基本RRT算法

對于給定的狀態(tài)空間，初始化包裹入口(q_init)和包裹出口(q_goal)節(jié)點，包裹入口為隨機樹的根節(jié)點，通過逐漸增加葉節(jié)點的方式生成隨機樹，當(dāng)隨機樹中的節(jié)點包含出口點或出口區(qū)域時，隨機樹擴展停止。此時，可從隨機樹中找到從起點到終點的路徑。隨機樹的擴展方式如圖3所示。

圖中：q_rand作為搜索樹中當(dāng)前節(jié)點(q_near)的子目標(biāo)點，具有全局搜索、無方向的特點;q_new為擴展的下一步節(jié)點。在改進過程中設(shè)置一定概率指向目標(biāo)點，可以加快搜索樹向目標(biāo)點生長的速度。加入搜索概率的RRT算法實現(xiàn)如圖4所示。

以一定概率指向目標(biāo)點的策略可以使得隨機樹在一定程度上偏向目標(biāo)點生長，但是搜索隨機樹的隨機性依然很強。并且搜索樹在生長過程中有多枝的情況，在隨機樹生長過程中更希望保留主干，避免多次搜索的狀況。

3 改進RRT算法

基礎(chǔ)RRT算法存在隨機性強，路徑非最優(yōu)的問題，改進算法分別從增加引力分量、局部避障和平滑路徑3方面來進行闡述，為驗證算法的有效性，本文通過與其他改進算法作對比，說明了該改進算法的優(yōu)越性。

3.1 增加引力分量

基本RRT算法有很強的隨機性，引入人工勢場中的引力分量，可在節(jié)點擴展過程中進行方向修正，改變不平滑的缺點。

通過加入人工勢場中的引力分力思想，可使得目標(biāo)點對于當(dāng)前節(jié)點具有引力作用，如圖5所示，因此當(dāng)前節(jié)點的生長函數(shù)F(n)由隨機樹擴展節(jié)點的隨機性與目標(biāo)點的吸引力共同作用影響。此時

F(n)=R(n)+G(n)。

(1)

式中：R(n)為當(dāng)前點到新節(jié)點的隨機生長函數(shù)，G(n)為目標(biāo)點的引力函數(shù)。

目標(biāo)點對于當(dāng)前點的引力勢場函數(shù)為：

(2)

其中目標(biāo)點對于當(dāng)前點的引力為對應(yīng)引力場的負梯度，得到相應(yīng)的引力函數(shù)為

G(n)=kp‖q_goal-q_near‖。

(3)

此時，在F(n)方向上生成的節(jié)點q_new為：

q_new=q_near+q_dist×(‖q_rand-

q_near‖+kp×‖q_goal-q_near‖)。

(4)

加入引力分量使得節(jié)點在擴展過程中受到目標(biāo)點的吸引力而偏向于目標(biāo)點生長，其中kp參數(shù)的設(shè)置影響隨機樹的生長，對于在無障礙物區(qū)域時，參數(shù)設(shè)置大一些可加速隨機樹朝著目標(biāo)點生長，在障礙物區(qū)域附近時，應(yīng)減弱目標(biāo)點的引力作用，使得隨機樹繞開障礙物生長。

3.2 局部避障算法

隨機樹在擴展過程中對于進入障礙物的節(jié)點會以重新采樣的方式繞開障礙物，多次采樣會影響路徑生成的質(zhì)量，當(dāng)環(huán)境復(fù)雜時會出現(xiàn)多次采樣的情況，因此算法改進引入扇形區(qū)域線段避障(如圖6)，通過評價扇形內(nèi)生成線段的安全性，進而成功避開障礙物區(qū)。

在包裹運行過程中，每一個運動周期內(nèi)的環(huán)境信息總在更新，在該窗口內(nèi)進行局部路徑規(guī)劃，選取最優(yōu)線段，找出當(dāng)前節(jié)點到目標(biāo)點可行的局部路徑。根據(jù)包裹的轉(zhuǎn)向能力在局部區(qū)域內(nèi)設(shè)置若干條待選線段，通過評價函數(shù)選出最優(yōu)線段。

在選擇最優(yōu)線段前，需要對各條線段進行檢測判斷，若扇形區(qū)域內(nèi)的線段沒有與障礙物發(fā)生碰撞，稱這樣的線段為可選線段，剔除發(fā)生碰撞的線段。

對于可選線段，選擇線段終點到目標(biāo)點之間的距離LEG作為搜索的評價函數(shù)，可選線段的可行程度評價函數(shù)為：

F=LEG。

(5)

3.3 平滑路徑算法

RRT算法規(guī)劃后的路徑中存在最大的問題就是平滑度的問題。為了提高包裹在傳輸過程中的平滑轉(zhuǎn)向，本文提出了二次優(yōu)化的方法，以期得到較為理想的軌跡。

刪除節(jié)點流程圖如圖7所示。第一次優(yōu)化時，以第一個節(jié)點為根節(jié)點，判斷后續(xù)節(jié)點與根節(jié)點之間是否穿過障礙物，若穿過障礙物，將前一個節(jié)點保存在新數(shù)組中并將此節(jié)點記為根節(jié)點，與后續(xù)節(jié)點進行判斷直到遍歷所有節(jié)點。第一次優(yōu)化完成。

對于一次平滑得到的路徑點依然存在轉(zhuǎn)折點轉(zhuǎn)向不夠圓滑的現(xiàn)象，繼續(xù)進行二次平滑。平滑節(jié)點流程圖如圖8所示，本文選擇貝塞爾曲線公式進行處理，假設(shè)一次平滑后路徑節(jié)點數(shù)為n個，依次在兩節(jié)點之間取中間節(jié)點，則可取n-1個節(jié)點，判斷相連節(jié)點之間的線段是否在障礙物區(qū)域內(nèi)，若不在障礙物區(qū)域內(nèi)，將中間節(jié)點替換右側(cè)節(jié)點并保存在數(shù)組中。若在障礙物區(qū)域內(nèi)，則將保留原有節(jié)點，依次類推，可得到最后一個節(jié)點，將該節(jié)點保存在數(shù)組中。由此得到整個平滑后的路徑節(jié)點。

以第一次的優(yōu)化結(jié)果進行再次優(yōu)化，可以提高軌跡的平滑度，滿足包裹實際轉(zhuǎn)向。

3.4 算法實現(xiàn)

綜合前文所述，所提算法的實現(xiàn)流程如圖9所示，具體步驟如下：

步驟1利用圖像識別獲取障礙物的位置信息，設(shè)置算法參數(shù)。

步驟2判斷當(dāng)前節(jié)點與目標(biāo)點之間的位置關(guān)系。若當(dāng)前點在目標(biāo)區(qū)域內(nèi)，則路徑規(guī)劃結(jié)束，否則，執(zhí)行步驟3。

步驟3在全局范圍內(nèi)搜索子目標(biāo)點，計算隨機樹中距離子目標(biāo)點最近的節(jié)點q_near，并在合力方向上擴展一定的步長得到節(jié)點q_new。

步驟4判斷包裹當(dāng)前所走路徑是否進入障礙物區(qū)域，是則采用局部區(qū)域避障;否則將q_new節(jié)點保存在隨機樹中，并返回步驟2。

通過上述改進提高包裹傳輸?shù)乃俣群唾|(zhì)量，并對規(guī)劃后的路徑做平滑處理，使包裹傳輸?shù)穆窂礁屿`活。

4 仿真對比及探究

實驗平臺為MATLAB 7.0版本，實驗環(huán)境為智能包裹分揀系統(tǒng)模擬平臺，期望的結(jié)果是包裹從起始點出發(fā)，繞過故障模塊到達指定包裹出口位置，結(jié)合RRT算法進行路徑規(guī)劃，并成功抵達目標(biāo)區(qū)域。

RRT算法具有隨機性強、全局范圍搜索、搜索質(zhì)量不高等特點，本文依次從節(jié)點生成、局部區(qū)域修正節(jié)點、路徑平滑處理方面對RRT算法進行改進，改進效果如圖10所示。

圖10a中加入人工勢場中的引力分量，使得路徑點生成偏向于目標(biāo)方向。對于進入障礙物區(qū)域的節(jié)點采用局部避障策略，對局部路徑進行調(diào)整，使包裹避開障礙物以提高算法的性能，仿真結(jié)果如圖10b所示，該策略在避障過程中采取了局部最優(yōu)的路徑選擇，符合包裹在實際情況中的轉(zhuǎn)向要求。對于規(guī)劃后的路徑存在拐點較多、轉(zhuǎn)向不平滑的特點，采取二次平滑的優(yōu)化策略，首先減少路徑拐點的個數(shù)，然后對尖角拐點進行處理，使得規(guī)劃路徑更加平滑。軌跡優(yōu)化如圖10c所示，規(guī)劃后的路徑使得路徑更短，滿足包裹在智能包裹分揀系統(tǒng)上的路徑規(guī)劃要求。

為了驗證該改進算法的有效性，本文在局部避障時加入人工勢場法局部優(yōu)化進行改進，改進效果如圖11所示。

從圖中可以看到，采用人工勢場法進行避障也可得到良好的路徑。但是由于人工勢場法中的引力場和斥力場勢能函數(shù)需要合理設(shè)置以滿足轉(zhuǎn)向要求，并且在仿真過程中需要對參數(shù)、步長進行合理設(shè)置。通過以上方法進行改進，對比各算法的仿真時間與路徑長度，結(jié)果如圖12和表1所示。

表1 算法仿真結(jié)果對比

圖12和表1數(shù)據(jù)為獨立運行30次得到的平均值，路徑長度的計算為算法改進后得到的數(shù)據(jù)結(jié)果。從運行時間上來看，本文改進算法平均運行時間最短為0.122 7 s，與傳統(tǒng)RRT算法相比提高了73.22%，相比于人工勢場法的局部優(yōu)化提高了94.46%，從方差結(jié)果來看，本文改進算法平均運行時間較穩(wěn)定，基本維持在0.122 7 s左右；從路徑長度來看，本文改進算法平均路徑長度值為1 098 m，比傳統(tǒng)RRT算法平均路徑長度減少了約90.42%，與人工勢場法局部優(yōu)化獲得的路徑長度基本一致，從方差結(jié)果來看，本文改進算法路徑長度較穩(wěn)定，在多次運行的情況下，路徑長度基本維持在1 098 m左右；綜合來看，本文改進算法運行效果最好。其中，改進人工勢場法局部優(yōu)化提高了算法的準(zhǔn)確率卻是以運行時長為代價，傳統(tǒng)RRT算法雖然運行時間較短，但忽略了路徑生成的質(zhì)量。

為了驗證本文改進算法的有效性，選取經(jīng)典避障算法中的A*算法和蟻群算法進行對比，對比結(jié)果如圖13和圖14所示。

對蟻群算法、A*算法及本文改進算法進行多次仿真，得出路徑長度值相差不大，但在仿真時長上表現(xiàn)為T蟻群>TA*>T本文改進，從圖14中可以看出本文改進算法仿真時長最短，效果最好。為了驗證本文改進算法的適應(yīng)性，選取以下幾種工作環(huán)境進行仿真。

在簡單工作環(huán)境以及復(fù)雜環(huán)境中進行仿真實驗，可以看到包裹安全無碰撞地到達分揀出口，如圖15所示，黑色線條為算法規(guī)劃出來的包裹行駛軌跡。

5 結(jié)束語

針對基礎(chǔ)RRT算法隨機性強、路徑生成質(zhì)量不高、路徑非漸進最優(yōu)等問題，本文主要做了以下幾方面的工作：

(1)分析了RRT算法原理，并在隨機樹擴展過程中引入人工勢場引力分量，使節(jié)點擴展更有效。

(2)針對RRT算法中對于處于障礙物區(qū)域內(nèi)的節(jié)點需要重新迭代的情況，引入扇形避障策略，并對規(guī)劃后的軌跡進行二次平滑處理以平滑路徑。

(3)通過與加入人工勢場法局部優(yōu)化的改進算法對比驗證了本文改進算法的有效性，并且路徑更加趨近于最優(yōu)路徑。

鑒于RRT算法易于實現(xiàn)的優(yōu)點，在接下來的工作中將把該改進算法應(yīng)用到多包裹的路徑規(guī)劃中，并對其進行仿真。