Bounds on Optimal Revisit Times in Persistent Monitoring Missions with a Distinct \& Remote Service Station
This addresses efficient UAV routing for long-term monitoring tasks, but it is incremental as it builds on existing NP-hard optimization problems.
The paper tackles the problem of minimizing the maximum time between successive visits to targets in persistent monitoring missions with a remote service station, developing an algorithm that produces near-optimal solutions within 0.01% of the optimum on average.
Persistent monitoring missions require an up-to-date knowledge of the changing state of the underlying environment. UAVs can be gainfully employed to continually visit a set of targets representing tasks (and locations) in the environment and collect data therein for long time periods. The enduring nature of these missions requires the UAV to be regularly recharged at a service station. In this paper, we consider the case in which the service station is not co-located with any of the targets. An efficient monitoring requires the revisit time, defined as the maximum of the time elapsed between successive revisits to targets, to be minimized. Here, we consider the problem of determining UAV routes that lead to the minimum revisit time. The problem is NP-hard, and its computational difficulty increases with the fuel capacity of the UAV. We develop an algorithm to construct near-optimal solutions to the problem quickly, when the fuel capacity exceeds a threshold. We also develop lower bounds to the optimal revisit time and use these bounds to demonstrate (through numerical simulations) that the constructed solutions are, on an average, at most 0.01% away from the optimum.