Efficient Computation of Optimal UAV Routes for Persistent Monitoring of Targets
- Additional Document Info
- View All
© 2019 IEEE. In this article, we consider a routing problem that arises in the scenario of persistently monitoring a set of targets using an unmanned vehicle. A UAV is tasked with monitoring a set of targets, by frequently visiting them for data collection. The UAV has a limited fuel capacity, which is specified in terms of the number of visits it makes, at the end of which it must be recharged at a depot. The problem considered here is to plan an optimal sequence of visits (to targets) for the UAV, such that the maximum time between consecutive revisits to the targets is minimized. The problem is a generalization of the Traveling Salesman Problem (TSP) and is computationally challenging; It is significantly difficult to compute optimal solutions using standard formulations. However, the authors recently developed a set of theoretical results characterizing the structure of optimal solutions for this problem. Using these results, in this article, we propose a new formulation to solve the problem. Extensive numerical simulations suggest that the average computation time required to solve the problem using the proposed formulation is within a fraction of a second on a standard laptop (here, a MacBook Pro with Intel Core i7 processor and 16 GB RAM was used).
author list (cited authors)
Hari, S., Rathinam, S., Darbha, S., Kalyanam, K., Manyam, S. G., & Casbeer, D.