Multi-robot Patrol via the Metropolis-Hastings Algorithm

Abstract

The problem of multi-robot patrol is a growing field of study that focuses on the problem of coordinating teams of robots to optimally patrol a perimeter or area. In this paper, we propose a new method of generating patrolling policies in the form of Markov chains via the Metropolis-Hastings algorithm. Our proposed method generates non-deterministic patrolling policies with the purpose of minimizing the probability of adversarial attack to a given area. We compare our method to a wide variety of approaches to patrolling methods on a large set of graphs in order to test the effectiveness of Markov chains as a patrolling policy.