New Patrolling Strategies with Short-Range Perception

Abstract

In a Multi-Agent Patrolling Problem (MAPP), a team of agents must optimize a collective metric by moving through a given environment model. MAPPs have a wide range of applications, like continuous surveillance, floor cleaning, and detecting gas leakage. Many heuristic strategies for MAPPs were proposed in the literature using different techniques. In the k-range strategies, autonomous agents communicate indirectly by reading and writing information in the surrounding nodes that are located up to k edges away from the agent. From these, the 0-range strategies (where agents can only sense its current node) are especially suitable for the design of robust autonomous robots with simple hardware. In this work, we propose a new method to convert 1-range strategies (the most common case) into 0-range strategies. We evaluated the new strategies in simulations comparing them to the original 1-range versions. We also built a real low-cost robot that runs the 0-range strategies.