We studied the problem of designing optimal multi-agent trajectories to patrol an environment which is large w.r.t. the number of agents. Agents must continuously travel in order to periodically cover the whole environment but they can communicate with other agents only when "in visibility" and the inter-distance is small enough. As performance criteria for optimal patrolling we considered the worst-case time gap between any two visits of the same region and the latency for a message to be transferred from any to any robot in the group. 

In [1] we deal with the problem of patrolling of an environment with the aid of a team of autonomous agents. We consider both the design of open-loop trajectories with optimal properties, and of distributed control laws converging to optimal trajectories. As performance criteria, the refresh time and the latency are considered, i.e., respectively, time gap between any two visits of the same region, and the time necessary to inform every agent about an event occurred in the environment. We associate a graph with the environment, and we study separately the case of a chain, tree, and cyclic graph. For the case of chain graph, we first describe a minimum refresh time and latency team trajectory, and we propose a polynomial time algorithm for its computation. Then, we describe a distributed procedure that steers the robots toward an optimal trajectory. For the case of tree graph, a polynomial time algorithm is developed for the minimum refresh time problem, under the technical assumption of a constant number of robots involved in the patrolling task. Finally, we show that the design of a minimum refresh time trajectory for a cyclic graph is NP-hard, and we develop a constant factor approximation algorithm.

In [2] we presented a preliminary version of this work where 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 also presented a heuristic with performance guarantees, and an 8-approximation algorithm to solve the NP-hard patrolling problem. 

References