陳 偉（電子信息控制重點(diǎn)實(shí)驗(yàn)室）

本文分析了復(fù)雜環(huán)境下無人機(jī)航跡規(guī)劃問題。首先，基于飛行環(huán)境建立了約束模型和優(yōu)化模型；其次在算法的設(shè)計(jì)上，采用了引入局部搜索操作的粒子群算法，有效平衡了算法在整個(gè)搜索過程中的全局搜索能力和局部搜索能力，并通過仿真實(shí)驗(yàn)證明了模型和算法的有效性。

引言

無人機(jī)具有低成本、小體積、強(qiáng)隱蔽性和高生存力等特點(diǎn)，在多個(gè)領(lǐng)域取得了廣泛應(yīng)用。為保證無人機(jī)高效完成指定任務(wù)，需要為其規(guī)劃特定的航跡，而隨著任務(wù)復(fù)雜性和飛行環(huán)境復(fù)雜多變性逐漸增加，預(yù)規(guī)劃航跡往往不能滿足實(shí)際需求，需要對環(huán)境和任務(wù)進(jìn)行實(shí)時(shí)評(píng)估，并進(jìn)行在線航跡規(guī)劃。

無人機(jī)航跡規(guī)劃技術(shù)，是在綜合考慮無人機(jī)任務(wù)、飛行環(huán)境以及自身性能約束下，設(shè)計(jì)合理的飛行路線，以最大限度地保障無人機(jī)成功完成任務(wù)并返航。其核心是在綜合考慮無人機(jī)平臺(tái)約束和環(huán)境約束前提下，如續(xù)航時(shí)間、油耗、機(jī)動(dòng)性能、威脅等，設(shè)計(jì)最優(yōu)或較優(yōu)的航跡。由于約束因素較多，數(shù)學(xué)模型較為復(fù)雜，是典型的NP-Hard優(yōu)化問題。在相關(guān)理論研究中，廣泛采用的方法包括概略圖法、單元分解法、人工勢場法、數(shù)學(xué)規(guī)劃法和進(jìn)化算法。其中，進(jìn)化算法基于其啟發(fā)式的搜索能力，能夠處理復(fù)雜且變化的問題，得到廣泛的研究，主要包括遺傳算法、蟻群算法和粒子群算法。

遺傳算法是一種模擬生物進(jìn)化過程的啟發(fā)式搜索算法，在早期的路徑規(guī)劃問題中被廣泛采用。但受限于編碼方式，遺傳算法在進(jìn)行航跡規(guī)劃時(shí)的編解碼過程往往比較復(fù)雜，增加了計(jì)算復(fù)雜度。蟻群算法是模擬螞蟻覓食行為的啟發(fā)式算法，通過不斷更新起點(diǎn)至食物源的路徑信息素實(shí)現(xiàn)最優(yōu)路徑的獲取。由于蟻群算法起源于路徑選擇，使其在航跡規(guī)劃中設(shè)計(jì)思路清晰、編解碼過程簡單，應(yīng)用非常廣泛。然而，蟻群算法的運(yùn)行機(jī)制使得求解過程易于陷入局部最優(yōu)值，同時(shí)當(dāng)解空間增大時(shí)，計(jì)算復(fù)雜度顯著提升，限制了其在三維航跡規(guī)劃上的應(yīng)用。

粒子群算法是模擬鳥群覓食行為的啟發(fā)式算法，形式簡單，性能高效，廣泛應(yīng)用于神經(jīng)網(wǎng)絡(luò)、數(shù)據(jù)挖掘等領(lǐng)域。在航跡規(guī)劃中，有多種三維航跡規(guī)劃的粒子群算法，第一種是基于地形和威脅信息建立最小威脅曲面，并在該曲面上進(jìn)行最優(yōu)航跡搜索。同時(shí)，通過將三維航跡在水平面進(jìn)行投影構(gòu)建有限多項(xiàng)式，進(jìn)而將航跡規(guī)劃問題轉(zhuǎn)化為解空間多項(xiàng)式組合問題，降低了計(jì)算復(fù)雜度；第二種是以平臺(tái)機(jī)動(dòng)性能限制、威脅程度和目標(biāo)距離作為適應(yīng)度函數(shù)，采用連續(xù)粒子群算法進(jìn)行實(shí)時(shí)規(guī)劃，求取航跡的中間節(jié)點(diǎn)；第三種粒子群算法，引入自適應(yīng)變異算子，實(shí)現(xiàn)粒子速度和位置的自適應(yīng)更新和變異，以處理三維航跡規(guī)劃問題；第四種是結(jié)合粒子群優(yōu)化算法和B樣條插值方法，通過特定的編碼方式和適應(yīng)度評(píng)價(jià)函數(shù)，使得生成的航跡具有較好的平滑度；第五種以障礙物頂點(diǎn)為基礎(chǔ)構(gòu)造二維解空間，將航跡規(guī)劃問題轉(zhuǎn)化為非線性最小化問題，在靜態(tài)和動(dòng)態(tài)環(huán)境下實(shí)現(xiàn)了最優(yōu)無碰撞航跡的設(shè)計(jì)；第六種是針對粒子群算法后期搜索能力不足等缺點(diǎn)，對慣性權(quán)重因子進(jìn)行了改進(jìn)，并在三維航跡規(guī)劃中取得了良好的效果。

相關(guān)研究表明，標(biāo)準(zhǔn)的粒子群算法在前期具有良好的全局搜索能力，但后期局部搜索能力不足，因此引入的動(dòng)態(tài)調(diào)整慣性權(quán)重因子方法被廣泛采用，以提升算法在后期的局部搜索性能。然而，在相關(guān)的改進(jìn)算法中，由于慣性權(quán)重因子的逐漸減小，算法的全局搜索能力顯著下降，易于陷入局部最優(yōu)解。為保證算法的全局搜索能力，同時(shí)加強(qiáng)算法的局部搜索能力，本文引入局部搜索算子，實(shí)現(xiàn)算法整體性能的提升。

問題分析

在航跡規(guī)劃的相關(guān)設(shè)計(jì)中，主要對飛行環(huán)境模型、約束條件和性能指標(biāo)函數(shù)進(jìn)行分析。在飛行環(huán)境模型中，主要包括可通行威脅區(qū)和不可通行威脅區(qū)。其中，可通行威脅區(qū)是指無人機(jī)可以從該區(qū)域飛行通過，但該區(qū)域的某些因素會(huì)影響無人機(jī)的飛行安全和任務(wù)執(zhí)行能力，包括強(qiáng)風(fēng)區(qū)、側(cè)風(fēng)區(qū)或其他人為影響因素。不可通行威脅區(qū)是指無人機(jī)不能從該區(qū)域威脅通過，否則無人機(jī)會(huì)損毀，主要包括地形限制和障礙物等。其飛行環(huán)境模型如圖1所示。

圖1 飛行環(huán)境威脅圖。

在約束條件分析上，主要考察平臺(tái)機(jī)動(dòng)性能的限制，包括轉(zhuǎn)向角、最小航跡段和油耗。設(shè)無人機(jī)航跡表示如(1)所示。

其中（xS，yS）和（xT，yT）分別表示無人機(jī)任務(wù)的起點(diǎn)和終點(diǎn)，（xi，yi）表示航跡第i個(gè)中間節(jié)點(diǎn)。

根據(jù)平臺(tái)的機(jī)動(dòng)性能，航跡的轉(zhuǎn)向角應(yīng)不小于特定角度θmin，即有

其中(xi-1，yi-1)，(xi，yi)，和(xi+1，yi+1)為航跡的相鄰節(jié)點(diǎn)，Angle{.，.}為兩向量間的夾角，可由余弦定理進(jìn)行計(jì)算。

在最小航跡段約束中，由于平臺(tái)的慣性，無人機(jī)在相鄰兩次改變飛行姿態(tài)期間，必須保證最低的直線飛行距離，即有

在油耗約束中，忽略無人機(jī)在不同飛行速度下油耗的差異，將油耗與整體航程等同考慮，可得

在航跡規(guī)劃中，性能指標(biāo)作為衡量航跡的唯一標(biāo)準(zhǔn)，在很大程度上決定了算法的性能。結(jié)合相關(guān)文獻(xiàn)研究，以航跡所經(jīng)過區(qū)域的威脅度和航跡長度作為評(píng)價(jià)指標(biāo)，可以建立如下的優(yōu)化數(shù)學(xué)模型。其中，α為權(quán)重因子，表征航跡長度length(x，y)和航跡威脅threat(x，y)在總體性能指標(biāo)中所占比重，可以根據(jù)不同需求進(jìn)行具體設(shè)計(jì)。

算法設(shè)計(jì)

粒子群優(yōu)化算法的每個(gè)粒子都有自己的位置和速度，粒子的位置代表解空間的點(diǎn)，通常以xi表示，粒子的速度代表粒子的搜索方向和前進(jìn)距離，通常以vi表示。該算法在初始時(shí)候隨機(jī)初始化，以f(xi)衡量該粒子的適應(yīng)度，并以pBesti表示第i個(gè)粒子搜索過的最優(yōu)位置，以gBest表示種群搜索過的最優(yōu)位置。在進(jìn)化過程中，粒子基于個(gè)體最優(yōu)信息和全局最優(yōu)信息進(jìn)行更新，如(6)、（7）所示。

其中ωd為慣性權(quán)重因子，c1和c2分別為個(gè)體學(xué)習(xí)因子和全局學(xué)習(xí)因子。

研究表明，粒子群算法的搜索能力和更新方程中的參數(shù)有很大關(guān)系，包括慣性權(quán)重因子、個(gè)體/全局學(xué)習(xí)因子和種群規(guī)模。慣性權(quán)重因子能夠平衡算法的全局和局部搜索能力，是重要的控制參數(shù)。研究指出，較大的慣性權(quán)重因子可以保證算法具有較好的全局搜索能力，而較小的慣性權(quán)重因子可以保證較好的局部搜索能力。學(xué)習(xí)因子決定著粒子向個(gè)體歷史信息和全局歷史信息學(xué)習(xí)的程度，相關(guān)文獻(xiàn)對其進(jìn)行了深入研究并給出了指導(dǎo)性設(shè)計(jì)意見。在種群規(guī)模上，大量的理論研究和仿真實(shí)例表明，針對解空間較小的情形，種群規(guī)模為20，一般能夠滿足性能需求，而對于復(fù)雜解空間，種群規(guī)模為50，一般能夠滿足性能需求。

從上述分析可知，通過動(dòng)態(tài)調(diào)節(jié)慣性權(quán)重因子，能夠有效平衡算法在前期的全局搜索能力和后期的局部搜索能力，一般采用線性或指數(shù)遞減的形式。另一方面，由于算法在中后期的全局搜索能力下降，會(huì)增加陷入局部最優(yōu)解的風(fēng)險(xiǎn)，尤其在處理具有較多局部最小值的問題時(shí)性能欠佳。針對此類情形，本文提出了局部搜索的優(yōu)化策略，其中粒子群算法始終保持較大的慣性權(quán)重因子，以保證算法對全局的搜索能力。同時(shí)，在每一次迭代后引入局部搜索算子，對當(dāng)前解的相鄰空間進(jìn)行局部隨機(jī)搜索，如(8)所示。

可以看出，局部搜索的前進(jìn)方向依然受個(gè)體最優(yōu)和全局最優(yōu)的影響，可以有效地增加算法對歷史信息的利用效率。同時(shí)應(yīng)滿足v d＜vmax，其中vmax表征算法進(jìn)行局部搜索領(lǐng)域的范圍。根據(jù)隨機(jī)搜索的步長，可以形成新的個(gè)體。進(jìn)一步，將局部搜索的新個(gè)體與當(dāng)前個(gè)體進(jìn)行比較，保留性能較優(yōu)個(gè)體。算法流程如圖2所示。

圖2 改進(jìn)PSO算法流程圖。

仿真實(shí)驗(yàn)

根據(jù)圖1的環(huán)境威脅圖，采用基于局部搜索的改進(jìn)粒子群算法，設(shè)計(jì)種群數(shù)為50，迭代50代，慣性權(quán)重因子ω=0.9，學(xué)習(xí)因子分別為c1=c2=1.5，其穩(wěn)定的航跡規(guī)劃結(jié)果（最優(yōu)解出現(xiàn)概率不低于80%）如圖3所示。而對于標(biāo)準(zhǔn)粒子群算法（權(quán)重因子動(dòng)態(tài)變化），在采用相同種群規(guī)模時(shí)達(dá)到相同的穩(wěn)定結(jié)果需迭代100代左右，體現(xiàn)了局部搜索操作的有效性。

為了進(jìn)一步比較標(biāo)準(zhǔn)粒子群算法與本文改進(jìn)粒子群算法的效率，按相同的參數(shù)設(shè)置運(yùn)行分別運(yùn)行20和50次，并進(jìn)行統(tǒng)計(jì)分析，結(jié)果如表1所示?？梢钥闯?，本文中的算法在有限的迭代步數(shù)內(nèi)具有較強(qiáng)的穩(wěn)定性。

圖3 航跡規(guī)劃效果圖

表1 運(yùn)行結(jié)果統(tǒng)計(jì)表

結(jié)論

本文針對典型的無人機(jī)任務(wù)場景，考察了二維情形下無人機(jī)航跡規(guī)劃問題?；趯αＷ尤核惴ǖ纳钊胙芯亢头治觯岢隽司植克阉鞯倪M(jìn)化策略。相對于慣性權(quán)重動(dòng)態(tài)變化的粒子群算法，本文改進(jìn)的算法既保證了在整個(gè)進(jìn)化過程中都具有良好的全局搜索能力，也保證了對局部區(qū)域的充分搜索。仿真實(shí)驗(yàn)表明，基于局部搜索的粒子群算法在航跡規(guī)劃中有效。 ■