凹多边形区域覆盖无人机航迹规划方法
王自亮 罗德林 吴顺祥
摘要：覆盖航迹规划技术对于提高无人机的目标搜索能力和正确完成任务能力具有重要的意义。针对凹多边形区域形状，本文提出一种无人机覆盖算法，该算法旨在协助无人机自主完成无遗漏地覆盖搜索给定区域。首先，描述了如何选取无人机的飞行方向;其次，给出了如何将凹多边形转变为凸多边形的流程，并详细说明无人机覆盖区域的过程;最后，通过仿真示例验证了算法的有效性与正确性。
关键词：无人机;航迹规划;目标搜寻;区域覆盖;凹多边形
中图分类号：TJ760;V279文献标识码：A文章编号：1673-5048（2019）01-0095-06[SQ0]
0引言
无人机（UAV）已经被广泛用于军用和民用领域，航迹规划是保证无人机实现真正意义的“无人”的关键。覆盖区域作为无人机的重要任务之一，要求无人机能够无遗漏地覆盖给定区域。
目前，国内外对于无人机的航迹规划算法有大量的研究。文献[1-2]采用算法规划无人机的侦察路径，无人机依照此路径飞行保证代价最小。文献[3]采用Voronoi图根据威胁源划分给定区域，在此基础上计算出一条能够规避危险的路径，保证无人机可以安全抵达目标位置。文献[4]提出了构造目标存在概率图，采用遗传算法实现无人机的航迹规划。上述航迹规划的方法都是基于点到点的，即无人机位置到目标位置，没有实现无遗漏地覆盖给定区域。文献[5-6]采用之字形覆盖策略实现了无遗漏地覆盖凸多边形区域，其中文献[6]提到将凹多边形进行凸分割后，无人机再覆盖每个凸的子区域。在这两篇文献的研究基础上，本文通过寻找最小宽度所对应的边从而确定飞行方向，并详细描述了无需将凹多边形区域先进行凸分割预处理，无人机直接进入区域执行覆盖任务的算法。
通过仿真示例验证算法的有效性与正确性，并进行总结。由于无人机具有转弯半径的限制，假设无人机的转弯半径和无人机上携带的探测器的探测半径相等。
1航迹规划算法
1.1飞行方向的选择
文献[7]给出了无人机在覆盖区域为凸多边形时飞行方向选取的证明，即飞行路径平行于最小宽度所在的边时能够保证转弯次数最少。对于区域为凹多边形时，飞行方向的选取和凸多边形的情况一致，飞行路径仍然和最小宽度所在的边平行，这样能够保证无人机完成覆盖任务且飞行路径最短。
3结论
无人机的路径规划在许多领域具有重要的作用，本文对无人机覆盖凹多边形区域进行了研究。按照所提出的算法，能够保证无人机尽可能地少覆盖无需搜索的区域完成覆盖给定区域的任务，且不需要对区域进行凸分割处理，再让无人机对每个凸多边形子区域进行覆盖，实现无人机直接对区域进行覆盖。
多无人机协同完成任务是未来的研究趋势。本文仅仅描述了单架无人机覆盖凹多边形区域，对于多无人机协同覆盖搜索给定区域，首先需要按照无人机可覆盖面积大小对区域进行分割，文献[8]中给出了解决方案，分割好的每个子区域都分派一架无人机。随后每个子区域由其所对应的无人机完成覆盖搜索的任务，可以由本文提出的算法完成。
参考文献：
[1]张一豆，赵剡，魏彤.基于改进的A*算法的导盲避障路径规划策略研究[J].航空兵器，2017（3）：86-92.
ZhangYidou，ZhaoYan，WeiTong.ImprovedA*AlgorithmforObstacleAvoidancePathPlanningStrategyoftheBlind[J].AeroWeaponry，2017（3）：86-92.（inChinese）
[2]宋雪倩，胡士强.基于Dubins路径的A*算法的多无人机路径规划[J].电光与控制，2018，25（11）：25-29.
SongXueqian，HuShiqiang.MultiUAVPathPlanningbyDubinsPathBasedA*Algorithm[J].ElectronicsOptics&Control，2018，25（11）：25-29.（inChinese）
[3]史红玉，刘淑芬.基于Voronoi图的无人机航路改进规划[J].吉林大学学报：理学版，2018，56（4）：945-952.
ShiHongyu，LiuShufen.UnmannedAerialVehicleRouteImprovementPlanningBasedonVoronoiDiagram[J].JournalofJilinUniversity：ScienceEdition，2018，56（4）：945-952.（inChinese）
[4]张莹莹，周德云，夏欢.不确定环境下多无人机协同搜索算法研究[J].电光与控制，2012，19（2）：5-8.
ZhangYingying，ZhouDeyun，XiaHuan.CooperativeSearchAlgorithmforMultiUAVinUncertainEnvironment[J].ElectronicsOptics&Control，2012，19（2）：5-8.（inChinese）
[5]于驷男，周锐，夏洁，等.多无人机协同搜索区域分割与覆盖[J].北京航空航天大学学报，2015，41（1）：167-173.
YuSinan，ZhouRui，XiaJie，etal.DecompositionandCoverageofMultiUAVCooperativeSearchArea[J].JournalofBeijingUniversityofAeronauticsandAstronautics，2015，41（1）：167-173.（inChinese）
[6]陳海，王新民，焦裕松，等.一种凸多边形区域的无人机覆盖航迹规划算法[J].航空学报，2010，31（9）：1802-1808.
ChenHai，WangXinmin，JiaoYusong，etal.AnAlgorithmofCoverageFlightPathPlanningforUAVsinConvexPolygonAreas[J].ActaAeronauticaetAstronauticaSinica，2010，31（9）：1802-1808.（inChinese）
[7]AraujoJF，SujitPB，SousaJB.MultipleUAVAreaDecompositionandCoverage[C]∥IEEESymposiumonComputationalIntelligenceforSecurityandDefenceApplications（CISDA），Singapore，2013：30-37.
[8]HertS，LumelskyV.PolygonAreaDecompositionforMultipleRobotWorkspaceDivision[J].InternationalJournalofComputationalGeometry&Applications，1999，8（4）：437-466.
