王自亮 羅德林 吳順祥
摘要:覆蓋航跡規(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ī)劃的方法都是基于點到點的,即無人機(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.