Decentralized Strategies Based on Node Marks for Multi-Robot Patrolling on Weighted Graphs

Abstract

In the multi-robot patrolling problem in graphs, each robot continually visits the nodes in order to minimize a collective performance metric. Many decentralized strategies were proposed. However, the more general case of graphs with arbitrary weights (representing distances or costs) was approached mostly by centralized algorithms or algorithms with some kind of global information. In this work, we propose three decentralized techniques that use only local information - data written on the nodes - and can be implemented in simple robots. They extend three previous decentralized strategies byincorporating the edge weights in the decision process. We present a simulation study that show that the extended techniques increased the performances in many settings, but not in all.