基于改進蟻群算法的三維路徑規(guī)劃研究*

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

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

0 引 言

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

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

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

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

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

圖1 三維空間劃分

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

圖2 平面劃分

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

1.2 可視化搜索空間

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

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

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

2 改進蟻群算法

2.1 信息素的初始化

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

(1)

(2)

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

2.2 啟發(fā)函數的改進

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

1)可行性因素[12]

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

(3)

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

(4)

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

(5)

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

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

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

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

D(ia,ja,ka)=

(6)

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

3)距目標點路徑長度

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

Q(ia,ja,ka)=

(7)

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

4)夾角因素

圖4 夾角示意

(8)

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

(9)

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

(10)

式中ω0為夾角因素系數初值，len(Pa,S)為當前點與起始點的距離，len(S,D)為起始點和目標點的距離。結合上述因素，本文構造啟發(fā)函數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 權重因子α和β的改進

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

(13)

(14)

式中Nmax為迭代總次數，N為當前迭代次數，則改進后的概率轉移為

(15)

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

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

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

(16)

(17)

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

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

(18)

式中ρmin為預先設置的信息素揮發(fā)速率的最小值，以防止ρ過小而導致收斂速度太慢。

3 算法流程

改進算法的具體步驟如下：

Step1 構建三維工作環(huán)境，確定起始點S和目標點D，并初始化相關參數。

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

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

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

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

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

4 仿真結果與分析

為了驗證文中改進算法是否有效，在MATLAB 2018a中進行仿真實驗，并將結果與文獻[10]進行對比。

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

本文改進算法的各項參數如表1所示。

表1 實驗參數取值

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

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

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

表2 實驗結果

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

圖6 場景二實驗結果對比

隨機抽取4組實驗結果繪制成表格如表3所示。

表3 場景二實驗結果

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

5 結束語

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