  In this paper, we consider the problem of planning a path for a robot to
monitor a known set of features of interest in an environment. We represent the
environment as a graph with vertex weights and edge lengths. The vertices
represent regions of interest, edge lengths give travel times between regions,
and the vertex weights give the importance of each region. As the robot
repeatedly performs a closed walk on the graph, we define the weighted latency
of a vertex to be the maximum time between visits to that vertex, weighted by
the importance (vertex weight) of that vertex. Our goal is to find a closed
walk that minimizes the maximum weighted latency of any vertex. We show that
there does not exist a polynomial time algorithm for the problem. We then
provide two approximation algorithms; an $O(\log n)$-approximation algorithm
and an $O(\log \rho_G)$-approximation algorithm, where $\rho_G$ is the ratio
between the maximum and minimum vertex weights. We provide simulation results
which demonstrate that our algorithms can be applied to problems consisting of
thousands of vertices, and a case study for patrolling a city for crime.
