鄭博文 陳志 陳銳 張佳煜

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

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

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

1 無人機搜索策略分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結語

本文通過分析無人機區(qū)域覆蓋搜索算法與RRT算法實現(xiàn)過程，針對無人機搜索給定區(qū)域特征點的情況，將兩種算法進行集成優(yōu)化，提出改進的RRT搜索算法，在一定程度上解決了當前無人機搜索特定區(qū)域困難的問題。在算法實現(xiàn)過程中，需要解決兩個問題：一是將算法裝載在無人機平臺時，對無人機攜帶GPU的工作效率有較高要求;二是整個生成路徑雖然在一定程度上進行了針對無人機系統(tǒng)的優(yōu)化，但在極端條件下仍會出現(xiàn)轉(zhuǎn)彎半徑過小導致無法執(zhí)行的情況。在今后的工作中，可考慮重點研究無人機轉(zhuǎ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*算法的無人機航跡規(guī)劃技術的研究與應用 [D].綿陽：西南科技大學，2012.

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

[4] 邱莉莉. 基于改進蟻群算法的機器人路徑規(guī)劃[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] 楊盛毅，柳陽陽，楊偉力. 一種未知環(huán)境下的局部動態(tài)概率路線圖法[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] 李猛. 基于智能優(yōu)化與RRT算法的無人機任務規(guī)劃方法研究 [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] 劉雨坤，侯捷. 無人機航跡規(guī)劃群智能優(yōu)化算法綜述 [J]. 理論與算法，2017（24）：48-50.

[12] 吳青坡，周紹磊，尹高揚，等.多無人機協(xié)同區(qū)域覆蓋搜索算法的改進[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算法的四旋翼無人機航跡規(guī)劃[J]. 計算機工程與設計，2018，39（12）：3705-3711.

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

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

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

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

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

（責任編輯：黃 ?。?/p>