M.Sc Thesis

M.Sc StudentRabinovich Dmitry
SubjectGathering of Agents on a Line
DepartmentDepartment of Computer Science
Supervisor PROF. Alfred Bruckstein
Full Thesis textFull thesis text - English Version


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 - e) a unit distance towards the neighbors (otherwise, with low probability e, they jump one unit away). We prove that all agents, except two, gather almost surely inside a unit size interval for any e < 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.