# Efficient Coverage Path Planning for a Drone in an Urban Environment
## 2 Related Work  
The GPP problem studied in this work is related to a wide range of studies in the literature spread across several fields, from computational geometry problems to coverage and optimal trajectory planning. Indeed, the problem can be considered a variation of area coverage, initially formulated by [14] and extensively studied since then. Coverage Path Planning (CPP) can be formulated as follows: given a specified region in 2D or 3D, plan a trajectory for one or multiple robots such that every point in the region is visited while avoiding obstacles. Applications of the CPP problem are numerous and include part painting in the automobile industry, guaranteeing full floor cleaning or grass cutting, and finding people in distress in emergency areas. The survey provided by [15] provides a good introduction and pointers to the literature. In a typical CPP formulation, the area to be visited is divided into two sub-regions: the Area of Interest (AOI) and obstacles. The AOI is sometimes divided into smaller cells, and each cell may have a deterministic or probabilistic value attached to it. Probabilistic values may help establish an order in which the cells are to be visited and are commonly used when performing search tasks. For instance, Refs. [9] and [16] calculate a discrete path for a drone by using probability maps where each cell represents the potential risk/occupancy degree. In particular, [16] develops a greedy algorithm that uses clustering to accumulate maximum probabilities and is limited by the maximum allowed length. Another extensive survey [17] specifically considers the coverage problem using drones. Although the land and air versions of the problem are strongly related, planning a coverage path for a drone includes some additional features, including the limited endurance of the platform, its maneuverability limitations, restricted payload, obstacles that may cause occlusions, and other similar issues. The survey revises different CPPapproaches, from simple geometric flight patterns for non-complex AOI to more complex grid-based solutions considering full and partial information about the AOI. The use of drones for coverage tasks requires considering their mounted camera properties, which can only capture points with a cone-shaped Field of View (FOV). The FOV of the camera can be further reduced by obstacles like buildings and walls. To achieve complete coverage of the AOI, each point must be mapped onto the image plane at least once in a complete trajectory. This was considered, for instance, in [7; 18], which introduce two-step trajectory planning algorithms for coverage missions of geometrically complex environments that consider camera sensing constraints. First, they find a set of waypoints from which the AOI can be covered fully; then, they plan a smooth trajectory along these waypoints such that the completion time is minimal. In [19], a flight path planning algorithm is proposed to find collision-free, minimum-length paths for drones' coverage missions. The authors use a footprints' sweeps fitting method to address this problem, considering the camera footprint as a coverage unit. In drone coverage missions, the AOI is sometimes partitioned using a grid where the camera footprint determines the size of each cell [20]. As a result, the drone can observe an entire cell when located at its geometrical center, and the area is said to be fully covered when it visits the centers of all cells. The GPP problem discussed in this paper consists of finding a safe path covering an AOI while meeting a time constraint--i.e., the path length is limited. As a result, it is not possible to scan the entire AOI but to choose which sub-areas have a high priority for scanning. In the case described in [5; 21], a drone needs to visit several spatially distributed Points of Interest (POIs) to maximize the information collected subject to energy constraints. Similarly, [8] suggests an efficient localization solution for SAR missions.