李文廣, 孫世宇, 李建增, 胡永江, 張 巖

(陸軍工程大學(xué)石家莊校區(qū)無人機(jī)工程系, 河北 石家莊 050003)

0 引 言

目前,大多數(shù)的航跡規(guī)劃主要研究在靜態(tài)威脅下如何規(guī)劃航跡[1-3],對于突發(fā)威脅下的動態(tài)航跡規(guī)劃問題相關(guān)文獻(xiàn)較少。在實戰(zhàn)背景下,只考慮靜態(tài)威脅對無人機(jī)飛行安全的影響是不符合實際任務(wù)要求的。無人機(jī)動態(tài)航跡規(guī)劃就是解決無人機(jī)在發(fā)現(xiàn)突發(fā)威脅時,該如何重新規(guī)劃局部航跡的問題。這有利于提升無人機(jī)對于復(fù)雜戰(zhàn)場環(huán)境的適應(yīng)能力和生存能力,同時更符合實戰(zhàn)背景，所以研究無人機(jī)動態(tài)航跡規(guī)劃意義重大。

在無人機(jī)動態(tài)航跡規(guī)劃方面,學(xué)者們做了大量的工作:文獻(xiàn)[4]提出了一種改進(jìn)的快速擴(kuò)展隨機(jī)樹(rapidly-exploring random tree, RRT)算法,提升了算法搜索路徑的效率和可行性,路徑的可跟蹤性更強(qiáng)。但該算法只考慮了靜態(tài)威脅下的航跡規(guī)劃問題,不符合實戰(zhàn)任務(wù)要求。文獻(xiàn)[5]提出了稀疏A*和人工勢場相結(jié)合的動態(tài)航跡規(guī)劃算法。該算法首先利用稀疏A*算法完成全局航跡規(guī)劃,然后在出現(xiàn)突發(fā)威脅的情況下結(jié)合人工勢場法完成局部航跡規(guī)劃。其充分利用了稀疏A*和人工勢場法的優(yōu)點,同時避免了出現(xiàn)局部極小的缺陷。但稀疏A*算法需要前期對規(guī)劃空間進(jìn)行預(yù)處理,算法效率不高,并且用稀疏A*算法的航跡代價函數(shù)去近似描述局部航跡的代價,誤差較大。文獻(xiàn)[6]提出了基于動態(tài)貝葉斯網(wǎng)絡(luò)(dynamic Bayesian network, DBN)威脅評估模型與模型預(yù)測控制(model predictive control, MPC)路徑規(guī)劃算法相結(jié)合的方法。該算法首先利用DBN模型評估得到突發(fā)威脅的威脅等級,然后結(jié)合航跡規(guī)劃算法規(guī)劃動態(tài)航跡。其能夠解決一般不確定的突發(fā)威脅以及尾隨無人機(jī)的突發(fā)威脅的動態(tài)航跡規(guī)劃問題。但考慮空中威脅(敵機(jī))并不是實戰(zhàn)條件下的主要威脅來源,實用性不強(qiáng)。文獻(xiàn)[7]提出了一種基于動態(tài)步長的實時航跡規(guī)劃算法,即無人機(jī)在飛行過程中實時規(guī)劃飛行航跡,若出現(xiàn)突發(fā)威脅,則通過設(shè)置子目標(biāo)點的方法,規(guī)劃局部航跡。該算法將規(guī)劃空間進(jìn)行了簡化處理,降低了問題的復(fù)雜度,同時提升了算法在威脅區(qū)域搜索航跡的精度。但由于整個規(guī)劃過程都是實時的,對算法的實時性要求非常高,也對無人機(jī)的智能化程度要求非常高。

上述航跡規(guī)劃算法都針對突發(fā)威脅下的動態(tài)航跡規(guī)劃問題進(jìn)行了不同算法的創(chuàng)新和改進(jìn),但仍存在以下問題:前期全局航跡規(guī)劃效率較低,導(dǎo)致整體規(guī)劃效率不高;DBN威脅評估模型對于突發(fā)威脅的等級評估結(jié)果可信度不高;算法對無人機(jī)智能化程度要求太高,實用性不強(qiáng)。

針對以上問題,本文提出了分段優(yōu)化RRT的無人機(jī)動態(tài)航跡規(guī)劃算法(dynamic path planning of unmanned aerial vehicle based on segment optimization RRT, DPPUAVSORRT)。該算法首先利用分段優(yōu)化RRT算法生成全局航跡。然后在規(guī)劃空間中若有對無人機(jī)飛行安全產(chǎn)生影響的突發(fā)威脅,則根據(jù)新的威脅信息確定局部航跡規(guī)劃的起點和終點,并使用分段優(yōu)化RRT算法生成從新起點能夠繞過突發(fā)威脅并回到原航跡的局部航跡。若無,則繼續(xù)沿著全局航跡飛行直至目標(biāo)點。最后通過實驗對所提出的方法進(jìn)行了驗證。

1 算法流程

DPPUAVSORRT算法流程如圖1所示。

圖1 DPPUAVSORRT流程圖Fig.1 Flowchart of DPPUAVSORRT

步驟1規(guī)劃全局航跡。根據(jù)已知的戰(zhàn)場情報信息和任務(wù)要求,利用分段優(yōu)化RRT算法規(guī)劃從起點到終點的全局航跡。

步驟2威脅實時檢測。無人機(jī)沿著全局航跡飛行時,利用各類傳感器實時探測戰(zhàn)場信息,同時不間斷接收地面的情報信息。判斷規(guī)劃空間中是否有未知突發(fā)威脅產(chǎn)生,且突發(fā)威脅的位置、類型和作用范圍是否對無人機(jī)的飛行安全有很大影響。

步驟3更新規(guī)劃空間。根據(jù)步驟2的結(jié)果,若有突發(fā)威脅,則更新整個規(guī)劃空間的威脅信息,包括威脅的位置、類型和作用范圍等(將威脅作用范圍放大1.2倍);若無,則無人機(jī)繼續(xù)沿著全局航跡飛行,并繼續(xù)探測戰(zhàn)場信息。

步驟4確定新的起點。動態(tài)航跡規(guī)劃算法首先根據(jù)突發(fā)威脅的相關(guān)威脅信息,判斷所有航程點中最先可能處在威脅作用范圍內(nèi)的航程點pj和最后可能處在威脅作用范圍內(nèi)的航程點pk(2

步驟5規(guī)劃避讓航跡。根據(jù)步驟4確定的起點和終點,利用分段優(yōu)化RRT算法搜索得到避讓突發(fā)威脅的局部航跡,使得無人機(jī)能夠成功繞過突發(fā)威脅并回到原航跡。

相關(guān)說明:

(1) 假定全局航跡的前兩個航程點和最后兩個航程點之內(nèi)不會有未知的突發(fā)威脅。

(2) 將威脅作用范圍擴(kuò)大1.2倍,是為了在規(guī)劃局部航跡時,降低航跡的威脅代價以及無人機(jī)被擊落的概率。

(3) 利用分段優(yōu)化RRT算法規(guī)劃得到的航跡經(jīng)過B樣條曲線法平滑后是大量擬合航跡的點,通過對這些擬合點的處理,設(shè)置均勻分布的若干航程點,可確保設(shè)置的起點pj-2和終點pk+2不會距離突發(fā)威脅太近,提高規(guī)劃的成功率。

2 分段優(yōu)化RRT算法

2.1 算法流程

分段優(yōu)化RRT算法流程如圖2所示。

圖2 分段優(yōu)化RRT算法流程圖Fig.2 Flowchart of segmented optimization RRT

步驟1搜索節(jié)點。在整個規(guī)劃空間中根據(jù)面向目標(biāo)的采樣策略隨機(jī)選取節(jié)點。

步驟2節(jié)點篩選。根據(jù)步驟1選取的節(jié)點,判斷其是否滿足所有約束條件。若滿足,則執(zhí)行步驟3;若不滿足,則執(zhí)行步驟1。

步驟3擴(kuò)展隨機(jī)樹。在隨機(jī)樹中找到離節(jié)點最近的葉節(jié)點,并根據(jù)步長要求擴(kuò)展新的節(jié)點(該節(jié)點也必須滿足所有約束條件),將新的節(jié)點加入到隨機(jī)樹中。若不存在,則執(zhí)行步驟1。

步驟4反向搜索。當(dāng)隨機(jī)樹擴(kuò)展到終點或距離終點在一個步長以內(nèi)時,反向搜索隨機(jī)樹,找到起點和終點之間的最短航跡。

步驟5分段優(yōu)化。根據(jù)分段優(yōu)化的航跡策略對所有航程點進(jìn)行處理,分段優(yōu)化航跡。

2.2 面向目標(biāo)的采樣策略

傳統(tǒng)RRT算法在擴(kuò)展隨機(jī)樹時,是對整個規(guī)劃空間進(jìn)行隨機(jī)采樣并得到隨機(jī)節(jié)點prand,這樣雖然有利于對未知的規(guī)劃空間進(jìn)行探索,保證了樹節(jié)點在規(guī)劃空間中的均勻分布,但實際上在規(guī)劃空間中的部分區(qū)域擴(kuò)展隨機(jī)樹對尋找路徑?jīng)]有實質(zhì)性的幫助,反而導(dǎo)致了隨機(jī)樹擴(kuò)展效率低,搜索路徑速度慢的缺點。

面向目標(biāo)的采樣策略是通過設(shè)定引導(dǎo)因子來改變隨機(jī)節(jié)點的采樣規(guī)則。引導(dǎo)因子是將終點pend以一定的概率q(引導(dǎo)因子的大小就是q值的大小)作為隨機(jī)節(jié)點prand(prand=pend),導(dǎo)致隨機(jī)節(jié)點的選取并不完全是隨機(jī)的。這樣使得隨機(jī)樹擴(kuò)展時向目標(biāo)位置生長的趨勢更加明顯,減約了隨機(jī)樹在部分規(guī)劃空間的擴(kuò)展過程,大大減少了隨機(jī)樹擴(kuò)展過程中隨機(jī)節(jié)點的數(shù)目,不僅使搜索路徑更具有目的性,而且有利于隨機(jī)樹快速擴(kuò)展至目標(biāo)點。

2.3 分段優(yōu)化的航跡策略

現(xiàn)有的大部分RRT改進(jìn)算法都考慮了規(guī)劃后的航跡是否滿足無人機(jī)最小轉(zhuǎn)彎半徑等無人機(jī)自身性能的約束[1,4,8],于是對隨機(jī)節(jié)點prand的選取提出了不同的約束條件,確保規(guī)劃得到的航跡能夠滿足無人機(jī)的性能約束。但這一方面限制了算法對于各類無人機(jī)的通用性,另一方面增加了隨機(jī)樹擴(kuò)展過程中的運算代價,對算法搜索路徑的效率產(chǎn)生一定影響。

分段優(yōu)化的航跡策略是將數(shù)據(jù)結(jié)構(gòu)中“二分查找法”[9]的思想引入到RRT算法中。首先利用基于面向目標(biāo)的采樣策略RRT算法規(guī)劃得到一系列航程點(按飛行順序排列),接著利用二分法將所有航程點一分為二,并從后一半航程點中找到能與目標(biāo)點pend直接相連且與所有障礙不相交的航程點,記為Pn-1(記pend=Pn),然后對起始點pstart和Pn-1之間的航程點再進(jìn)行分段優(yōu)化處理,得到Pn-2,重復(fù)以上步驟直到所有航程點處理完畢。

分段優(yōu)化的航跡策略處理的航程點數(shù)量遠(yuǎn)遠(yuǎn)小于隨機(jī)節(jié)點的數(shù)量,所以該優(yōu)化策略的計算量遠(yuǎn)小于對隨機(jī)節(jié)點的選取考慮無人機(jī)性能時的計算量,同時由于該改進(jìn)策略不需要結(jié)合無人機(jī)的具體性能約束,使得算法通用性不受限制,并且該優(yōu)化策略能夠大大縮短路徑長度。

相關(guān)性說明:分段優(yōu)化的航跡策略不僅僅采用“二分法”,也可根據(jù)算法效率和精度的要求,對基于面向目標(biāo)的采樣策略RRT算法規(guī)劃得到一系列航程點(按飛行順序排列)多劃分幾段進(jìn)行優(yōu)化。

2.4 航跡平滑

采用分段優(yōu)化RRT規(guī)劃得到的航跡是由幾條線段組成的,但部分線段相交的拐點部分不夠平滑,不利于無人機(jī)在拐點處的機(jī)動飛行,需進(jìn)行平滑處理。

由于B樣條曲線法兼?zhèn)淞薆ezier曲線法的幾何不變性、仿射不變性等優(yōu)點,同時克服了由于整體表示帶來不具備局部性質(zhì)的缺點[10],使其在航跡規(guī)劃中應(yīng)用廣泛。本文利用B樣條曲線法對拐點部分路徑點進(jìn)行擬合,生成平滑路徑。

B樣條曲線方程可寫為

(1)

式中,控制頂點為di(i=0,1,…,n);k次規(guī)范B樣條基函數(shù)為Ni,k(u)(i=0,1,…,n),最高次數(shù)為k?；瘮?shù)是由一個稱為節(jié)點矢量的非遞減參數(shù)u的序列U:u0≤u1≤…≤un+k+1所決定的k次分段多項式。

B樣條的基函數(shù)采用Cox-deBoor遞推公式,即

(2)

式中,i為節(jié)點序號;k是基函數(shù)的次數(shù),共有n+1個控制點。

2.5 算法的概率完備性及收斂性證明

傳統(tǒng)RRT算法的隨機(jī)節(jié)點選取是在整個規(guī)劃空間中隨機(jī)選取的,使其能夠?qū)σ?guī)劃空間的未知區(qū)域展開搜索。而待擴(kuò)展節(jié)點的概率是收斂于均勻分布的[11-14],算法具備概率完備性。本文引入面向目標(biāo)的采樣策略影響了算法隨機(jī)節(jié)點選取的規(guī)則,下面從理論上對引入面向目標(biāo)的采樣策略RRT算法的概率完備性進(jìn)行證明。

假設(shè)Dk(p*)表示節(jié)點p*與隨機(jī)樹上最近節(jié)點之間距離的隨機(jī)變量。dk表示該隨機(jī)變量的取值,k表示節(jié)點數(shù),ε表示擴(kuò)展步長。

定理1在n維有界規(guī)劃空間U中(包含威脅),起始點pstart和目標(biāo)點pend在同一連通區(qū)域內(nèi),當(dāng)引入面向目標(biāo)的采樣策略RRT算法的隨機(jī)樹節(jié)點數(shù)趨向于無窮大時,擴(kuò)展節(jié)點pi等價于目標(biāo)點pend的概率為1。即

(3)

式中，Ufree表示安全子空間,即規(guī)劃空間中無威脅障礙的區(qū)域。

證明設(shè)p*為Ufree中的任意一點,O(p*)表示以p*為圓心,ε為半徑的圓形區(qū)域,則有

O(p*)={p‖p-p*‖≤ε}

(4)

O′(p*)表示O(p*)與Ufree的交集,則有O′(p*)=O(p*)∩Ufree,μ(O′(p*))>0,μ表示集合的測度。

初始i=1時,d1(p*)=ρ(pend,p*),其中ρ(pend,p*)表示p*與起始點的距離。當(dāng)隨機(jī)樹不斷擴(kuò)展,隨機(jī)節(jié)點prand位于O′(p*)內(nèi)的概率滿足

P{prand∈O′(p*)}>0

(5)

假設(shè)所有節(jié)點均在O′(p*)的外部,算法進(jìn)一步擴(kuò)展。當(dāng)prand=p*時,依據(jù)pnew的擴(kuò)展方法可知,Dk+1(p*)的數(shù)學(xué)期望是

E[Dk+1(p*)|prand=p*]

(6)

當(dāng)prand≠p*時,有

E[Dk+1(p*)|prand≠p*]≤E[Dk(p*)]

(7)

進(jìn)一步可得到

E[Dk+1(p*)]=E[qr·(Dk+1(p*)|prand=p*)+

(1-qr)·(Dk+1(p*)|prand≠p*)]

(8)

式中,00,使得Dk+1的數(shù)學(xué)期望E(Dk+1)

由此可以得出,引入面向目標(biāo)的采樣策略RRT算法在擴(kuò)展過程中使得p*與隨機(jī)樹節(jié)點之間的距離在逐漸縮小,當(dāng)且僅當(dāng)隨機(jī)樹節(jié)點數(shù)趨于無窮大時,節(jié)點位于O′(p*)的概率為1,即

由此可知,引入面向目標(biāo)的采樣策略實質(zhì)上只是改變了Ufree區(qū)域的大小,并沒有改變傳統(tǒng)RRT算法有界連通性以及隨機(jī)采樣性,保證了算法的概率完備性。同時在擴(kuò)展節(jié)點趨于無窮時,保證擴(kuò)展節(jié)點仍然服從于隨機(jī)節(jié)點采樣分布。

證畢

下面對引入面向目標(biāo)的采樣策略RRT算法的收斂性進(jìn)行證明。

證明設(shè)X和Xi分別是傳統(tǒng)RRT算法和引入面向目標(biāo)的采樣策略RRT算法的節(jié)點概率分布密度函數(shù),且pstart和p*位于同一連通區(qū)域內(nèi),則存在一個序列p1,p2,p3,…,pn以及對應(yīng)的O(p1),O(p2),…,O(pn)圓形區(qū)域,且滿足pstart∈O(p1),p*∈O(pn),則有

Oi(pi)∩Oi+1(pi+1)≠?,i=1,2,…,n-1

(9)

(10)

設(shè)第i次擴(kuò)展時Ufree中未被引入面向目標(biāo)的采樣策略RRT算法搜索到的區(qū)域為

Yi={p*∈Ufree|ρ(p*,q)>ε,?ζ∈Hi}

(11)

ρ(p*,q)為p*與隨機(jī)樹節(jié)點q之間的距離,Hi為此時的節(jié)點集合,μ(Yi)為Yi的測度,且有Yi+1?Yi,當(dāng)i→∞時,μ(Yi)→0。根據(jù)概率函數(shù)的光滑性,可知Xi概率收斂于X。

由上述證明可知,引入面向目標(biāo)的采樣策略RRT算法仍然是收斂的。

證畢

3 實驗驗證

工作站配置:Thinkstation D30,CPU:Intel Xeon E5-2620 (雙處理器),64G內(nèi)存,64位Win7系統(tǒng)。

編程工具:Matlab 2015(64位)。

3.1 分段優(yōu)化RRT算法參數(shù)設(shè)置實驗

3.1.1 數(shù)據(jù)集

實驗設(shè)置200×200的二維無量綱規(guī)劃空間,起點為(10, 10),終點為(190, 190),用紅色五角星表示。其中分別設(shè)有8個威脅區(qū)域,10個威脅區(qū)域和12個威脅區(qū)域,用黃色圓形區(qū)域表示。3種規(guī)劃空間如圖3所示。

圖3 3種規(guī)劃空間Fig.3 Three types of planning space

3.1.2 實驗對象及相關(guān)參數(shù)設(shè)置

對象1分段優(yōu)化RRT算法是以一定的引導(dǎo)因子q選取目標(biāo)點pend作為prand。實驗對q值在[0,1)(q=1時,無法成功規(guī)劃航跡)范圍內(nèi),每隔0.1取值,并進(jìn)行仿真實驗(步長設(shè)置為ε=5)。記錄每個q值下的100次仿真數(shù)據(jù)。

對象2隨機(jī)樹擴(kuò)展時,若隨機(jī)節(jié)點prand和pnear(隨機(jī)樹上離prand最近的節(jié)點)之間的距離大于一個步長,則在pnear沿著prand的方向上,擴(kuò)展一個步長ε得到新的節(jié)點pnew;若不大于,則直接將prand作為pnew。實驗對步長ε值取1,3,5,8,10,12,15,20,25,30,35,40,45,50(引導(dǎo)因子q=0.5)。記錄每個ε值下的100次仿真數(shù)據(jù)。

3.1.3 評估準(zhǔn)則

指標(biāo)1隨機(jī)樹節(jié)點數(shù)。隨機(jī)樹節(jié)點數(shù)是指在完成路徑搜索時,擴(kuò)展隨機(jī)樹的節(jié)點數(shù)。隨機(jī)樹節(jié)點數(shù)越少表征算法搜索路徑時采樣點越少,算法效率越高。

指標(biāo)2路徑代價。路徑代價是指航跡規(guī)劃算法計算得到路徑的長度,這是航跡規(guī)劃所關(guān)心的一項重要指標(biāo)。因為在無人機(jī)性能有限的條件下,路徑代價直接決定著規(guī)劃的航跡是否可行。

指標(biāo)3算法運行時間。算法運行時間是指在相同的硬件條件下算法的運行速度。在完成相同目標(biāo)時,算法運行時間和算法效率呈負(fù)相關(guān)。

3.1.4 實驗結(jié)果及分析

q值對算法性能影響的實驗對比結(jié)果如圖4所示。

圖4 q值對算法性能的影響Fig.4 Effect of q value on the performance of the algorithm

將實驗結(jié)果分析如下:

(1) 由圖4可知,整體上當(dāng)q=0(等價于傳統(tǒng)RRT算法)時,隨機(jī)樹節(jié)點數(shù)和算法運行時間都遠(yuǎn)大于其他情況,路徑代價也大于其他情況,表明引入面向目標(biāo)的采樣策略RRT算法效率優(yōu)于傳統(tǒng)的RRT算法。

(2) 在第一種規(guī)劃空間中,隨機(jī)樹節(jié)點數(shù)呈現(xiàn)遞減趨勢,但當(dāng)q>0.5時,遞減趨勢很小,此時增大q值對隨機(jī)樹節(jié)點數(shù)的影響很小。路徑代價隨著q值的增大呈遞減趨勢。而算法運行時間在0.1

(3) 在第二種規(guī)劃空間中,隨機(jī)樹節(jié)點數(shù)和路徑代價的變化趨勢與第一種規(guī)劃空間相似。而算法運行時間在q>0.5時的增長趨勢相對于第一種規(guī)劃空間更加明顯。但算法運行效率均低于第一種規(guī)劃空間。

(4) 在第三種規(guī)劃空間中,隨機(jī)樹節(jié)點數(shù)和路徑代價的變化趨勢與前兩種規(guī)劃空間相似。特別的是算法運行時間的變化趨勢在q≥0.5時增長更快更明顯。算法運行效率均低于前兩種規(guī)劃空間。

以上結(jié)果表明,增大q值能夠有效降低算法的隨機(jī)樹節(jié)點數(shù)、路徑代價以及在一定范圍內(nèi)降低算法運行時間。但較大的q值反而會降低算法運行效率,這是由于較大的q值使得隨機(jī)節(jié)點prand以較大的概率選取目標(biāo)點,導(dǎo)致隨機(jī)節(jié)點的選取比較單一,不利于隨機(jī)樹的擴(kuò)展。同時越復(fù)雜的規(guī)劃空間,搜索路徑的效率也比較低。

ε值對算法性能影響的實驗對比結(jié)果如圖5所示。

圖5 ε值對算法性能的影響Fig.5 Effect of ε value on the performance of the algorithm

圖5(a)步長為1時的隨機(jī)樹節(jié)點數(shù)(3種規(guī)劃空間)遠(yuǎn)大于其他情況,為了實驗數(shù)據(jù)顯示更加客觀形象,所以未在折線圖中表示。圖5(c)步長為1時的算法運行時間(規(guī)劃空間2和規(guī)劃空間3)遠(yuǎn)大于其他情況,也未在折線圖中表示。

將實驗結(jié)果分析如下:

(1) 由圖5可知,隨著ε的增大,隨機(jī)樹節(jié)點數(shù)呈現(xiàn)遞減趨勢。路徑代價開始在一定范圍內(nèi)波動,之后隨著ε繼續(xù)增大,呈現(xiàn)遞增趨勢。而算法運行時間也在一定范圍內(nèi)呈現(xiàn)遞減趨勢,過大的ε值反而會增大算法運行時間。整體上看在適當(dāng)范圍內(nèi)選擇ε的值能夠有效降低算法運行效率。

(2) 在第一種規(guī)劃空間中,隨機(jī)樹節(jié)點數(shù)呈現(xiàn)遞減趨勢,但當(dāng)ε>25時,遞減趨勢很小,此時增大ε值對隨機(jī)樹節(jié)點數(shù)的影響很小。路徑代價開始在一定范圍內(nèi)波動(ε為3時規(guī)劃空間1的實驗數(shù)據(jù)誤差較大),之后隨著ε增大,呈現(xiàn)遞增趨勢。而算法運行時間在5<ε≤35時變化很小,此時算法已經(jīng)能夠很快搜索得到路徑。但當(dāng)ε>35時,算法運行時間有增長的趨勢,此時增大ε值反而降低了搜索路徑的效率。

(3) 在第二種規(guī)劃空間中,隨機(jī)樹節(jié)點數(shù)、路徑代價以及算法運行時間的變化趨勢與第一種規(guī)劃空間相似。但算法運行效率均低于第一種規(guī)劃空間。

(4) 在第三種規(guī)劃空間中,3類性能指標(biāo)的變化趨勢同前二種規(guī)劃空間。算法運行效率也均低于前兩種規(guī)劃空間。但路徑代價在ε>30時增長趨勢更快更明顯。算法運行效率均低于前兩種規(guī)劃空間。

以上結(jié)果表明,在一定范圍內(nèi)增大ε值能夠有效降低算法的運行效率。但較大的ε值反而會提升算法路徑代價以及運行時間,大大降低算法運行效率。這是由于較大的步長雖然有利于減少隨機(jī)樹的擴(kuò)展,簡約了隨機(jī)樹擴(kuò)展的空間。但是隨著規(guī)劃空間的復(fù)雜度提升,較大的步長使得擴(kuò)展節(jié)點的失敗率也在增大,只能通過更遠(yuǎn)距離的繞行來避開威脅,反而增大了路徑代價和算法運行時間。

綜上所述,引導(dǎo)因子q和步長ε的值在一定范圍內(nèi)能夠提高算法搜索路徑的效率,其取值不僅要考慮規(guī)劃空間的復(fù)雜度也應(yīng)結(jié)合具體任務(wù)要求、威脅態(tài)勢和其他情報信息等條件。

3.2 分段優(yōu)化RRT算法實驗

3.2.1 實驗對象及相關(guān)參數(shù)設(shè)置

實驗對象:在設(shè)置的規(guī)劃空間中,利用分段優(yōu)化RRT算法計算得到起點和終點之間的路徑。

仿真參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

3.2.2 實驗結(jié)果及分析

分段優(yōu)化RRT算法實驗結(jié)果如圖6所示。

圖6 分段優(yōu)化RRT算法實驗結(jié)果Fig.6 Simulation results of segmented optimization RRT

圖6(a)、圖6(b)中藍(lán)色表示擴(kuò)展的隨機(jī)樹,紅色表示搜索得到的路徑。圖6(c)藍(lán)色表示采用分段優(yōu)化的航跡策略優(yōu)化后的路徑,紅色表示B樣條曲線法平滑后的路徑。表2是對航跡進(jìn)行分段優(yōu)化前后的路徑長度實驗對比數(shù)據(jù)。

表2 分段優(yōu)化前后路程比較

將實驗結(jié)果分析如下:

(1) 圖6(a)的隨機(jī)樹擴(kuò)展遍布整個規(guī)劃空間,圖6(b)的隨機(jī)樹擴(kuò)展只分布在路徑沿線的局部區(qū)域,表明引入面向目標(biāo)的采樣策略的RRT算法在擴(kuò)展隨機(jī)樹的過程中大大節(jié)約了擴(kuò)展空間,使得隨機(jī)樹向目標(biāo)點擴(kuò)展趨勢更加明顯,提升了算法搜索路徑的效率。

(2) 圖6(c)藍(lán)色路徑是分段優(yōu)化RRT算法搜索得到的路徑,由幾條線段組成,相比于傳統(tǒng)RRT算法大大減少了無人機(jī)進(jìn)行機(jī)動轉(zhuǎn)彎的部分。同時,由表2可知,分段優(yōu)化RRT算法相對于傳統(tǒng)RRT算法縮短了11.53%左右的路徑長度。表明引入分段優(yōu)化的航跡策略一方面能夠減少無人機(jī)的機(jī)動轉(zhuǎn)彎,算法的通用性更強(qiáng);另一方面能夠縮短路程長度,降低路徑代價。

3.3 動態(tài)航跡規(guī)劃實驗

數(shù)據(jù)集以及相關(guān)參數(shù)設(shè)置均同第3.2節(jié)。動態(tài)航跡規(guī)劃實驗結(jié)果如圖7所示。

圖7 動態(tài)航跡規(guī)劃實驗結(jié)果Fig.7 Simulation results of dynamic path planning

圖7中綠色圓點表示航程點,紅色圓形表示突發(fā)威脅區(qū)域,綠色五角星表示動態(tài)規(guī)劃航跡的起點和終點,淡藍(lán)色表示局部航跡規(guī)劃搜索得到的路徑,紫色表示分段優(yōu)化后的路徑。

將實驗結(jié)果分析如下:

(1) 圖7(a)是突發(fā)威脅所處的位置、范圍對無人機(jī)沿著全局航跡飛行沒有影響的情況下,無人機(jī)無需重新規(guī)劃局部航跡,仍沿著全局航跡飛行即可。

(2) 圖7(b)是突發(fā)威脅的作用范圍與全局航跡相交時,無人機(jī)需規(guī)劃局部航跡的情形。此時算法能夠生成避讓突發(fā)威脅的局部航跡,并重新回到原航跡。

(3) 圖7(c)與圖7(b)相似,區(qū)別在于圖7(c)在突發(fā)威脅的兩側(cè)存在兩個狹窄通道,只有通過上方的通道繞行才能避開突發(fā)威脅。而算法能夠根據(jù)威脅信息在可行的通道內(nèi)規(guī)劃局部航跡,確保無人機(jī)能夠安全避讓突發(fā)威脅。

(4) 實驗表明算法能夠準(zhǔn)確判斷突發(fā)威脅的位置和范圍是否會對無人機(jī)的飛行安全產(chǎn)生影響,若有影響,則算法能夠成功規(guī)劃得到新起點和終點間的路徑并回到原航跡。

4 結(jié) 論

本文提出分段優(yōu)化RRT的無人機(jī)動態(tài)航跡規(guī)劃算法,并通過實驗驗證了算法的可行性與優(yōu)勢,主要得到以下結(jié)論:

(1) 面向目標(biāo)的采樣策略能大大簡約隨機(jī)樹在規(guī)劃空間的擴(kuò)展,提升算法搜索路徑的效率。

(2) 分段優(yōu)化的航跡策略使得算法的通用性更強(qiáng),同時減小了路徑代價,使得整體航跡代價更小,實用性更強(qiáng)。

(3) DPPUAVSORRT能夠準(zhǔn)確判斷突發(fā)威脅對于無人機(jī)的飛行安全是否有影響。若有,則規(guī)劃局部航跡,確保無人機(jī)能夠安全避讓突發(fā)威脅。若無,則無人機(jī)繼續(xù)沿著全局航跡飛行。