A distributed ant algorithm for efficiently patrolling a network

A distributed ant algorithm for efficiently patrolling a network

0.00 Avg rating0 Votes
Article ID: iaor2005397
Country: United States
Volume: 37
Issue: 3
Start Page Number: 165
End Page Number: 186
Publication Date: Nov 2003
Journal: Algorithmica
Authors: , ,
Keywords: search
Abstract:

We consider the problem of patrolling, i.e. ongoing exploration of a network by a decentralised 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 Eulerian cycle within 2|E|D steps, |E| being the number of edges in the graph and D being its diameter. For a team of k agents, we show that after at most 2(l + 1/k)|E|D 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.

Reviews

Required fields are marked *. Your email address will not be published.