Technical Report CIS-2009-15

Title: Autonomous Multi-Agent Cycle Based Patrolling.
Authors: Yotam Elor and Alfred M. Bruckstein
Abstract: We introduce a novel multi-agent patrolling strategy. By assumption, the swarm of agents performing the task consists of very low capability ant-like agents. The agents have little memory, they can not communicate and their sensing abilities are local. Furthermore, the agents do not posses any knowledge regarding the graph or the swarm size. However, the agents may mark the graph vertices with pheromone stamps which can later be sensed. These markings are used as a primitive form of distributed memory and communication. The proposed strategy is a bundle of two algorithms. A single agent (the "leader") is responsible of finding a short cycle which covers the graph, this is achieved using a "cycle finding" algorithm. All other agents follow that cycle while maintaining even gaps between them using a "spreading algorithm". We prove that the algorithms converge within a finite time. After convergence, the maximum time lag between two successive visits to any vertex using the proposed strategy is at most 4k/(k-1)*lmax/lmin the optimal where lmax (lmin) is the longest (shortest) edge in the graph and k is the swarm size.

The proposed strategy is scalable and robust. In case the number of agents changes during run (e.g. as a result of an agent break down) the agents autonomously redeploy uniformly over the cycle. In case the graph changes, the leader autonomously finds a new patrolling route.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 2009
To the main CS technical reports page

Computer science department, Technion