Dispersion of Mobile Robots

Abstract

We introduce a new problem in the domain of mobile robots, which we term dispersion. In this problem, n robots are placed in an n node graph arbitrarily and must coordinate with each other to reach a final configuration such that exactly one robot is at each node. We study this problem through the lenses of minimizing the memory required by each robot and of minimizing the number of rounds required to achieve dispersion.