Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Spiral <s> We present algorithms for the efficient insertion and removal of constraints in Delaunay Triangulations. Constraints are considered to be points or any kind of polygonal lines. Degenerations such as edge overlapping, self-intersections or duplicated points are allowed and are automatically detected and fixed on line. As a result, a fully Dynamic Constrained Delaunay Triangulation is achieved, able to efficiently maintain a consistent triangulated representation of dynamic polygonal domains. Several applications in the fields of data visualization, reconstruction, geographic information systems and collision-free path planning are discussed. <s> BIB001 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Spiral <s> Several approaches can be identified in the literature for area decomposition: Grid based methods, Cellular decomposition and Boustrophedon (or Morse) decomposition. This paper proposes a novel discretization method for the area based on computational geometry approaches. By using a Constrained Delaunay Triangulation, a complex area is segmented in cells which have the size of the projected field of view of the RPAS (UAS) on-board sensor. In addition, costs are associated to each of these cells for both partitioning the area among several RPAS and full covering each sub-area. Simulation results show that this approach manages to optimally decompose and partition a complex area, and also produces a graph that can be used for different cost-based path planning methods. <s> BIB002 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Spiral <s> The paper presents a novel algorithmic approach that allows to tackle in a common framework the problems of area decomposition, partition and coverage for multiple heterogeneous Unmanned Aircraft Systems (UAS). The approach combines computational geometry techniques and graph search algorithms in a multi-UAS context. Even though literature provides several strategies for area decomposition like grid overlay decomposition or exact cellular methods, some fail to either successfully decompose complex areas, or the associated path generation strategies are not feasible. The proposed approach manages to perform an exact cellular decomposition of non-convex polygonal coastal areas and includes an attributes based schema for area partitioning. In particular, the proposed solution uses a Constrained Delaunay Triangulation (CDT) for computing a configuration space of a complex area containing obstacles. The cell size of each produced triangle is constrained to the maximum projected Field-of-View (FoV) of the sensor on-board each UAS. In addition, the resulting mesh is considered as an undirected graph, where each vertex has several attributes used for area partitioning and coverage in a multi-UAS context. Simulation results show how the algorithms can compute sound solutions in real complex coastal regions. <s> BIB003 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Spiral <s> This paper tackles the problems of exact cell decomposition and partitioning of a coastal region for a team of heterogeneous Unmanned Aerial Vehicles (UAVs) with an approach that takes into account the field of view or sensing radius of the sensors on-board. An initial sensor-based exact cell decomposition of the area aids in the partitioning process, which is performed in two steps. In the first step, a growing regions algorithm performs an isotropic partitioning of the area based on the initial locations of the UAVs and their relative capabilities. Then, two novel algorithms are applied to compute an adjustment of this partitioning process, in order to solve deadlock situations that generate non-allocated regions and sub-areas above or below the relative capabilities of the UAVs. Finally, realistic simulations have been conducted for the evaluation of the proposed solution, and the obtained results show that these algorithms can compute valid and sound solutions in complex coastal region scenarios under different setups for the UAVs. <s> BIB004 </s> Survey on Coverage Path Planning with Unmanned Aerial Vehicles <s> Spiral <s> This paper addresses area coverage in complex non concave coastal regions for an arbitrary number of heterogeneous Unmanned Aircraft Systems (UAS). The space is discretized with the constrained Delaunay triangulation and the Lloyd optimization is applied to the computed mesh. The paper presents an algorithm to compute a waypoint list for each UAS such that each sub-area is covered with its sensor on-board following a pattern that goes from the borders of the sub-area to the inner regions. In addition, the resulting paths lead to a uniform coverage pattern that avoids visiting some regions more times than others. Different sensitivity parameters of the algorithm are compared based on the average angles between the waypoints and the total length of the paths. Results show that these parameters support the optimization of the computed waypoint lists and the proposed algorithm produces feasible coverage paths while increasing their smoothness. <s> BIB005
A spiral CPP algorithm for missions in coastal regions using multiple heterogeneous UAVs is explored by Balampanis et al. in several works. The authors discretize the workspace considering the sensing capabilities of the aerial vehicles using a Constrained Delaunay Triangulation (CDT) BIB001 introduced by Balampanis et al. BIB002 and Balampanis et al. BIB003 . The authors state that the classical grid decomposition creates regular square cells that are partially over no-fly zones or outside the workspace. Thus, the CDT provides triangle cells within the area of interest matching almost the exact shape of the area. In order to generate more uniform triangles, they applied the Lloyd optimization  . This technique approximates the cell angle to 60 degrees, enhancing the uniformity. Then, a spiral algorithm previously proposed by Balampanis et al. BIB004 , and improved by Balampanis et al. BIB005 by introducing a smoothing parameter, is used to generate the coverage paths in the resulting sub-areas. The proposed strategy has been tested in Software-In-The-Loop simulation. A further analysis regarding coverage patterns is performed by comparing the spiral-like pattern using the CDT/Lloyd optimization (triangle cells) with the classical grid decomposition (square cells) using back-and-forth motions. The authors claim that their approach is capable of covering fully a given area with a smoother trajectory without entering into NFZ or going outside the area. However, the approach presents longer coverage paths with a higher number of turns compared with the back-and-forth.