Dispersion of Mobile Robots: The Power of Randomness

We consider cooperation among insects, modeled as cooperation between mobile robots on a graph. Within this setting, we consider the problem of mobile robot dispersion on graphs. The study of mobile robots on a graph is an interesting paradigm with many interesting problems and applications. The problem of dispersion in this context, introduced by Augustine and Moses Jr., asks that $n$ robots, initially placed arbitrarily on an $n$ node graph, work together to quickly reach a configuration with exactly one robot at each node. Previous work on this problem has looked at the trade-off between the time to achieve dispersion and the amount of memory required by each robot. However, the trade-off was analyzed for $\mathit{\text{deterministic}}\mathit{\text{algorithms}}$ and the minimum memory required to achieve dispersion was found to be $\mathrm{\Omega }(\log n)$ bits at each robot. In this paper, we show that by harnessing the power of $\mathit{\text{randomness}}$, one can achieve dispersion with $O(\log \mathrm{\Delta })$ bits of memory at each robot, where $\mathrm{\Delta }$ is the maximum degree of the graph. Furthermore, we show a matching lower bound of $\mathrm{\Omega }(\log \mathrm{\Delta })$ bits for any $\mathit{\text{randomized}}\mathit{\text{algorithm}}$ to solve dispersion. We further extend the problem to a general $k$-dispersion problem where $k> n$robotsneedtodisperseover$n$nodessuchthatatmost$\lceil k/n \rceil$ robots are at each node in the final configuration.