# \(k\)-Circle Formation and \(k\)-epf by Asynchronous Robots
## 4 Algorithm
### Moveto Destination
If \(q\) is not a robot position, then \(r_{i}\) selects \(q(t)=q\) and \(P=\overline{r_{i}(t)q}\) (Figure 7a). Next, consider the case when \(q\) is a robot position and \(C(f_{j},\rho)\) does not contain any robot positions other than being collinear with \(r_{i}\) and \(f_{j}\). Let \(B_{1}\) be the ray starting from \(r_{i}(t)\) such that \(\measuredangle\overline{r_{i}(t)q}r_{i}(t)B_{1}=\frac{\pi}{4}\) (Figure 7b). Suppose \(B_{1}\) intersects \(C(f_{j},\rho)\) at \(q_{1}\). The candidate robot \(r_{i}\) selects \(q(t)=q_{1}\) and \(P=\overline{r_{i}(t)q_{1}}\). Otherwise, let \(r_{u}\) (not collinear with \(r_{i}\) and \(f_{j}\)) be the robot position on \(C(f_{j},\rho)\) such that \(\measuredangle\overline{r_{i}(t)q}r_{i}(t)\overline{r_{i}(t)r_{u}(t)}\) is the smallest. Let \(B_{2}\) be the ray starting from \(r_{i}(t)\) such that \(\measuredangle\overline{r_{i}(t)q}r_{i}(t)B_{2}=\frac{1}{2}min(\frac{\pi}{2}, \measuredangle\overline{r_{i}(t)q}r_{i}(t)\overline{r_{i}(t)r_{u}(t)})\). Suppose \(q_{2}\) is the intersection point between \(B_{2}\) and \(C(f_{j},\rho)\). The candidate robot selects \(q(t)=q_{2}\) and \(P=\overline{r_{i}(t)q_{2}}\) (Figure 7c). Figure 3: (**a**) \(P=\overline{r_{i}(t)p(t)}\) and \(q(t)=p(t)\). (**b**) \(r_{\mathrm{e}}(t)\) is the robot position on \(p(t)\). \(q(t)=q\) and \(P=\overline{r_{i}(t)q}\), where \(q\) is the point of intersection between \(t^{\mathrm{a}}\) and \(C(f_{j},\rho)\). fixed point lies on the \(y\)-axis. A candidate robot will consider the tangent line and robot positions, which lie in its half-plane, while computing its destination point and movement path. ### Algorithm One Axis

This is the proposed algorithm that solves the \(k\)-circle formation problem with one axis agreement. The pseudocode is given in Algorithm 2. Given a configuration \(C(t)\), each active robot executes \(AlgorithmOneAxis(C(t))\). During an execution of \(AlgorithmOneAxis(C(t))\), if \(C(t)\) is not a final configuration, then an active robot (say \(r_{k}\)) executes algorithm \(AgreementOneAxis(C(t))\). Next, \(r_{k}\) considers the following cases:
```
Input:\(C(t)=(R(t),F)\)
1 Let \(r_{k}\) be an active robot at time \(t\);
2\(r_{k}\) executes \(AgreementOneAxis(C(t))\);
3 if the robots have an agreement on the positive direction of the \(x\)-axisthen
4\(r_{k}\) executes \(TargetFPSelection(C(t))\);
5 Let \(f_{j}\) be the target fixed point;
6\(r_{k}\) executes \(CandidateSelection(C(t),f_{j})\);
7 Let \(r_{k}\) be the candidate robot;
8 if\(r_{k}=r_{l}\)then
9\(r_{k}\) executes \(MovetoDestination(C(t),f_{j},r_{k})\);
10
11 end if
12
13 ifall the fixed points in \(F\setminus F_{j}\) are saturatedthen
14\(r_{k}\) executes \(TargetFPSelection(C(t))\);
15 Let \(f_{j}\) be the target fixed point;
16\(r_{k}\) executes \(CandidateSelection(C(t),f_{j})\);
17 ifthere is a unique candidate robotthen
18 Let \(r_{i}\) be the candidate robot;
19 if\(r_{k}=r_{i}\)then
20\(r_{k}\) executes \(MovetoDestination(C(t),f_{j},r_{k})\);
21
22 end if
23
24 else
25 Let \(r_{i}\) be the candidate robot such that \(r_{k}\) and \(r_{i}\) lie in the same half-plane;
26 if\(r_{k}=r_{i}\)then
27\(r_{k}\) executes \(MovetoDestination(C(t),f_{j},r_{k})\);
28
29 end if
30
31 end if
32
33 end if
34
35
```

**Algorithm 2**Algorithm \(AlgorithmOneAxis\)

The robots have an agreement on the positive direction of the \(x\)-axis. Robot \(r_{k}\) executes \(TargetFPSelection(C(t))\). In this case there is a unique target fixed point. Let \(f_{j}\) be the target fixed point. Next, \(r_{k}\) identifies the candidate robot by executing \(CandidateRSelection(C(t),f_{j})\). Let \(r_{i}\) be the candidate robot selected for \(f_{j}\). If \(r_{k}=r_{i}\), then it executes \(MovetoDestination(C(t),f_{j},r_{i})\). The robots do not have any agreement on the positive direction of the \(x\)-axis. Robot \(r_{k}\) considers the following cases:

1. All the fixed points in \(F\setminus F_{j}\) are saturated. Robot \(r_{k}\) executes \(TargetFPSelection(C(t))\). In this case the unique target fixed point lies on the \(y\)-axis.