基于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.

（责任编辑：黄 健）