Minimum Energy Coverage Path Planning for UAVs | DRONES Lab

About the project

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.

Related publications

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

J. Modares , Farshad Ghanei , N. Mastronarde , Karthik Dantu
International Conference on Robotics and Automation (ICRA), 2017 , pp. 6182-6189
Project Page | PDF

BibTeX

@inproceedings{Ghanei:2017:ub-anc-planner:7989732,
  author = {Modares, J. and Ghanei, F. and Mastronarde, N. and Dantu, K.},
  journal = {International Conference on Robotics and Automation (ICRA)},
  title = {UB-ANC planner: Energy efficient coverage path planning with multiple drones},
  year = {2017},
  volume = {},
  number = {},
  pages = {6182-6189},
  keywords = {autonomous aerial vehicles;computational complexity;minimisation;path planning;travelling salesman problems;CPP problem;EECPP;MEPP;NP-hard problem;TSP;UB-ANC planner;back tracking algorithm;battle field surveillance;coverage path planning problem;drone design;drone flight paths;drone flight time;energy-efficient coverage path planning;energy-efficient coverage path planning problem;load-balanced allocation;maximum energy consumption minimization;minimum energy path planning problem;traveling salesman problem;unmanned aerial vehicles;Drones;Energy consumption;Energy measurement;Optimization;Path planning;Planning;Power demand},
  doi = {10.1109/ICRA.2017.7989732},
  issn = {},
  month = may
}