Circle formation by asynchronous opaque robots on infinite grid

Ranendu Adhikary, Manash Kumar Kundu, Buddhadeb Sau


This paper presents a distributed algorithm for circle formation problem under the infinite grid environment by asynchronous mobile opaque robots. Initially all the robots are acquiring distinct positions and they have to form a circle over the grid. Movements of the robots are restricted only along the grid lines. They do not share any global co-ordinate system. Robots are controlled by an asynchronous adversarial scheduler that operates in Look-Compute-Move cycles. The robots are indistinguishable by their nature, do not have any memory of their past configurations and previous actions. We consider the problem under luminous model, where robots communicate via lights, other than that they do not have any external communication system. Our protocol solves theĀ  circle formation problem using seven colors. A subroutine of our algorithm also solves the line formation problem using three colors.


Distributed computing, Autonomous robots, Circle formation, Line formation, Robots with lights, Asynchronous, Look-Compute-Move cycle, Grid

Full Text: