基于RRT的無人機(jī)特征點(diǎn)覆蓋搜索算法優(yōu)化

鄭博文 陳志 陳銳 張佳煜

摘 要：為提高無人機(jī)對特定目標(biāo)點(diǎn)的覆蓋搜索效率，設(shè)計(jì)一種無人機(jī)特征點(diǎn)覆蓋搜索算法。首先采用一般的“Z”字型搜索方式確認(rèn)大致搜索范圍，并且以此設(shè)置轉(zhuǎn)彎起點(diǎn)、終點(diǎn)及搜索障礙物，然后使用經(jīng)引入引力分量優(yōu)化后的快速拓展隨機(jī)樹（RRT）算法產(chǎn)生搜索路徑，最后對路徑進(jìn)行圓弧化處理產(chǎn)生最終路徑，完成針對特征點(diǎn)的區(qū)域覆蓋。算法實(shí)現(xiàn)與理論分析結(jié)果表明，該無人機(jī)特征點(diǎn)覆蓋搜索算法將“Z”字型搜索與RRT快速隨機(jī)搜索樹方法進(jìn)行集成優(yōu)化，能較為高效地完成對給定區(qū)域特征點(diǎn)的搜索覆蓋。

關(guān)鍵詞：無人機(jī);路徑規(guī)劃;覆蓋搜索;快速拓展隨機(jī)樹;算法優(yōu)化

DOI：10. 11907/rjdk. 201474 開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號：TP312文獻(xiàn)標(biāo)識(shí)碼：A 文章編號：1672-7800（2020）007-0056-04

UAV Feature Points Coverage Searching Algorithm Optimization Based on RRT

ZHENG Bo-wen 1， CHEN Zhi2， CHEN Rui 1， ZHANG Jia-yu 3

（1. Bell Honors School， Nanjing University of Posts and Telecommunications;2. College of Computer， Nanjing University of Posts and Telecommunications;3. College of Overseas Education， Nanjing University of Posts and Telecommunications， Nanjing 210003， China）

Abstract： In order to improve the efficiency of unmanned aerial vehicle （UAV） coverage searching for specific target points， a UAV feature point coverage searching algorithm is designed. The proposed algorithm first uses the general “Z” search method to confirm the approximate search range， and then sets the turning beginning points， ending points and searching barriers， then uses the rapidly-exploring random tree （RRT） algorithm which has introduced the gravity component optimization to generate the search path， and finally generates the final path through the path arc processing to complete the area coverage for the feature points. The results of the algorithm implementation and theoretical analysis show that the proposed UAV feature point coverage search algorithm integrates the “Z” search and RRT fast random search tree， and can effectively complete the search coverage of the given area feature points.

Key Words： unmanned aerial vehicle; path planning; coverage searching; rapidly-exploring random tree; algorithm optimization

0 引言

無人機(jī)（Unmanned Aerial Vehicle，UAV）在現(xiàn)代生產(chǎn)生活領(lǐng)域發(fā)揮著重要作用。在無人機(jī)的工作中，很重要的一部分便是對目標(biāo)區(qū)域進(jìn)行搜索覆蓋，針對多無人機(jī)系統(tǒng)的配合問題是目前研究的重點(diǎn)。其要求在多種約束條件下實(shí)現(xiàn)對區(qū)域的合理覆蓋，目前主要采用的方法包括[A*]搜索算法[1-3]、蟻群算法[4]、Voronoi圖分割法[5-6]、概率路線圖法[7]及多種智能優(yōu)化算法[8-11]。這些傳統(tǒng)方法可在保證質(zhì)量和效率的前提下實(shí)現(xiàn)對區(qū)域的覆蓋。同時(shí)，在搜索模式方面，目前主要采用“Z”字型搜索覆蓋方式，文獻(xiàn)[12]中詳細(xì)介紹了這種搜索方法。但目前現(xiàn)有方法都無法高效完成針對數(shù)個(gè)給定特征點(diǎn)的搜索覆蓋。本文將隨機(jī)搜索樹（Rapidly-Exploring Random Tree，RRT）算法與一般無人機(jī)覆蓋搜索算法相結(jié)合，在完成區(qū)域覆蓋的基礎(chǔ)上，通過增加搜索樹節(jié)點(diǎn)過程，實(shí)現(xiàn)針對給定特征點(diǎn)的覆蓋搜索。

1 無人機(jī)搜索策略分析

在無人機(jī)搜索過程中，基于現(xiàn)實(shí)情況與節(jié)約資源的考慮，大多采用平行線掃描法[13]。在這種方法下，無人機(jī)搜索是基于一個(gè)寬度為兩倍搜索半徑、長度不固定的矩形完成的。但由于無人機(jī)是一種飛行器，受其自身存在最小轉(zhuǎn)彎半徑的限制，在需要完成整個(gè)區(qū)域覆蓋的情況下，無人機(jī)需要在搜索區(qū)域外進(jìn)行方向轉(zhuǎn)變才能盡量保證區(qū)域完全覆蓋，但這一段轉(zhuǎn)彎的飛行過程相對整個(gè)搜索過程是無用的，因而目前無人機(jī)搜索策略研究主要為優(yōu)化無人機(jī)轉(zhuǎn)向方式，以提升無人機(jī)搜索效率。

文獻(xiàn)[14]對給定凸多邊形區(qū)域最小寬度進(jìn)行了定義：定義凸多邊形切線為一條與該凸多邊形相交，且該凸多邊形在其一側(cè)的線，在平面上作一條與凸多邊形中一條邊重合的切線[l1]，此時(shí)一定存在一條與這條切線平行的直線[l2]，該直線也是與凸多邊形相切于一點(diǎn)或一邊的切線，上述兩條切線[l1與l2]之間的距離即被定義為凸多邊形基于[l1]的距離。若[l2]與凸多邊形相切于一點(diǎn)，將其定義為點(diǎn)—邊型距離;若[l2]與凸多邊形相切于一邊，將其定義為邊—邊型距離。一個(gè)具有[n]條邊的凸多邊形最多有[n]個(gè)不同的點(diǎn)—邊型距離或邊—邊型距離，其中的最小距離即為凸多邊形最小寬度，如圖1所示。

根據(jù)文獻(xiàn)[15]，對于一個(gè)凸多邊形區(qū)域，通常使用普通“Z”字型搜索方式進(jìn)行搜索。因此，本文將與表示凸多邊形最小寬度的兩條直線平行的一條邊定義為坐標(biāo)系的[x]軸?；谠摱x，可保證在整個(gè)無人機(jī)搜索過程中，飛行方向除轉(zhuǎn)彎過程外始終平行于該坐標(biāo)軸。通過推導(dǎo)可以得出其最小轉(zhuǎn)彎次數(shù)[nmin=LminR-1]，其中[R]為無人機(jī)搜索半徑，[Lmin]為多邊形最小距離。同時(shí)，由于無人機(jī)最小轉(zhuǎn)彎半徑的存在，在保證區(qū)域完全覆蓋的情況下，會(huì)出現(xiàn)如圖2所示的搜索遺漏區(qū)域。

文獻(xiàn)[15]首先對搜索過程的掉頭點(diǎn)和結(jié)束點(diǎn)（圖2中的[A]、[B]點(diǎn)）進(jìn)行定義。在該定義的基礎(chǔ)上，針對無人機(jī)最小轉(zhuǎn)彎半徑[r與]搜索區(qū)域半徑[R]兩者的關(guān)系，給出多種不同優(yōu)化方案。簡單地說，即根據(jù)[r]與[R]的關(guān)系適當(dāng)改變掉頭點(diǎn)、結(jié)束點(diǎn)位置，在不改變整體“Z”字型搜索方式的情況下，通過花費(fèi)一定多余的搜索距離以保證搜索區(qū)域的完全覆蓋，具體優(yōu)化方式如圖3所示。

上文所述為單無人機(jī)在凸多邊形區(qū)域的搜索方式，目前受限于無人機(jī)搜索范圍，大多數(shù)情況下需要多無人機(jī)聯(lián)合完成對一個(gè)區(qū)域的搜索。多無人機(jī)對凸多邊形區(qū)域的搜索一般有兩種方式：①根據(jù)文獻(xiàn)[12]的優(yōu)化方式采用多無人機(jī)編隊(duì)進(jìn)行協(xié)同搜索;②對無人機(jī)搜索區(qū)域進(jìn)行分割，在每個(gè)區(qū)域內(nèi)進(jìn)行單無人機(jī)搜索。本文采用第二種方式并對其進(jìn)行改進(jìn)。

與單無人機(jī)搜索策略不同，多無人機(jī)搜索策略的重點(diǎn)在于統(tǒng)籌規(guī)劃。首先需要完成針對凸多邊形搜索區(qū)域的分割。在理論推導(dǎo)中，可假定整個(gè)搜索過程需要[N]架無人機(jī)，因而整個(gè)多邊形區(qū)域應(yīng)被[N-1]條直線分為[N]個(gè)搜索距離大致相同的區(qū)域。同時(shí)，為方便對不同方案的搜索距離進(jìn)行比較，可將無人機(jī)在搜索區(qū)域中的行進(jìn)距離近似轉(zhuǎn)化為無人機(jī)搜索區(qū)域的面積。具體分割方式為：以一定順序?qū)⒃撏苟噙呅吸c(diǎn)定義為[V1]至[Vn]點(diǎn)，將其按照隨機(jī)順序壓入隊(duì)列，并將每次分割后的點(diǎn)放入隊(duì)列尾部，對其進(jìn)行標(biāo)記，經(jīng)過[N]次操作后取得結(jié)果。在該過程結(jié)束后，可通過檢測該組無人機(jī)搜索面積的方差判定此次結(jié)果的準(zhǔn)確性，在經(jīng)歷過多次迭代后，即可得出最終的最優(yōu)化結(jié)果。

在凸多邊形區(qū)域完成分割后，無人機(jī)需要飛行前往搜索起始點(diǎn)，此時(shí)采用“飛行+轉(zhuǎn)彎”模式，保證搜索初始路徑與轉(zhuǎn)彎圓相切即可，具體方式如圖4所示。

由于目前無人機(jī)對區(qū)域搜索覆蓋的精細(xì)化程度日益提高，產(chǎn)生了針對給定特征點(diǎn)的搜索需要，即在一定搜索區(qū)域內(nèi)，在完成區(qū)域覆蓋的前提下需要針對特征點(diǎn)進(jìn)行精確覆蓋，可將該過程抽象為無人機(jī)航路經(jīng)過特征點(diǎn)附近。但如果采用普通的“Z”型無人機(jī)進(jìn)行搜索，顯然無法達(dá)到這一效果，因而需要引入RRT快速拓展隨機(jī)樹算法。

2 RRT快速拓展隨機(jī)樹算法分析

RRT算法[16]是一種廣泛應(yīng)用于機(jī)器人尋路的路徑規(guī)劃算法，也有不少學(xué)者將其應(yīng)用于無人機(jī)路徑規(guī)劃 [17-20]。其全稱為快速拓展隨機(jī)樹算法，通過給定起始點(diǎn)作為種子，可使枝葉如樹一般向外延伸，從而完成對整個(gè)區(qū)域的填充。主要步驟如下：

Step1：給定起點(diǎn)作為種子[q0]。

Step2：在整個(gè)構(gòu)型空間中生成一個(gè)隨機(jī)點(diǎn)[pi]。

Step3：在樹的現(xiàn)存點(diǎn)中找到距離點(diǎn)[pi]最近的點(diǎn)[qj]。

Step4：從[qj]將現(xiàn)存搜索樹向[pi]處延伸，若無障礙物，則將兩點(diǎn)相連，將[pi]點(diǎn)加入樹中，轉(zhuǎn)回Step2。

隨機(jī)樹構(gòu)建過程如圖5所示。

該方法的優(yōu)點(diǎn)是能較為迅速地完成對路徑的大致規(guī)劃，且實(shí)現(xiàn)過程簡單。當(dāng)情況相對復(fù)雜時(shí)也可通過快速迭代找到近似解。同時(shí)，只要給定區(qū)域的約束情況完整，RRT一定會(huì)給出一個(gè)可行解。當(dāng)然，構(gòu)建出的隨機(jī)樹由于產(chǎn)生隨機(jī)點(diǎn)的不確定性，在保證搜索自由度的情況下經(jīng)常會(huì)出現(xiàn)樹曲線不平滑、無法向外衍生等多種情況，此時(shí)需要對整個(gè)RRT算法進(jìn)行優(yōu)化。

3 針對無人機(jī)區(qū)域特征點(diǎn)覆蓋搜索的RRT算法優(yōu)化

目前，RRT算法主要優(yōu)化方向是引入人工勢場法中的引力分量。其核心思想是在路徑的每個(gè)節(jié)點(diǎn)延伸過程中，給每一個(gè)隨機(jī)節(jié)點(diǎn)[pi]都引入一個(gè)方向朝向搜索終點(diǎn)[ptar]，且大小與這兩點(diǎn)之間距離相關(guān)的目標(biāo)引力函數(shù)[G（n）][21]。在一般的RRT算法中，指導(dǎo)節(jié)點(diǎn)生長的生長函數(shù)[F（n）]即為節(jié)點(diǎn)的隨機(jī)生長系數(shù)[R（n）]，但在引入引力分量后，公式變?yōu)閇F（n）=G（n）+R（n）]。因此，算法生成的新節(jié)點(diǎn)相對最近點(diǎn)的延伸矢量即為兩個(gè)矢量的合成。具體如圖6所示。

但是一般隨機(jī)搜索樹的優(yōu)化方式?jīng)]有考慮到無人機(jī)作為飛行器存在最小轉(zhuǎn)彎半徑的問題，且搜索終點(diǎn)也不能作為搜索路徑終點(diǎn)直接行進(jìn)，所以這種RRT算法不能直接應(yīng)用于無人機(jī)特征搜索過程中。本文對該算法的優(yōu)化分為兩方面，一是對區(qū)域約束進(jìn)行優(yōu)化，二是對隨機(jī)樹輪廓進(jìn)行優(yōu)化。

首先是對區(qū)域約束的優(yōu)化。由于搜索過程需要保證搜索區(qū)域的全覆蓋，因此搜索路徑仍大致按照一般“Z”字型無人機(jī)區(qū)域覆蓋的方式進(jìn)行，即為“前進(jìn)—掉頭—前進(jìn)”的過程?？紤]到RRT算法在生成拓展路徑時(shí)，會(huì)自動(dòng)刪除路徑中經(jīng)過的障礙物，因而可考慮在搜索區(qū)域中人工劃分寬度可忽略不計(jì)的障礙物，從而保證搜索區(qū)域不會(huì)橫跨兩個(gè)沿[x]軸的搜索方向，具體為在原搜索區(qū)域形成的圓環(huán)區(qū)域中將各圓環(huán)相切處連接，即為新產(chǎn)生的搜索障礙物（見圖7中黑色實(shí)線）。

接著，顯然可以發(fā)現(xiàn)生成的隨機(jī)樹實(shí)際上是雜亂無章的，并且會(huì)出現(xiàn)延伸方向與目標(biāo)方向相反的情況，這在無人機(jī)搜索過程中顯然是無法實(shí)現(xiàn)的，而且是無效操作。此時(shí)需要考慮將特征點(diǎn)按照搜索過程的不同階段進(jìn)行分割?？蓪ⅰ癦”型搜索方式中無人機(jī)轉(zhuǎn)彎起點(diǎn)、終點(diǎn)分別定義為搜索過程中一個(gè)搜索階段的終點(diǎn)與起點(diǎn)，并將搜索區(qū)域按照這一定義進(jìn)行階段分割，具體如圖7所示：[ptar1]至[ptar4]，即淺色點(diǎn)為特征點(diǎn)，[ptar5]、[ptar6]分別為“Z”型搜索區(qū)域前一搜索階段的搜索終點(diǎn)與后一搜索階段的搜索起點(diǎn)，因而在這一段區(qū)域，1～5號點(diǎn)即為一個(gè)搜索階段。

最后，要去除路徑上的冗余節(jié)點(diǎn)。由于引力分量的引入，在前進(jìn)過程中很少會(huì)出現(xiàn)大角度偏移，但在路徑初始節(jié)點(diǎn)附近，很可能會(huì)有冗余節(jié)點(diǎn)可以刪除。同樣地，在搜索末尾節(jié)點(diǎn)也有很大概率出現(xiàn)可刪除的冗余節(jié)點(diǎn)。因此，可以引入偏移角度因子[？]。對于一個(gè)點(diǎn)，若以其為終點(diǎn)的路徑和以其為起點(diǎn)的路徑形成的角度大于給定的偏移角度因子，即可認(rèn)為其為冗余節(jié)點(diǎn)，刪除經(jīng)過該點(diǎn)的兩條路徑，將該條路徑起點(diǎn)與下條路徑起點(diǎn)相連。如圖8所示，刪除冗余節(jié)點(diǎn)[p1]。

在路徑規(guī)劃過程中，需要充分考慮無人機(jī)的搜索限制，因而需要將搜索路徑在拐點(diǎn)處向偏轉(zhuǎn)角補(bǔ)角方向平移一定距離，使得整個(gè)搜索過程呈圓弧狀，更加平滑且符合無人機(jī)搜索過程，具體方式如圖9所示。在到達(dá)下一個(gè)起點(diǎn)后，再次進(jìn)行圓弧化，最終在圓弧化過程中優(yōu)化冗余節(jié)點(diǎn)形成過程。

在進(jìn)行一系列優(yōu)化后，可采用優(yōu)化后的RRT搜索算法對區(qū)域給定特征點(diǎn)進(jìn)行無人機(jī)覆蓋搜索，最終目標(biāo)效果如圖10所示。

4 結(jié)語

本文通過分析無人機(jī)區(qū)域覆蓋搜索算法與RRT算法實(shí)現(xiàn)過程，針對無人機(jī)搜索給定區(qū)域特征點(diǎn)的情況，將兩種算法進(jìn)行集成優(yōu)化，提出改進(jìn)的RRT搜索算法，在一定程度上解決了當(dāng)前無人機(jī)搜索特定區(qū)域困難的問題。在算法實(shí)現(xiàn)過程中，需要解決兩個(gè)問題：一是將算法裝載在無人機(jī)平臺(tái)時(shí)，對無人機(jī)攜帶GPU的工作效率有較高要求;二是整個(gè)生成路徑雖然在一定程度上進(jìn)行了針對無人機(jī)系統(tǒng)的優(yōu)化，但在極端條件下仍會(huì)出現(xiàn)轉(zhuǎn)彎半徑過小導(dǎo)致無法執(zhí)行的情況。在今后的工作中，可考慮重點(diǎn)研究無人機(jī)轉(zhuǎn)彎半徑與飛行路徑之間的關(guān)系，從而讓無人機(jī)更好、更高效地工作。

參考文獻(xiàn)：

[1] SZCZERBA R J，GALKOWSHI P，GLICKTEIN I S. Robust algorithm for real-time route planning [J]. IEEE Trans on Aerospace and Electronic System， 2000， 36（3）： 869-878.

[2] 唐曉東. 基于A*算法的無人機(jī)航跡規(guī)劃技術(shù)的研究與應(yīng)用 [D].綿陽：西南科技大學(xué)，2012.

[3] 王淼弛. 基于A*算法的移動(dòng)機(jī)器人路徑規(guī)劃[D].沈陽：沈陽工業(yè)大學(xué)，2017.

[4] 邱莉莉. 基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃[D].上海：東華大學(xué)，2015.

[5] CHANDLER P，RASMUSSEN S A，PACHTER M. UAV cooperative path panning[C]. AIAA Guidance， Navigation， and Control Conference and Exhibit， 2000.

[6] MCLAIN T，BEARD R.Trajectory planning for coordinated rendezvous of unmanned air vehicles[C]. Proceedings of the AIAAA Guidance， Navigation， and Control Conference， 2000.

[7] 楊盛毅，柳陽陽，楊偉力. 一種未知環(huán)境下的局部動(dòng)態(tài)概率路線圖法[J].航空航天技術(shù)，2016，27（4）：69-73.

[8] ANDINA D，JAIMES A，GOMEZ J. Unmanned aerial vehicle route optimization using ant system algorithm[C]. International Conference on System of Systems Engineering. Loughborough，2010.

[9] 李猛. 基于智能優(yōu)化與RRT算法的無人機(jī)任務(wù)規(guī)劃方法研究 [D]. 南京： 南京航空航天大學(xué)， 2012.

[10] BESADA P E，DE L T L，DE L C， et al. Evolutionary trajectory planner for multiple UAVs in realistic scenarios[J]. IEEE Transactions on Robotics，2010，26（4）：619-634.

[11] 劉雨坤，侯捷. 無人機(jī)航跡規(guī)劃群智能優(yōu)化算法綜述 [J]. 理論與算法，2017（24）：48-50.

[12] 吳青坡，周紹磊，尹高揚(yáng)，等.多無人機(jī)協(xié)同區(qū)域覆蓋搜索算法的改進(jìn)[J].電光與控制，2016，23（1）：80-84.

[13] BOLONKIN A，CLOUTIER J R. Search and attack strategies[C]. 2005 AIAAA Guidance，Navigation，and Control Conference and Exhibit，2005.

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

[15] 張亞倫. 基于改進(jìn)RRT算法的無人機(jī)航路規(guī)劃研究[D]. 沈陽： 沈陽航空航天大學(xué)，2015.

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

[17] 陳海，王新民，焦裕松，等. 一種凸多邊形區(qū)域的無人機(jī)覆蓋航跡規(guī)劃算法[J]. 航空學(xué)報(bào)，2010，31 （9）：1802-1807.

[18] 于駟男，周銳，夏潔，等.多無人機(jī)協(xié)同搜索區(qū)域分割與覆蓋[J].北京航空航天大學(xué)學(xué)報(bào)，2015，41（1）：167-173.

[19] KARAMAN S，WALTER M R，PEREZ A，et al. Anytime motion planning using the RRT[C]. IEEE International Conference on Robotics and Automation，2011：1478-1483.

[20] 王全. 基于RRT的全局路徑規(guī)劃方法及其應(yīng)用研究[D]. 長沙：國防科學(xué)技術(shù)大學(xué)，2014.

[21] 劉成菊，韓俊強(qiáng)，安康. 基于改進(jìn)RRT算法的RoboCup機(jī)器人動(dòng)態(tài)路徑規(guī)劃[J]. 機(jī)器人，2017，39（1）：8-15.

（責(zé)任編輯：黃 ?。?/p>