Coverage of an environment using energy-constrained unmanned aerial vehicles

Abstract We study the problem of covering an environment using an Unmanned Aerial Vehicle (UAV) with limited battery capacity. We consider a scenario where the UAV can land on an Unmanned Ground Vehicle (UGV) and recharge the onboard battery. The UGV can also recharge the UAV while transporting the UAV to the next take-off site. We present an algorithm to solve a new variant of the area coverage problem that takes into account this symbiotic UAV and UGV system. The input consists of a set of boustrophedon cells — rectangular strips whose width is equal to the field-of-view of the sensor on the UAV. The goal is to find a tour for the UAV that visits and covers all cells in minimum time. This includes flight time for visiting and covering all cells, recharging time, as well as the take-off and landing times. We show how to reduce this problem to a known NP-hard problem, Generalized Traveling Salesperson Problem (GTSP). Given an optimal GTSP solver, our approach finds the optimal coverage paths for the UAV and UGV. We evaluate our algorithm through simulations and proof-of-concept experiments.

@inproceedings{YuOKaTok19,
  author = {Kevin Yu and Jason M. O'Kane and Pratap Tokekar},
  booktitle = {Proc. IEEE International Conference on Robotics and
               Automation},
  title = {Coverage of an environment using energy-constrained unmanned
           aerial vehicles},
  year = {2019}
}