Show all publications

The Multi-Agent Patrolling Problem - Theoretical Results About Cyclic Strategies

Download PDFDownload Bibliography in Open DocumentDownload Bibliography in HTMLDownload BibTeXDownload RISDownload Bibliographical Ontology (RDF)
In Proc. of Practical Applications of Agents and Multi-Agent Systems (PAAMS), 2014.
Patrolling an environment consists in visiting as frequently as possible its most relevant areas in order to supervise, control or protect it. This task is commonly performed by a team of agents that seek to optimize a performance criterion generally based on the notion of node idleness, that is the period during which a node remains unvisited. For some patrolling strategies, the performance criterion may be unbounded or the classical iterative evaluation algorithm may be ineffective to rapidly provide this performance criterion. The contribution of this paper is fourfold. Firstly we extend the formulation of the classical multi-agent patrolling problem. Secondly we define a large class of multi-agent patrolling strategies, the consistent cyclic patrolling strategies, where every agent may visit some nodes once before ultimately visiting the same set of nodes infinitely often. Idleness-based performance criteria considered in this paper to evaluate such strategies are always bounded. Thirdly we provide theoretical results about the computation time required for evaluating efficiently and accurately any consistent cyclic strategy. Fourthly we propose an efficient and accurate evaluation algorithm of polynomial complexity based on these theoretical results.
Multi-agent patrolling, cyclic strategies, theoretical results
Publication Category:
International conference with proceedings
Copyright 2010-2019 © Laboratoire Connaissance et Intelligence Artificielle Distribu√©es - Université Bourgogne Franche-Comté - Privacy policy