## 2 Preliminary Information
### Assumptions and Notations  
Using the notations in graph theory [27], a weighted directed graph \(G\) is a set \(G=(V(G),E(G))\), in which \(V(G)\) is the node set and \(E(G)\) is the directed edge set. The weight of every directed edge, say \(e\in E(G)\), is \(w(e):e\to Z^{+}\). A _directed path_ is a sequence of directed edges. Suppose that we have \(S\) surface ships in total. Let \(p^{s}\) denote the \(s\)-th surface ship where \(s\in\{1,2,\ldots,S\}\). Each surface ship \(p^{s}\) carries \(N^{s}\) robots in total. As a ship arrives at the sea surface of the workspace, it begins dropping robots while not moving at the site. Let \(n_{1}^{s}\) denote the \(i\)-th robot dropped by \(p^{s}\). Since \(p^{s}\) carries \(N^{s}\) robots, we have \(i\in\{1,2,\ldots,N^{s}\}\). The ship \(p^{s}\) drops robots in the following order : \(n_{1}^{s}\to n_{2}^{s}\cdot\cdots\to n_{N^{s}}^{s}\). Suppose that each robot has both Ultra-Short BaseLine acoustic positioning (USBL) and depth sensors. USBL sensors can be used to derive both the range and the azimuth of a signal source. USBL sensors can also be used for mutual communication, i.e., a transmitter can send data to a receiver. Each USBL sensor can work as a transmitter as well as a receiver. For instance, one can access the information on commercial USBL sensors in the following website: [[https://www.ixblue.com/products/usbl-positionning-system](https://www.ixblue.com/products/usbl-positionning-system)]([https://www.ixblue.com/products/usbl-positionning-system](https://www.ixblue.com/products/usbl-positionning-system)) (accessed on 10 May 2021). Let \(r_{i}^{d}\) represent the detection (sensing) range of \(n_{i}^{s}\). Also, let \(r_{i}^{c}\) represent the communication range of \(n_{i}^{s}\). Let _detect-communicate range_\(r_{i}^{dc}\) be defined as  
\[r_{i}^{dc}=min(r_{i}^{d},r_{i}^{c}). \tag{1}\]  
Let \(Sphere^{dc}\) of a robot \(n_{i}^{s}\) define a sphere with radius \(r_{i}^{dc}\), whose center is located at \(n_{i}^{s}\). Let \(Boundary^{dc}\) of a robot indicate the boundary of the \(Sphere^{dc}\) of the robot. Let \(\mathbf{n}_{i}^{s}\) denote the 3D coordinates of \(n_{i}^{s}\) where \(i\in\{1,2,\ldots,N^{s}\}\). If \(\|\mathbf{n}_{i}^{s}-\mathbf{n}_{j}^{s}\|<r_{i}^{dc}\), then \(n_{i}^{s}\) can sense \(n_{i}^{s}\). Also, \(n_{i}^{s}\) can send a communication signal to \(n_{j}^{s}\). On the \(Boundary^{dc}\) of a robot \(n_{i}^{s}\), \(Q\) points are evenly generated. These points represent the points where the sensing ray of \(n_{i}^{s}\) can reach. As an example, we discuss generating \(Q=18*18\) points on a \(Boundary^{dc}\) of a robot. (This generation method is utilized in Section 4.) Let us rotate one vector \([r_{i}^{dc},0,0]^{T}\) by \(\phi\in[\pi/9,2*\pi/9,3*\pi/9\ldots,2\pi]\) about the \(z\)-axis. The matrix presenting the rotation is  
\[\mathbf{R}(\psi)=\left( \begin{array}{ccc}c(\psi)&-s(\psi)&0\\ s(\psi)&c(\psi)&0\\ 0&0&1\end{array} \right). \tag{2}\]  
Thereafter, we rotate \(\mathbf{R}(\theta)[r_{i}^{dc},0,0]^{T}\) by \(\theta\in[\pi/9,2*\pi/9,3*\pi/9,\ldots,2\pi]\) about the \(y\)-axis. The matrix presenting the rotation is  
\[\mathbf{R}(\theta)=\left( \begin{array}{ccc}c(\theta)&0&s(\theta)\\ 0&1&0\\ -s(\theta)&0&c(\theta)\end{array} \right). \tag{3}\]  
The resulting vector after two rotations is  
\[\mathbf{fp}(\psi,\theta)=\mathbf{R}(\psi)\mathbf{R}(\theta)[r_{i}^{dc},0,0]^{ T}. \tag{4}\]  
The vector \(\mathbf{fp}(\psi,\theta)\) represents the relative position of a point on the \(Boundary^{dc}\) of \(n_{i}^{s}\), with respect to \(\mathbf{n}_{i}^{s}\). As we add \(\mathbf{n}_{i}^{s}\) to \(\mathbf{fp}(\psi,\theta)\), we obtain the 3D coordinates of a point on the \(Boundary^{dc}\) of \(n_{i}^{s}\). Note that \(\psi\) and \(\theta\) are chosen from 18 values, respectively. Therefore, \(Q=18*18\) points are derived on \(Boundary^{dc}\) of \(n_{i}^{s}\). Let \(L(\mathbf{n},\mathbf{m})\) denote a straight line segment connecting two robots \(\mathbf{n}\) and \(\mathbf{m}\).