# \(k\)-Circle Formation and \(k\)-epf by Asynchronous Robots
## 4 Algorithm
### Moveto Destination
Since \(C(0)\) is asymmetric about the \(y\)-axis in this case, there exists at least one robot asymmetric robot position. The positive \(x\)-axis direction is considered towards the half-plane, which contains the asymmetric robot with the highest configuration rank. For any \(t^{\prime}>t\), either \(C(t^{\prime})=C(0)\) or it is guaranteed to have more progress in the positive side of the \(y\)-axis. Therefore, the agreement on the positive direction of the \(x\)-axis remains invariant. Hence, if the robots agree upon the positive direction of the \(x\)-axis by the execution of \(AgreementOneAxis(C(t))\), then at any arbitrary point of time \(t^{\prime}>t\) the agreement remains invariant. Next, we consider the balanced configurations in which the robots make an agreement on the positive direction of the \(x\)-axis at some \(t^{\prime}>0\). Lemma 1 ensures that the agreement remains invariant for any \(t^{\prime\prime}>t^{\prime}\). Note that, at any arbitrary point of time \(t\in[0,t^{\prime})\), the robots have selected two target fixed points, one from each of the half-planes. Since the scheduler is assumed to be asynchronous, it is possible to have a candidate robot on the negative side of the \(y\)-axis, selected at some \(t\in[0,t^{\prime})\) and which has not reached its destination point at \(t^{\prime}\). We need to ensure that there would not be any collision due to the inherent motion of such a candidate robot. **Lemma 2**. : _Let \(C(t^{\prime})\) for some \(t^{\prime}>0\), be the configuration in which the robots make an agreement on the positive direction of the \(x\)-axis. Let \(r_{i}\) be the candidate robot on the negative side of the \(y\)-axis, that was selected for some target fixed point \(f_{j}\) at \(t\in[0,t^{\prime})\). If \(t^{\prime\prime}\) is the point of time at which it re-computes its destination point, then it does not collide with any other candidate robots in the time interval \([t^{\prime},t^{\prime\prime}]\)._

Proof of Lemma 2.: Let \(f_{a}\) be the target fixed point at some \(t\in[t^{\prime},t^{\prime\prime}]\). Since the robots have agreement on the positive direction of the \(x\)-axis, a unique candidate robot would be selected by the execution of \(CandidateRSelection(C(t),f_{a})\). Let \(r_{b}\) be the candidate robot. Note that, \(f_{a}\geq f_{j}\), i.e., the configuration rank of \(f_{j}\) cannot be higher than \(f_{a}\). Otherwise, \(f_{j}\) would have been selected as the target fixed point. Consider the following cases:

**Case 1.**\(f_{a}=f_{j}\). In this case \(r_{a}=r_{i}\). This is because \(r_{i}\) is the candidate robot that was selected for \(f_{j}\) at \(t\in[0,t^{\prime})\) and has not reached \(C(f_{j},\rho)\). It would remain as the closest robot position from \(f_{j}\), that does not lie on a saturated circle. Since \(r_{i}\) would be the unique robot which is in motion within \(d(f_{j},r_{i})\) distance from \(f_{j}\), there would not be any collision of robots. **Case 2. ** So we assume that \(f_{j}\
eq f_{a}\). The movement paths of \(r_{i}\) and \(r_{b}\) would not intersect. Otherwise, by triangle inequality \(r_{i}\) would have been at closer distance from \(f_{a}\). So \(r_{i}\) would have selected as the candidate robot for \(f_{a}\) by the execution \(CandidateRSelection(C(t),f_{a})\). Since the movement paths do not intersect, \(r_{i}\) would not collide with \(r_{b}\) during the time interval \([t^{\prime},t^{\prime\prime}]\). Since the scheduler is assumed to be asynchronous, it is possible that \(r_{i}\) becomes the candidate robot for \(f_{a}\) as in Figure 8. As the movement paths do not intersect, \(r_{i}\) would continue its movement towards \(C(f_{j},\rho)\) without collision unless it stops and re-computes its destination point. If it stops it will execute \(MovetoDestination(C(t),f_{a},r_{i})\). It computes its movement path towards \(C(f_{a},\rho)\) that does not intersect with the movement path of \(r_{b}\). As a result, it would continue its movement towards \(C(f_{a},\rho)\) in subsequent time without any collision with \(r_{b}\).