The Generalized Persistent Monitoring Problem

In this article, we consider the problem of planning an optimal route for an unmanned vehicle, tasked with persistently monitoring a set of targets. The targets are grouped into m subsets, referred to as clusters. To monitor a cluster, the vehicle must collect data from any one target in the cluster, by making a physical visit to the target. The vehicle has a finite fuel capacity, which is specified in terms of the number of visits it can make, at the end of which it must be refueled/recharged at a depot (which is one of the targets). Given k allowed visits for the vehicle, the problem of interest is to plan a closed walk (route) of k visits that can be repeated continuously, such that the maximum time between successive visits to the clusters is minimized (the minimum value is R* (k)). Here, we prove that for k >= m(2) m, R* (k) takes only two values, R*(m) when k is an integral multiple of m, and R* (m+1) otherwise, leading to significant computational savings. We corroborate this result by performing numerical simulations on a Dubins vehicle.