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

陳懷民 方泰淙 段曉軍

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

關鍵詞： 飛行器； 數字地圖； 骨架提取； 航跡規劃； 尋路算法； 可飛航跡

中圖分類號： TN967.6?34； V249 文獻標識碼： 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 引 言

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

1 提取骨架圖

1.1 生成骨架圖算法

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

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

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

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

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

1.2 骨架的拼接和精簡

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

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

2） B類點。8個鄰居中有兩個鄰居是骨架點，這種點組成了骨架網絡的邊。

3） C類點。8個鄰居中有大于三個的鄰居是骨架點，這種點是骨架網絡的關節。

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

1.3 威脅代價

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

1.4 骨架遇威脅區的處理

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

2 航跡規劃

2.1 航跡代價計算

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

現采用如下方程來描述：

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

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

2.2 航跡規劃的尋路算法

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

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

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

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

直線可達：若A，B兩點間的直線段都在可飛區域中，稱AB直線可達。

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

探路終點：距離任務終點較近的骨架點。當某個探路點距離任務終點較近時，探路結束。將任務終點和任務起點連接在直線上，最后一個任務直線可達的骨架點作為探路終點。

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

放電端點：已經被探路先鋒抵達的A類點。算法中將當前所有的放電端點保存到一個放電端點隊列中。放電端點進行放電操作時，放電半徑R內距離該點最近的、沒被探路先鋒經過的點會被擊中，被擊中的點變為新的探路先鋒。

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

探路樹：尋路算法從探路起點開始，所經歷的關鍵點構成一棵樹，這棵樹稱為探路樹。

完成一次航跡規劃任務的尋路算法描述如下：

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

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

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

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

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

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

2.3 航跡平滑處理

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

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

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

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

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

3 仿真測試

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

本文分別對離線靜態航路和動態實時航路進行仿真實驗驗證。

3.1 靜態航跡規劃路徑

設定任務起點和任務終點的經緯度分別為（108.80，34.20）和（107.02，33.70），設定禁飛區域為圓形區域，威脅區域有威脅區域1經緯度為（108.80，34.20），威脅半徑為10 000 m，威脅區域2經緯度為（108.80，33.80），威脅半徑為40 000 m，威脅區域3經緯度為（107.90，33.80），威脅半徑為30 000 m。通過加載高程數字地圖及威脅區之后通過拼接骨架，然后通過尋路算法規劃出的航跡路徑界面圖如圖5所示。

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

3.2 動態航跡規劃路徑

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

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

3.3 各階段花費時間

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

4 結 論

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

參考文獻

[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] 王維平，劉娟.無人飛行器航跡規劃方法綜述[J].飛行力學，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] 李季，孫秀霞.基于改進A?Star算法的無人機航跡規劃算法研究[J].兵工學報，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] 張俊峰，周成平.基于改進稀疏A*算法的三維航跡規劃方法[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.