基于SAS算法的直升機(jī)應(yīng)召搜潛航路規(guī)劃研究?

李 林 韓 強(qiáng) 黎子芬

（海軍航空大學(xué)青島校區(qū) 青島 266041）

1 引言

直升機(jī)搜潛方式主要包括應(yīng)召、巡邏等搜潛方式。相比較而言，應(yīng)召搜潛是反潛作戰(zhàn)、訓(xùn)練中使用最多而且十分重要的戰(zhàn)術(shù)方式。應(yīng)召搜潛是指在已經(jīng)獲取了目標(biāo)潛艇在某一時(shí)刻的概略位置或航向、航速等信息的前提下，反潛直升機(jī)領(lǐng)受任務(wù)后飛抵目標(biāo)海域，再次對(duì)目標(biāo)進(jìn)行搜索定位的過程［1］。如何克服應(yīng)召搜潛飛行航路存在的隨機(jī)性和盲目性，提高搜索效率是各方關(guān)心的問題。本文基于SAS算法對(duì)直升機(jī)搜潛航路進(jìn)行仿真計(jì)算和規(guī)劃效率評(píng)估，可以為部隊(duì)反潛訓(xùn)練中制定應(yīng)召搜潛航路提供參考，在提高搜潛效率方面發(fā)揮積極作用。

2 算法分析

應(yīng)用于飛行器航路規(guī)劃的算法主要有簡單航路規(guī)劃、A*搜索算法、遺傳算法、蟻群算法、電視規(guī)劃算法以及一些新型的規(guī)劃算法［2］，但并非所有算法都適用于直升機(jī)應(yīng)召反潛航路規(guī)劃。經(jīng)初步篩選，可用于直升機(jī)航路規(guī)劃的算法主要有簡單航路規(guī)劃、遺傳算法、蟻群算法、A*搜索算法等。其中，蟻群算法應(yīng)用于直升機(jī)搜潛航路規(guī)劃本文作者已經(jīng)進(jìn)行了研究，這里也不再贅述。

簡單航路規(guī)劃算法適用于飛行航線上障礙物少、威脅程度低、威脅源移動(dòng)速度慢等簡單情況，具有航路簡單、速度快的優(yōu)點(diǎn)，通常用于近海反潛作戰(zhàn)，這里不作為主要研究對(duì)象。

遺傳算法作為一種仿生學(xué)技術(shù)，因其獨(dú)特的組織學(xué)習(xí)適應(yīng)能力，在許多領(lǐng)域都有出色的表現(xiàn)。但是，在航路規(guī)劃方面并沒有其他啟發(fā)式路徑尋優(yōu)算法表現(xiàn)的效果好。綜合考慮該算法的特性和應(yīng)用實(shí)際，也不作為本文的主要研究對(duì)象。

A*搜索算法是啟發(fā)式搜索算法的一種，是非常優(yōu)秀的最短路徑搜索算法之一［3］。由于A*算法的復(fù)雜性以及其搜索的可能種類為無窮，導(dǎo)致解算過程需占用大量的時(shí)間和空間。為便于實(shí)際應(yīng)用，將其進(jìn)行壓縮和優(yōu)化處理，改進(jìn)為SAS算法，即稀疏A*搜索算法（Sparse A*search，SAS）［4］，適用于直升機(jī)搜潛航路規(guī)劃。

3 SAS算法

3.1 算法描述

SAS算法是Robert J.Barbarize等為了加快A*算法的收斂速度、節(jié)省運(yùn)算空間改進(jìn)的一種新算法［5］。 A*算 法 的 函 數(shù) 表 達(dá) 式 為f*(x)=p*g*(x)+q*h*(x)，SAS算法則是將該函數(shù)中的系數(shù)設(shè)置為常數(shù)，簡化為 f*(x)=g*(x)+h*(x)。該算法的核心是評(píng)估函數(shù)的設(shè)計(jì)，在選擇當(dāng)前節(jié)點(diǎn)的下一個(gè)考察接點(diǎn)i時(shí)引入了估價(jià)函數(shù)，f*(x)表示從節(jié)點(diǎn)S0到節(jié)點(diǎn)x的一條最佳路徑的實(shí)際代價(jià)加上從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)之和，g*(x)就是從節(jié)點(diǎn)S0到節(jié)點(diǎn)x之間最小代價(jià)路徑的實(shí)際代價(jià)，h*(x)則是從x節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最小代價(jià)路徑上的代價(jià)［6］。

SAS算法具有兩種優(yōu)秀的特性，即可采納性（在可解狀態(tài)空間里能在有限的時(shí)間內(nèi)終止并找到解）和單調(diào)性（通過對(duì)h*(x)啟發(fā)函數(shù)以適當(dāng)單調(diào)性限制，可使一系列節(jié)點(diǎn)的評(píng)估值成一定的單調(diào)增或非減特性）［7～8］，可以保證對(duì)直升機(jī)應(yīng)召搜潛航路進(jìn)行高效、最優(yōu)規(guī)劃。

3.2 算法流程

路徑規(guī)劃求解是要求全局最優(yōu)的優(yōu)先搜索問題，SAS算法流程如圖1所示，其搜索算法如下：

1）初始化，把初始節(jié)點(diǎn)S0放入OPEN表；

2）尋找該節(jié)點(diǎn)周圍可到達(dá)的點(diǎn)，該點(diǎn)作為這些點(diǎn)的上輩節(jié)點(diǎn)；

3）從OPEN列表刪除該點(diǎn)，加入CLOSE列表；

4）計(jì)算該點(diǎn) F=G+H（F=f*(x)；G=g*(x)；H=h*(x)）；

5）判斷F是否最小，最小則尋找節(jié)點(diǎn)成功，把它從OPEN列表刪除，加入CLOSE列表；否則，該點(diǎn)不加入CLOSE列表；

6）該點(diǎn)是否為目標(biāo)點(diǎn)，是則結(jié)束；否則跳轉(zhuǎn)到第2）步。

圖1 SAS算法流程圖

4 約束條件

在對(duì)應(yīng)召搜潛航路進(jìn)行評(píng)價(jià)時(shí)，首先要構(gòu)建評(píng)價(jià)指標(biāo)，通常要考慮直升機(jī)的航程指標(biāo)、安全指標(biāo)、飛行時(shí)間指標(biāo)以及綜合權(quán)重指標(biāo)等。除此之外，還須考慮到直升機(jī)自身的性能特點(diǎn)和所處的戰(zhàn)場環(huán)境，包括機(jī)動(dòng)性能、最大航程和威脅、戰(zhàn)術(shù)等方面的約束條件［9］。

4.1 機(jī)動(dòng)性能約束

機(jī)動(dòng)性能約束主要是指由于威脅區(qū)的存在，直升機(jī)在航路轉(zhuǎn)彎時(shí)對(duì)飛行方向和高度進(jìn)行調(diào)整時(shí)需考慮的最小轉(zhuǎn)彎半徑以及最大爬升速度等限制。

1）最小轉(zhuǎn)彎半徑

反映了直升機(jī)在水平面上轉(zhuǎn)變航向的機(jī)動(dòng)能力，主要考慮的是威脅區(qū)影響和目標(biāo)大角度規(guī)避時(shí)為及時(shí)跟蹤搜索而進(jìn)行的機(jī)動(dòng)。關(guān)鍵航路點(diǎn)的設(shè)置應(yīng)滿足：

式中： ||KAKB是兩個(gè)關(guān)鍵航路點(diǎn)間的距離；θ是轉(zhuǎn)彎角；rmin是最小轉(zhuǎn)彎半徑。

2）最大爬升速度

反映了直升機(jī)在一定的水平初速情況下在垂直方向上的機(jī)動(dòng)能力。在一定的速度下，在飛躍軍艦、海島等一定高度的障礙時(shí)，需對(duì)其考慮，以免其發(fā)生碰撞。

4.2 最大航程約束

直升機(jī)執(zhí)行應(yīng)召搜潛任務(wù)時(shí)需攜帶一種甚至多種搜潛器材，必要時(shí)還要攜帶攻潛武器，這就限制了所能攜帶的燃油數(shù)量，而且直升機(jī)通常還要在目標(biāo)海域滯留一段時(shí)間，上述因素決定了規(guī)劃的航路必須考慮最大航程的約束，即各航段的總路程之和不能大于最大航程。

對(duì)于一條有n個(gè)航路點(diǎn)的航路，其最大航程約束可表示為

式中，JC為某條航路的航程指標(biāo)；Li-1為兩個(gè)相鄰航路點(diǎn)之間的航程；Lmax為燃料消耗指標(biāo)所允許的最大值。

4.3 威脅約束

威脅約束是動(dòng)態(tài)變化的，是重要的約束條件。常見的威脅源主要包括敵方的防空雷達(dá)、防空武器以及戰(zhàn)機(jī)等［10］。由于在進(jìn)行航路規(guī)劃時(shí)威脅是必須規(guī)避的，可將其歸結(jié)為不可穿越障礙區(qū)，并在仿真中適當(dāng)予以擴(kuò)大，防止直升飛機(jī)執(zhí)行搜潛任務(wù)時(shí)因累積偏差誤入威脅區(qū)。

假設(shè)直升機(jī)領(lǐng)受搜潛任務(wù)后飛向目標(biāo)海域過程中的威脅區(qū)和禁飛區(qū)的集合為RT，航路函數(shù)為f(x ，y，t)=0（x，y，t分別表示航路上任意點(diǎn)的經(jīng)緯度坐標(biāo)和直升機(jī)飛行時(shí)間），則威脅約束可以用下式進(jìn)行描述：

4.4 戰(zhàn)術(shù)約束

在反潛作戰(zhàn)中，目標(biāo)從被發(fā)現(xiàn)到消失的時(shí)間通常十分有限，因此要求直升機(jī)必須在最短的時(shí)間內(nèi)到達(dá)目標(biāo)海域，這就涉及到戰(zhàn)術(shù)約束條件［11］。

1）進(jìn)入搜索區(qū)的方位約束

由于目標(biāo)散布概率模型不同，直升機(jī)進(jìn)入搜索區(qū)的方位不同，搜索概率也不同。理想的進(jìn)入方位是沿著潛艇運(yùn)動(dòng)方向進(jìn)入，即對(duì)直升機(jī)進(jìn)入搜索區(qū)的方位進(jìn)行約束。

式中，HS為進(jìn)入搜索區(qū)的預(yù)定方向；(Xf，Yf)為直升機(jī)最后一個(gè)航路點(diǎn)坐標(biāo)；(Xt，Yt) 為目標(biāo)被發(fā)現(xiàn)的坐標(biāo)；DH為允許進(jìn)入方位最大偏差。

2）時(shí)間約束

直升機(jī)從領(lǐng)受任務(wù)至到達(dá)搜索區(qū)的時(shí)間受天氣、環(huán)境、速度、航路軌跡等諸多因素的約束，在多機(jī)、艦機(jī)協(xié)同作戰(zhàn)中的要求更高。為避免給目標(biāo)更多的逃逸時(shí)間，這就要求規(guī)劃的航路必須合理、高效。

4.5 其它約束

除了上述約束外，還有諸如航空管制區(qū)、禁飛區(qū)、飛行限制區(qū)等需要考慮［12］。為方便仿真計(jì)算，可將其簡化為威脅區(qū)性質(zhì)的障礙模型處理。

5 仿真驗(yàn)證

直升機(jī)在執(zhí)行應(yīng)召搜潛任務(wù)時(shí)，首先要獲取目標(biāo)的概略位置，然后獲取戰(zhàn)場地圖信息、敵我態(tài)勢(shì)信息以及禁飛區(qū)等障礙區(qū)域信息，最后選擇合適的航路規(guī)劃算法計(jì)算出最優(yōu)航路。

為了適應(yīng)SAS算法尋找最優(yōu)路徑，可將相關(guān)地圖信息用方格圖的形式進(jìn)行顯示，并適當(dāng)放大禁飛區(qū)范圍。戰(zhàn)場環(huán)境可通過通過加載txt文件矩陣數(shù)據(jù)來生成，在具體使用過程中同樣可以加載獲取的實(shí)時(shí)戰(zhàn)場態(tài)勢(shì)信息來進(jìn)行實(shí)時(shí)航路規(guī)劃。

在航路規(guī)劃時(shí)，首先加載禁飛區(qū)域信息和相關(guān)數(shù)據(jù)，由飛行員手動(dòng)選取開始點(diǎn)和目標(biāo)點(diǎn)（如圖2所示）后便可動(dòng)畫顯示搜索路徑（如圖3所示），當(dāng)搜索到最短路徑后自動(dòng)顯示在屏幕上（如圖4所示）。

為便于使用，采用北東坐標(biāo)系進(jìn)行顯示，可以以開始點(diǎn)為參考點(diǎn)，以目標(biāo)相對(duì)我方位置進(jìn)行顯示。飛行員根據(jù)圖中最短路徑（由于已經(jīng)把其他因素給排除掉了，所以這里所說的最短路徑，即最優(yōu)路徑）操縱飛行到達(dá)目標(biāo)點(diǎn)，也可根據(jù)戰(zhàn)場態(tài)勢(shì)變化，實(shí)時(shí)規(guī)劃出最優(yōu)路徑，輔助飛行員進(jìn)行決策。

采用SAS算法對(duì)直升機(jī)應(yīng)召搜潛航路規(guī)劃進(jìn)行仿真分析，可以得出如下結(jié)果：

圖3 輸入開始點(diǎn)、目標(biāo)點(diǎn)后動(dòng)畫顯示的搜索路徑

1）在地圖信息信息不是很大的情況下，運(yùn)行32*32大的矩陣圖進(jìn)行尋找最優(yōu)路徑，SAS約為46.6個(gè)方格距離（如圖5所示）。在規(guī)劃速度方面，整個(gè)仿真程序耗時(shí)大概在8s左右，其中SAS算法路徑規(guī)劃耗時(shí)0.2s左右。

圖4 搜索到的最短路徑

圖5 SAS算法仿真圖

2）在地圖信息信息進(jìn)行適當(dāng)放大以后，運(yùn)行84*84大的矩陣圖進(jìn)行尋找最優(yōu)路徑，規(guī)劃出的最優(yōu)路徑約為118.6個(gè)方格距離（如圖6所示）。在規(guī)劃速度方面，整個(gè)仿真程序耗時(shí)24s，其中SAS算法路徑規(guī)劃耗時(shí)約2.8s。

圖6 SAS算法仿真圖

3）為了進(jìn)一步驗(yàn)證該算法是否符合實(shí)際要求，用168*168的地理信息矩陣進(jìn)行仿真，規(guī)劃出的最短路徑約為233.7個(gè)方格距離（如圖7所示），最短路徑效果指標(biāo)也比較理想。而且，規(guī)劃速度也很快，整個(gè)仿真程序耗時(shí)約88.3s，其中SAS算法路徑規(guī)劃耗時(shí)約21.7s。

圖7 SAS算法仿真圖

6 結(jié)語

通過利用SAS算法對(duì)直升機(jī)應(yīng)召搜潛航路規(guī)劃進(jìn)行仿真計(jì)算，結(jié)果表明：

1）地圖信息量不大時(shí)，在獲取的最優(yōu)路徑效果相當(dāng)?shù)那闆r下，SAS算法與其他算法（如蟻群算法、遺傳算法等）相比在運(yùn)算速度方面基本相當(dāng)，都能夠較好的滿足要求。也就是說，在非交戰(zhàn)環(huán)境下執(zhí)行搜潛任務(wù)或者在交戰(zhàn)環(huán)境下敵方海上軍力一般的情況下，采用SAS算法對(duì)直升機(jī)應(yīng)召搜潛航路進(jìn)行規(guī)劃是適用的。

2）地圖信息量較大時(shí)，也就是說執(zhí)行應(yīng)召搜潛區(qū)域的海況比較復(fù)雜或者敵方海上力量比較強(qiáng)大時(shí)，SAS算法與其他算法（如蟻群算法、遺傳算法等）相比在運(yùn)算速度和航路規(guī)劃效果上表現(xiàn)出明顯優(yōu)勢(shì)，能夠較好地滿足作戰(zhàn)、訓(xùn)練的需求。

因此，直升機(jī)在執(zhí)行應(yīng)召搜潛航路規(guī)劃時(shí)，無論地圖信息量大小選擇SAS算法都能比其他算法更好滿足實(shí)際需求，但考慮到地圖信息量大時(shí)運(yùn)算速度會(huì)下降，有必要對(duì)戰(zhàn)場信息進(jìn)行過濾和簡化來提高規(guī)劃效率。