搜索
31 9 Vol.31No.9 2010 9ACTAAERONAUTICAETASTRONAUTICASINICASept. 2010:2009-09-09;:2009-11-30:E-mail:liyan@nwpu.edu.cn :1000-6893(2010)09-1802-07,,,(, 710072)AnAlgorithmofCoverageFlightPathPlanningforUAVsinConvexPolygonAreasChenHai,WangXinmin,JiaoYusong,LiYan(CollegeofAutomation,NorthwesternPolytechnicalUniversity,Xi'an 710072,China) :。、、,。,。“”,“”。,。,。:;;;;:V279 :AAbstract:ThecoverageflightpathplanningisveryimportanttoenhancetheUAV'sabilitiesofreconnaissanceandtargetsearching.Fromtheviewpointsofenergy,routelengthandduration,theturningmotionisprovedtobelessefficientcomparedwiththeflatflyingtheoretically.Thedefinitionsofspanandwidthforconvexpol-ygonsaregiven,andtheproblemofcoverageflightpathplanninginaconvexpolygonareaistransformedtothewidthcalculationoftheconvexpolygon.Ahighperformancevertex-edgealgorithmtoobtainthewidthofaconvexpolygonisgivenbasedonthetheoremwhichprovesthatonlyvertex-edgepairsneedtobeconsideredinthecomputationofthewidth.IfaUAVfliesalongthedirectionofparallellinesofsupportwiththeobtai-ningofwidth,thecoveragepathcangettheleastnumberofturns.Finally,asimulationisimplementedandtheresultprovesthattheproposedalgorithmcansolvetheproblemofcoverageflightpathplanninginaconvexpolygonefficiently.Keywords:unmannedaerialvehicles;convexpolygonarea;coverageflightpathplanning;span;width (UnmannedAerialVehicle,UAV)、、、、、,。(FlightPathPlanning),,。“”,,,[1]。,,(CoverageFlightPathPlanning)。,,[2]。、、、、。,“”,,[3-5]。(CoveragePathPlanning)[6],。:①、、,,;②,;③ 9: 、、,。[7-8],,,[9-10]。,,,。1 ,,,。,:(1)。(2),,,,,[3]。(3)。(4),。,,Sk(Okxkykzk)[11]:mdvdt=T-D-Gsinμmvdμdt=Lcosγ-Gcosμ(mvcosμ)dφdt=Lsinγ(1):m;v;T;D;G;L;μ;φ;γ。,,dv/dt=0,dμ/dt=0,μ=0。(mvcosμ)dφ/dt=mv2/r,r,(1)T=D(2a)Lcosγ=G(2b)mv2/r=Lsinγ(2c)(2a);(2b);(2c)[12]。,r=mv2Lsinγ=v2g·GL·1sinγ=v2gn2z-1(3):nz=L/G。(2b),nz=1/cosγ。U,t=πrv=πvgn2z-1(4)(2b)L=Gcosγ(5)cosγ1,LG。。nz=L/G=1/cosγCL=nzG12ρv2S=nzGQS(6):ρ;S;Q=ρv2/2。,D=12ρv2CDS=12ρv2S(CD0+KC2L)=12ρv2SCD0+KnzG12ρv2S2=D0+n2zDt (7):CD;CD0;K;D0Dt、。(7),、,、。(2a),,。,,。,,。2 ,1。1803 311 Fig.1 CamerafootprintofaUAV1:H;h;FOVv(VerticalFieldofView),OKFOVv;FOVh(HorizontalFieldofView),OFOEFOVh;θ;αf,FOVv;d;w1;w2;ABCI。ABCI。,,、。,,,,2。2 UFig.2 U-turnofaUAV2:;;w,,w1。2,U,。,2d+(π/2-1)w。,,,,。,,,。,。3 ,V。lalllall=lin+lout(8):lin;lout。V,lin=∑nturn+1k=1lin,k=AV/w(9):lin,kk;AV;nturn。w=w1=2htan(FOVh/2)sin(αf-θ-FOVv/2)(10):αf、FOVvFOVh,。,wθh。θh,。,θh。,w。,AV。,lin。lout。loutlout=lturnnturn(11):lturn,,。,,nturn,。nturnnturn=Ds/w-1(12)1804 9: :Ds;＊。,。1 ,,Ds。W,(ParallelLinesofSupport),3。,。3 Fig.3 Spansandwidthsofconvexpolygons3:“”(3(a)),“”(3(b))“”(3(c))[13]。“”;“”;“”。“”“”,,。3(b)3(c),。,,()。,,。4 “”1 “”(“”“”)[13],。 4,l1l2,V,,A′、B′C′,“”,C′F′Ds1。4 Fig.4 Twokindsofconvexpolygonspan,Vl1l2(4A′C′),。l1l2A′C′(,4),(4A′B′),l′1l′2。V“”,,,。C′l′1C′D′,C′D′Vl′1l′2(Ds2)。∠C′D′E′,C′D′C′E′C′F′,“”“”。。,“”“”“”,“”。“”“”,。。2 。 1,“”,,,,2。。1805 31,“”,:,;,,;,;,,。,“”。 V{v1,v2,…,vn+1},n。vi(i∈[1,n+1])(xi,yi),(xn+1,yn+1)=(x1,y1)。 WlWvW(vWlW)。1 i→1。2 j→1。3 j≠ij≠i+1(vivi+12vivi+1vivi+1),(13)vjvivi+1:distance2ij=(yi+1-yi)xj-(xi+1-xi)yj+xi+1yi-xiyi+12(yi+1-yi)2+(xi+1-xi)2(13) 4 j=n5,j→j+13。5 vivi+1n-2distance2ijmaxdistance2i(vivi+1),maxindexi。6 i=n7,i→i+12。7 maxdistance2iW,lWvW。3 “”,O(n2)。 1,“”,“”1～5,7,,,。“”3(13),88。3n(n-2),,16n(n-2)。,O(n2)。。“”3vivi+1vivi+1。,,。vivi+1n-2,(13),,(13)distance′ij=|(yi+1-yi)xj-(xi+1-xi)yj+xi+1yi-xiyi+1|(14) 9n(n-2)n(n-2)。,,。5 ,,,,。5,{v1,v2,v3,v4,v5,v6},V={(14.5488,1.7658),(21.4962,3.4383),(29.4813,20.2185),(24.1992,29.9835),(21.1071,28.8492),(5.5770,17.0031)}×102m5 Fig.5 Uncoveredconvexpolygonarea V1806 9: v2v3,v6。,v2v3,。,(15):x′=(x-a)cosω+(y-b)sinωy′=-(x-a)sinω+(y-b)cosω(15):(a,b)O′Oxy;ωO′x′Ox。O′x′,,。,V′={(4.0000,5.5547),(8.4955,0),(27.0787,0),(33.6266,8.9656),(31.2737,11.2702),(13.9038,20.2033)}×102m ,,,;;,w=2×102m。6。6 Fig.6 Coverageflightpathinconvexpolygonarea6,,。6,,。6 。,,,。。,,,;,:,,,,;、,:,,,,。,,,,。 [1] BortoffSA.PathplanningforUAVs[C]∥TheProceed-ingsoftheAmericanControlConference.2000:364-368.[2] AgarwalA,LimMH,ErMJ,etal.ACOforanewTSPinregioncoverage[C]∥IEEE/RSJInternationalConfer-enceonIntelligentRobotsandSystems.2005:1717-1722.[3] ChoestH.Coverageforrobotics—asurveyofrecentre-sults[J].AnnalsofMathematicsandArtificialIntelli-gence,2001,31(1/2/3/4):113-126.[4] GabrielyY,RimonE.Spanning-treebasedcoverageofcontinuousareasbyamobilerobot[C]∥Proceedingsofthe2001IEEEInternationalConferenceonRoboticsandAutomation.2001:1927-1933.[5] AcarEU,ChosetH,RizziAA,etal.Morsedecomposi-tionsforcoveragetasks[J].TheInternationalJournalofRoboticsResearch,2002,21(4):331-344.[6] JonesP,VachtsevanosG,TangL.Multi-unmannedaerialvehiclecoverageplannerforareasurveillancemissions[R].AIAA-2007-6453,2007.[7] AgarwalA,HiotLM,NghiaNT,etal.ParallelregioncoverageusingmultipleUAVs[C]∥2006IEEEAerospaceConference,2006.1807 31[8] MazaI,OlleroA.MultipleUAVcooperativesearchingoperationusingpolygonareadecompositionandefficientcoveragealgorithms[C]∥7thInternationalSymposiumonDistributedAutonomousRoboticsSystems.2004:211-220.[9] HuangWH.Optimalline-sweep-baseddecompositionsforcover