基于改進蟻群算法的倉儲物流機器人路徑規劃*

辜 勇 段晶晶 蘇宇霞 袁源乙

(武漢理工大學物流工程學院 武漢 430063)

0 引 言

現代物流業高速發展的過程中，智能倉儲是其中的關鍵環節，用以保證物流過程能夠對海量物料需求做出及時反饋，滿足客戶的需求.在倉儲活動中，引入倉儲物流機器人代替傳統人工作業已成為必然趨勢.亞馬遜倉庫，京東“亞洲一號”，海康威視等企業紛紛應用倉儲物流機器人作業，顯示了智能倉儲的快速興起和發展.其中倉儲物流機器人路徑規劃是目前的熱門研宄方向，在倉儲物流[1]、工業生產[2]、分揀配送[3]等領域有著廣泛的應用前景.移動機器人路徑規劃是指按照目標函數，避開所有障礙物，選擇出一條從起點到終點的最優或次優的連續路徑.其本質是在若干約束條件下得到最優解或可行解的問題.

常見的路徑規劃方法[4]有：人工勢場法，模糊邏輯算法，神經網絡法，智能優化算法等.Chen等[5]采用兩階段混沌優化方法，借助改進人工勢場，有效克服了目標不可達的缺點，實現機器人路徑規劃.Noto等[6]在傳統Dijkstra算法的基礎上進行擴展，從初始點和目標點同時向外搜索移動機器人的最短路徑，直到搜索結果重疊結束，以此加快收斂速度.王雷等[7]在遺傳算法中加入人工勢場對初始種群進行引導，克服基本遺傳算法收斂速度慢等缺點.除此之外，蟻群算法常用于路徑規劃問題，是一種較為成熟和有效的智能化方法，具有隨機并行搜索能力，許多學者對此展開大量研究.Qiang等[8]為避免機器人在早期的盲目搜索尋路，在蟻群算法中使用偽隨機狀態轉移規則選擇路徑，并且引入動態懲罰方法解決死鎖問題，有效提高了全局最優搜索能力和收斂速度.萬曉鳳等[9]在蟻群算法中利用揮發自適應方式更新信息素，有效避免陷入局部最優.王雷等[10]運用改進蟻群算法解決了機器人易陷入凹型障礙并在復雜環境搜索效率低的問題.杜磊等[11]在蟻群算法轉移概率中引入自適應期望函數，通過增加相鄰節點被選擇概率的差距，避免路徑迂回的出現.封聲飛等[12]制定自適應的信息素更新策略，使蟻群算法在迭代后期仍具有較強的搜索能力.以上算法對路徑尋優問題提出改進，針對的是不同類型的障礙物環境，對倉儲環境下障礙物多變的情況沒有普遍適用性.并且多數蟻群算法在搜索過程中易出現算法不穩定的問題.

此外，對于路徑平滑處理方面，孫瑞等[13]提出控制點轉移策略，通過控制路徑走向的柵格中心點向柵格角頂點的轉移，實現了路徑規劃的平滑改進.王紅衛等[14]對A*算法規劃的路徑進行平滑優化，將兩節點之間無障礙物的中間節點刪除，建立平滑路徑.上述算法側重于轉折角度大、折點多的路徑平滑處理，且算法較為復雜.

本文在基本蟻群算法的基礎上,提出一種改進蟻群算法.通過對蟻群的轉移規則進行改進，隨迭代次數動態改變信息素殘留因子，使得移動機器人適應不同的障礙物環境變化；并對規劃路徑結果進行二次優化的處理.最后，通過仿真實驗與其他算法對比，在不同復雜度的倉儲環境下進行實驗，結果驗證了改進蟻群算法的有效性.

1 環境描述

常見的環境建模方法主要有可視圖法、拓撲法、自由空間法,以及柵格法等.可視圖法雖然能夠得到最短路徑，但將移動機器人視作質點，忽略尺寸大小，使得移動機器人在經過障礙物頂點時可能造成碰撞，且搜索時間較長.拓撲法利用拓撲特征大大縮小了搜索空間，但建立拓撲網絡卻十分復雜.自由空間法比較靈活，但其復雜程度與障礙物的多少成正比，并且有時無法獲得最短路徑.柵格法[15]從橫、縱兩個維度，將移動機器人工作環境分解成一系列的網格單元.將環境中的障礙物用柵格進行分割，不滿一個柵格的按照一個計算.通過以柵格為單位記錄環境信息，對有障礙物的地方進行區分，再利用路徑尋優方法使移動機器人避開障礙物.

采用柵格化方法進行環境建模，見圖1，在環境中建立直角坐標系，按照倉儲物流機器人行走和轉折時占用的最小空間，來切割橫向和縱向區域.每個柵格都有確定的坐標(x,y)，x=row，y=col.其中:row為柵格所在的行號,col為柵格所在的列號.并用屬性obstacle記錄環境地圖情況，當柵格被障礙物占據，如obstacle(20，1)=1；否則，obstacle(20，1)=0.

圖1 環境建模

機器人在二維平面上的有限區域內工作，機器人在一個柵格上可以沿8個方向到達相鄰的柵格，見圖2.

圖2 機器人運動方向

2 基本蟻群算法

2.1 啟發函數

蟻群算法是一種啟發式算法，在選擇下一個節點時，優先選擇離自己最近的節點.定義人工蟻群的螞蟻數目為m，當前節點i到節點j的距離為dij(i,j=1,2,…，n).兩節點間的啟發函數(或者可見度)為ηij，兩節點間的信息素濃度為τij.則螞蟻k從節點i轉移至節點j的轉移概率pkij.定義屬性ηij為兩節點間的啟發函數(或者可見度)，是距離的倒數.

ηij=1/dij

(1)

dij=((ix-jx)2+(iy-jy)2)1/2

(2)

式中：dij為節點i和節點j之間的歐幾里得距離；ix，iy為節點i的橫縱坐標；jx，jy是節點j的橫縱坐標.

2.2 信息素濃度

信息素濃度是螞蟻群體協作發揮作用的關鍵.初始設置全局的信息素濃度均相等.隨著不斷探索和行走，螞蟻在走過的路線上會留下與路徑長度有關的信息素，引導后續螞蟻選擇優勢路徑.因此在全部螞蟻完成一次循環后，對各路徑上的信息素含量進行更新，更新規則為

τij(NC+1)=(1-ρ)τij(NC)+Δτij(NC)

(3)

(4)

式中：ρ為信息素揮發因子，ρ∈(0,1).Δτij(NC)第NC代中節點i到節點j之間路徑上信息素增量.Δτkij(NC)為螞蟻k本次迭代過程中在節點i和節點j之間的路徑上留下的信息素含量.

2.3 轉移概率

螞蟻k從節點i轉移到節點j的概率pkij為

(5)

式中：allowedk為螞蟻k在該階段可訪問的節點集合；?為信息素重要性因子，其值越大，表示螞蟻越易選擇有較多螞蟻選擇過的路徑；β為啟發函數重要性因子，其值越大，表示螞蟻更易選擇離自己最近的節點.

3 改進蟻群算法

3.1 轉移概率

在柵格化環境下進行節點選擇時，節點之間的路徑長度已被標準化.

(6)

ηij=ζ/Lj

(7)

式中：Lj為節點j到終點之間的歐幾里得距離；ζ為常數，通常節點距離終點距離較大，使得啟發函數值ηij較小.因此可根據信息素因子τij的數量級，對啟發函數進行擴大.

再者，引入變量q0，螞蟻選擇下一個節點S按式(8)的規則進行.

(8)

式中：q為隨機變量，q∈(0,1).即在隨機變量q小于變量q0時，螞蟻選擇轉移概率最大的節點進行訪問，否則，就隨機選擇節點進行訪問.隨著迭代的進行，q0的值先變大再變小，這使各螞蟻在前期隨機選擇節點，有助于擴大全局搜索能力，尋找到優勢路徑；中期則選擇概率最大的節點，及時收斂；后期又隨機選擇節點，有助于跳出局部最優.

3.2 信息素更新規則

信息素揮發因子ρ一般是常數，不利于蟻群算法在迭代過程中實現快速收斂與跳出局部最優之間的平衡.因此，在算法前期希望快速找到優勢路徑，需要一個較大ρ值；而在算法后期，為了避免陷入局部最優，需要擴大搜索范圍，需要一個較小的ρ值，見圖2.為此，ρ值隨著迭代的進行，應該是一個由大到小的變化過程.可按照式(9)進行自適應變化.

圖3 ρ隨迭代變化函數圖

(9)

式中：c為常數，根據具體情況調整.

3.3 目標函數

倉儲物流機器人路徑規劃的目的是能夠找到一條從起點到終點的無障礙路徑.假設機器人以勻速行走，那么路徑最短的同時也能達到時間最短.因此，取路徑規劃的總長度L為目標函數,即

(10)

式中：dtij是在第t步從節點i到節點j的歐幾里得距離.螞蟻經歷T步到達終點.

3.4 路徑平滑

螞蟻通過在柵格化環境中直線行走，在行走路徑過程中，經過障礙物會有較多轉折點.在實際工作環境下，移動機器人所得到的路徑雖然總體上長度較短，但存在著個別不必要的折角，機器人在經過拐角時需要調整自身狀態以適應角度轉變，導致行駛難度加大，行駛時間增加.

為增加機器人行走路徑的實際可行性，需要對改進蟻群算法規劃出的路徑進行平滑處理.假設改進蟻群算法的路徑規劃結果為Path，為二維數組[x(1),y(1);x(2),y(2);…；x(n),y(n)]；經過平滑處理后的結果為Smooth_Path，為二維數組[a(1),b(1);a(2),b(1);…；a(n),b(n)].平滑路徑是通過使平滑前后路徑偏離程度最小，見式(11)；同時路徑的總轉折角度較小，為

(11)

(12)

因此，路徑平滑優化的目標函數為

(13)

式中：λ，μ為常數參數.通過調整λ和μ的值來找到最優化路徑.

3.5 改進蟻群算法步驟

移動機器人路徑規劃包含環境的柵格法建模、改進蟻群算法進行路徑規劃、路徑平滑處理等過程.具體流程描述見圖4.

圖4 算法步驟圖

4 仿真實驗

經過初步實驗，改進蟻群算法的參數設置：NCmax為20；m為20；?為1；β為7；Q為100；ζ為10；c為5；λ為0.5；μ為0.5.

轉移概率中隨機變量q0為

(14)

4.1 2020環境下算法比較

選取文獻[12]的算例，該算例環境是較為規則的大型障礙物倉儲環境.其運行結果與改進蟻群算法的行走路徑對比，見圖5a).其次，選取文獻[9]的算例，該算例環境是零散分布的眾多小型障礙物倉儲環境.其運行結果與改進蟻群算法的行走路徑對比，見圖5b).

圖5 文獻[12]、[9]與改進蟻群算法對比

采用文獻[12]的共同算例，算法均獨立運行 20 次，比較仿真結果，兩個算例的衡量尺度均為最優路徑長度和收斂代數，見表1.由于路徑的平滑處理，使得改進蟻群算法的最優路徑長度在兩種條件下，較文獻[12]均有明顯改進.并且轉移概率中增大啟發函數的作用，將隨機性選擇和確定性選擇相結合，使收斂速度更快，更穩定.對比文獻[12]，收斂代數平均值縮短一半，標準差減少16.4%；對比文獻[9]，收斂代數平均值減少91.8%，收斂速度大幅增加.通過直觀觀察圖4～5可知，改進蟻群算法路徑更加平緩，轉折角度更小.

4.2 30×30環境下算法比較

對復雜環境進行擴大，采用文獻[7]的算例進行計算，對比結果見圖6a).經過20次仿真，實驗數據見表1.改進蟻群算法仍然具有較強優勢.在最優路徑方面，改進蟻群算法的最大值為43.571，小于文獻[7]的最優路徑平均值48.53，最優路徑平均值要縮短10.2%；最優路徑最小值、最大值和平均值均小于文獻[12].與文獻[12]對比，收斂速度更快、更穩定，見圖6b).

4.3 障礙復雜程度不同的環境

為檢驗改進蟻群算法的普遍適應性.在20×20環境下利用MATLAB隨機生成四組障礙物環境，障礙物比例分別是20%，25%，30%和35%，表示為環境1、2、3和4.平滑處理前后的算法運行結果對比，見圖7.在30×30環境下障礙物比例是20%，表示為環境5，平滑處理前后的算法運行結果對比見圖8.觀察未平滑優化的路徑規劃結果，改進蟻群算法在障礙物占比不同的情況下，均能找到已知最優解；平滑優化之后，路徑長度更短，減少了總轉折角度.

為了進一步實驗改進蟻群算法的效果，在五種環境下，分別對基本蟻群算法(ACO)和改進蟻群算法(IACO)在上述五種環境下，分別進行仿真實驗，運行20次.對比結果見表2、表3.

圖6 文獻[7]、[12]與本文算法對比

表1 文獻[12]、[9]、[7]與本文仿真結果比較 m

圖7 20×20環境下不同復雜度路徑尋優圖

圖8 30×30環境下路徑尋優圖(環境5)

表2 收斂所需的循環次數

表3 最優收斂長度

由表2～3可知，改進蟻群算法運行效率高，收斂所需的迭代次數遠低于基本蟻群算法；并且最優路徑長度更短，結果更加穩定.改進蟻群算法擴大啟發函數的影響力，使得算法初期就能夠引導尋找到優勢路徑；轉移概率采用確定性與隨機性相結合的方式，有利于及時跳出局部障礙物，使得改進蟻群算法能夠快速收斂至較優結果.

5 結 束 語

通過對倉儲物流機器人路徑規劃問題進行柵格化建模，設計了一種新的求解機器人避障路徑的改進蟻群算法.該算法改進路徑選擇參數，優化轉移規則和信息素更新條件，并對路徑結果進行平滑處理.隨著算法迭代變化，對路徑選擇以及信息素揮發系數進行調整，在保證算法全局搜索最優的同時，能夠快速收斂，并且有足夠的穩定性.平滑處理后的路線更符合實際環境中機器人行走條件，減少能耗及縮短距離，也更加安全.