基于CMPSO算法的無人機復雜三維路徑規劃

甯 洋, 鄭 波,2, 龍足騰, 羅金超

(1.中國民用航空飛行學院航空電子電氣學院,四川 廣漢 618000; 2.核工業西南物理研究院,成都 610000)

0 引言

無人機(UAV)路徑規劃是無人機領域的研究熱點之一,它是指在不違背自身物理特性及約束條件的前提下,形成一條從出發點到末端點的最優路徑。20世紀80年代之前,無人機的路徑規劃主要靠人工來完成,但是戰場環境復雜多變,人工規劃的路徑不足以面對復雜多變的現代戰場,隨著科技的快速發展,無人機的通訊、交互、控制、探測、導航技術都得到了增強,對地面人工的操控要求就逐漸變低,無人機路徑規劃逐漸趨于智能化。

目前,國內外學者提出了大量用于無人機路徑規劃的方法,其中比較經典的有基于圖搜索的算法包括Dijstra算法[1]、A*算法[2]、D*算法[3]等;基于采樣的算法包括隨機路標[4]和隨機搜索樹[5]等;一些局部規劃算法,例如人工勢場法[6]和動態窗口法[7]等。隨著群智能算法的發展,眾多學者也將群仿生智能算法應用于無人機路徑規劃,其中,比較常見的群智能算法有粒子群優化(PSO)算法、蟻群算法、遺傳算法、人工勢場法等。文獻[8]提出了一種改進蟻群優化(ACO)算法,使用柵格法來將三維空間平分,雖然改進算法能夠有效避免陷入局部最優,但是約束條件較少且模擬的三維空間較簡單,柵格法規劃的路徑對航路起點和終點的位置比較敏感,且規劃的路徑不平滑;文獻[9]利用了人工勢場法進行規劃,但是涉及的模型過于理想;文獻[10]利用ACO算法進行規劃,但是所涉及的算法僅僅在二維空間可行,無法應用于三維空間。

PSO算法是一種啟發式智能算法,相比于其他算法,PSO算法具有魯棒性較好、對種群個體數量敏感性低[11]、涉及的參數和公式較少、收斂速度快等優點,但缺點是后期收斂速度慢,且收斂精度低導致早熟現象。針對其缺點,眾多學者進行了研究。文獻[12]將PSO算法與細菌覓食算法、遺傳算法混合,各算法間取長補短,在速度、收斂值、跳出局部最優方面均有改善;文獻[13]利用Logistic混沌映射處理粒子群,提升粒子種群的初始化質量,提高種群的多樣性,能夠有效提高PSO算法的全局尋優能力;文獻[14]提出了一種結合天牛須算法的粒子群算法,利用天牛須算法幫助粒子群算法跳出局部最優;文獻[15]將雞群算法的分組優化策略應用于粒子群算法,并在更新時采取模擬退火操作,有效避免了陷入局部最優。

本文綜合考慮航程代價等約束條件,設計了代價函數,考慮了城市和山區兩種復雜環境,將CMPSO(Compression and Mutation PSO)、CPSO與PSO算法分別進行仿真實驗,結果表明,CMPSO算法具有較高的尋優精度,在兩種環境下都能得到高質量的路徑。

1 粒子群算法

1.1 傳統粒子群算法

假設粒子群的種群規模為N,在d維空間中搜索,粒子i的當前速度和位置分別為vi與xi(i=1,2,…,N),所經歷過的最優位置為pi,群體經歷過的最優位置為pg,上述參數分別表示為

(1)

PSO算法靠更新粒子的速度和位置來迭代,直到滿足停止規則,速度和位置更新規則為

(2)

式中:w為慣性權重,表示對當前粒子速度的信任程度;c1、c2為粒子的學習因子,調節粒子移動的最大步長;r1、r2為0～1間的隨機數,增加粒子搜索的隨機性。

1.2 融合壓縮策略與變異策略的粒子群(CMPSO)算法

傳統的PSO算法的所有參數都是固定的,因此算法易理解易操作,但是在解決實際復雜工程問題時,會出現搜索不到全局最優解,或者搜索到全局最優解需要消耗大量時間成本的情況,固定的參數往往都不能很好地解決問題,導致結果不理想。本文提出融合壓縮策略與變異策略的思想,在壓縮策略中,取消了慣性權重w,加入了壓縮因子,避免因選取錯誤的權重而導致尋優結果與預期差別較大,再通過變異策略來增加粒子的多樣性,以此提高算法的全局搜索能力。

1.2.1 慣性權重的影響

慣性權重w影響粒子的飛行速度,表示對當前粒子速度的信任程度,w的取值對PSO算法的性能有明顯影響,較大的慣性權重有利于全局搜索,但是容易導致粒子錯過最優解,較小的慣性權重有利于局部搜索,但是容易陷入局部最優。采用了錯誤的慣性權重,則可能造成收斂精度低或者無法收斂,在無人機路徑規劃方面則會導致找不到合適的路徑。所以粒子在前期能夠有較快的搜索速度,后期有較慢的搜索速度,以達到平衡粒子全局搜索能力與局部搜索能力的目的,文獻[16]提出了線性遞減慣性權重的粒子群(Linear Decreasing Inertia Weight PSO,LDIWPSO)算法,文獻[17]提出了一種余弦式遞減慣性權重粒子群(Cosine Decreasing Inertia Weight PSO,CDIWPSO)算法,這兩種權重的算式分別為

(3)

(4)

式中:w1為線性遞減慣性權重;w2為余弦式遞減慣性權重;wmax為權重最大值,可取0.9;wmin為權重最小值,可取0.4;Imax為最大迭代次數;k為當前迭代次數。兩種遞減慣性權重的變化趨勢如圖1所示。

圖1 兩種遞減慣性權重變化趨勢對比

擁有兩種遞減慣性權重的PSO算法在低維問題中能夠有效地避免早熟,但是對于高維復雜問題,算法的尋優效果并不是很理想,當粒子在迭代過程中,某粒子當前代的適應度值相比于上一代變差,如果此時慣性權重變小的話,不利于該粒子進行全局搜索,導致該粒子不能遍歷全局從而陷入局部最優。

1.2.2 壓縮策略

無論是線性遞減慣性權重還是余弦式遞減慣性權重都實現不了真正意義上的自我調節,為了減少w對粒子狀態的影響,避免采用錯誤的慣性權重,同時又能平衡前期的全局搜索與后期局部搜索,需要所有粒子都能根據自身情況自適應調節,本文采用帶壓縮因子的粒子群(CPSO)算法[18],其粒子速度更新算式為

(5)

式中,δ為壓縮因子,其算式為

(6)

相比于傳統PSO,CPSO算法相當于擁有遞減慣性權重的粒子群算法。為了平衡算法的全局搜索能力與局部搜索能力,CPSO算法刪除了慣性權重w,取而代之的是壓縮因子δ,這樣粒子群算法的速度就僅靠c1、c2兩個學習因子來調節,c1、c2的取值為

(7)

(8)

其中:cmax的取值為2.5;cmin的取值為1.5[18];f(xi)為粒子i的適應度大小;favg為種群的平均適應度。當粒子i的適應度f(xi)小于種群的平均適應度favg時,粒子xi進行局部搜索,c1、c2的取值按照式(7)進行;當粒子i的適應度f(xi)大于種群的平均適應度favg時,粒子i進行全局搜索,c1、c2的取值按照式(8)進行。

1.2.3 變異策略

PSO算法在每次迭代后都會形成新的粒子,新粒子相比舊粒子會有新的速度和位置,因其受到全局最優解的影響,新粒子會向全局最優粒子的方向移動,但是如果此時全局最優粒子的位置不是真正的全局最優解,則粒子就會陷入局部最優。所以本文對粒子進行提前變異,增加粒子的多樣性和活躍性,增加因不斷迭代而慢慢縮小的活動空間,增強粒子跳出局部最優的能力,粒子變異算式為

(9)

式中,β為與xid同維,且每一項都是[0,1]間隨機數的D維向量,這樣做的目的是使xid中的部分元素被pgd中相應位置的元素替代,還能增加粒子的搜索范圍,不僅增加了粒子多樣性還能增加粒子的后期開發能力。

CMPSO算法的具體步驟如下:

1) 設置種群規模N,最大迭代次數Imax,最小學習因子cmin,最大學習因子cmax,變異率γ等參數,并初始化各粒子的速度vi和位置xi;

2) 計算各粒子的適應度,并計算個體最優位置與群體最優位置,計算個體最優適應度與群體最優適應度;

3) 根據壓縮策略更新各粒子的速度;

4) 判斷0～1間的隨機數R是否大于變異率γ,如果是,則按照式(2)更新位置,否則按照式(9)更新位置;

5) 判斷是否滿足終止條件,未滿足則重復步驟2)～4),滿足則結束循環,本文設置的結束條件為達到最大迭代次數。

2 算法性能測試

為了驗證改進算法的可行性,本文對CEC2017測試函數中的部分基準函數進行仿真測試,這些函數都具有復雜、多模態等特點。本次測試函數的算法分別為粒子群算法(PSO)、采用線性遞減慣性權重的算法(w1-PSO)、采用余弦式遞減慣性權重的粒子群算法(w2-PSO)、僅采用壓縮策略的粒子群算法(CPSO)、僅采用變異策略的粒子群算法(MPSO),以及同時采用壓縮策略與變異策略的粒子群算法(CMPSO),算法參數如表1所示。共有的參數取相同的值。

表1 算法參數

10種測試函數的函數特征如表2所示。

表2 測試函數及特征

其中既包含單峰測試函數也包括多峰測試函數,為了測試所有算法在低維和高維的尋優能力,其中函數f1、f2僅在2維測試,函數f3～f10都在50維測試。函數f1、f2、f3、f4、f6、f10為多峰測試函數,它們雖然只有一個全局極小值點,但是都存在大量局部極小值影響算法的尋優結果,函數f5、f7、f8、f9都為單峰測試函數。

每個算法獨立運行100次,取其適應度均值(mean)、方差(StD)和平均消耗時間(MET)來衡量尋優性能。測試函數運行結果如表3所示。

表3 測試函數運行結果

由表3可以看出,PSO、CPSO、MPSO與CMPSO算法對測試函數的測試過程等同于一種消融實驗,PSO、CPSO與MPSO算法的尋優結果明顯優于PSO算法,而CMPSO算法的尋優結果又明顯優于CPSO算法與MPSO算法,且也優于w1-PSO與w2-PSO算法,總體來看,CMPSO算法測試結果的均值和方差都明顯優于其他算法,結果更接近最優值,說明CMPSO算法的收斂效果更好,且更加穩定,收斂時間也處于較理想的水平。綜合比較下,CMPSO算法的收斂性和計算復雜度都比較理想,證明了壓縮策略與變異策略的有效性。這是因為壓縮策略能夠使粒子根據自身狀態進行正確的自適應調節,加強了局部尋優能力,而變異策略又能增加粒子的多樣性,提高粒子的開發能力,加強了全局尋優能力,從而使CMPSO算法的尋優能力要遠遠優于其他算法,表明CMPSO算法能為路徑規劃提供強有力的技術支撐。

3 環境建模及約束條件

3.1 環境建模

3.1.1 城市環境建模

環境建模就是將環境中的各種物理信息轉換為計算機算法能處理的數字模型,這是規劃無人機路徑的前提和基礎[19]。為了驗證CMPSO算法的有效性,本文主要模擬城市和山區兩種環境下的路徑規劃,在城市環境中,所有不同形狀的建筑物都可以等同于圓柱形障礙物,當無人機飛過這些障礙物,需要與這些障礙物有一定的距離來保證自身的安全。障礙物示意圖見圖2。

圖2 障礙物示意圖

圖2中,R1為障礙物的半徑,S為無人機的尺寸,T為危險飛行區域,要求無人機離障礙物中心點垂直線的距離R2大于R1+S才能滿足要求。

本文的城市環境建模設計了26個圓柱形障礙物,半徑從小到大分別為3 km、4 km、5 km,城市環境仿真如圖3所示。

圖3 城市環境仿真

3.1.2 山區環境建模

山區環境仿真地圖可建模為

(10)

式中:z0為地基高度,取值為0.02 km;M為山峰的個數,取值為15;hm、xm、ym、xsm、ysm都為M維的系數向量,hm為山峰的高度,(xam,yam)為山峰中心軸在地面的坐標值;xsm,ysm為山峰分別在x方向和y方向的坡度,表示山峰的陡峭程度。山區環境仿真如圖4所示。

圖4 山區環境仿真

3.2 約束條件

固定翼無人機在飛行過程中,并不能像旋轉翼無人機一樣自由升降、前進、后退、以及空中停滯。因此,固定翼無人機的飛行要求相比于旋轉翼無人機更嚴格。本文綜合考慮航程代價、飛行約束代價(包含高度約束代價、最小慣性距離約束代價、俯仰角約束代價)和環境威脅代價,以此使本文研究內容更貼近現實,更有應用價值。

1) 航程代價。

由于自身航油攜帶量、自身油耗、總油量等因素的影響,無人機的飛行距離都是有限的。設最終航跡有D個航路點,每個航路點i和i+1之間的距離為li,則航程代價為

(11)

式中,Lmax為最大航程。

2) 高度約束代價。

無人機在飛行過程中,如果飛行高度太低容易受到建筑物或者山谷地貌的影響,飛行高度太高則容易受到大氣和自身性能的影響,因此需要在一個合適高度范圍內飛行,無人機在城市或者山谷低空偵察飛行時,由于自身有一定的體積,還面臨著電桿、樹木等障礙物的威脅,因此飛行時需要與環境保持一定的安全距離,設電桿和樹木的高度為hz,無人機不能貼著這些障礙物飛行,因此還要設置一定的安全距離hsafe,為了達到較好的偵察效果,無人機飛行時的高度并不能太高,設某航跡點下方的地面高度為ht,距離地面的最大高度為hd,則無人機飛行高度Zi為

(12)

則高度約束代價為

(13)

式中,C0為代價常數,可自行設置。

3) 最小慣性距離約束代價。

無人機在飛行時,由于自身的慣性原因及動力原因,急轉彎是不被允許的,因此要設置最小慣性距離Lmin防止飛機突然進行轉彎,此約束可表示為

li≥Lmini∈[1,D-1]

(14)

則最小慣性距離約束代價為

(15)

4) 俯仰角約束代價。

由于自身性能的限制,無人機在升高或者俯沖時,角度需要有一定的限制,設置最大俯仰角θmax,只有當俯仰角小于θmax時才能安全飛行,否則有可能對飛機機體造成損壞。設前后相鄰的兩航路點坐標分別為(xi-1,yi-1,zi-1)、(xi,yi,zi),如果zi≠zi-1,則說明飛機在進行升高或者俯沖動作,則飛機的最大俯仰角θmax應滿足

(16)

則俯仰角約束代價為

(17)

式中,θ為無人機的俯仰角。綜合考慮無人機的飛行高度約束、最小慣性距離約束、俯仰角約束,則飛行約束代價為

Trestrain=T1+T2+T3。

(18)

5) 環境威脅代價。

本文的環境威脅主要為兩種:1) 山區障礙物的威脅;2) 城市建筑障礙物的威脅。無人機在飛行過程中,如果距離這些障礙物越遠,則表明無人機越安全,設航路點與障礙物中心軸的水平距離為

(19)

式中:(xd,yd)為航路點在水平面投影的坐標;(xm,ym)為障礙物中心軸在水平面投影的坐標。則環境威脅代價為

(20)

適應度函數包含了優化目標,以及約束條件,是定量評價解優劣的標準[20],綜合上述分析,無人機的總代價函數為

f=ω1Tvoyage+ω2Trestrain+ω3Tthreat

(21)

式中,ω1、ω2、ω3為權重系數,表示這些代價的重要程度,且滿足ω1+ω2+ω3=1。

4 仿真實驗分析

為了驗證CMPSO算法的有效性,本文將CMPSO、CPSO與PSO算法應用于無人機路徑規劃,對比分析算法的尋優結果。山區和城市兩種環境都是在100 km×100 km×2 km的空間中仿真。

為了驗證算法在不同末端航線規劃的性能,假設將起點視為坐標原點,對于起點在不同象限的區域各設置一個偵察點,在山區環境中,設置起點為(50 km,50 km,0.13 km),設置4個象限的偵察點分別為(5 km,90 km,0.06 km)、(95 km,90 km,0.06 km)、(20 km,5 km,0.06 km)、(97 km,10 km,0.06 km),形成航線為L1～L4。在城市環境中,設置起點為(50 km,50 km,0.07 km),4個偵察點分別為(5 km,90 km,0.3 km)、(59 km,90 km,0.3 km)、(5 km,5 km,0.3 km)、(90 km,7 km,0.3 km)。PSO算法種群數N為300,每條航路的航路點個數為30,最大迭代次數為150,學習因子c1、c2都設置為1.5,慣性權重w為0.9。CPSO算法的cmax、cmin分別取0.9、0.4,設置無人機的約束條件為:Lmax=100 km,hz=0.005 km,hsafe=0.15 km,hd=2 km,Lmin=1 km,C0=500;θmax根據式(16)確定。

圖5為3種算法在山區環境中的路徑規劃仿真圖。

圖5 山區環境路徑規劃圖

圖6為3種算法在城市環境中的路徑規劃仿真圖。

圖6 城市環境路徑規劃圖

如圖5～6所示,CMPSO算法規劃的航跡路線無論是平滑度還是偏轉次數,都比PSO和CPSO算法規劃的航跡要好,有利于無人機的飛行安全。

表4、表5為山區和城市兩種環境中的3種算法的航路規劃性能比較。

表4 山區環境尋優數據對比

表5 城市環境尋優數據對比

每條航路各自獨立仿真20次,計算20次仿真的平均消耗時間,20次航程的最小值(min)、平均值(mean)、標準差(StD),以及違反約束代價(Constraint Violations,CV)的次數,CV為1×5的矩陣,反映20次仿真過程中算法未滿足3.2節中約束代價的次數,例如,CV=[5,0,6,0,0],表示這20次實驗中,5次違反航程約束條件,6次違反最小慣性距離約束條件。由表4、表5可以看出,在L1～L4這4種不同末端航線的規劃中,相比于其他算法,CMPSO算法規劃航路所消耗的時間最少,航路的距離最短,性能最穩定,違反約束條件的次數最少。充分證明了CMPSO算法面對實際工程問題時優秀的尋優能力。

圖7為山區和城市兩種環境中航線L1的目標函數迭代圖。

圖7 目標函數迭代圖

由圖7可以看出,隨著迭代次數的增加,3種算法的目標函數值都在減小,不過CMPSO算法的最終目標函數值和規劃快速性均優于CPSO、PSO算法,且PSO算法的尋優結果明顯差于其余兩種算法,這說明CPSO和PSO算法都可能陷入局部最優,而改進后的CMPSO 算法,通過壓縮策略增加了粒子的自調節能力,通過變異策略增加了粒子的多樣性,從而增加了算法跳出局部最優的能力,證明了CMPSO算法面對路徑規劃問題時的有效性。

5 結束語

本文提出了CMPSO算法,利用壓縮策略使粒子實現自適應調節,利用變異策略增加了粒子的活躍性與多樣性,并用10種經典測試函數對CMPSO算法的尋優性能進行了驗證,結果表明,CMPSO算法具有優秀的尋優能力和避免陷入局部最優的能力。綜合考慮航程代價、飛行約束代價和環境威脅代價設計了目標函數,通過仿真測試,相比于PSO與CPSO算法,CMPSO算法無論在山區環境中還是在城市環境中,規劃出來的路徑更加合理,航程更短,性能更穩定且耗時更短。