無(wú)人機(jī)快速三維航跡規(guī)劃算法

尹高揚(yáng), 周紹磊, 吳青坡

(海軍航空工程學(xué)院 控制科學(xué)與工程系, 山東 煙臺(tái)　264001)

?

無(wú)人機(jī)快速三維航跡規(guī)劃算法

尹高揚(yáng), 周紹磊, 吳青坡

(海軍航空工程學(xué)院 控制科學(xué)與工程系, 山東 煙臺(tái)264001)

摘要：針對(duì)無(wú)人機(jī)三維航跡規(guī)劃的實(shí)時(shí)性問(wèn)題，提出了基于快速擴(kuò)展隨機(jī)樹(shù)的三維航跡規(guī)劃方法。該算法能夠根據(jù)當(dāng)前環(huán)境快速有效搜索規(guī)劃空間，通過(guò)隨機(jī)采樣點(diǎn)將搜索導(dǎo)向空白區(qū)域，使三維航跡規(guī)劃能夠用于實(shí)時(shí)航跡規(guī)劃。通過(guò)引入航跡距離約束，搜索樹(shù)將沿著路徑距離最短的近似最優(yōu)航跡的方向進(jìn)行擴(kuò)展，克服了基本快速擴(kuò)展隨機(jī)樹(shù)方法隨機(jī)性強(qiáng)，只能快速獲得可行航跡，無(wú)法獲得較優(yōu)航跡的缺點(diǎn)。在搜索過(guò)程中無(wú)人機(jī)的航跡約束條件和地形信息得到了充分利用，使算法生成的航跡能夠自動(dòng)回避地形和威脅，同時(shí)滿足無(wú)人機(jī)的動(dòng)力學(xué)約束。通過(guò)生成的虛擬數(shù)字地圖對(duì)算法進(jìn)行了仿真驗(yàn)證，仿真結(jié)果表明該方法能夠快速有效地規(guī)劃出滿意的無(wú)人機(jī)三維航跡。

關(guān)鍵詞：無(wú)人機(jī)；快速擴(kuò)展隨機(jī)樹(shù)；實(shí)時(shí)性；地形回避；三維航跡

在現(xiàn)代戰(zhàn)爭(zhēng)中，無(wú)人機(jī)所處的戰(zhàn)場(chǎng)環(huán)境瞬息萬(wàn)變，同時(shí)由于其所執(zhí)行任務(wù)的不確定性，無(wú)人機(jī)要能夠根據(jù)任務(wù)過(guò)程中的實(shí)時(shí)環(huán)境信息進(jìn)行在線的自主航跡規(guī)劃，這對(duì)規(guī)劃算法的實(shí)時(shí)性提出了很高要求[1-2]。傳統(tǒng)的航跡規(guī)劃方法是基于預(yù)先確定的代價(jià)函數(shù)生成一條具有最小代價(jià)的路徑。由于無(wú)人機(jī)航跡規(guī)劃的規(guī)劃區(qū)域廣闊，雖然近年來(lái)研究人員從規(guī)劃環(huán)境建模和求解算法兩方面均提出了許多改進(jìn)策略，但由于規(guī)劃算法強(qiáng)調(diào)航跡的最優(yōu)性，加上要考慮無(wú)人機(jī)的性能約束等要求，傳統(tǒng)的規(guī)劃方法如遺傳算法[3-4]、蟻群算法[5-6]、稀疏A*算法[7-8]、粒子群算法[9-10]等要獲得一條最優(yōu)路徑需要很長(zhǎng)的收斂時(shí)間和極大的內(nèi)存需求，失去了在線航跡規(guī)劃的現(xiàn)實(shí)可行性。

快速擴(kuò)展隨機(jī)樹(shù)(RRT)方法是一種基于采樣的單查詢(xún)隨機(jī)搜索算法，由S.M.LaValle在1998年首次提出[11]。RRT的節(jié)點(diǎn)擴(kuò)展不需要在規(guī)劃前執(zhí)行預(yù)處理，能夠根據(jù)當(dāng)前的環(huán)境信息快速有效地搜索規(guī)劃空間，在可行路徑的搜索概率意義上是完全的。RRT方法已被成功應(yīng)用于許多非完整系統(tǒng)的規(guī)劃問(wèn)題中，包括地面移動(dòng)機(jī)器人運(yùn)動(dòng)規(guī)劃[12]和無(wú)人機(jī)航跡規(guī)劃[13]等問(wèn)題。雖然基本RRT方法具有很多良好特性，但是其隨機(jī)性太強(qiáng)，只能夠保證高效快速地獲取無(wú)人機(jī)的可行軌跡，無(wú)法獲得較優(yōu)軌跡。針對(duì)基本RRT方法的不足，研究者們從RRT方法的節(jié)點(diǎn)采樣方式、節(jié)點(diǎn)擴(kuò)展方式和節(jié)點(diǎn)選擇方式3個(gè)方面對(duì)其進(jìn)行了改進(jìn)，取得了一定的成果[14-19]。

基本RRT及其改進(jìn)方法雖然能夠滿足無(wú)人機(jī)在線自主航跡規(guī)劃的應(yīng)用要求，但是它們都是在二維平面上進(jìn)行航跡搜索，因而未能利用地形的高度信息，不能有效地利用地形進(jìn)行地形規(guī)避和威脅規(guī)避。本文在基本RRT方法的基礎(chǔ)上，提出了一種三維快速航跡規(guī)劃方法。并在生成的虛擬數(shù)字地形圖上進(jìn)行了仿真驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，該方法能夠充分利用地形的高程信息，有效地進(jìn)行地形回避和威脅回避，是一種快速有效的三維航跡規(guī)劃算法。

1問(wèn)題提出

無(wú)人機(jī)三維在線航跡規(guī)劃要求無(wú)人機(jī)根據(jù)預(yù)先裝載的任務(wù)區(qū)的三維地形數(shù)據(jù)，規(guī)劃出一條從規(guī)劃起始點(diǎn)到目標(biāo)點(diǎn)的三維航跡，該航跡避開(kāi)了所有三維障礙物和威脅，并且滿足無(wú)人機(jī)自身的飛行性能約束。無(wú)人機(jī)在慣性坐標(biāo)系下的三自由度質(zhì)點(diǎn)運(yùn)動(dòng)方程為：

(1)

式中,(x,y,z)表示無(wú)人機(jī)在慣性坐標(biāo)系中的位置;v表示無(wú)人機(jī)的速度;ψ為無(wú)人機(jī)的航向角;γ為無(wú)人機(jī)的航跡傾角。

具體來(lái)說(shuō),三維航跡規(guī)劃生成的目標(biāo)航跡要求滿足以下幾個(gè)約束條件[20]:

1) 最小航跡段長(zhǎng)度:無(wú)人機(jī)在開(kāi)始改變飛行姿態(tài)前必須保持直飛的最短距離。這一約束取決于無(wú)人機(jī)的機(jī)動(dòng)能力和導(dǎo)航要求。

2) 最大拐彎角:無(wú)人機(jī)只能在小于或等于由自身水平平面機(jī)動(dòng)性能預(yù)先確定的最大拐彎角范圍內(nèi)轉(zhuǎn)彎。

3) 最大爬升、俯沖角:無(wú)人機(jī)只能在小于或等于由自身垂直平面機(jī)動(dòng)性預(yù)先確定的上升和下滑的最大角度內(nèi)爬升或俯沖。

4) 最大航跡長(zhǎng)度:無(wú)人機(jī)的規(guī)劃航跡的長(zhǎng)度必須小于或等于一個(gè)預(yù)先設(shè)置的最大距離,它由無(wú)人機(jī)所攜帶的燃料以及指定任務(wù)中到達(dá)目標(biāo)的允許飛行時(shí)間決定。

5) 最低飛行高度:無(wú)人機(jī)利用地形進(jìn)行地形回避和威脅回避時(shí),需要盡可能在離地面低的高度上飛行,但是飛得過(guò)低往往會(huì)增加與地面的相撞概率。一般在保持離地高度不小于某一指定高度的前提下,使飛行高度盡量降低。

只有滿足了以上基本約束條件的三維航跡才是無(wú)人機(jī)的三維可行航跡。本文將這些約束條件結(jié)合到基本RRT算法中,從而得到一種快速有效的無(wú)人機(jī)三維航跡規(guī)劃方法。

2基于RRT方法的三維航跡規(guī)劃

基于RRT方法的航跡規(guī)劃以狀態(tài)空間中的規(guī)劃起始點(diǎn)為根節(jié)點(diǎn),通過(guò)隨機(jī)采樣逐漸增加葉節(jié)點(diǎn)的方式生成隨機(jī)擴(kuò)展樹(shù)。當(dāng)隨機(jī)樹(shù)的葉節(jié)點(diǎn)中包含了目標(biāo)點(diǎn)或者目標(biāo)區(qū)域的點(diǎn)時(shí),隨機(jī)樹(shù)的擴(kuò)展停止,便可在隨機(jī)樹(shù)中找到一條以根節(jié)點(diǎn)組成的從起始點(diǎn)到目標(biāo)點(diǎn)的路徑。RRT的擴(kuò)展方式如圖1所示。

圖1　RRT算法的擴(kuò)展過(guò)程

圖1中T表示當(dāng)前存在的擴(kuò)展樹(shù),qrand表示狀態(tài)空間中的隨機(jī)采樣點(diǎn),qnear表示離隨機(jī)采樣點(diǎn)qrand最近的一個(gè)樹(shù)節(jié)點(diǎn),然后在qrand和qnear的連線上以擴(kuò)展步長(zhǎng)step為單位截取一個(gè)新節(jié)點(diǎn)qnew,如果在向新節(jié)點(diǎn)qnew行進(jìn)的過(guò)程中沒(méi)有碰到障礙物,則將應(yīng)qnew加入到擴(kuò)展樹(shù)中,否則需要重新選擇為qrand。繼續(xù)迭代計(jì)算直到qnew到達(dá)目標(biāo)區(qū)域則算法結(jié)束,此時(shí)可以在擴(kuò)展樹(shù)T中找到一條從起點(diǎn)qstart到目標(biāo)點(diǎn)qgoal的路徑。

RRT算法主要包括3個(gè)部分:采樣點(diǎn)選擇;搜索擴(kuò)展樹(shù)上距采樣點(diǎn)最近的節(jié)點(diǎn);擴(kuò)展節(jié)點(diǎn)。下面將從這3個(gè)部分,結(jié)合無(wú)人機(jī)的性能約束和地形高程數(shù)據(jù),將RRT方法引入到無(wú)人機(jī)三維航跡規(guī)劃。

2.1采樣點(diǎn)選擇

采樣點(diǎn)qrand的選擇不僅影響航跡質(zhì)量,而且影響規(guī)劃速度。三維航跡規(guī)劃中采樣點(diǎn)的隨機(jī)選取原則如下:以概率p選擇目標(biāo)點(diǎn)作為采樣點(diǎn);以概率1-p在整個(gè)規(guī)劃窗口內(nèi)隨機(jī)選擇采樣點(diǎn)。對(duì)于隨機(jī)采樣點(diǎn),根據(jù)采樣點(diǎn)的在水平面的位置信息可以查詢(xún)到采樣點(diǎn)的高程信息。令隨機(jī)采樣點(diǎn)在水平面的投影坐標(biāo)為(xrand,yrand),則隨機(jī)采樣點(diǎn)的高程信息為z(xrand,yrand)。令無(wú)人機(jī)的最低飛行高度約束為Hmin,則隨機(jī)采樣點(diǎn)的三維坐標(biāo)為qrand=(xrand,yrand,z(xrand,yrand)+Hmin)。

2.2節(jié)點(diǎn)擴(kuò)展

通過(guò)隨機(jī)采樣點(diǎn)qrand,可以找出已存在擴(kuò)展樹(shù)T的樹(shù)節(jié)點(diǎn)q中離隨機(jī)采樣點(diǎn)距離最近的一個(gè)樹(shù)節(jié)點(diǎn)qnear,使得

(2)

在qnear和qrand的連線上,計(jì)算從qnear以最小航跡段長(zhǎng)度L到達(dá)的新點(diǎn)qnew

(3)

令qnew的坐標(biāo)為(xnew,ynew,znew),qnear的坐標(biāo)為(xnear,ynear,znear),qnear的根節(jié)點(diǎn)為qnear-root(xnear-root,ynear-root,znear-root)。qnew必須滿足避障和無(wú)人機(jī)自身性能約束的條件下才能加入到擴(kuò)展樹(shù)T中。

1) 最大拐彎角約束

如圖2所示,令航跡段qnear-rootqnear和qnearqnew的水平投影分別為

設(shè)最大允許拐彎角為θ,則qnew必須滿足

(4)

圖2　拐彎角約束示意圖

2) 最大爬升/俯沖角約束

如圖3所示,航跡段qnearqnew的坐標(biāo)為

設(shè)最大爬升、俯沖角為φ,則qnew必須滿足

(5)

圖3　爬升角約束示意圖

3) 最大航跡長(zhǎng)度

最大航跡長(zhǎng)度是無(wú)人機(jī)的航跡距離約束,它取決于無(wú)人機(jī)的燃料載荷和任務(wù)執(zhí)行時(shí)間的限制,記為dmax。節(jié)點(diǎn)擴(kuò)展過(guò)程中長(zhǎng)度大于這個(gè)距離的航跡認(rèn)為是無(wú)效航跡,新節(jié)點(diǎn)為無(wú)效點(diǎn)。該約束在二維空間的投影表示如圖4所示。新的擴(kuò)展節(jié)點(diǎn)qnew,通過(guò)追溯根節(jié)點(diǎn)得到從起始點(diǎn)到qnew的航跡距離為D(qnew),圖中黑色粗實(shí)線航跡。SL(qnew)是從擴(kuò)展節(jié)點(diǎn)qnew到目標(biāo)點(diǎn)qgoal的歐氏距離。只有當(dāng)滿足D(qnew)+SL(qnew)≤dmax時(shí),才能把qnew加入到已有的擴(kuò)展樹(shù)T中。

圖4　最大航跡長(zhǎng)度約束

2.3冗余擴(kuò)展點(diǎn)剪裁

由于RRT方法是一種隨機(jī)方法。在RRT方法產(chǎn)生的可行航跡中可能會(huì)包含冗余的節(jié)點(diǎn)。去除冗余的航跡節(jié)點(diǎn),可以縮短無(wú)人機(jī)的航跡長(zhǎng)度,減少無(wú)人機(jī)的機(jī)動(dòng)次數(shù)。

設(shè)經(jīng)過(guò)RRT方法求得的可行路徑的節(jié)點(diǎn)序列為{wp1,…,wpn},其中wpn為目標(biāo)點(diǎn)位置。記經(jīng)過(guò)冗余節(jié)點(diǎn)剪裁后的節(jié)點(diǎn)序列為φ,φ初始為空。令j=n,首先將目標(biāo)點(diǎn)wpj添加到φ中。對(duì)于i∈[1,…j-1],循環(huán)檢查(wpj,wpi)之間的連線是否存在障礙或者威脅,是否存在不滿足無(wú)人機(jī)自身性能約束的情況。如果存在,則令i=i+1;否則,只要檢測(cè)出第一個(gè)不違背條件的節(jié)點(diǎn)wpi就停止循環(huán),令j=i,并將wpi添加到φ中。重復(fù)上述循環(huán),直到j(luò)=1時(shí)結(jié)束。

2.4算法描述

基于RRT方法的三維航跡規(guī)劃算法的具體步驟如下:

1) 以無(wú)人機(jī)當(dāng)前位置作為規(guī)劃起始點(diǎn)qstart,初始化搜索樹(shù)T。

2) 以概率p選擇目標(biāo)點(diǎn)作為采樣點(diǎn);以概率1-p在整個(gè)規(guī)劃窗口內(nèi)隨機(jī)選擇采樣點(diǎn)qrand。

3) 通過(guò)隨機(jī)采樣點(diǎn)qrand,找出已存在擴(kuò)展樹(shù)T的樹(shù)節(jié)點(diǎn)q中離隨機(jī)采樣點(diǎn)距離最近的一個(gè)樹(shù)節(jié)點(diǎn)qnear。在qnear和qrand的連線上,計(jì)算從qnear以最小航跡段長(zhǎng)度L到達(dá)的新點(diǎn)qnew。

4) 判斷qnew是否滿足避障和文中所述無(wú)人機(jī)自身性能約束,若滿足,則將qnew加入到擴(kuò)展樹(shù)T中。否則轉(zhuǎn)到步驟 2)。

5) 判斷|qnew-qgoal|≤L,若滿足,轉(zhuǎn)到步驟6),否則轉(zhuǎn)到步驟 2)。

6) 通過(guò)形成的擴(kuò)展樹(shù)T,獲得從起始點(diǎn)qstart到終點(diǎn)qnear的可行路徑。

7) 對(duì)冗余航跡節(jié)點(diǎn)進(jìn)行剪裁,得到最終航跡。

3數(shù)字地圖數(shù)據(jù)的模擬

通過(guò)對(duì)實(shí)際地形的研究,一定范圍內(nèi)的地形特性,可以通過(guò)地形高度均值、地形起伏的均方差及地形點(diǎn)之間的抗相關(guān)系數(shù)來(lái)描述[21]。

地形的高程可以表示為

(6)

式中,H(x,y)為(x,y)點(diǎn)的實(shí)際高度;H0為該地區(qū)的平均高度;Z(x,y)為地形平均高度基礎(chǔ)上的地形起伏高度。

3.1隨機(jī)地形的模擬

實(shí)際地形的起伏可以表征為高斯分布的隨機(jī)序列。文中采用通用的兩維一階離散自遞推過(guò)程進(jìn)行求解,即

(7)

(8)

(9)

(10)

式中，Std為地形起伏高度的均方差;τxc和τyc分別為x方向和y方向上的抗相關(guān)距離。

兩維離散自遞推過(guò)程需要有2個(gè)一維隨機(jī)過(guò)程產(chǎn)生該地區(qū)隨機(jī)地形在x方向和y方向上的地形邊界的初始條件,即

(11)

(12)

(13)

(14)

(15)

(16)

3.2山峰的模擬

文中使用多項(xiàng)式產(chǎn)生地形數(shù)據(jù),模擬山峰地形:

式中，Zi為基準(zhǔn)地形高度Z0上的第i個(gè)山峰的高度;x0i、y0i是第i個(gè)山峰的坐標(biāo);xsi、ysi分別是與第i座山沿x方向和y方向上的與坡度有關(guān)的量。

4仿真實(shí)驗(yàn)

4.1仿真參數(shù)設(shè)置

基于上述算法設(shè)計(jì),在Intel 2.5 GHz 主頻,8GB內(nèi)存的普通PC機(jī)上使用MATLAB編程進(jìn)行算法仿真實(shí)驗(yàn)。無(wú)人機(jī)執(zhí)行任務(wù)區(qū)域的地形為1 001×1 001(無(wú)量綱)大小的由上述數(shù)字地圖的模擬算法生成的虛擬三維地形圖和模擬威脅地圖。地形高度均值為0;地形起伏方差為50;該地形在x方向和y方向上抗相關(guān)距離均為300。5座模擬山峰在坐標(biāo)(400,500)、(600,800)、(600,200)、(350,200)和(300,300)處,山峰高度分別為450、300、400、400和300;1個(gè)模擬湖泊位于坐標(biāo)(500,100)處,深度為150;2個(gè)防空導(dǎo)彈威脅區(qū)位于坐標(biāo)(330,750)和(750,500)處,用半球體表示,球體半徑均為200。無(wú)人機(jī)的最大轉(zhuǎn)彎角為60°;最大爬升/俯沖角為30°;最低飛行高度為50;最小航跡段長(zhǎng)度為100。

4.2仿真結(jié)果

圖5～圖6和表1顯示了規(guī)劃起始點(diǎn)坐標(biāo)為(10,10,49),目標(biāo)點(diǎn)坐標(biāo)為(900,900,0)進(jìn)行的試驗(yàn)1的結(jié)果。圖5中最大航跡約束dmax取值為起始點(diǎn)到目標(biāo)點(diǎn)的直線距離S的1.3倍;而圖6中采用一個(gè)較大的dmax,取值為起始點(diǎn)到目標(biāo)點(diǎn)的直線距離S的2倍。圖中a)為規(guī)劃航跡的三維顯示結(jié)果。b)為規(guī)劃航跡航路點(diǎn)的高度與該點(diǎn)地形高度對(duì)比。圖7、圖8和表2顯示了規(guī)劃起始點(diǎn)坐標(biāo)為(10,900,49),目標(biāo)點(diǎn)坐標(biāo)為(900,10,50)進(jìn)行的試驗(yàn)2的結(jié)果。

表1　試驗(yàn)1數(shù)據(jù)

圖5　試驗(yàn)1中采用小dmax值規(guī)劃的結(jié)果　　　　圖6　試驗(yàn)1中采用較大dmax值規(guī)劃的結(jié)果

圖7　試驗(yàn)2中采用小dmax值規(guī)劃的結(jié)果　　　　　圖8　試驗(yàn)2中采用較大dmax值規(guī)劃的結(jié)果

最大航跡長(zhǎng)度擴(kuò)展節(jié)點(diǎn)數(shù)規(guī)劃航跡長(zhǎng)度節(jié)點(diǎn)未處理冗余剪裁1.3S1636.3571597.91385.92S2517.4471799.31578.6

實(shí)驗(yàn)結(jié)果表明，基于RRT方法的三維航跡規(guī)劃算法對(duì)于不同的規(guī)劃起始點(diǎn)和目標(biāo)點(diǎn)均能夠快速地規(guī)劃出滿足地形、威脅回避和無(wú)人機(jī)自身性能約束條件的可行航跡，通過(guò)對(duì)冗余節(jié)點(diǎn)的剪裁，可以去除不必要的航跡點(diǎn)，縮短了規(guī)劃航跡的長(zhǎng)度。對(duì)于相同的規(guī)劃起始點(diǎn)和目標(biāo)點(diǎn)，通過(guò)引入航跡距離約束，限制了生成路徑中可能的轉(zhuǎn)彎次數(shù)，減少了可擴(kuò)展節(jié)點(diǎn)，提高了搜索效率，同時(shí)以一定概率選擇目標(biāo)點(diǎn)作為采樣點(diǎn)來(lái)加強(qiáng)搜索過(guò)程中的啟發(fā)信息，搜索樹(shù)將沿著路徑距離最短的近似最優(yōu)航跡的方向進(jìn)行擴(kuò)展。該算法克服了基本RRT方法隨機(jī)性強(qiáng)，只能快速獲得可行航跡，無(wú)法獲得較優(yōu)航跡的缺點(diǎn)。

5結(jié)論

本文針對(duì)無(wú)人機(jī)自主航跡規(guī)劃的實(shí)時(shí)性問(wèn)題，提出了基于RRT方法的三維快速航跡規(guī)劃算法。該算法繼承了RRT方法用于航跡規(guī)劃的快速性，同時(shí)將地形信息和無(wú)人機(jī)的自身性能約束結(jié)合到擴(kuò)展樹(shù)的節(jié)點(diǎn)擴(kuò)展中，使得規(guī)劃出來(lái)的航跡能夠滿足實(shí)戰(zhàn)要求。通過(guò)引入航跡距離約束，增加啟發(fā)信息克服搜索的隨機(jī)性，使得規(guī)劃出的可行航跡接近最優(yōu)航跡，有效地提高了無(wú)人機(jī)自主航跡規(guī)劃的時(shí)間性能，兼顧了航跡規(guī)劃的最優(yōu)性與實(shí)時(shí)性。

參考文獻(xiàn)：

[1]沈林成,牛軼峰,朱華勇. 多無(wú)人機(jī)自主協(xié)同控制理論與方法[M]. 北京: 國(guó)防工業(yè)出版社, 2013

Shen L C, Niu Z F, Zhu H Y. Theories and Methods of Autonomous Cooperative Control for Multiple UAVs[M]. Beijing, National Defense Industry Press, 2013: 109-110 (in Chinese)

[2]沈林成,陳璟,王楠. 飛行器任務(wù)規(guī)劃技術(shù)綜述[J]. 航空學(xué)報(bào), 2014, 35(3): 593-606

Shen L C, Chen J, Wang N. Overview of Air Vehicle Mission Planning Techniques[J]. Acta Aeronoutica et Astronautica Sinica, 2014, 35(3): 593-606 (in Chinese)

[3]Zheng C W, Ding M Y, Zhou C P. Real-Time Route Planning for Unmanned Air Vehicle with An Evolutionary Algorithm[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2003, 17(1): 63-81

[4]何珮,屈香菊,武哲. 應(yīng)用自適應(yīng)遺傳算法進(jìn)行參考航跡規(guī)劃[J]. 航空學(xué)報(bào), 2003, 24(6): 499-502

He P, Qu X J, Wu Z. Aircraft Referenced Flight Path Planning by Using Adaptive Genetic Algorithms[J]. Acta Aeronoutica et Astronautica Sinica, 2003, 24(6): 499-502 (in Chinese)

[5]Chen M, Wu Q X, Jiang C S. A Modified Ant Optimization Algorithm for Path Planning of UCAV[J]. Applied Soft Computation, 2008, 8(4): 1712-1718

[6]Duan H B, Zhang X Y, Wu J. Max-Min Adaptive Ant Colony Optimization Approach to Multi-UAVs Coordinated Trajectory Replanning in Dynamic and Uncertain Environments[J]. Journal of Bionic Engineering, 2009, 6(2): 161-173

[7]李春華,鄭昌文,周成平. 一種三維航跡快速搜索方法[J]. 宇航學(xué)報(bào), 2002, 23(3):13-16

Li C H, Zheng C W, Zhou C P. Fast Search Algorithm for 3D-Route Planning[J]. Journal of Astronautics, 2002, 23(3): 13-16 (in Chinese)

[8]Wang Z, Liu L, Long T. Enhanced Sparse A*Search for UAV Path Planning Using Dubins Path Estimation[C]∥Proceedings of the 33rdChinese Control Conference, Nanjing, 2014: 738-742

[9]Li S B, Sun X X, Xu Y J. Particle Swarm Optimization for Route Planning of Unmanned Air Vehicles[C]∥Proceedings of the Congress on Information Acquisition. Weihai, 2006: 1213-1218

[10] Fu Y G, Ding M Y, Zhou C P. Routing Planning for Unmanned Aerial Vehicle(UAV) on the Sea Using Hybrid Differential Evolution and Quantum-Behaved Particle Swarm Optimization[J]. IEEE Trans on Systems, Man, and Cybernetics: Systems, 2013,43(6): 1451-1465

[11] LaValle S M. Rapidly-Exploring Random Trees: A New Tool for Path Planning[R]. Computer Science Department, Iowa State University, 1998

[12] 周金良,黃彥文,曹其新. 對(duì)抗環(huán)境下足球機(jī)器人路徑規(guī)劃[J]. 上海交通大學(xué)學(xué)報(bào), 2006,40(11):1827-1831

Zhou J L, Huang Y W, Cao Q X. The Path Planning for Robot Soccer Under Antagonistic Environment[J]. Journal of Shanghai Jiaotong University, 2006,40(11): 1827-1831 (in Chinese)

[13] Amin J N, Boskovic J D, Mehra R K. A Fast and Efficient Approach to Path Planning for Unmanned Vehicles[C]∥Proceedings of AIAA Guidance, Navigation and Control Conference and Exhibit. Keystone, 2006

[14] Kuffner J J, LaValle S M. RRT-Connect: An Efficient Approach to Single-Query Path Planning[C]∥Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, 2000:995-1001

[15] Kalisiak M, Panne M. RRT-Blossom: RRT with a Local Flood-Fill Behavior[C]∥Proceedings of the 2006 IEEE International Conference on Robotics and Automation, Florida, 2006: 1237-1242

[16] Melchior N A, Simmons R. Particle RRT for Path Planning with Uncertainty[C]∥Proceedings of the IEEE International Conference on Robotics and Automation, Roma, 2007: 1617-1624

[17] 彭輝,王林,沈林成. 區(qū)域搜索中基于改進(jìn)RRT的UAV實(shí)時(shí)航跡規(guī)劃[J]. 國(guó)防科學(xué)技術(shù)大學(xué)學(xué)報(bào), 2009, 31(5): 86-91

Peng H, Wang L, Shen L C. The Modified RRT-Based Real-Time Route Planning for UAV Area Target Searching[J]. Journal of National University of Defense Technology, 2009, 31(5): 86-91 (in Chinese)

[18] Bruce J, Veloso M. Real-Time Randomized Path Planning for Robot Navigation[C]∥Proceedings of the IEEE International Conference on Intelligent Robots and Systems, Lausanne, 2002: 2383-2388

[19] Yershova A, Jaillet L, Simeon T. Dynamic-Domain RRTs: Efficient Exploration by Controlling the Sampling Domain[C]∥Proceedings of the IEEE International Conference on Robotics and Automation, Barcelona, 2005: 3851-3861

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

Ding M Y, Zheng C W, Zhou C P, Yan P. Route Planning for Unmanned Aerial Vehicles[M]. Beijing, Publishing House of Electronics Industry, 2009: 41-43 (in Chinese)

[21] 葉文,范洪達(dá),朱愛(ài)紅. 無(wú)人飛行器任務(wù)規(guī)劃[M]. 北京: 國(guó)防工業(yè)出版社, 2011

Ye W, Fan H D, Zhu A H. Mission Planning for Unmanned Aerial Vehicles[M]. Beijing, National Defense Industry Press, 2011: 42-47 (in Chinese)

Efficient Path Planning Algorithm in Three Dimensions for UAV

Yin Gaoyang, Zhou Shaolei, Wu Qingpo

(Department of Control Engineering, Naval Aeronautical and Astronautical University, Yantai 264001, China)

Abstract:To satisfy the real-time requirement of path planning in three dimensions for unmanned aerial vehicle, a path planning algorithm based on rapidly-exploring random tree is proposed. By random sampling point in configuration space, the search will be guided to empty area, thus the algorithm can search the high-dimension space quickly and efficiently according to the current environment, which can be used in real-time path planner. By introducing the path length constraint, the search tree will explore along the direction of the near optimal path. The proposed algorithm overcomes the disadvantage of basic RRT algorithm that only to quickly get feasible path, unable to obtain near optimal path. During the search process, the path constraints of UAV and the terrain information are fully utilized, so that the path generated by the algorithm can avoid terrain and threat automatically, and meet the dynamic constraints of UAV. Simulations for the algorithm are made on a generated virtual digital map. Simulation results demonstrated that this proposed method can complete path planning mission in three dimensions quickly and effectively.

Keywords:unmanned aerial vehicle (UAV); rapidly-exploring random tree; real-time; terrain avoidance; 3D-path

收稿日期：2016-02-12

基金項(xiàng)目：航空科學(xué)基金(20135184007)資助

作者簡(jiǎn)介：尹高揚(yáng)(1987—)，海軍航空工程學(xué)院博士研究生,主要從事導(dǎo)航、制導(dǎo)與控制的研究。

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

文獻(xiàn)標(biāo)志碼：A

文章編號(hào):1000-2758(2016)04-0564-07