凹多邊形區域覆蓋無人機航跡規劃方法

王自亮 羅德林 吳順祥

摘要：覆蓋航跡規劃技術對于提高無人機的目標搜索能力和正確完成任務能力具有重要的意義。針對凹多邊形區域形狀，本文提出一種無人機覆蓋算法，該算法旨在協助無人機自主完成無遺漏地覆蓋搜索給定區域。首先，描述了如何選取無人機的飛行方向;其次，給出了如何將凹多邊形轉變為凸多邊形的流程，并詳細說明無人機覆蓋區域的過程;最后，通過仿真示例驗證了算法的有效性與正確性。

關鍵詞：無人機;航跡規劃;目標搜尋;區域覆蓋;凹多邊形

中圖分類號：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.