王小璐，黃辰，于遠(yuǎn)航，陳福豪，胡蝶，陸琪，崔曦予

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

0 引言

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

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

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

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

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

圖1 環(huán)境描述

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

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

當(dāng)無人機(jī)執(zhí)行飛行任務(wù)時，可能會面臨敵方導(dǎo)彈攻擊、雷達(dá)探測等高風(fēng)險威脅。因為雷達(dá)和導(dǎo)彈的防御范圍是全方位的，因此用圓來描述威脅源的數(shù)學(xué)模型。第i個雷達(dá)或?qū)椀臄?shù)學(xué)模型可以被寫成：

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

2 建立目標(biāo)函數(shù)

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

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

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

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

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

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

3 改進(jìn)粒子群算法

3.1 粒子群算法

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

設(shè)在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次迭代中粒子的位置及速度按照以下方程進(jìn)行更新：

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

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

3.2 改進(jìn)粒子群算法

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

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

4 仿真實驗與分析

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

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

表1 兩種算法的適應(yīng)度值結(jié)果

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

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

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

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

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

5 結(jié)論

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