# \(k\)-Circle Formation and \(k\)-epf by Asynchronous Robots
## 1 Introduction  
A swarm of robots is a multi-robot system consisting of small and inexpensive mobile robots working together in a cooperative environment to achieve some specific goal. A swarm of robots has the potential to be utilized in risky and hazardous scenarios, such as in the fields of search and rescue operations, military operations, fire fighting, etc. Robots are autonomous, anonymous, homogeneous, and oblivious. A robot is modeled as a geometric point in the plane. The robots do not have any agreement on a global coordinate system. Each robot has its own local coordinate system. They do not have any explicit means of communication. When a robot becomes active, it operates in Look-Compute-Move (LCM) cycles. The study of such a distributed system of mobile robots aims at finding a minimal set of capabilities in order to solve a given problem. Some of the well-known co-ordination problems studied in this area of research work are gathering and convergence [1, 2, 3, 4, 5, 6, 7, 8, 9], arbitrary pattern formation [10, 11, 12, 13], embedded pattern formation [14, 15], circle formation [16, 17, 18, 19, 20, 21] etc. The embedded pattern formation [14, 15] asks the robots to form a given pattern, in which the points comprising the pattern are assumed to be pre-fixed and visible to all the robots like landmarks. [PERSON] et al. [22] studied the gathering on meeting points problem where the robots need to gather at one of the pre-determined points in the plane, referred to as meeting points. In the discrete domain, [PERSON] et al. [23] studied the gathering over meeting nodes problem in an infinite grid, where some of the nodes of the grid have been considered as meeting nodes. In this paper, we have considered \(m>0\) fixed points in the Euclidean plane. For a given positive integer \(k\), we consider \(n\) mobile robots such that \(n=\text{km}\). The \(k\)-circleformation problem is defined as follows: the \(n\) mobile robots need to form \(m\) circles, each centered at one of the fixed points, such that each circle contains exactly \(k\) robots at distinct positions. The circles formed by the robots must be disjoint, i.e., no robot is allowed to lie on any two distinct circles. Note that the circles do not require to be necessarily uniform. In other words the \(k\) robots forming one particular circle have identical distance from a particular fixed point, but their mutual distances can be anything. In general, one may consider different radii for the circles. In this paper, we consider all the circles to have the same radius, which is a special case of the \(k\)-circle formation problem. We have considered a swarm of mobile robots, which are represented as points in the Euclidean plane. The robots are silent, i.e., they do not have any explicit direct way of communication. They coordinate their movements by perceiving the positions of other robots. The robots are assumed to have unlimited visibility, i.e., the robots can observe the entire plane. We assume that initially all the robots are placed at distinct locations in the plane. Robots are assumed to be:  
* Autonomous, i.e., they do not have any centralized controller;
* Anonymous, i.e., they have no unique identifier;
* Oblivious, i.e., they do not remember anything about the past events;
* Homogeneous, i.e., they execute the same deterministic algorithm. The robots operate in Look-Compute-Move (LCM) cycles. In the look phase, the robot senses the current configuration in its own local coordinate system. In the compute phase, a destination point is computed by the robot. The destination point may be the robot's current location. In the move phase, the robot moves towards the destination point. A robot cannot distinguish between a static robot and a moving robot, in its look phase. The robots have non-rigid motion, i.e., there exists a fixed but unknown \(\delta>0\) such that if the destination is more than \(\delta\) distance away from a robot, the robot moves at least \(\delta\) amount towards its destination.