K Circle Formation by Swarm Robots on a Grid

Abstract

For a given positive integer k, the k-circle formation problem asks a set of distributed autonomous, identical, oblivious, asynchronous robots to form disjoint circles having k robots each at distinct locations. The robots are identical, anonymous, oblivious, and they operate in Look–Compute–Move cycles. This work studies the k-circle formation problem on a 2D grid where a circle is defined using the Bresenham’s circle drawing algorithm. The correctness of the proposed deterministic distributed algorithm is proved. Simulation result is also presented.