基于骨架提取的飛行器航跡實(shí)時(shí)重規(guī)劃法

陳懷民 方泰淙 段曉軍

摘 要： 隨著低空防御系統(tǒng)的不斷完善，飛行器成功突防的安全性越來(lái)越低。該文旨在解決動(dòng)態(tài)航跡規(guī)劃問(wèn)題。首先根據(jù)飛行器自身飛行約束條件和高程數(shù)字地圖信息，利用地形特征，將相對(duì)平坦的山谷地形提取出來(lái)，建立骨架，作為航跡規(guī)劃的參考。然后，根據(jù)航跡策略，飛行器在地面起飛前通過(guò)尋路算法快速制定一條可飛的航跡，在空中作戰(zhàn)遇到突發(fā)威脅時(shí)，也能夠快速重規(guī)劃出一條可飛航跡。仿真實(shí)驗(yàn)結(jié)果證明了該算法費(fèi)時(shí)短并且實(shí)時(shí)性高。

關(guān)鍵詞： 飛行器； 數(shù)字地圖； 骨架提取； 航跡規(guī)劃； 尋路算法； 可飛航跡

中圖分類號(hào)： TN967.6?34； V249 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2018）16?0127?05

Abstract： With the continuous improvement of the low?altitude defense system， the security of successful aircraft penetration is becoming lower and lower. Therefore， the dynamic track planning problem is addressed in this paper. According to the flight constraint condition of the aircraft and the information of the elevation digital map， the relatively flat valley terrain is extracted based on the terrain feature， so as to establish the skeleton as a reference for the flight track planning. According to the track strategy， a flyable track is rapidly determined before the aircraft takes off from the ground by using the pathfinding algorithm， and the flyable track can be quickly replanned when the aircraft encounters an unexpected threat during the air combat. The results of the simulation experiment show that the algorithm has short time?consumption and high real?time performance.

Keywords： aircraft； digital map； skeleton extraction； track planning； pathfinding algorithm； flyable track

0 引 言

隨著科技的不斷進(jìn)步，現(xiàn)代化戰(zhàn)爭(zhēng)的防御系統(tǒng)也日益完善，而飛行器成功從敵方勢(shì)力范圍突防的可能性卻不斷降低。飛行器作低空和超低空突防時(shí)，由于地形遮蔽和地面雜波的干擾使得飛行器不易被地面雷達(dá)發(fā)現(xiàn)，完成作戰(zhàn)任務(wù)的可能性更強(qiáng)。因此，低空和超低空突防在現(xiàn)代化戰(zhàn)爭(zhēng)中的優(yōu)勢(shì)很大，并逐漸成為現(xiàn)代戰(zhàn)爭(zhēng)中完成突防的主要作戰(zhàn)方式。地形跟隨、地形回避技術(shù)根據(jù)自身的地形地貌，利用導(dǎo)航系統(tǒng)來(lái)尋找最適合的飛行航跡路徑。地形跟隨、地形回避技術(shù)也極大地提高了飛行器的突防能力和生存能力，其中航跡規(guī)劃是核心技術(shù)。航跡規(guī)劃分為靜態(tài)航跡和動(dòng)態(tài)航跡。本文首先通過(guò)灌水操作將梯度變化較大的山脊進(jìn)行預(yù)處理操作，然后通過(guò)二值分法進(jìn)行骨架化處理，再通過(guò)中柱轉(zhuǎn)換提取骨架，最后通過(guò)模擬火種燃燒的算法找出可飛的航跡路徑。飛行器不僅可以在起飛前制定一條靜態(tài)航跡，也可以在空中遇到突發(fā)威脅時(shí)重新規(guī)劃出一條可飛路徑。

1 提取骨架圖

1.1 生成骨架圖算法

高程地圖的梯度信息能夠一定程度上反映地形上的差異，遇到山脊的地形，數(shù)字高程信息梯度變化較大，而山谷處較為平緩，數(shù)字高程信息梯度變化不大。可以先對(duì)地圖模擬給山谷灌水的預(yù)處理操作，通過(guò)灌水處理后，谷底平坦，梯度較小，能利用梯度識(shí)別出是適合飛行的區(qū)域。然后通過(guò)設(shè)置閾值來(lái)分割梯度圖，分割處理后，各點(diǎn)值為0或1，得到對(duì)應(yīng)的二值圖。再根據(jù)地形信息提取相對(duì)平臺(tái)的山谷骨架，提取骨架的方法有很多種，其中中軸變換是一種比較有效的方法，如圖1所示。

圖中有區(qū)域[R]、邊界[B]、骨架點(diǎn)[P]。對(duì)于每一個(gè)骨架點(diǎn)[P]，可在區(qū)域[R]中找到和它距離最近的骨架點(diǎn)。如果在[P]中能找到多于一個(gè)這樣的點(diǎn)，就認(rèn)為[P]是屬于[R]的骨架點(diǎn)。

用一個(gè)區(qū)域點(diǎn)與兩個(gè)邊界點(diǎn)的最小距離來(lái)定義骨架，即：

[DS（P，B）=inf{D（P，Z）Z?B}]

若S是區(qū)域R的骨架，則滿足：R完全包含S，S處在R里中心位置；S為單個(gè)像素寬；S與R具有相同數(shù)量的連通組元；R的補(bǔ)集與S的補(bǔ)集具有相同數(shù)量的連通組元；根據(jù)S重建R。

1.2 骨架的拼接和精簡(jiǎn)

骨架圖上的點(diǎn)可以分為如下三類：

1） A類點(diǎn)。8個(gè)鄰居中僅有一個(gè)鄰居是骨架點(diǎn)，稱這樣的點(diǎn)為端點(diǎn)，或葉子節(jié)點(diǎn)。

2） B類點(diǎn)。8個(gè)鄰居中有兩個(gè)鄰居是骨架點(diǎn)，這種點(diǎn)組成了骨架網(wǎng)絡(luò)的邊。

3） C類點(diǎn)。8個(gè)鄰居中有大于三個(gè)的鄰居是骨架點(diǎn)，這種點(diǎn)是骨架網(wǎng)絡(luò)的關(guān)節(jié)。

生成的骨架圖有的不是聯(lián)通的，通過(guò)將骨架柵格的最后一行和最后一列記錄下一個(gè)骨架柵格的信息，這樣就能保證骨架與骨架之間能夠拼接的上。在骨架圖上，將A類點(diǎn)通過(guò)B類點(diǎn)到C類點(diǎn)的這部分線條稱為懸掛邊，較短的懸掛邊稱為短毛。在地形復(fù)雜的地區(qū)，尤其是山區(qū)地形，對(duì)應(yīng)的骨架圖上會(huì)有大量的長(zhǎng)度很小的短毛。通過(guò)設(shè)定一個(gè)閾值來(lái)清理這些短毛，這樣就會(huì)使骨架圖精簡(jiǎn)。

1.3 威脅代價(jià)

飛行器在執(zhí)行任務(wù)時(shí)所面臨的威脅是雷達(dá)探測(cè)、低空火力、地形威脅和禁飛區(qū)。其中禁飛區(qū)的威脅是殺傷力最大。飛行器在執(zhí)行任務(wù)遇到禁飛區(qū)時(shí)，會(huì)做規(guī)避處理。在現(xiàn)代化戰(zhàn)爭(zhēng)中，由于戰(zhàn)場(chǎng)環(huán)境非常復(fù)雜，地面防御系統(tǒng)發(fā)現(xiàn)敵對(duì)目標(biāo)后，要花一些時(shí)間處理消息并通知低空火力才能夠有效阻截目標(biāo)。為了避免這些威脅，盡量選擇走山谷的盲雷達(dá)區(qū)來(lái)規(guī)避威脅。這些威脅區(qū)經(jīng)研究之后把它們近似作圓域處理，經(jīng)過(guò)圓域處理的威脅區(qū)，成為絕對(duì)威脅區(qū)，飛行器在里面飛行的殺傷力為100%。經(jīng)過(guò)威脅區(qū)作圓域處理，這樣，初始航跡的規(guī)劃空間已經(jīng)形成。

1.4 骨架遇威脅區(qū)的處理

飛行器執(zhí)行飛行任務(wù)時(shí)會(huì)面臨各種威脅，規(guī)劃的航跡路線不能進(jìn)入威脅區(qū)域。威脅區(qū)域不能飛行，這樣就會(huì)使原骨架發(fā)生斷裂，同時(shí)也破壞了保持區(qū)域連通性的骨架圖。為了解決這個(gè)問(wèn)題，采用如下方法：在拼接完成的骨架圖上，將威脅區(qū)域設(shè)置為背景點(diǎn)，然后檢查威脅區(qū)域的外邊界點(diǎn)，如果外邊界點(diǎn)是可飛區(qū)域點(diǎn)，將其設(shè)置為骨架點(diǎn)。威脅加載后，原來(lái)的骨架會(huì)被截?cái)啵菍⑼{的外邊界點(diǎn)加入到骨架中后，依然保持了骨架圖的連通性。

2 航跡規(guī)劃

2.1 航跡代價(jià)計(jì)算

航跡規(guī)劃的最終路徑是由一段一段的航跡初路徑的邊組成。在骨架處理完之后的地圖上，關(guān)鍵點(diǎn)和關(guān)鍵段都會(huì)非常清楚的標(biāo)出來(lái)。航跡段的總目標(biāo)是綜合考慮航跡段的威脅因素和燃料代價(jià)使航跡總代價(jià)最小，最后形成關(guān)鍵點(diǎn)之間通過(guò)代價(jià)系數(shù)連接而成的網(wǎng)絡(luò)圖，進(jìn)而轉(zhuǎn)化成網(wǎng)絡(luò)圖中尋路問(wèn)題。

現(xiàn)采用如下方程來(lái)描述：

[Fx，y=（1-z）·Mx，y+zNx，y]

式中：[x，y=0，1，2，…，m，][m]為關(guān)鍵點(diǎn)總數(shù)；[Mx，y]代表關(guān)鍵點(diǎn)[x]到[y]的威脅代價(jià)；[Nx，y]代表關(guān)鍵點(diǎn)[x]到[y]的燃料代價(jià)。

2.2 航跡規(guī)劃的尋路算法

根據(jù)數(shù)字地圖和骨架圖的信息，設(shè)計(jì)基于骨架提取的快速尋路算法。通過(guò)做骨架，將關(guān)鍵點(diǎn)和關(guān)鍵路徑提取出來(lái)，此算法模擬火種在骨架上的燃燒傳播。火種從起點(diǎn)開(kāi)始勻速向前推進(jìn)，遇到C類點(diǎn)后分為若干路繼續(xù)勻速向前，遇到A類端點(diǎn)或已燃燒的點(diǎn)就熄滅，直到火種燃燒到目標(biāo)點(diǎn)為止。如果起點(diǎn)和終點(diǎn)在骨架圖的同一個(gè)連通分支上，經(jīng)過(guò)一些時(shí)間，火種一定能從起點(diǎn)燃燒到終點(diǎn)，第一個(gè)到達(dá)終點(diǎn)的火種所走過(guò)的路就是最短路。但實(shí)際上，會(huì)存在起點(diǎn)和終點(diǎn)不在一個(gè)連通分支上的情況，如果允許火種從端點(diǎn)處向周圍以一定的范圍噴發(fā)，或者像帶電鐵絲一樣向外放電，使得火種能在距離端點(diǎn)較近的其他分支進(jìn)行傳播，然而跨過(guò)背景點(diǎn)且確保不跨越威脅區(qū)需要有一定的懲罰系數(shù)，這樣起點(diǎn)和終點(diǎn)不在一個(gè)連通分支上也能很好解決。

尋路整體算法流程圖如圖2所示。

一次尋路過(guò)程的流程如圖3所示。

為了更好的描述算法，先定義如下概念：

直線可達(dá)：若A，B兩點(diǎn)間的直線段都在可飛區(qū)域中，稱AB直線可達(dá)。

探路起點(diǎn)：即首次進(jìn)行探路操作的骨架點(diǎn)。如果任務(wù)起點(diǎn)剛好在骨架上，其本身作為探路起點(diǎn)；否則使用距離任務(wù)起點(diǎn)最近的骨架點(diǎn)作為探路起點(diǎn)。為了減少算法的尋路步驟，將任務(wù)起點(diǎn)和終點(diǎn)直線連線上的最后一個(gè)骨架點(diǎn)作為探路起點(diǎn)。

探路終點(diǎn)：距離任務(wù)終點(diǎn)較近的骨架點(diǎn)。當(dāng)某個(gè)探路點(diǎn)距離任務(wù)終點(diǎn)較近時(shí)，探路結(jié)束。將任務(wù)終點(diǎn)和任務(wù)起點(diǎn)連接在直線上，最后一個(gè)任務(wù)直線可達(dá)的骨架點(diǎn)作為探路終點(diǎn)。

探路先鋒：尋路算法執(zhí)行過(guò)程中，在骨架圖上能向前推進(jìn)的B類或C類點(diǎn)。算法中使用一個(gè)探路先鋒隊(duì)列保存當(dāng)前所有的探路先鋒。探路起點(diǎn)也是探路先鋒，并且探路起點(diǎn)在骨架圖上的所有鄰居都將成為下一代探路先鋒。

放電端點(diǎn)：已經(jīng)被探路先鋒抵達(dá)的A類點(diǎn)。算法中將當(dāng)前所有的放電端點(diǎn)保存到一個(gè)放電端點(diǎn)隊(duì)列中。放電端點(diǎn)進(jìn)行放電操作時(shí)，放電半徑R內(nèi)距離該點(diǎn)最近的、沒(méi)被探路先鋒經(jīng)過(guò)的點(diǎn)會(huì)被擊中，被擊中的點(diǎn)變?yōu)樾碌奶铰废蠕h。

能量：探路先鋒向前推進(jìn)的動(dòng)力，每向前推進(jìn)一個(gè)骨架點(diǎn)，消耗一個(gè)能量。

探路樹(shù)：尋路算法從探路起點(diǎn)開(kāi)始，所經(jīng)歷的關(guān)鍵點(diǎn)構(gòu)成一棵樹(shù)，這棵樹(shù)稱為探路樹(shù)。

完成一次航跡規(guī)劃任務(wù)的尋路算法描述如下：

1） 初始化探路先鋒隊(duì)列、放電端點(diǎn)隊(duì)列和探路樹(shù)，初始值為空，確定探路起點(diǎn)和探路終點(diǎn)；

2） 將探路起點(diǎn)作為樹(shù)根建立探路樹(shù)，同時(shí)將其放到探路先鋒隊(duì)列中；

3） 給探路先鋒隊(duì)列和放電端點(diǎn)隊(duì)列中所有點(diǎn)補(bǔ)充能量；

4） 按順序檢查放電端點(diǎn)隊(duì)列中的每個(gè)放電端點(diǎn)，如果放電端點(diǎn)的能量大于某一常量就進(jìn)行一次放電操作，同時(shí)將這個(gè)點(diǎn)從隊(duì)列中刪除；

5） 按順序檢查探路先鋒隊(duì)列中的每個(gè)探路先鋒，如果探路成功，轉(zhuǎn)步驟6）；否則，讓探路先鋒按照規(guī)則向前推進(jìn)，直到所有的探路先鋒把能量耗盡為止，然后轉(zhuǎn)步驟3）；

6） 此時(shí)已經(jīng)得到了從探路起點(diǎn)到探路終點(diǎn)的一條路，從探路樹(shù)中可得到這條路的關(guān)鍵點(diǎn)序列（[V1，V2，…，Vn]）。

2.3 航跡平滑處理

飛行器在執(zhí)行任務(wù)時(shí)不能瞬間改變飛行器飛行的方向和飛行速度，這樣飛行器在空中不能瞬間完成轉(zhuǎn)彎，這一因素也影響了飛行器在航路規(guī)劃中的實(shí)際性能。因此，為使現(xiàn)有航跡實(shí)時(shí)性高，需要對(duì)航跡做平滑處理。飛行器的最小轉(zhuǎn)彎半徑是影響航跡平滑的主要因素。飛行器的飛行速度和最大法向過(guò)載影響和決定了最小轉(zhuǎn)彎半徑的大小。

式中：[Vmin]是飛行器的最小飛行速度；[nmin]是飛行器的最大法向過(guò)載；[Rmin]代表飛行器的最小轉(zhuǎn)彎半徑。

如圖4所示。給定飛行器的位置、機(jī)頭方向、飛行方向、最小轉(zhuǎn)彎半徑以及下一個(gè)航跡點(diǎn)，其中速度方向和機(jī)頭方向一致。

M點(diǎn)是以[Rmin]為半徑的圓心，[γ]是飛行器沿圓周運(yùn)動(dòng)時(shí)較初始位置轉(zhuǎn)過(guò)的角度，它們之間的關(guān)系如下：

航跡經(jīng)過(guò)平滑處理，就可以告訴飛行器在什么時(shí)候開(kāi)始轉(zhuǎn)彎，這樣就能得到一條實(shí)時(shí)性高且可飛的航跡。

3 仿真測(cè)試

本文在LabWindows/CVI 8.5的開(kāi)發(fā)平臺(tái)下對(duì)模型和算法進(jìn)行仿真實(shí)驗(yàn)。本實(shí)驗(yàn)中設(shè)置兩個(gè)大的威脅區(qū)和一個(gè)小的威脅區(qū)，其中紅色的圓形區(qū)域?yàn)榻w區(qū)。對(duì)每塊經(jīng)緯度的地圖進(jìn)行骨架提取后保存，使用時(shí)根據(jù)任務(wù)區(qū)域再進(jìn)行骨架拼接，再通過(guò)模擬火種燃燒的算法得到航跡規(guī)劃關(guān)鍵點(diǎn)，之后通過(guò)航跡平滑處理，得到可飛的航跡。

本文分別對(duì)離線靜態(tài)航路和動(dòng)態(tài)實(shí)時(shí)航路進(jìn)行仿真實(shí)驗(yàn)驗(yàn)證。

3.1 靜態(tài)航跡規(guī)劃路徑

設(shè)定任務(wù)起點(diǎn)和任務(wù)終點(diǎn)的經(jīng)緯度分別為（108.80，34.20）和（107.02，33.70），設(shè)定禁飛區(qū)域?yàn)閳A形區(qū)域，威脅區(qū)域有威脅區(qū)域1經(jīng)緯度為（108.80，34.20），威脅半徑為10 000 m，威脅區(qū)域2經(jīng)緯度為（108.80，33.80），威脅半徑為40 000 m，威脅區(qū)域3經(jīng)緯度為（107.90，33.80），威脅半徑為30 000 m。通過(guò)加載高程數(shù)字地圖及威脅區(qū)之后通過(guò)拼接骨架，然后通過(guò)尋路算法規(guī)劃出的航跡路徑界面圖如圖5所示。

對(duì)于規(guī)劃出的航跡要在地形回避、地形威脅、地形匹配中進(jìn)行模擬航跡飛行軌跡驗(yàn)證。任務(wù)起點(diǎn)和任務(wù)終點(diǎn)之間的飛行距離為250 km，飛行速度為200 m/s，如圖6所示，飛行器的飛行軌跡驗(yàn)證了靜態(tài)航跡的可飛性。

3.2 動(dòng)態(tài)航跡規(guī)劃路徑

飛行器在空中作戰(zhàn)時(shí)，按照起飛前制定的航跡規(guī)劃路徑飛行，當(dāng)飛行器飛行到經(jīng)緯度為（108.13，34.12）的點(diǎn)時(shí)前方突然遇到了突發(fā)性的威脅，威脅區(qū)為圓形，圓心經(jīng)緯度為（108.00，34.12），威脅半徑為10 000 m，此時(shí)距離任務(wù)終點(diǎn)的距離為195 km，導(dǎo)航算法必須重新規(guī)劃出一條路徑。這時(shí)飛行器根據(jù)航跡策略，通過(guò)尋路算法快速實(shí)現(xiàn)一條可突圍的航跡路徑，如圖7所示。

對(duì)于重規(guī)劃出的新航跡路徑要在地形回避、地形威脅、地形匹配中進(jìn)行模擬航跡飛行軌跡驗(yàn)證。任務(wù)起點(diǎn)和終點(diǎn)之間的飛行距離為250 km，飛行速度為200 m/s，在中途突發(fā)遇到威脅時(shí)，按照重新規(guī)劃的航跡能夠飛行繞過(guò)突發(fā)威脅區(qū)。如圖8所示，飛行器的飛行軌跡驗(yàn)證了動(dòng)態(tài)航跡的可飛性。

3.3 各階段花費(fèi)時(shí)間

經(jīng)過(guò)多次測(cè)試，飛行器在遇到威脅需要重新規(guī)劃出一條可飛路徑時(shí)，在相距任務(wù)點(diǎn)間的距離有250 km時(shí)，設(shè)置多個(gè)威脅區(qū)域。骨架拼接、加載威脅區(qū)域及任務(wù)起點(diǎn)和任務(wù)終點(diǎn)之間尋路所花費(fèi)的時(shí)間如表1所示。

4 結(jié) 論

本文通過(guò)加載已知威脅區(qū)域提取骨架圖的方法，將關(guān)鍵點(diǎn)和關(guān)鍵路徑標(biāo)記出來(lái)，再通過(guò)骨架拼接和修剪，去除短毛，把威脅區(qū)域簡(jiǎn)化為威脅圓，得到了航跡規(guī)劃的搜索空間，這樣航跡規(guī)劃路徑就變成一個(gè)網(wǎng)絡(luò)圖。用模擬火種燃燒的廣度優(yōu)先方法快速搜索出一條從起始點(diǎn)到終點(diǎn)的航跡路徑。由于加載骨架圖之后，就把關(guān)鍵點(diǎn)和關(guān)鍵路徑標(biāo)記出來(lái)了，這樣在尋路的時(shí)候就節(jié)省了大量的時(shí)間。飛行器在空中遇到突發(fā)威脅時(shí)，也同樣能夠規(guī)劃出一條可飛航跡，這種算法不僅適合靜態(tài)航跡規(guī)劃，同樣也適應(yīng)于動(dòng)態(tài)航跡規(guī)劃。圖形仿真證明，整體思路可行，算法實(shí)時(shí)性高。

參考文獻(xiàn)

[1] OH H， SHIN H S， KIM S， et al. Cooperative mission and path planning for a team of UAVs [M]. Springer Netherlands， 2015： 1509?1545.

[2] DING Z， ZHANG J， LI C， et al. A real?time path planning method for emergent threats [C]// Proceedings of IEEE International Conference on Information and Automation. Lijiang： IEEE， 2015： 3014?3019.

[3] LIU Y， ZHANG W， LI G， et al. Path planning of UAV in dynamic environment [J]. Journal of Beijing University of Aeronautics &Astronautics;， 2014， 40（2）： 252?256.

[4] DENG T， XIONG Z M， LIU Y J， et al. Research on 3D route planning for UAV in low?altitude penetration based on improved ant colony algorithm [J]. Applied mechanics & materials， 2014， 442（4）： 556?561.

[5] XU Z J， TANG S. Flight path planning based on improved genetic algorithm [J]. Journal of astronautics， 2008（5）： 80?85.

[6] MENG H， XIN G. UAV route planning based on the genetic simulated annealing algorithm [C]// Proceedings of IEEE International Conference on Mechatronics and Automation. Xian： IEEE， 2010： 788?793.

[7] LAMONT G B. UAV swarm mission planning development using evolutionary algorithms and parallel simulation： Part II SCI?195 [J/OL]. [2008?01?24]. http：//www.ixueshu.com/download/5581d1dc3627cb78318947a18e7f9386.html.

[8] 王維平，劉娟.無(wú)人飛行器航跡規(guī)劃方法綜述[J].飛行力學(xué)，2010，28（2）：6?10.

WANG Weiping， LIU Juan. Introduction to unmanned air vehicle route planning methods [J]. Flight dynamics， 2010， 28（2）： 6?10.

[9] 李季，孫秀霞.基于改進(jìn)A?Star算法的無(wú)人機(jī)航跡規(guī)劃算法研究[J].兵工學(xué)報(bào)，2008，29（7）：788?792.

LI Ji， SUN Xiuxia. A route planning′s method for unmanned aerial vehicles based on improved A?Star algorithm [J]. Acta Armamentarii， 2008， 29（7）： 788?792.

[10] 張俊峰，周成平.基于改進(jìn)稀疏A*算法的三維航跡規(guī)劃方法[J/OL].[2013?02?01].http：//www.doc88.com/p?789355360238.html.

ZHANG Junfeng， ZHOU Chengping. A 3D route planning based on improved sparse A* algorithm [J/OL]. [2013?02?01]. http：//www.doc88.com/p?789355360238.html.