An Empirical Method for Benchmarking Multi-Robot Patrol Strategies in Adversarial Environments

Abstract

In the field of multi-robot patrolling, graph-based environment models are a popular approach for designing and testing distributed multi-robot patrol strategies. These strategies are typically optimized for regular visiting of the vertices of the patrol graphs. However, analysis of these strategies against potential attackers is limited. We present an empirical, simulation-based method to assess performance of multi-agent patrol strategies against potential adversaries by estimating the probability of simulated attackers succeeding against the patrol agents. We show that this approach can provide new insights into performance that would not be found in standard non-adversarial analysis.