Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Full Information <s> The Fraunhofer Institute for Information and Data Processing operates different types of sensors on several mobile and stationary platforms for surveillance such as multiple micro UAVs, a helium captive balloon, networks of radio sensors, various network cameras, and mobile land and underwater robots. The surveillance system AMFIS presented in this paper is an integration platform that can be used to interconnect system components and algorithms. The specific tasks that can be performed using AMFIS include surveillance of scenes and paths, detection, localization and identification of people and vehicles as well as collection of evidence. The major advantages of this ground control station are its capability to display and fuse data from multiple sensor sources and the high flexibility of the software framework to build a variety of surveillance applications. <s> BIB001 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Full Information <s> Aerial images are useful tools for farmers who practise precision agriculture. The difficulty in taking geo-referenced high-resolution aerial images in a narrow time window considering weather restrictions and the high cost of commercial services are the main drawbacks of these techniques. In this paper, a useful tool to obtain aerial images by using low cost unmanned aerial vehicles (UAV) is presented. The proposed system allows farmers to easily define and execute an aerial image coverage mission by using geographic information system tools in order to obtain mosaics made of high-resolution images. The system computes a complete path for the UAV by taking into account the on-board camera features once the image requirements and area to be covered are defined. This work introduces a full four-step procedure: mission definition, automatic path planning, mission execution and mosaic generation. <s> BIB002 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Full Information <s> A complete procedure that can be used with any commercial quadrotor has been designed.A novel technique denoted as Harmony Search has been applied to path planning.A vineyard parcel has been used as a case study.An improved approach has been obtained in comparison with former techniques. The coverage path planning (CPP) problem belongs to a sub-field of motion planning where the goal is to compute a complete coverage trajectory from initial to final position, within the robot workspace subjected to a set of restrictions. This problem has a complexity NP-complete, and has no general solution. Moreover, there are very few studies addressing this problem applied to aerial vehicles. Previous studies point out that the variable of interest to be optimized is the number of turns. Thus, by minimizing the number of turns, it can be ensured that the mission time is likewise minimized. In this paper, an approach to optimize this cost variable is proposed. This approach uses a quite novel algorithm called Harmony Search (HS). HS is a meta-heuristic algorithm based on jazz musician's improvisation through a pleasant harmony. Finally, the results achieved with this technique are compared with the results obtained with the previous approach found in the literature. <s> BIB003 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Full Information <s> In this article, work in progress on a system for rapid aerial mapping is presented. We believe that a tool able to quickly generate an up-to-date high resolution aerial view, e.g. shortly after a natural disaster or a big incident occurs, can be a highly valuable asset to help first responders in the decision making. The presented work focuses on the path planning capabilities of the system, together with the area partitioning and workload distribution among a team of multi-rotor unmanned aircraft. Sensor footprint and range of the involved aircraft may differ. The presented approach is based on an approximate cellular decomposition of the area of interest. The results of this work will be integrated into an existing system which already provides a mobile ground control station able to supervise and control multiple sensor carriers. <s> BIB004 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Full Information <s> Area coverage is one of the compelling applications of UAVs. The existing methods for coverage path planning assume a uniformly interesting target area. However in many real world applications items of interest are not uniformly distributed but form clusters. Here it can be advantageous to only sample regions of interest while skipping uninteresting sections of the environment. In this paper, we present a coverage tree structure that can accommodate non-uniform coverage of regions in the target area. Three strategies are proposed to traverse the coverage tree. Experiments indicate that in some situations our method can cover the interesting regions with about half the travel time / cost of a naive regular ‘lawnmower’ coverage pattern. <s> BIB005 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Full Information <s> We propose a novel method for non-uniform terrain coverage using Unmanned aerial vehicles (UAVs). The existing methods for coverage path planning consider a uniformly interesting target area and hence all the regions are covered with high resolution. However in many real world applications items of interest are not uniformly distributed but form patches of locally high interest. Therefore, with sparse sampling of uninteresting sections of the environment and high resolution sampling of interesting patches, the trajectory of the robot can become shorter. In this paper, we present a novel coverage strategy based on Space-Filling Curves that can accomplish non-uniform coverage of regions in the target area. Simulations and real robot experiments indicate that with the new strategy, travel time / cost of the task can be (almost) always less than a regular ‘lawnmower’ coverage pattern. <s> BIB006 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Full Information <s> In this paper, an offline flight planner that computes an efficient coverage trajectory for a quad-rotors UAV is presented. The planner consists of three steps: mission definition, automatic path planning and trajectory generation. The proposed planner, as a useful tool, allows an UAV operator to easily define and generate a coverage trajectory for any specific task. The resultant trajectory can be dispatched to a quad-rotors with trajectory tracking controller for the missions that require a complete area coverage. <s> BIB007 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Full Information <s> In this paper, a quadrotor optimal coverage planning approach in damaged area is considered. The quadrotor is assumed to visit a set of reachable points following the shortest path while avoiding the no-fly zones. The problem is solved by using a two-scale proposed algorithm. In the first scale, an efficient tool for cluttered environments based on optimal Rapidly-exploring Random Trees (RRT) approach, called multi-RRT∗ Fixed Node (RRT∗FN), is developed to define the shortest paths from each point to their neighbors. Using the pair-wise costs between points provided by the first-scale algorithm, in the second scale, the overall shortest path is obtained by solving the Traveling Salesman Problem (TSP) using Genetic Algorithms (GA). Taking into consideration the limited onboard energy, a second alternative based on the well-known Vehicle Routing Problem (VRP) is used. This latter is solved using the savings heuristic approach. The effectiveness of this proposed two-scale algorithm is demonstrated through numerical simulations and promising results are obtained. <s> BIB008
Back-and-forth flight pattern is usually employed in applications like agriculture, but this type of motion generates inefficient trajectories considering areas of interest with an irregular shape. A coverage path planning approach for image mosaicing in precision agriculture with irregular-shaped fields is proposed by Valente et al. BIB002 . In this approach, named gradient-based, the area of interest is discretized into a regular grid using the approximate cellular decomposition, as shown in Figure 19 . Each cell represents a waypoint of the path and its size depends on the picture dimensions of the on-board camera. The grid configuration is attained through image demands and image sensor characteristics. The decomposed area is converted to a regular graph numerically labeled by the Wavefront algorithm, which is a flooding algorithm that marks the neighborhood adjacency of cells. A Deep-limited search (DLS)  is applied to discover a full path without revisiting previously explored nodes. With the DLS, the exploration length is restricted to the quantity of vertices and do not gets stuck in loops or revisits a node. A backtracking procedure is also employed to solve issues such as the choice among neighbors of equal values. The proposed method enables a simplistic and faster solution to achieve a near-optimal results in complex areas with certain constraints. Another approach exploring the Wavefront algorithm and the approximate cellular decomposition for coverage in agricultural areas is presented by Nam et al. BIB007 . The coverage path is obtained over an area of interest labeled according to the Wavefront, as shown in Figure 20a , and smoothed through a cubic interpolation algorithm, as illustrated in Figure 20b . Different from Valente et al. BIB002 , the authors present a novel optimization criterion for the mission execution time based on the path length and the number of turning maneuvers. An optimal CPP algorithm with a quadrotor UAV is presented by Bouzid et al. BIB008 . The area of interest is represented as a map containing Points Of Interests (POIs). The UAV should perform a minimum path connecting the POIs and avoiding obstacles with distinct formats to guarantee complete coverage in the area. The mission is planned in two steps. The algorithm computes the travelling cost to explore the neighborhood and then determines the sequence of points that should be visited in order to minimize the total distance. After visiting the POIs a single time, the vehicle should return to the initial position. In this way, the problem is treated as the Traveling Salesman Problem (TSP) and the overall shortest path can be computed using a Genetic Algorithm (GA). The authors consider the accumulative Euclidean distance among the points as the performance metric. Besides, they consider the energy consumption to be constant during the whole mission, measuring it in terms of time. In real-world applications, the quadrotor may need to charge or replace the battery a couple of times while performing a task considering its limited on-board energy. Thus, the authors explore a different possibility inspired on the Vehicle Routing Problem (VRP). This solution finds the minimum group of shortest trajectories in cases with only one or several initial positions. In this scenario, the aerial vehicle performs the designated task and keeps coming back to the base station every time it needs to recharge its battery. At the same time, the UAV also downloads the acquired information during each part of the mission. A coverage approach for precision agriculture involving a team of heterogeneous quadcopters is discussed by Barrientos et al.  , including two main phases: task subdivision and allocation, and coverage path planning. In the first phase, using a negotiation protocol, the subdivision of the area and the allocation of the resulting sub-regions are simultaneously accomplished in a distributed way. In this phase, the vehicles have to analyze the cost and the recompense of a task, i.e, cover a certain subregion. Considering its internal parameters, the vehicle evaluates the cost of a task execution, the initial cost to move from the current location to the search area, certain restrictions as NFZ, turning angles and embedded sensors, and the prize related with the mission accomplishment. The objective function sums several terms with different weights, including the task dimension and the distance between the starting point to the mission location. Furthermore, a penalty can be applied if one task superposes another or the exploration goes beyond the general area. In a second phase, the area is discretized into a regular grid using approximate cellular decomposition. Each vehicle uses a Wavefront algorithm to create a coverage path for its sub-region minimizing the flight time, the quantity of turning maneuvers and the amount of revisited cells. Also, the vehicles keep a constant altitude to guarantee a desired resolution according to the field of view of the on-board camera. Finally, the authors present a control system to improve the vehicle's altitude stabilization during high-speed maneuvers. Experiments were performed with three vehicles in a vineyard field, characterized by its irregular-shaped format and its changeable altitude profile. The sub-regions boundaries delimit a safe zone, in which the vehicles should not get in to avoid collisions, as illustrated in Figure 21 . Focusing also on precision agriculture, a meta-heuristic algorithm named Harmony Search (HS) is proposed by Valente et al. BIB003 to minimize the number of turning maneuvers in irregular areas. The proposed algorithm is based on jazz musician's improvisation and its main body is a Harmony Memory (HM). The HM consists of a matrix, where the lines are composed by vectors comprising possible solutions, while the columns represent decision variables. The cost-function result is placed in the last column. Following the approach proposed by Valente et al. BIB003 , the matrix initialization is performed randomly and an iteration known as improvisation begins when the first generation is complete. New vectors are created through exchanges between neighboring cells according to a certain probability. If a new harmony has an improvement in comparison to the worst solution, it replaces the old vector in the matrix. Otherwise, the matrix would remain unchanged. The authors compared the HS approach against the Wavefront algorithm employed by Barrientos et al.  using the same scenario with three subregions, as shown in Figure 22 . The HS achieves a smaller number of turns than the Wavefront, but a longer computational time. However, the authors do not consider computational time as a problem, once the planning is performed offline. More recently, Sadat et al. BIB005 and Sadat et al. BIB006 propose approaches for online non-uniform coverage path planning. In this context, the vehicle can change its altitude during the coverage according to the importance of each part of the area. The authors use a tree structure to deal with grids considering different resolutions. The closer the node is to the leaves, the higher is the resolution. Sadat et al. BIB005 introduced three methods to explore the tree: Breadth-First strategy, Depth-First, and Shortcut Heuristic, while Sadat et al. BIB006 proposed an Hilbert-based approach, as shown in Figure 23 , comparing it with the previous strategies and the lawnmower pattern. When visiting a zone of interest, the resolution is increased by traversing down the tree. In this way, the area that was being explored by a parent node, now is being fully covered by their child nodes at an increased resolution. On the other hand, if the zone is not interesting, the search goes up in the coverage tree and decreases the resolution. Therefore, a single vehicle moves around the area exploring zones at different altitudes to perform the mission. High-resolution aerial sensing with multiple heterogeneous UAVs for non-convex areas is discussed by Santamaria et al. BIB004 . The vehicles present different coverage range and image sensors, so the area of interest is discretized into a grid with cells of different sizes through the approximate cellular decomposition, as illustrated in Figure 24 . Initially, a roughly estimation determines the portion of the area to be explored by the UAVs considering their on-board sensor footprint. A flooding technique selects a starting position and extends the neighborhood area until it reaches the estimated amount of cells. Places located out of the area or within NFZ are invalid cells. After the first completed round, the unsigned cells are addressed to the nearest area and a re-balance is executed to uniformly distribute the cells. Following the approach presented by Santamaria et al. BIB004 , flight paths to cover each of the sub-areas are computed using an algorithm to find long-distance segments of free cells, called strides. The algorithm computes the strides for all unexplored adjacent cells of the actual position, selecting the longest line. The last cell of the selected line turns into the current cell, repeating the process. When there are no unvisited neighbor cells, the algorithm generates trajectories from the actual location to the closest unexplored cells, selects the minor path and adds the corresponding cells to the coverage plan. The shortest distance is also computed to return to the landing location. The proposed approach was integrated with the AMFIS BIB001 , which consists of ground control station for real-time vehicle controlling and monitoring.