Multiple Uniform Circle Formation by Fat Robots Under Limited Visibility

摘要

Formation of arbitrary shapes and patterns using swarm robots is a fairly well researched topic. However, there is still a long way to go. This is due to the hindrance caused by the immense complexity of distributed algorithms and their lack of scalability. This paper proposes a scalable algorithm that allows a set of identical, homogeneous, disk shaped fat mobile robots to form multiple uniform circles. All the robots run the same proposed (completely distributed and deterministic) algorithm. The robots follow a global coordinate system. All the points that the robots must occupy are pre-computed by them. The robots in this paper are not oblivious, and use a message passing technique to prevent collisions. The robots have the same limited visibility, within which they can observe other robots. Based on one’s current position and position of other robots in its visibility, a robot takes appropriate decisions so that the objective can be fulfilled. The algorithm guarantees formation of multiple uniform circles under a synchronous environment. At the end of the paper, we also discuss why this algorithm is independent of the shape the robots have to form, and can be extended to the formation of any arbitrary geometric shape by just changing the computation of the points that the robots eventually occupy.