Show all publications

Ant Colony Optimization Applied to the Multi-Agent Patrolling Problem

Download PDFDownload Bibliography in Open DocumentDownload Bibliography in HTMLDownload BibTeXDownload RISDownload Bibliographical Ontology (RDF)
In Proc. of IEEE Symposium on Swarm Intelligence, 2006.
Patrolling an environment involves a team of agents whose goal usually consists of continuously visiting its most relevant areas as frequently as possible. For such a task, agents have to coordinate their actions in order to achieve optimal performance. Current research that tackles this complex multi-agent problem 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 instances of the multi-agent patrolling problem where all agents are placed on the same starting node. These instances are often encountered in robotics applications, where eg drones start to patrol from the same area. The Ant Colony Optimization is adopted as the solution 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. Experimental results show that, for three graph topologies out of the six which were evaluated, one of our ACO techniques, GU/AA, significantly outperforms the reinforcement learning technique proposed by Santana extit{et al.} (2004) (ie GBLA), irrespective of the number of the involved patrolling agents. For the other graph topologies, GU/AA approaches the results obtained with GBLA.
Multi-agent patrolling, ACO.
Publication Category:
International conference with proceedings
Copyright 2010-2019 © Laboratoire Connaissance et Intelligence Artificielle DistribuĂ©es - Université Bourgogne Franche-Comté - Privacy policy