  Mobile robots, especially unmanned aerial vehicles (UAVs), are of increasing
interest for surveillance and disaster response scenarios. We consider the
problem of multi-robot persistent surveillance with connectivity constraints
where robots have to visit sensing locations periodically and maintain a
multi-hop connection to a base station. We formally define several problem
instances closely related to multi-robot persistent surveillance with
connectivity constraints, i.e., connectivity-constrained multi-robot persistent
surveillance (CMPS), connectivity-constrained multi-robot reachability (CMR),
and connectivity-constrained multi-robot reachability with relay dropping
(CMRD), and show that they are all NP-hard on general graph. We introduce three
heuristics with different planning horizons for convex grid graphs and combine
these with a tree traversal approach which can be applied to a partitioning of
non-convex grid graphs (CMPS with tree traversal, CMPSTT). In simulation
studies we show that a short horizon greedy approach, which requires parameters
to be optimized beforehand, can outperform a full horizon approach, which
requires a tour through all sensing locations, if the number of robots is
larger than the minimum number of robots required to reach all sensing
locations. The minimum number required is the number of robots necessary for
building a chain to the farthest sensing location from the base station.
Furthermore, we show that partitioning the area and applying the tree traversal
approach can achieve a performance similar to the unpartitioned case up to a
certain number of robots but requires less optimization time.
