Optimal UAV Route Planning for Persistent Monitoring Missions

This article addresses a persistent monitoring problem (PMP) that requires an unmanned aerial vehicle (UAV) to repeatedly visit n targets of equal priority. The UAV has limited onboard fuel/charge and must be regularly serviced at a depot. Given a fixed number of visits, k, for the UAV to the targets between successive services, the objective of the PMP is to determine an optimal sequence of visits such that the maximum time elapsed between successive visits to any target is minimized. This planning problem is a generalization of the traveling salesman problem and is NP-hard. We characterize the optimal solutions to this problem for different values of k and develop algorithms that can compute the optimal solutions relatively fast. Numerical results are also presented to corroborate the performance of the proposed approach.

I. Introduction

Persistent monitoring missions are repetitive in nature and last for prolonged periods of time. In this work, we consider an optimal route planning problem arising in persistent monitoring missions that require a UAV to repeatedly visit targets of which one target (referred to as the depot) also acts as a recharging or a refueling station. For the optimal performance of these missions, it is desirable to make the revisit time, defined as the maximum of the time elapsed between successive visits to any target, as small as possible.