Time-optimal uniform scattering in a grid

Abstract

We consider the distributed setting of K = (k + 1) × (k + 1) autonomous mobile robots operating on a grid graph of N = (n + 1) × (n + 1) nodes with n = k · d, d ≥ 2, k ≥ 2, following Look-Compute-Move cycles and communicating with other robots using colored lights under the robots with lights model. We consider the uniform scattering problem of repositioning the robots on the nodes of the grid graph so that each robot reach to a static configuration in which they cover uniformly the grid. In this paper, we provide the first O(n) time algorithm for this problem for robots with lights in the fully synchronous setting, given that the robots have the common orientation, the knowledge of parameters n and k, and the visibility range of distance 2d. The best previously known algorithm solves this problem in O(N/d) (i.e., O(n2/d)) time under the classic oblivious robots model (with no lights) with the same capabilities in the asynchronous setting. Our algorithm is asymptotically time-optimal, since for any solution to this uniform scattering problem in both the classic and lights models, Ω(n) time is necessary. Moreover, the proposed algorithm is collision-free.