Technical Report CIS-2002-05

Title: A Distributed Ant Algorithm for Efficiently Patrolling a Network
Authors: Vladimir Yanovski, Israel A. Wagner, Alfred M. Bruckstein
Abstract: We consider the problem of patrolling - i.e. ongoing exploration of a network by a decentralized group of simple memoryless robotic agents. The model for the network is an undirected graph, and our goal, beyond complete exploration, is to achieve close to uniform frequency of traversal of the graph's edges. A simple multi-agent exploration algorithm is presented and analyzed. It is shown that a single agent following this procedure enters, after a transient period, a periodic motion which is an extended Eulerian cycle, during which all edges are traversed an identical number of times. We further prove that if the network is Eulerian, a single agent goes into an Eulerian cycle within 2ED steps, E being the number of edges in the graph and D - its diameter. For a team of k agents, we show that after at most 2(1 + 1/k)|ED steps the numbers of edge visits in the network are balanced up to a factor of two. In addition, various aspects of the algorithm are demonstrated by simulations.
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 or PS files directly. The latter URLs may change without notice.

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

Computer science department, Technion