Robust Planning for Persistent Surveillance With Energy-Constrained UAVs and Mobile Charging Stations

We consider persistent (long-horizon) surveillance over an environment by using energy-constrained unmanned aerial vehicles (UAVs), which are supported by unmanned ground vehicles (UGVs) serving as mobile charging stations. The goal is to periodically visit a set of monitoring points by the UAVs while minimizing the maximum time between the consecutive visits to any of those points. In general, the optimal planning of UAVs and UGVs in such a persistent surveillance scenario is an NP-hard combinatorial optimization problem. Furthermore, the problem also demands a solution strategy that can successfully handle obstacles, especially on the ground, that are unknown a priori in many real-life scenarios. We present a scalable and robust approximate algorithm that is based on 1) forming uniform UAV-UGV teams, 2) decomposing the environment into maximal partitions that can be covered by the UAVs in a single fuel cycle as long as the UAVs are released sufficiently close to the centers of the partitions, 3) maintaining the teams uniformly distributed over a cyclic path traversing those partitions, and 4) having the UAVs in each team cover their current partition and be transported to the next partition while being recharged by the UGV. We support our proposed algorithm with some theoretical results and simulations.