# Three-Dimensional Formation Control for Robot Swarms
## 4 Formation Controls
### Formation Controls for Expanding the Network  
Once all ARs rendezvous at the leader, then every AR is controlled one at a time, such that as more ARs arrive at their assigned positions, an uncovered space in the user-specified 3D shape reduces incrementally. The proposed formation controls (Algorithm 1) work by sequentially locating ARs one by one, until the network fills the user-specified 3D shape. Algorithm 1 is explained as follows. Once the rendezvous is finished, a tree \(T\) is formed in a distributed fashion. For generating \(T\), every AR \(u_{i}\) stops maneuvering, while utilizing its proximity sensor for measuring the relative coordinates of its neighbors. The distributed BFS algorithm in Section 4.1 is applied for the distributed generation of \(T\). Initially, the leader \(u_{1}\) switches on its proximity sensor for covering the space close to \(u_{1}\). \(u_{1}\) localizes its global position utilizing Assumption (A4). Thereafter, frontierPts of \(u_{1}\) are built. Suppose an AR arrives at its assigned position. Thereafter, the AR switches on its proximity sensor for covering its surroundings. For generating a connected network, an AR maneuvers into an uncovered space within \(r_{sc}\) distance units. As an AR arrives at its assigned position, the AR switches on its proximity sensor with range \(r_{sc}\). See _EnableSensor_ function (Algorithm 2). ```
1:Initially, every AR will rendezvous at the leader under distributed rendezvous control in Section 4.2;
2:\(S=[u_{1},u_{2},\ldots,u_{N}]\);
3:The leader \(u_{1}\) switches on its proximity sensor with range \(r_{sc}\) and builds a frontierPt inside the user-specified 3D shape;
4:\(i=N\);
5:repeat
6:By applying the distributed BFS in Section 4.1, \(u_{i}\) finds an AR with a frontierPt, which has the smallest hop distance from \(u_{i}\);
7:if no frontierPt is detected by running the distributed BFS then
8: This algorithm is finished;
9:endif
10: Let \(u_{f}\) present the found AR;
11: A frontierPt on the senseSphere of \(u_{f}\) is set as \(f_{u_{i}}\);
12: The AR \(u_{i}\) maneuvers along the path to \(u_{f}\), then tracks the edge from \(u_{f}\) to \(f_{u_{i}}\);
13:if The AR \(u_{i}\) arrives at its assigned position \(f_{u_{i}}\)then
14: EnableSensor(\(u_{i}\),\(u_{f}\));
15:endif
16:\(i=i-1\);
17:until the index \(i\) becomes \(1\)
```  
**Algorithm 1** Formation controls  
In Algorithm 1, every AR is controlled one at a time with the following order: \(u_{N}\to u_{N-1},\ldots\to u_{2}\). The AR \(u_{N}\) maneuvers to arrive at its frontierPt \(f_{u_{N}}\). Thereafter, \(u_{N}\) switches on its proximity sensor for covering its close space. FrontierPts of \(u_{N}\) are built accordingly. See Algorithm 2. Once \(u_{N}\) arrives at its assigned position, \(u_{N-1}\) maneuvers until reaching its frontierPt \(f_{u_{N-1}}\). Keep iterating this procedure until all ARs arrive at their assigned positions. Consider the case in which \(u_{i+1}\) just turned on its proximity sensor for covering its close space. Thereafter, \(u_{i}\) finds an AR, say \(u_{s}\), with a frontierPt, which has the smallest hop distance from \(u_{i}\). The distributed BFS in Section 4.1 is applied for this search. Thereafter, the frontierPt on the senseSphere of the found AR is set as \(f_{u_{i}}\). An AR \(u_{i}\) maneuvers along a path, say \(P\), in the spanning tree \(T\) until reaching its frontierPt \(f_{u_{i}}\). Considering the definition of the neighbor, the length of each line segment along this path is shorter than \(r_{sc}\). In addition, the path is collision-free, since no obstacle hinders the path. In this way, the proposed control considers obstacle avoidance of each AR. At the instant when \(u_{i}\) arrives at an AR in \(P\), \(u_{i}\) maneuvers toward the next AR in \(P\), since an AR can sense its neighbor in \(P\). (8) addresses how to make \(u_{i}\) maneuver toward an AR in \(P\) utilizing local sensing measurements. In order to track along the path \(P\), \(u_{i}\) measures an AR in \(P\) using its local sensor.