MSP algorithm

Abstract

This article addresses the problem of efficient multi-robot patrolling in a known environment. The proposed approach assigns regions to each mobile agent. Every region is represented by a subgraph extracted from the topological representation of the global environment. A new algorithm is proposed in order to deal with the local patrolling task assigned for each robot, named Multilevel Subgraph Patrolling (MSP) Algorithm. It handles some major graph theory classic problems like graph partitioning, Hamilton cycles, non-Hamilton cycles and longest path searches. The flexible, scalable, robust and high performance nature of this approach is testified by simulation results.