基于RRT的無人機特征點覆蓋搜索算法優化

鄭博文 陳志 陳銳 張佳煜

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

關鍵詞：無人機;路徑規劃;覆蓋搜索;快速拓展隨機樹;算法優化

DOI：10. 11907/rjdk. 201474 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：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 引言

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

1 無人機搜索策略分析

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

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

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

文獻[15]首先對搜索過程的掉頭點和結束點（圖2中的[A]、[B]點）進行定義。在該定義的基礎上，針對無人機最小轉彎半徑[r與]搜索區域半徑[R]兩者的關系，給出多種不同優化方案。簡單地說，即根據[r]與[R]的關系適當改變掉頭點、結束點位置，在不改變整體“Z”字型搜索方式的情況下，通過花費一定多余的搜索距離以保證搜索區域的完全覆蓋，具體優化方式如圖3所示。

上文所述為單無人機在凸多邊形區域的搜索方式，目前受限于無人機搜索范圍，大多數情況下需要多無人機聯合完成對一個區域的搜索。多無人機對凸多邊形區域的搜索一般有兩種方式：①根據文獻[12]的優化方式采用多無人機編隊進行協同搜索;②對無人機搜索區域進行分割，在每個區域內進行單無人機搜索。本文采用第二種方式并對其進行改進。

與單無人機搜索策略不同，多無人機搜索策略的重點在于統籌規劃。首先需要完成針對凸多邊形搜索區域的分割。在理論推導中，可假定整個搜索過程需要[N]架無人機，因而整個多邊形區域應被[N-1]條直線分為[N]個搜索距離大致相同的區域。同時，為方便對不同方案的搜索距離進行比較，可將無人機在搜索區域中的行進距離近似轉化為無人機搜索區域的面積。具體分割方式為：以一定順序將該凸多邊形點定義為[V1]至[Vn]點，將其按照隨機順序壓入隊列，并將每次分割后的點放入隊列尾部，對其進行標記，經過[N]次操作后取得結果。在該過程結束后，可通過檢測該組無人機搜索面積的方差判定此次結果的準確性，在經歷過多次迭代后，即可得出最終的最優化結果。

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

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

2 RRT快速拓展隨機樹算法分析

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

Step1：給定起點作為種子[q0]。

Step2：在整個構型空間中生成一個隨機點[pi]。

Step3：在樹的現存點中找到距離點[pi]最近的點[qj]。

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

隨機樹構建過程如圖5所示。

該方法的優點是能較為迅速地完成對路徑的大致規劃，且實現過程簡單。當情況相對復雜時也可通過快速迭代找到近似解。同時，只要給定區域的約束情況完整，RRT一定會給出一個可行解。當然，構建出的隨機樹由于產生隨機點的不確定性，在保證搜索自由度的情況下經常會出現樹曲線不平滑、無法向外衍生等多種情況，此時需要對整個RRT算法進行優化。

3 針對無人機區域特征點覆蓋搜索的RRT算法優化

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

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

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

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

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

在路徑規劃過程中，需要充分考慮無人機的搜索限制，因而需要將搜索路徑在拐點處向偏轉角補角方向平移一定距離，使得整個搜索過程呈圓弧狀，更加平滑且符合無人機搜索過程，具體方式如圖9所示。在到達下一個起點后，再次進行圓弧化，最終在圓弧化過程中優化冗余節點形成過程。

在進行一系列優化后，可采用優化后的RRT搜索算法對區域給定特征點進行無人機覆蓋搜索，最終目標效果如圖10所示。

4 結語

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

參考文獻：

[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*算法的無人機航跡規劃技術的研究與應用 [D].綿陽：西南科技大學，2012.

[3] 王淼弛. 基于A*算法的移動機器人路徑規劃[D].沈陽：沈陽工業大學，2017.

[4] 邱莉莉. 基于改進蟻群算法的機器人路徑規劃[D].上海：東華大學，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] 楊盛毅，柳陽陽，楊偉力. 一種未知環境下的局部動態概率路線圖法[J].航空航天技術，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] 李猛. 基于智能優化與RRT算法的無人機任務規劃方法研究 [D]. 南京： 南京航空航天大學， 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]. 理論與算法，2017（24）：48-50.

[12] 吳青坡，周紹磊，尹高揚，等.多無人機協同區域覆蓋搜索算法的改進[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] 成浩浩，楊森，齊曉慧. 基于改進RRT算法的四旋翼無人機航跡規劃[J]. 計算機工程與設計，2018，39（12）：3705-3711.

[15] 張亞倫. 基于改進RRT算法的無人機航路規劃研究[D]. 沈陽： 沈陽航空航天大學，2015.

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

[17] 陳海，王新民，焦裕松，等. 一種凸多邊形區域的無人機覆蓋航跡規劃算法[J]. 航空學報，2010，31 （9）：1802-1807.

[18] 于駟男，周銳，夏潔，等.多無人機協同搜索區域分割與覆蓋[J].北京航空航天大學學報，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的全局路徑規劃方法及其應用研究[D]. 長沙：國防科學技術大學，2014.

[21] 劉成菊，韓俊強，安康. 基于改進RRT算法的RoboCup機器人動態路徑規劃[J]. 機器人，2017，39（1）：8-15.

（責任編輯：黃 健）