Technical Report MSC-2017-32

Title: Gathering of Agents on a Line
Authors: Dmitry Rabinovich
Supervisors: Alfred M. Bruckstein
PDFCurrently accessibly only within the Technion network
Abstract: We consider a group of mobile agents on a line, identical and indistinguishable, memoryless, having the sole capability to sense the presence of neighboring agents to the left and to the right. The agents' rule of motion is as follows: at each moment, agents with neighbors on both sides stay put, while agents with neighbors on one side only jump with high probability $(1 - \varepsilon)$ a unit distance towards the neighbors (otherwise, with low probability $\varepsilon$, they jump one unit away). We prove that all agents, except two, gather almost surely inside a unit size interval for any $\varepsilon < \nicefrac{1}/{2}$ and do that in finite expected time. Two agents, the current left-most and right-most ones perform random walks biased towards the cluster of other agents. The cluster of gathered agents slowly moves on the line. Interesting interactions occur when the left and/or right Random Walkers reach the clustered agents and these interactions are completely analyzed herein. We give an upper bound estimate on the rate of convergence to stationary distribution of left and right Random Walkers, and test empirically our theoretical results. We briefly examine the generalization of the model to higher dimensions and analyze some pathological cases. We conclude that some additional assumptions should be made, to apply our results to more complex models.

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 MSC technical reports of 2017
To the main CS technical reports page

Computer science department, Technion