Technical Report CIS-2009-16

Title: Multi-Agent Deployment and Patrolling on a Ring Graph
Authors: Yotam Elor and Alfred M. Bruckstein
Abstract: We consider three variants of the task of spreading a swarm of agents uniformly on a ring graph. Let n be the size of the ring and k the size of the swarm. Ant-like oblivious agents having limited capabilities are considered. The agents are assumed to have little memory, they all execute the same algorithm and no direct communication is allowed between them. Furthermore, the agents do not possess any global information. In particular n and k are unknown to them. The agents operate on an unweighted ring graph. Every agent can measure the distance to his two neighbors on the ring up to a limited range of d* edges.

In the first task we consider, the agents are required to spread uniformly over the ring. We show that if the ring is undirected or d*<n/k, this is an impossible mission for them. Considering a directed ring and d*>=n/k, we propose an algorithm which achieves the task within the optimal time. The second task discussed requires the agents to spread uniformly over the ring and stop moving. This is called quiescent spread. We prove that under our model in which every agent can measure the distance of only his two closest neighbors, this task is impossible. Instead, we propose an algorithm which achieves quiescent and almost uniform spread. In the third task the agents are required to patrol the ring. Based on the spreading algorithms, we present two algorithms which guarantee an optimal patrol with regard to the worst idleness criterion.

The algorithms we present are scalable and robust. In case the environment (the size of the ring) or the number of agents changes during the run, the swarm adapts and re-deploys without requiring any outside interference.

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