董志洋,李 慧,葛靖宇,程建華

(哈爾濱工程大學智能科學與工程學院,黑龍江 哈爾濱 150001)

近年來,隨著無人機相關技術的快速發(fā)展,無人機性能得到大幅度提升,被廣泛應用于土地利用航拍調查[1]、物流配送[2]及深林消防滅火[3]等軍用與民用領域,發(fā)揮了巨大作用[4]。路徑規(guī)劃是無人機自主安全飛行的關鍵技術,要求在特定約束條件下,確保無人機在避開障礙物的同時,能夠規(guī)劃出從起始點到終點的最優(yōu)航路[5]。無人機路徑規(guī)劃直接關系到無人機是否高效、安全地完成指定任務,一直是無人機領域的研究熱點。國內外學者針對無人機路徑規(guī)劃問題開展了大量研究工作,目前主要的路徑規(guī)劃算法有遺傳算法、快速擴展隨機樹法、A*算法、人工勢場法、粒子群算法、蟻群算法等。遺傳算法可有效處理相對簡單的路徑規(guī)劃問題,但當外部環(huán)境條件復雜時,其可行性急劇下降[6]。A*搜索算法和快速擴展隨機樹法在處理優(yōu)化問題時可以找到全局最優(yōu)解,但在處理計算量大、多維搜索問題時存在局限性[7-9]。人工勢場法優(yōu)勢是具有一定的穩(wěn)健性,但是該方法很容易落入局部最小值[10]。粒子群算法的參數(shù)少、易于實現(xiàn),但是尋優(yōu)過程不夠靈活,且復雜環(huán)境中收斂速度較小[11]。蟻群算法是一種隨機搜索的仿生智能優(yōu)化算法,通過模擬自然界螞蟻的覓食行為進行搜索優(yōu)化,具有穩(wěn)健性強、通用性好、計算能力強等優(yōu)點,但直接應用于路徑規(guī)劃時,存在局部最優(yōu)、收斂速度慢等問題[12]。

本文針對蟻群算法在進行路徑規(guī)劃時存在的問題,提出用引導函數(shù)改變狀態(tài)轉移規(guī)則、初始信息素先驗分配、時變信息素更新方式3個改進策略,使算法搜索初期有明確的方向性,搜索過程不易陷入局部最優(yōu),提升最優(yōu)路徑搜索效率,進而實現(xiàn)三維環(huán)境下的路徑規(guī)劃。

1 環(huán)境建模

環(huán)境建模將空間環(huán)境抽象為數(shù)學模型,是無人機路徑規(guī)劃的基礎。相對于傳統(tǒng)的二維環(huán)境,三維環(huán)境精度更高,算法也更加復雜。本文采用柵格法對三維空間環(huán)境進行建模,將一定范圍的三維空間分割成若干個等大的柵格,將障礙物存在范圍內的柵格視作不可行柵格,沒有障礙物覆蓋的柵格視作自由柵格[13]。以山峰為障礙物,設計山峰的不同位置與高度,制造地形起伏的三維環(huán)境。為了提升算法收斂速度,實際情況下利用環(huán)境切片法模擬三維環(huán)境,在高度方向將三維空間按照上升的步長進行n等分,得到n+1個平面,每一層的平面劃分為若干個柵格。蟻群算法進行三維路徑規(guī)劃的本質為:在不同的切片平面確定不同的柵格,將這些柵格利用樣條函數(shù)繪制成光滑的曲線,如圖1所示。首先確定主方向,從起始目標點P1開始,搜索第二個切片上的最優(yōu)可行點,確定下一位置P2;然后在進行下一個切片的最優(yōu)可行點,確定下一位置P3,依次進行至目標點結束,由此確定出一條最優(yōu)路徑。

圖1 切片法

2 傳統(tǒng)蟻群算法基本原理

(1)

式中,ηij(t)為啟發(fā)函數(shù),表示螞蟻從位置i到位置j的期望程度;allowk為螞蟻k下一個可訪問位置的集合;α為信息素重要程度因子,其值越大,表示信息素的濃度對螞蟻移動到下一位置的作用就越大;β為期望啟發(fā)函數(shù)重要程度因子,其值越大,表示位置i與j之間的相對距離對螞蟻移動到下一位置的作用就越大。啟發(fā)函數(shù)可表示為

ηij(t)=1/dij

(2)

式中,dij為位置i與j之間的歐式距離。

信息素更新是蟻群算法的關鍵部分。設參數(shù)ρ(0<ρ<1)表示信息素的揮發(fā)程度,每當完成一次迭代后,各個位置連接路徑上的信息素濃度會發(fā)生變化[15],當有螞蟻經(jīng)過此條路徑時信息素濃度會增加,反之則會降低。具體變化公式為

(3)

(4)

式中,Q為信息素常量;Lk為位置i與位置j之間的距離。

3 算法改進

3.1 改進蟻群算法轉移策略

傳統(tǒng)蟻群算法中,螞蟻按隨機比例規(guī)則選取下一個位置,在搜索空間較大時,無法快速、精準地向著目標點位置靠近。本文充分挖掘路徑規(guī)劃先驗信息,通過增加引導函數(shù)進行路徑增強,增大最優(yōu)路徑的選擇概率。引導函數(shù)ξij(t)可表示為

ξij(t)=K/dend

(5)

式中,K為環(huán)境比例系數(shù),根據(jù)具體的環(huán)境復雜程度而定;dend為選擇的下一位置j距離目標點的歐式距離,具體表示為

(6)

式中,(xend,yend,zend)為目標位置坐標;(xj,yj,zj)為位置j的坐標。引導函數(shù)ξij(t)利用目標點位置坐標進行最優(yōu)路徑增強,考慮路徑增強的螞蟻轉移概率可表示為

(7)

式中,γ為ξij(t)的重要程度。引導函數(shù)ξij(t)的加入使算法能夠加快收斂速度,使其收斂更有目的性,尤其是在障礙物較多的復雜環(huán)境下,算法收斂性能提升明顯。

3.2 改進信息素初始濃度分配

傳統(tǒng)蟻群算法中,初始信息素濃度均勻分配,不具備任何路徑指向性,導致算法初期收斂速度相對較慢,且容易陷入局部最優(yōu),影響算法的性能。為提升蟻群算法的收斂效率,盡量避免螞蟻在算法初期因向錯誤路徑前進而陷入局部最優(yōu)的情況,本文對信息素初始濃度分配方法進行改進,根據(jù)與先驗路徑的距離賦予信息素不同的初始濃度。

將連接初始點和目標點的線段L作為先驗路徑,先驗路徑為搜索空間中連接初始點和目標點的最短路徑。搜索空間中越靠近先驗路徑位置的信息素初始濃度越高,越遠離先驗路徑位置的信息素初始濃度則越低,以此激勵螞蟻優(yōu)先選擇距離較短的路線,加快算法收斂速度。改進的信息素初始濃度可表示為

(8)

式中,τ0為初始信息素濃度;σ為比例因子,根據(jù)初始濃度τ0大小不同來確定;di為與先驗路徑相關的量,即此點距離切片其他柵格點的歐式距離

(9)

式中,(xi,yi)為線段L經(jīng)過切片i的點。

3.3 改進信息素濃度更新方式

3.3.1 信息素濃度更新

傳統(tǒng)蟻群算法中,由于算法具有隨機性,根據(jù)信息素濃度每一次選擇的路徑不一定是最優(yōu)路徑,隨著信息素濃度不斷增加,容易陷入局部最優(yōu)解,無法得到最優(yōu)路徑。為避免算法陷入局部最優(yōu),本文對信息素濃度更新策略進行改進,增加本次迭代中最優(yōu)螞蟻提供最強的反饋,將優(yōu)勝劣汰的思想加入到蟻群算法的信息素更新中,加強最優(yōu)路徑對全局的影響,并將信息素更新標準更改為

(10)

(11)

3.3.2 信息素揮發(fā)因子設置

傳統(tǒng)蟻群算法中,信息素揮發(fā)因子ρ通常是一個固定常數(shù)。在全局搜索過程中,當信息素的揮發(fā)因子不變時,算法的搜索效率較慢,而且在信息素不斷積累過程中可能在先發(fā)現(xiàn)的路徑上會積累大量信息素,進而導致算法停滯,無法搜索到最優(yōu)路徑。本文提出一種信息素揮發(fā)因子波動機制,揮發(fā)因子ρ隨時間變化且服從Laplace分布,公式為

(12)

式中,a為常數(shù);x服從Laplace分布;λ為尺度參數(shù);μ為位置參數(shù);ρmin為信息素揮發(fā)因子的最小值,經(jīng)過調整a的值確定揮發(fā)因子所需要的分布曲線。

揮發(fā)因子ρ服從Laplace分布,在算法早期,ρ較小,可防止信息素揮發(fā)過多而削弱信息素的引導作用;在算法中期,ρ較大,防止大量的信息素積累會使算法過早收斂,失去尋找最優(yōu)路徑的能力;在算法后期,ρ較小,后期路徑選擇變得單一,應增加信息素引導作用。相比于傳統(tǒng)蟻群算法中揮發(fā)因子固定的設置,服從Laplace分布的揮發(fā)因子可根據(jù)算法不同階段情況有效調節(jié)整個算法過程中信息素的引導作用,進而提升算法尋優(yōu)路徑能力。

4 試驗驗證

本文設計了兩組仿真對照試驗,分別為簡單環(huán)境和復雜環(huán)境,其中復雜環(huán)境的障礙物山峰數(shù)為簡單環(huán)境的1倍,增加了地形起伏,通過與傳統(tǒng)蟻群算法比較,評估本文改進算法的性能。設定試驗仿真螞蟻個數(shù)為100,迭代次數(shù)50次,表1列出了試驗的具體參數(shù)。

表1 試驗參數(shù)設定

環(huán)境1:簡單環(huán)境初始蟻群算法在 100×100×150的網(wǎng)格環(huán)境中進行驗證,設置障礙物、初始點、目標點,進行路徑規(guī)劃,在簡單環(huán)境中設置障礙物較少,驗證仿真結果如圖2—圖4所示。

圖2 蟻群算法簡單環(huán)境下路徑軌跡

圖3 改進蟻群算法簡單環(huán)境下路徑軌跡

圖4 簡單環(huán)境下收斂曲線變化趨勢

環(huán)境2:復雜環(huán)境初始蟻群算法在100×100×200的網(wǎng)格環(huán)境中,設置障礙物、初始點、目標點,進行路徑規(guī)劃,在復雜環(huán)境中設置障礙物時簡單環(huán)境中障礙物數(shù)量的1倍,驗證仿真結果如圖5—圖7所示。

圖5 蟻群算法復雜環(huán)境路徑軌跡

圖6 改進蟻群算法復雜環(huán)境下路徑軌跡

根據(jù)兩組試驗的規(guī)劃路徑軌跡圖及迭代收斂曲線變化圖可以看出,傳統(tǒng)蟻群算法在算法初期隨機性明顯較大,在復雜環(huán)境中隨機性更加突出,軌跡初期由于隨機性的缺點,算法路徑搜索能力不強,所規(guī)劃出的路徑距離更長。通過本文對算法改進后,能夠看出算法初期有明確的方向性,路徑搜索能力增強,能夠獲得更短的路徑,也加快了算法的收斂速度。

表2和表3進一步給出了簡單環(huán)境和復雜環(huán)境下傳統(tǒng)蟻群算法和本文改進蟻群算法規(guī)劃的最優(yōu)路徑長度和收斂迭代次數(shù)。

表2 簡單環(huán)境算法性能對比

表3 復雜環(huán)境算法性能對比

由表2和表3的對比分析可知,在簡單環(huán)境下經(jīng)過對傳統(tǒng)蟻群算法的改進,最優(yōu)路徑長度由205.290 m降至183.593 m,降為原來的89%;迭代次數(shù)由33次降至8次,降低了76%。在復雜環(huán)境下,經(jīng)過對傳統(tǒng)蟻群算法的改進,最優(yōu)路徑長度由241.174 m降至202.873 m,降為原來的84%;迭代次數(shù)由41次降至26次,降低了37%。相比于傳統(tǒng)的蟻群算法,本文所提出的改進蟻群算法能夠在更短的時間內規(guī)劃出長度更短的路徑。

5 結 語

本文針對傳統(tǒng)蟻群算法在三維路徑規(guī)劃中存在路徑尋優(yōu)效率低、算法初期隨機性較大、易陷入局部最優(yōu)的問題,提出用引導函數(shù)改變狀態(tài)轉移規(guī)則、初始信息素先驗分配、時變信息素更新方式3個改進策略,完成對傳統(tǒng)蟻群算法的改進。簡單環(huán)境和復雜環(huán)境下的路徑規(guī)劃仿真試驗表明,相較于傳統(tǒng)的蟻群算法,改進后的蟻群算法在有效躲避障礙物的同時,有效降低了最優(yōu)路徑長度,并大大提升了路徑尋優(yōu)效率。