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

（海軍指揮學(xué)院 南京 210016）

1 引言

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

在規(guī)劃反潛巡邏飛機(jī)飛行航路時(shí)，不僅需要考慮雷暴、云層等自然因素，還需要考慮藍(lán)方防空火力、偵察探測(cè)的覆蓋范圍等戰(zhàn)場(chǎng)態(tài)勢(shì)?？焖俚貫榉礉撗策夛w機(jī)擬定安全、可靠、高效的飛行航線，是提高反潛巡邏飛機(jī)作戰(zhàn)效率的有效途徑之一。

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

2 Lazy Theta*算法

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

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

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

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

3.1 幾點(diǎn)說明

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

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

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

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

3.2 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 程序?qū)崿F(xiàn)

4.1 地圖柵格化

地圖柵格化的程序計(jì)算流程如下。

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

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

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

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

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

4.3 實(shí)例化

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

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

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

基于初始態(tài)勢(shì)，系統(tǒng)對(duì)相關(guān)區(qū)域進(jìn)行柵格化操作，如圖4所示，以平行緯線方向?yàn)閄軸，平行經(jīng)線方向?yàn)閅軸建立柵格坐標(biāo)系，使地圖上的每一個(gè)點(diǎn)都能對(duì)應(yīng)到某一個(gè)柵格當(dāng)中。

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

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

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

圖6 航路規(guī)劃計(jì)算結(jié)果

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

5 結(jié)語(yǔ)

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