Fast Uniform Scattering on a Grid for Asynchronous Oblivious Robots

We consider $K=(k+1)\times (k+1)$ autonomous mobile robots operating on an anonymous $N=(n+1)\times (n+1)$-node grid, $n=k·d,d\ge 2$, $k\ge 2,$ following Look-Compute-Move cycles under the classic oblivious robots model. Starting from any initial configuration of robots positioned on distinct grid nodes, we consider the uniform scattering problem of repositioning them on the grid nodes so that each robot reaches to a static configuration in which they cover uniformly the grid. In this paper, we provide the first O(n) time, collision-free algorithm for this problem in the asynchronous setting, given that the robots have common orientation, knowledge of n and k, O(1)-bits of memory, and visibility range of $2·max\{n/k,k\}$. The best previously known algorithm for this problem on a grid has runtime $O(n^2/d)$ (or O(nk)) with the same robot capabilities in the asynchronous setting except the visibility range $2·n/k$. The proposed algorithm is asymptotically time-optimal since there is a time lower bound of $\Omega (n)$.