楊曉龍，曲東才

(海軍航空工程學(xué)院 a.研究生管理大隊(duì);b.控制工程系，山東 煙臺(tái) 264001)

飛機(jī)地形跟蹤飛行過程中由于飛行航路方向固定、飛越山頂時(shí)暴露時(shí)間過長(zhǎng)，易被敵方發(fā)現(xiàn)和跟蹤。地形回避(terrain avoidance，TA)是在保持飛機(jī)飛行高度不變的基礎(chǔ)上，通過飛機(jī)橫向機(jī)動(dòng)來繞過地形障礙的一種超低空飛行技術(shù)［1］，它可以在保證飛行安全的前提下，進(jìn)一步改善飛機(jī)的飛行隱蔽性，提高飛機(jī)執(zhí)行低空突防任務(wù)的成功率。

本文主要對(duì)飛機(jī)地形回避的航跡規(guī)劃進(jìn)行研究，首先對(duì)地形障礙進(jìn)行分類和建模，然后依據(jù)飛機(jī)地形回避的實(shí)際約束條件，利用改進(jìn)狄克斯特拉算法進(jìn)行初始航路規(guī)劃，在保證飛行安全的基礎(chǔ)上，運(yùn)用遺傳模擬退火算法對(duì)航路進(jìn)行優(yōu)化，尋找到整體航程最短的航路。

1 障礙空間建模

航跡規(guī)劃是指在特定約束條件下，尋找運(yùn)動(dòng)體從初始點(diǎn)到目標(biāo)點(diǎn)滿足某種性能指標(biāo)最優(yōu)的運(yùn)動(dòng)軌跡，它是飛機(jī)進(jìn)行地形回避飛行過程中的一個(gè)關(guān)鍵環(huán)節(jié)，是飛機(jī)成功實(shí)現(xiàn)低空突防的基礎(chǔ)［4］。

地形障礙是飛機(jī)低空飛行的主要威脅來源，也是航跡規(guī)劃中需要避開的主要障礙物。所以在飛機(jī)進(jìn)行地形回避飛行過程中要首先對(duì)地形障礙進(jìn)行建模分析，盡可能地保持模型的真實(shí)性和可靠性。

1.1 地形障礙建模

實(shí)際地形多種多樣，要用一個(gè)統(tǒng)一的模型來表示各種地形往往比較困難。考慮海拔高度是地形的最直接的表述參數(shù)之一，而對(duì)于地形回避而言，由于飛行高度一定，海拔高度大于其飛行高度的地形均是威脅部分。

對(duì)地形進(jìn)行采樣后，選取出飛行障礙點(diǎn)集，并對(duì)其中各個(gè)采樣點(diǎn)所屬障礙的類別進(jìn)行判定。因?yàn)橥粋€(gè)障礙的采樣點(diǎn)間距緊湊，所以采用k均值聚類分析算法，對(duì)采樣點(diǎn)集進(jìn)行分類。k均值聚類算法是一種動(dòng)態(tài)聚類法，該算法的基本思想為:隨機(jī)選取k個(gè)初始聚類中心，按最小距離的原則將各個(gè)采樣點(diǎn)分配到k類中的某一類，然后不斷地循環(huán)計(jì)算類心、調(diào)整各采樣點(diǎn)的類別，最終使得各采樣點(diǎn)到其類心距離的平方和最小［5］。

通過k均值算法分類后，對(duì)同一類地形采樣點(diǎn)進(jìn)行統(tǒng)一考慮，建立地形模型。因?yàn)榈匦握系K邊界的不確定性，為了同時(shí)滿足對(duì)模型的精確性和統(tǒng)一表述的要求，只能采取折中的辦法建立近似的模型，其方法為:用一個(gè)圓形模型來近似代替一個(gè)地形障礙，其中，每個(gè)類別的類心為圓心，取該類中所有樣本點(diǎn)與類心距離的最大值為半徑。這樣圓心參數(shù)顯示障礙的位置，而圓半徑則反映出障礙的大小。圖1所示的是在k均值聚類方法的基礎(chǔ)上2個(gè)地形障礙的建模過程。

圖1 地形障礙建模過程示意圖

圖1中，通過k均值聚類算法，將采樣點(diǎn)分成2類，分別用圓形點(diǎn)和方形點(diǎn)表示，以類心(cx1，cy1)、(cx2，cy2)為圓心，采樣點(diǎn)到類心距離的最大值r1、r2為半徑，建立了地形障礙的近似模型。

1.2 建立可行節(jié)點(diǎn)空間

可行節(jié)點(diǎn)是指飛機(jī)可以安全飛行的節(jié)點(diǎn)，顯然，在威脅空間里擁有無窮多個(gè)可行節(jié)點(diǎn)，為了降低算法的復(fù)雜度，縮短算法運(yùn)行時(shí)間，需要減少可行節(jié)點(diǎn)的數(shù)量。本文進(jìn)行初始航跡規(guī)劃時(shí)選取障礙圓心之間的連線的中點(diǎn)和障礙圓心到地圖邊界連線的中點(diǎn)為可行節(jié)點(diǎn)。這樣選取可行節(jié)點(diǎn)可以將飛機(jī)飛行過程中相對(duì)于臨近的障礙威脅的危險(xiǎn)系數(shù)降到最小。

檢驗(yàn)每個(gè)可行節(jié)點(diǎn)的合法性，計(jì)算可行節(jié)點(diǎn)到每個(gè)障礙圓心的距離與其半徑的差值Dij，判斷該可行節(jié)點(diǎn)是否處于障礙模型內(nèi)部，即

式中:i=1，2，…，n;j=1，2，…，k;Dij表示第 i個(gè)可行節(jié)點(diǎn)到第j個(gè)障礙圓心的距離與其半徑的差值。

向量 Di=［Di1，Di2，…，Dij，…］，如果 Di中存在小于或等于0的元素，則可行節(jié)點(diǎn)i是不合法的，反之則為合法的可行節(jié)點(diǎn)。

建立可行節(jié)點(diǎn)空間后，2個(gè)可行節(jié)點(diǎn)之間的連線就構(gòu)成了一段飛行航跡，給每段航跡賦權(quán)值，由可行節(jié)點(diǎn)為頂點(diǎn)，節(jié)點(diǎn)之間相互連接構(gòu)成一個(gè)賦權(quán)圖。Costij表示從可行節(jié)點(diǎn)i到可行節(jié)點(diǎn)j之間連線的代價(jià)函數(shù)。

并不是任何2個(gè)可行節(jié)點(diǎn)之間都有連線，這是因?yàn)?個(gè)可行節(jié)點(diǎn)的連線可能穿過某一障礙，此時(shí)該連線的代價(jià)函數(shù)的值為無窮大，如果飛機(jī)沿此航路飛行就會(huì)發(fā)生撞地的危險(xiǎn)。

因此取代價(jià)函數(shù)的表達(dá)式

其中，sij表示可行節(jié)點(diǎn)i與j之間航路的長(zhǎng)度;表示可行節(jié)點(diǎn)i與j之間航路到第k個(gè)障礙圓心的距離的，eij=min(-rk)，如果eij＞0則說明該航路合法，反之則不合法。由代價(jià)函數(shù)的表達(dá)式可以看出，代價(jià)函數(shù)與航路長(zhǎng)度近似成正比，與航路的威脅系數(shù)近似成反比。

2 初始航跡規(guī)劃

當(dāng)障礙空間建模完成之后，就可以利用尋優(yōu)算法搜索累計(jì)代價(jià)函數(shù)值最小的最優(yōu)航跡。狄克斯特拉算法是一種典型的單源最短路徑尋優(yōu)算法，算法的基本思想是將賦權(quán)圖中的頂點(diǎn)分為2組，第1組S存放已經(jīng)確定最短路徑的節(jié)點(diǎn)，第2組V存放未確定的節(jié)點(diǎn)。算法循環(huán)過程中按最短路徑長(zhǎng)度遞增的順序?qū)中的節(jié)點(diǎn)逐個(gè)移至S中，當(dāng)終點(diǎn)被從V中移至 S 中時(shí)，算法循環(huán)結(jié)束［4，6］。

針對(duì)地形回避問題的特殊情況，對(duì)狄克斯特拉算法進(jìn)行改進(jìn)，加入航路最短距離smin和最大轉(zhuǎn)彎角φ兩個(gè)約束條件，保證規(guī)劃出的航路能夠滿足飛機(jī)飛行條件。

改進(jìn)狄克斯特拉算法流程:

1)初始化節(jié)點(diǎn)集S、V，將初始點(diǎn)p0放到S組，其余可行節(jié)點(diǎn)和終點(diǎn)pend放到V組，利用賦權(quán)圖建立可行節(jié)點(diǎn)之間的鄰接矩陣，初始化可行節(jié)點(diǎn)到初始點(diǎn)的最短路徑d(v0i)(k=0)，(i=1，2，…，n)，k表示循環(huán)次數(shù)，如果初始點(diǎn)到可行節(jié)點(diǎn)有連接線段，則對(duì)應(yīng)值為線段的權(quán)值，反之取極大值。

2)選擇d(v0i)(k)中最小值d(v0j)(k)將節(jié)點(diǎn)j從點(diǎn)集V中移到點(diǎn)集S中。

3)根據(jù)節(jié)點(diǎn)j的鄰接矩陣更新數(shù)據(jù)d(v0i)(k+1)。設(shè)ηj為以節(jié)點(diǎn)j為末端點(diǎn)的航路線段向量，ηji表示以j為起點(diǎn)，未確定節(jié)點(diǎn)i為結(jié)點(diǎn)的航路向量，則對(duì)于航路j→i的2個(gè)約束條件可表示為

滿足式(3)則航路滿足最小距離約束，滿足式(4)，則航路滿足最大轉(zhuǎn)彎角約束，此時(shí)新的最短路徑依照式(5)更新，否則不更新。

式(5)中，d(vji)是點(diǎn)集V中剩余節(jié)點(diǎn)到節(jié)點(diǎn)j的路徑，如果剩余節(jié)點(diǎn)與j有連接線段，則對(duì)應(yīng)值為線段的權(quán)值，反之取極大值。

4)重復(fù)第二和第三步，直到終點(diǎn)pend移到點(diǎn)集S中，此時(shí)d(v0n)(k)為初始點(diǎn)到終點(diǎn)的最短路徑。

3 基于遺傳模擬退火算法的航跡優(yōu)化

初始航跡規(guī)劃中的可行節(jié)點(diǎn)為連接線的中點(diǎn)，因此不是整個(gè)規(guī)劃空間的最優(yōu)航跡，利用遺傳算法對(duì)規(guī)劃初始航跡進(jìn)行調(diào)整，讓各航跡節(jié)點(diǎn)在相應(yīng)的障礙端點(diǎn)連接線上滑動(dòng)，得到新的航跡節(jié)點(diǎn)，根據(jù)新的航跡點(diǎn)進(jìn)行規(guī)劃，得到最優(yōu)航跡。

遺傳算法由于不受搜索空間限制性假設(shè)約束，不要求優(yōu)化函數(shù)具備隱含并行性、連續(xù)、可導(dǎo)等假設(shè)，對(duì)于航跡規(guī)劃這種含有大量模糊信息、多約束的優(yōu)化問題來說，具有特別重要的意義。模擬退火算法模擬固體退火的溫度參數(shù)T，在判斷是否接受新解時(shí)依據(jù)Metropolis接受準(zhǔn)則，既接受好的新解，同時(shí)按一定的概率對(duì)惡化解也接受，通過這樣的判斷，有效地避免了很多優(yōu)化算法容易陷入局部極值和過早收斂的問題。

正是利用了模擬退火算法的優(yōu)點(diǎn)，與遺傳算法相結(jié)合，設(shè)計(jì)一種遺傳模擬退火算法，在遺傳算法的交叉和變異操作中引入Metropolis接受準(zhǔn)則，避免了遺傳算法陷入局部極值的問題。

3.1 基因編碼方式

遺傳算法首先需要確定基因編碼方式，用以表達(dá)需要解決的問題。基因的編碼方法除了決定個(gè)體基因染色體排列形式外，還決定了個(gè)體從搜索空間基因型變換到解空間表現(xiàn)型時(shí)的解碼方法。

航跡規(guī)劃中基因編碼通常經(jīng)緯度坐標(biāo)系法，而單純的經(jīng)緯度坐標(biāo)系法不能全面反映飛行器當(dāng)前狀態(tài)。因此，本文設(shè)計(jì)了一種動(dòng)態(tài)鏈表染色體編碼方案，它能減少航跡規(guī)劃時(shí)重復(fù)計(jì)算量，提高了內(nèi)存空間的利用效率，簡(jiǎn)化了插入和刪除節(jié)點(diǎn)操作，其鏈表格式如圖2所示。

圖2 神經(jīng)網(wǎng)絡(luò)染色體結(jié)構(gòu)

圖2中Nn為航跡節(jié)點(diǎn)，Nni表示航跡節(jié)點(diǎn)的基因，其值如表1所示。這種基因編碼方式雖然增加了計(jì)算機(jī)物理內(nèi)存，但是減少了重復(fù)計(jì)算量，同時(shí)，便于實(shí)時(shí)提取飛行器航跡相關(guān)信息，在不用解碼的情況下，就可以直接計(jì)算參考航跡的代價(jià)函數(shù)值，更接近問題的原始形式，表達(dá)式更有效，更能夠生成好的解。

表1 基因編碼在航跡中的物理意義

3.2 適應(yīng)度函數(shù)

在遺傳算法航跡規(guī)劃中，適應(yīng)度是評(píng)價(jià)航跡優(yōu)劣的唯一標(biāo)準(zhǔn)。個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)，直接影響遺傳算法的計(jì)算效率和計(jì)算時(shí)間。它通過威脅源、航跡距離、安全高度和約束違背量等評(píng)價(jià)因素指標(biāo)，評(píng)定滿足初始點(diǎn)到目標(biāo)點(diǎn)的可行航跡。從本質(zhì)上講，航跡規(guī)劃的目標(biāo)就是使航跡的適應(yīng)度更優(yōu)。

對(duì)于地形回避系統(tǒng)，可行航跡的飛行高度一致，對(duì)威脅都已進(jìn)行有效回避，只需考慮航跡總航程即可，因此可以取適應(yīng)度函數(shù)f(n)為航跡總航程。

3.3 遺傳操作算子

遺傳操作算子是遺傳算法具備強(qiáng)大搜索能力的核心，是調(diào)整和控制進(jìn)化過程的基本工具。在航跡規(guī)劃中，由于算法特殊的基因編碼方式，遺傳操作算子需要進(jìn)行改進(jìn)以滿足其實(shí)現(xiàn)航跡規(guī)劃任務(wù)。為此對(duì)遺傳算子進(jìn)行的特殊處理，將其應(yīng)用于航跡節(jié)點(diǎn)，從而生成更好的航跡路徑。

1)選擇算子。選擇運(yùn)算使用比例選擇算子，是利用比例于各個(gè)個(gè)體適應(yīng)度的概率來確定子孫被選擇的可能性，設(shè)種群數(shù)量為M，個(gè)體i的適應(yīng)度為fi，則個(gè)體i被選中的概率為

個(gè)體的概率給定以后，隨機(jī)產(chǎn)生［0，1］之間的隨機(jī)數(shù)，如果個(gè)體的選擇概率大于此數(shù)則被選中，小于此數(shù)則被淘汰，從而那些高適配值個(gè)體被選中的概率就大，低適配值個(gè)體就容易被淘汰。

2)交叉算子。將2條航跡重新組合，生成新的航跡。交叉運(yùn)算采用單點(diǎn)交叉算子，只有一個(gè)交叉點(diǎn)。生成2個(gè)新的子代個(gè)體可以可行，也可以不可行，且航跡節(jié)點(diǎn)數(shù)可以不相同。交叉概率pc一般選為0.25～1。

3)擾動(dòng)算子。對(duì)航跡節(jié)點(diǎn)中的一個(gè)節(jié)點(diǎn)坐標(biāo)隨機(jī)進(jìn)行改變，使其沿著相應(yīng)障礙的端點(diǎn)連線進(jìn)行滑動(dòng)，得到新的航跡。

3.4 算法描述

遺傳模擬退火算法航跡規(guī)劃的基本步驟如下:

1)設(shè)定種群的規(guī)模M，最大遺傳操作代數(shù)為N，初始溫度T=T0，溫度更新次數(shù)l=0，設(shè)定溫度變化按照 Tl+i=0.9Tl，設(shè)定終止溫度 Te;

2)生成初始種群Pl(k)，k=0;

3)計(jì)算種群Pl(k)中的每個(gè)染色體的適應(yīng)度函數(shù)，按照適應(yīng)度的大小根據(jù)比例算子選出M個(gè)染色體組成新種群Pls(k+1);

4)將新種群Pls(k+1)中染色體按照傳統(tǒng)方法進(jìn)行交叉操作得新種群Plcl(k+1)，設(shè)種群Pls(k+1)中個(gè)體i和個(gè)體j進(jìn)行了交叉得到種群Plcl(k+1)中個(gè)體i'和個(gè)體j'，交叉前2個(gè)個(gè)體i和j的適應(yīng)值分別為f(i)和f(j)，交叉操作后2個(gè)個(gè)體i'和個(gè)體 j'的適應(yīng)值分別為 f(i')和 f(j')，按照下式Metropolis接受準(zhǔn)則經(jīng)過若干次的迭代得到新種群Plc(k+1)

5)變異操作與交叉操作類似，將Plc(k+1)變異得到Plm1(k+1)，然后對(duì)變異后的各個(gè)個(gè)體依據(jù)式(9)得到新的種群Plm(k+1)

式(9)中i和i'分別表示變異前和變異后的個(gè)體，適應(yīng)值為f(i)和 f(i')。

6)將Plm(k+1)賦給Pl(k)，同時(shí)k=k+1。判斷k是否小于N，如果是則轉(zhuǎn)至第7步，否則轉(zhuǎn)至第4步。

7)更新溫度 Tl+i=0.9Tl，l=l+1，并且更新種群Pl+1(k)=Pl(k)。如果滿足停止準(zhǔn)則，則停止計(jì)算輸出最優(yōu)解;否則轉(zhuǎn)至第4步。

4 實(shí)例仿真

對(duì)本文提出的航跡優(yōu)化方案進(jìn)行驗(yàn)證，構(gòu)建一個(gè)3000 m2區(qū)域的數(shù)字地圖［7］，在高度為300 m的基準(zhǔn)平面內(nèi)進(jìn)行地形回避航路規(guī)劃。

首先構(gòu)建基準(zhǔn)平面圖，如圖3所示。在此基礎(chǔ)上，對(duì)平面圖中的4個(gè)地形障礙運(yùn)用k均值算法聚類建模，建立障礙空間模型。如圖4所示。

設(shè)置飛行起點(diǎn)為p0=(200，2800)、飛行終點(diǎn)為pend=(2800，200)，進(jìn)行初始航跡規(guī)劃，得到初始航路圖。在初始航跡的基礎(chǔ)上，運(yùn)用遺傳模擬退火算法對(duì)航跡進(jìn)行優(yōu)化，設(shè)種群大小為50，以航跡的總航程為適應(yīng)度值對(duì)航路進(jìn)行優(yōu)化，循環(huán)迭代100次后，得到航跡曲線如圖5中，圖5中實(shí)線所示初始航跡，虛線表示優(yōu)化航跡，圖6將規(guī)劃的航跡還原到數(shù)字地圖中，遺傳模擬退火算法的適應(yīng)度值變化曲線如圖7所示。

圖3 基準(zhǔn)平面

圖4 k均值算法聚類建模

圖5 優(yōu)化航跡曲線

圖6 優(yōu)化航跡3D示意圖

圖7 適應(yīng)度值變化曲線

5 結(jié)束語

本文對(duì)飛機(jī)地形回避飛行進(jìn)行航路規(guī)劃研究，通過k均值算法實(shí)現(xiàn)了對(duì)地形障礙采用點(diǎn)的聚類，并在此基礎(chǔ)上完成了對(duì)地形障礙空間的統(tǒng)一建模，通過狄克斯特拉算法完成了對(duì)飛行航跡的初始規(guī)劃，然后在此基礎(chǔ)上運(yùn)用將模擬退火算法用于遺傳算法實(shí)現(xiàn)了對(duì)航跡的優(yōu)化，仿真結(jié)果顯示經(jīng)過優(yōu)化后的航跡在保證航路安全的基礎(chǔ)上，縮短了整個(gè)航路的航程，達(dá)到了優(yōu)化的目的，證明了本文提出的方案的可行性和合理性。

［1］閔昌萬，袁建平.軍用飛行器航跡規(guī)劃綜述［J］.飛行力學(xué)，1998，19(2)：13-18.

［2］沈春林，徐克虎，賀也平.低空突防中的若干關(guān)鍵技術(shù)［J］.南京航空航天大學(xué)學(xué)報(bào)，2003(3)：134-139.

［3］范洪達(dá)，馬向玲，葉文.飛機(jī)低空突防航路規(guī)劃技術(shù)［M］.北京：國(guó)防工業(yè)出版社，2007：7-8，105-107.

［4］黃明.武裝直升機(jī)航跡規(guī)劃與軌跡控制研究［D］.南京：南京航空航天大學(xué)，2004：12-16.

［5］孫即祥.現(xiàn)代模式識(shí)別［M］.長(zhǎng)沙：國(guó)防科技大學(xué)出版社，2002：30-32.

［6］項(xiàng)林斌，秦碩，黃學(xué)宇，等.一種無源自動(dòng)地形跟隨系統(tǒng)的設(shè)計(jì)［J］.彈箭與制導(dǎo)學(xué)報(bào)，2005，25(2)：635-639.

［7］StephanWei，Markus Achtelik，Laurent Kneip.Intuitive 3D Maps for MAV Terrain Explorationand Obstacle Avoidance［J］.J Intell Robot Syst，2011(61)：473 – 493.

［8］王美仙，李明，張子軍.飛行器控制律設(shè)計(jì)方法發(fā)展綜述［J］.飛行力學(xué)，2007，25(2)：1-5.

［9］Sterens B L，Lewis F L.Aircraft Control and Simulation［M］.New York：John Wiley and Sons INC.，1992：175-240.

［10］辛貴州.無人飛行器航跡規(guī)劃算法研究［D］.哈爾濱：哈爾濱工程大學(xué)，2010：48-50.