The Gravitational Strategy for the Timed Patrolling

A great number of techniques were already applied to the non-adversarial variation of the multiagent patrolling problem. Experiments suggest that, for general graphs, all those approaches are inferior to a strategy based on the travelling salesman problem (TSP), in which agents are distributed equidistantly along the TSP-cycle. This approach, however, is neither optimal nor scalable. In this article, we present a novel patrolling strategy which tries to overcome these limitations. Inspired on Newton´s law of gravitation, our approach consists in assigning to each node of the graph an abstract mass which grows while the node remains unvisited, creating a force that attracts agents to it. We defined some variations of our approach and experimentally compared them to the TSP-based strategy, concluding that our approach performs better in general.