Optimizing Robot Dispersion on Unoriented Grids: With and Without Fault Tolerance
摘要
The introduction and study of dispersing mobile robots across the nodes of an anonymous graph have recently gained traction and have been explored within various graph classes and settings. While optimal dispersion solution was established for oriented grids [Kshemkalyani et al., WALCOM 2020], a significant unresolved question pertains to whether achieving optimal dispersion is feasible on an unoriented grid. This paper investigates the dispersion problem on unoriented grids, considering both non-faulty and faulty robots. The challenge posed by unoriented grids lies in the absence of a clear sense of direction for a single robot moving between nodes, as opposed to the straightforward navigation of oriented grids. We present two deterministic algorithms tailored to our robot model. The first algorithm addresses non-faulty robots, ensuring both time and memory optimality, achieving dispersion in \(O(\sqrt{n})\) rounds while requiring \(O(\log n)\) bits of memory per robot. The second algorithm tackles faulty robots, which are prone to crashing at any time, causing permanent failure. In this scenario, our algorithm operates within \(O(\sqrt{n} \log n)\) time and uses \(O(\sqrt{n} \log n)\) bits of memory per robot. The robots need to know the value of n for termination.