基于改進(jìn)粒子群算法的UAV航跡規(guī)劃方法

1212

(1.衛(wèi)星導(dǎo)航系統(tǒng)與裝備技術(shù)國家重點(diǎn)實驗室，石家莊 050081；2.中國電子科技集團(tuán)公司 第五十四研究所，石家莊 050081)

0 引言

無人機(jī)具有低成本、操作簡單、無人員傷亡等特點(diǎn)，正在成為未來信息化的重要基礎(chǔ)平臺。隨著近年來無人機(jī)越來越廣泛的應(yīng)用，無人機(jī)集群協(xié)同編隊飛行已經(jīng)成為了當(dāng)前研究的熱點(diǎn)。無人機(jī)集群航跡規(guī)劃是實現(xiàn)集群編隊飛行執(zhí)行任務(wù)的關(guān)鍵技術(shù)之一，其是指考慮飛行地形、氣候、威脅等因素，以及飛機(jī)自身平臺性能約束，為無人機(jī)集群制定從初始位置到目標(biāo)位置的最優(yōu)飛行路徑。

解決無人機(jī)集群航跡規(guī)劃問題的關(guān)鍵在于優(yōu)化算法設(shè)計，當(dāng)前國內(nèi)外對無人機(jī)航跡規(guī)劃算法設(shè)計進(jìn)行了一些嘗試與突破，但仍存在較大的局限性，主要問題在于算法計算復(fù)雜度、求解精度、搜索時間難以平衡同時滿足任務(wù)要求，因此設(shè)計具有計算快、精度高、容錯率大等特點(diǎn)的航跡規(guī)劃算法是未來發(fā)展趨勢。

解決航跡規(guī)劃問題的算法一般包括傳統(tǒng)優(yōu)化算法和各類進(jìn)化算法，其中進(jìn)化算法又以群智能算法為重點(diǎn)研究對象。粒子群優(yōu)化算法就是一類典型的群智能算法，也是本文重點(diǎn)研究對象。粒子群算法(particle swarm optimization，PSO)是在1995年由美國社會心理學(xué)博士Kennedy和電子工程學(xué)博士 Eberhart共同提出的一種優(yōu)化算法，是一個基于迭代方法的隨機(jī)搜索與最優(yōu)化處理過程[1]。和遺傳算法相似，粒子群算法也是通過迭代尋找最優(yōu)解，但它沒有遺傳算法中“交叉”和“變異”的操作，因此規(guī)則更加簡單。在粒子群優(yōu)化算法中，目標(biāo)被看作是所優(yōu)化問題的可能解，個體被看作沒有質(zhì)量和體積的粒子，每個粒子的運(yùn)動方向和速度都受到自己和群體的歷史狀態(tài)信息的雙重影響，利用群體中個體間的信息共享和協(xié)作，引導(dǎo)群體朝著更好的解的方向運(yùn)動，從而完成整個粒子群在解空間中搜索最優(yōu)解[2]。

1 經(jīng)典粒子群算法

在D維的解空間上，粒子群的速度更新和位置更新如下兩式所示，其中d表示位置或速度的第d維。

通常用Ns表示粒子群種群規(guī)模，記f(xi)為所優(yōu)化問題的評價函數(shù)，粒子位置的優(yōu)劣是依靠f(xi)的值來決定的。得到粒子新的位置后，可以求出對應(yīng)的f(xi)，并更新粒子的歷史最優(yōu)位置信息pBesti和種群的歷史最優(yōu)位置信息gBesti，繼續(xù)迭代進(jìn)行下一步操作。

圖1是粒子群優(yōu)化算法求解優(yōu)化問題的示意圖，搜索空間是二維，全局最優(yōu)解在黑點(diǎn)處，粒子從初始位置更新到了更新位置。其中v1是全局歷史最優(yōu)解引起的粒子的速度，v2是粒子歷史最優(yōu)解引起的速度，v3是粒子原來具有的速度。粒子最終的速度v由v1、v2和v3共同決定，使得粒子從初始位置到達(dá)更新位置，接下來以同樣的方式繼續(xù)更新速度和位置，粒子會逐漸接近全局最優(yōu)解位置[4]。

圖1 粒子群優(yōu)化算法求解優(yōu)化問題的示意圖

粒子群算法的優(yōu)點(diǎn)包括：通用性較強(qiáng)、搜索能力全面、算法原理簡單等等。但是標(biāo)準(zhǔn)粒子群算法的缺點(diǎn)也很明顯，比如在以全局最優(yōu)值為搜索目標(biāo)時局部搜索能力較差、容易早熟陷入局部最優(yōu)，無法保證一定能夠搜索到全局最優(yōu)值等等[5]。

2 改進(jìn)粒子群算法在航跡規(guī)劃中的應(yīng)用

由于傳統(tǒng)粒子群優(yōu)化算法應(yīng)用在集群航跡規(guī)劃中有早熟收斂過快，后期容易陷入局部最優(yōu)，搜索到的航跡點(diǎn)軌跡不一定是最優(yōu)解的問題，而單純增加種群數(shù)量和節(jié)點(diǎn)個數(shù)則會導(dǎo)致計算量大幅度增加[6]，故本文采用整體粒子群航跡規(guī)劃和節(jié)點(diǎn)間粒子群航跡再規(guī)劃相結(jié)合的策略，可以更好地滿足航跡規(guī)劃從快速全局搜索過渡到精確局部搜索的要求。

整體粒子群航跡規(guī)劃。建立無人機(jī)航跡規(guī)劃模型，考慮無人機(jī)各項約束條件、優(yōu)化指標(biāo)等信息，設(shè)定粒子群種群數(shù)量、節(jié)點(diǎn)數(shù)目、迭代次數(shù)、學(xué)習(xí)因子、慣性權(quán)重等參數(shù)，快速規(guī)劃得出無人機(jī)由當(dāng)前位置到目標(biāo)位置的最優(yōu)飛行航跡。

節(jié)點(diǎn)間粒子群航跡再規(guī)劃。在整體粒子群航跡規(guī)劃之后，對于每兩個相鄰的節(jié)點(diǎn)間的航跡，先利用改進(jìn)評價函數(shù)判斷其可靠性，若滿足指標(biāo)則保留，若不滿足指標(biāo)，則選取該相鄰兩個節(jié)點(diǎn)作為初始點(diǎn)和目標(biāo)點(diǎn)，考慮無人機(jī)各種約束信息，改進(jìn)位置速度更新公式使其滿足局部搜索要求，進(jìn)行粒子群航跡的再規(guī)劃。

利用改進(jìn)粒子群算法進(jìn)行航跡規(guī)劃流程大致如圖2所示。

圖2 航跡規(guī)劃流程圖

對于整體粒子群航跡規(guī)劃，首先進(jìn)行航跡規(guī)劃模型建立，包括環(huán)境建模以及確定約束條件和評價函數(shù)[7-8]。

航跡規(guī)劃的環(huán)境模型包括基準(zhǔn)地形模型、障礙區(qū)域以及威脅區(qū)域3個部分?；鶞?zhǔn)地形建模設(shè)置飛行區(qū)域為200 m×200 m×100 m的直角坐標(biāo)區(qū)域；障礙區(qū)域建模采用山峰模型，其數(shù)學(xué)描述為：

式中，hi表示第i座山的高度，(xi,yi)為山峰的地理中心坐標(biāo)，xsi,ysi分別表示山峰在x軸和y軸方向的坡度向量，(x,y)代表地形中每個點(diǎn)投影到平面的點(diǎn)坐標(biāo)，z(x,y)表示地形中每個點(diǎn)的高度；威脅區(qū)域一般指電磁干擾區(qū)域、禁飛區(qū)域以及敵方探測區(qū)域[9]等，可采用半球形模型對威脅區(qū)域建模，其數(shù)學(xué)描述為：

式中，Wi(x,y,z)表示第i個威脅區(qū)域；(xi,yi,0)表示威脅區(qū)域的中心；ri表示威脅區(qū)域半徑。

約束條件一般包括以下幾項[10-11]：

1)航跡長度Lp：無人機(jī)一次任務(wù)的總飛行路程。設(shè)第i個節(jié)點(diǎn)與下一個節(jié)點(diǎn)間的距離為li，兩個節(jié)點(diǎn)的坐標(biāo)分別為(xi,yi,zi)，(xi+1,yi+1,zi+1)，則有:

2)剩余飛行時間tp：無人機(jī)在執(zhí)行一次任務(wù)過程中，最大飛行時間與已飛行時間的差值；

3)最低飛行高度h：無人機(jī)在飛行中與地形之間允許的最短距離，h太小會增加無人機(jī)與地面碰撞的概率；

還有很多無人機(jī)集群約束和環(huán)境約束條件，例如無人機(jī)數(shù)量約束、節(jié)點(diǎn)間距約束、大氣威脅等[12]。本文選擇航跡長度、剩余飛行時間和最低飛行高度來組成整體航跡評價函數(shù)，如下式所示:

式中,N為節(jié)點(diǎn)總數(shù)，Li為第i個節(jié)點(diǎn)與前一個節(jié)點(diǎn)間的距離；ti為到第i個節(jié)點(diǎn)的剩余時間；Ti為第i個節(jié)點(diǎn)處的高度威脅值。φ1、φ2和φ3為0～1的權(quán)重系數(shù)，通過調(diào)整它們的大小來改變各項約束條件對整體航跡評價函數(shù)的影響。

對于節(jié)點(diǎn)間粒子群航跡再規(guī)劃，其要求航跡搜索的解更加精確，所得到的航跡結(jié)果更加圓滑，故可以采用改進(jìn)航跡評價函數(shù)和速度位置更新公式的方法增強(qiáng)算法局部搜索能力。

與整體粒子群航跡規(guī)劃評價函數(shù)不同，節(jié)點(diǎn)間航跡的評價函數(shù)應(yīng)當(dāng)更加關(guān)注無人機(jī)自身飛行條件約束情況[13]。本文選擇最小轉(zhuǎn)彎角、最大上升角和最大下降角來組成節(jié)點(diǎn)間航跡評價函數(shù)，如下式所示:

fi=?1θi+?2φi+?3αi，i=1,…,N-1

式中,N為節(jié)點(diǎn)總數(shù)；θi為第i個節(jié)點(diǎn)間距中的最小轉(zhuǎn)彎角度；φi為第i個節(jié)點(diǎn)間距中的最大上升角度，αi為第i個節(jié)點(diǎn)間距中的最大下降角度。?1、?2和?3為0～1的權(quán)值。通過該評價函數(shù)判斷各個節(jié)點(diǎn)間的航跡是否符合要求，滿足要求的則保留，不滿足要求的則利用改進(jìn)的粒子群更新公式進(jìn)行節(jié)點(diǎn)間航跡再規(guī)劃。

對于節(jié)點(diǎn)間粒子群航跡規(guī)劃的更新公式的改進(jìn)主要在于合理調(diào)節(jié)算法參數(shù)上。由于慣性權(quán)重ω的取值對算法的搜索性能有很大的影響，較大的慣性權(quán)重可加快算法搜索速度，較小的慣性權(quán)重可增強(qiáng)算法搜索能力。但是單純設(shè)計成線性遞減的慣性權(quán)重在迭代后期不能很好地滿足精確搜索的要求，而節(jié)點(diǎn)間粒子群航跡規(guī)劃重點(diǎn)就在于迭代后期的精確搜索，故本文設(shè)計了一種針對局部精確搜索的慣性權(quán)重調(diào)整方法。具體的調(diào)整公式為：

式中，ωmax和ωmin為慣性權(quán)重的最大值和最小值，t為已迭代次數(shù)，T為最大迭代次數(shù)。λ1和λ2表示算法前期所占的比例，范圍為0≤λ1<λ2<1。λ1和λ2的取值是由規(guī)劃問題的復(fù)雜程度、要求的搜索精度等因素共同決定的[14]。由于節(jié)點(diǎn)間粒子群搜索前已經(jīng)由整體粒子群搜索規(guī)劃好大致航跡，所以在實驗中λ1應(yīng)當(dāng)盡可能地取小，必要時可取為0。這種分段式調(diào)整策略使得在節(jié)點(diǎn)間航跡規(guī)劃的初期有一個短暫的快速搜索階段，防止在算法初期就陷入局部搜索停滯不前的情況；在算法前中期搜索速度快速下降，搜索精度快速大幅度上升，并在算法后期維持最高的搜索精度，有助于節(jié)點(diǎn)間航跡規(guī)劃問題的解決[15-16]。

3 仿真與分析

針對本文提出的基于改進(jìn)粒子群算法的航跡規(guī)劃方法，利用Matlab R2017a進(jìn)行仿真，并與傳統(tǒng)和其他粒子群航跡規(guī)劃方法進(jìn)行對比分析。

建立環(huán)境模型：設(shè)定2000 m×2000 m×1000 m的直角坐標(biāo)區(qū)域，給定半球形威脅模型、山峰模型的中心及半徑。環(huán)境建模如圖3所示。

圖3 環(huán)境建模仿真

設(shè)置整體航跡規(guī)劃粒子群算法參數(shù)：設(shè)定無人機(jī)數(shù)量為12，種群數(shù)量N=50，群體最大迭代次數(shù)T=100，航跡節(jié)點(diǎn)數(shù)目取為30，最大迭代時間tmax取1000。學(xué)習(xí)因子取C1=C2=2，慣性權(quán)重ω取0.7。整體粒子群航跡規(guī)劃評價函數(shù)中φ1、φ2和φ3分別取0.5,0.3,0.2。整體粒子群航跡規(guī)劃仿真結(jié)果如圖4所示。

圖4 整體粒子群航跡規(guī)劃圖

繼續(xù)進(jìn)行節(jié)點(diǎn)間航跡規(guī)劃。利用節(jié)點(diǎn)間航跡規(guī)劃評價函數(shù)判斷各節(jié)點(diǎn)航跡合理性，?1、?2和?3分別取0.4,0.3,0.3。設(shè)置節(jié)點(diǎn)間航跡規(guī)劃粒子群算法參數(shù)：種群數(shù)量改為100，航跡節(jié)點(diǎn)數(shù)目改為10。慣性權(quán)重ω按照調(diào)整公式設(shè)置，其中λ1和λ2分別取為0.1和0.3，ωmax和ωmin取為0.9和0.4。其余參數(shù)不變。

12架無人機(jī)航跡規(guī)劃結(jié)果如圖5所示?？梢姛o人機(jī)編隊形成圓滑航跡，繞過障礙和山峰飛行并在目的地形成大致圓形構(gòu)型。

圖5 最終航跡規(guī)劃結(jié)果圖

表1 算法性能對比

可以看出，本文提出的改進(jìn)算法對比傳統(tǒng)粒子群航跡規(guī)劃算法(BPSO)，在整體航跡規(guī)劃評價值相差不多的情況下，航跡規(guī)劃時間明顯縮短；對比慣性權(quán)重線性變化的粒子群算法(LPSO)，整體航跡規(guī)劃評價值和時間相近，而節(jié)點(diǎn)間航跡規(guī)劃評價平均值明顯更大，航跡規(guī)劃時間也明顯縮短，因此可以很好地滿足無人機(jī)集群航跡規(guī)劃搜索速度和精度的要求。但是，無論是LPSO還是IPSO，兩部分航跡規(guī)劃的時間總和都要比一次航跡規(guī)劃時間要多，雖然很大程度上提高了解的精度，卻在某些方面不能滿足航跡規(guī)劃實時性的需要，因此也為后續(xù)的研究指出了方向。

4 結(jié)束語

本文提出了一種基于改進(jìn)粒子群算法的無人機(jī)航跡規(guī)劃策略，相較于標(biāo)準(zhǔn)粒子群算法和傳統(tǒng)航跡規(guī)劃策略具有如下優(yōu)點(diǎn)：

1)算法適應(yīng)性強(qiáng)。對于慣性權(quán)重ω的分段式調(diào)整簡單快捷，使得算法既滿足了航跡規(guī)劃前期的快速搜索要求又滿足了后期高搜索精度要求，對于評價函數(shù)的兩種設(shè)計使得不同階段的航跡規(guī)劃更加有針對性。

2)航跡規(guī)劃策略靈活。采用的整體航跡規(guī)劃和節(jié)點(diǎn)間航跡規(guī)劃相結(jié)合的策略確保了在計算資源的高效利用下，快速搜索到滿足要求的精確航跡。

該算法策略可以很好地滿足航跡規(guī)劃的需求，但仍存在一些不足之處，比如應(yīng)對突發(fā)威脅時缺乏在線實時航跡規(guī)劃手段，集中式計算負(fù)擔(dān)過大有時不能滿足需要等等。后續(xù)將在算法自主實時性方面尋求突破，重點(diǎn)關(guān)注在線實時航跡規(guī)劃方法和分布式算法架構(gòu)，完善本文所提出的無人機(jī)集群航跡規(guī)劃策略。