Dispersion of Mobile Robots on Grids

The dispersion problem on graphs asks \(k\le n\) robots initially placed arbitrarily on the nodes of an n-node anonymous graph to reposition autonomously to reach a configuration in which each robot is on a distinct node of the graph. This problem is of significant interest due to its relationship to many other fundamental robot coordination problems, such as exploration, scattering, load balancing, relocation of self-driven electric cars (robots) to recharge stations (nodes), etc. The objective in this problem is to simultaneously minimize (or provide trade-off between) two fundamental performance metrics: (i) time to achieve dispersion and (ii) memory requirement at each robot. The existing algorithms for trees and arbitrary graphs either minimize time or memory but not both. In this paper, we consider for the very first time the dispersion problem on a grid graph embedded in the Euclidean plane and present solutions that simultaneously minimize both the metrics. The grid graph is appealing as it naturally discretizes the 2-dimensional Euclidean plane and finds applications in many real-life robotic systems. Particularly, we provide two deterministic algorithms on an anonymous grid graph that achieve simultaneously optimal bounds for both the metrics.