基于RRT算法的某型無人機航路在線規劃設計

路 引，郭昱津，王道波

(1.南京航空航天大學 中小型無人機先進技術工業和信息化部重點實驗室， 南京 210016；2.中電集團第二十八研究所，南京 210007；3.南京航空航天大學 自動化學院，南京 210016)

【裝備理論與裝備技術】

基于RRT算法的某型無人機航路在線規劃設計

路 引1,3，郭昱津2，王道波3

(1.南京航空航天大學 中小型無人機先進技術工業和信息化部重點實驗室， 南京 210016；2.中電集團第二十八研究所，南京 210007；3.南京航空航天大學 自動化學院，南京 210016)

針對高原地區復雜地形地貌，提出了無人機需具備在線航路規劃能力；分析了快速隨機搜索樹(RRT)算法的基本原理，并對RRT算法的收斂性和參數選擇進行了探討，設計了基于RRT算法的在線航路規劃方法；對所設計的方法進行仿真驗證。仿真結果表明：該航路在線規劃方法達到了預期目的，能夠很好的規避突發障礙。

無人機；航路規劃；快速隨機搜索樹

高原地區地形地貌復雜，群山連綿，無人機按照預設的航線飛行，可能會遇到山等障礙物，對無人機飛行造成很大的威脅。無人機在復雜的應用環境中執行飛行任務，外界環境突發變化，無人機很難預先獲得飛行過程中的全部環境信息，突發威脅僅當無人機抵達其附近一定區域后才能發現，在無人機的飛行過程中，改變無人機的飛行任務，這都需要無人機具備在線的航路規劃能力，在滿足飛行條件限制的前提下避開當前的危險。考慮實時性、可行性等需求，所研制的某型無人機采用快速隨機搜索樹(RRT)算法作為無人機的復雜航路在線規劃方法[1-4]。

1 RRT算法

快速隨機搜索樹(RRT)算法是一種隨機性、實時性好、速度快的算法，該算法能夠在威脅、障礙物復雜的情況下快速找到一條路徑。RTT搜索能力強，其獨特優點是經過擴展后，可以直接應用到動力學規劃。此算法采用一種能逐步迅速縮短隨機狀態與期望狀態點之間距離的特殊增量方式進行構造[5]，考慮高原地區復雜的地形地貌條件，采用RRT算法進行航路規劃能快速找到一條規避突發威脅的航路。

如圖1所示，無人機按照預設航路從A點飛向G點，在飛行過程中，遇到突發威脅，需要在線規劃航路，改變飛行路徑，保證飛行安全。

圖1 無人機飛行中遇威脅示意圖

2 RRT算法的基本原理

假設無人機飛行區域為R，Rfree為無障礙區域，Robs為障礙區域，Rfree是Robs的補集，兩個同為R的子集，且Rfree∪Robs=R。Rinit為起點，Rgoal為終點，且滿足Rinit和Rgoal都為Rfree的子集。在飛行區域R中尋找一條從Rinit到Rgoal的可行路徑。

RRT 算法是通過逐步迭代的增量方式構建隨機樹的。圖2為RRT算法的節點擴展過程。首先RRT算法中樹的根節點是在任務區域內選定的起始節點Rinit，所生成的隨機樹是通過從根節點連續擴展出葉節點方式構建的。以概率rg選擇目標位置Rgoal為隨機目標Rran，臨近節點Rnear是在隨機樹的葉節點里離Rran最近的節點。從Rnear向Rran的方向延伸一個步長的距離ε，得到一個新的節點Rnew。在延伸過程中，判斷是否與威脅區域有沖突，若Rnew與威脅區域有沖突，則舍棄該擴展的新節點，并重新選取隨機目標點Rran，若Rnew與威脅區域無沖突，則接受該擴展的新節點Rnew，并將其新節點Rnew添加為隨機樹的節點。依此通過這樣連續的擴展，直至隨機樹中的葉節點與目標點Rgoal足夠近的時候，認為隨機樹的構建工作完成，從構建的隨機樹中，尋找從起始點Rinit到最終目標點Rgoal的路徑，可以獲得一條從起始位置到目標位置的可行路徑[6]。

圖2 RRT算法的節點擴展

3 RRT 算法收斂性分析

RRT 算法具有很強的路徑規劃能力，下面從理論上對RRT能夠從起始位置擴展到目標位置的概率完備性進行分析[7]。令Dk(R*)是一個隨機變量，表示位置R*與RRT隨機樹T上的最近節點之間的距離，dk表示隨機變量的取值，k表示RRT的節點數，ε是RRT算法的擴展步長。

定理1Rfree為n維非凸有界開集，起始位置R0和目標位置R*位于Rfree的同一個連通區內，隨著RRT節點足夠增大，則RRT獲得從R0到R*路徑的概率為1，即

證明：R0與R*位于Rfree內的同一連通區內，那么在Rfree內存在一個節點序列R0,R1,…Rm，以及相應的超球體B(R1),B(R2),…B(Rm)，使得R0∈B1(R1)和R*∈Bm(Rm)，并且同時滿足：

Bi(Ri)∩Bi+1(Ri+1)≠?，i=1,2,…,m-1

令Ci=Bi∩Bi+1，對B(Ri)的構造，可以使得Ci為開集，測度μ(Ci)>0。

4 RRT參數研究

與其他的路徑規劃方法相比，RRT算法的一個顯著優點是該算法需要設置的參數較少，主要包括隨機點Rran和擴展步長ε等。簡單的結構有利于RRT算法的應用推廣，但目前關于算法參數的選取缺少嚴格的理論依據，在實際應用中一般根據經驗試湊獲得，不能保證算法參數的最優性。此處主要探討參數擴展步長ε對RRT算法的影響。

在Rran與隨機樹所有節點計算距離之后，得到與之最近的節點Rnear，然后沿著Rnear與Rran的方向，從Rnear開始延伸一個步長的距離ε。較大的步長有利于減少路徑所需要的節點數，但也增加了節點擴展過程中遇到威脅區域的概率，被迫重新進行隨機節點的選擇，反而降低了優化效率；較小的步長能夠增大從Rnear到Rnew擴展的成功率，但需要很多的步數才能到達目標位置。在簡單威脅環境下，可使用較大的步長ε，以加快規劃的速度，且所得路徑較短；在復雜威脅環境下，過大的步長會限制RRT算法的擴展能力，導致規劃成功率降低，且所得路徑的長度較大，不符合最優性要求，此時可以采用較小的步長。綜合來看，RRT 算法中的參數ε選取至關重要，直接影響著規劃問題的求解優劣和成功率，并且對任務環境有一定的依賴性，可以根據實際環境情況，進行此參數的選擇。

5 RRT算法的在線實時規劃

無人機按照預設的航線飛行，一邊飛行，一邊探測附近區域是否有突發威脅信息，一旦探測到新威脅，立即更新威脅信息表。如果突發威脅與預設航路有交點，則啟動航路在線規劃，將航路前面一定距離的節點作為新起始點，利用RRT算法在線重新規劃新航路[8]。無人機按照重新規劃的新航路飛行到指定航點，為了減少計算量，需確定合適的規劃空間。無人機在正常飛行過程中，遇到突發威脅時，航路在線規劃流程如圖3所示。

圖3 RRT算法在線規劃流程

利用RRT算法進行無人機在線航路規劃算法如下：

1) 無人機按照預設航線飛行；

2) 若無人機到達目標點，則算法終止，飛行結束；否則，進入第3步；

3) 無人機沿預設航路飛行，同時探測附近是否有威脅信息；

4) 若無人機探測到有突發威脅信息，進入第5步；否則，轉第2步；

5) 利用RRT算法在線重新規劃航路，更新飛行航路；

6) 轉第2步。

6 RRT算法的仿真驗證

選取無人機任務區域為100 km×100 km的矩形地形區域，隨機生成100個障礙威脅，起始位置的坐標為(0,0)，目標位置坐標為(100,100)。設置RRT算法的參數為rg=0.5，步長ε=5。首先進行離線情況下的航路預規劃，所得RRT隨機樹和飛行路徑如圖4所示。離線航路長度為182.06 km，程序運行時間為4.186 1 s。

當無人機飛行至圖5中的A點位置，任務環境中出現突發威脅區域，如圖5所示，由該圖可知，新出現的突發威脅與無人機的待飛航路由重合，因此無人機此時不能再按照原有路徑飛行，必須進行航路重規劃。此時進行數字地圖更新，并以無人機當前位置為起點，重新調用RRT算法進行航路重規劃，所得結果如圖6所示。

航路重規劃的運行時間為1.781 5 s，耗時較少，能夠滿足無人機航路重規劃的實時性要求。新的航路長度為118.38 km。

圖4 無人機離線航路預規劃路徑

圖5 無人機飛行中突發威脅

圖6 無人機航路重規劃路徑

7 結束語

無人機的航路規劃是無人機飛行控制的重要組成部分，根據某型無人機的飛行控制研制需求，為了適應復雜地形地貌高原地區的飛行要求，分析了快速隨機搜索樹(RRT)算法的基本原理，并對RRT算法的收斂性和參數選擇進行了探討，設計了基于快速隨機搜索樹(RRT)算法作為無人機的航路在線規劃方法，仿真結果表明該航路在線規劃方法達到了預期目的，能夠很好的規避突發障礙。

[1] 楊力.無人機航路規劃技術研究[D].南京航空航天大學碩士論文,2009.

[2] MARTIN S R,WRIGHT S E,SHEPPARD J W.Offline and Online Evolutionary Bi-Directional RRT Algorithms for Efficient Re-Planning in Dynamic Environments[C]//Proceedings of the 3rd Annual IEEE Conference on Automation Science and Engineering,Scottsdale,2007:1131-1136.

[3] JAMES J,STEVEN M.An Efficient Approach to Single-Query Path Planning[C]//Proceedings of the 2000 IEEE International Conference on Robotics and Automation,2000,995-1002.

[4] 彭輝，王林，沈林成.區域目標搜索中基于改進 RRT 的 UAV 實時航跡規劃[J].國防科技大學學報,2009,31(5):86-91.

[5] 李猛.基于智能優化與RRT算法的無人機任務規劃方法研究[D].南京：南京航空航天大學,2012.

[6] LAVALLE S M.Planning Algorithms[M].Cambridge：Cambridge University Press,2006:229-243.

[7] LAVALLE S M,KUFFNER J J.DONALD B R,et al.Rapidly-Exploring Random Trees[J].Progress and Prospects.Algorithmic and Computational Robotics:New Directions,Wellesley,2001:293-308.

[8] PENG H,SU F,BU Y L,et al.Cooperative Area Search for Multiple UAVs Based RRT and Decentralized Receding Horizon Optimization[C]//Proceedings of the 7th Asian Control Conference,Hong Kong,2009:298-303.

[9] 李子杰，劉湘偉.基于進化算法的多無人機協同航路規劃[J].火力與指揮控制，2015(2):85-89.

[10]沈培志，張邦鈺，聶奇剛，等.基于蟻群算法的無人機航路規劃輔助決策研究[J].四川兵工學報，2015(8):145-148.

(責任編輯周江川)

Design on Route Online Planning for a Certain UAV Based on RRT Algorithm

LU Yin1,3, GUO Yu-jin2, WANG Dao-bo3

(1.Key Laboratory of Unmanned Aerial Vehicle Technology, Nanjing University of Aeronautics and Astronautics, Ministry of Industry and Information Technology, Nanjing 210016, China; 2.The 28thResearch Institute of China Electronics Technology Group Corporation, Nanjing 210007, China; 3.College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China)

Route online planning function of the UAV was putted forward in view of the complex plateau topography. Rapidly-exploring Random Tree(RRT) algorithm was analyzed and the convergence of RRT algorithm and parameter selection were discussed. RRT algorithm, as the method of route online planning, was designed. The method was applied to the route online planning simulation. And the simulation results show that the design of the method has reached the expected purpose and can avoid unexpected obstacles very well.

UAV; route planning; rapidly-exploring random tree

2016-07-25；

高空長航時無人直升機保性能飛行控制與旋翼轉速優化策略研究(61374188)

路引(1988—)，男，博士，主要從事無人機飛行力學與飛行控制研究。

10.11809/scbgxb2016.12.004

路引，郭昱津，王道波.基于RRT算法的某型無人機航路在線規劃設計[J].兵器裝備工程學報，2016(12):18-21.

format:LU Yin, GUO Yu-jin, WANG Dao-bo.Design on Route Online Planning for a Certain UAV Based on RRT Algorithm[J].Journal of Ordnance Equipment Engineering,2016(12):18-21.

V279+.2

A

2096-2304(2016)12-0018-04

修回日期：2016-08-25