Quality-aware UAV coverage and path planning in geometrically complex environments

Networks of unmanned aerial vehicles (UAVs), capable of providing flexible aerial views over large areas, are playing important roles in today's distributed sensing systems. Since camera sensors are sensitive to occlusions, it is more challenging for UAVs to provide satisfactory sensing quality in geometrically complex environments, such as dense urban areas and mountainous terrains. This paper proposes a new quality-aware and energy-efficient UAV coverage and path planning scheme with the objective of sensing a geometrically complex target area with satisfactory spatial and temporal resolutions. An occlusion-aware waypoint generation algorithm is first designed to find the best set of waypoints for taking pictures in a target area to satisfy the spatial resolution requirement. The selected waypoints are then assigned to multiple UAVs by solving a vehicle routing problem (VRP) such that all the waypoints are visited within a global deadline to satisfy the temporal resolution requirement. The vehicle routing problem is formulated to minimize the maximum energy for the UAVs to travel through the waypoints within the deadline. A Min-Max energy path planning algorithm is designed to solve this problem in two steps: first, a mixed integer linear programming problem (MILP) is solved to calculate the minimum energy for a UAV to go from one waypoint to other; then, a genetic algorithm is devised to plan the paths for all the UAVs. Evaluation results show that the proposed coverage and path planning scheme results in better coverage and energy consumption than traditional coverage and path planning techniques for UAVs.