In [1] we studied the the problem of designing optimal multi-agent trajectories to patrol an environment. As performance criterion for optimal patrolling we considered the worst-case time gap between any two visits of the same region. 

We represented the area to be patrolled with a graph, and we characterized the computational complexity of the trajectory design (patrolling) problem with respect to the environment topology and to the number of robots employed in the patrolling task. Even though the patrolling problem is generally NP-hard, we identified particular cases that are solvable efficiently, and we described optimal patrolling trajectories.

Finally, we present a heuristic with performance guarantees, and an 8-approximation algorithm to solve the NP-hard patrolling problem. 

References