分段優(yōu)化RRT的無人機(jī)動(dòng)態(tài)航跡規(guī)劃算法

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

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

0 引 言

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

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

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

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

1 算法流程

DPPUAVSORRT算法流程如圖1所示。

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

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

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

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

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

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

相關(guān)說明:

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

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

(3) 利用分段優(yōu)化RRT算法規(guī)劃得到的航跡經(jīng)過B樣條曲線法平滑后是大量擬合航跡的點(diǎn),通過對(duì)這些擬合點(diǎn)的處理,設(shè)置均勻分布的若干航程點(diǎn),可確保設(shè)置的起點(diǎn)pj-2和終點(diǎn)pk+2不會(huì)距離突發(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é)點(diǎn)。在整個(gè)規(guī)劃空間中根據(jù)面向目標(biāo)的采樣策略隨機(jī)選取節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

2.4 航跡平滑

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

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

B樣條曲線方程可寫為

(1)

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

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

(2)

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

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

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

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

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

(3)

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

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

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

(4)

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

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

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

(5)

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

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

(6)

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

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é)點(diǎn)之間的距離在逐漸縮小,當(dāng)且僅當(dāng)隨機(jī)樹節(jié)點(diǎn)數(shù)趨于無窮大時(shí),節(jié)點(diǎn)位于O′(p*)的概率為1,即

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

證畢

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

證明設(shè)X和Xi分別是傳統(tǒng)RRT算法和引入面向目標(biāo)的采樣策略RRT算法的節(jié)點(diǎn)概率分布密度函數(shù),且pstart和p*位于同一連通區(qū)域內(nèi),則存在一個(gè)序列p1,p2,p3,…,pn以及對(duì)應(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ò)展時(shí)Ufree中未被引入面向目標(biāo)的采樣策略RRT算法搜索到的區(qū)域?yàn)?/p>

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

(11)

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

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

證畢

3 實(shí)驗(yàn)驗(yàn)證

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

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

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

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

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

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

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

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

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

3.1.3 評(píng)估準(zhǔn)則

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

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

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

3.1.4 實(shí)驗(yàn)結(jié)果及分析

q值對(duì)算法性能影響的實(shí)驗(yàn)對(duì)比結(jié)果如圖4所示。

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

將實(shí)驗(yàn)結(jié)果分析如下:

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

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

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

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

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

ε值對(duì)算法性能影響的實(shí)驗(yàn)對(duì)比結(jié)果如圖5所示。

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

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

將實(shí)驗(yàn)結(jié)果分析如下:

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

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

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

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

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

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

3.2 分段優(yōu)化RRT算法實(shí)驗(yàn)

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

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

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

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

3.2.2 實(shí)驗(yàn)結(jié)果及分析

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

圖6 分段優(yōu)化RRT算法實(shí)驗(yàn)結(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是對(duì)航跡進(jìn)行分段優(yōu)化前后的路徑長(zhǎng)度實(shí)驗(yàn)對(duì)比數(shù)據(jù)。

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

將實(shí)驗(yàn)結(jié)果分析如下:

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

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

3.3 動(dòng)態(tài)航跡規(guī)劃實(shí)驗(yàn)

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

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

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

將實(shí)驗(yàn)結(jié)果分析如下:

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

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

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

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

4 結(jié) 論

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

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

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

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