陳潔, 石鵬飛, 王琳

(西安飛行自動控制研究所 飛控部, 陜西 西安 710065)

?

基于DSAS算法的直升機貼地飛行在線航跡規(guī)劃

陳潔, 石鵬飛, 王琳

(西安飛行自動控制研究所 飛控部, 陜西 西安 710065)

摘要:通過改進優(yōu)化傳統(tǒng)A* 算法,利用動態(tài)稀疏A* 搜索(DSAS)算法在線設(shè)計了直升機貼地飛行軌跡。該算法采用逆向搜索方式規(guī)劃航跡,在遇到新生探測威脅時,只需局部調(diào)整受到影響的航跡,減少了重新規(guī)劃的范圍,提高了搜索效率。此外,在生成節(jié)點時考慮了直升機性能及飛行約束, 優(yōu)化了搜索范圍;并且根據(jù)影響貼地飛行航跡性能的各種因素,設(shè)計了航跡代價計算方法;利用層次分析法結(jié)合專家分析計算得到最優(yōu)代價權(quán)值。仿真結(jié)果表明,該方法在線設(shè)計的飛行軌跡能夠較全面地滿足避障、貼地功能,相比稀疏A* 搜索(SAS)算法節(jié)省了計算時間。

關(guān)鍵詞:貼地飛行; DSAS算法; 在線航跡規(guī)劃; A* 算法

0引言

隨著現(xiàn)代防空技術(shù)的不斷發(fā)展,非隱身飛行器難以從高、中空域突防,貼地飛行戰(zhàn)術(shù)成為發(fā)展的主要趨勢。直升機作為一種超低空火力平臺,可在30 m以下高度利用地形起伏及雜波對抗防御雷達,在雷達盲區(qū)內(nèi)貼地飛行,具有巨大優(yōu)勢[1]。

在貼地飛行實際任務(wù)中,由于規(guī)劃環(huán)境是動態(tài)變化的,預(yù)先未知威脅只有在直升機飛行到附近時才能探測識別到準確數(shù)據(jù),因此在線航跡規(guī)劃是直升機貼地飛行的關(guān)鍵技術(shù)之一[2]。目前在線航跡規(guī)劃算法主要有純數(shù)學算法及人工智能算法[3]。純數(shù)學算法包括動態(tài)規(guī)劃方法[4]、能量狀態(tài)法和梯度法等,但在多約束條件下,存在計算繁瑣、計算量較大和時間較長問題。人工智能方法包括A*搜索算法[5]、蟻群算法[6]、粒子群算法[7]和進化算法[8]等。這類算法具備較好的運算簡易性,相對于其他方法容易達到實時性要求,但為保證最優(yōu)性和智能性,還需加以改進。

本文針對直升機貼地飛行階段,改進了Szczerba等[9]提出的稀疏A*搜索 (Sparse A*Search, SAS) 算法,采用動態(tài)稀疏A*搜索(Dynamic Sparse A*Search, DSAS)算法在三維空間在線設(shè)計生成了可行的飛行航跡,通過改進搜索機制,結(jié)合飛行約束條件,對代價函數(shù)進行加權(quán)選取,達到了縮小搜索空間、提高搜索效率的作用。

1算法介紹

1.1傳統(tǒng)A*算法

A*搜索算法進行路徑規(guī)劃時,將規(guī)劃環(huán)境表示為網(wǎng)格形式。首先對當前位置的每個可達網(wǎng)格單元計算代價,然后選擇最低代價的網(wǎng)格單元加入搜索空間。加入搜索空間的新網(wǎng)格單元又被用來產(chǎn)生更多的可能路徑。A*算法采用的代價函數(shù)為:

(1)

式中:g(x)為從起始節(jié)點START到當前節(jié)點x的真實航跡代價;h(x)為啟發(fā)函數(shù),表示從當前節(jié)點x到目標節(jié)點GOAL航跡代價的估值。

1.2DSAS算法

DSAS在線規(guī)劃算法是對傳統(tǒng)A*搜索算法的改進。原理如下:當遇到新探測威脅時,采用逆向搜索實時地重新規(guī)劃航跡,提高搜索效率。

DSAS算法基于A*算法的節(jié)點擴展方式,改進搜索方向,將目標節(jié)點作為根節(jié)點,從目標位置向直升機當前位置逆向搜索。通過這種改進,當環(huán)境威脅發(fā)生變化時,只需局部調(diào)整搜索圖中受到影響的路徑,可大大減少計算量。

DSAS算法搜索原理如圖1所示。當直升機探測到當前航跡前方存在新的威脅時,DSAS算法將威脅覆蓋區(qū)域的航跡節(jié)點及其所有后代節(jié)點(小實心點)刪除,并將其父節(jié)點(空心點)重新插入OPEN表,然后計算擴展節(jié)點的代價值,繼續(xù)其搜索過程,直到獲得最優(yōu)的航跡。

圖1　DSAS算法搜索原理Fig.1　Searching principles of DSAS algorithm

2直升機貼地飛行軌跡設(shè)計

2.1規(guī)劃空間

本文所研究的直升機貼地飛行階段的在線航跡規(guī)劃空間是一個三維網(wǎng)格空間。采用啟發(fā)式搜索算法確定規(guī)劃空間時,搜索當前節(jié)點的擴展鄰域范圍越大,生成的航跡精度越高。然而,若擴展所有鄰域中的網(wǎng)格單元,收斂到最優(yōu)解則需要大量的時間和內(nèi)存,并隨規(guī)劃區(qū)域的增大呈指數(shù)增長。因此,本文進行三維航跡搜索擴展節(jié)點時,把飛行約束條件結(jié)合到搜索算法中去,可以有效優(yōu)化傳統(tǒng)A*算法的搜索效率。

2.2飛行約束的轉(zhuǎn)化及航跡節(jié)點的生成

直升機貼地飛行航跡規(guī)劃中考慮的基本約束主要包括:最小航跡段長度l、最高/最低飛行高度hmax/min、最大拐彎角φ以及最大爬升/下滑角θ。

最小航跡段長度指直升機在開始改變飛行姿態(tài)前必須保持直飛的最短距離。這一限制主要取決于直升機的機動能力與直升機的導(dǎo)航要求。合適的最小航跡段長度應(yīng)大于飛機的最小轉(zhuǎn)彎半徑。

限制最高飛行高度的目的是防止直升機被敵方雷達探測識別,達到貼地隱蔽飛行的目的;限制最低飛行高度的目的是防止直升機意外撞地。

最大拐彎角限制了生成航跡只能在小于等于最大拐彎角范圍內(nèi)轉(zhuǎn)彎。拐彎角計算如下:

(2)

最大爬升/下滑角限制了生成航跡只能在小于等于最大爬升/下滑角范圍內(nèi)爬升/俯沖。爬升/下滑角計算如下:

(3)

假設(shè)給定了直升機的當前節(jié)點以及最小航跡段長度、最高/最低飛行高度、最大拐彎角和最大爬升/下滑角,那么從當前節(jié)點生成的子節(jié)點如圖2所示,僅有有限數(shù)量的位置單元。這些單元被限制在一個由四棱錐和球面所包圍的區(qū)域內(nèi)。四棱錐在頂點x處縱向的張角為2θ,在水平方向的張角為2φ,球面半徑為l。

圖2　當前節(jié)點的可行搜索范圍Fig.2　Available searching space of present pitch point

本文基于以上分析,考慮直升機的上述制約因素,并進行適當簡化,得到搜索空間如圖3所示。圖中,每個網(wǎng)格取作一個正方體,水平剖面滿足最大拐彎角限制,垂直剖面滿足最大爬升/下滑角限制,最小航跡段長度為其邊長,假設(shè)當前節(jié)點為x,其三維空間滿足飛行約束的可行子節(jié)點的點集為S={S1,S2,…,S21}。

圖3　DSAS算法三維空間搜索示意圖Fig.3　3-D searching diagram of DSAS algorithm

2.3代價函數(shù)的選取

代價函數(shù)的選取直接影響到規(guī)劃航跡的性能。直升機貼地飛行過程中,為了隱蔽飛行,規(guī)劃航跡的高度應(yīng)在安全范圍內(nèi)盡可能低;考慮到直升機的機動性能,規(guī)劃航跡的拐彎次數(shù)、拐彎半徑、俯仰角應(yīng)盡可能小;考慮到直升機的飛行安全性,飛行時間應(yīng)盡可能短,故規(guī)劃航跡的總長應(yīng)盡可能短,距威脅源的距離應(yīng)盡可能遠。

根據(jù)上述影響飛行器航跡性能的各種因素,本文采用如下航跡代價計算方法:

(4)

式中:ω1,ω2,ω3,ω4為權(quán)系數(shù);hi為直升機在節(jié)點i的海拔高度,通過高度懲罰降低被敵方雷達發(fā)現(xiàn)的概率;li為第i段航跡的長度,單航跡段長度越長,則機動角度越大,通過單航跡段長度懲罰降低航跡的機動程度;di為節(jié)點i到目標點的距離,即懲罰航跡總長度;fTAi為節(jié)點i處的威脅指數(shù),懲罰威脅影響,計算方法如下:

(5)

式中:c為雷達或威脅常數(shù);r為路徑點到威脅中心的距離。

2.4代價函數(shù)權(quán)系數(shù)的確定

權(quán)系數(shù)ω1,ω2,ω3,ω4分別表示航跡高度、單航跡段長度、距目標點距離以及威脅影響對航跡綜合性能的影響程度。權(quán)系數(shù)的取值直接影響規(guī)劃航跡的性能,本文采用層次分析法[10]確定權(quán)系數(shù)向量ω=[ω1,ω2,ω3,ω4]T。

首先由業(yè)內(nèi)專家結(jié)合貼地飛行目的、環(huán)境、威脅等情況,采用9標度法確定指標i與指標j對航跡代價的影響程度比aij,有aij=ωi/ωj,且有aij=1/aji>0。產(chǎn)生判斷矩陣:

(6)

各參數(shù)如表1所示。

表1　比較判斷矩陣

經(jīng)驗證:

(7)

(8)

矩陣A具有完全一致性。歸一化后的權(quán)系數(shù)向量為ω=[0.6,0.1,0.1,0.2]T

3仿真與結(jié)果分析

下面對DSAS算法進行仿真驗證,運行環(huán)境為Windows XP,編程環(huán)境為MATLAB。仿真采用的相關(guān)參數(shù)取值如下:代價函數(shù)權(quán)系數(shù)ω1=0.6,ω2=0.1,ω3=0.1,ω4=0.2;節(jié)點擴展時,選擇3×7=21節(jié)點擴展;最小航跡段長度200 m;最低飛行高度5 m,最高飛行高度30 m,最大拐彎角70°,最大爬升/俯沖角45°。

圖4和圖5為根據(jù)傳感器探測到的預(yù)先未知威脅采用DSAS在線規(guī)劃算法所規(guī)劃的航跡。圖中:實線區(qū)域、短虛線圓形區(qū)域分別表示預(yù)先已知的禁飛區(qū)威脅和雷達威脅;長虛線圓形區(qū)域表示預(yù)先未知的地形威脅;虛線表示初始規(guī)劃航跡;實線表示在線DSAS規(guī)劃的路徑。仿真結(jié)果表明,直升機在貼地飛行過程中,沿著初始最優(yōu)航跡飛行到START點時,探測到新生威脅并更新威脅數(shù)據(jù),設(shè)傳感器為理想傳感器,新探測威脅的中心坐標為(660, 880, 8.066),新威脅覆蓋節(jié)點的父節(jié)點為P,將P點重新插入OPEN表,從P點向START點繼續(xù)規(guī)劃得到在線實時規(guī)劃的新航跡,如圖4和圖5中的實線所示。

圖4　在線DSAS規(guī)劃的2D航跡圖Fig.4　2D chart of online DSAS planned path

圖5　在線DSAS規(guī)劃的3D航跡圖Fig.5　3D chart of online DSAS planned path

在相同仿真條件下,采用SAS算法進行在線重規(guī)劃的示意圖如圖6和圖7所示。

圖6　在線SAS規(guī)劃的2D航跡圖Fig.6　2D chart of online SAS planned path

圖7　在線SAS規(guī)劃的3D航跡圖Fig.7　Online SAS planned path 3D chart

表2給出了兩種方法仿真結(jié)果的比較。從表中可以看出,相比SAS算法,利用DSAS算法規(guī)劃路徑節(jié)省規(guī)劃時間56.03%,減少規(guī)劃節(jié)點13.3%,減少搜索節(jié)點56.17%,航跡總代價減少51.94%。

表2　DSAS與SAS仿真結(jié)果對比

4結(jié)束語

本文將DSAS算法應(yīng)用到直升機貼地飛行軌跡規(guī)劃設(shè)計中,通過改進搜索方向,將飛行約束與三維航跡搜索節(jié)點結(jié)合考慮,確定代價函數(shù)的選取,利用層次分析法確定代價函數(shù)的權(quán)值,有效減小了搜索空間,縮短了搜索時間。從仿真結(jié)果可以看出,DSAS算法規(guī)劃出的航跡能夠保證直升機有效避開雷達、氣象、地形等障礙威脅,并盡可能地沿著高度低、航跡短的航跡飛行,相比SAS算法計算時間短,實時性更好。

參考文獻：

[1]楊松山.直升機貼地飛行時人-機響應(yīng)特性研究[J].飛行力學,1992,10(2):36-44.

[2]丁明躍,鄭昌文,周成平,等.無人飛行器航跡規(guī)劃[M].北京:電子工業(yè)出版社,2009.

[3]胡中華,趙敏.無人飛行器在線航跡規(guī)劃技術(shù)研究[J].航天電子對抗,2010(4):11-14.

[4]唐振民,趙春霞,楊靜宇,等.基于動態(tài)規(guī)劃思想的多機器人路徑規(guī)劃[J].南京理工大學學報,2003,27(5):610-615.

[5]周成平,陳前洋,秦筱械.基于稀疏 A*算法的三維航跡并行規(guī)劃算法[J].華中科技大學學報(自然科學版),2005,33(5):42-45.

[6]張元良,楊巍巍,劉青,等.蟻群算法在路徑規(guī)劃中的應(yīng)用[J].數(shù)字技術(shù)與應(yīng)用,2013(5):159-160.

[7]陳冬.基于粒子群優(yōu)化算法的無人機航跡規(guī)劃[D].西安:西北工業(yè)大學,2007.

[8]Zhao L,Murthy V R.Trajectory planning with collision avoidance for autonomous helicopter by evolutionary methods path [J].AIAA Journal,2006,10(6):251-264.

[9]Szczerba R J,Galkowski P,Glicktein I S,et al.Robust algorithm for real-time route planning[J].Aerospace and Electronic Systems,IEEE Transactions on,2000,36(3):869-878.

[10]許樹柏.實用決策方法:層次分析法原理[M].天津:天津大學出版社,1988.

(編輯：崔立峰)

Online path planning based on DSAS for helicopter NOE fight

CHEN Jie, SHI Peng-fei, WANG Lin

(Department of Flight Control, Xi’an Flight Automatic Control Research Institute,Xi’an 710065, China)

Abstract:In this paper, dynamic sparse A* search (DSAS) algorithm was used to design helicopter nap-of-earth (NOE) flight path online. DSAS algorithm used backward searching method to plan path, which could reduce re-planning space and improve searching efficiency. Besides, this paper took both helicopter performance and flight restraints into consideration when generating pitch points, which reduced the searching space. The paper also designed the path cost calculating method, and Analytic Hierarchy Process (AHP) was used to figure out the optimal weight value. The simulation results showed that DSAS path planning algorithm could meet the requirements of both obstacle avoidance and NOE flight, and showed significant enhancement over SAS.

Key words:NOE fight; DSAS algorithm; online path planning; A* algorithm

中圖分類號：V249.3

文獻標識碼：A

文章編號：1002-0853(2016)02-0086-04

作者簡介:陳潔(1991-)，女，陜西渭南人，碩士研究生，研究方向為先進飛行器控制技術(shù)。

收稿日期:2015-04-23;

修訂日期:2015-08-06; 網(wǎng)絡(luò)出版時間:2015-09-08 13:57