  In this paper we study multi-robot path planning for persistent monitoring
tasks. We consider the case where robots have a limited battery capacity with a
discharge time $D$. We represent the areas to be monitored as the vertices of a
weighted graph. For each vertex, there is a constraint on the maximum allowable
time between robot visits, called the latency. The objective is to find the
minimum number of robots that can satisfy these latency constraints while also
ensuring that the robots periodically charge at a recharging depot. The
decision version of this problem is known to be PSPACE-complete. We present a
$O(\frac{\log D}{\log \log D}\log \rho)$ approximation algorithm for the
problem where $\rho$ is the ratio of the maximum and the minimum latency
constraints. We also present an orienteering based heuristic to solve the
problem and show empirically that it typically provides higher quality
solutions than the approximation algorithm. We extend our results to provide an
algorithm for the problem of minimizing the maximum weighted latency given a
fixed number of robots. We evaluate our algorithms on large problem instances
in a patrolling scenario and in a wildfire monitoring application. We also
compare the algorithms with an existing solver on benchmark instances.
