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

辜 勇 段晶晶 蘇宇霞 袁源乙

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

0 引 言

現(xiàn)代物流業(yè)高速發(fā)展的過程中，智能倉儲是其中的關(guān)鍵環(huán)節(jié)，用以保證物流過程能夠?qū)Ａ课锪闲枨笞龀黾皶r反饋，滿足客戶的需求.在倉儲活動中，引入倉儲物流機器人代替?zhèn)鹘y(tǒng)人工作業(yè)已成為必然趨勢.亞馬遜倉庫，京東“亞洲一號”，?？低暤绕髽I(yè)紛紛應(yīng)用倉儲物流機器人作業(yè)，顯示了智能倉儲的快速興起和發(fā)展.其中倉儲物流機器人路徑規(guī)劃是目前的熱門研宄方向，在倉儲物流[1]、工業(yè)生產(chǎn)[2]、分揀配送[3]等領(lǐng)域有著廣泛的應(yīng)用前景.移動機器人路徑規(guī)劃是指按照目標(biāo)函數(shù)，避開所有障礙物，選擇出一條從起點到終點的最優(yōu)或次優(yōu)的連續(xù)路徑.其本質(zhì)是在若干約束條件下得到最優(yōu)解或可行解的問題.

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

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

本文在基本蟻群算法的基礎(chǔ)上,提出一種改進蟻群算法.通過對蟻群的轉(zhuǎn)移規(guī)則進行改進，隨迭代次數(shù)動態(tài)改變信息素殘留因子，使得移動機器人適應(yīng)不同的障礙物環(huán)境變化；并對規(guī)劃路徑結(jié)果進行二次優(yōu)化的處理.最后，通過仿真實驗與其他算法對比，在不同復(fù)雜度的倉儲環(huán)境下進行實驗，結(jié)果驗證了改進蟻群算法的有效性.

1 環(huán)境描述

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

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

圖1 環(huán)境建模

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

圖2 機器人運動方向

2 基本蟻群算法

2.1 啟發(fā)函數(shù)

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

ηij=1/dij

(1)

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

(2)

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

2.2 信息素濃度

信息素濃度是螞蟻群體協(xié)作發(fā)揮作用的關(guān)鍵.初始設(shè)置全局的信息素濃度均相等.隨著不斷探索和行走，螞蟻在走過的路線上會留下與路徑長度有關(guān)的信息素，引導(dǎo)后續(xù)螞蟻選擇優(yōu)勢路徑.因此在全部螞蟻完成一次循環(huán)后，對各路徑上的信息素含量進行更新，更新規(guī)則為

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

(3)

(4)

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

2.3 轉(zhuǎn)移概率

螞蟻k從節(jié)點i轉(zhuǎn)移到節(jié)點j的概率pkij為

(5)

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

3 改進蟻群算法

3.1 轉(zhuǎn)移概率

在柵格化環(huán)境下進行節(jié)點選擇時，節(jié)點之間的路徑長度已被標(biāo)準(zhǔn)化.

(6)

ηij=ζ/Lj

(7)

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

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

(8)

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

3.2 信息素更新規(guī)則

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

圖3 ρ隨迭代變化函數(shù)圖

(9)

式中：c為常數(shù)，根據(jù)具體情況調(diào)整.

3.3 目標(biāo)函數(shù)

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

(10)

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

3.4 路徑平滑

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

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

(11)

(12)

因此，路徑平滑優(yōu)化的目標(biāo)函數(shù)為

(13)

式中：λ，μ為常數(shù)參數(shù).通過調(diào)整λ和μ的值來找到最優(yōu)化路徑.

3.5 改進蟻群算法步驟

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

圖4 算法步驟圖

4 仿真實驗

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

轉(zhuǎn)移概率中隨機變量q0為

(14)

4.1 2020環(huán)境下算法比較

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

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

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

4.2 30×30環(huán)境下算法比較

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

4.3 障礙復(fù)雜程度不同的環(huán)境

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

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

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

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

圖7 20×20環(huán)境下不同復(fù)雜度路徑尋優(yōu)圖

圖8 30×30環(huán)境下路徑尋優(yōu)圖(環(huán)境5)

表2 收斂所需的循環(huán)次數(shù)

表3 最優(yōu)收斂長度

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

5 結(jié) 束 語

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