李時(shí)東，艾 青，劉 嵩

(湖北民族學(xué)院 信息工程學(xué)院,湖北 恩施 445000)

無人機(jī)航跡規(guī)劃是為了完成特定的飛行任務(wù)，在綜合考慮飛行器的機(jī)動(dòng)性能約束、飛行環(huán)境、油耗因素等一系列特定約束條件的基礎(chǔ)上，自動(dòng)規(guī)劃從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)航跡或滿足一定要求的航跡.無人機(jī)的種類繁多[1]，其中固定翼無人機(jī)由于約束眾多，其航跡規(guī)劃問題更為復(fù)雜.各種無人機(jī)航跡規(guī)劃算法都不可避免要在巨大的規(guī)劃空間中進(jìn)行搜索，規(guī)劃過程相當(dāng)耗時(shí)，航跡規(guī)劃精度與航跡規(guī)劃時(shí)間往往是一對(duì)突出的矛盾，在保證航跡規(guī)劃質(zhì)量的情況下，如何提高航跡規(guī)劃的速度以縮短規(guī)劃時(shí)間是一個(gè)急需解決的問題.

對(duì)航跡規(guī)劃算法的研究始于任務(wù)規(guī)劃系統(tǒng)的研制，近三十年來積累了豐碩的成果，廣大研究者提出的規(guī)劃算法可分為三類：①軌跡優(yōu)化類的方法基于最優(yōu)控制理論，通過確定動(dòng)態(tài)模型中的狀態(tài)變量和控制變量, 以達(dá)到代價(jià)函數(shù)最優(yōu)，典型算法有最速下降法、動(dòng)態(tài)規(guī)劃法、非線性規(guī)劃法、最優(yōu)控制法和奇異攝動(dòng)法等；②基于概略圖和單元分解的確定性搜索法通過將規(guī)劃空間表示成由一維線段構(gòu)成的網(wǎng)絡(luò)圖，或者將規(guī)劃空間分解成簡單網(wǎng)格單元，結(jié)合搜索算法尋找圖或網(wǎng)格中的最優(yōu)路徑，典型搜索算法如A*搜索、Dijkstra搜索等，構(gòu)圖或分解的方法很多，如Voronoi圖，Skeleton圖等，其中隨機(jī)路標(biāo)圖(PRM)和隨機(jī)搜索樹(RRT)更是得到廣泛的應(yīng)用；③基于模仿的方法借助仿生學(xué)或者物理學(xué)的概念對(duì)航跡規(guī)劃問題進(jìn)行轉(zhuǎn)化，然后求解，被廣泛研究的有遺傳算法(GA)、粒子群優(yōu)化(PSO)、神經(jīng)網(wǎng)絡(luò)(NN)、模擬退火(SA)、蟻群算法(AC)、人工免疫算法(AI)、人工勢(shì)場(chǎng)法(APF)、水平集方法(LS)、人工蜂群算法(ABA)等.然而現(xiàn)有算法大多因?yàn)橐?guī)劃速度不夠理想而難以實(shí)用，尤其是在無人機(jī)的三維航跡規(guī)劃應(yīng)用中，快速高效的航跡規(guī)劃算法意義重大.本文采用二維平面規(guī)劃結(jié)合高度規(guī)劃的策略實(shí)現(xiàn)三維航跡規(guī)劃，二維規(guī)劃過程采用水平集方法，確保所得航跡具有良好的地形回避特性，高度規(guī)劃采用稀疏A*實(shí)現(xiàn)快速性，實(shí)驗(yàn)表明，該方法整體規(guī)劃速度快，所得到的三維航跡具有良好的避障能力和地形跟隨能力.

1 航跡規(guī)劃建模

1.1 問題描述

航跡規(guī)劃問題本質(zhì)上是一個(gè)多約束條件下的極值求解問題，定義距離函數(shù)：u:R2→R+，則航跡可通過求下列問題的最小值得到.

(1)

其中:xs和xg分別代表起始點(diǎn)和目標(biāo)點(diǎn)的位形，ρ(τ)為某種距離測(cè)度，τ是測(cè)度的弧長參量.文獻(xiàn)證明[2]該極小值問題與求解Eikonal方程(2)等效.

|u|=c

(2)

其中正定代價(jià)函數(shù)c與距離測(cè)度ρ(τ)之間的關(guān)系用式(3)來進(jìn)行描述:

(3)

Cx,x′(s)表示位形x和x′之間的一條路徑，s為C的弧長參數(shù).

1.2 航跡規(guī)劃約束

在不同的應(yīng)用場(chǎng)景中，航跡規(guī)劃存在著各種不同的約束[3]，可以分為兩類：環(huán)境約束和本體約束.環(huán)境約束主要指來自無人機(jī)飛行空間的各類障礙和威脅源，諸如山峰、建筑、氣象禁飛區(qū)、敵方雷達(dá)、導(dǎo)彈以及火炮等，無人機(jī)應(yīng)該盡可能規(guī)避；本體約束指無人機(jī)由于機(jī)動(dòng)能力的限制和支持技術(shù)(如導(dǎo)航方法)的限制而形成的，如轉(zhuǎn)彎半徑、過載等.航跡規(guī)劃應(yīng)在滿足各類約束的前提下進(jìn)行.

環(huán)境約束中，各種障礙按照其高度可折算為飛越代價(jià)，高度越高代價(jià)越大，通常威脅源在不同的方向上具有不同的威脅能力，可等效為具有不同長、短軸的橢球或者不同半徑的球形區(qū)域，進(jìn)行二維規(guī)劃時(shí)它們投影成橢圓或圓，威脅源位于橢圓中心，它對(duì)無人機(jī)的威脅強(qiáng)度從橢圓中心沿軸向外視威脅種類不同按特定規(guī)律遞減，規(guī)劃出的航跡應(yīng)盡可能遠(yuǎn)離威脅源，航跡與橢圓無交點(diǎn)意味著對(duì)應(yīng)的威脅源不影響無人機(jī)飛行，航跡一旦與橢圓相交，處于橢圓內(nèi)的航跡段對(duì)應(yīng)的飛行代價(jià)將增加，從而增加航跡的整體飛行代價(jià)，威脅對(duì)應(yīng)的整個(gè)橢圓形區(qū)域都不能通過的區(qū)域稱之為禁飛區(qū)，規(guī)劃航跡時(shí)要保證與禁飛區(qū)無交集.

機(jī)動(dòng)約束很多，主要存在最大轉(zhuǎn)彎角、最大爬升/俯沖角、最低飛行高度、最大航程、最大過載量、最短直飛航跡長度以及由導(dǎo)航技術(shù)決定的航跡修正間距等多個(gè)方面，全部考慮所有的機(jī)動(dòng)約束是一件十分困難的問題，本文采用簡化模型：在二維航跡規(guī)劃過程，主要考慮最大轉(zhuǎn)彎角和最短直飛航跡長度的限制，在高度規(guī)劃過程中處理最大爬升/俯沖角、最低飛行高度約束.

2 三維航跡規(guī)劃算法

2.1 二維規(guī)劃

對(duì)于方程Eikonal(2)，如果T(x) 作為距離函數(shù)代表從起始點(diǎn)到當(dāng)前點(diǎn)x的到達(dá)時(shí)間測(cè)度，可以得到用T(x)來表示的Eikonal方程形式[4]:

(4)

其中:Ω表示規(guī)劃空間，?Ω為其邊界；F為規(guī)劃空間中的速度場(chǎng),它代表距離函數(shù)(在水平集理論中叫做水平集函數(shù))在規(guī)劃空間中各點(diǎn)的演化速度，該求解Eikonal方程的方法[5]為Fast Marching Method(FMM).

在將規(guī)劃空間離散化的前提下，兩點(diǎn)之間的距離記作Ti,j=T(xi,j)，假定笛卡爾坐標(biāo)中網(wǎng)格的寬度為h，對(duì)方程(4)定義下面的算子以進(jìn)行一階數(shù)值近似：

|

(5)

其中代價(jià)函數(shù)ci,j=c(xi,j)=1/Fij.

圖1 二維航跡擬合過程示意圖

圖2 稀疏A*高度規(guī)劃示意圖

2.2 高度規(guī)劃

經(jīng)過二維規(guī)劃得到的航跡只能保證滿足無人機(jī)的水平機(jī)動(dòng)約束，以此為基礎(chǔ)，進(jìn)行高度規(guī)劃產(chǎn)生三維航跡與直接在三維空間搜索航跡相比，規(guī)劃空間得到有效壓縮，規(guī)劃速度得到提高.本文結(jié)合所得到的二維航跡和相應(yīng)的地形高程信息，采用稀疏A*搜索法進(jìn)行.如圖2，在二維航跡的直飛段，以當(dāng)前點(diǎn)A為參考點(diǎn)，OA為參考基線，由無人機(jī)的最大爬升角、最大俯沖角構(gòu)成扇形搜索區(qū)域，并對(duì)扇形區(qū)域進(jìn)行離散化，以當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的歐式距離作為A*搜索的啟發(fā)函數(shù)在扇形區(qū)域開始搜索，新的擴(kuò)展節(jié)點(diǎn)必須滿足兩個(gè)約束：①最短距離約束；②與空間障礙的碰撞檢測(cè)約束.對(duì)新節(jié)點(diǎn)重復(fù)上述擴(kuò)展過程，直至的目標(biāo)點(diǎn)包含其中，高度規(guī)劃結(jié)束.

3 應(yīng)用算例

仿真實(shí)驗(yàn)用地形高程圖數(shù)據(jù)來自http://gisweb.ciat.cgiar.org/sig/90m_data_tropics.htm，其分辨率為90 m，規(guī)劃范圍為600 km×600 km，仿真所用到的參數(shù)設(shè)置如下：

1)無人機(jī)最低飛行高度為100 m；

2)最短直飛距離為4 km；

3)巡航速度為音速的0.8倍，即0.8 Ma；

4)最小轉(zhuǎn)彎半徑為6 km；

5)最大爬升/俯沖角為30°.

圖3顯示了一個(gè)完整的航跡規(guī)劃過程， 在圖3(a)中，采用文中所述方法產(chǎn)生一條長度為450km的航跡，小紅旗所在位置為起始點(diǎn)，藍(lán)色三角對(duì)應(yīng)目標(biāo)點(diǎn)，其中設(shè)置兩類威脅源，藏青色區(qū)域表示普通威脅區(qū)，紅色區(qū)域表示禁飛區(qū)，航跡上藏青點(diǎn)為航跡水平轉(zhuǎn)彎點(diǎn)，橙色點(diǎn)為高度變化點(diǎn).圖3(b)是對(duì)所獲得的二維航跡，結(jié)合飛行器的垂直機(jī)動(dòng)能力、最小離地高度和地形高程信息進(jìn)行高度規(guī)劃所得的航跡剖面效果，其中紅色線條為航跡高度，線條上的黃點(diǎn)為高度變化點(diǎn)，藏青點(diǎn)為航跡轉(zhuǎn)彎點(diǎn)，藍(lán)色曲線為地表.經(jīng)過高度規(guī)劃以后的航跡就是一條在三維空間可飛的航跡.

(a)二維航跡規(guī)劃結(jié)果 (b) 高度規(guī)劃

圖4 三維航跡示例(離地高度設(shè)為50 m，最小直飛距離設(shè)為500 m，轉(zhuǎn)彎半徑設(shè)為2 km)

為了清楚地顯示三維航跡的效果，圖4為在512×512大小地圖上，采用本文的方法所獲得的三維航跡效果，圖中所示的兩條航跡分別對(duì)應(yīng)于從相同的起點(diǎn)出發(fā)到達(dá)不同目標(biāo)點(diǎn)的最優(yōu)航跡.由于地圖變小，為了顯示效果明顯，將航跡離地高度、最小直飛距離和最小轉(zhuǎn)彎半徑等規(guī)劃參數(shù)都作了相應(yīng)改變.所得的三維航跡具有良好的地形跟隨能力.

4 結(jié)語

本文利用地形高程信息結(jié)合威脅簡化模型，采用FMM方法進(jìn)行二維平面航跡規(guī)劃，并在此基礎(chǔ)上進(jìn)行曲線擬合以滿足無人機(jī)水平機(jī)動(dòng)約束，實(shí)現(xiàn)了航跡的直線段加圓弧的表示；然后結(jié)合稀疏A*搜索進(jìn)行高度規(guī)劃，滿足無人機(jī)垂直機(jī)動(dòng)約束條件，從而實(shí)現(xiàn)了無人機(jī)的三維航跡規(guī)劃.仿真實(shí)驗(yàn)表明：該方法所得到的航跡具有良好的障礙/威脅回避性能，并具有很好的地形跟隨能力，同時(shí)由于該方法只在二維航跡所對(duì)應(yīng)的空間進(jìn)行高度規(guī)劃，極大地壓縮了搜索空間，因此規(guī)劃效率很高.

[1] 諾曼·弗里德曼.全球作戰(zhàn)無人機(jī)[M].聶春明譯.北京:中國市場(chǎng)出版社,2011.

[2] Rouy E,Tourin A.A viscosity solutions approach to shape-from-shading[J].SIAM Journal on Numerical Analysis,1992,29(3):867-884.

[3] 熊丹君,蔡滿意,劉宇坤.多約束條件下飛行器航路規(guī)劃[J].彈箭與制導(dǎo)學(xué)報(bào),2009,29(2):289-292.

[4] Sethian J A.Level set methods and fast marching methods:evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science[M]. 2nd. Cambridge: Cambridge University Press,1999.

[5] Sethian J.Fast marching methods[J]. SIAM review,1999,41(2):199-235.

[6] 李時(shí)東,蔡超,丁明躍.一種航跡約束演化新模型及其FMM實(shí)現(xiàn)[J].系統(tǒng)仿真學(xué)報(bào),2011,23(5):925-929.

[7] Yang K,Sukkarieh S.An Analytical Continuous-Curvature Path-Smoothing Algorithm Robotics[J].IEEE Transactions on,2010,26(3):561-568.