基于SAS算法的飛行器低空突防三維航路規劃研究?

孫 濤 劉家祺 張龍杰 樊鵬飛 周 濤

基于SAS算法的飛行器低空突防三維航路規劃研究?

孫 濤1劉家祺1張龍杰1樊鵬飛1周 濤2

（1.海軍航空工程學院兵器科學與技術系 煙臺 264001）（2.海軍航空工程學院學員二旅 煙臺 264001）

SAS算法的各個主要搜索參數對飛行器航路規劃的結果影響關系復雜，論文在對低空突防三維航路規劃進行仿真實現的基礎上，對最小步長搜索步長、擴展節點數、代價函數權重、最大飛行高度、最大轉彎角等主要搜索參數進行了多組數據仿真對比，分析了各個參數對低空突防航路規劃結果的影響關系，對于基于SAS算法進行飛行器航路規劃的改進和優化具有參考意義。

SAS算法；飛行器；低空突防；航路規劃

AbstractThe influence of SAS parameters on aircraft low altitude penetration route planning is complicated.Based on the simulation of aircraft low altitude penetration，the influence of the main searching parameters，such as the min searching step，the number of extended nodes，the weight of cost function，the max flight altitude，and the max turn angle are compared by several groups of simulation with different parameters.The relation between SAS parameters and route planning result is analyzed，which has some reference significance in aircraft low altitude penetration route planning improvement and optimization.

Key WordsSASalgorithm，aircraft，low altitude penetration，route planning

Class NumberTP39

1 引言

飛行器低空突防航路規劃屬于路徑尋優問題，目前較為多見的航路規劃算法研究主要有簡單幾何規劃方法、遺傳算法［1］、蟻群算法［2］、Voronoi圖［3］、A*［4］及其改進的 SAS（稀疏 A*）算法［5～7］、D*優化算法［8］，以及魚群算法［9］、粒子群優化［10］等多種方法。其中，SAS算法可證明能夠找到最優解，并且具有可解析的求解過程，因此研究和應用比較廣泛。

SAS算法的各個搜索參數對航路規劃結果的影響關系比較復雜，給實際的航路規劃實現帶來困難，因此，有必要對給各參數的影響規律進行分析。本文通過仿真實驗分析算法搜索所得航路的總代價、搜索時間以及儲存數據空間與所采用的搜索參數之間的關系。

2 算法描述

A*算法是一種啟發式搜索算法。通過設置啟發函數，然后通過迭代的方法選擇下一個滿足最小代價的航路點，進行航路擴展，從而得到一條最優航路。該算法通過設置啟發函數來尋找下一個節點進行擴展。啟發函數是從起始航路點至當前航路點的實際代價函數值和從當前航路點到目標點的估計代價函數值加權得到的。也就是說飛行器低空突防航路規劃的啟發函數由兩部分組成，一部分是飛行器已經飛行過的航路產生的代價也稱歷史代價，另一部分是飛行器將要飛行產生的代價也稱估計代價。啟發函數也稱代價函數。A*算法的總代價函數的形式如下

式中：f(x)是整個航路的代價；a、b分別是真實代價函數值和估計代價值的加權系數；g(x)、h(x)分別是從起始航路點到當前航路點的真是代價函數，以及從當前航路點到目標點的估計代價函數，由于三維低空突防航路規劃中希望飛行高度盡可能低，因此在代價函數中除了包含三維航程代價外，通常還包含航路各節點離地高度的最大值、平均值和方差的加權值。

在使用A*算法進行航路規劃時，總是選擇總代價值的航路節點進行擴展，從而保證從起點到目標點的真實代價達到最小，得到一條最優的航路。

SAS算法在進行搜索時，為了精簡搜索空間，縮短規劃時間，就需要把每一個航路點可能有的擴展空間劃分若干個子空間，只在每個子空間內找一個點進行可能的航路擴展。每個子空間的航路點不是隨意確定的，被選擇的子空間航路點是當前子空間中代價最小的點，然后從當前節點對選擇的子節點進行擴展。

3 三維擴展設計

三維航路規劃中，SAS算法在水平方向和垂直方向進行航路節點擴展，其擴展過程如圖1所示。

圖1 航路節點三維擴展示意圖

擴展航路點與當前航路點之間的距離是最小搜索步長；在進行每一步節點擴展時，垂直方向上的角度改變由飛行器的最大爬升/下滑角確定；水平方向上的角度改變由飛行器的最大轉彎角確定。這樣，形成了一個以當前節點為頂點的錐形擴展區域，再將該區域劃分成若干子區域，每個子區域選取所有可能擴展節點中總代價最小的作為SAS算法的一個擴展節點。

每一次進行擴展時都選擇當前所有待擴展節點中總代價最小的節點進行擴展，同時將該節點按照排序規則插入到已擴展節點的存儲結構中。直至算法完成。對于擴展得到的子節點，先進行約束條件判斷，僅保留其中滿足所有約束條件并且與現有待擴展節點不重復的節點。節點擴展及存儲的過程如圖2所示。

圖2 節點擴展及存儲

經過反復的節點選取和擴展后，當最終到達目標時，就可以沿著航路搜索樹逆向回溯至初始點，從而得到一條最優航路。

4 SAS算法仿真實驗系統

仿真系統中采用了柵格形式的地形數據，可以從外部標準文件中導入，也可模擬生成。如圖3所示。

圖3 仿真系統提供的地形數據

在仿真地形中，可按地形坐標設置初始點或目標點。采用前文所述SAS算法進行低空突防三維航路規劃。通過記錄算法搜索過程的時間和空間消耗情況，研究SAS算法主要參數對搜索結果和搜索過程的影響。單飛行器低空突防的仿真效果如下圖所示，包括航路規劃結果、主干擴展節點和航路高程剖面圖等。如圖4～圖6所示。

5 主要參數對算法搜索結果的影響

在模擬仿真地形中，設置初始點三維坐標為（30，40，20），目標點三維坐標為（160，140，10）。通過調整改變各個搜索參數，考察SAS算法搜索效果的影響因素。

圖4 航路規劃結果的三維視圖

圖5 航路二維視圖及主干擴展節點

圖6 航路高程剖面圖

默認設置為：每個父節點的子節點擴展在高度上分為上中下3層，每層擴展數目為3，實驗中僅改變每層的擴展數目，而不改變擴展層數，節點擴展方向取為當前節點在每一高度層的正前方和±30°三個方向；SAS算法代價函數的權重稀疏取為a=b=1，飛行器最大飛行高度設為40，最低飛行高度設為5。時間單位為秒，數據儲存空間單位為1個節點結構體所占用的字節數。

5.1 最小步長對SAS搜索的影響

最小步長L（以仿真地形網格為單位）是SAS算法中父節點到子節點的擴展距離。通過改變最小搜索步長L，對比實驗數據如表1所示。

表1 最小步長對SAS算法的影響

分析實驗結果可知，在其他參數值不變的情況下，步長增大時，算法運行時間和所占用的儲存空間有所減少。這實質上是在犧牲航路搜索精度的情況下，加快了算法收斂速度。工程應用時，可根據實際情況反復實驗對比選取。

5.2 擴展節點數對航路規劃的影響

稀疏A*算法中，擴展節點數是對當前父節點一次擴展所得到的子節點數目。最小步長L取為9，通過改變節點擴展數目，對比實驗數據如表2所示。

表2 擴展節點數對SAS算法的影響

分析實驗結果可知，擴展節點數增大，規劃結果更優化。因為稀疏A*算法在進行航路擴展時，是將前方的擴展空間分成等分的多個子區間，從每個子區間中找該區間的最優點作為可能的擴展點。每增加一個擴展節點，就會多一種優化選擇，遺漏優化航路點的可能性減小。

5.3 代價函數權重對航路規劃的影響

稀疏A*算法的代價函數由兩部分組成。一部分是待擴展節點的歷史航路代價，另一部分是待擴展節點到達目標點的估計剩余代價。權重值體現了歷史代價和估計剩余代價在代價函數中的比重。通過改變權重組合，對比實驗數據如表3所示。

表3 代價權重對SAS算法的影響

分析實驗結果可知，在本次實驗所用的地形條件下，增加歷史代價的權重，能夠得到更加優化的結果，但會消耗更多的計算時間和空間。實際上，權重值的改變并不是直接影響規劃結果，往往需要根據規劃問題所采用的具體地形分布情況，通過反復調整對比來確定適合某一地形環境的規劃問題的權重值。也就是說在不同的情況下有著不同的一組權重值使得當前規劃問題的結果更優化。

5.4 最大飛行高度航路規劃結果的影響

最大飛行高度是由于飛行器升限，以及為了某種戰術效果或提高飛行生存概率而設定的約束條件。通過最大飛行高度，對比實驗數據如表4所示。

分析實驗結果可知，最大飛行高度增高，算法運行的時間趨短，占用存儲空間趨少。這是因為，允許的飛行高度越高，飛行器必須規避的地形越少，從而需要更少的航路點和算法搜索時間，相當于減少了規劃問題的規模和難度。

表4 最大飛行高度對SAS算法的影響

5.5 最大轉彎角對航路規劃結果的影響

最大轉彎角限定了子節點偏離其父節點飛行方向的最大絕對值。通過改變最大轉彎角，對比實驗數據如表5所示。

表5 最大轉彎角對SAS算法的影響

分析實驗結果未見最大轉彎角對規劃結果的直接影響。原因是改變最大轉彎角的選取與規劃問題的地形分布，以及初始點、目標點相對態勢有關，而對算法總的搜索節點數、問題的規模和難度均沒有實質影響。

6 結語

本文針對SAS算法進行了飛行器低空突防三維航路規劃的仿真實驗，并對該算法的各個搜索參數對航路規劃結果的影響進行了分析，得出了各因素的影響規律。

實際的航路規劃問題可能是多種因素同時變化和相互影響的結果，后續將深入研究各種典型地形分布特征或者典型任務要求下，多個搜索參數協同變化對飛行器三維航路規劃的影響規律及其優化方法。

［1］席慶彪，李康，劉慧霞.振動遺傳算法在無人機三維航路規劃的算法研究［J］.火力與指揮控制，2014，39（10）：30-35.

XIQingbiao，LIKang，LIUHuixia.Research on UAV Path Planning Based on Vibrational Genetic Algorithm in 3D［J］.Fire Control&Command Control，2014，39（10）：30-35.

［2］程琪，荊濤，于志游.利用三次樣條改進蟻群算法的無人機航路規劃［J］.計算機測量與控制，2016，24（8）：272-274.

CHENG Qi，JING Tao，YU Zhiyou.UAV Path Planning Based on Ant Colony Optimization Improved by Cubic Spline［J］.Computer Measurement&Control，2016，24（8）：272-274.

［3］聶俊嵐，張慶杰，王艷芬.基于加權Voronoi圖的無人飛行器航跡規劃［J］.飛行力學，2015，33（4）：339-343.

NIE Junlan，ZHANG Qingjie，WANG Yanfen.UAV path planning based on weighted-Voronoi diagram［J］.Flight Dynamics，2015，33（4）：339-343.

［4］李太平，陳艷，袁大天.航路規劃的試飛評估技術初步研究［J］.電子測試，2016（12）：40-41.

LI Taiping，CHEN Yan，YUAN Datian.Preliminary study on flight test evaluation technology of route planning［J］.Electronic Test，2016（12）：40-41.

［5］焦衛東，程穎，柯然.基于SAS算法的起飛一發失效應急 路 徑 規 劃 方 法［J］.航 空 學 報 ，2016，37（10）：3140-3148.

JIAO WD，CHENG Y，KE R.A path planning method for EOSID based on SAS algorithm［J］.Acta Aeronautica et Astronautica Sinica，2016，37（10）：3140-3148.

［6］謝曉方，孫濤，歐陽中輝.反艦導彈航路規劃技術［M］.北京：國防工業出版社，2010.

XIE Xiaofang，SUN Tao，OUYANG Zhonghui.Anti-ship missile route planning technology［M］.Beijing：National Defence Industry Press，2010.

［7］譚雁英，胡淼，祝小平，等.基于人機合作策略下SAS算法的多無人機路徑再規劃［J］.西北工業大學學報，2014（5）：688-692.

TAN Yanying，HU Miao，ZHU Xiaoping，et al.Path Re?planning Approach for Multiple UAVs Based on SAS（Sparse A*Search）Algorithm under Human Automation Collaboration［J］.Journal of Northwestern Polytechnical University，2014（5）：688-692.

［8］吳劍，張東豪.基于改進D*算法的無人機航路規劃及光順［J］.航空科學技術，2013（6）：69-71.

WU Jian，ZHANG Donghao.UAV Route Planning and Smoothing Based on Improved D*Algorithm［J］.Aeronau?tical Science&Technology，2013（6）：69-71.

［9］沈華，陳金良，周志靖，等.無人機作戰對目標點的航跡規劃方法研究［J］.計算機仿真，2016，33（9）：73-76.

SHEN Hua，CHEN Jinliang，ZHOU Zhijing，et al.The Method Research for Target Point Path Planning for Target Point of UAV［J］.Computer Simulation，2016，33（9）：73-76.

［10］孫健，吳森堂.基于改進粒子群優化算法的巡航導彈航路規劃［J］.北京航空航天大學學報，2011，37（10）：1228-1232.

SUN Jian，WU Sentang.Route planning of cruise missile based on improved particle swarm algorithm［J］.Journal of Beijing University of Aeronautics and Astronautics.2011，37（10）：1228-1232.

3D Route Planning for Aircraft Low A ltitude Penetration Based on SASA lgorithm

SUN Tao1LIU Jiaqi2ZHANG Longjie1FAN Pengfei1ZHOU Tao2
（1.Department of Ordnance Science and Technology，Naval Aeronautical and Astronautical University，Yantai 264001）（2.No.2 Cadets’Brigade，Naval Aeronautical and Astronautical University，Yantai 264001）

TP39

10.3969/j.issn.1672-9722.2017.09.014

2017年4月5日，

2017年5月15日

中國博士后科學基金項目（編號：2013T60923）資助。

孫濤，男，博士，講師，研究方向：導彈航路規劃。