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

任鵬博，董澤華

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

任鵬博，董澤華

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

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

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

0 引言

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

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

1.1 人工勢(shì)場(chǎng)法

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

圖2 人工勢(shì)場(chǎng)算法的流程圖

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

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

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

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

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

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

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

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

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

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

圖5 RRT的節(jié)點(diǎn)擴(kuò)展過程示意圖

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

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

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

2 仿真驗(yàn)證與分析

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

2.1 二維任務(wù)空間仿真實(shí)驗(yàn)

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

2.2 三維任務(wù)空間仿真實(shí)驗(yàn)

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

3 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

[11] 田曉亮. 無人機(jī)航跡規(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—），陜西咸陽人，碩士研究生，主要研究方向?yàn)樾盘?hào)檢測(cè)與信號(hào)處理。