Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> No Decomposition <s> We present a path planning algorithm for time-critical cooperative surveillance using a set of unmanned aerial platforms. The unique constraints imposed by maneuver limits and body-fixed cameras make the problem quite challenging. An Integer Programming (IP) based strategy for successfully operating within these constraints is developed. The main contribution of the paper is the incorporation of highly constrained motion and sensor capabilities of the vehicles in the mathematical programming formalism. Simulation and experimental results are presented to demonstrate the efficacy of the proposed approach. <s> BIB001 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> No Decomposition <s> This thesis considers path planning for a low-cost multicopter used in the search part of a search and rescue mission. Search patterns or trajectories are considered and evaluated through simulations in MATLAB. How to place the onboard camera in order to cover as much area as possible and which altitude that gives the most area coverage without making the subjects too small to detect is discussed. The proposed search patterns are implemented in the existing software structure used in this project. The implementation is tested using a ArduPilot software in the loop simulator, and by flight tests using a hexacopter. <s> BIB002 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> No Decomposition <s> Unmanned Aerial Vehicles (UAVs) are starting to be used for photogrammetric sensing of large areas in several application domains, such as agriculture, rescuing, and surveillance. In this context, the problem of finding a path that covers the entire area of interest is known as Coverage Path Planning (CPP). Although this problem has been addressed by several authors from a geometrical point of view, other issues such as energy, speed, acceleration, and image resolution are not often taken into account. To fill this gap, this paper first proposes an energy model derived from real measurements, and then uses this model to implement a coverage path planning algorithm for reducing energy consumption, as well as guaranteeing a desired image resolution. In addition, two safety mechanisms are presented: the first, executed off-line, checks whether the energy stored in the battery is sufficient to perform the planned path; the second, performed online, triggers a safe return-to-launch (RTL) operation when the actual available energy is equal to the energy required by the UAV to go back to the starting point. <s> BIB003 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> No Decomposition <s> An energy-optimal coverage path planning algorithm is proposed for environment survey. First, 3D terrains are modelled by tensor product Bezier surfaces for a mesh representation. Then, a power estimator is derived to calculate the consumed energy for a piecewise spatial path. Based on the digital surface model, an energy consumption map is constructed for the whole area by means of a weighted directed graph. Finally, an energy-optimal path can be achieved through traversing the map by a genetic algorithm. Numerical experiments demonstrate the effectiveness and efficiency of the proposed algorithm. <s> BIB004 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> No Decomposition <s> Unmanned Aerial Vehicles (UAVs) represent an appealing technology that open new possibilities in civil use. Despite the promising convenience, UAVs face several major setbacks which include limited energy supply and short operation time. With focus on a specific application, localization of mobile devices using wireless communication, this work analyses those aspects of the localization process which cause energy and time sinks. Furthermore, by using the concept of Bezier curves, energy-aware trajectories are developed by generating path smoothing algorithms called Exterior Modification of Trajectory Algorithm (E-MoTA) and Interior Modification of Trajectory Algorithm (I-MoTA) which are applied to the static trajectories. The observation of the impact of these algorithms on the energy and time expenditures at various resolution and on the level of localization accuracy is analyzed. Several state-of-the-art trajectories are compared with E-MoTA and I-MoTA using analytical studies. The results show that applying MoTA aids in reducing energy and time expenditures while maintaining the level of the localization accuracy close to the original one. <s> BIB005 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> No Decomposition <s> Most unmanned aerial vehicles nowadays engage in coverage missions using simple patterns, such as back-and-forth and spiral. However, there is no general agreement about which one is more appropriate. This letter proposes an E-Spiral algorithm for accurate photogrammetry that considers the camera sensor and the flight altitude to apply the overlapping necessary to guarantee the mission success. The algorithm uses an energy model to set different optimal speeds for straight segments of the path, reducing the energy consumption. We also propose an improvement for the energy model to predict the overall energy of the paths. We compare E-Spiral and E-BF algorithms in simulations over more than 3500 polygonal areas with different characteristics, such as vertices, irregularity, and size. Results showed that E-Spiral outperforms E-BF in all the cases, providing an effective energy saving even in the worst scenario with a percentage improvement of <inline-formula><tex-math notation="LaTeX">$10.37\%$</tex-math> </inline-formula> up to the best case with <inline-formula><tex-math notation="LaTeX">$\text{16.1}\%$</tex-math> </inline-formula> of improvement. Real flights performed with a quadrotor state the effectiveness of the E-Spiral over E-BF in two areas, presenting an improvement of <inline-formula><tex-math notation="LaTeX">$\text{9}\%$</tex-math> </inline-formula> in the time and <inline-formula><tex-math notation="LaTeX">$\text{7.7}\%$</tex-math></inline-formula> in the energy. The improved energy model increases the time and the energy estimation precision of <inline-formula> <tex-math notation="LaTeX">$\text{13.24}\%$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX"> $\text{13.41}\%$</tex-math></inline-formula>, respectively. <s> BIB006
Coverage missions performed over regular-shaped and non-complex areas of interest with a single UAV usually do not require any type of decomposition. Simple geometric patterns are sufficient to explore such areas. The most common patterns are the back-and-forth (BF) and the spiral (SP). The former one is adopted by the Mission Planner, the most popular flight-control software  , to enable the area coverage using a standard pattern. In this pattern, the motions consist of straight lines crossed in both directions with closed-angle maneuvers at the end of each round. The latter one usually performs motions passing by the external vertices of the area and reducing the radius towards the central point. Some approaches explore only rectangular areas, according to Andersen BIB002 , where the author compares different types of flight patterns. In this work, the back-and-forth pattern is classified into parallel and creeping line, as illustrated in Figure 5a ,b, and it is preferable when the search area is large and there is no information about the likely target meeting point. The square flight pattern consists of straight lines and 90 • turning maneuvers to the right side. The pattern starts at the central point and extends towards the borders, following a pattern similar to an ellipse shape, and it is normally employed when a uniform area coverage is desired, as shown in Figure 5c . The sector search pattern, presented in Figure 5d , consists of a straight line with 120 • turning maneuvers to the right when the vehicle reaches the border of the area. After three sectors, the path returns to the initial point at the center of the area. Then, the same pattern is repeated with 30 • of displacement. The barrier patrol consists of the definition of 12 points spatially distributed in the search area, as illustrated in Figure 5e . The vehicle initiates its trajectory in the starting point and using a circular movement achieves the next point. From this point, instead of continuing the circular trajectory, it follows to the point closer to the right-corner and achieves the center point. An analysis of the effect of wind disturbances in the mission execution time of BF coverage paths performed by a fixed-wing UAV is presented by Coombes et al.  . Using a circular area of interest covered with BF motions, the authors explore different sweep directions varying from 0 to 360 degrees in increments of 10 degrees with a predefined wind direction with six different speeds. According to the simulated experiments, the coverage direction must be perpendicular to the wind direction to minimize flight time. However, the turning maneuvers are directly affected by the choice of the perpendicular direction (clockwise or counterclockwise). The authors believe that in more complex scenarios decomposed into cells, the transition distance between those cells has more impact in the flight time than the wind direction. Recent studies present energy-aware solutions exploring the dynamics and the behavior of the UAVs to save energy. Considering regular-shaped areas as rectangles and convex polygons, Di Franco and Buttazzo BIB003 presented an energy-aware back-and-forth CPP approach (E-BF) for photogrammetry with energy and resolution constraints imposed by the mission. In this approach, an algorithm determines the best configuration of back-and-forth motions at maximum altitude according to resolution constraints while minimizing the number of turns. The authors claim that it is possible to minimize the amount of energy flying at an optimal speed. This optimal speed varies according to the travelled distance. The algorithm finds the first vertex of the longest edge and computes the scan direction parallel to it. Then, it calculates the number of stripes and waypoints, the distance between the stripes and consecutive waypoints, and the overlapping rates. Finally, a straight line connects the farthest vertex to the initial vertex. An algorithm improvement is also presented to avoid previously explored covered zones, as shown in Figure 6a . Turning the number of stripes in even and increasing the overlapping rate, the returning path can also be used as a scanning path, as illustrated in Figure 6b . The authors also proposed offline and online failsafe measures. The former one is checked offline in order to verify if the battery has enough energy to execute the mission. The latter one is checked online during the flight and constantly analyzes if the remaining energy is capable of bringing back the aerial vehicle to the starting point. An energy-aware spiral CPP algorithm (E-Spiral) is proposed by Cabreira et al. BIB006 for regular-shaped areas of interest. The algorithm consists of building a coverage path passing by each vertex of the area. Once the first coverage layer is completed, the algorithm should reduce the radius in order to move the vehicle towards the central point, as illustrated in Figure 7 . The algorithm performs turning maneuvers with wider angles and does not need to reduce the speed to zero on every turn, which decreases the acceleration and deceleration periods. This behavior keeps the optimal speed adopted in straight segments of the path for longer periods, providing an even more effective energy saving than the one proposed by Di Franco and Buttazzo BIB003 . The E-BF BIB003 and the E-Spiral BIB006 adopt the energy model proposed by Di Franco and Buttazzo  derived from real measurements. The approaches are compared in simulations performed in 3750 different convex polygonal areas varying features, such as the angular points, the nonuniformity, and the size. Using a quadrotor, the authors also performed real experiments using both patterns in a rectangular and a polygonal area to analyze the energy spent during the missions. The E-Spiral overcomes the E-BF, both simulations and real flights, and can be considered the most efficient CPP approach for convex polygonal areas considering energy spent during missions. A triple-stage CPP algorithm for UAVs is presented in Li et al. BIB004 , where the authors explore important features not addressed by Di Franco and Buttazzo BIB003 , such as payload and power variation. The first step is to build a 3D terrain model using control points in order to obtain an analytical model. Next, the stable power consumption is calculated considering take-off weight, flight speed, and air friction. The authors consider that the vehicle moves with constant speed in a steady state, deriving the optimal speed aimed at minimizing energy. Furthermore, an energy consumption map is built to show the amount of energy spent on every part of the path. Finally, an optimization is performed with a Genetic Algorithm in order to discover minimum-cost paths comprising all vertices. Energy-aware algorithms for smoothing trajectories are presented by Artemenko et al. BIB005 . The authors observed that a UAV spends a lot of time and energy making turns, once the vehicle has to decelerate, rotate and accelerate every time it performs these maneuvers. Thus, using the concept of Bézier curves, the algorithms modify conventional trajectories such as SCAN (back-and-forth), HILBERT, and LMAT, shown in Figure 8 , by smoothing maneuvers along a given path. A more effective turning maneuver can be performed smoothing the movement with minimum deceleration. The authors compare the modified trajectories with the conventional ones and conclude that the new trajectories are able to reduce the amount of energy and time spent, keeping the level of the localization accuracy (LoLA). Forsmo et al.  employs the Mixed Integer Linear Programming (MILP) for coverage missions in rectangular areas involving UAVs. The waypoints distribution over a certain area considers the UAV on-board camera in order to obtain full coverage. The authors simplify the problem considering only rectangular obstacles and placing the aerial vehicles in distinct zones of the area, not using any type of area decomposition nor properly dealing with the collision avoidance issue among the vehicles. Simulation experiments were performed to evaluate the proposed solution considering different cases with constraints, such as waypoint visitation order and camera range reduction. Coverage missions may require a team of aerial vehicles working in a cooperative way in order to improve the task performance given the complexity and size of different scenarios. A cooperative coverage algorithm with critical time for rectangular areas using multiple fixed-wing heterogeneous UAVs is presented by Ahmadzadeh et al. BIB001 . The vehicles fly at distinct and fixed altitudes, such as 80 m, 90 m, 100 m, and 110 m, and with constant velocity. Furthermore, the vehicles present maneuverability restrictions and fixed cameras either in the front or in the left wing. An approach based on Integer Linear Programming is used to generate a solution considering these restrictions. The paths of the UAVs with the frontal camera are basically circular, while the paths of the UAVs with the left side camera are composed of straight lines and left turns. When this vehicle turns right, the camera focuses on the horizon and does not capture any image of the coverage area or image resolution drastically decreases. The authors compare the proposed approach using the four fixed-wings vehicles against simple methods such as back-and-forth. Due to motion constraints and field of view, simple patterns such as back-and-forth presented a coverage of about 80% of the area of interest, while the proposed approach obtained 100% of coverage. The proposal was tested and evaluated in simulations performed in MATLAB and in real flights.