无人机区域覆盖航迹规划技术研究

西北工业大学博士学位论文（学位研究生）题目：无人机区域覆盖航迹规划技术研究作者：陈海学科专业：控制科学与工程指导教师：王新民2010年6月ResearchonAreaCoverageFlightPathPlanningforUAVsByChenHaiInPartialFulfillmentoftheRequirementsfortheDegreeofDoctorofPhilosophyinControlScienceandEngineeringSupervisor:ProfessorWangXin-MinSchoolofAutomationNorthwesternPolytechnicalUniversityJune2010西北工业大学博士学位论文摘要I摘摘摘摘要要要要无人机区域覆盖航迹规划就是在满足某种（某些）性能指标最优的前提下，避开障碍物和威胁源，规划出一条能够遍历待覆盖区域的最优飞行路线。该技术是无人机完成侦察、监视及搜索任务的关键，对于提高无人机的任务执行能力具有重要意义。本文对无人机区域覆盖航迹规划技术进行了深入的研究，提出了一些新颖的思路和算法。本文首先从理论上证明了转弯机动对于无人机覆盖航迹规划来说是低效的，由此确定了本文的优化准则为转弯次数最少；其次把基本区域的覆盖航迹规划问题转化为求凸多边形的宽度问题，只要无人机沿宽度的垂直方向飞行，即可获得最少的转弯次数；接下来对精确单元分解法进行了改进，用于复杂区域的覆盖航迹规划；最后把无人机的任务性能评价和任务区域划分相结合，用于多无人机的协同覆盖航迹规划。本文的主要创新点如下：1.针对无人机覆盖航迹规划过程与机器人的不同，对无人机不同姿态角下的探测区域及转弯机动的运动学特性进行了分析。给出了探测区域的长度和宽度随俯仰角和滚转角变化的数学关系，以及偏航机动时，无人机坐标与探测区域坐标之间的转换公式；推导出了给定巡航速度下燃油消耗量最低的法向过载计算公式；分析了U型转弯和直角转弯过程中探测区域移动路线与无人机飞行路线之间的关系，分三种情况给出了U型转弯过程中转弯路程、转弯时间和距离差值的计算公式；从理论上证明了U型转弯机动比直角转弯机动的效率高。2.提出了一种基本区域的无人机覆盖航迹规划算法。给出了凸多边形跨度和宽度的定义，把基本区域的覆盖航迹规划问题转化为求凸多边形的宽度问题；证明了凸多边形区域的宽度只可能出现于“点边式”跨度之中，缩小了宽度的计算范围；提出了一种距离比较算法，降低了凸多边形跨度的计算量；在“点边式”基本算法和距离比较算法的基础上，提出了一种优化宽度算法，使算法的时间复杂性降低为O(n)。3.提出了一种改进的精确单元分解算法，用于无人机在复杂区域中的覆盖航迹规划。提出了一种基于贪心递归的最小宽度和（MinimalSumofWidth，MSW）西北工业大学博士学位论文摘要II凸划分算法，实现了子区域的最佳划分，并对该多变量递归问题的算法复杂性进行了分析；提出了多边形相邻和完全相邻的概念，对满足完全相邻和宽度方向一致的子区域进行了合并，减少了不必要的往返运动；提出了子区域衔接点的概念，构造了衔接点矩阵以及出点和入点的对应关系，并提出了一种基于赋权无向图最小遍历的子区域衔接算法，实现了子区域之间的最短距离衔接。4.提出了一种由任务性能评价和任务区域划分两部分组成的多无人机协同覆盖航迹规划算法。把层次分析法（AnalyticHierarchyProcess，AHP）和灰关联度分析法（GreyRelationalAnalysis，GRA）相结合，提出了一种AHP-GRA综合评价算法对无人机执行覆盖任务的能力进行了评价；针对传统一致性比例检验法理论性差，高阶计算困难的缺点，把一致性检验问题，转化成了一般的统计假设检验问题，便于理解和计算；提出了一种基于无人机性能和子区域宽度的任务区域划分算法，使规划出的任务区域达到了全局最优。关键词关键词关键词关键词：无人机；覆盖航迹规划；探测区域；最小宽度和；衔接矩阵；AHP-GRA评价法西北工业大学博士学位论文ABSTRACTIIIABSTRACTTheareaCoverageFlightPathPlanning(CFPP)ofUnmannedAerialVehicles(UAVs)istoplanapathtocovertheallpointsofgivenarea,whichsatisfiessomeoptimalperformanceindicesandavoidstheobstaclesandthreatsources.Thistechnologyisthekeytocompletethemissionofreconnaissance,surveillanceandsearchandimprovetheabilityofmissionexecutionforUAVs.ThispaperstudiesthetechnologyofCFPPforUAVsandproposessomenovelideasandalgorithms.Firstly,theturningmaneuverofcoverageforUAVsisprovedtobelessefficientcomparedwiththeflatflyingmaneuver,sotheleastnumberofturnsischosenastheoptimizationcriteria.Secondly,theproblemofCFPPinbasicareasistransformedtothewidthcalculationoftheconvexpolygons.IfaUAVfliesalongtheverticaldirectionofwidth,thecoveragepathcangettheleastnumberofturns.Thirdly,anenhancedexactcellulardecompositionmethodtoplanthecoveragepathofUAVsincomplexpolygonareasisproposed.Finally,themissionperformanceevaluationandmissionregionpartitionarecombinedtoplanthecooperativecoveragepathofmulti-UAVs.Themaininnovationsofthispaperareasfollows:1.ComparingwiththecoveragedifferencesbetweentherobotsandtheUAVs,thecamerafootprintwithdifferentattitudeanglesandkinematicspropertiesinturningmaneuverforUAVsareanalyzed.ThemathematicalformulasofthelengthandthewidthofcamerafootprintinpitchandrollmaneuversandthecoordinatetransformationbetweentheUAVcentroidandthefootprintcenterinyawmaneuveraregiven.Aformulatoobtainthenormalaccelerationforminimumfuelconsumptionundergivenflyingvelocityispresented.TherelationshipsbetweenthecamerafootprintpathsandtheflyingpathsinU-turnandright-angled-turnareanalyzed.Thedistance,durationanddistancedifferencevalueofturnarecalculatedinthreedifferentsituations.ItisprovedthattheU-turnismoreefficientthantheright-angled-turnintheory.2.AnalgorithmtoplanthecoveragepathforUAVsinthebasicareaisproposed.Thedefinitionsofspanandwidthofconvexpolygonsaregiven,andtheproblemofCFPPinconvexpolygonareasistransformedtothewidthcalculationoftheconvexpolygon.Itisprovedthatthewidthofaconvexpolygononlybefoundinthespanofvertex-edgepairs.Inthisway,therangeofcalculationnarrowsdown.Thenanalgorithmusingdistancecomparisonisinvestigatedtoreducethecalculatedamountof西北工业大学博士学位论文ABSTRACTIVthespan.Basedonthebasicalgorithmofvertex-edgepairsandthedistancecomparison,anoptimalalgorithmtocalculatethewidthisproposed,whosetimecomplexityisO(n).3.AnenhancedexactcellulardecompositionmethodtoplanthecoveragepathofUAVsinthecomplexpolygonareasisproposed.AMinimalSumofWidths(MSW)decompositionalgorithmbasedonthegreedyrecursivemethodwhichrevolvesarounddecomposingtheconcaveareaintoconvexsubregionsisdeveloped.Itisprovedthatthealgorithmisapolynomialtimealgorithm.Thedefinitionsofadjacencyandentirelyadjacencyofpolygonsaregiven.Toavoidunnecessarybackandforthmotion,someentirelyadjacentsubregionsarecombined.Thejoint-pointsmatrixandtherelationshipbetweentheincomingjoint-pointandtheoutgoingjoint-pointareconstructed.Comparingdifferentweightsoftwojoint-points,asubregionconnectionalgorithmbasedonminimumtraversalofweightedundirectedgraphisproposedtoconnectthecoveragepathsofthesubregions.4.AnalgorithmofcooperativeCFPPformulti-UAVs,whichincludestwoparts:missionperformanceevaluationandmissionregionpartition,isproposed.CombiningAnalysisHierarchyProcess(AHP)andGreyCorrelationAnalysis(GRA)method,anAHP-GRAevaluationmethodtoevaluatethecoveragemissi