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

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

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

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

（1.海軍航空工程學(xué)院兵器科學(xué)與技術(shù)系 煙臺(tái) 264001）（2.海軍航空工程學(xué)院學(xué)員二旅 煙臺(tái) 264001）

SAS算法的各個(gè)主要搜索參數(shù)對(duì)飛行器航路規(guī)劃的結(jié)果影響關(guān)系復(fù)雜，論文在對(duì)低空突防三維航路規(guī)劃進(jìn)行仿真實(shí)現(xiàn)的基礎(chǔ)上，對(duì)最小步長(zhǎng)搜索步長(zhǎng)、擴(kuò)展節(jié)點(diǎn)數(shù)、代價(jià)函數(shù)權(quán)重、最大飛行高度、最大轉(zhuǎn)彎角等主要搜索參數(shù)進(jìn)行了多組數(shù)據(jù)仿真對(duì)比，分析了各個(gè)參數(shù)對(duì)低空突防航路規(guī)劃結(jié)果的影響關(guān)系，對(duì)于基于SAS算法進(jìn)行飛行器航路規(guī)劃的改進(jìn)和優(yōu)化具有參考意義。

SAS算法；飛行器；低空突防；航路規(guī)劃

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 引言

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

SAS算法的各個(gè)搜索參數(shù)對(duì)航路規(guī)劃結(jié)果的影響關(guān)系比較復(fù)雜，給實(shí)際的航路規(guī)劃實(shí)現(xiàn)帶來(lái)困難，因此，有必要對(duì)給各參數(shù)的影響規(guī)律進(jìn)行分析。本文通過(guò)仿真實(shí)驗(yàn)分析算法搜索所得航路的總代價(jià)、搜索時(shí)間以及儲(chǔ)存數(shù)據(jù)空間與所采用的搜索參數(shù)之間的關(guān)系。

2 算法描述

A*算法是一種啟發(fā)式搜索算法。通過(guò)設(shè)置啟發(fā)函數(shù)，然后通過(guò)迭代的方法選擇下一個(gè)滿(mǎn)足最小代價(jià)的航路點(diǎn)，進(jìn)行航路擴(kuò)展，從而得到一條最優(yōu)航路。該算法通過(guò)設(shè)置啟發(fā)函數(shù)來(lái)尋找下一個(gè)節(jié)點(diǎn)進(jìn)行擴(kuò)展。啟發(fā)函數(shù)是從起始航路點(diǎn)至當(dāng)前航路點(diǎn)的實(shí)際代價(jià)函數(shù)值和從當(dāng)前航路點(diǎn)到目標(biāo)點(diǎn)的估計(jì)代價(jià)函數(shù)值加權(quán)得到的。也就是說(shuō)飛行器低空突防航路規(guī)劃的啟發(fā)函數(shù)由兩部分組成，一部分是飛行器已經(jīng)飛行過(guò)的航路產(chǎn)生的代價(jià)也稱(chēng)歷史代價(jià)，另一部分是飛行器將要飛行產(chǎn)生的代價(jià)也稱(chēng)估計(jì)代價(jià)。啟發(fā)函數(shù)也稱(chēng)代價(jià)函數(shù)。A*算法的總代價(jià)函數(shù)的形式如下

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

在使用A*算法進(jìn)行航路規(guī)劃時(shí)，總是選擇總代價(jià)值的航路節(jié)點(diǎn)進(jìn)行擴(kuò)展，從而保證從起點(diǎn)到目標(biāo)點(diǎn)的真實(shí)代價(jià)達(dá)到最小，得到一條最優(yōu)的航路。

SAS算法在進(jìn)行搜索時(shí)，為了精簡(jiǎn)搜索空間，縮短規(guī)劃時(shí)間，就需要把每一個(gè)航路點(diǎn)可能有的擴(kuò)展空間劃分若干個(gè)子空間，只在每個(gè)子空間內(nèi)找一個(gè)點(diǎn)進(jìn)行可能的航路擴(kuò)展。每個(gè)子空間的航路點(diǎn)不是隨意確定的，被選擇的子空間航路點(diǎn)是當(dāng)前子空間中代價(jià)最小的點(diǎn)，然后從當(dāng)前節(jié)點(diǎn)對(duì)選擇的子節(jié)點(diǎn)進(jìn)行擴(kuò)展。

3 三維擴(kuò)展設(shè)計(jì)

三維航路規(guī)劃中，SAS算法在水平方向和垂直方向進(jìn)行航路節(jié)點(diǎn)擴(kuò)展，其擴(kuò)展過(guò)程如圖1所示。

圖1 航路節(jié)點(diǎn)三維擴(kuò)展示意圖

擴(kuò)展航路點(diǎn)與當(dāng)前航路點(diǎn)之間的距離是最小搜索步長(zhǎng)；在進(jìn)行每一步節(jié)點(diǎn)擴(kuò)展時(shí)，垂直方向上的角度改變由飛行器的最大爬升/下滑角確定；水平方向上的角度改變由飛行器的最大轉(zhuǎn)彎角確定。這樣，形成了一個(gè)以當(dāng)前節(jié)點(diǎn)為頂點(diǎn)的錐形擴(kuò)展區(qū)域，再將該區(qū)域劃分成若干子區(qū)域，每個(gè)子區(qū)域選取所有可能擴(kuò)展節(jié)點(diǎn)中總代價(jià)最小的作為SAS算法的一個(gè)擴(kuò)展節(jié)點(diǎn)。

每一次進(jìn)行擴(kuò)展時(shí)都選擇當(dāng)前所有待擴(kuò)展節(jié)點(diǎn)中總代價(jià)最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展，同時(shí)將該節(jié)點(diǎn)按照排序規(guī)則插入到已擴(kuò)展節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)中。直至算法完成。對(duì)于擴(kuò)展得到的子節(jié)點(diǎn)，先進(jìn)行約束條件判斷，僅保留其中滿(mǎn)足所有約束條件并且與現(xiàn)有待擴(kuò)展節(jié)點(diǎn)不重復(fù)的節(jié)點(diǎn)。節(jié)點(diǎn)擴(kuò)展及存儲(chǔ)的過(guò)程如圖2所示。

圖2 節(jié)點(diǎn)擴(kuò)展及存儲(chǔ)

經(jīng)過(guò)反復(fù)的節(jié)點(diǎn)選取和擴(kuò)展后，當(dāng)最終到達(dá)目標(biāo)時(shí)，就可以沿著航路搜索樹(shù)逆向回溯至初始點(diǎn)，從而得到一條最優(yōu)航路。

4 SAS算法仿真實(shí)驗(yàn)系統(tǒng)

仿真系統(tǒng)中采用了柵格形式的地形數(shù)據(jù)，可以從外部標(biāo)準(zhǔn)文件中導(dǎo)入，也可模擬生成。如圖3所示。

圖3 仿真系統(tǒng)提供的地形數(shù)據(jù)

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

5 主要參數(shù)對(duì)算法搜索結(jié)果的影響

在模擬仿真地形中，設(shè)置初始點(diǎn)三維坐標(biāo)為（30，40，20），目標(biāo)點(diǎn)三維坐標(biāo)為（160，140，10）。通過(guò)調(diào)整改變各個(gè)搜索參數(shù)，考察SAS算法搜索效果的影響因素。

圖4 航路規(guī)劃結(jié)果的三維視圖

圖5 航路二維視圖及主干擴(kuò)展節(jié)點(diǎn)

圖6 航路高程剖面圖

默認(rèn)設(shè)置為：每個(gè)父節(jié)點(diǎn)的子節(jié)點(diǎn)擴(kuò)展在高度上分為上中下3層，每層擴(kuò)展數(shù)目為3，實(shí)驗(yàn)中僅改變每層的擴(kuò)展數(shù)目，而不改變擴(kuò)展層數(shù)，節(jié)點(diǎn)擴(kuò)展方向取為當(dāng)前節(jié)點(diǎn)在每一高度層的正前方和±30°三個(gè)方向；SAS算法代價(jià)函數(shù)的權(quán)重稀疏取為a=b=1，飛行器最大飛行高度設(shè)為40，最低飛行高度設(shè)為5。時(shí)間單位為秒，數(shù)據(jù)儲(chǔ)存空間單位為1個(gè)節(jié)點(diǎn)結(jié)構(gòu)體所占用的字節(jié)數(shù)。

5.1 最小步長(zhǎng)對(duì)SAS搜索的影響

最小步長(zhǎng)L（以仿真地形網(wǎng)格為單位）是SAS算法中父節(jié)點(diǎn)到子節(jié)點(diǎn)的擴(kuò)展距離。通過(guò)改變最小搜索步長(zhǎng)L，對(duì)比實(shí)驗(yàn)數(shù)據(jù)如表1所示。

表1 最小步長(zhǎng)對(duì)SAS算法的影響

分析實(shí)驗(yàn)結(jié)果可知，在其他參數(shù)值不變的情況下，步長(zhǎng)增大時(shí)，算法運(yùn)行時(shí)間和所占用的儲(chǔ)存空間有所減少。這實(shí)質(zhì)上是在犧牲航路搜索精度的情況下，加快了算法收斂速度。工程應(yīng)用時(shí)，可根據(jù)實(shí)際情況反復(fù)實(shí)驗(yàn)對(duì)比選取。

5.2 擴(kuò)展節(jié)點(diǎn)數(shù)對(duì)航路規(guī)劃的影響

稀疏A*算法中，擴(kuò)展節(jié)點(diǎn)數(shù)是對(duì)當(dāng)前父節(jié)點(diǎn)一次擴(kuò)展所得到的子節(jié)點(diǎn)數(shù)目。最小步長(zhǎng)L取為9，通過(guò)改變節(jié)點(diǎn)擴(kuò)展數(shù)目，對(duì)比實(shí)驗(yàn)數(shù)據(jù)如表2所示。

表2 擴(kuò)展節(jié)點(diǎn)數(shù)對(duì)SAS算法的影響

分析實(shí)驗(yàn)結(jié)果可知，擴(kuò)展節(jié)點(diǎn)數(shù)增大，規(guī)劃結(jié)果更優(yōu)化。因?yàn)橄∈鐰*算法在進(jìn)行航路擴(kuò)展時(shí)，是將前方的擴(kuò)展空間分成等分的多個(gè)子區(qū)間，從每個(gè)子區(qū)間中找該區(qū)間的最優(yōu)點(diǎn)作為可能的擴(kuò)展點(diǎn)。每增加一個(gè)擴(kuò)展節(jié)點(diǎn)，就會(huì)多一種優(yōu)化選擇，遺漏優(yōu)化航路點(diǎn)的可能性減小。

5.3 代價(jià)函數(shù)權(quán)重對(duì)航路規(guī)劃的影響

稀疏A*算法的代價(jià)函數(shù)由兩部分組成。一部分是待擴(kuò)展節(jié)點(diǎn)的歷史航路代價(jià)，另一部分是待擴(kuò)展節(jié)點(diǎn)到達(dá)目標(biāo)點(diǎn)的估計(jì)剩余代價(jià)。權(quán)重值體現(xiàn)了歷史代價(jià)和估計(jì)剩余代價(jià)在代價(jià)函數(shù)中的比重。通過(guò)改變權(quán)重組合，對(duì)比實(shí)驗(yàn)數(shù)據(jù)如表3所示。

表3 代價(jià)權(quán)重對(duì)SAS算法的影響

分析實(shí)驗(yàn)結(jié)果可知，在本次實(shí)驗(yàn)所用的地形條件下，增加歷史代價(jià)的權(quán)重，能夠得到更加優(yōu)化的結(jié)果，但會(huì)消耗更多的計(jì)算時(shí)間和空間。實(shí)際上，權(quán)重值的改變并不是直接影響規(guī)劃結(jié)果，往往需要根據(jù)規(guī)劃問(wèn)題所采用的具體地形分布情況，通過(guò)反復(fù)調(diào)整對(duì)比來(lái)確定適合某一地形環(huán)境的規(guī)劃問(wèn)題的權(quán)重值。也就是說(shuō)在不同的情況下有著不同的一組權(quán)重值使得當(dāng)前規(guī)劃問(wèn)題的結(jié)果更優(yōu)化。

5.4 最大飛行高度航路規(guī)劃結(jié)果的影響

最大飛行高度是由于飛行器升限，以及為了某種戰(zhàn)術(shù)效果或提高飛行生存概率而設(shè)定的約束條件。通過(guò)最大飛行高度，對(duì)比實(shí)驗(yàn)數(shù)據(jù)如表4所示。

分析實(shí)驗(yàn)結(jié)果可知，最大飛行高度增高，算法運(yùn)行的時(shí)間趨短，占用存儲(chǔ)空間趨少。這是因?yàn)?，允許的飛行高度越高，飛行器必須規(guī)避的地形越少，從而需要更少的航路點(diǎn)和算法搜索時(shí)間，相當(dāng)于減少了規(guī)劃問(wèn)題的規(guī)模和難度。

表4 最大飛行高度對(duì)SAS算法的影響

5.5 最大轉(zhuǎn)彎角對(duì)航路規(guī)劃結(jié)果的影響

最大轉(zhuǎn)彎角限定了子節(jié)點(diǎn)偏離其父節(jié)點(diǎn)飛行方向的最大絕對(duì)值。通過(guò)改變最大轉(zhuǎn)彎角，對(duì)比實(shí)驗(yàn)數(shù)據(jù)如表5所示。

表5 最大轉(zhuǎn)彎角對(duì)SAS算法的影響

分析實(shí)驗(yàn)結(jié)果未見(jiàn)最大轉(zhuǎn)彎角對(duì)規(guī)劃結(jié)果的直接影響。原因是改變最大轉(zhuǎn)彎角的選取與規(guī)劃問(wèn)題的地形分布，以及初始點(diǎn)、目標(biāo)點(diǎn)相對(duì)態(tài)勢(shì)有關(guān)，而對(duì)算法總的搜索節(jié)點(diǎn)數(shù)、問(wèn)題的規(guī)模和難度均沒(méi)有實(shí)質(zhì)影響。

6 結(jié)語(yǔ)

本文針對(duì)SAS算法進(jìn)行了飛行器低空突防三維航路規(guī)劃的仿真實(shí)驗(yàn)，并對(duì)該算法的各個(gè)搜索參數(shù)對(duì)航路規(guī)劃結(jié)果的影響進(jìn)行了分析，得出了各因素的影響規(guī)律。

實(shí)際的航路規(guī)劃問(wèn)題可能是多種因素同時(shí)變化和相互影響的結(jié)果，后續(xù)將深入研究各種典型地形分布特征或者典型任務(wù)要求下，多個(gè)搜索參數(shù)協(xié)同變化對(duì)飛行器三維航路規(guī)劃的影響規(guī)律及其優(yōu)化方法。

［1］席慶彪，李康，劉慧霞.振動(dòng)遺傳算法在無(wú)人機(jī)三維航路規(guī)劃的算法研究［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ìn)蟻群算法的無(wú)人機(jī)航路規(guī)劃［J］.計(jì)算機(jī)測(cè)量與控制，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］聶俊嵐，張慶杰，王艷芬.基于加權(quán)Voronoi圖的無(wú)人飛行器航跡規(guī)劃［J］.飛行力學(xué)，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］李太平，陳艷，袁大天.航路規(guī)劃的試飛評(píng)估技術(shù)初步研究［J］.電子測(cè)試，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］焦衛(wèi)東，程穎，柯然.基于SAS算法的起飛一發(fā)失效應(yīng)急 路 徑 規(guī) 劃 方 法［J］.航 空 學(xué) 報(bào) ，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］謝曉方，孫濤，歐陽(yáng)中輝.反艦導(dǎo)彈航路規(guī)劃技術(shù)［M］.北京：國(guó)防工業(yè)出版社，2010.

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

［7］譚雁英，胡淼，祝小平，等.基于人機(jī)合作策略下SAS算法的多無(wú)人機(jī)路徑再規(guī)劃［J］.西北工業(yè)大學(xué)學(xué)報(bào)，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］吳劍，張東豪.基于改進(jìn)D*算法的無(wú)人機(jī)航路規(guī)劃及光順［J］.航空科學(xué)技術(shù)，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］沈華，陳金良，周志靖，等.無(wú)人機(jī)作戰(zhàn)對(duì)目標(biāo)點(diǎn)的航跡規(guī)劃方法研究［J］.計(jì)算機(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ìn)粒子群優(yōu)化算法的巡航導(dǎo)彈航路規(guī)劃［J］.北京航空航天大學(xué)學(xué)報(bào)，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日

中國(guó)博士后科學(xué)基金項(xiàng)目（編號(hào)：2013T60923）資助。

孫濤，男，博士，講師，研究方向：導(dǎo)彈航路規(guī)劃。