  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.
