M.Sc Thesis | |

M.Sc Student | Rabinovich Dmitry |
---|---|

Subject | Gathering of Agents on a Line |

Department | Department of Computer Science |

Supervisor | PROF. Alfred Bruckstein |

Full Thesis text |

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.