## 3 Coverage Methods Utilizing Multiple Heterogeneous Robots
The time complexity of the directed breadth-first search is \(O(\|E(l^{s})\|)\), since every edge will be explored in the worst case. One frontierPoint on \(m\) is then chosen as \(f_{n_{i}^{s}}\). Based on the directed breadth-first search, \(n_{i}^{s}\) travels along a directed path, say \(P\), in \(l^{s}\) to arrive at \(m\). Recalling the notation of \(l^{s}\), \(P\) is a safe path for \(n_{i}^{s}\). Furthermore, the length of every straight line segment of \(P\) is shorter than \(r_{i}^{dc}\). As \(n_{i}^{s}\) arrives at a robot in the path \(P\), \(n_{i}^{s}\) can move towards the next robot in the path \(P\) under Assumption (A1). GPS is not required for this local maneuver. In order to traverse the path \(P\), \(n_{i}^{s}\) utilizes local interaction with a robot in \(P\). As \(n_{i}^{s}\) arrives at a robot, say \(n_{i}^{s}\), in \(P\), \(n_{i}^{s}\) lets \(n_{i}^{s}\) access the next robot in \(P\). This information sharing is possible under Assumption (A1). As \(n_{i}^{s}\) arrives at the last robot in the path \(P\), \(n_{i}^{s}\) can move towards \(f_{n_{i}^{s}}\) under Assumption (A3). After \(n_{i}^{s}\) arrives at \(f_{n_{i}^{s}}\), \(n_{i}^{s}\) activates its local sonar sensors to sense its surroundings. Once \(n_{i}^{s}\) activates its local sonar sensors, several frontierPoints inside the \(Sphere^{dc}\) of \(n_{i}^{s}\) are deleted. This deletion is possible based on local interaction of \(n_{i}^{s}\). We explain the deletion process in detail. Suppose that a point in \(f(n_{i}^{s})\) is inside the \(Sphere^{dc}\) of \(n_{i}^{s}\). Since the relative distance between \(n_{j}^{s}\) and a point in \(f(n_{j}^{s})\) is \(r_{j}^{dc}\), \(n_{j}^{s}\) is a neighbor to \(n_{i}^{s}\). Under Assumption (A1), \(n_{i}^{s}\) calculates the relative location of \(n_{j}^{s}\). Suppose that \(n_{i}^{s}\) calculates the relative location of \(n_{j}^{s}\). The relative vector from \(n_{i}^{s}\) to a point in \(f(n_{j}^{s})\) is derived by adding the below two vectors, which are available based on Assumptions (A1) and (A3):  
1. the vector from \(n_{j}^{s}\) to the point in \(f(n_{j}^{s})\). 2. the vector from \(n_{i}^{s}\) to \(n_{j}^{s}\). As \(n_{i}^{s}\) activates its local sonar sensors, several frontierPoints inside the \(Sphere^{dc}\) of \(n_{i}^{s}\) are deleted. Recall that \(5*\|\mathcal{N}(n_{i}^{s})\|\) communication pings are required to calculate the relative location of a frontierPoint in \(f(n_{i}^{s})\). Then, \(n_{i}^{s}\) broadcasts the deletion of frontierPoints to every other robot which can communicate with \(n_{i}^{s}\) using multi-hop communication. Here, multi-hop communication is feasible using USBL of each robot. This broadcast of \(n_{i}^{s}\) requires \(\|V(I^{s})\|\) communication pings, since there are \(\|V(I^{s})\|\) nodes in \(I^{s}\). Using Algorithm 1, \(\|V(I^{s})\|\) increases from 1 to \(\sum_{s=1}^{S}N^{s}\). Therefore, the number of broadcast pings is \(1+2+\cdots+\sum_{s=1}^{S}N^{s}\). Also, \(n_{i}^{s}\) transmits a signal to the ship via multi-hop communication using USBL, so that the ship can deploy the next robot \(n_{i+1}^{s}\). \(n_{i+1}^{s}\) finds the nearest frontierPoint. Then, \(n_{i+1}^{s}\) travels along \(I^{s}\) until arriving at the frontierPoint. This repeats until \(i==N^{s}\) in Algorithm 1. Figure 1 illustrates the case where \(n_{i}^{s}\) heads towards \(f_{n_{i}^{s}}\). In this figure, \(n_{i}^{s}\) is illustrated as a sphere. \(n_{i}^{s}\) travels along a narrow passage in Figure 1. Red curves indicate the obstacle boundaries, and the path of \(n_{i}^{s}\) is illustrated with yellow line segments. The large dots indicate the robots which are already at their target positions. \(Sphere^{dc}\) of every robot is illustrated as a sphere. FrontierPoints are depicted as points on one robot's \(Boundary^{dc}\).