单侧区域分割的多无人机扫描线搜索方法研究

谢朋志　魏晨

摘 要：本文针对区域覆盖任务需求对多无人机搜索问题展开研究。首先， 提出一种任意搜索区域的等面积单侧区域分割方法（Unilateral Region Segmentation）。然后，每个搜索区域分派一架或一个编队的无人机进行扫描线搜索，再基于人工勢场法来规避障碍物或者威胁从而获得搜索路径。最后，进行仿真分析，验证了该算法在不同情况下的有效性、鲁棒性以及适应性。该算法在面向任意搜索区域、考虑无人机机动性以及存在威胁等问题时具有明显优势。

关键词：
多无人机;任意搜索区域;区域分割;扫描线搜索;人工势场法;路径规划

中图分类号：
V279 文献标识码：A文章编号：
1673-5048（2020）03-0067-06

0 引言

多无人机搜索问题一直是近些年的热点问题。国内外针对不同的任务需求展开了大量的研究，其中包括多无人机协同搜索以及区域覆盖等方面的研究。

面向多无人机协同搜索问题，主要解决如何由多架无人机以最小的代价协同搜索发现特定任务区域内可能存在的多个目标，主要方法为控制理论融合智能计算方法。文献[1]将最大可知度的控制算法与搜索不确定度图结合，能够有效实现多无人机之间的协同搜索，同时保证良好的时间优越性。文献[2]将模型预测控制理论和遗传算法相结合，建立了协同搜索的预测模型，并使用贝叶斯理论进行更新，有效降低了环境的不确定性。还有基于概率图[3]、信息素图[4]等智能计算方法的协同搜索算法。这类方法可以有效解决多无人机协同搜索优化问题中的NP-hard问题，有较好的侦察效果，但也普遍存在计算时间长、很难找到全局最优解以及难以覆盖搜索区域等问题。

面向区域覆盖的搜索算法虽然在协同性上不如前者，但在计算时间、任务分配难度和区域覆盖率等方面却有着明显的优势。

从国内外研究现状来看，针对区域覆盖搜索问题的研究大多采用分治策略的方法，即先进行区域分割（区域整理），然后采用扫描线[5]、螺旋线[6]等方式进行搜索。有学者将问题简化为给定一个固定几何区域内随机分布的许多目标点，栅

格化离散目标区域以提取侦察航路点[7-9]，然后将该问题抽象为一个旅行商问题（Traveling Salesman Problem，TSP），可以有效提高区域覆盖率，但这种区域划分的方法没有考虑区域几何形状对搜

索问题的影响，采用栅格化的方法没有考虑无人机机动性的要求。彭辉等人[10]针对多无人机协同区域覆盖搜索问题，将其分解为多无人机任务区域的分配以及分配后路径规划两个子问题，基于分层模糊推理的方法求解无人机的性能评估指标，采用基于面积的区域分割方法对搜索任务区域进行分割分配。类似的还有于驷男等人[11]提出的多无人机协同搜索区域分割与覆盖方法。但都没有对无人机初始位置的选取给出合理的安排，没有考虑存在威胁的情况。

目前多无人机的搜索问题的一个研究重点是如何有效提高搜索区域的覆盖率，然而侧重于多无人机协同搜索的方法大都存在计算时间长、覆盖率低等问题;而覆盖率比较高的扫描线方式的搜索算法也存在着没有考虑搜索区域几何形状对搜索算法适应性的要求、对无人机机动性的要求、目标区域存在威胁的要求以及无人机初始位置的要求等问题。

1 问题描述

1.1 问题分析

基于上述多无人机搜索面向区域覆盖方面的研究还存在一些需要解决的问题，因此从该研究出发，主要考虑搜索区域较大以及无人机从搜索区域外指定位置飞到搜索区域进行搜索的情况，进而研究对于搜索区域同一侧（边）作为初始位置的任意几何区域的扫描线搜索方法，同时考虑无人机机动性对搜索路径的影响以及存在障碍物或者威胁的情况。

本文主要研究任意多边形的等面积单侧区域分割方法，根据区域分割结果计算扫描线位置以及基于人工势场法得到搜索路径，实现对任务区域的搜索覆盖。

1.2 问题建模

（1） 传感器探测模型

基于区域覆盖的需求对传感器进行建模，采用下视的传感器类型，不考虑无人机姿态的变化对传感器视角的影响，高度H处的传感器探测到的区域范围是一个圆，其半径为R=H·tanθ。如图1所示。

（2） 无人机运动模型

对于一个由n架无人机组成的多无人机系统，用xi（t）， vi（t）， ui（t）分别表示无人机i的位置、速度和加速度，则无人机的运动方程可表示为

则无人机集群的动力学方程可表示为

X·=AX+BU（3）

根据运动方程，可将U设为无人机集群运动控制输入。每个个体的速度以及加速度受到最大范围的限制：

式中：
Umax和Vmax分别为无人机可达到的最大加速度和最大速度。

个体控制量可分为两个部分：
集群内部个体运动控制与避免环境威胁控制，即

ui（t）=uiα（t）+uiβ（t）（6）

式中：
uiα（t）为集群内部个体运动控制量，主要基于避撞规则防止与其他无人机相撞，见式（7）;uiβ（t）为避免环境威胁控制量，计算思路见第5节。

uiα（t）=∑j∈Ri， j≠i1rij-1dr（xi-xj） （7）

式中：
rij为无人机j到无人机i的距离; dr为无人机间的最大安全距离;xi和xj为无人机的位置向量。

2 单侧区域分割的多无人机扫描线搜索算法

（1） 任意多边形的等面积单侧区域分割方法：首先采用格雷厄姆算法将任意多边形区域拓展为凸多边形区域，然后对凸多边形的区域分割展开研究。同时对于一个较大的任务区域，采用多个方向分割的方式会使得同一位置起飞的无人机飞到各个初始位置再进行搜索的效率不高，因此研究对于多边形同一侧（边）作为初始位置的区域分割方法。

（2） 根据区域分割结果计算扫描线位置：
多边形区域分割之后，获得了多个不同的小多边形区域，以分割线的方向作为无人机初始运动方向，同时根据无人机搜索范围计算得到每个小区域的扫描线的数量以及位置。

（3） 基于人工勢场法得到搜索路径：
得到扫描线的数量以及位置之后，还需要规避障碍物以及威胁，因此考虑使用具有良好避撞效果以及可以得到平滑运动轨迹的人工势场法来计算搜索路径。

本文扫描线搜索研究内容及过程如图2所示。

3 任意多边形的等面积单侧区域分割方法

3.1 区域预处理

为了解决基于区域覆盖需求的搜索任务问题，提出一种新的多边形区域分割方法——等面积单侧区域分割算法（Unilateral Region Segmentation）。

首先采用格雷厄姆算法[12]将任意多边形区域拓展为凸多边形区域，如图3所示，然后对凸多边形的区域分割展开研究。

3.2 区域分割

设任一凸多边形搜索任务区域为P，其顶点序列V（P）按照逆时针进行排列，共有N架无人机对任务区域进行搜索侦察。本文针对的是大型搜索任务区域，并没有采用无人机的初始位置位于多边形区域的多条边（角）上，而是认为无人机群在飞往任务区时优先选择飞往任务区域的一条边上，然后展开搜索。因此，可将多边形的一条边作为无人机群开始搜索的起始位置，如图4所示。这样基于等面积的凸多边形的单侧区域分割方法计算分割线的过程如下：

Step 1：
取多边形任务区域的一条边作为起始边，将这条边等分为N份，以这条边逆时针方向第一个顶点作为第1架无人机的起始位置，N-1个等分点作为剩下N-1架无人机的起始位置，该起始位置序列用S（N）表示，并且令V（1）=S（1）。

Step 2：
计算将凸多边形区域N等分之后的面积，记为Aave。

Step 3：
令Nv=Size（V），Ns=Size（S），Vtemp=[V（Nv）， V（1）， S（2）]，计算其面积记为Atemp，如果Atemp=Aave，则执行Step 4;如果Atemp>Aave，则执行Step 5;如果Atemp

Step 4：
该条分割线起点为S（2），终点为V（Nv）。令V（1）=S（2），S（Ns）去掉第一个点，转至Step 3计算下一条分割线。

Step 5：
在（V（Nv）， V（1））这条边上找寻一点E，使得[V（1）， S（2）， E]的面积等于Aave，此时该条分割线起点为S（2），终点为E。令V（1）=S（2），并将E点放至V的序列最后，S（Ns）去掉第一个点，转至Step 3计算下一条分割线。

Step 6：
在（V（Nv）， V（Nv-1））这条边上找寻一点E，使得[V（Nv）， V（1）， S（2）， E]的面积等于Aave，如果这条边上找不到这样一个点，则在（V（Nv-1）， V（Nv-2））这条边上找寻，以此类推直至找到E点，则该条分割线起点为S（2），终点为V（Nv）。同样地，更新V序列，S（Ns）去掉第一个点，转至Step 3计算下一条分割线。

直至计算完N-1条分割线的起点终点，结束计算。

4 扫描线位置的计算

在得到任意多边形区域的分割结果之后，对每个分割后的区域进行扫描线的计算，得到该区域扫描线的数量以及每条扫描线的两个端点，计算扫描线的过程如下：

设计算的区域为V，Nv=Size（V），即该区域顶点数。

Step 1：
取该区域的（V（1），V（Nv））这条边作为基准线（起始方向），计算这条线的斜率、截距。

Step 2：
计算与基准线平行且过距离基准线最远的顶点的直线的截距，并求出最大距离，进而根据搜索能力的要求（搜索范围）求出该区域扫描线的数量。

Step 3：
计算每条与基准线平行的扫描线与区域V的两个交点的位置：
遍历该扫描线与V上所有边所在直线的交点，并判断交点是否属于该边，以此得到扫描线端点位置。

Step 4：
将得到的扫描线的端点按“Z”字扫描线进行排序。

5 基于人工势场法对威胁进行规避

在搜索过程中会有障碍物、禁飞区、雷达等威胁的存在，本文采用人工势场法[13]进行规避威胁得到扫描线的航迹。人工势场法的原理[14]是在无人机周围构建一种虚拟的势场指引无人机的运动，运动环境中的威胁产生斥力场，目标点产生引力场，人工势场由这两种势场叠加而成，对势场中的无人机起到作用，飞行路径由其受到的复合场函数梯度下降方向决定。

5.1 引力势场

引力势场主要与无人机和目标点间的距离有关，距离越大，无人机所受的势能值就越大;距离越小，无人机所受的势能值则越小，所以引力势场的计算函数为

Uigra=η2r2ig（8）

式中：
rig为无人机个体i到目标点g之间的距离;η为正比例增益系数。对应的引力可表示为

Figra=ηrig（9）

引力方向与xig相同，xig为无人机个体i指向目标点g的向量。

5.2 斥力势场

决定障碍物斥力势场的因素是无人机与威胁之间的距离。当无人机未进入障碍物的影响范围时，其受到的势能值为零;在无人机进入威胁的影响范围后，两者直接的距离越大，无人机受到的势能值就越小，距离越小，无人机受到的势能值就越大。斥力势场的计算函数为

式中：
k为正比例系数;rit为无人机个体i到威胁中心t之间的距离;R为威胁对无人机产生作用的最大距离（影响距离）。相应的斥力为斥力场的负梯度，即

Firep=k1rit-1R1r2igrit∈（0， R）

0rit≥R（11）

斥力方向与xti相同，xti为威胁中心t指向无人机个体i的向量。

5.3 合力势场

根据人工势场法原理，无人机受到以上引力势场与斥力势场所组成的复合场的作用，在无人机前往目标点的过程中很可能同时受到多个威胁的斥力场的作用，即无人机所受到的斥力场的作用是叠加的，则无人机所受的合力势场的作用可表示为

Ui=Uigra+∑Uirep（12）

无人机所受的合力可表示为

Fi=Figra+∑Firep（13）

6 场景仿真与分析

本文基于一定的任务场景进行仿真，场景设定为：
在已知的一个任意多边形的搜索任务区内，分派Nu个无人机节点对4个静目标和2个动目标进行侦察搜索，无人机的传感器类型为具有下视能力的截击雷达，探测半径为25～50 km。仿真测试过程如下。

6.1 单侧区域分割方法

任意四边形、五边形、多边形10架机区域分割结果如图5所示;

任意五边形1架、10架、20架机区域分割结果如图6所示。

从图中可以看出，该区域分割算法能够实现任意不同凸多边形、任意无人机数量的等面积单侧区域分割。

6.2 扫描线位置的计算

不同多边形8架机小搜索范围的仿真对比如图7所示;同一多边形8架机不同搜索范围的仿真对比如图8所示;同一多边形8架、16架机小搜索范围的仿真对比如图9所示。

从图中可以看出，该方法能够实现任意不同凸多边形、任意无人机数量，以及不同搜索范围需求的扫描线搜索，具有很好的适应性。

6.3 规避威胁后的无人机轨迹

此仿真场景下，设置2个禁飞区以及4个敌方雷达，无人机搜索过程中应避开这些威胁，仿真结果如下。

不同多边形8架机小搜索范围航迹对比如图10所示;同一多边形8架机不同搜索范围航迹对比如图11所示;

同一多邊形8架、16架机小搜索范围航迹对比如图12所示。

从图中可以看出，本文提出的区域全覆盖的扫描线搜索算法不仅能够适应多样的区域几何形状，而且对于不同无人机数量、不同搜索范围的选择均有良好的适应性;从搜索目标的能力来看，不论是静目标还是动目标均具有极高的搜索能力。

6.4 与其他搜索方法的比较

最后，与目前应用比较广泛的一种基于搜索图采用滚动优化方式在线求解最优航迹的分布式多无人机协同搜索方法进行对比，该方法能够有效实现多无人机之间的协同搜索，同时保证良好的时间优越性以及有效降低环境的不确定性等优势，搜索航迹的对比如图13所示。

主要采取以下统计指标来综合衡量两种不同搜索方法下的搜索效率：

（1） 平均区域覆盖率：
该指标表示多次仿真条件下无人机在一定任务时间内搜索过的区域占总任务区域的平均面积比。

（2） 平均发现目标数量：
该指标表示多次仿真条件下无人机在足够的任务时间内搜索到目标的平均数量。

在任意五边形任务区域内，分派8架无人机对4个静目标与2个动目标进行搜索，两种搜索方法各进行10次仿真，其搜索指标对比结果如图14与表1所示。

从图14可以看出，到仿真结束时，本文提出的基于单侧区域分割算法的多无人机扫描线搜索方法的平均区域覆盖率为96.1%，而基于搜索图的滚动时域优化方法的分布式多无人机协同搜索方法的平均区域覆盖率仅为69.8%。

从表1可以看出，在动目标的搜索中，基于搜索图的滚动时域优化方法略优于本文所提方法，但搜索效果差别不大;而对于静目标的搜索，本文所提出的基于单侧区域分割算法的多无人机扫描线搜索方法的搜索效果则明显好于另一种搜索方法。仿真测试结果证明了本文所提方法的有效性。

7 结论

本文提出了一种任意搜索区域的等面积单侧区域分割方法，并基于人工势场法规避威胁得到扫描线搜索路径，实现对任务区域的搜索覆盖，最后结合扫描线搜索任务特点进行仿真分析。仿真分析结果表明所提方法可实现对待搜索区域的全面覆盖，同时能够在避免威胁的基础上有效提高多无人机系统覆盖侦察效率。

本文所提方法解决了搜索区域几何形状对搜索问题的限制问题;相比传统扫描线搜索的方法，考虑了搜索区域中存在威胁的情况;与栅格化的扫描线方法相比更加符合无人机机动性的要求。但该方法是在考虑搜索区域较大以及无人机从搜索区域外指定位置飞到搜索区域进行搜索的情况下提出的，因此无人机的起始点限定在了区域的一侧用来解决相应的搜索问题。未来可能会从多方向进行搜索的问题展开研究。

参考文献：

[1] 张立鹏， 赵建辉， 肖永德. 基于最大可知度的无人机协同搜索控制方法[J]. 电光与控制， 2014， 21（11）：
33-40.

Zhang Lipeng， Zhao Jianhui， Xiao Yongde. A Control Method for the UAV Cooperative Searching Based on Uncertainty Value Reducing Maximization [J]. Electronics Optics and Control， 2014， 21（11）：
33-40. （in Chinese）

[2] 符小卫， 魏广伟， 高晓光. 不确定环境下多无人机协同区域搜索算法[J]. 系统工程与电子技术， 2016， 38（4）：
821-827.

Fu Xiaowei，Wei Guangwei，Gao Xiaoguang. Cooperative Area Search Algorithm for Multi-UAVs in Uncertainty Environment[J]. Systems Engineering and Electronics， 2016， 38（4）：
821-827. （in Chinese）

[3] Lu Ping. Predictor-Corrector Entry Guidance for Low-Lifting Vehicles[J]. Journal of Guidance， Control， and Dynamics， 2008， 31（4）：
1067-1075.

[4] Joshi A， Sivan K， Amma S S. Predictor-Corrector Reentry Gui-dance Algorithm with Path Constraints for Atmospheric Entry Vehicles[J]. Journal of Guidance， Control， and Dynamics， 2007， 30（5）：
1307-1318.

[5] Altshuler Y， Yanovsky V， Wagner I A， et al. Efficient Cooperative Search of Smart Targets Using UAV Swarms[J]. Robotica， 2008， 26（4）：
551-557.

[6] Erignac C A. An Exhaustive Swarming Search Strategy Based on Distributed Pheromone Maps[C]∥ AIAA Infotech@Aerospace 2007 Conference and Exhibit，Rohnert Park，2007：
1130-1145.

[7] 赵晨皓， 刘永兰， 赵杰. 一种基于PEGA 算法的UAV 區域覆盖搜索路径规划方法[J]. 科技导报， 2014， 32（28/29）：85-90.

Zhao Chenhao， Liu Yonglan， Zhao Jie. Path Planning Method of UAV Area Coverage Searching Based on PEGA[J]. Science & Technology Review， 2014， 32（28/29）：85-90. （in Chinese）

[8] 赵晨皓， 李为民， 刘永兰， 等. 多异构无人机覆盖搜索任务区域分配方法研究[J]. 战术导弹技术， 2014（6）：
32-37.

Zhao Chenhao， Li Weimin， Liu Yonglan， et al. Research on Mi-ssion Area Allocation Method for Multiple Heterogeneous UAVs Area Coverage Searching[J]. Tactical Missile Technology， 2014（6）：
32-37. （in Chinese）

[9] 吴青坡， 周绍磊， 闫实. 复杂区域多UAV覆盖侦察方法研究[J]. 战术导弹技术， 2016（1）：
50-55.

Wu Qingpo， Zhou Shaolei， Yan Shi. Multi-UAVs Cooperative Coverage Reconnaissance in Complex Area[J]. Tactical Missile Technology， 2016（1）：
50-55. （in Chinese）

[10] 彭辉， 沈林成， 霍霄华. 多UAV协同区域覆盖搜索研究[J]. 系统仿真学报， 2007， 19（11）：
2472-2476.

Peng Hui， Shen Lincheng， Huo Xiaohua. Reasearch on Multiple UAV Cooperative Area Coverage Searching[J]. Journal of System Simulation， 2007， 19（11）：
2472-2476. （in Chinese）

[11] 于驷男， 周锐， 夏洁， 等. 多无人机协同搜索区域分割与覆盖[J]. 北京航空航天大学学报， 2015， 41（1）：
167-173.

Yu Sinan， Zhou Rui， Xia Jie， et al. Decomposition and Coverage of Multi-UAV Cooperative Search Area[J]. Journal of Beijing University of Aeronautics and Astronautics， 2015， 41（1）：167-173. （in Chinese）

[12] Graham R L. An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set[J]. Information Processing Letters， 1972， 1（4）：
132-133.

[13] Khatib O. Real-Time Obstacle Avoidance for Manipulators and Mobile Robots[M]∥Cox I J，Wilfong G T. Autonomous Robot Vehicles. New York：
Springer， 1986：396-404.

[14] Ge S S， Cui Y J. New Potential Functions for Mobile Robot Path Planning[J]. IEEE Transactions on Robotics and Automation， 2000， 16（5）：615-620.

Research on Scanning Line Search Method for Multi-UAV

Based on Unilateral Region Segmentation

Xie Pengzhi， Wei Chen*

（School of Automation Science and Electrical Engineering， Beihang University， Beijing 100083， China）

Abstract：Aiming at the requirement of area coverage task， the multi-UAV scanning line search task is researched. Firstly， an unilateral region segmentation for equal area （URSEA） method for arbitrary search region is proposed. Each search area is assigned one or a group of UAVs for scanning line search， and then obstacles or threats are evaded based on the artificial potential field method to obtain the search path. Finally， simulation analysis is carried out to verify the effectiveness， robustness and adaptability of the algorithm in different situations. The algorithm has obvious advantages when facing arbitrary search area， considering UAV maneuverability and threat.

Key words：multi-UAV;arbitrary search region;region segmentation;scanning line search;artificial potential field method;path planning

收稿日期：2019-07-17

基金項目：
国家自然科学基金项目（91648205）;航空科学基金项目（20185851022）

作者简介：
谢朋志（1993-），男，吉林舒兰人，硕士研究生，研究方向为无人机集群智能感知与搜索。

通讯作者：魏晨（1971- ），女，山东聊城人，博士，副教授，研究方向为非线性控制、模糊控制及时滞系统。

E-mail：weichen@buaa.edu.cn

引用格式：
谢朋志， 魏晨. 单侧区域分割的多无人机扫描线搜索方法研究[ J].

航空兵器，2020， 27（ 3）：
67-72.

Xie Pengzhi， Wei Chen. Research on Scanning Line Search Method for Multi-UAV Based on Unilateral Region Segmentation [ J]. Aero Weaponry，2020， 27（ 3）：
67-72.（in Chinese）