Dispersion of Mobile Robots on Triangular Grid

Abstract

The utilization of mobile robots to solve global problems in a distributed manneris an intriguing and novel approach to problem solving. In this paradigm, eachrobot operates independently while collaborating with other robots to achieve agoal that would be impossible to achieve using a centralised global approach.This method can be used to simulate a variety of real-world problems, such astoxic hazard cleanup, large-scale maze exploration, and collective gathering in asingle location.The Dispersion problem on a Triangular Grid with a particular set of configurationsis introduced in this thesis. We present a five-Round algorithm that cansolve the problem in O(max(HG,WG)) time rounds, using only O(log k) bits forthe mobile robots, where HG is height of grid, WG is width of grid and k is numberof the mobile robots. Our solution provides an optimal solution in terms ofboth time and memory complexity for Dispersion on a given configuration of atriangular grid.