Finding optimal routes for multi-robot patrolling in generic graphs

Multi-robot patrolling is a problem that has important applications in security and surveillance. However, the optimal task assignment is known to be NP-hard. We consider evenly spacing the robots in a cyclic Traveling Salesman Problem (TSP) tour or partitioning the graph of the environment. The trade-off in performance, overall team travel cost and coordination is analyzed in this paper. We provide both a theoretical analysis and simulation results across multiple environments. The results demonstrate that generally cyclic-based strategies are superior, especially when small teams are used but at the expense of greater team cost, whereas partitioning strategies are especially suitable for larger teams and unbalanced graph topologies. The reported results show that graph topology and team size are fundamental to determine the best choice for a patrol strategy.