Multi-robot patrolling algorithms: examining performance and scalability

In this paper the problem of patrolling an environment with a dynamic team of robots is targeted. Lately, the interest of the research community has been focused in the development of patrol strategies; however there is a deficit of studies comparing such strategies, namely in terms of their performance and team scalability in different environments. For this reason, an evaluation of five representative patrol approaches is presented in this article. Aiming to analyze the performance, ability to scale and the behavior resulting from interactions between teammates, extensive realistic simulation using ROS together with Stage was conducted. The metric used to compare the performance is the average idleness of the topological environment (i.e. graph), that represents the area to patrol. The results presented help to identify which strategies enable enhanced team scalability and which are the most suitable approaches given any environment, supporting future research directions in the field.