UB-ANC planner: Energy efficient coverage path planning with multiple drones

Advancements in the design of drones have led to their use in varied environments and applications such as battle field surveillance. In such scenarios, swarms of drones can coordinate to survey a given area. We consider the problem of covering an arbitrary area containing obstacles using multiple drones, i.e., the so-called coverage path planning (CPP) problem. The goal of the CPP problem is to find paths for each drone such that the entire area is covered. However, a major limitation in such deployments is drone flight time. To most efficiently use a swarm, we propose to minimize the maximum energy consumption among all drones' flight paths. We perform measurements to understand energy consumption of a drone. Using these measurements, we formulate an Energy Efficient Coverage Path Planning (EECPP) problem. We solve this problem in two steps: a load-balanced allocation of the given area to individual drones, and a minimum energy path planning (MEPP) problem for each drone. We conjecture that MEPP is NP-hard as it is similar to the Traveling Salesman Problem (TSP). We propose an adaptation of the well-known Lin-Kernighan heuristic for the TSP to efficiently solve the problem. We compare our solution to the recently proposed depth-limited search with back tracking algorithm, the optimal solution, and rastering as a baseline. Results show that our algorithm is more computationally efficient and provides more energy-efficient solutions compared to the other heuristics.