動態(tài)步長BI-RRT的無人機(jī)航跡規(guī)劃算法

武曉晶　許磊　甄然　吳學(xué)禮

摘 要：為解決傳統(tǒng)RRT算法收斂速度慢、生成的航徑距離過長等問題，提出動態(tài)步長BI-RRT算法。首先，采用引向目標(biāo)的采樣策略對空間進(jìn)行探索以得到采樣點，利用動態(tài)步長策略確定該采樣點的增長步長以確定新節(jié)點;之后，通過樹枝裁剪策略對新節(jié)點進(jìn)行調(diào)整，當(dāng)探索到目標(biāo)節(jié)點時，算法返回初始航跡，對于初始航跡，應(yīng)用貪心算法對航跡點進(jìn)行篩選，以減少無人機(jī)（UAV）的無效節(jié)點與總航跡長度;最后，利用B樣條進(jìn)行平滑處理，得到一條可行航跡。搭建了二維和三維環(huán)境下的仿真地圖模型，驗證了該算法在保證無人機(jī)避障的基礎(chǔ)上獲得一條有效航跡。動態(tài)步長BI-RRT算法在無人機(jī)航跡規(guī)劃方面不僅有實時性強(qiáng)、航跡光滑的優(yōu)點，而且與分段優(yōu)化RRT算法相比，在優(yōu)化航跡節(jié)點個數(shù)的前提下，提高了收斂速度且降低了航跡距離。

關(guān)鍵詞：航空、航天科學(xué)技術(shù)基礎(chǔ)學(xué)科其他學(xué)科;雙向快速擴(kuò)展隨機(jī)樹（BI-RRT）;概率搜索;引向目標(biāo)動態(tài)步長;樹枝裁剪策略

中圖分類號：TP273;V279+.2 文獻(xiàn)標(biāo)志碼：A

doi：10.7535/hbkd.2019yx05005

Dynamic step BI-RRT UAV path planning algorithm

WU Xiaojing1，2， XU Lei1， ZHEN Ran1，2， WU Xueli1，2

（1.School of Electrical Engineering， Hebei University of Science and Technology， Shijiazhuang， Hebei 050018， China; 2.Hebei Engineering Technology Research Center of Production Process Automation， Shijiazhuang， Hebei 050018， China）

Abstract：To solve the problems of traditional RRT algorithm， such as slow convergence and long path length， the dynamic step BI-RRT algorithm is proposed. The sampling efficiency of the RRT algorithm is improved by using a target-oriented sampling strategy. The dynamic step algorithm improves the local smoothness of the path in the obstacle environment. A new tree cutting strategy is proposed to make the growth trend of random trees more obvious and improve the convergence rate of the algorithm. For the initial path， the path nodes are filtered by applying greedy algorithm to reduce the invalid nodes and path length of the unmanned aerial vehicle （UAV）. Finally， a feasible smooth path is obtained by using B-Spline. The simulation maps in 2D and 3D environment are built to verify the effectiveness of the algorithm. Compared to the segmentated optimization RRT algorithm， the dynamic step BI-RRT algorithm proposed in this paper improves the convergence rate and reduces the path distance， while ensuring that the number of path nodes is optimal. This path planning algorithm has some advantages such as good real-time performance and smoothness of path.

Keywords：basic science and technology of aeronautics and astronautics other disciplines; bidirectional rapidly-exploring random tree （BI-RRT）; probability search; target oriented dynamic step size; branch cutting strategy

近年來，隨著無人機(jī)在現(xiàn)場救援、地形探測等方面的應(yīng)用，航跡規(guī)劃已成為無人機(jī)技術(shù)的一個重要領(lǐng)域[1]。無人機(jī)航跡規(guī)劃是在考慮無人機(jī)自身運動品質(zhì)與地域環(huán)境等約束條件下，計算出品質(zhì)最佳的航跡。航跡的安全性、平滑度和最短航距等多種動態(tài)約束對智能算法提出了更大的挑戰(zhàn)。

傳統(tǒng)的航跡規(guī)劃算法包括A*算法[2]、蟻群算法[3]、人工勢場法[4]、神經(jīng)網(wǎng)絡(luò)算法[5]，但這些離散化算法均存在收斂速度較慢、難以應(yīng)用在高維的復(fù)雜環(huán)境中、需要已知空間模型、針對未知環(huán)境會出現(xiàn)失效等問題。RRT算法具有快速性與強(qiáng)大的空間探索能力，可通過隨機(jī)采樣拓展解空間，區(qū)別于依賴已知障礙物的傳統(tǒng)算法，RRT算法不需要依賴于環(huán)境建模就能夠有效解決未知復(fù)雜障礙物空間和高維動態(tài)環(huán)境的航跡規(guī)劃問題[6]。

基于RRT算法，研究人員在路徑規(guī)劃方面做了大量工作。其中，文獻(xiàn)[7]在隨機(jī)樹節(jié)點增長過程中融入無人機(jī)動力學(xué)約束條件，優(yōu)化了節(jié)點配置。文獻(xiàn)[8]通過引入基于障礙物的動態(tài)步長算法，解決了固定步長引起的局部極小問題。文獻(xiàn)[9]改進(jìn)了隨機(jī)配置節(jié)點的機(jī)制，避免了路徑上的冗余節(jié)點，減少路徑上生長的節(jié)點，降低規(guī)劃成本，避免了對空間的過度搜索。文獻(xiàn)[10]和文獻(xiàn)[11]針對大規(guī)模以及復(fù)雜環(huán)境下收斂速度過慢的問題提出PB-RRT*和Quad-RRT算法，在提高算法收斂速度的同時更有效地利用了內(nèi)存。針對隨機(jī)采樣機(jī)制導(dǎo)致的路徑不平滑問題，文獻(xiàn)[12]利用四次樣條策略生成平滑路徑。

在無人機(jī)航跡規(guī)劃方面，文獻(xiàn)[13]采用冗余節(jié)點裁剪策略減小航線長度，但未充分利用RRT算法在高維空間的探索能力。文獻(xiàn)[14]通過無人機(jī)間共享威脅信息，測試航跡規(guī)劃的實時性，但未考慮規(guī)劃航跡的可飛性與平滑性。文獻(xiàn)[15]提出了分段優(yōu)化RRT的無人機(jī)動態(tài)規(guī)劃算法，加快了無人機(jī)航跡規(guī)劃速度，縮短了航跡距離，但在復(fù)雜環(huán)境下規(guī)劃效果難以保證。以上文獻(xiàn)雖都基于RRT算法做出無人機(jī)航跡規(guī)劃的優(yōu)化，但均在二維環(huán)境下進(jìn)行驗證，未涉及三維環(huán)境，實用方面具有局限性。目前，RRT算法在三維環(huán)境進(jìn)行航跡規(guī)劃的應(yīng)用還非常有限[16-17]。

本文提出了動態(tài)步長BI-RRT算法與一種新的樹枝裁剪策略，并通過無人機(jī)航跡規(guī)劃仿真實驗對該算法進(jìn)行驗證。

1 無人機(jī)航跡規(guī)劃問題

1.1 航跡規(guī)劃問題描述

無人機(jī)航跡規(guī)劃問題旨在復(fù)雜環(huán)境中于起始點與終止點之間尋找一條滿足約束條件的航跡[18]。其中障礙物區(qū)域設(shè)定為靜態(tài)，即認(rèn)為是建筑物或山體。對于非完整約束條件下實現(xiàn)近似最優(yōu)解的問題，大多算法都停留于二維環(huán)境。RRT算法對于高維與動態(tài)環(huán)境具有很高的探索效率與適應(yīng)性。

1.2 二維環(huán)境模型

二維隔斷式地圖如圖1所示。用黑色像素代表障礙物區(qū)域，白色像素代表自由區(qū)域。通過建立隔斷式地圖對算法進(jìn)行測試。

1.3 三維環(huán)境模型

無人機(jī)三維環(huán)境下航跡規(guī)劃空間環(huán)境可以表示為點集{（x，y，z）|xmin≤x≤xmax，ymin≤y≤ymax，zmin≤z≤zmax}，其中x，y表示無人機(jī)在水平面投影的坐標(biāo)，z表示海拔高度。通過連接航跡點{Pinit，P2，…，Pgoal}，生成無人機(jī)規(guī)劃的航跡。對于無人機(jī)的飛行環(huán)境，用圓錐體近似表示山體，實現(xiàn)對現(xiàn)實環(huán)境空間的建模，通過指數(shù)函數(shù)生成多個不同的圓錐體并進(jìn)行疊加形成山體[19]。考慮z=0平面作為參考海拔，山體建模如式（1）所示：

式中：h0為空間基準(zhǔn)高度;hk為第k座山峰的高度;n為空間中山峰的個數(shù);x0k和y0k分別為第k座山峰中心點所對應(yīng)的坐標(biāo);xik和yik分別為第k座山峰對應(yīng)的橫向坡度與縱向坡度。

2 動態(tài)步長BI-RRT航跡規(guī)劃算法

2.1 BI-RRT算法

BI-RRT通過實現(xiàn)2棵隨機(jī)樹的初始化和生長，完成對空間的高效探索。第1棵樹T1以起始點為根節(jié)點，朝著第2顆樹生長。第2棵樹T2以目標(biāo)點為根節(jié)點，朝著第1棵樹生長。當(dāng)兩棵樹的葉子節(jié)點相同或距離小于一個步長時，認(rèn)為完成航跡規(guī)劃。BI-RRT算法的流程如表1所示。

2.2 動態(tài)步長BI-RRT算法

2.2.1 基于引向目標(biāo)的偏向性算法優(yōu)化原理

針對隨機(jī)樹探索過程中擴(kuò)展效率低、收斂速度慢的問題，在BI-RRT算法的結(jié)構(gòu)上進(jìn)行改進(jìn)。通過配置引力因子，削弱隨機(jī)采樣機(jī)制。在隨機(jī)采樣過程中，根據(jù)引力因子的值來決定隨機(jī)樹的生長方向，降低采樣過程的隨機(jī)性。引力因子以一定的概率配置隨機(jī)節(jié)點Xrand與目標(biāo)點Xgoal的關(guān)系，使得Xrand=Xgoal，隨機(jī)樹以一定趨勢朝目標(biāo)生長，減少隨機(jī)采樣的規(guī)劃過程。引向目標(biāo)的采樣策略保證隨機(jī)樹在充分探索空間的同時提高收斂速度。

2.2.2 動態(tài)步長優(yōu)化策略

BI-RRT算法通過對整個解空間進(jìn)行規(guī)劃，構(gòu)建從起始點Xinit朝向目標(biāo)點Xgoal生長的可行路徑樹T1。通過迭代生長，生成隨機(jī)節(jié)點Xrand，同時找到在T1上與之最近的節(jié)點Xnear，再以固定步長S向XnearXrand方向進(jìn)行生長，生成新節(jié)點Xnew。檢測Xnew是否在地圖內(nèi)且在障礙物區(qū)域外，直到搜索到第2棵樹T2。更新新節(jié)點Xnew的計算公式如式（2）所示。

固定步長增長機(jī)制導(dǎo)致隨機(jī)樹遇到障礙物時，生成的航跡不平滑，使無人機(jī)產(chǎn)生過多無效動作。針對這一問題，本文算法提出一種動態(tài)步長策略?；舅枷耄涸O(shè)定一個閾值q，表示無人機(jī)與障礙物之間的最小安全距離。當(dāng)無人機(jī)與障礙物之間距離d大于或等于閾值，認(rèn)為無人機(jī)處于空曠空間，此時以固定步長進(jìn)行生長探索。當(dāng)無人機(jī)與障礙物之間距離d小于閾值時，認(rèn)為無人機(jī)處于障礙物環(huán)境，此時動態(tài)縮短步長S，以保證航跡的平滑性。動態(tài)步長的數(shù)學(xué)描述如式（3）所示：

式中：d≥q時，表示空曠環(huán)境下隨機(jī)樹的固定增長步長，通過選取較大步長，加快航跡規(guī)劃收斂速度;d

2.3 半角樹枝裁剪策略

BI-RRT算法對整個規(guī)劃空間進(jìn)行隨機(jī)采樣，雖有利于航跡點在解空間中的均勻分布，但部分?jǐn)U展區(qū)域?qū)σ?guī)劃并沒有實質(zhì)性幫助，反而降低了收斂速度。因此，本文提出一種半角樹枝裁剪策略，半角樹枝裁剪策略原理圖如圖2所示。

BI-RRT算法樹枝增長原理：基于隨機(jī)點Xrand，找到樹上T1與之最近頂點Xnear，再通過預(yù)設(shè)步長S生成Xnew。由于隨機(jī)采樣機(jī)制會出現(xiàn)采樣域偏離，使得隨機(jī)樹出現(xiàn)“逆向生長”，導(dǎo)致收斂速度降低。半角樹枝裁剪策略通過及時更新向量XnearXnew與向量XnearXgoal之間的角度α，保證航跡點可以探索空間的同時，加快規(guī)劃速度。裁剪公式如式（4）所示：

式中：當(dāng)角度α滿足0≤α<90°時，認(rèn)為Xnew滿足規(guī)劃約束條件，進(jìn)行保留;當(dāng)角度α滿足90°≤α≤180°時，通過半角樹枝裁剪策略對其進(jìn)行修剪。其原理是以Xnear為軸心，S為軸長，將向量XnearXnew朝向量XnearXgoal旋轉(zhuǎn)[SX（]α[]2[SX）]角度，獲得修剪后的新節(jié)點X′new。

2.4 基于貪心算法優(yōu)化成本函數(shù)

貪心算法是作出基于當(dāng)前狀態(tài)的最優(yōu)選擇。其原理為不從整體進(jìn)行最優(yōu)考慮，而是選擇某種意義上的局部最優(yōu)解。貪心算法通過每一步最優(yōu)選擇，最終使得整體解不斷接近最優(yōu)解。由于BI-RRT算法隨機(jī)采樣的特性，盡管通過引向目標(biāo)的優(yōu)化算法進(jìn)行偏向性增長，但依然會產(chǎn)生很多曲折的路徑與無效動作?？紤]到無人機(jī)自身性能約束，大量無效動作會增加無人機(jī)的不穩(wěn)定性與能耗。針對這一問題提出基于貪心算法的最短路徑優(yōu)化思想。貪心啟發(fā)式算法與概率完備的BI-RRT隨機(jī)采樣特性相結(jié)合，很好地避免了局部極小的缺陷。

成本函數(shù)定義如式（5）所示：

式中Li表示航跡中相鄰2個節(jié)點Pi，Pi+1之間的距離。

貪心算法原理：首先導(dǎo)入已規(guī)劃得到的航跡節(jié)點，以第1個航跡點Pinit為優(yōu)化路徑的起點，每一次迭代挑選出距離起始點Pinit最近的后續(xù)節(jié)點Pnearest，并判斷其與Pinit的連線PnearestPinit[TX-]是否會與障礙物相交，若不相交，則認(rèn)為該節(jié)點Pnearest為無效節(jié)點，刪除該無效節(jié)點，并繼續(xù)檢查后續(xù)節(jié)點Pnearest。若經(jīng)過障礙物則保留該航跡點Pnearest，并以該航跡點為新起點繼續(xù)向后續(xù)節(jié)點發(fā)起貪心選擇，挑選離新起點最近的后續(xù)節(jié)點并檢查其連線是否會經(jīng)過障礙物，重復(fù)以上動作直到所有航跡點處理完畢?；谪澬倪x擇的優(yōu)化策略減少了規(guī)劃器得到的航跡點，降低了無人機(jī)規(guī)劃的復(fù)雜度，大大減少了無人機(jī)的無效動作與飛行距離。

2.5 基于B樣條的平滑處理

由于BI-RRT隨機(jī)采樣的機(jī)制，使得算法規(guī)劃的路徑呈現(xiàn)出不規(guī)則的折線，航跡不夠平滑、可飛性差。故需要作進(jìn)一步的平滑處理。

B樣條曲線具有設(shè)計自由型曲線曲面的強(qiáng)大功能。B樣條兼?zhèn)淞薆ezier方法的優(yōu)點，如仿射不變性，同時克服了Bezier方法由于整體表示所帶來的局限性。本文采用B樣條曲線擬合方法，針對航跡拐點部分進(jìn)行平滑處理，B樣條曲線方程如式（6）所示：

式中：di（i=0，1，…，n）為控制頂點坐標(biāo);Ni，k（i=0，1，…，n）為k次規(guī)范B樣條基函數(shù)，k為最高次數(shù);基函數(shù)是由1個節(jié)點矢量的非遞減參數(shù)u的序列U：u0≤u1≤…≤un+k+1所決定的k次分段多項式[20]。B樣條的基函數(shù)采用Cox-deBoor遞推公式：

Ni，0（u）=1，ui≤u≤ui+1，0，其他，

定義（7）

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

2.6 算法流程圖

動態(tài)步長BI-RRT算法的總體流程圖如圖3所示。

步驟1：隨機(jī)點選取。通過引向目標(biāo)的采樣策略，在整個解空間選取采樣點。

步驟2：隨機(jī)點的調(diào)整。對步驟1選取的節(jié)點判別是否需要進(jìn)行步長調(diào)整以滿足障礙物約束條件。若滿足約束條件，則以固定步長擴(kuò)展新節(jié)點;若不滿足，則動態(tài)調(diào)整步長并擴(kuò)展新節(jié)點。計算新節(jié)點與目標(biāo)點之間的偏離角度，根據(jù)角度判定條件對新節(jié)點進(jìn)行裁剪調(diào)整。

步驟3：航跡優(yōu)化。當(dāng)2棵隨機(jī)樹的葉子節(jié)點重合或相距1個步長，認(rèn)為找到航跡。對航跡節(jié)點進(jìn)行貪心選擇，得到最短航跡，并對其進(jìn)行平滑處理，獲得最終航跡。

3 實驗驗證

3.1 二維環(huán)境仿真

設(shè)置實驗空間尺寸為500 km×500 km，起始點坐標(biāo)設(shè)置為（0， 500），終點坐標(biāo)設(shè)置為（500， 0）。分別用RRT算法、分段優(yōu)化RRT算法、動態(tài)步長BI-RRT算法進(jìn)行50次仿真實驗，得到的結(jié)果如圖4所示。圖4中虛線部分表示算法生長的隨機(jī)樹，實線部分表示算法所得到的無人機(jī)航跡。其中，圖4 a）—c）分別代表傳統(tǒng)RRT算法、分段優(yōu)化RRT算法[15]和動態(tài)步長BI-RRT算法得到的結(jié)果。從路徑長度、航跡點數(shù)、規(guī)劃時間3方面對比得到的仿真實驗數(shù)據(jù)如表2所示。

數(shù)據(jù)分析如下。

從圖4可以看出，與傳統(tǒng)RRT算法和分段優(yōu)化RRT算法相比，本文所提出的動態(tài)步長BI-RRT算法在保證航跡平滑性的同時節(jié)約了擴(kuò)展空間。從表2可以看出，本文所提出的動態(tài)步長BI-RRT算法大大降低了規(guī)劃時間，縮短了路徑長度。

注1：傳統(tǒng)RRT算法基于全空間進(jìn)行航跡規(guī)劃，航跡距離過長、收斂速度過慢。分段優(yōu)化RRT算法[15]由于采用了面向目標(biāo)的采樣策略，使得規(guī)劃器在擴(kuò)展過程中節(jié)約了擴(kuò)展空間，但收斂速度較慢，依然有過多無效樹枝。而采用本文所提出的動態(tài)步長BI-RRT算法，通過2棵樹同時生長大大縮短了規(guī)劃時間，提高了航跡規(guī)劃的實時性，同時采用樹枝裁剪策略，使隨機(jī)樹的擴(kuò)展趨勢更加明顯。

注2：與文獻(xiàn)[15]相比，動態(tài)步長BI-RRT算法大大提高了航跡規(guī)劃的收斂速度與算法的偏向性，降低了成本函數(shù)。同時本文所提出的算法可推廣應(yīng)用到三維環(huán)境，解決三維環(huán)境下的航跡規(guī)劃問題，算法更具實用性。

3.2 三維環(huán)境仿真

規(guī)劃空間采用山峰威脅模型實現(xiàn)對現(xiàn)實環(huán)境的模擬。設(shè)置實驗空間尺寸為80 km×80 km×40 km，規(guī)劃空間中設(shè)置6座山峰，中心坐標(biāo)分別為（10，10），（40，25），（45，50），（60，30），（20，45），（20，10）。高度分別為20，35，25，38，20，25 km。威脅源主要為山體，起始點設(shè)置為[5，70，5]，終點設(shè)置為[80，30，10]，并對空間進(jìn)行建模，如圖5所示。

采用RRT算法與動態(tài)步長BI-RRT算法進(jìn)行50次仿真實驗，得到的三維航跡規(guī)劃結(jié)果如圖6所示。其中，傳統(tǒng)RRT算法在三維環(huán)境的規(guī)劃結(jié)果如圖6 a）所示;圖6 b）為本文所提出的算法得到的三維仿真結(jié)果。從路徑長度、航跡點數(shù)、規(guī)劃時間3方面得到對比數(shù)據(jù)，如表3所示。

從圖6和表3可以看出，本文所提出的算法在三維環(huán)境下仍然具有很好的收斂性，與傳統(tǒng)RRT算法對比，大大縮短了路徑長度和規(guī)劃時間，提高了飛行效率。

4 結(jié) 語

針對RRT算法隨機(jī)性過大、收斂速度較慢、搜索節(jié)點過多等問題，提出了動態(tài)步長BI-RRT的無人機(jī)航跡規(guī)劃算法，通過仿真實驗驗證了該算法的優(yōu)勢。與分段優(yōu)化RRT算法面向目標(biāo)的采樣策略相比，本文所提出的目標(biāo)引向策略和半角樹枝裁剪策略，提高了算法的采樣效率，縮短了航跡規(guī)劃的時間，加快了算法的收斂速度。同時，提出的動態(tài)步長策略提高了隨機(jī)樹對障礙物的敏感性。仿真數(shù)據(jù)表明，該算法得到的航跡具有航徑短、收斂速度快、可飛性強(qiáng)、內(nèi)存需求小等優(yōu)點。今后的研究中，將考慮動態(tài)障礙物綜合避險問題，并對此算法進(jìn)行優(yōu)化，以提高其動態(tài)性能。

參考文獻(xiàn)/References：

[1]MONTIEL O， OROZCO-ROSAS U， SEPULVEDA R. Path planning for mobile robots using Bacterial Potential Field for avoiding static and dynamic obstacles[J]. Expert Systems with Applications， 2015， 42（12）： 5177-5191.

[2]SONG Rui， LIU Yuanchang， BUCKNALL R. Smoothed A* algorithm for practical unmanned surface vehicle path planning[J]. Applied Ocean Research， 2019， 83： 9-20.

[3]PEREZ-CARABAZA S， BESADA-PORTAS E， LOPEZ-OROZCO J A， et al. Ant colony optimization for multi-UAV minimum time search in uncertain domains[J]. Applied Soft Computing， 2018， 62： 789-806.

[4]HU Hongyu， ZHANG Chi， SHENG Yuhuan， et al. An improved artificial potential field model considering vehicle velocity for autonomous driving[J]. IFAC-PapersOnLine， 2018， 51： 863-867.

[5]BHARADWAJ H， KUMAR E V. Comparative study of neural networks in path planning for catering robots[J]. Procedia Computer Science， 2018， 133： 417-423.

[6]王全， 王維， 李焱，等.基于混合策略的輪式機(jī)器人路徑規(guī)劃方法[J].計算機(jī)工程與應(yīng)用， 2014， 50（4）：45-49.

WANG Quan， WANG Wei， LI Yan， et al. Wheeled robot path planning method based on hybrid strategy[J]. Computer Engineering and Applications， 2014， 50（4）： 45-49.

[7]尹高揚， 周紹磊， 吳青坡.基于改進(jìn)RRT算法的無人機(jī)航跡規(guī)劃[J]. 電子學(xué)報， 2017， 45（7）：1764-1769.

YIN Gaoyang， ZHOU Shaolei， WU Qingpo. An improved RRT algorithm for UAV path planning[J]. Acta Electronica Sinica， 2017， 45（7）： 1764-1769.

[8]林娜， 張亞倫. 自適應(yīng)RRT無人機(jī)航路規(guī)劃算法研究與仿真[J]. 計算機(jī)仿真， 2015， 32（1）：73-77.

LIN Na， ZHANG Yalun. Research and simulation on adaptive RRT algorithm for UAVs path planning[J]. Computer Simulation， 2015， 32（1）： 73-77.

[9]ZHANG Haojian， WANG Yunkuan， ZHENG Jun， et al. Path planning of industrial robot based on improved RRT algorithm in complex environments[J]. IEEE Access， 2018：2871222.

[10]TAHIR Z， QURESHI A H， AYAZ Y， et al. Potentially guided bidirectionalized RRT* for fast optimal path planning in cluttered environments[J]. Robotics???? and Autonomous Systems， 2018， 108： 13-27.

[11]HIDALGO-PANIAGUA A， BANDERA J P， RUIZ-de-QUINTANILLA M， et al. Quad-RRT： A real-time GPU-based global path planner in large-scale real environments[J]. Expert Systems with Applications， 2018， 99： 141-154.

[12]JANJO? F， REICHART R， NIERMEYER P. Smooth path-generation aroud obstacles using quartic splines and RRTs[J]. IFAC-Papers-OnLine， 2017， 50： 9108-9113.

[13]李俊濤， 毛紅保， 張鵬，等.基于多優(yōu)化策略RRT的無人機(jī)實時航線規(guī)劃[J]. 火力與指揮控制， 2017， 42（12）：115-119.

LI Juntao， MAO Hongbao， ZHANG Peng， et al. Multi-optimization RRT based UAV real-time trajectory planning algorithm[J]. Fire Control & Command Control， 2017， 42（12）： 115-119.

[14]ZHENG Zheng， LIU Yang， ZHANG Xiaoyi. The more obstacle information sharing， the more effective real-time path planning？[J]. Knowledge-Based Systems， 2016， 114： 36-46.

[15]李文廣， 孫世宇， 李建增，等. 分段優(yōu)化RRT的無人機(jī)動態(tài)航跡規(guī)劃算法[J]. 系統(tǒng)工程與電子技術(shù)， 2018， 40（8）：1786-1793.

LI Wenguang， SUN Shiyu， LI Jianzeng， et al. UAV dynamic path planning algorithm based on segmentated optimization RRT[J]. Systems Engineering and Electronics， 2018， 40（8）： 1786-1793.

[16]WEN Naifeng， ZHAO Lingling， SU Xiaohong， et al. UAV online path planning algorithm in a low altitude dangerous environment[J]. IEEE/CAA Journal of Automatica Sinica， 2015， 2（2）： 173-185.

[17]RAMANA M V， VARMA S A， KOTHARI M. Motion planning for a fixed-wing UAV in urban environments[J]. IFAC-PapersOnLine，2016， 49： 419-424.

[18]劉華偉， 張帥， 趙搏欣，等. 改進(jìn)RRT算法陷阱空間下的無人機(jī)航跡規(guī)劃[J]. 計算機(jī)工程與應(yīng)用， 2018， 54（8）：119-122.

LIU Huawei， ZHANG Shuai， ZHAO Boxin， et al. UAV path planning based on improved RRT algorithm in trap space[J]. Computer Engineering and Applications， 2018， 54（8）： 119-122.

[19]XUE Qian， CHENG Peng， CHENG Nong. Offline path planning and online replanning of UAVs in complex terrain[C]// Guidance， Navigation & Control Conference.[S.l.]：IEEE， 2015：7007525.

[20]施法中. 計算機(jī)輔助幾何設(shè)計與非均勻有理B樣條（修訂版）[M]. 北京：高等教育出版社， 2013：217-248.