任鵬博，董澤華

基于RRT算法的無人機路徑規(guī)劃應(yīng)用研究

任鵬博，董澤華

（中國電子科技集團公司第二十研究所，西安 710068）

經(jīng)典的路徑規(guī)劃算法大都需要在全局已知空間中對環(huán)境進行建模，包括人工勢場法、遺傳算法、啟發(fā)式算法、仿生學(xué)算法等。由于需要預(yù)先構(gòu)建環(huán)境，因此這些方法并不適合解決在高維度空間中的路徑規(guī)劃問題?；诳焖贁U展隨機樹（RRT）的路徑規(guī)劃方式其優(yōu)勢在于可以避免對全局環(huán)境的構(gòu)建，通過對狀態(tài)空間進行隨機采樣，檢測碰撞點，能夠有效地解決在平面及三維狀態(tài)空間下的復(fù)雜路徑規(guī)劃問題。通過與人工勢場法和A*算法進行比對，確定了RRT算法在復(fù)雜環(huán)境中解決無人機路徑規(guī)劃問題的優(yōu)勢，在對相關(guān)參數(shù)進行優(yōu)化后該方法是概率完備且存在最優(yōu)解的，同時在固定翼智能集群飛行編隊控制及協(xié)同項目中應(yīng)用。

無人機；路徑規(guī)劃；RRT算法

0 引言

無人機的航跡規(guī)劃是在地形環(huán)境、外部威脅和機動性能三者綜合約束條件下，規(guī)劃出一條從任務(wù)起始點到目標(biāo)點的最優(yōu)飛行航線[1]。地形環(huán)境主要考慮飛行中不同海拔的山地因素；外部威脅主要考慮路徑生成中的敵方導(dǎo)彈威脅、電磁干擾威脅、外部障礙威脅等；無人機的機動性能主要考慮無人機的飛行速度、最大航程、最大轉(zhuǎn)彎角、最大爬升俯沖角、飛行高度等性能約束。當(dāng)前全局路徑規(guī)劃中比較常規(guī)的算法包括人工勢場法、啟發(fā)算法的A*算法、仿生算法的蟻群算法，以及這些算法的優(yōu)化改進算法，但這些路徑規(guī)劃算法都需要事先完成對空間內(nèi)的障礙物等環(huán)境進行建模，不適合解決無人機在復(fù)雜環(huán)境中的全局路徑預(yù)規(guī)劃問題[2]。本文主要研究快速擴展隨機樹算法（Rapidly Exploring Random Tree，RRT）在固定翼智能集群飛行編隊控制及協(xié)同項目中路徑規(guī)劃的應(yīng)用與實現(xiàn)。

1 無人機全局路徑規(guī)劃算法研究

1.1 人工勢場法

人工勢場法的算法思想是受到電荷在電場中的運動特點的啟發(fā)，將移動主體單位當(dāng)做一個帶電的電荷，其所處環(huán)境相當(dāng)于一個復(fù)雜的電場[3]，其環(huán)境中的所有障礙物均帶與移動單位相同的電荷，而目標(biāo)點則為異種電荷，因此，移動單位與障礙物之間產(chǎn)生斥力，與目標(biāo)點產(chǎn)生引力。這樣，在障礙物與目標(biāo)點的復(fù)雜合力作用下，對無人機的飛行路徑進行規(guī)劃。人工勢場法的基本原理如圖1所示，在已知無人機初始狀態(tài)、目標(biāo)位置以及障礙物位置的基礎(chǔ)上，人工勢場法產(chǎn)生一條安全平滑機動能耗小的飛行路線[4]。人工勢場算法的流程圖如圖2所示。

圖2 人工勢場算法的流程圖

通過將無人機所在的任務(wù)區(qū)間使用一定的勢場函數(shù)進行設(shè)置，具體分為兩部分，無人機與障礙物間的作用力用斥力勢場函數(shù)表示，而與目標(biāo)點之間的相互作用力則使用引力勢場函數(shù)描述。

勢場函數(shù)的具體表示如下，其中無人機與目標(biāo)點之間產(chǎn)生的吸引力勢場函數(shù)如式（1）所示：

另一方面，無人機對障礙物產(chǎn)生的斥力由斥力勢場函數(shù)所產(chǎn)生，無人機與障礙物之間產(chǎn)生的排斥力勢場函數(shù)如式（2）所示：

1.2 A*路徑規(guī)劃算法

在構(gòu)建好的隊列中，每個節(jié)點都會指向其前面的那個節(jié)點，目標(biāo)節(jié)點將指向其前導(dǎo)節(jié)點，依此類推，直到某個節(jié)點的前導(dǎo)是開始節(jié)點。這樣就得到了一條從初始點到達目標(biāo)點的最短路徑序列，A*算法流程如圖3所示。

圖3 A*路徑規(guī)劃算法流程圖

1.3 RRT路徑規(guī)劃算法

相較于傳統(tǒng)的路徑規(guī)劃算法，RRT算法具有無需事先對任務(wù)環(huán)境進行建模的優(yōu)勢，其本質(zhì)是通過構(gòu)建一棵隨機搜索樹對未知環(huán)境空間進行探索，將根節(jié)點設(shè)置為起始點，探索點的隨機性保證了目標(biāo)點探索的概率完備性，有利于在多維空間下的路徑探索，可以解決具有非完整約束的路徑規(guī)劃問題[8]。RRT路徑規(guī)劃算法流程如圖4所示，利用搜索策略進行設(shè)定區(qū)域內(nèi)搜索，找到下一個待擴展的葉節(jié)點；然后利用步長策略作為判定條件實現(xiàn)隨機樹擴展生長，最后獲得無人機初始點到達目標(biāo)點的規(guī)劃路徑[9]。

RRT路徑規(guī)劃算法是一種在多維空間路徑規(guī)劃過程效率較高的方法，通常從狀態(tài)空間中的一個初始點出發(fā)，初始點作為根節(jié)點，通過隨機采樣擴展的方式來增加葉子節(jié)點進而生成一個隨機擴展樹，當(dāng)隨機樹中的葉子節(jié)點包含了目標(biāo)點或進入目標(biāo)區(qū)域，便可以在隨機擴展樹中至少找到一條從初始點到目標(biāo)點的路徑信息[10]。

圖4 RRT路徑規(guī)劃算法流程圖

圖5 RRT的節(jié)點擴展過程示意圖

1.4 路徑規(guī)劃算法分析

傳統(tǒng)的路徑規(guī)劃算法受限于必須在靜態(tài)環(huán)境中對周遭空間進行建模，其路徑規(guī)劃的效率受到狀態(tài)空間大小的影響，主要是移動主體的動作空間，即無人機的自由度，其算法時間復(fù)雜度呈指數(shù)遞增。因此，經(jīng)典的路徑規(guī)劃算法不利于解決多自由度機器人的路徑規(guī)劃問題?；赗RT的方式可以省去以往的對狀態(tài)空間的建模過程，并能同時解決高維空間下及多約束條件下的路徑規(guī)劃問題。結(jié)合多種路徑規(guī)劃算法的優(yōu)缺點分析選擇RRT算法作為固定翼無人機路徑規(guī)劃算法，并在固定翼智能集群飛行編隊控制及協(xié)同項目中應(yīng)用，常規(guī)路徑規(guī)劃算法優(yōu)缺點如表1所示。

表1 路徑規(guī)劃算法優(yōu)缺點對比

2 仿真驗證與分析

為了驗證RRT路徑規(guī)劃算法在無人機運動平臺中路徑規(guī)劃的有效性，本文在Windows 10操作系統(tǒng)，Intel（R）Core（TM）i7-9700K CPU @ 3.6 GHz,內(nèi)存16 GB實驗環(huán)境中基于PyCharm 2021.1（Community Edition）編譯工具實現(xiàn)RRT路徑規(guī)劃算法的仿真與分析。

2.1 二維任務(wù)空間仿真實驗

圖6 二維任務(wù)空間路徑規(guī)劃效果圖

2.2 三維任務(wù)空間仿真實驗

圖7 三維任務(wù)空間路徑規(guī)劃效果圖

3 結(jié)論

RRT算法的優(yōu)勢不僅體現(xiàn)在二維空間，高維空間中的路徑搜索同樣有效。RRT算法對整個區(qū)域空間進行更為充分的搜索，能夠應(yīng)對更為復(fù)雜的障礙物情況下路徑規(guī)劃問題。在仿真實驗中可以發(fā)現(xiàn)，通過設(shè)置合適的隨機概率使無人機能夠在保持向目標(biāo)點探索的基礎(chǔ)上增加尋找到完整路徑的概率，加強目標(biāo)點導(dǎo)向性，設(shè)置適當(dāng)?shù)乃阉鞑介L則確保了無人機既可以從多障礙物中找到通路又可以減少規(guī)劃迭代的次數(shù)。實驗結(jié)果表明RRT算法不僅能夠在高位空間中快速尋找到較優(yōu)路徑的能力，另一方面還可以保證規(guī)劃路徑的相對平滑，目前在RRT路徑規(guī)劃算法在固定翼智能集群飛行編隊控制及協(xié)同項目中已應(yīng)用并取得較好的效果。

[1] 成浩浩，楊森，齊曉慧. 基于改進RRT算法的四旋翼無人機航跡規(guī)劃[J]. 計算機工程與設(shè)計，2018（12）：115-118.

[2] 張建英，趙志萍，劉暾. 基于人工勢場法的機器人路徑規(guī)劃[J]. 哈爾濱工業(yè)大學(xué)學(xué)報，2006，38（8）：1306-1309.

[3] 文勇，張懷相，曾虹. 新型勢場法的移動機器人避障研究[J]. 杭州電子科技大學(xué)學(xué)報，2009，29（1）：50-53.

[4] 衛(wèi)珊，王凌，王斌銳. A*算法的改進及其在AGV路徑規(guī)劃中的應(yīng)用[J]. 自動化儀表，2017（11）：246-251.

[5] 范偉倫，李薇，馮杭. 基于改進RRT算法的無人機實時航跡規(guī)劃[J]. 艦船電子工程，2019（2）：333-337.

[6] 李洋，徐達，周誠. 基于自適應(yīng)步長RRT的雙機器人協(xié)同路徑規(guī)劃[J]. 農(nóng)業(yè)機械學(xué)報，2019（3）：1016-1021.

[7] 劉曉倩，張輝，王英健. 基于改進RRT的路徑規(guī)劃算法[J]. 自動化技術(shù)與應(yīng)用，2019（5）：454-459.

[8] 張藝巍，譚建豪，王耀南. 3維復(fù)雜山地環(huán)境下旋翼無人飛行器高時效航跡規(guī)劃策略[J]. 機器人，2016，38（6）：727-737.

[9] 陳淼. 自轉(zhuǎn)式無人旋翼機飛行控制技術(shù)研究[D]. 南京：南京航空航天大學(xué)，2012：56-61.

[10] 盧恩超，張鄧斕，寧雅男，等. 改進人工勢場法的機器人航跡規(guī)劃[J]. 西北大學(xué)學(xué)報（自然科學(xué)版），2012，42（5）：735-738.

[11] 田曉亮. 無人機航跡規(guī)劃方法研究[D]. 西安：西安電子科技大學(xué)，2014：28-29.

Research on UAV Path Planning Application Based on RRT Algorithm

REN Pengbo, DONG Zehua

Traditional global path planning algorithms include artificial potential field method, genetic algorithm, intelligent bionics algorithm, heuristic algorithm and so on. However, these methods all need to model obstacles in the known global space, and are not suitable for solving the planning problem of multi-degree-of-freedom robots in complex environments. The path planning algorithm based on rapidly exploring random tree, through the collision monitoring of sampling points in the state space, avoids the modeling of the global space, and can effectively solve the path planning problems of high-dimensional space and complex constraints. By comparing with the artificial potential field method and the A*algorithm, the advantages of the RRT algorithm in solving the UAV path planning problem in a complex environment is determined in the paper. After optimizing the relevant parameters, the method is probabilistic and has an optimal solution, and applied in the Fixed-wing intelligent cluster flight formation control and coordination project at the same time.

UAV; Path Planning; RRT Algorithm

V279

A

1674-7976-(2022)-01-062-05

2021-10-15。

任鵬博（1995.02—），陜西咸陽人，碩士研究生，主要研究方向為信號檢測與信號處理。