Approximation Algorithms for Multi-Robot Patrol-Scheduling with Min-Max Latency
This addresses efficient surveillance or monitoring tasks for robotics applications, but it is incremental as it builds on known NP-hard scheduling problems with new approximation bounds.
The paper tackles the problem of scheduling patrols for multiple robots to visit sites in a metric space, aiming to minimize the weighted maximum latency between consecutive visits, and presents polynomial-time approximation algorithms with factors such as O(k^2 log(w_max/w_min)) for the general case and a 12-approximation for a 1D variant with constant robots.
We consider the problem of finding patrol schedules for $k$ robots to visit a given set of $n$ sites in a metric space. Each robot has the same maximum speed and the goal is to minimize the weighted maximum latency of any site, where the latency of a site is defined as the maximum time duration between consecutive visits of that site. The problem is NP-hard, as it has the traveling salesman problem as a special case (when $k=1$ and all sites have the same weight). We present a polynomial-time algorithm with an approximation factor of $O(k^2 \log \frac{w_{\max}}{w_{\min}})$ to the optimal solution, where $w_{\max}$ and $w_{\min}$ are the maximum and minimum weight of the sites respectively. Further, we consider the special case where the sites are in 1D. When all sites have the same weight, we present a polynomial-time algorithm to solve the problem exactly. If the sites may have different weights, we present a $12$-approximate solution, which runs in polynomial time when the number of robots, $k$, is a constant.