Hari, Sai Krishna Kanth (Texas A & M University, College Station), Rathinam, Sivakumar (Texas A & M University), Darbha, Swaroop (Texas A & M Univ.), Kalyanam, Krishna (PARC), Manyam, Satyanarayana Gupta (Infoscitex corporation), Casbeer, David (Air force Research laboratories)

Bounding Algorithms for Persistent Monitoring of Targets Using Unmanned Vehicles

Scheduled for presentation during the Regular Session "Path Planning III" (ThA1), Thursday, June 13, 2019, 11:20−11:40, Heritage B

2020 International Conference on Unmanned Aircraft Systems (ICUAS), June 11-14, 2019, Athens, Greece

This information is tentative and subject to change. Compiled on April 25, 2024

Abstract

Persistent monitoring of targets in civil and military applications require a team of Unmanned Vehicles to visit the targets repeatedly over time. The vehicles visit the targets and transmit the collected information to the base station for further processing. The frequency of monitoring any given target is intuitively specified by its target revisit time, $i.e.$, the maximum time elapsed between any two successive visits to the target. The persistent monitoring problem considered in this article is as follows: Given $m$ vehicles and $k$ allowed visits to $n$ targets, find an optimal path for each vehicle such that each target is visited at least once, each target is visited at most by one vehicle and the maximum revisit time over all the targets is minimized. This problem is a generalization of the min-max, multiple Traveling Salesman Problem and is NP-Hard. Bounds on the optimal revisit times are provided for the case when the number of visits is large. Specifically, it is shown that the optimal revisit time for any number of visits is lower and upper bounded by the optimal revisit times corresponding to $n+m$ visits and $n+m+1$ visits. Optimal revisit times are also developed for the single vehicle problem with tighter bounds. These results are practically useful in reducing the computational burden as one only needs to solve two problems for any large number of visits to find a good feasible solution.