孫利軍

(光電信息控制和安全技術(shù)重點(diǎn)實(shí)驗(yàn)室，河北三河 065201)

0 引言

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

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

1.1 突防網(wǎng)格模型

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

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

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

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

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

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

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

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

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

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

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

算法如下:

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

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

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

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

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

1.5 航跡合并

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

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

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

1.6 航跡評(píng)估

航跡選擇實(shí)質(zhì)上就是在每個(gè)匹配區(qū)選擇最佳匹配點(diǎn)的過程，在上面航跡合并的基礎(chǔ)上，計(jì)算連接起始點(diǎn)到航跡樹的每條航跡路線，再由每條航跡路線到達(dá)目標(biāo)點(diǎn)的總的飛越成本，選擇具有最低飛越成本值的路徑，即為最佳航跡路線。

圖4 航跡合并Fig.4 Trajectory merge

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

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

2 仿真結(jié)果及分析

2.1 突防網(wǎng)格模型的建立

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

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

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

攻擊半徑在內(nèi)圓范圍內(nèi)殺傷力為70%，

攻擊半徑在外圓范圍內(nèi)殺傷力為30%;

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

攻擊半徑在內(nèi)圓范圍內(nèi)殺傷力為70%，

攻擊半徑在外圓范圍內(nèi)殺傷力為30%;

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

攻擊半徑在內(nèi)圓范圍內(nèi)殺傷力為70%，

攻擊半徑在外圓范圍內(nèi)殺傷力為30%。

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

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

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

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

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

3 結(jié)束語

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

［1］ 葉文，廉華耕，漆云海，等.無人機(jī)航路算法研究［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.低可觀測(cè)性飛機(jī)和巡航導(dǎo)彈的航跡規(guī)劃問題［J］.徐海江，編譯.飛航導(dǎo)彈，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.低可觀測(cè)性飛機(jī)和巡航導(dǎo)彈的航跡規(guī)劃問題(續(xù))［J］.徐海江，編譯.飛航導(dǎo)彈，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］.南京航空航天大學(xué)學(xué)報(bào)，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)化算法的無人機(jī)航跡規(guī)劃方法研究［J］.彈箭與制導(dǎo)學(xué)報(bào)，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］ 高暉，陳欣，夏云程.無人機(jī)航路規(guī)劃研究［J］.南京航空航天大學(xué)學(xué)報(bào)，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ìn)的地形輪廓預(yù)測(cè)匹配輔助導(dǎo)航算法［J］.航空計(jì)算技術(shù)，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］ 李躍.導(dǎo)航與定位［M］.北京:國(guó)防工業(yè)出版社，2008:433-446.LI Yue.Navigation and Positioning［M］.Beijing:National Defense Industry Press，2008:433-446.

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

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

［11］ 吳劍，喻玉華，周繼強(qiáng)，等.無人機(jī)航路規(guī)劃中的變步長(zhǎng) 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］.飛行力學(xué)，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.