RoboCops: a study of coordination algorithms for autonomous mobile robots in patrolling missions

Abstract

Nowadays, the evolution in the robotics eld allows to free human beings in a set of tasks, mainly the most monotonous and repetitive or, eventually, with dangerous concerns. One of these tasks is the patrolling task in infrastructures. The development and conception of patrolling methods using mobile robots is a scienti c area which has a growing interest. This work focuses on patrolling algorithms for teams of mobile robots endowed with the environment map and the ability for self-location and navigation. The main objective is to develop and validate an original algorithm, scalable to large dimension environments, patrolled by a large number of agents with e cient cooperation, resulting in a high-performance execution of the mission and robustness in the case a fault occurs in a subset of the initially available agents. The presented algorithm is based on multilevel partitioning of the environment map, assigning di erent regions to each mobile agent. Each region corresponds to a subgraph extracted from the existing topological representation. The algorithm deals with the local patrolling task assigned for each robot, being named Multilevel Subgraph Patrolling (MSP) Algorithm. In order to support the algorithm's development and evaluate its performance, a simulator was built, which represented an essential tool during the project. Its properties are presented throughout this document.