凹多邊形區(qū)域覆蓋無人機(jī)航跡規(guī)劃方法

王自亮 羅德林 吳順祥

摘要：覆蓋航跡規(guī)劃技術(shù)對于提高無人機(jī)的目標(biāo)搜索能力和正確完成任務(wù)能力具有重要的意義。針對凹多邊形區(qū)域形狀，本文提出一種無人機(jī)覆蓋算法，該算法旨在協(xié)助無人機(jī)自主完成無遺漏地覆蓋搜索給定區(qū)域。首先，描述了如何選取無人機(jī)的飛行方向;其次，給出了如何將凹多邊形轉(zhuǎn)變?yōu)橥苟噙呅蔚牧鞒蹋⒃敿?xì)說明無人機(jī)覆蓋區(qū)域的過程;最后，通過仿真示例驗證了算法的有效性與正確性。

關(guān)鍵詞：無人機(jī);航跡規(guī)劃;目標(biāo)搜尋;區(qū)域覆蓋;凹多邊形

中圖分類號：TJ760;V279文獻(xiàn)標(biāo)識碼：A文章編號：1673-5048（2019）01-0095-06[SQ0]

0引言

無人機(jī)（UAV）已經(jīng)被廣泛用于軍用和民用領(lǐng)域，航跡規(guī)劃是保證無人機(jī)實現(xiàn)真正意義的“無人”的關(guān)鍵。覆蓋區(qū)域作為無人機(jī)的重要任務(wù)之一，要求無人機(jī)能夠無遺漏地覆蓋給定區(qū)域。

目前，國內(nèi)外對于無人機(jī)的航跡規(guī)劃算法有大量的研究。文獻(xiàn)[1-2]采用算法規(guī)劃無人機(jī)的偵察路徑，無人機(jī)依照此路徑飛行保證代價最小。文獻(xiàn)[3]采用Voronoi圖根據(jù)威脅源劃分給定區(qū)域，在此基礎(chǔ)上計算出一條能夠規(guī)避危險的路徑，保證無人機(jī)可以安全抵達(dá)目標(biāo)位置。文獻(xiàn)[4]提出了構(gòu)造目標(biāo)存在概率圖，采用遺傳算法實現(xiàn)無人機(jī)的航跡規(guī)劃。上述航跡規(guī)劃的方法都是基于點(diǎn)到點(diǎn)的，即無人機(jī)位置到目標(biāo)位置，沒有實現(xiàn)無遺漏地覆蓋給定區(qū)域。文獻(xiàn)[5-6]采用之字形覆蓋策略實現(xiàn)了無遺漏地覆蓋凸多邊形區(qū)域，其中文獻(xiàn)[6]提到將凹多邊形進(jìn)行凸分割后，無人機(jī)再覆蓋每個凸的子區(qū)域。在這兩篇文獻(xiàn)的研究基礎(chǔ)上，本文通過尋找最小寬度所對應(yīng)的邊從而確定飛行方向，并詳細(xì)描述了無需將凹多邊形區(qū)域先進(jìn)行凸分割預(yù)處理，無人機(jī)直接進(jìn)入?yún)^(qū)域執(zhí)行覆蓋任務(wù)的算法。

通過仿真示例驗證算法的有效性與正確性，并進(jìn)行總結(jié)。由于無人機(jī)具有轉(zhuǎn)彎半徑的限制，假設(shè)無人機(jī)的轉(zhuǎn)彎半徑和無人機(jī)上攜帶的探測器的探測半徑相等。

1航跡規(guī)劃算法

1.1飛行方向的選擇

文獻(xiàn)[7]給出了無人機(jī)在覆蓋區(qū)域為凸多邊形時飛行方向選取的證明，即飛行路徑平行于最小寬度所在的邊時能夠保證轉(zhuǎn)彎次數(shù)最少。對于區(qū)域為凹多邊形時，飛行方向的選取和凸多邊形的情況一致，飛行路徑仍然和最小寬度所在的邊平行，這樣能夠保證無人機(jī)完成覆蓋任務(wù)且飛行路徑最短。

3結(jié)論

無人機(jī)的路徑規(guī)劃在許多領(lǐng)域具有重要的作用，本文對無人機(jī)覆蓋凹多邊形區(qū)域進(jìn)行了研究。按照所提出的算法，能夠保證無人機(jī)盡可能地少覆蓋無需搜索的區(qū)域完成覆蓋給定區(qū)域的任務(wù)，且不需要對區(qū)域進(jìn)行凸分割處理，再讓無人機(jī)對每個凸多邊形子區(qū)域進(jìn)行覆蓋，實現(xiàn)無人機(jī)直接對區(qū)域進(jìn)行覆蓋。

多無人機(jī)協(xié)同完成任務(wù)是未來的研究趨勢。本文僅僅描述了單架無人機(jī)覆蓋凹多邊形區(qū)域，對于多無人機(jī)協(xié)同覆蓋搜索給定區(qū)域，首先需要按照無人機(jī)可覆蓋面積大小對區(qū)域進(jìn)行分割，文獻(xiàn)[8]中給出了解決方案，分割好的每個子區(qū)域都分派一架無人機(jī)。隨后每個子區(qū)域由其所對應(yīng)的無人機(jī)完成覆蓋搜索的任務(wù)，可以由本文提出的算法完成。

參考文獻(xiàn)：

[1]張一豆，趙剡，魏彤.基于改進(jìn)的A*算法的導(dǎo)盲避障路徑規(guī)劃策略研究[J].航空兵器，2017（3）：86-92.

ZhangYidou，ZhaoYan，WeiTong.ImprovedA*AlgorithmforObstacleAvoidancePathPlanningStrategyoftheBlind[J].AeroWeaponry，2017（3）：86-92.（inChinese）

[2]宋雪倩，胡士強(qiáng).基于Dubins路徑的A*算法的多無人機(jī)路徑規(guī)劃[J].電光與控制，2018，25（11）：25-29.

SongXueqian，HuShiqiang.MultiUAVPathPlanningbyDubinsPathBasedA*Algorithm[J].ElectronicsOptics&Control，2018，25（11）：25-29.（inChinese）

[3]史紅玉，劉淑芬.基于Voronoi圖的無人機(jī)航路改進(jìn)規(guī)劃[J].吉林大學(xué)學(xué)報：理學(xué)版，2018，56（4）：945-952.

ShiHongyu，LiuShufen.UnmannedAerialVehicleRouteImprovementPlanningBasedonVoronoiDiagram[J].JournalofJilinUniversity：ScienceEdition，2018，56（4）：945-952.（inChinese）

[4]張瑩瑩，周德云，夏歡.不確定環(huán)境下多無人機(jī)協(xié)同搜索算法研究[J].電光與控制，2012，19（2）：5-8.

ZhangYingying，ZhouDeyun，XiaHuan.CooperativeSearchAlgorithmforMultiUAVinUncertainEnvironment[J].ElectronicsOptics&Control，2012，19（2）：5-8.（inChinese）

[5]于駟男，周銳，夏潔，等.多無人機(jī)協(xié)同搜索區(qū)域分割與覆蓋[J].北京航空航天大學(xué)學(xué)報，2015，41（1）：167-173.

YuSinan，ZhouRui，XiaJie，etal.DecompositionandCoverageofMultiUAVCooperativeSearchArea[J].JournalofBeijingUniversityofAeronauticsandAstronautics，2015，41（1）：167-173.（inChinese）

[6]陳海，王新民，焦裕松，等.一種凸多邊形區(qū)域的無人機(jī)覆蓋航跡規(guī)劃算法[J].航空學(xué)報，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.