基于SAS算法的直升機應召搜潛航路規劃研究?

李 林 韓 強 黎子芬

（海軍航空大學青島校區 青島 266041）

1 引言

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

2 算法分析

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

簡單航路規劃算法適用于飛行航線上障礙物少、威脅程度低、威脅源移動速度慢等簡單情況，具有航路簡單、速度快的優點，通常用于近海反潛作戰，這里不作為主要研究對象。

遺傳算法作為一種仿生學技術，因其獨特的組織學習適應能力，在許多領域都有出色的表現。但是，在航路規劃方面并沒有其他啟發式路徑尋優算法表現的效果好。綜合考慮該算法的特性和應用實際，也不作為本文的主要研究對象。

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

3 SAS算法

3.1 算法描述

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

SAS算法具有兩種優秀的特性，即可采納性（在可解狀態空間里能在有限的時間內終止并找到解）和單調性（通過對h*(x)啟發函數以適當單調性限制，可使一系列節點的評估值成一定的單調增或非減特性）［7～8］，可以保證對直升機應召搜潛航路進行高效、最優規劃。

3.2 算法流程

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

1）初始化，把初始節點S0放入OPEN表；

2）尋找該節點周圍可到達的點，該點作為這些點的上輩節點；

3）從OPEN列表刪除該點，加入CLOSE列表；

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

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

6）該點是否為目標點，是則結束；否則跳轉到第2）步。

圖1 SAS算法流程圖

4 約束條件

在對應召搜潛航路進行評價時，首先要構建評價指標，通常要考慮直升機的航程指標、安全指標、飛行時間指標以及綜合權重指標等。除此之外，還須考慮到直升機自身的性能特點和所處的戰場環境，包括機動性能、最大航程和威脅、戰術等方面的約束條件［9］。

4.1 機動性能約束

機動性能約束主要是指由于威脅區的存在，直升機在航路轉彎時對飛行方向和高度進行調整時需考慮的最小轉彎半徑以及最大爬升速度等限制。

1）最小轉彎半徑

反映了直升機在水平面上轉變航向的機動能力，主要考慮的是威脅區影響和目標大角度規避時為及時跟蹤搜索而進行的機動。關鍵航路點的設置應滿足：

式中： ||KAKB是兩個關鍵航路點間的距離；θ是轉彎角；rmin是最小轉彎半徑。

2）最大爬升速度

反映了直升機在一定的水平初速情況下在垂直方向上的機動能力。在一定的速度下，在飛躍軍艦、海島等一定高度的障礙時，需對其考慮，以免其發生碰撞。

4.2 最大航程約束

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

對于一條有n個航路點的航路，其最大航程約束可表示為

式中，JC為某條航路的航程指標；Li-1為兩個相鄰航路點之間的航程；Lmax為燃料消耗指標所允許的最大值。

4.3 威脅約束

威脅約束是動態變化的，是重要的約束條件。常見的威脅源主要包括敵方的防空雷達、防空武器以及戰機等［10］。由于在進行航路規劃時威脅是必須規避的，可將其歸結為不可穿越障礙區，并在仿真中適當予以擴大，防止直升飛機執行搜潛任務時因累積偏差誤入威脅區。

假設直升機領受搜潛任務后飛向目標海域過程中的威脅區和禁飛區的集合為RT，航路函數為f(x ，y，t)=0（x，y，t分別表示航路上任意點的經緯度坐標和直升機飛行時間），則威脅約束可以用下式進行描述：

4.4 戰術約束

在反潛作戰中，目標從被發現到消失的時間通常十分有限，因此要求直升機必須在最短的時間內到達目標海域，這就涉及到戰術約束條件［11］。

1）進入搜索區的方位約束

由于目標散布概率模型不同，直升機進入搜索區的方位不同，搜索概率也不同。理想的進入方位是沿著潛艇運動方向進入，即對直升機進入搜索區的方位進行約束。

式中，HS為進入搜索區的預定方向；(Xf，Yf)為直升機最后一個航路點坐標；(Xt，Yt) 為目標被發現的坐標；DH為允許進入方位最大偏差。

2）時間約束

直升機從領受任務至到達搜索區的時間受天氣、環境、速度、航路軌跡等諸多因素的約束，在多機、艦機協同作戰中的要求更高。為避免給目標更多的逃逸時間，這就要求規劃的航路必須合理、高效。

4.5 其它約束

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

5 仿真驗證

直升機在執行應召搜潛任務時，首先要獲取目標的概略位置，然后獲取戰場地圖信息、敵我態勢信息以及禁飛區等障礙區域信息，最后選擇合適的航路規劃算法計算出最優航路。

為了適應SAS算法尋找最優路徑，可將相關地圖信息用方格圖的形式進行顯示，并適當放大禁飛區范圍。戰場環境可通過通過加載txt文件矩陣數據來生成，在具體使用過程中同樣可以加載獲取的實時戰場態勢信息來進行實時航路規劃。

在航路規劃時，首先加載禁飛區域信息和相關數據，由飛行員手動選取開始點和目標點（如圖2所示）后便可動畫顯示搜索路徑（如圖3所示），當搜索到最短路徑后自動顯示在屏幕上（如圖4所示）。

為便于使用，采用北東坐標系進行顯示，可以以開始點為參考點，以目標相對我方位置進行顯示。飛行員根據圖中最短路徑（由于已經把其他因素給排除掉了，所以這里所說的最短路徑，即最優路徑）操縱飛行到達目標點，也可根據戰場態勢變化，實時規劃出最優路徑，輔助飛行員進行決策。

采用SAS算法對直升機應召搜潛航路規劃進行仿真分析，可以得出如下結果：

圖3 輸入開始點、目標點后動畫顯示的搜索路徑

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

圖4 搜索到的最短路徑

圖5 SAS算法仿真圖

2）在地圖信息信息進行適當放大以后，運行84*84大的矩陣圖進行尋找最優路徑，規劃出的最優路徑約為118.6個方格距離（如圖6所示）。在規劃速度方面，整個仿真程序耗時24s，其中SAS算法路徑規劃耗時約2.8s。

圖6 SAS算法仿真圖

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

圖7 SAS算法仿真圖

6 結語

通過利用SAS算法對直升機應召搜潛航路規劃進行仿真計算，結果表明：

1）地圖信息量不大時，在獲取的最優路徑效果相當的情況下，SAS算法與其他算法（如蟻群算法、遺傳算法等）相比在運算速度方面基本相當，都能夠較好的滿足要求。也就是說，在非交戰環境下執行搜潛任務或者在交戰環境下敵方海上軍力一般的情況下，采用SAS算法對直升機應召搜潛航路進行規劃是適用的。

2）地圖信息量較大時，也就是說執行應召搜潛區域的海況比較復雜或者敵方海上力量比較強大時，SAS算法與其他算法（如蟻群算法、遺傳算法等）相比在運算速度和航路規劃效果上表現出明顯優勢，能夠較好地滿足作戰、訓練的需求。

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