屈新懷, 單 笛, 孟冠軍

(合肥工業(yè)大學(xué) 機械工程學(xué)院,安徽 合肥 230009)

移動機器人(automated guided vehicle, AGV)導(dǎo)航運輸車也被稱作移動機器人,是一種裝有導(dǎo)航定位及安全保護裝置的、能夠按照規(guī)劃路徑行駛且具有移載功能的運輸小車。AGV最顯著的特點是無人駕駛、柔性較好、自動化與智能化水平高。隨著社會進步以及工業(yè)技術(shù)的快速發(fā)展,AGV已經(jīng)成為當(dāng)今生產(chǎn)以及自動化倉儲系統(tǒng)的重要工具之一,對AGV及其關(guān)鍵技術(shù)的研究,可以有效降低成本,提高生產(chǎn)率,而AGV路徑規(guī)劃是眾多研究中的關(guān)鍵一環(huán)[1-3]。

路徑規(guī)劃問題通常分為環(huán)境建模、路徑搜索、路徑平滑3個步驟。其中環(huán)境建模是將實際的物理空間抽象成算法能夠計算的抽象空間,現(xiàn)階段常采用柵格法、可視圖法、拓?fù)浞?、自由空間法等方法[4-5],傳統(tǒng)的路徑規(guī)劃方法有A-star算法[6]、Dijkstra算法[7]、RRT算法[8]等,但這些算法常存在魯棒性差、精度低的問題。后期學(xué)者多應(yīng)用群體智能算法，如遺傳算法[9]、蟻群算法[10]等,并對群智能算法進行改進與優(yōu)化,大大提高了路徑規(guī)劃的精度和效率[11]。

本文對障礙物進行多邊化及膨脹處理,建立多目標(biāo)適應(yīng)度函數(shù)并提出統(tǒng)一化權(quán)重系數(shù),在傳統(tǒng)粒子群算法中引入Metropolis準(zhǔn)則,加速算法跳出停滯搜索狀態(tài),引入自適應(yīng)引力系數(shù),從而提出靠近目標(biāo)的粒子群算法,并將其應(yīng)用到AGV路徑規(guī)劃中。該算法所求得的路徑長度更短,同時在路徑平滑度、算法穩(wěn)定性上表現(xiàn)更優(yōu)。

1 環(huán)境建模

1.1 問題描述及障礙物處理

靜態(tài)環(huán)境下的路徑規(guī)劃是在障礙物已知的情況下,尋找一條最優(yōu)的從起點至終點的無碰撞路徑。本文旨在求得路徑最短且AGV轉(zhuǎn)彎最平滑的路徑,即進行多目標(biāo)優(yōu)化。

在研究機器人運行路徑時不考慮AGV體積大小,故需對AGV工作空間中的障礙物進行多邊形轉(zhuǎn)換及膨脹處理,以保證AGV行駛的安全性,避免其與障礙物邊界發(fā)生擦碰。如圖1所示,先將不同形狀的障礙物按AGV體積的最大半徑進行膨脹,再轉(zhuǎn)換成凸多邊形,轉(zhuǎn)化原則為凸圓弧或不規(guī)則部分取水平或垂直的最高點切線,凹陷部分用直線填充,直線部分不進行操作。

圖1 障礙物“多邊化”及“膨脹”處理

1.2 環(huán)境建模

AGV運行環(huán)境及建模示意圖如圖2所示。圖2a中采用自由空間法為AGV工作環(huán)境建立坐標(biāo)系Oxy,黑色實心多邊形為經(jīng)多邊化及膨脹處理的障礙物,記起點坐標(biāo)為O(x0,y0),終點坐標(biāo)為G(xn,yn),從起點到終點不穿過障礙物的連線為一條有效路徑。

為確定各位置坐標(biāo)點,按障礙物頂點劃分區(qū)域,保證AGV在每個區(qū)段內(nèi)只需對一條障礙物邊界進行避障處理,從而簡化避障過程。如圖2b所示,從所有障礙物多邊形的頂點引出一條平行于y軸的虛線貫穿坐標(biāo)系,算法取初始解時在每條虛線上隨機獲取一個不在障礙物內(nèi)部的位置坐標(biāo)點Pij(xij,yij),且保證相鄰坐標(biāo)點之間的連線不穿越所有障礙物,則所有位置坐標(biāo)點的連線所構(gòu)成的由起點至終點的一條無碰路徑即可表示為Pi=(Pi0,Pi1,Pi2,…,Pij,…,Pi(n-1),Pin),其中j=0,1,…,n。若Pi中各點之間的連線不穿過障礙物,則視該條路徑為有效路徑。

圖2 AGV運行環(huán)境及建模示意

2 靠近目標(biāo)粒子群算法

2.1 傳統(tǒng)粒子群算法

粒子群算法是一種生物進化算法,最初是受到鳥群覓食過程的啟發(fā)[12]。在優(yōu)化問題的解空間內(nèi)隨機初始化一群粒子,每個粒子代表目標(biāo)函數(shù)的一個可行解,其位置由粒子運動速度決定,而粒子運動速度受粒子歷史最優(yōu)解和群體歷史最優(yōu)解影響。

假設(shè)粒子群中包含n個粒子,其搜索區(qū)域的維數(shù)為D維。xi=(xi1,xi2,…,xiD)為粒子i在D維空間中的位置,vi=(vi1,vi2,…,viD)為粒子i的飛行速度,Pbest為粒子的個體極值,即粒子i在尋優(yōu)過程中所找到的歷史最優(yōu)解,則該粒子在D維空間中的位置可以表示為Pi=(Pi1,Pi2,…,PiD),整個群體在搜索過程中尋找到的歷史最優(yōu)解為gbest,其在D維搜索空間的位置表示為Pg=(Pg1,Pg2,…,PgD),對于第k+1次迭代,每個粒子的每一維度的移動速度和位置都按照下列迭代公式進行更新迭代:

(1)

(2)

2.2 靠近目標(biāo)粒子群算法

針對傳統(tǒng)粒子群算法的缺陷,本文對算法進行了改進,在算法迭代過程中引入Metropolis準(zhǔn)則,并提出自適應(yīng)引力系數(shù)的概念,以提高粒子群算法的搜索效率及精度。

(1) 在算法迭代后期,粒子種群多樣性急劇下降,使算法陷入局部最優(yōu)值而出現(xiàn)“早熟”現(xiàn)象。針對該問題,引入Metropolis準(zhǔn)則,并將該準(zhǔn)則應(yīng)用到群體最優(yōu)值更新部分,以增加迭代后期解的更多可能性,避免陷入局部最優(yōu)解。

本文以最大迭代次數(shù)k來表示Metropolis準(zhǔn)則中溫度的概率,改進公式為:

(3)

更新群體最優(yōu)值時，按(3)式概率接受非最優(yōu)解的新解作為當(dāng)前群體最優(yōu),(3)式中迭代次數(shù)k逐一增加,概率P隨k的增加而變小,即算法迭代后期接受該新解的概率逐漸變小,搜索效率提高。群體最優(yōu)值更新部分改進后程序代碼如下:

輸入:y(i);F(i)

//y(i)為粒子;F(i)為粒子適應(yīng)度值

輸出:gbest;F(gbest)

//gbest為群體最優(yōu)粒子;F(gbest)為群體最優(yōu)粒子適應(yīng)度值

ifF(i)

gbest=y(i);

F(gbest)=F(i);

elseif exp((1-k2)/k)≥srand

gbest=y(i);

F(gbest)=F(i)

end.

(2) 因為算法只利用個體最優(yōu)和群體最優(yōu)進行迭代,所以最終解無法達到一定的精度,當(dāng)粒子被困于較差搜索區(qū)域難以自動跳出時,就會導(dǎo)致搜索效率降低,算法收斂變慢的問題。本文為了解決上述路徑規(guī)劃問題提出自適應(yīng)引力系數(shù)的概念,使粒子在搜索后期趨近于個體最優(yōu)及群體最優(yōu)值迭代的同時,受目標(biāo)點引力影響,加速靠近并搜索到最優(yōu)解。

設(shè)求解當(dāng)前坐標(biāo)點(xi,yi),利用路徑規(guī)劃目標(biāo)終點(xn,yn)以及當(dāng)前坐標(biāo)點的前一個坐標(biāo)點(xi-1,yi-1)之間的最短線段,即兩點連線來控制當(dāng)前點迭代范圍,已知兩點所在的直線方程為:

(4)

則當(dāng)前點(xi,yi)的橫坐標(biāo)值xi在該直線上對應(yīng)的縱坐標(biāo)值yi為:

(5)

求得的(xi,yi)點即為理想點。為保證各坐標(biāo)點在迭代過程中能夠趨于該理想點,在傳統(tǒng)粒子群算法的位置迭代公式中,增加自適應(yīng)引力系數(shù)a,改進后的迭代公式為:

(6)

其中,a為自適應(yīng)引力系數(shù),其取值如下:

(7)

由于該算法逐點優(yōu)化迭代,當(dāng)前點與終點連接的線段即為最短路線。為保證下一點靠近當(dāng)前點與終點連線進行搜索,在障礙物環(huán)境中增加引力因子,在避開障礙物的情況下快速向最優(yōu)解靠近,提高搜索效率的同時提高求解精度。

3 基于改進算法的AGV路徑規(guī)劃

3.1 粒子編碼

粒子編碼指粒子位置的表達方式,是粒子群算法設(shè)計應(yīng)用的關(guān)鍵問題,本文對AGV路徑規(guī)劃問題中的粒子進行編碼。設(shè)粒子數(shù)為m,粒子中除起點外的坐標(biāo)點數(shù)為n,算法開始時隨機生成的每條可行路徑為待優(yōu)化的一個粒子,包含構(gòu)成該路徑的各個坐標(biāo)點,粒子集M可表示為:

M={(x0,yi0),(x1,yi1),…,(xj,yij),…,

(xn,yin)}

(8)

其中:i=1,2,…,m;j=0,1,…,n。

環(huán)境建模階段,按障礙物頂點對坐標(biāo)系進行劃分,故粒子中的各坐標(biāo)點x值為定值,算法求解過程則是搜索最優(yōu)y值解集的過程.

3.2 適應(yīng)度函數(shù)建立

在移動機器人路徑規(guī)劃問題中,最終目標(biāo)是要規(guī)劃出一條最優(yōu)的可行路徑,其約束條件是路徑不與障礙物相交,且要求與障礙物保持一定的安全距離。適應(yīng)度值是評估路徑優(yōu)劣程度的標(biāo)準(zhǔn),因此需將規(guī)劃路徑時所涉及的一些要求包含進去并用數(shù)值的形式體現(xiàn),以便比較與衡量。本文適應(yīng)度函數(shù)包含路徑長度和路徑平滑度。

(1) 路徑長度評價函數(shù)F1。路徑長度評價函數(shù)F1為各分段路徑長度之和，即

(9)

其中,n為環(huán)境坐標(biāo)系中的區(qū)域劃分線數(shù)量。

(2) 路徑平滑度評價函數(shù)F2。路徑平滑度通常取決于AGV移動時的轉(zhuǎn)角大小,故用相鄰2條路段之間的夾角之和作為判斷路徑平滑度優(yōu)劣的指標(biāo)。夾角越接近180°,路徑越平滑。

(10)

其中:θ(PiPi+1,Pi+1Pi+2)為2條相鄰路段PiPi+1與Pi+1Pi+2之間的夾角。相鄰路段夾角與180°差值總和越小,則路徑越平滑,AGV轉(zhuǎn)彎消耗越小。

對于多目標(biāo)優(yōu)化函數(shù),需要對多目標(biāo)進行歸一化處理。本文參考了標(biāo)準(zhǔn)歸一化處理方法,同時結(jié)合多目標(biāo)權(quán)重分配,以路徑長度權(quán)重取1為基礎(chǔ)對多目標(biāo)進行統(tǒng)一化。統(tǒng)一化權(quán)重系數(shù)β為:

(11)

因此,AGV路徑規(guī)劃適應(yīng)度函數(shù)為:

F=F1+βF2

(12)

3.3 算法步驟

本文將求解AGV最優(yōu)路徑問題簡化為求解構(gòu)成最優(yōu)路徑的坐標(biāo)集,劃分環(huán)境坐標(biāo)系得到虛線集lj={l0,l1,…,ln},具體劃分方法見第1節(jié)。虛線上部分范圍被障礙物覆蓋,則其對應(yīng)障礙物為Dj=(0,D1,…,Dn-1,Dn)。在各虛線上取一個坐標(biāo)點,所有坐標(biāo)點連線最終構(gòu)成一條可行路徑,虛線集對應(yīng)坐標(biāo)點的橫坐標(biāo)xj=(x0,x1,…,xj,…,xn)為定值,則算法所尋優(yōu)的解即為各坐標(biāo)點的縱坐標(biāo)集yij=(y0,yi1,…,yij,…,yn)。其中:l0為坐標(biāo)系y軸;y0、yn分別為起點和終點縱坐標(biāo)。

基于靠近目標(biāo)粒子群算法的AGV路徑規(guī)劃步驟如下:

(1) 以AGV運行起點為原點建立平面直角坐標(biāo)系,對障礙物進行多邊化處理和膨脹處理后,過障礙物各頂點繪制垂直于x軸的虛線,得到虛線集lj={l0,l1,…,ln}。

(2) 參數(shù)初始化。確定迭代公式參數(shù)c、ω、種群數(shù)量m、粒子中包含的坐標(biāo)點個數(shù)n、最大迭代次數(shù)maxgen;確定坐標(biāo)取值范圍,y=max(xn,yDmax),其中,xn為終點橫坐標(biāo),yDmax為障礙物頂點縱坐標(biāo)最大值;確定最大迭代速度vmax∈(0.1lDmin,0.2lDmin),其中,lDmin為與虛線集重疊的障礙物邊界的最小長度。

(3) 初始化粒子。隨機生成各坐標(biāo)的初始迭代速度v=vmaxrands(n,m),v≤|vmax|;隨機生成各坐標(biāo)點位置構(gòu)成初始粒子(xj,yij),yij∈Ml,其中Ml為虛線l上未被障礙物覆蓋的縱坐標(biāo)集合。

(4) 計算各粒子適應(yīng)度F(j),并記錄個體最優(yōu)值Pbest(j)及群體最優(yōu)值gbest。

(5) 按改進后的迭代公式(6)更新粒子的速度與位置,并計算更新后粒子的適應(yīng)度函數(shù)值。

(7) 若搜索結(jié)果滿足終止條件或迭代次數(shù)達到上限,則算法結(jié)束;否則轉(zhuǎn)至步驟(5)繼續(xù)迭代。

4 實驗仿真與結(jié)果分析

使用仿真實驗對本文提出的靠近目標(biāo)粒子群算法進行驗證。AGV普通工作環(huán)境為7 m×6 m,粒子種群數(shù)為80,算法最大迭代更新次數(shù)為60次,最大迭代速度vmax=0.18,粒子維數(shù)與構(gòu)成最終路徑的坐標(biāo)點個數(shù)一致，即D=8。對于復(fù)雜環(huán)境,AGV工作環(huán)境為10 m×7.5 m,粒子種群為180,算法最大迭代更新次數(shù)為100次,最大迭代速度為vmax=0.1,粒子維數(shù)取D=13。2種環(huán)境中均取c1=149 445,c2=149 445,ws=0.9,we=0.4,AGV起始坐標(biāo)均為(0,0),目標(biāo)點坐標(biāo)分別為(7,6)和(10,6),算法最大循環(huán)次數(shù)均為20次。

實驗分為2組,分別驗證傳統(tǒng)粒子群算法和靠近目標(biāo)粒子群算法在普通和復(fù)雜環(huán)境下的算法有效性和路徑規(guī)劃能力。該實驗對傳統(tǒng)粒子群算法及靠近目標(biāo)粒子群算法分別在普通環(huán)境下運行1 000次,在復(fù)雜環(huán)境下運行1 800次。普通環(huán)境和復(fù)雜環(huán)境運行數(shù)次后平均值的規(guī)劃結(jié)果如圖3、圖4所示,普通環(huán)境和復(fù)雜環(huán)境下算法運行數(shù)次的路徑規(guī)劃統(tǒng)計數(shù)據(jù)見表1、表2所列。

圖3 普通環(huán)境下算法路徑規(guī)劃及求解迭代示意圖

由圖3和表1可知,普通環(huán)境下2種算法均可規(guī)劃出一條可行路徑,但靠近目標(biāo)粒子群算法相較于傳統(tǒng)算法路徑更短且更平滑,迭代時間更短,收斂速度更快。對比2種算法的求解方差可知,靠近目標(biāo)粒子群算法求解更穩(wěn)定,而傳統(tǒng)算法所求解的波動較大。

表1 普通環(huán)境下2種算法數(shù)據(jù)統(tǒng)計

由圖4可知,復(fù)雜環(huán)境下，傳統(tǒng)粒子群算法更容易陷入局部最優(yōu)解,而靠近目標(biāo)粒子群算法則在數(shù)次運算中均避開了局部最優(yōu)解。

由表2可知,靠近目標(biāo)粒子群算法在路徑長度、迭代穩(wěn)定性、收斂速度及算法穩(wěn)定性方面均優(yōu)于傳統(tǒng)算法。

圖4 復(fù)雜環(huán)境下算法路徑規(guī)劃及求解迭代示意圖

表2 復(fù)雜環(huán)境下2種算法數(shù)據(jù)統(tǒng)計

為了更直觀地驗證改進算法的穩(wěn)定性,在普通工作環(huán)境中,對傳統(tǒng)粒子群算法和靠近目標(biāo)粒子群算法各在其迭代60次的基礎(chǔ)上循環(huán)計算20次,得到2種算法的20次計算結(jié)果并繪制求解結(jié)果變化折線，如圖5所示。

從圖5可以看出，相較于傳統(tǒng)算法,靠近目標(biāo)粒子群算法求解結(jié)果十分穩(wěn)定,沒有大幅度波動，且更接近最優(yōu)解。

靠近目標(biāo)粒子群算法在路徑長度、收斂速度等方面的優(yōu)勢主要在于Metropolis準(zhǔn)則能使算法避開局部最優(yōu)解,及時跳出較差區(qū)域,相較于傳統(tǒng)算法能更易搜索到最優(yōu)解;自適應(yīng)引力系數(shù)的提出則讓算法運行時受目標(biāo)引力作用,加快收斂速度,相較于傳統(tǒng)算法能更快找到最優(yōu)解。仿真實驗結(jié)果充分說明了靠近目標(biāo)粒子群算法的有效性及穩(wěn)定性。

圖5 2種算法求解結(jié)果變化折線圖

5 結(jié) 論

在AGV路徑規(guī)劃研究中,本文針對傳統(tǒng)粒子群算法易陷入局部最優(yōu)解等問題,提出靠近目標(biāo)粒子群算法以優(yōu)化算法性能,提高算法效率,引入Metropolis準(zhǔn)則并應(yīng)用到算法中,避免了算法陷入局部最優(yōu)解的問題,并有效加快了算法跳出停滯狀態(tài)的速度;在傳統(tǒng)算法中引入自適應(yīng)引力系數(shù),并將其應(yīng)用到迭代公式中,使算法靠近目標(biāo)進行快速迭代,明顯加快了收斂速度,提高了搜索效率。仿真結(jié)果表明,本文提出的靠近目標(biāo)粒子群算法在收斂速度、精度、穩(wěn)定性等方面均具有明顯優(yōu)勢,具備一定的實際應(yīng)用價值。