Self-Organization of Patrolling-Ant Algorithms

We consider here multi-agent patrolling as the task for a group of agents to repeatedly visit all the cells of a discrete environment. Wagner et al. have introduced patrolling ant algorithms, where each agent can only mark and move according to its local perception of the environment. Among various results, it has been experimentally observed that for some algorithms the agents often self-organize in stable cycles which are near optimal in terms of visit frequency. This property is particularly interesting as it guarantees the long-term performance of the patrol. The present paper focuses on the convergence behavior of a typical ant-based algorithm, EVAW. The main contribution of this paper is to theoretically prove that the group of agents self-organizes in cycles under certain hypotheses. These hypotheses rely on some implementation details that allow to control the predictability of the system. In addition to these qualitative results on the convergence behavior, we aim at experimentally evaluating its characteristics. This led us to a second contribution: an algorithm that detects steady states. Finally, we propose an improved behavior that dramatically speeds up the self-organization and allows us to experiment on larger problems (both in terms of size and number of agents).