Circle formation by asynchronous opaque robots on infinite grid

Abstract

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