Technical Report CIS-2016-01

Title: Chase Your Farthest Neighbour: a simple gathering algorithm for anonymous, oblivious and non-communicating agents
Authors: Rotem Manor and Alfred M. Bruckstein
PDFCurrently accessibly only within the Technion network
Abstract: We consider a group of mobile robotic agents, identical and indistinguishable, having no memory (oblivious) and no common frame of reference (neither absolute location nor a common orientation). Furthermore, these agents are assumed to posses only rudimentary sensing and computational capabilities (limited visibility and basic geometric sorting). We prove that, such robots, implementing a Chase the farthest neighbour policy, preform the task of gathering to a point within a finite time or a finite expected number of time steps.

In continuous time, preforming such a gathering task is rather straightforward, while in the discrete time, we prove that a randomized semi-synchronised timing model leads to gathering within a finite expected number of time-steps.

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 2016
To the main CS technical reports page

Computer science department, Technion