# \(k\)-Circle Formation and \(k\)-epf by Asynchronous Robots
## 1 Introduction
If the destination point is less than \(\delta\) distance away, the robot is guaranteed to reach its destination. The scheduler is assumed to be fair, i.e., each robot is activated infinitely often and performs its LCM cycle within finite time. The following types of schedulers are commonly used:  
1. Fully-synchronous (FSYNC): Robots have a common notion of time. All the robots are activated simultaneously and perform all operations synchronously. 2. Semi-synchronous (SSYNC): It coincides with the FSYNC scheduler with the only difference that not all the robots are activated in each round. 3. Asynchronous (ASYNC): Robots do not have a common notion of time. They are activated independently, and the duration of each LCM cycle and inactivity phase is finite but unbounded. We have considered a fair ASYNC scheduler. Due to the asynchrony, a robot might be in motion when some other robot is in its look phase. As a result, for an active robot, the perceived configuration in its look phase might be different from the configuration at the time when it actually starts moving. The theoretical motivation for studying the \(k\)-circle formation problem is twofold. First, we believe that the problem is theoretically interesting as it is a hybrid problem in between the partitioning problem [24] and the circle formation problem [16; 17; 18; 19; 20; 21]. Both the problems individually differs from the \(k\)-circle formation problem w.r.t. the following points:  
1. The partitioning problem asks the robots to divide themselves into \(m\) groups, each having \(k\) robots. In addition, the robots in each group are asked to converge into a small area. Unlike the \(k\)-circle formation problem, the robots do not need to form circles containing exactly \(k\) robots, centered at one of the pre-fixed points. 2. The circle formation problem asks the robots to place themselves at distinct locations on a circle (not defined a priori), within finite amount of time. In this problem, all the robots participate in forming one single circle, whereas, in the \(k\)-circle formation problem, the robots need to form \(m\) circles each containing exactly \(k\) robots and centered at one of the fixed points. To the best of our knowledge, we believe that this is the first work that aims at connecting the two well-known problems in the literature, namely the partitioning problem and the circle formation problem. Secondly, if the robots could solve the \(k\)_-circle formation_ problem, then all the \(k\) robots which lie on the same circle can gather at their respective center, which is a fixed point, within finite number of moves. Thus, studying the solvability of the \(k\)-circle formation problem includes investigating the solvability of a generalized version of the embedded pattern formation problem (referred to as \(k\)-epf problem in this paper), where \(k\) robots need to reach and remain at each fixed point. In addition, we believe that the \(k\)-circle formation problem would have the following applications in the field of swarm robotics:  
1. The set of fixed points can be considered as emergency points, which need to be surrounded. By solving the \(k\)-circle formation problem, a swarm of robots can divide themselves into groups, containing \(k\) robots and build a perimeter, surrounding the emergency points. 2. The set of fixed points can also be considered as charging stations, with some given permitted capacity. The robots need to be charged after a certain amount of time to continue working. By solving \(k\)-circle formation problem, the robots can reach the charging stations without violating the permitted capacity.