# Three-Dimensional Formation Control for Robot Swarms
## 4 Formation Controls
### Formation Controls for Expanding the Network
At the instant when \(u_{i}\) arrives at an AR, say \(A\), in \(P\), \(u_{i}\) detects the relative coordinates of the next AR in \(P\). See Assumption (A1). As \(u_{i}\) arrives at \(u_{s}\) (the last AR in \(P\)), \(u_{i}\) is able to maneuver toward \(f_{u_{i}}\) under Assumption (A2). After \(u_{i}\) arrives at \(f_{u_{i}}\), \(u_{i}\) switches on its proximity sensor to sense its close space. See _EnableSensor_ function (Algorithm 2). Once \(u_{i}\) switches on its proximity sensor, frontierPts inside the senseSphere of \(u_{i}\) disappear. This disappearance is achieved through the local sensing of \(u_{i}\). Consider the case in which a point in \(f(m)\) is in the senseSphere of \(u_{i}\). The distance between \(m\) and a point in \(f(m)\) is shorter than \(r_{sc}\). Thus, \(m\) is a closeAR of \(u_{i}\). \(u_{i}\) is able to sense the relative coordinates of \(m\) under Assumption (A1). Consider the case where \(u_{i}\) measures the relative coordinates of its closeAR \(m\). The vector from \(u_{i}\) to a point in \(f(m)\) is the addition of the following two vectors, which are accessible using Assumptions (A1) and (A2):  
1. The vector from \(m\) to the point in \(f(m)\). 2. The vector from \(u_{i}\) to \(m\). At the moment when \(u_{i}\) switches on its proximity sensor, all frontierPts in the senseSphere of \(u_{i}\) disappear. Then, \(u_{i}\) broadcasts the disappearance of the frontierPts to all ARs through multi-hop communication. \(u_{i-1}\) then searches for its frontierPt \(f_{u_{i-1}}\), and maneuvers toward the found frontierPt. This repeats until \(i\) becomes 1 or no frontierPt is detected utilizing the distributed BFS. Once \(i\) decreases to 1, then one has no remaining ARs for covering a remaining frontierPt. There may be a case in which the networked ARs entirely cover the user-specified 3D shape, but we want to add more ARs into the 3D shape. In this case, we apply distributed rendezvous controls in Section 4.2, while not moving the leader. Based on distributed rendezvous controls, the network begins clustering toward the leader. After the network begins clustering, coverage holes are newly formed in the 3D shape. Additional ARs are further located until they cover the holes in the shape entirely. Covering the sensing holes in the 3D shape is further handled in Section 5. Analysis  
We analyze the computational complexity of Algorithm 1. \(u_{i}\) finds an AR with a frontierPt, which has the smallest hop distance from \(u_{i}\). This search can be performed through distributed BFS, whose computational complexity is \(O(1)\)[32; 33]. Since \(i\) decreases from \(N\) to 1 in the worst case, the computational complexity of the loop in Algorithm 1 is \(O(N)\). As \(Q\) increases to infinity, frontierPts on a senseSphere become the frontierInfty. Theorem 1 proves that if an AR cannot find a frontierInfty, then the entire space inside the user-specified shape is covered by coverSpheres. Theorem 1: _If an AR cannot find a frontierInfty, then the entire space inside the user-specified shape is covered by coverSpheres._Proof. : Under the transposition rule of propositional logic, the following statement is proved: if one has an uncovered space inside the user-specified shape, then an AR is able to find a frontierInfty. Suppose that one has an uncovered space in the user-specified shape. Let \(O\) present this uncovered space. Using the definition of a frontierInfty, at least one AR can find a frontierInfty on the boundary of \(O\). Therefore, an AR is able to find this frontierInfty. If \(Q\) is not so large, then frontierPts may represent a frontierInfty coarsely. Therefore, Theorem 1 may not always hold. In Algorithm 1, an AR \(u_{i}\) maneuvers along a path, say \(P\), until reaching \(f_{u_{i}}\). Theorem 2 implies that \(u_{i}\) applies local communication only for its maneuver. In addition, network connection is assured during the maneuver. Theorem 2 further proves that as \(u_{i}\) arrives at \(f_{u_{i}}\), we are able to locate \(u_{i}\) in global coordinates. **Theorem 2**.