In Partial Fulfillment of the Requirements for the Degree of
Doctor of Philosophy
in
Control Science and Engineering
Supervisor: Professor Wang Xin-Min
School of Automation Northwestern Polytechnical University June 2010
III
西北工业大学博士学位论文
ABSTRACT
the span. Based on the basic algorithm of vertex-edge pairs and the distance comparison, an optimal algorithm to calculate the width is proposed, whose time complexity is O(n). 3. An enhanced exact cellular decomposition method to plan the coverage path of UAVs in the complex polygon areas is proposed. A Minimal Sum of Widths (MSW) decomposition algorithm based on the greedy recursive method which revolves around decomposing the concave area into convex subregions is developed. It is proved that the algorithm is a polynomial time algorithm. The definitions of adjacency and entirely adjacency of polygons are given. To avoid unnecessary back and forth motion, some entirely adjacent subregions are combined. The joint-points matrix and the relationship between the incoming joint-point and the outgoing joint-point are constructed. Comparing different weights of two joint-points, a subregion connection algorithm based on minimum traversal of weighted undirected graph is proposed to connect the coverage paths of the subregions. 4. An algorithm of cooperative CFPP for multi-UAVs, which includes two parts: mission performance evaluation and mission region partition, is proposed. Combining Analysis Hierarchy Process (AHP) and Grey Correlation Analysis (GRA) method, an AHP-GRA evaluation method to evaluate the coverage mission performances of UAVs is developed. The consistency checking problem is transformed to the general statistical hypothesis testing problem which can improve the disadvantage of the traditional consistency proportional checking method. A partition algorithm based on the performances of UAVs and the widths of subregions is proposed to get the global optimization. Keywords: Unmanned Aerial Vehicles (UAVs); Coverage Flight Path Planning (CFPP); camera footprint; Minimal Sum of Widths (MSW); Joint-points matrix; AHP(Analysis Hierarchy Process)-GRA (Grey Correlation Analysis) evaluation algorithm
西 北 工 业 大 学
博 士 学 位 论 文
（学位研究生）
题目：
无人机区域覆盖 航迹规划技术研究
作
者：
陈海
学科专业： 控制科学与工程 指导教师： 王新民
2010 年 6 月
Research on Area Coverage Flight Path Planning for UAVs
By Chen Hai
西北工业大学博士学位论文
摘要
摘 要
无人机区域覆盖航迹规划就是在满足某种（某些）性能指标最优的前提下， 避开障碍物和威胁源，规划出一条能够遍历待覆盖区域的最优飞行路线。该技术 是无人机完成侦察、监视及搜索任务的关键，对于提高无人机的任务执行能力具 有重要意义。本文对无人机区域覆盖航迹规划技术进行了深入的研究，提出了一 些新颖的思路和算法。 本文首先从理论上证明了转弯机动对于无人机覆盖航迹规划来说是低效的， 由此确定了本文的优化准则为转弯次数最少；其次把基本区域的覆盖航迹规划问 题转化为求凸多边形的宽度问题，只要无人机沿宽度的垂直方向飞行，即可获得 最少的转弯次数；接下来对精确单元分解法进行了改进，用于复杂区域的覆盖航 迹规划；最后把无人机的任务性能评价和任务区域划分相结合，用于多无人机的 协同覆盖航迹规划。 本文的主要创新点如下： 1. 针对无人机覆盖航迹规划过程与机器人的不同，对无人机不同姿态角下的 探测区域及转弯机动的运动学特性进行了分析。给出了探测区域的长度和宽度随 俯仰角和滚转角变化的数学关系，以及偏航机动时，无人机坐标与探测区域坐标 之间的转换公式；推导出了给定巡航速度下燃油消耗量最低的法向过载计算公式； 分析了U型转弯和直角转弯过程中探测区域移动路线与无人机飞行路线之间的关 系， 分三种情况给出了U型转弯过程中转弯路程、 转弯时间和距离差值的计算公式； 从理论上证明了U型转弯机动比直角转弯机动的效率高。 2. 提出了一种基本区域的无人机覆盖航迹规划算法。给出了凸多边形跨度和 宽度的定义，把基本区域的覆盖航迹规划问题转化为求凸多边形的宽度问题；证 明了凸多边形区域的宽度只可能出现于“点边式”跨度之中，缩小了宽度的计算 范围；提出了一种距离比较算法，降低了凸多边形跨度的计算量；在“点边式” 基本算法和距离比较算法的基础上，提出了一种优化宽度算法，使算法的时间复 杂性降低为O(n)。 3. 提出了一种改进的精确单元分解算法，用于无人机在复杂区域中的覆盖航 迹规划。提出了一种基于贪心递归的最小宽度和（Minimal Sum of Width，MSW）
AHP-GRA 关键词：无人机；覆盖航迹规划；探测区域；最小宽度和；衔接矩阵； 关键词 评价法
II
西北工业大学博士学位论文
ABSTRACT
ABSTRACT
The area Coverage Flight Path Planning (CFPP) of Unmanned Aerial Vehicles (UAVs) is to plan a path to cover the all points of given area, which satisfies some optimal performance indices and avoids the obstacles and threat sources. This technology is the key to complete the mission of reconnaissance, surveillance and search and improve the ability of mission execution for UAVs. This paper studies the technology of CFPP for UAVs and proposes some novel ideas and algorithms. Firstly, the turning maneuver of coverage for UAVs is proved to be less efficient compared with the flat flying maneuver, so the least number of turns is chosen as the optimization criteria. Secondly, the problem of CFPP in basic areas is transformed to the width calculation of the convex polygons. If a UAV flies along the vertical direction of width, the coverage path can get the least number of turns. Thirdly, an enhanced exact cellular decomposition method to plan the coverage path of UAVs in complex polygon areas is proposed. Finally, the mission performance evaluation and mission region partition are combined to plan the cooperative coverage path of multi-UAVs. The main innovations of this paper are as follows: 1. Comparing with the coverage differences between the robots and the UAVs, the camera footprint with different attitude angles and kinematics properties in turning maneuver for UAVs are analyzed. The mathematical formulas of the length and the width of camera footprint in pitch and roll maneuvers and the coordinate transformation between the UAV centroid and the footprint center in yaw maneuver are given. A formula to obtain the normal acceleration for minimum fuel consumption under given flying velocity is presented. The relationships between the camera footprint paths and the flying paths in U-turn and right-angled-turn are analyzed. The distance, duration and distance difference value of turn are calculated in three different situations. It is proved that the U-turn is more efficient than the right-angled-turn in theory. 2. An algorithm to plan the coverage path for UAVs in the basic area is proposed. The definitions of span and width of convex polygons are given, and the problem of CFPP in convex polygon areas is transformed to the width calculation of the convex polygon. It is proved that the width of a convex polygon only be found in the span of vertex-edge pairs. In this way, the range of calculation narrows down. Then an algorithm using distance comparison is investigated to reduce the calculated amount of