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.
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.
A swarm of robots is a collection of tiny identical autonomous robots. The robots perform a given task, e.g., cleaning a big surface, moving a big object, guarding an area etc., in a collaborative framework. The goal of research in swarm robotics is to develop a low cost multi-robot system which will be at least as efficient as one big expensive unit. The field of swarm robotics has been addressed from various aspects such as artificial intelligence, mechanical and electrical engineering, motion control, robots' path planning etc. From theoretical point of view, designing deterministic algorithms for these robots to execute a particular job is an emerging and useful field of research. As the robots work individually but in collaboration, distributed algorithms are more appropriate than centralized ones. This chapter discusses the distributed framework for swarm robots and presents some reported research results as well as a few open problems.