改進蟻群算法的無人機三維環境路徑規劃

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

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

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

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

1 環境建模

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

圖1 切片法

2 傳統蟻群算法基本原理

(1)

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

ηij(t)=1/dij

(2)

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

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

(3)

(4)

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

3 算法改進

3.1 改進蟻群算法轉移策略

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

ξij(t)=K/dend

(5)

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

(6)

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

(7)

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

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

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

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

(8)

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

(9)

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

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

3.3.1 信息素濃度更新

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

(10)

(11)

3.3.2 信息素揮發因子設置

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

(12)

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

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

4 試驗驗證

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

表1 試驗參數設定

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

圖2 蟻群算法簡單環境下路徑軌跡

圖3 改進蟻群算法簡單環境下路徑軌跡

圖4 簡單環境下收斂曲線變化趨勢

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

圖5 蟻群算法復雜環境路徑軌跡

圖6 改進蟻群算法復雜環境下路徑軌跡

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

表2和表3進一步給出了簡單環境和復雜環境下傳統蟻群算法和本文改進蟻群算法規劃的最優路徑長度和收斂迭代次數。

表2 簡單環境算法性能對比

表3 復雜環境算法性能對比

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

5 結 語

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