## 2 Preliminary Information
### Assumptions and Notations
We say that \(L(\mathbf{n},\mathbf{m})\) is _safe_ once it does not intersect an obstacle. This implies that a robot avoids colliding with an obstacle, as it travels along \(L(\mathbf{n},\mathbf{m})\). A _freePoint_ of \(n_{i}^{s}\) denotes a point among \(Q\) points of \(n_{i}^{s}\), such that a straight line segment connecting \(n_{i}^{s}\) and the point does not intersect obstacles. In practice, freePoints can be detected by active sonar sensors. A robot has active sonars, which can detect an obstacle close to the robot [28]. The authors of [28] considered the case where the active sonars are positioned, so that the viewing angle of the sonars is 200 degrees. In our paper, we need to install active sonars surrounding the robot. In this way, the sonars can cover the space surrounding the robot. As a sonar ray does not meet an obstacle, the ray is associated to a freePoint of the robot. A _frontierPoint_\(f(n_{i}^{s})\) of a robot \(n_{i}^{s}\) denotes a freePoint of \(n_{i}^{s}\), which is outside the \(Sphere^{dc}\) of any other robot. As \(Q\rightarrow\infty\), one obtains dense frontierPoints on a \(Boundary^{dc}\). Let _frontierSurface_ denote the set of frontierPoints as \(Q\rightarrow\infty\). A frontierSurface is on the border between a space covered by all \(Sphere^{dc}\)s and a space covered by no \(Sphere^{dc}\). If every robot has no frontierSurface, then all robots' \(Sphere^{dc}\)s cover the open space completely. Recall that \(n_{i}^{s}\) denotes the \(i\)-th robot which is dropped by the ship \(p^{s}\) (\(s\in\{1,2,\ldots,S\}\)). Each robot \(n_{i}^{s}\) stores and expands the _traversible graph_, say \(I^{s}=(V(I^{s}),E(I^{s}))\). Each vertex in \(V(I^{s})\) indicates a deployed robot. Every directed edge, say \(\{n_{i}^{s},n_{j}^{s}\}\in E(I^{s})\), is established as the following conditions are met:\(L(\mathbf{n}_{i}^{s},\mathbf{n}_{j}^{s})\) is safe. 2. \(\|\mathbf{n}_{i}^{s}-\mathbf{n}_{j}^{s}\|\leq r_{i}^{dc}\). Using the above definition, \(\{n_{i}^{s},n_{j}^{s}\}\in E(I^{s})\) implies that \(n_{i}^{s}\) can detect \(n_{j}^{s}\). Also, \(n_{i}^{s}\) can send a communication signal to \(n_{j}^{s}\). \(\|\mathbf{n}_{i}^{s}-\mathbf{n}_{j}^{s}\|\) is accessible using USBL sensors. Suppose that a new robot, say \(n_{i}^{s}\), is deployed in \(I^{s}\), so that this new robot and a robot, say \(n_{j}^{s^{\prime}}\), in \(I^{s^{\prime}}\) (\(s^{\prime}\
eq s\)) satisfy the following two conditions for establishing a directed edge. 1. \(L(\mathbf{n}_{i}^{s},\mathbf{n}_{j}^{s^{\prime}})\) is safe. 2. \(\|\mathbf{n}_{i}^{s}-\mathbf{n}_{j}^{s^{\prime}}\|\leq r_{i}^{dc}\). In this case, a new directed edge is established from \(n_{i}^{s}\) to \(n_{j}^{s^{\prime}}\). Then, \(I^{s}\) and \(I^{s^{\prime}}\) merge to generate the bigger graph \(I^{s}\bigcup I^{s^{\prime}}\). In this way, \(I^{s}\) can expand to contain a robot \(n_{j}^{s^{\prime}}\) which is dropped by a ship \(p^{s^{\prime}}\) where \(s^{\prime}\
eq s\). In the case where \(I^{s}\) is not connected to \(I^{s^{\prime}}\) (\(s^{\prime}\
eq s\)), \(I^{s}\) and \(I^{s}\) expand independently to each other. Once \(I^{s}\) is connected to \(I^{s^{\prime}}\), they merge to generate the bigger graph \(I^{s}\bigcup I^{s^{\prime}}\). Utilizing the notation of \(E(I^{s})\), \(n_{i}^{s}\) avoids collision while traversing an edge in \(E(I^{s})\). This implies that \(I^{s}\) is a safe topological map for \(n_{i}^{s}\). The weight of every directed edge, say \(e\in E(I^{s})\), is \(w(e)\). \(\|\mathbf{n}_{i}^{s}-\mathbf{n}_{j}^{s}\|\) is accessible using USBL sensors and is set as \(w(\{n_{i}^{s},n_{j}^{s}\})\). The weight of every edge in \(I^{s}\) is used to let \(n_{i}^{s}\) find the path in \(I^{s}\). We say that two robots \(n_{i}^{s}\) and \(n_{j}^{s}\) are _neighbors_ in the case where \(\|\mathbf{n}_{i}^{s}-\mathbf{n}_{j}^{s}\|<r_{i}^{dc}+r_{j}^{dc}\). Let \(\mathcal{N}(n_{i}^{s})\) denote a neighbor of \(n_{i}^{s}\). We assume that a ship dropping robots can localize itself using GPS. In summary, every robot satisfies the below assumptions:  
1.