Ant Colony Optimization applied to the Multi-Agent Patrolling Problem

摘要

Abstract- Patrolling an environment involves a team of agents whose goal usually consists of continuously visiting its most relevant areas as frequently as possi-ble. For such a task, agents have to coordinate their ac-tions in order to achieve optimal performance. Current research that tackles this complex multi-agent prob-lem usually defines the environment as a graph, so that a wide range of applications can be dealt with, from computer network management to computer games and vehicle routing. In this paper, we consider only in-stances of the multi-agent patrolling problem where all agents are placed on the same starting node. These in-stances are often encountered in robotics applications, where e.g. drones start to patrol from the same area. The Ant Colony Optimization is adopted as the solu-tion approach to these problem instances. Two novel ACO algorithms are proposed here, in which several ants ' colonies are engaged in a competition for finding out the best multi-agent patrolling strategy. Experi-mental results show that, for three graph topologies out of the six which were evaluated, one of our ACO techniques, GU/AA, significantly outperforms the re-inforcement learning technique proposed by Santana et al. (2004) (i.e. GBLA), irrespective of the number of the involved patrolling agents. For the other graph topologies, GU/AA approaches the results obtained with GBLA. 1