Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Single Strategies <s> This article settles the following two longstanding open problems:?What is the worst case approximation ratio between the greedy triangulation and the minimum weight triangulation??Is there a polynomial time algorithm that always produces a triangulation whose length is within a constant factor from the minimum?The answer to the first question is that the known lower bound is tight. The second question is answered in the affirmative by using a slight modification of anO(nlogn) algorithm for the greedy triangulation. We also derive some other interesting results. For example, we show that a constant-factor approximation of the minimum weight convex partition can be obtained within the same time bounds. <s> BIB001 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Single Strategies <s> Coverage path planning is the determination of a path that a robot must take in order to pass over each point in an environment. Applica­ tions include vacuuming, floor scrubbing, and inspection. We developed the boustrophedon cellular decomposition, which is an exact cel­ lular decomposition approach, for the purposes of coverage. Each cell in the boustrophedon is covered with simple back and forth motions. Once each cell is covered, then the entire envi­ ronment is covered. Therefore, coverage is re­ duced to finding an exhaustive path through a graph which represents the adjacency relation­ ships of the cells in the boustrophedon decom­ position. This approach is provably complete and Experiments on a mobile robot validate this approach. <s> BIB002 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Single Strategies <s> Robotic coverage is the problem of moving a sensor or actuator over all points in given region. Ultimately, we want a coverage path that minimizes some cost such as time. We take the approach of decomposing the coverage region into subregions, selecting a sequence of those subregions, and then generating a path that covers each subregion in turn. We focus on generating decompositions based upon the planar line sweep. After a general overview of the coverage problem, we describe how our assumptions lead to the optimality criterion of minimizing the sum of subregion altitudes (which are measured relative to the sweep direction assigned to that subregion). For a line-sweep decomposition, the sweep direction is the same for all subregions. We describe how to find the optimal sweep direction for convex polygonal worlds. We then introduce the minimal sum of altitudes (MSA) decomposition in which we may assign a different sweep direction to each subregion. This decomposition is better for generating an optimal coverage path. We describe a method based on multiple line sweeps and dynamic programming to generate the MSA decomposition. <s> BIB003 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Single Strategies <s> This paper proposes an improved method of exact cellular decomposition to plan the coverage path in polygon area. Firstly, the problem of Coverage Path Planning (CPP) in the convex polygon area is transformed to the width calculation of the convex polygon, and the strategy of flying along the vertical direction of width is presented to reach the least number of turns. Secondly, a convex decomposition algorithm of minimum width sum based on the greedy recursive method is presented to decompose the concave area into some convex subregions. Finally, a subregion connection algorithm based on minimum traversal of undirected graph is proposed to connect the coverage paths of the subregions. The simulation shows that the proposed method is feasible and effective. <s> BIB004 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Single Strategies <s> Abstract In this paper, an enhanced exact cellular decomposition method to plan the coverage path of UAVs in a polygon area is proposed. To be more specific, the contributions of the paper are: firstly, the turning motion of UAVs is shown to be less efficient from the viewpoints of route length, duration and energy. Secondly, the problem of coverage Path Planning (CPP) in a convex polygon area is transformed to width calculation of the convex polygon, and a novel algorithm to calculate the widths of convex polygons with time complexity of O ( n ) is developed. The path of the least number of turns for an UAV based on the widths of convex polygons is devised. Thirdly, a convex decomposition algorithm for minimum width sum 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. To avoid unnecessary back and forth motion, some entirely adjacent subregions are combined. Finally, 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. Simulation results show that the proposed method is feasible and effective. <s> BIB005 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Single Strategies <s> We present the adaptation of an optimal terrain coverage algorithm for the aerial robotics domain. The general strategy involves computing a trajectory through a known environment with obstacles that ensures complete coverage of the terrain while minimizing path repetition. We introduce a system that applies and extends this generic algorithm to achieve automated terrain coverage using an aerial vehicle. Extensive experimental results in simulation validate the presented system, along with data from over 100 kilometers of successful coverage flights using a fixed-wing aircraft. <s> BIB006 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Single Strategies <s> Focus is on the coverage path planning problem with UAV for 3D terrain reconstruction.The aim is to obtain a path that reduces the battery consumption, minimizing the turns.Our algorithm deals with both convex and non-convex regionsThe algorithm can perform the coverage when complex regions are considered.Can achieve better solutions than a previous result (using less turns). Three-dimensional terrain reconstruction from 2D aerial images is a problem of utmost importance due its wide level of applications. It is relevant in the context of intelligent systems for disaster managements (for example to analyze a flooded area), soil analysis, earthquake crisis, civil engineering, urban planning, surveillance and defense research.It is a two level problem, being the former the acquisition of the aerial images and the later, the 3D reconstruction. We focus here in the first problem, known as coverage path planning, and we consider the case where the camera is mounted on an unmanned aerial vehicle (UAV).In contrast with the case when ground vehicles are used, coverage path planning for a UAV is a lesser studied problem. As the areas to cover become complex, there is a clear need for algorithms that will provide good enough solutions in affordable times, while taking into account certain specificities of the problem at hand. Our algorithm can deal with both convex and non-convex areas and their main aim is to obtain a path that reduces the battery consumption, through minimizing the number of turns.We comment on line sweep calculation and propose improvements for the path generation and the polygon decomposition problems such as coverage alternatives and the interrupted path concept. Illustrative examples show the potential of our algorithm in two senses: ability to perform the coverage when complex regions are considered, and achievement of better solution than a published result (in terms of the number of turns used). <s> BIB007 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Single Strategies <s> In this paper, a new method for planning coverage paths for fixed-wing Unmanned Aerial Vehicle (UAV) aerial surveys is proposed. Instead of the more generic coverage path planning techniques presented in previous literature, this method specifically concentrates on decreasing flight time of fixed-wing aircraft surveys. This is achieved threefold: by the addition of wind to the survey flight time model, accounting for the fact fixed-wing aircraft are not constrained to flight within the polygon of the region of interest, and an intelligent method for decomposing the region into convex polygons conducive to quick flight times. It is shown that wind can make a huge difference to survey time, and that flying perpendicular can confer a flight time advantage. Small UAVs, which have very slow airspeeds, can very easily be flying in wind, which is 50% of their airspeed. This is why the technique is shown to be so effective, due to the fact that ignoring wind for small, slow, fixed-wing aircraft is a considerable oversight. Comparing this method to previous techniques using a Monte Carlo simulation on randomised polygons shows a significant reduction in flight time. <s> BIB008
An exact cellular decomposition approach considering concave polygonal areas is explored by Jiao et al. BIB004 , Li et al. BIB005 . Initially, the workspace is decompounded in non-concave sub-areas through a minimum width sum approach exploring a greedy recursive method previously proposed by Levcopoulos and Krznaric BIB001 . Then, back-and-forth motions perpendicular to the sweeping direction, which is the minimum distance between an edge and a vertex, are performed in order to minimize the turning maneuvers BIB003 . Two sub-regions entirely adjacent and with the same sweep direction, obtained from the convex decomposition (from Figure 9a ), are combined into the sub-region P4 to avoid unnecessary back-and-forth moves, as revealed by Figure 9b . It is also possible to change the motion direction from one sub-region to another in order to obtain a coverage improvement, as shown in Figure 9c . Finally, the optimal sequence of sub-regions is defined to join the final trajectory, as illustrated in Figure 9d . Another coverage approach exploring the exact cellular decomposition for convex and concave areas is presented by Torres et al. BIB007 . The authors aim to capture pictures using aerial vehicles in order to achieve a 3D reconstruction. Convex polygons can be swept by BF motions according to the optimal direction. However, in more complex areas as concave polygons, it is needed to check if the mission can be performed in the same way with no gaps during the stripes, i.e., none of the stripes cross a part outside of the polygon. This particular case is illustrated in Figure 10a . When the path is interrupted, as shown in Figure 10b , an exact decomposition of the polygon is used to simplify the area creating sub-regions. Once the optimal sweeping direction is defined for each sub-region, four different back-and-forth alternatives are explored considering two criteria related to the direction and the orientation. The former one explores if the coverage is going to follow the optimal motion direction or opposite way. The latter one considers the orientation of the first turning maneuvers, clockwise (left turn) or counterclockwise (right turn). The alternatives influence the transition distances, i.e., the distance between the last point of a given sub-region A and the first point of a given sub-region B. Permuting the sub-regions coverage order with the alternatives of each one, it is possible to minimize the transition distances and, consequently, minimize the path length. When the coverage is complete, the approach directly connects the final point with the first one using a straight line. Exploring all permutations may consume an elevated computational time depending on the number of sub-regions. Thus, the authors use only the adjacent sub-regions for the transitions, reducing the number of permutations. The proposed approach was evaluated in two scenarios. In the first scenario, a concave area is decomposed in five sub-regions pondering only four adjacencies. The authors drastically diminish the amount of permutations and the computational time spent generating a solution with an insignificant increment in the total distance. In the second scenario, the approach is compared to the one proposed by Li et al. BIB005 using the same area, as shown in Figure 11 . The proposed approach decomposes the area into only four sub-regions, computing only 80 turning maneuvers against 87 of the original work. A coverage path planning technique for fixed-wing UAVs exploring wind to decrease the flight time is presented by Coombes et al. BIB008 . The authors incorporated the wind in the model to compute the coverage paths in a previous work  and extended their work by proposing a decomposition method to split the complex region into convex polygons. The area of interest is decomposed through trapezoidal decomposition exploring several rotations of the polygon. Cell recombination is employed using Dynamic Programming to merge cells into convex polygons. It is important to notice that this decomposition method also considers optional cells external to the region in order to find different decomposition with lower flight times. The UAVs explore the area using back-and-forth motions perpendicular to the wind direction and are allowed to fly outside the area of interest. The initial and final waypoint of each straight line intersects the contour of the area and the UAV performs 180 degrees turning maneuvers to move from the final point of one line to the first point of the next one. This maneuver in the presence of wind is called a trochoidal turn. It consists of the shortest curve connecting the waypoints considering the fixed-wing restricted turning rate. The transition distance between adjacent cells is also considered during the path computation. The authors present a cost function called Flight Time in Wind (FTIW) to compute the flight time needed by the aircraft to cover an area. The total time is the sum of the time to fly the straight lines, to perform the trochoidal turns, and to make the transitions between the cells. The proposed method (FTIW) is compared with previous techniques that aim to minimize the number of turns (NT) BIB005 and the sum of the altitudes (MSA) BIB003 . Using a real field and several random polygons generated by a Monte Carlo simulation, the authors claim that their FTIW approach overcomes both previous approaches considering the flight time needed to execute coverage. Xu et al. BIB006 and Xu et al.  present an optimal coverage algorithm for fixed-wing UAVs able to avoid flights in obstacle-regions with arbitrary shapes and previously explored regions. The area of interest is decomposed into a simple set of cells using Boustrophedon Cellular Decomposition (BCD), originally proposed by Choset and Pignon BIB002 , in an offline phase through a bitmap representation. The BCD is an exact cellular decomposition able to work with non-polygonal obstacles, which presents more efficient coverage paths than the trapezoidal decomposition. From the decomposition, an adjacency graph can be built with the vertices representing the cells and the edges connecting the adjacent cells, as illustrated in Figure 12 . Cells are explored using back-and-forth motions in an online phase. The order between the cells follows a Eulerian circuit with start and end at the same vertex. Depending on the next cell location, it is necessary to go through sub-regions previously explored in the scenario. Thus, a more efficient technique is proposed to eliminate the disjunctions adding an extra sweep line. This line guarantees the continuity of the path when it reaches the border of the cells and prevents repeated explorations. The original and the modified approach were applied in simulations and real flights. Both were evaluated regarding the total path length and the time to perform the coverage. The method proposed by the authors was 10% more efficient in both criteria. A convex decomposition method to split complex shapes into smaller shapes and transform concave shapes with sharp edges into convex shapes is presented by Öst  . The author explores the back-and-forth and the spiral motion, as illustrated in Figure 13 , combining them with the proposed area decomposition technique. The authors claim that back-and-forth pattern with no area decomposition presents reliable outcomes with respect to different combinations. This confidence is because all maneuvers have 90 • turns, which allow us to predict the pattern after four moves. Despite generating slightly longer paths, this pattern is capable of handling complex shapes without losing coverage. However, the algorithm consumes a considerable time testing all different rotations in the polygon between 0 • and 180 • to find the optimal motion direction. Shortest paths are generated with spiral pattern in rounded shapes with large inner angles, according to Öst  . However, sometimes the pattern does not conclude the coverage in complex areas. Mixed variations comprising patterns and decomposition are able to generate a path with minor distance, but these combinations do not always deal with all the instances in a good way. It has proved to be really effective only when the area has too many protrusions in different directions, such as a star shape. In some cases, the decomposition may contain more vertices with a large number of small inner angles, generating self-intersections during the junction of the areas.