陳潔, 石鵬飛, 王琳

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

?

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

陳潔, 石鵬飛, 王琳

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

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

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

0引言

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

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

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

1算法介紹

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

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

(1)

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

1.2DSAS算法

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

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

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

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

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

2.1規(guī)劃空間

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

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

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

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

限制最高飛行高度的目的是防止直升機(jī)被敵方雷達(dá)探測(cè)識(shí)別,達(dá)到貼地隱蔽飛行的目的;限制最低飛行高度的目的是防止直升機(jī)意外撞地。

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

(2)

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

(3)

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

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

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

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

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

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

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

(4)

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

(5)

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

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

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

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

(6)

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

表1　比較判斷矩陣

經(jīng)驗(yàn)證:

(7)

(8)

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

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

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

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

圖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算法進(jìn)行在線重規(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ī)劃時(shí)間56.03%,減少規(guī)劃節(jié)點(diǎn)13.3%,減少搜索節(jié)點(diǎn)56.17%,航跡總代價(jià)減少51.94%。

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

4結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

[7]陳冬.基于粒子群優(yōu)化算法的無(wú)人機(jī)航跡規(guī)劃[D].西安:西北工業(yè)大學(xué),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]許樹(shù)柏.實(shí)用決策方法:層次分析法原理[M].天津:天津大學(xué)出版社,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

中圖分類(lèi)號(hào)：V249.3

文獻(xiàn)標(biāo)識(shí)碼：A

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

作者簡(jiǎn)介:陳潔(1991-)，女，陜西渭南人，碩士研究生，研究方向?yàn)橄冗M(jìn)飛行器控制技術(shù)。

收稿日期:2015-04-23;

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