PatrolGRAPH: a Distributed Algorithm for Multi-Robot Patrolling

Abstract

This paper describes PatrolGRAPH, a novel real-time search algorithm which has been specifically designed to solve the “patrolling problem”, i.e., the problem of repeatedly visiting a set of specific locations in the environment. The algorithm has extremely low requirements in terms of computational power, does not require inter-robot communication, and can even be implemented on memoryless robots. Moreover, the algorithm is proven to be statistically complete as well as easily implementable on real, marketable robot swarms for real-world applications.