基于突防網格模型的動態(tài)航跡規(guī)劃*

孫利軍

(光電信息控制和安全技術重點實驗室，河北三河 065201)

0 引言

隨著現(xiàn)代科技的快速發(fā)展，低空飛行受到越來越多的重視。為了提高低空飛行的生存概率和作戰(zhàn)效果，需要制定一個綜合的規(guī)劃系統(tǒng)進行任務規(guī)劃、資源協(xié)調和確定飛行航路［1］。其中航跡規(guī)劃為重要組成部分，它的目的就是在最短的時間內，面對復雜的地形、地貌、障礙、威脅等因素進行快速、有效地規(guī)劃，實現(xiàn)安全航行，到達目標［2-3］。對于航跡規(guī)劃的具體方法本文查閱了許多資料，分析比較了動態(tài)規(guī)劃法、梯度法、神經網絡、專家系統(tǒng)和遺傳算法等［4-5］，由于動態(tài)規(guī)劃算法最適合解決動態(tài)全局最優(yōu)問題，在具體的程序實現(xiàn)中并沒有發(fā)現(xiàn)“維數(shù)爆炸”的問題［6］，所以最終方案是將動態(tài)規(guī)劃算法用于節(jié)點間的分段航跡規(guī)劃，繼而進行航跡合并、航跡選擇與評估，并給出了最優(yōu)的規(guī)劃結果，經仿真驗證了該方法能夠快速、有效地完成低空航跡規(guī)劃任務。

1 動態(tài)航跡規(guī)劃方法

1.1 突防網格模型

以數(shù)字地形高程模型為基礎，將該數(shù)字地圖劃分為具有離散梯度值的網格單元［1］，形成分區(qū)網格，每個網格的成本值即為該網格內的平均地形梯度值。

在分區(qū)網格的基礎上，一方面考慮地形的山峰障礙威脅，將山峰的高程值大于一定值的區(qū)域設為禁飛區(qū)，即該處的網格概率值設為1。另一方面考慮攻擊威脅，根據(jù)攻擊區(qū)中心坐標和區(qū)域半徑所對應的網格區(qū)域中，將殺傷力指標合并到對應的網格概率值中［7］。經過這兩方面的處理，將山峰障礙威脅、攻擊威脅一并數(shù)字化在分區(qū)網格上，這樣就形成了突防網格模型，每個網格的成本值即為該處的飛行突防概率值。這樣建立的突防網格模型是綜合了地形、攻擊威脅、山峰障礙等因素為一體的飛行模型，以此為基礎規(guī)劃的飛行航跡能夠繞過山峰障礙和威脅區(qū)以最低的墜毀概率安全飛行。因此突防網格模型是航跡規(guī)劃系統(tǒng)的環(huán)境數(shù)據(jù)基礎。

1.2 基本航跡區(qū)、導航點的選擇以及匹配導航

基本航跡區(qū)通常是包括目標點在內的一片導航基準地圖，常用的有地形匹配區(qū)［8］和景象匹配區(qū)［8］。導航點是導航基準地圖上的一些小區(qū)域，導航點相應地有地形匹配點和景象匹配點。地形匹配點的選擇依據(jù)地形的高度和梯度，在導航區(qū)基準圖上，計算選擇高度在一定高度以下，綿延起伏的丘陵地區(qū)中的特征點作為地形匹配點。景象匹配點常常選定那些特征明顯，獨立像元數(shù)較大的區(qū)域作為景象匹配點。

在低空飛行中地形匹配區(qū)通常采用地形斷線掃描匹配，通過高度及梯度計算找到導航基準圖中的地形匹配點，以進行地形導航的實時修正。飛行器在景象匹配區(qū)采用圖像方差匹配方法，在拍攝到的實時景象圖片后，通過與庫存的基準圖的統(tǒng)計方差計算找到相應的景象匹配點，以完成景象匹配導航的實時修正。

1.3 動態(tài)規(guī)劃算法原理

在航跡規(guī)劃中，用節(jié)點的概念來涵蓋包括起始點、各個地形匹配點、各個景象匹配點、目標點在內的航跡必須經過的所有約束點。在2個相鄰節(jié)點之間進行的航跡規(guī)劃方法是整個航跡規(guī)劃的基礎，本文選用動態(tài)規(guī)劃算法［9-10］用于節(jié)點間的航跡規(guī)劃。

在由窮舉法求A0至Am之間最短路徑的問題上，對于任一節(jié)點 Pk(i，j)，i與 j之間有多條路徑，如圖1所示。

圖1 A0至Am之間最短路徑問題Fig.1 Shortest path problem of A0and Am

可以得出最短路徑問題的這樣一個特性:如果A0至Am之間最短路徑的第k站通過Pk，則這一最短路徑在由Pk出發(fā)到達終點Am的那一部分路徑，對于始點為Pk到達終點的所有可能的路徑來說，必定也是距離最短的。根據(jù)這一特性，可以把一個最短路徑問題轉化為多段判決問題來解決。

設 d(i，j，k)為從 i與 j的最短路徑，k 為最短路徑經過的第k站，得到遞歸公式如下:

算法如下:

以上為動態(tài)規(guī)劃的算法原理，在運用該方法解決具體問題的時候，將最短距離替換以具體的目標要素，即可解決具體的各種實際問題，本文用該算法解決航跡規(guī)劃問題的原理如下所述。

1.4 基于動態(tài)規(guī)劃的航跡規(guī)劃方法

圖2中的表格為某一區(qū)域建立的突防網格模型圖中的一部分，表格中數(shù)值為各點的突防概率初始值，由終止節(jié)點到起始節(jié)點逆向搜索［11］，根據(jù)動態(tài)規(guī)劃算法計算圖上各點所走航路的突防概率過程值見圖3。根據(jù)圖3的計算結果，確定出航跡路線，如圖3中箭頭線所示。在航跡規(guī)劃之后，即可得出2節(jié)點間的總的飛越成本，也就是這2個節(jié)點之間所經航路的突防概率過程值的總和，將其保存以備作進一步的處理。

圖2 突防概率初始值Fig.2 Initial probability of penetration

圖3 突防概率過程值及航跡規(guī)劃結果Fig.3 Process probability of penetration＆the result of trajectory planning

1.5 航跡合并

這一過程是將相應的分段航跡連接成一條近似完整的航跡線。每一個起始點可以到達許多導航點，最終到達目標點，這樣產生的航跡表現(xiàn)為樹形，稱為航跡樹。這棵航跡樹包括了起始點和它所能到達的每個匹配點經規(guī)劃后的航跡路線，將這棵航跡樹每條航跡線的飛越成本計算得出并存儲以備使用。

為了作簡潔說明和減少航線的數(shù)目，暫不考慮起始點和目標點，在突防網格模型圖4中，選定的第1地形匹配區(qū)的匹配點為M1與M2，第2地形匹配區(qū)的匹配點為M3與M4，第3地形匹配區(qū)的匹配點為M5與M6，第1景象匹配區(qū)的匹配點為V1與V2，第2景象匹配區(qū)的匹配點為V3與V4，第3景象匹配區(qū)的匹配點為V5與V6。

從圖中可清楚地看出，經過每個匹配節(jié)點的航跡線均為32條，從起始節(jié)點M1與M2開始計算出連接目標點的節(jié)點V5與V6的每條航線的飛越成本，并儲存以備下一步使用。

1.6 航跡評估

航跡選擇實質上就是在每個匹配區(qū)選擇最佳匹配點的過程，在上面航跡合并的基礎上，計算連接起始點到航跡樹的每條航跡路線，再由每條航跡路線到達目標點的總的飛越成本，選擇具有最低飛越成本值的路徑，即為最佳航跡路線。

圖4 航跡合并Fig.4 Trajectory merge

在圖4中，從目標點開始反向搜索，分別計算到達景象匹配節(jié)點V5和V6的飛越成本，選擇兩者中具有最低飛越成本的節(jié)點，如圖4中加粗航線所經的V5，然后根據(jù)上述航跡合并中所計算儲存好的經過V5的每條航線的飛越成本中，選擇具有最低飛越成本的航跡，圖4中V5至M2之間加粗的航線，也就是其間的最佳航跡。從M2開始至起始點之間仍然是動態(tài)規(guī)劃反向搜索，直至起始點為止，這樣規(guī)劃完成的一條完整航跡線即為從起始點到目標點之間最終選擇出的最優(yōu)航跡，如圖4中所示的加粗線即為最優(yōu)的參考航跡。

由一系列具體的規(guī)劃方法生成一條最優(yōu)的參考航跡，但是在實際的飛行中并非一定嚴格按照參考航跡來飛，它還要受到自身約束條件(例如:飛行高度、飛行速度、最小轉彎半徑、滾轉角等)的限制。因此生成參考航跡后還要根據(jù)飛行器自身的性能指標對參考航跡進行局部優(yōu)化［12］，最后生成最優(yōu)航跡。

2 仿真結果及分析

2.1 突防網格模型的建立

根據(jù)上面介紹的低空動態(tài)規(guī)劃方法，本文以某一區(qū)域數(shù)字地圖為基礎數(shù)據(jù)，形成了突防網格模型，然后選擇地形匹配區(qū)和景象匹配區(qū)及相應的地形匹配點和景象匹配點，建立了基于動態(tài)規(guī)劃算法為分段航跡規(guī)劃的應用程序，并通過航跡段合并及航跡選擇和評估，最后得到最優(yōu)的參考航跡路線結果。

在本航跡規(guī)劃系統(tǒng)中，可隨時根據(jù)攻擊區(qū)變化的情況，將最新的內容讀入程序，在程序執(zhí)行之中，即將攻擊威脅數(shù)字轉化在突防網格模型圖上，如圖5所示為突防網格模型圖，其中A，B，C為3個攻擊區(qū)，其具體內容如下:

A區(qū):攻擊武器為導彈，

攻擊半徑在內圓范圍內殺傷力為70%，

攻擊半徑在外圓范圍內殺傷力為30%;

B區(qū):攻擊武器為高炮，

攻擊半徑在內圓范圍內殺傷力為70%，

攻擊半徑在外圓范圍內殺傷力為30%;

C區(qū):攻擊武器為導彈，

攻擊半徑在內圓范圍內殺傷力為70%，

攻擊半徑在外圓范圍內殺傷力為30%。

根據(jù)上述匹配區(qū)及匹配點的選擇原則，最終的選擇結果如圖5所示，靠近起始點Start為3個地形匹配區(qū)，每個地形匹配區(qū)內有2個地形匹配點(圖中標以M的點)，在靠近目標點Target為3個景象匹配區(qū)，每個景象匹配區(qū)內有2個景象匹配點(圖中標以V的點)。

2.2 最優(yōu)參考航跡結果及分析

由任務規(guī)劃系統(tǒng)選定的起始點、3個地形匹配區(qū)、3個景象匹配區(qū)、目標點等信息，根據(jù)本文建立的航跡規(guī)劃系統(tǒng)經過分段航跡規(guī)劃、航跡合并、航跡選擇與評估得出最終的航跡規(guī)劃結果。圖5為在突防網格模型基礎上的航跡規(guī)劃系統(tǒng)完成的最優(yōu)參考航跡結果，以紅色線表示。

圖5 最優(yōu)參考航跡結果Fig.5 Optimal result of trajectory planning

可以看到，在突防網格模型圖上從起始點開始最優(yōu)航跡線基本走突防概率低的網格(深色)，并能安全地繞過山峰障礙以及攻擊威脅區(qū)，安全到達目的地。經過改變包括起始點和目標點在內的節(jié)點坐標反復試驗，驗證了本文建立的航跡規(guī)劃方法能夠快速、有效地實現(xiàn)低空航行任務，具有很好的實用性。

3 結束語

本文建立了基于突防網格模型的航跡規(guī)劃系統(tǒng)，將動態(tài)規(guī)劃算法應用于分段航跡規(guī)劃方法中，然后通過航跡合并及航跡評估，最后得到最優(yōu)的參考航跡路線結果。經仿真試驗證明該系統(tǒng)不僅能夠回避已知的威脅、山峰障礙，而且能夠實時接收指控系統(tǒng)的指令，根據(jù)實際情況重新規(guī)劃航跡，回避突然來襲的威脅，最終安全完成低空飛行任務。

［1］ 葉文，廉華耕，漆云海，等.無人機航路算法研究［J］.電光與控制，2011，18(2):8-13.YE Wen，LIAN Hua-geng，QI Yun-hai，et al.Path Planning Algorithm for UAV［J］.Electronics Optics＆ Control，2011，18(2):8-12.

［2］ Myron Hura，Gary Mcleod.低可觀測性飛機和巡航導彈的航跡規(guī)劃問題［J］.徐海江，編譯.飛航導彈，1997(5):17-23 Myron Hura，Gary Mcleod.Trajectory Planning of Low Observable Aircraft and Cruise Missile［J］.XU Haijiang，Translated.Winged Missiles Journal，1997(5):17-23.

［3］ Myron Hura，Gary Mcleod.低可觀測性飛機和巡航導彈的航跡規(guī)劃問題(續(xù))［J］.徐海江，編譯.飛航導彈，1997(6):3-9.Myron Hura，Gary Mcleod.Trajectory Planning of Low Observable Aircraft and Cruise Missile［J］.XU Haijiang，Translated.Winged Missiles Journal，1997(6):3-9.

［4］ 袁衛(wèi)東.一種新的綜合TF/TA最優(yōu)航跡算法［J］.南京航空航天大學學報，1996，28(4):481-486.YUAN Wei-dong.A New Optimal Trajectory Planning of Comprehensive TF/TA［J］.Journal of Nanjing University of Aeronautics ＆ Astronautics，1996，28(4):481-486.

［5］ 趙鋒，楊偉，王偉，等.基于組合優(yōu)化算法的無人機航跡規(guī)劃方法研究［J］.彈箭與制導學報，2009，29(2):282-285.ZHAO Feng，YANG Wei，WANG Wei，et al.A Study of UAV Trajectory Planning Approach Based on Combined Optimization Method［J］.Journal of Projectiles，Rockets，Missile ＆ Guidance，2009，29(2):282-285.

［6］ 高暉，陳欣，夏云程.無人機航路規(guī)劃研究［J］.南京航空航天大學學報，2001，33(2):135-138.GAO Hui，CHEN Xin，XIA Yun-cheng.Study on Trajectory Plan for Unmanned Aircraft Vehicle［J］.Journal of Nanjing University of Aeronautics ＆ Astronautics，2001，33(2):135-138.

［7］ 徐克虎，賀也平，沈春林.一種改進的地形輪廓預測匹配輔助導航算法［J］.航空計算技術，2000，30(1):9-11.XU Ke-hu，HE Ye-ping，SHEN Chun-lin.A Improved Algorithmic of Terrain Contour Forecast Matching Aided Navigation［J］.Aeronautical Computing Technique，2000，30(1):9-11.

［8］ 李躍.導航與定位［M］.北京:國防工業(yè)出版社，2008:433-446.LI Yue.Navigation and Positioning［M］.Beijing:National Defense Industry Press，2008:433-446.

［9］ 盧開澄.單目標、多目標與整數(shù)規(guī)劃［M］.北京:清華大學出版社，1999.LU Kai-cheng.Single Objective and Multiple Objectives Programming［M］.Beijing:Tsinghua University Press，1999.

［10］ 羅伯特約翰.動態(tài)規(guī)劃原理［M］.陳偉基，譯.北京:清華大學出版社，1984.Robert John.The Principle of Dynamic Programming［M］.CHEN Wei-ji，Translated.Beijing:Tsinghua University Press，1984.

［11］ 吳劍，喻玉華，周繼強，等.無人機航路規(guī)劃中的變步長 A*算法［J］.電光與控制，2011，18(5):1-6.WU Jian，YU Yu-hua，ZHOU Ji-qiang，et al.Path Planning Algorithm of the Variable Step A*for UAV［J］.E-lectronics Optics ＆ Control，2011，18(5):1-6.

［12］ 閔昌萬，袁建平.航跡規(guī)劃中安全走廊及參考軌跡的確定［J］.飛行力學，1999，17(2):12-16.MIN Chang-wan，YUAN Jian-ping.The Determination of Safe Corridor and Reference Path in Route Planning［J］.Flight Dynamics，1999，17(2):12-16.