Efficient Coverage Path Planning for a Drone in an Urban Environment

Multirotor drones play an increasingly significant role in smart cities and are among the most widely discussed emerging technologies. They are expected to support various applications such as package delivery, data collection, traffic policing, surveillance, and medicine. As part of their services, future drones should be able to solve the last-mile challenge and land safely in urban areas. This paper addresses the path planning task for an autonomous drone searching for a landing place in an urban environment. Our algorithm uses a novel multi-resolution probabilistic approach in which visual information is collected by the drone at decreasing altitudes. As part of the exploration task, we present the Global Path Planning (GPP) problem, which uses probabilistic information and the camera’s field of view to plan safe trajectories that will maximize the search success by covering areas with high potential for proper landing while avoiding no-fly zones and complying with time constraints. The GPP problem is formulated as a minimization problem and then is shown to be NP-hard. As a baseline, we develop an approximation algorithm based on an exhaustive search, and then we devise a more complex yet efficient heuristic algorithm to solve the problem. Finally, we evaluate the algorithms’ performance using simulation experiments. Simulation results obtained from various scenarios show that the proposed heuristic algorithm significantly reduces computation time while keeping coverage performance close to the baseline. To the best of our knowledge, this is the first work referring to a multi-resolution approach to such search missions; further, in particular, the GPP problem has not been addressed previously.