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

陳懷民 方泰淙 段曉軍

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

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

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

1 提取骨架圖

1.1 生成骨架圖算法

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

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

用一個區(qū)域點與兩個邊界點的最小距離來定義骨架，即：

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

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

1.2 骨架的拼接和精簡

骨架圖上的點可以分為如下三類：

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

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

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

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

1.3 威脅代價

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

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

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

2 航跡規(guī)劃

2.1 航跡代價計算

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

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

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

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

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

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

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

一次尋路過程的流程如圖3所示。

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

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

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

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

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

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

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

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

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

1） 初始化探路先鋒隊列、放電端點隊列和探路樹，初始值為空，確定探路起點和探路終點；

2） 將探路起點作為樹根建立探路樹，同時將其放到探路先鋒隊列中；

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

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

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

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

2.3 航跡平滑處理

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

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

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

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

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

3 仿真測試

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

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

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

設(shè)定任務(wù)起點和任務(wù)終點的經(jīng)緯度分別為（108.80，34.20）和（107.02，33.70），設(shè)定禁飛區(qū)域為圓形區(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。通過加載高程數(shù)字地圖及威脅區(qū)之后通過拼接骨架，然后通過尋路算法規(guī)劃出的航跡路徑界面圖如圖5所示。

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

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

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

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

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

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

4 結(jié) 論

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

參考文獻(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] 王維平，劉娟.無人飛行器航跡規(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算法的無人機(jī)航跡規(guī)劃算法研究[J].兵工學(xué)報，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.