王小璐，黃辰，于遠航，陳福豪，胡蝶，陸琪，崔曦予

（沈陽航空航天大學民用航空學院，遼寧沈陽，110136）

0 引言

近年來，隨著傳感器技術和智能控制技術的發(fā)展，無人機已被廣泛應用于軍事和民用領域，如偵察[1]、監(jiān)視[2]、目標檢控[3]、無線通信[4]、油田檢測[5]等。與載人飛機相比，無人機因為體積小、成本低、對使用環(huán)境要求低和具有較強的生存能力等優(yōu)點而得到了廣泛的應用，并正在逐漸取代傳統(tǒng)的載人飛行器，無人機(Unmanned Aerial Vehicle, UAV)的研究對一個國家的經濟與民生起著重要的作用。路徑規(guī)劃作為[6]無人機系統(tǒng)自主導航的基礎技術，是保證飛行任務順利完成的重要組成部分，因而受到越來越多的關注。無人機路徑規(guī)劃的主要目標是在規(guī)定的約束條件下，在任務空間中尋找從起始位置到目的位置的最優(yōu)或接近最優(yōu)的飛行路徑。近年來，常用于解決路徑規(guī)劃問題的主要方法有啟發(fā)式算法（例如，A*算法[7]、D*算法[8]）、進化算法（例如，蟻群算法[9]、粒子群算法[10]、人工蜂群算法[11]、遺傳算法[12]）、人工勢場法[13]等。

與傳統(tǒng)方法相比，進化計算算法在路徑上獲得高質量解的能力很強。航跡規(guī)劃問題通常被認為是一個非線性NPhard優(yōu)化問題，通過進化算法進行求解。眾所周知，進化算法已經取得了很大的進展，并得到了深入而廣泛的研究。進化算法的靈感來自“自然生物進化”，通過將自然界各種事物的演化規(guī)律與解題過程相結合，從而得到實際問題的高精度近似解，并在生產實踐中得到了廣泛應用。進化算法已被成功應用于尋找全局或近似全局最優(yōu)路徑。Yang等[14]發(fā)現(xiàn)了在歷史搜索中的高質量路徑點難以得到進一步利用的缺點，提出了一種將路徑點分別評估和演化的方法用于二維無人機路徑規(guī)劃。Huang等[15]提出了一種基于全局最優(yōu)解競爭的改進PSO算法，并將路徑規(guī)劃器應用于三維無人機。Zhang[16]提出了一種改進的基于相位角編碼并結合突變適應機制的果蠅優(yōu)化算法，以解決無人機(UAV)路徑規(guī)劃問題。

粒子群優(yōu)化算法(Particle Swarm Optimization, PSO)[17]基于一個簡單的機制，通過模仿鳥類等群居動物的群體覓食行為。粒子群中包含有一群粒子，每個粒子表示優(yōu)化問題的一個候選解，并且每個粒子都有一個在D維搜索空間中飛行的位置和速度。為了找到全局最優(yōu)值，每個個體根據(jù)某些特定的適應值進行自我評估，在搜索過程中記住自己搜索到的最佳位置pbest以及全體的最佳位置gbest。利用這兩個極值來調整飛行，最終找到食物的位置。與其他受生物種群行為特征啟發(fā)的算法一樣，優(yōu)化問題從隨機初始解開始，通過計算適應度值來評估解的質量，通過迭代進化的方式逐步找到最優(yōu)解，反復迭代多次。

1 無人機路徑規(guī)劃問題描述

在搜索空間中，定義起始點為PS(x S,yT)，目標點為PT(xT,yT)，如圖1所示。圖1 描述無人機的飛行環(huán)境。飛行任務是根據(jù)目標函數(shù)下，在S和T之間生成最優(yōu)路徑。一條優(yōu)化路徑可以用一個集合C= {PS,P1,P2···,PD,PT}其中路徑點PD= (x d,yd)來表示。然后通過連接各個路徑點得到一條無人機的飛行路線。威脅的區(qū)域采用圓形來定義，如圖1所示。

圖1 環(huán)境描述

在進行路徑規(guī)劃之前，首先需要對運動空間進行離散化，使其成為對路徑規(guī)劃有意義的表示。這種表示與搜索算法密切相關，規(guī)劃算法只有在與環(huán)境表示相配合的情況下才會有好的表現(xiàn)。令(x,y)表示任務空間中任意一點的坐標，任務空間可以被表示為：

其中，xmin，xmax，ymin，ymax分別定義為,x y的邊界值。

當無人機執(zhí)行飛行任務時，可能會面臨敵方導彈攻擊、雷達探測等高風險威脅。因為雷達和導彈的防御范圍是全方位的，因此用圓來描述威脅源的數(shù)學模型。第i個雷達或導彈的數(shù)學模型可以被寫成：

其中，(xk,yk)為第k個威脅源的中心坐標，rk是第k個威脅源的半徑。

2 建立目標函數(shù)

無人機航跡的目標函數(shù)主要包括障礙危險成本和長度成本，所以目標函數(shù)是障礙威脅和長度的加權總和，可表示為：

其中，J1為長度成本，J2為障礙危險成本，w1、w2分別為障礙危險成本和長度成本的權重。

長度成本可通過下式來計算：

其中，i=D+1時，Pi表示目標點。i-1=0時代表起點。

規(guī)劃路徑的安全代價可計算為：

其中，Oj為第j個障礙物的圓心，rj為第j個障礙物的圓心。

3 改進粒子群算法

3.1 粒子群算法

粒子群優(yōu)化算法通過將求解的問題看作是空間中的粒子，算法通過模仿昆蟲，鳥類的覓食行為來解決各種工程最優(yōu)化問題。鳥群中個體的飛行過程類比為單個粒子的運動過程，將其群體覓食行為的過程類比為尋找最優(yōu)解的迭代過程。在該過程中基本無需外部信息，只通過群體內部的交流。在粒子群算法中，假設每個粒子都能記住歷史上的最佳位置，也就是整個種群所發(fā)現(xiàn)的最佳位置，被稱為全局最優(yōu)解，以及每個粒子目前所發(fā)現(xiàn)的最佳位置，即個體最佳位置。每個粒子向個人最佳位置和全局最佳位置學習。該算法操作簡單、實現(xiàn)容易、精度高、且具有優(yōu)秀的收斂性。

設在D維空間搜索域中，群體中有N個粒子，N為種群規(guī)模，種群規(guī)模不宜過小，以保證種群多樣性，提高算法性能；且不宜過大，致使收斂速度過于緩慢。

每個粒子i的位置表示為搜索域中的一個向量Xi=(xi1,xi2,···,xiD)，速度為Vi= (vi1,vi2,···,viD),i= 1,2,···,N。粒子個體的最優(yōu)位置和粒子群體整體最優(yōu)位置分別用pbest和gbest來表示，第k次迭代中粒子的位置及速度按照以下方程進行更新：

其中，ω為慣性權重，c1為個體加速系數(shù)，c2為群體加速系數(shù)，r1，r2為[0,1]上均勻分布的隨機數(shù)。

個體加速系數(shù)c1表示粒子下一步運動受自己經驗驅使所占的權重。即將粒子推向個體最優(yōu)位置pbest的加速權重；群體加速系數(shù)c2表示粒子下一步運動受其它粒子經驗影響所占的權重。即將粒子推向群體最優(yōu)位置gbest的加速權重。c1的值過小會造成群體多樣性降低，導致搜索局限。c2過小自會導致自我認知型粒子群算法，即社會共享信息少，致使收斂速度緩慢。

3.2 改進粒子群算法

慣性權重ω指粒子保持原有運動狀態(tài)的能力，使其有能力在搜索域中對新控件進行探索。進而使得PSO在全局搜索和局部開發(fā)之間取得平衡。ω作為粒子群優(yōu)化算法的關鍵參數(shù)之一，它的取值很大程度上決定了算法性能：在算法前期，ω值大有利于粒子搜索更大的范圍，在算法后期，ω值較小則可以加快收斂速度。

當慣性權值ω較小時，算法的局部搜索能力較好。ω較大時，算法的全局搜索能力得到了提高，在接近最優(yōu)位置時瞬間又飛越了最優(yōu)位置，這樣算法就很難收斂。一般選取慣性權重ω的值在[0.4, 0.9]范圍內，慣性權重ω的值很嚴重影響算法的優(yōu)化性能。根據(jù)種群中各粒子的適應度值，種群中的粒子將劃分為“開發(fā)型”與“探索型”兩種?！伴_發(fā)型”粒子主要任務是對已找到的優(yōu)質解進行優(yōu)化，而“探索型”粒子用于找到優(yōu)質解的區(qū)域。針對不同的搜索類型，建立了分段非線性慣性權重函數(shù), “開發(fā)型”慣性權重采用隨機方法獲得，粒子群算法中的慣性權值ω采用隨機機制，隨機機制有利于保持學習多樣性和種群多樣性可以避免過早收斂性和落入局部最優(yōu)。而 “探索型”慣性權重收斂速度最慢，因此，通過分組的方式來調整慣性權重的大小可以有效提高算法的搜索效率。改進后的慣性權重ω描述為：

4 仿真實驗與分析

為了研究算法對無人機路徑規(guī)劃的可行性和有效性，在MATLAB2016a仿真環(huán)境下進行實驗，并與PSO算法進行了進一步的實驗比較。環(huán)境1中設置起始點的坐標(0, 0)，目標點的坐標為(400, 600)。環(huán)境1中設置3個障礙物，其中心坐標分別為(150, 450)、(400, 300)和(120, 150)。 環(huán)境2中設置起點坐標為(200, 100)，目標點的坐標為(800, 800)。環(huán)境2中設置6個障礙物，其坐標為(300, 200)、(500, 400)、(600, 200)、(300, 500)、(700, 550)和(600, 750)。粒子個數(shù)N=100，最大迭代次數(shù)Tmax=100。

每個算法獨立運行25次，采用兩種算法進行路徑規(guī)劃，兩種算法的適應度值的結果如表1所示。PSO和改進的PSO算法得到的規(guī)劃路徑在兩種環(huán)境中的規(guī)劃路徑曲線分別如圖2和4所示，適應度值變化曲線如圖3和5所示。

表1 兩種算法的適應度值結果

圖2 環(huán)境1的規(guī)劃路徑

圖3 環(huán)境1中適應度值變化曲線

比較表1中的兩種算法的適應度值可以看出，在環(huán)境1和2中，F(xiàn)PSO算法的最優(yōu)適應度值小于原PSO算法，F(xiàn)PSO算法的平均適應度值比PSO算法要小，平均適應度值表示算法在多次運行時的穩(wěn)定性。對比實驗結果在PSO和FPSO之間，可以得出PSO的參數(shù)更新策略具有更強大的尋優(yōu)能力。這兩種環(huán)境下的實驗結果證明了FPSO算法的優(yōu)越性，可以用于求解無人機航路規(guī)劃問題。

圖4 環(huán)境2的規(guī)劃路徑

圖5 環(huán)境2中適應度值變化曲線

5 結論

在PSO算法用于處理無人機的路徑規(guī)劃問題中，由于傳統(tǒng)PSO算法存在易陷入局部最優(yōu)的缺陷，本文從整個種群粒子的適應度值出發(fā)，將種群劃分為探索和開發(fā)兩個子部分，在兩個子部分中分別采用不同的慣性權重ω選擇策略，以此來提高了算法的多樣性和搜索尋優(yōu)能力。通過對傳統(tǒng)PSO算法和改進后的PSO算法進行路徑規(guī)劃仿真并對結果進行對比分析。與傳統(tǒng)PSO算法相比，F(xiàn)PSO可以得到一條更平滑和路線較短的無人機飛行路線。