Minimum Energy Coverage Path Planning for UAVs

Advancements in the design of drones have led to their use in varied environments and applications such as search and rescue, surveillance, package delivery, first responder assistance and others. In such scenarios, drones might need to cover an arbitrary area containing obstacles, i.e., the so-called coverage path planning (CPP) problem. The goal of the problem is to find a path for the drone such that the entire area is covered. However, a major limitation in such deployments is the drone's flight time due to their limited battery energy. To most efficiently use its energy resource, we propose to minimize the energy consumption for covering the area. We perform measurements to understand the energy consumption of a drone with respect to distance traveled and turns. Using these measurements, we formulate a Minimum Energy Coverage Path Planning (MECPP) problem. The MECPP problem is similar to the Traveling Salesman Problem (TSP) which is NP-hard. We propose an adaptation of the Lin-Kernighan heuristic (LKH) for the TSP to efficiently solve the MECPP problem. In simulations, we compare our solution to the conventional LKH, the recently proposed depth-limited search (DLS) with back tracking algorithm, the optimal solution, and rastering as a baseline. Results show that our algorithm is more computationally efficient than the other heuristics and provides more energy-efficient solutions. Finally, we experimentally verify that our solution consumes approximately 15% less energy than DLS in actual flight tests.

Contributors

Publications