魯 飛， 魯照權(quán)， 牛 晨， 孫偉業(yè)， 詹浩東

(合肥工業(yè)大學(xué) 電氣與自動化工程學(xué)院,安徽 合肥 230009)

0 引 言

近年來，路徑規(guī)劃一直是機(jī)器人研究領(lǐng)域中的熱點問題，其核心要求是按照特定的優(yōu)化準(zhǔn)則如距離最短、時間最短、能耗最低等，搜索出一條從起始點到目標(biāo)點的最優(yōu)安全路徑。目前，國內(nèi)外已經(jīng)提出了很多算法用于機(jī)器人路徑規(guī)劃，如A＊算法[1]、人工勢場法等，但大部分研究都是基于二維環(huán)境，對于環(huán)境比較復(fù)雜的三維空間存在著不少局限性。隨著研究的深入，有學(xué)者提出了智能仿生算法以及它們改進(jìn)算法的應(yīng)用，如蟻群算法[2]、遺傳算法[3]、神經(jīng)網(wǎng)絡(luò)算法[4]等。其中蟻群算法由于具有較強(qiáng)的適應(yīng)性和魯棒性，又易與其他方法結(jié)合，在機(jī)器人路徑規(guī)劃領(lǐng)域得到了廣泛應(yīng)用，但蟻群算法也存在收斂速度慢、易出現(xiàn)停滯和局部收斂等缺點。文獻(xiàn)[5]、文獻(xiàn)[6]分別將蟻群算法和遺傳算法、粒子群算法相結(jié)合，提高了算法尋優(yōu)能力，具有一定的靈活性；文獻(xiàn)[7]通過對初始信息素的差異化分配，并在概率轉(zhuǎn)移函數(shù)中引入轉(zhuǎn)角啟發(fā)信息，提高了蟻群搜索效率，但沒有應(yīng)用于三維環(huán)境中；文獻(xiàn)[8]在螞蟻狀態(tài)轉(zhuǎn)移的過程中引入稀疏性約束進(jìn)行改進(jìn)，有效減少了蟻群的搜索時間，但算法的運行速度有待進(jìn)一步提高。為使螞蟻盡快找到最優(yōu)解，

本文以路徑的適應(yīng)度值為優(yōu)化標(biāo)準(zhǔn)，對蟻群算法進(jìn)行了改進(jìn)，并運用在三維空間的路徑規(guī)劃上，通過MATLAB仿真證明了改進(jìn)后的蟻群算法有一定的優(yōu)越性。

1 三維路徑規(guī)劃建模

1.1 三維環(huán)境建模

采用柵格法對三維路徑規(guī)劃空間進(jìn)行建模。模型抽象方法如下：將三維地圖左下角頂點作為坐標(biāo)原點A，建立三維坐標(biāo)系，以A為頂點，分別沿x軸、y軸和z軸方向取三維地圖的最大長度AB，AD，AA′構(gòu)造立方體區(qū)域ABCD-A′B′C′D，如圖1所示。

圖1 三維空間劃分

利用平面對三維空間進(jìn)行均勻劃分，從中抽取出三維路徑規(guī)劃所需要的離散點，首先沿AB邊將空間ABCD-A′B′C′D進(jìn)行n等分，得到n+1個平面Πi(i=1,2,…n)，再對這n+1個平面分別沿AD邊進(jìn)行m等分，沿AA′進(jìn)行l(wèi)等分，得到空間中的各個交點。平面劃分如圖2所示。

圖2 平面劃分

通過上述步驟，整個規(guī)劃空間ABCD-A′B′C′D被分解成空間離散點的集合，這些離散點便構(gòu)成蟻群算法搜索的各條路徑。

1.2 可視化搜索空間

為了降低路徑規(guī)劃的復(fù)雜程度，在算法中采取一種分層前進(jìn)與柵格平面法相結(jié)合的搜索模式[9]，如圖3所示。

圖3 搜索可視區(qū)域

其思想是: 設(shè)定x軸方向為機(jī)器人前進(jìn)的主方向，在該方向上以單位距離劃分層次[10]，從當(dāng)前節(jié)點建立可視域，在前向運動一定距離Lx,max情況下，設(shè)定機(jī)器人最大橫向移動距離為Ly,max，最大縱向移動距離Lz,max。這樣，當(dāng)螞蟻由當(dāng)前節(jié)點轉(zhuǎn)移到下一節(jié)點時，搜索范圍被限制在可視區(qū)域內(nèi)，從而簡化了路徑搜索的復(fù)雜度。

2 改進(jìn)蟻群算法

2.1 信息素的初始化

傳統(tǒng)蟻群算法由于各路徑初始信息素濃度相同，使螞蟻在搜索過程中行走的隨機(jī)性太強(qiáng)，收斂速度太慢，且信息素的載體為節(jié)點間的線段，大大增加了算法的空間復(fù)雜度。本文改進(jìn)算法將信息素存儲在離散點中，并在初始化時對各離散點信息素進(jìn)行不均勻分配，目的在于減小算法復(fù)雜度，并提高算法初期的搜索效率。具體方法如下：以線段L連接起始點S和目標(biāo)點D，由于最優(yōu)路徑多集中在L附近區(qū)域。因此，以L與各平面Πi(i=1,2,…,n)的交點為圓心，Lm為半徑，構(gòu)建較優(yōu)離散點域，根據(jù)區(qū)域內(nèi)各離散點到直線L的距離，計算各個離散點的初始信息素值，數(shù)學(xué)表達(dá)式如下

(1)

(2)

式中τ0為離散點初始信息素濃度；Ly,max和Lz,max分別為最大橫向移動距離和最大縱向移動距離；len(Pa,L)為節(jié)點Pa到直線L的距離；λ為地圖比例因子，根據(jù)地圖具體參數(shù)來確定。

2.2 啟發(fā)函數(shù)的改進(jìn)

啟發(fā)函數(shù)是蟻群算法中的重要組成部分，其作用是利用距離信息引導(dǎo)螞蟻選擇最短路徑，直接影響到算法的收斂性、穩(wěn)定性以及最優(yōu)性[11]。但螞蟻搜索節(jié)點時往往會忽視周圍障礙物因素，優(yōu)先選擇與當(dāng)前節(jié)點最近的離散點，從而陷入局部最優(yōu)。針對此問題，本文增加可行性策略構(gòu)造新的啟發(fā)函數(shù)，同時引入動態(tài)夾角因素，使螞蟻對最優(yōu)路徑的搜索更具有方向性。本文構(gòu)造啟發(fā)函數(shù)由以下四部分組成：

1)可行性因素[12]

根據(jù)三維空間內(nèi)離散點的可行性，對規(guī)劃空間中各節(jié)點的可視區(qū)域離散點計算可行性因素權(quán)值。數(shù)學(xué)表達(dá)式如下

(3)

式中s(ia+1,ja+1,ka+1)為可視域R(Pa)中各離散點的權(quán)值，可行點權(quán)值為1，否則為0。定義可行性因素S(ia,ja,ka)的計算公式如下

(4)

Num1=∑S(ia+1,ja+1,ka+1)

(5)

式中Num為在點(ia,ja,ka)上可視點的數(shù)量；Num1為可視點中可行離散點的數(shù)量。

啟發(fā)函數(shù)中引入可行性因素雖然使得路徑規(guī)劃的安全性提高，但同時也增加了算法的復(fù)雜度，原因在于選擇下一節(jié)點時，要對可視域中所有離散點進(jìn)行掃描，計算出所有的可行離散點。為解決此問題，本文選擇在建模階段就計算出可視域中各離散點的可行性權(quán)值，在計算啟發(fā)函數(shù)時直接調(diào)用相應(yīng)權(quán)值即可，有效節(jié)省了計算時間。

2)相鄰節(jié)點路徑長度

D(ia,ja,ka)為兩節(jié)點間路徑長度，促使螞蟻選擇距離較近的點；D(ia,ja,ka)的計算公式如下

D(ia,ja,ka)=

(6)

式中 (ia,ja,ka)為當(dāng)前節(jié)點的具體坐標(biāo)，(ia+1,ja+1,ka+1)為下一點坐標(biāo)。

3)距目標(biāo)點路徑長度

Q(ia,ja,ka)為下一點到目標(biāo)點的路徑長度，促使螞蟻選擇距離目標(biāo)更近的點，Q(ia,ja,ka)的計算公式如下

Q(ia,ja,ka)=

(7)

其中，(iD,jD,kD)為目標(biāo)節(jié)點坐標(biāo)。

4)夾角因素

圖4 夾角示意

(8)

夾角因素A(ia,ja,ka)定義為

(9)

式中δ為一個大于零的角度參數(shù)，防止θa(ia,ja,ka)為零。ω為角度因素系數(shù)，由式(8)可以看出，在當(dāng)前節(jié)點Pa(ia,ja,ka)可視域內(nèi)選擇下一節(jié)點Pa+1(ia+1,ja+1,ka+1)時，若夾角θa(ia,ja,ka)趨向于一個較小的角度，則對應(yīng)的路徑是較優(yōu)的。由于在路徑規(guī)劃初期可視區(qū)域距離目標(biāo)點D較遠(yuǎn)，ω應(yīng)取較小值以避免角度因素的盲目誘導(dǎo)，提高算法初期的路徑多樣性；在路徑規(guī)劃后期距離目標(biāo)點較近時，ω的值應(yīng)該相應(yīng)增大來提高角度因素的影響。因此，ω在算法迭代運算過程中是一個動態(tài)參數(shù)，定義如下

(10)

式中ω0為夾角因素系數(shù)初值，len(Pa,S)為當(dāng)前點與起始點的距離，len(S,D)為起始點和目標(biāo)點的距離。結(jié)合上述因素，本文構(gòu)造啟發(fā)函數(shù)H(ia,ja,ka)如下

Γ=D(ia,ja,ka)·Q(ia,ja,ka)

(11)

H(ia,ja,ka)=Γ·S(ia,ja,ka)·A(ia,ja,ka)

(12)

2.3 權(quán)重因子α和β的改進(jìn)

經(jīng)過分析，由于在迭代初期各離散點的信息素濃度不同，此時，信息素權(quán)重因子應(yīng)在路徑選擇中占主導(dǎo)地位，即α的值應(yīng)較大，β的值應(yīng)較小。隨著迭代的不斷進(jìn)行，最優(yōu)路徑上的信息素濃度逐漸遠(yuǎn)高于其他路徑，為防止算法陷入局部最優(yōu)，應(yīng)逐漸減小信息素濃度在路徑選擇中的重要程度，即α值逐漸減小，β值相應(yīng)增加，從而有助于找到全局最優(yōu)解[13]。因此，本文將信息素因子α和啟發(fā)函數(shù)因子β的值改為動態(tài)參數(shù)，隨著迭代的進(jìn)行而做出改變，為使α，β的取值變化更加平穩(wěn)，分別采用余弦和正弦函數(shù)進(jìn)行賦值，如式(13)、式(14)所示

(13)

(14)

式中Nmax為迭代總次數(shù)，N為當(dāng)前迭代次數(shù)，則改進(jìn)后的概率轉(zhuǎn)移為

(15)

2.4 信息素更新規(guī)則的改進(jìn)

當(dāng)蟻群完成一次路徑搜索，以長度作為評價值，將所有螞蟻的路徑長度按照升序排列，只選擇排在前面的部分螞蟻進(jìn)行信息素更新，更新規(guī)則如下

τijk=(1-ρ)τijk+ρΔτijk

(16)

(17)

式中l(wèi)en(k)為第k只螞蟻經(jīng)過的路徑長度；rank(k)為螞蟻k的排名；μ·M為要更新的螞蟻數(shù)量；ρ為信息素?fù)]發(fā)因子；Q為信息素常量。

為了更好地平衡全局尋優(yōu)能力和局部尋優(yōu)能力，本文根據(jù)文獻(xiàn)[14]中的自適應(yīng)方法調(diào)整ρ，ρ的初始值設(shè)置為0.9，當(dāng)算法在連續(xù)v次迭代內(nèi)沒有更新最優(yōu)值，ρ按照式(18)調(diào)整，計算公式如下

(18)

式中ρmin為預(yù)先設(shè)置的信息素?fù)]發(fā)速率的最小值，以防止ρ過小而導(dǎo)致收斂速度太慢。

3 算法流程

改進(jìn)算法的具體步驟如下：

Step1 構(gòu)建三維工作環(huán)境，確定起始點S和目標(biāo)點D，并初始化相關(guān)參數(shù)。

Step2 信息素初始化，通過式(1)得到各節(jié)點的信息素初始值，對圖中各節(jié)點進(jìn)行信息素的不均勻分配。

Step3 搜索最優(yōu)路徑，在起始點S放置M只螞蟻，將起始點S放入禁忌表[15]中，根據(jù)式(15)計算每只螞蟻對下一平面中各節(jié)點的狀態(tài)轉(zhuǎn)移概率，并采用輪盤賭法選擇下一節(jié)點。

Step4 更新禁忌表，并判斷是否到達(dá)終點D，當(dāng)所有螞蟻完成一次搜索后，將路徑長度按照從小到大的順序排列，由式(17)確定要更新的螞蟻數(shù)量，并采用式(16)更新相應(yīng)路徑上各節(jié)點的信息素值。

Step5 檢驗最優(yōu)解的更新情況，若最優(yōu)解在連續(xù)v次迭代中未發(fā)生變化，按式(18)調(diào)整信息素?fù)]發(fā)因子。

Step6 判斷是否達(dá)到最大迭代次數(shù)，若是，則輸出全局最優(yōu)路徑長度；若否，則清空禁忌表，轉(zhuǎn)到Step3繼續(xù)執(zhí)行。

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

為了驗證文中改進(jìn)算法是否有效，在MATLAB 2018a中進(jìn)行仿真實驗，并將結(jié)果與文獻(xiàn)[10]進(jìn)行對比。

規(guī)劃空間為21 km×21 km×2 km，其中x軸，y軸方向每個節(jié)點間距1 km，z軸方向每個節(jié)點間距200 m。設(shè)置路徑起點在規(guī)劃空間的序號為(1,11,3)，目標(biāo)點序號(21,10,5)。

本文改進(jìn)算法的各項參數(shù)如表1所示。

表1 實驗參數(shù)取值

根據(jù)以上參數(shù)進(jìn)行三維路徑規(guī)劃實驗，通過設(shè)置相同參數(shù)，與文獻(xiàn)[10]仿真結(jié)果圖對比如圖5。其中，三角形曲線為文獻(xiàn)[10]算法所得到的最優(yōu)路徑，正方形曲線為本文改進(jìn)算法得到的最優(yōu)路徑。

圖5 三維路徑規(guī)劃結(jié)果對比

由圖5的適應(yīng)度變化曲線可以看出，改進(jìn)后的算法在得到更優(yōu)解的同時，迭代次數(shù)有了明顯減小，證明了本文對蟻群算法的改進(jìn)是有效的。為保證結(jié)果的準(zhǔn)確性，分別運用本文改進(jìn)算法與文獻(xiàn)[10]算法進(jìn)行多次實驗，隨機(jī)抽取4組實驗結(jié)果，如表2所示。

表2 實驗結(jié)果

為驗證算法在復(fù)雜環(huán)境下的適應(yīng)性，更換地圖環(huán)境并改變起始點和目標(biāo)點的坐標(biāo)，設(shè)置起始點和目標(biāo)點坐標(biāo)序號分別為(1,17,3)和(21,15,6)，再次進(jìn)行多組實驗，其中一組實驗結(jié)果如圖6。

圖6 場景二實驗結(jié)果對比

隨機(jī)抽取4組實驗結(jié)果繪制成表格如表3所示。

表3 場景二實驗結(jié)果

從實驗結(jié)果可以看出，引入夾角因素和可行性因素后，算法規(guī)劃出的路徑安全性與方向性都得到了增強(qiáng)，由此可以證明本文提出的改進(jìn)策略使蟻群算法搜索最優(yōu)解的能力得到了提高，能保證在快速收斂的情況下依然具有較強(qiáng)的全局搜索能力，有效克服了傳統(tǒng)蟻群算法收斂速度慢，易陷入局部最優(yōu)的缺點。

5 結(jié)束語

本文針對蟻群算法在三維路徑規(guī)劃中存在的搜索效率低，易陷入局部最優(yōu)等問題，對蟻群算法的初始信息素分配，啟發(fā)函數(shù)，權(quán)重因子以及信息素更新規(guī)則提出了改進(jìn)，通過柵格法對三維環(huán)境進(jìn)行抽象建模，仿真結(jié)果表明：改進(jìn)后的蟻群算法能夠快速有效地實現(xiàn)三維空間中的路徑規(guī)劃，同時具有較強(qiáng)的全局尋優(yōu)能力，相比傳統(tǒng)蟻群算法具有一定的優(yōu)越性，不足之處在于算法的運行時間相對較長，后續(xù)會對如何提高算法運行速度展開進(jìn)一步研究。