Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Performance Metrics <s> This paper focuses on the problem of cooperatively searching a given area to detect objects of interest, using a team of heterogenous unmanned air vehicles (UAVs). The paper presents algorithms to divide the whole area taking into account UAV’s relative capabilities and initial locations. Resulting areas are assigned among the UAVs, who could cover them using a zigzag pattern. Each UAV has to compute the sweep direction which minimizes the number of turns needed along a zigzag pattern. Algorithms are developed considering their computational complexity in order to allow near-real time operation. Results demonstrating the feasibility of the cooperative search in a scenario of the COMETS multi-UAV project are presented. <s> BIB001 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Performance Metrics <s> This paper surveys recent results in coverage path planning, a new path planning approach that determines a path for a robot to pass over all points in its free space. Unlike conventional point-to-point path planning, coverage path planning enables applications such as robotic de-mining, snow removal, lawn mowing, car-body painting, machine milling, etc. This paper will focus on coverage path planning algorithms for mobile robots constrained to operate in the plane. These algorithms can be classified as either heuristic or complete. It is our conjecture that most complete algorithms use an exact cellular decomposition, either explicitly or implicitly, to achieve coverage. Therefore, this paper organizes the coverage algorithms into four categories: heuristic, approximate, partial-approximate and exact cellular decompositions. The final section describes some provably complete multi-robot coverage algorithms. <s> BIB002 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Performance Metrics <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> BIB003 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Performance Metrics <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> BIB004 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Performance Metrics <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> Performance Metrics <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> BIB006 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Performance Metrics <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> Performance Metrics <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> BIB008 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Performance Metrics <s> Multi-Agent Patrolling Problems consist in moving agents throughout a graph in order to optimize a collective performance metric. Some strategies from the literature tackle this problem by dispatching decentralized autonomous agents that coordinate themselves merely by sensing and writing information in the nodes. In this work, they are called k-range local strategies, were k indicates the range, in number of edges, of the agents’ sensing capabilities. The 1-range strategies (where agents can sense up to its neighbor nodes) are certainly the most common case in the literature. And only few 0-range strategies (where agents can only sense its current node) were found, although this type of strategy has the advantage of requiring simpler hardware, when applied in the design of real robots. In this work, we propose two higher-level procedures to reduce the perception range of 1-range strategies to 0: the Zr Method and the EZr Method. Applying both methods in 1-range strategies found in the literature, we created twenty new 0-range strategies, which were evaluated in a simulation experiment described and analyzed here. We also developed a prototype of a low-cost patrolling robot that is able to run the 0-range strategies proposed in this work. <s> BIB009
Coverage algorithms must consider several issues to guarantee the success of a coverage mission, such as the complexity of the area of interest, the presence or not of no-fly zones and the possibility to employ cellular decomposition techniques. Furthermore, the coverage algorithms should generate coverage paths according to the application requirements. For instance, the main goal of a photogrammetric sensing application is to create an orthomosaic composed by a set of overlapping aerial photographs. In this case, an application requirement is to guarantee the necessary quantity of frontal and side superposition in the pictures. Another necessary requirement for this type of application is the resolution, which can be calculated as ground sampling distance (GSD)  . The GSD is the length on the ground corresponding to the side of one pixel in the image, or the distance between pixel centers measured on the ground. The lower the flight altitude of the UAV, smaller the GSD and the better the image quality. For this reason, the performance metrics used to evaluate the candidate solutions for a coverage path must fulfill the application requirements. In addition, it should take into account whether the coverage is simple or continuous. In a simple coverage, the area of interest is covered only once, while in a continuous coverage the scenario is swept several times. In both cases, the coverage can be performed by a single or multiple vehicles. Specific metrics for continuous coverage include the number of detected objects/events, interval and frequency of visits in each environment cell, the quadratic mean of intervals (QMI) BIB009 , and the standard deviation of frequencies (SDF) BIB009 . Considering the context of a simple coverage, the most common performance metrics found in the literature are: the total travelled distance or the path length  BIB003 , the time-to-complete a mission BIB005 BIB004 , the area coverage maximization BIB006 , and the number of turning maneuvers BIB001 BIB007 . Minimizing the coverage path length lies in a trade-off with the area coverage maximization. In a workspace split by cellular decomposition, the path length should not be only minimized inside each cell, but also in the intermediate routes between adjacent cells, i.e., the path connecting the end of one cell and the start of the next cell. Keeping the UAV inside the area of interest, avoiding flying over locations previously visited and flying at higher altitudes also minimize the coverage distance. The use of multiple robots reduces the coverage flight time. For one robot, however, one can consider the area covered per unit path length travelled. Minimizing this quantity improves time-to-completion for both single and multi-robot coverage BIB002 . The use of multiple robots usually requires a coordination process that includes splitting the area of interest and assigning the resulting sub-areas among the UAVs. The workspace can be divided and assigned in two different steps BIB001 or simultaneously using a negotiation protocol through a distributed way  considering relative capabilities of the vehicles. However, a full solution including optimal area decomposition, allocation and efficient coverage is a cooperative control problem and usually is classified as NP-hard. Besides that, once a vehicle is out of the mission or the scenario changes, a reconfiguration process is necessary to divide and assign the areas to the remaining vehicles. Therefore, many studies simplify this problem considering that the vehicles fly at distinct altitudes in order to avoid collisions. Lastly but not least, there is the number of turning maneuvers often employed as the main performance metric in coverage. When an aerial vehicle executes a turning maneuver, it should reduce its speed, rotate and increase its speed again. Thus, the greater the number of executed maneuvers, the greater the time and the energy spent. In this way, the minimization of the number of maneuvers is often explored by the authors in order to indirectly save energy and prolong the mission time. The authors often connect metrics such as path length, time-to-complete a mission and number of turns with energy consumption trying to minimize them in order to save energy. However, for an efficient energy saving regarding UAVs, further features need to be investigated as vehicle's motions and constraints, turning angles, and optimal speeds. As stated by Di Franco and Buttazzo BIB008 , different distances may have different optimal speeds with minimum energy consumption depending on their length. Therefore, as the major technological boundary using UAVs, the energetic consumption has attracted the interest of researchers  BIB005 BIB004 BIB006  and has become the main optimization criteria due to the limited endurance of UAVs in coverage path planning missions.