基于Lazy Theta*算法的反潛巡邏飛機航路規(guī)劃研究?

（海軍指揮學院 南京 210016）

1 引言

反潛巡邏飛機是現(xiàn)在乃至將來海上反潛作戰(zhàn)的主要作戰(zhàn)力量，由于其相對水面艦艇和潛艇反潛而言，機動性更強、搜索效率更高、不易被潛艇攻擊等特點，得到各國海軍的重視［1］。一般情況下，反潛巡邏飛機通常是在獲得相關情報信息后，對指定海域執(zhí)行巡邏反潛任務，或者對疑似潛艇目標執(zhí)行應召反潛任務。

在規(guī)劃反潛巡邏飛機飛行航路時，不僅需要考慮雷暴、云層等自然因素，還需要考慮藍方防空火力、偵察探測的覆蓋范圍等戰(zhàn)場態(tài)勢。快速地為反潛巡邏飛機擬定安全、可靠、高效的飛行航線，是提高反潛巡邏飛機作戰(zhàn)效率的有效途徑之一。

目前，經(jīng)典的航路規(guī)劃方法主要有A*算法［2］、遺傳算法［3～4］、蟻群算法［5～7］等。針對經(jīng)典航路規(guī)劃方法容易導致最終得到的路徑不平滑、存在過多轉折點的問題，本文采用Lazy Theta*算法，在搜索路徑的同時允許以任意角度改變路徑的方向、對路徑進行平滑處理。經(jīng)過仿真實驗表明，能夠得到平滑且距離更短的路徑。

2 Lazy Theta*算法

Lazy Theta*算法通過進行啟發(fā)式路徑搜索，同時對父節(jié)點進行可達性檢測分析，通過減少轉向次數(shù)和縮短路徑長度等方式，實現(xiàn)對搜索路徑的高效優(yōu)化［8］。其原理如圖1所示。

其中，灰色區(qū)域表示障礙區(qū)域，白色區(qū)域表示自由區(qū)域。算法從起點作為擴展節(jié)點開始搜索，如圖1（a），細箭頭表示箭頭所在點向起點進行可達性搜索；找到離終點最近的點后，以該點作為新的擴展節(jié)點進行可達性搜索，如圖1（b）；形成可能的路徑并將途徑障礙區(qū)域的路徑調整為從自由區(qū)域經(jīng)過，如圖1（c）、圖1（d），粗箭頭表示可能的路徑；以此類推，直到形成從起點到終點并避開障礙區(qū)域的路徑 A4→B3→B2→C1，如圖 1（e）；但此時形成的并不是最短路徑，該路徑的基礎上，通過判斷各節(jié)點之間的通視性，對路徑進行優(yōu)化，得到最優(yōu)路徑A4→B3→C1，如圖 1（f）。

圖1 Lazy Theta*航路規(guī)劃算法步驟示意圖

3 反潛巡邏飛機航路規(guī)劃問題建模

3.1 幾點說明

1）威脅區(qū)域包括該區(qū)域海平面以上的空域

在實際運用中，對于威脅區(qū)域往往是一個立體的概念，反潛巡邏飛機在規(guī)劃航路時需要避開。安全起見，通常認為威脅區(qū)域覆蓋了該區(qū)域從海平面到反潛巡邏飛機最大飛行高度的空間，反潛巡邏飛機一般不會采取調整高度的方式來規(guī)避某些防空火力的威脅，而是采用從區(qū)域外完全規(guī)避的方式飛行?；诖?，可以將三維空間的航路規(guī)劃問題簡化為二維平面中的航路規(guī)劃問題進行求解，大大提高計算效率，同時也保證實際運用的飛行安全問題。

2）區(qū)域內經(jīng)線相互平行

在地理坐標系中，各經(jīng)線之間并不平行，但反潛巡邏飛機飛行航路多集中于某一局部區(qū)域。由于區(qū)域跨度有限，在柵格化處理時可以近似的認為該區(qū)域內經(jīng)線互相平行，這種處理對反潛巡邏飛機飛行航路規(guī)劃的影響較小，同時也能簡化計算、提高效率。

3.2 問題描述

反潛巡邏飛機航路規(guī)劃問題實質上屬于最優(yōu)化問題的一種。其中，反潛巡邏飛機面臨的戰(zhàn)場環(huán)境即為最優(yōu)化問題的約束條件，飛行航路的評價指標即為最優(yōu)化問題的優(yōu)化指標，最終規(guī)劃的飛行航路即為最優(yōu)化問題在滿足約束條件下的全局最優(yōu)解。

根據(jù)約束條件、優(yōu)化指標的不同，反潛巡邏飛機航路規(guī)劃問題可以分為不同的類型。

1）最短航路規(guī)劃問題:將反潛巡邏飛機飛行路程作為優(yōu)化指標的飛行航路規(guī)劃。

2）最佳油耗規(guī)劃問題:將反潛巡邏飛機飛行油耗作為優(yōu)化指標的飛行航路規(guī)劃，這種規(guī)劃問題中通常還需要同時規(guī)劃飛機在不同航路段的飛行高度和速度。

3）最安全航路規(guī)劃問題:將反潛巡邏飛機飛行安全作為優(yōu)化指標的飛行航路規(guī)劃。

本文研究最短航路規(guī)劃問題，考慮氣象條件和藍方威脅兩類戰(zhàn)場環(huán)境作為約束條件，以反潛巡邏飛機飛行路程作為優(yōu)化指標進行研究。

3.3 戰(zhàn)場環(huán)境建模

為便于把戰(zhàn)場環(huán)境轉化為數(shù)學化的約束條件，采用柵格法對反潛巡邏飛機面臨的戰(zhàn)場環(huán)境進行建模。將戰(zhàn)場環(huán)境空間劃分成多個同樣大小的區(qū)域，對氣象威脅和藍方威脅轉換成區(qū)域的可通過性進行描述。

通常情況下，反潛巡邏飛機飛行航路上的威脅區(qū)域在地圖上的平面投影由一個或多個多邊形組成。在不同的規(guī)劃任務中，根據(jù)規(guī)劃路徑的精度要求，可以按照不同的精度對地圖進行柵格化，其柵格化規(guī)則如下。

1）每個柵格的威脅性設置為威脅柵格和安全柵格，威脅柵格用1描述，表示存在威脅，飛機不可通過；安全柵格用0描述，表示不存在威脅，飛機可安全通過。

2）威脅區(qū)域在柵格上的投影完全覆蓋柵格，認為該柵格是威脅柵格。

3）威脅區(qū)域在柵格上的投影覆蓋不滿一個柵格，認為該柵格是威脅柵格。

4）沒有威脅區(qū)域投影覆蓋的柵格，認為是安全柵格。

5）只對反潛巡邏飛機可能涉及的區(qū)域進行柵格化，為使問題簡化，認為區(qū)域柵格的橫軸與緯線平行，縱軸與經(jīng)線平行，橫縱軸相互垂直。

通過對地圖進行柵格化，能夠直觀地描述反潛巡邏飛機的航路規(guī)劃空間。柵格越小，對航路規(guī)劃的計算也就越精細，但對應的計算量也顯著增加，所耗費的計算時間也越多。在考慮航路規(guī)劃精度的同時，需要考慮算法所耗費的資源和時間，避免過于繁冗的計算過程。

3.4 航路規(guī)劃指標建模

在規(guī)劃反潛飛機飛行航路時，需要建立各航路的性能優(yōu)化指標。在地圖柵格化的基礎上，以柵格的橫軸方向為x軸，縱軸方向為y軸，柵格的坐標以（x，y）表示，柵格的安全性函數(shù)f（x，y）可以表示為

假設所有氣象威脅的柵格集合為RW，所有藍方威脅的柵格集合為RE，對于航路柵格集合R上的任意一個航路點柵格（xi，yi），應該滿足f（xi，yi）=0，則航路規(guī)劃問題的約束條件可以描述為

在避開氣象威脅和藍方威脅的基礎上，以反潛巡邏飛機最短飛行航路作為優(yōu)化目標，使飛機的飛行距離最小，對R上的任意一個航路點柵格（xi，yi），建立航路規(guī)劃目標函數(shù)如下:

其中，n為航路點個數(shù)。滿足使D最小的航路點柵格（xi，yi）集合和n即為滿足安全條件下的最短航路和航路點的個數(shù)。

4 程序實現(xiàn)

4.1 地圖柵格化

地圖柵格化的程序計算流程如下。

其中，涉及兩點間球面距離、點與區(qū)域相對位置的算法［9～10］已十分成熟，此處不再贅述。

4.2 基于Lazy Theta*算法的航路規(guī)劃

圖2 Lazy Theta*算法平滑處理流程圖

Lazy Theta*算法是Theta*算法的改進，其核心在于運用Theta*算法求得航路后，對所得航路進行平滑處理，從而進一步縮短航路的距離、減少航路轉彎次數(shù)［11］。其平滑處理的程序計算流程如下，該流程中，優(yōu)化的基準點記為P0，P0的后序節(jié)點記為P1，P1的后序節(jié)點記為P2。

在規(guī)劃航路的過程中，如何保留最有價值的節(jié)點作為航路的一部分有多種判斷方式。結合最短航路規(guī)劃的目標，主要以該節(jié)點與終點之間的距離、該節(jié)點和終點的連線與起點和終點連線形成夾角的大小作為判斷依據(jù)，距離越短價值越高，距離相同的情況下，夾角越小價值越高。

4.3 實例化

將本文提出的反潛巡邏飛機航路規(guī)劃思路進行計算機實現(xiàn)，形成反潛巡邏飛機航路規(guī)劃輔助決策系統(tǒng)。系統(tǒng)能夠根據(jù)飛機的起飛機場、執(zhí)行反潛任務的目標海區(qū)以及需要避開的危險區(qū)域，采用Lazy Theta*算法自動生成飛機從機場至目標海區(qū)的飛行航路。

假設當前時刻，某海域發(fā)現(xiàn)不明潛艇信號，獲取到其可能的航向航速信息，位于A機場的反潛巡邏飛機起飛赴不明信號所在海區(qū)執(zhí)行應召反潛任務，為保障任務的隱蔽性和安全性，飛機需避開藍方驅逐艦的對空雷達探測范圍和禁飛區(qū)。根據(jù)不明潛艇可能的航向航速信息和信號所在海域與A機場的直線距離，可以初步判斷飛機飛抵海區(qū)時其反潛目標海區(qū)為不明潛艇前方扇形區(qū)域［12］，系統(tǒng)初始態(tài)勢如圖3所示。

圖3 初始態(tài)勢示意圖

基于初始態(tài)勢，系統(tǒng)對相關區(qū)域進行柵格化操作，如圖4所示，以平行緯線方向為X軸，平行經(jīng)線方向為Y軸建立柵格坐標系，使地圖上的每一個點都能對應到某一個柵格當中。

在初始態(tài)勢柵格化的基礎上，采用Lazy Theta*算法計算的飛行航路如圖5所示。最后將柵格坐標還原為經(jīng)緯度坐標即為計算結果，如圖6。需要說明的是，圖4和圖5所示的過程為計算機后臺計算和處理的示例，并不會呈現(xiàn)在指揮人員和決策者面前。若指揮人員和決策者對航路規(guī)劃結果不滿意，可以通過系統(tǒng)對威脅區(qū)域進行增刪改，再自動規(guī)劃相應的航路，也可以直接在已有航路規(guī)劃結果的基礎上增加、刪除航路點或對航路點的坐標進行修改，直至獲得滿意的結果。

圖4 初始態(tài)勢柵格化

圖5 柵格狀態(tài)下的航路規(guī)劃結果

圖6 航路規(guī)劃計算結果

從圖6所示的結果來看，算法自動規(guī)劃的飛行航路能夠避開預先設定的威脅區(qū)域，且保持航路距離最小，作為以飛行路程作為優(yōu)化指標的航路規(guī)劃問題，其規(guī)劃結果能較好地滿足要求。

5 結語

本文針對反潛巡邏飛機飛行航路規(guī)劃問題，建立了戰(zhàn)場環(huán)境和航路規(guī)劃指標模型，將Lazy Theta*算法運用于模型求解過程；設計了地圖柵格化和Lazy Theta*算法解決該問題的計算機程序邏輯，采用C++語言對這些過程進行了計算機實現(xiàn)；通過應用實例，驗證了航路規(guī)劃模型的正確性和Lazy Theta*算法在解決該問題過程中的有效性，能夠為指揮人員和決策者提供一定的決策支撐。