## 4 Optimizing Path Schedule of the Mobile Sink
### The Ideal Case  
In this section, we first try to find a solution to solve the path optimizing problem of the mobile sink when each UGV follows its monitoring cycle strictly. Therefore, we have all the information to guide the scheduling. As described above, we now have the spatial-temporal graph of the system. The goal is to find a trajectory of the mobile sink that could visit UGVs as many times as possible. The problem is unique and quite different from the traditional salesman problem, i.e., the TSP problem. A TSP problem is trying to find the shortest path that visits all the points from the starting point and finally returns to the same point. The graph is a precedence graph that can not be solved using traditional algorithms. Definition 1: A path that visits all points in the precedence graph is called a **complete path**. Definition 2: If \(b\) is to the right of \(a\) and there is an edge linking them, we say that \(b\) is \(a\)'s **neighbor**. In other words, \(b\) appears later than \(a\) in the graph. Definition 3: If \(b\) is the closest point to a among all neighbors of \(a\) in the time scale, we say that \(b\) is \(a\)'s **nearest neighbor**. We have Theorem 1 that shows our problem is not equal to the traditional TSP problem since only one complete path exists, so it is not necessary to find the shortest path. Theorem 1: _If paths passing all points in the given Graph do exist, they are the same path._  
Proof: Suppose there exists two different paths that pass all points, i.e., \(P_{1}\) and \(P_{2}\). \(P_{1}\) has the point sequence of \((v_{0},v_{1},...,v_{i},...,v_{j},...v_{n})\). Then, there exists at least two points having different sequences in \(P_{2}\), e.g., \(v_{i}\) and \(v_{j}\). However, if there is path between \(v_{i}\) and \(v_{j}\), then \(t_{v_{j}}\) must be greater than \(t_{v_{i}}\). Therefore, the path is not valid from \(v_{j}\) to \(v_{i}\), which means path \(P_{2}\) is not a valid path. Theorem 2: _The necessary and sufficient condition under which we could find a complete path in a given graph is that each point has an edge to its nearest neighbor._  
Proof: Suppose there exists at least two points \(v_{i}\) and its nearest neighbor \(v_{j}\), and there is no direct edge between them. Therefore, the path connecting \(v_{i}\) and \(v_{j}\) must go through at least one middle point \(v_{k}\). However, since \(v_{j}\) is already the nearest neighbor of \(v_{i}\), there is no point \(v_{k}\) between them, i.e., \(v_{k}\) does not exist at all. Thus, there is no such path that can visit both \(v_{i}\) and \(v_{j}\). From Theorems 1 and 2, we propose the algorithm 1 to find the complete path in the given graph. ```
0: adjacency matrix M
0: a point sequence \(P=\{v_{0},v_{1},...,v_{m}\}\) forming a path. 1: Set current point \(q\) to the leftmost point in the graph (starting from the element \(M[q,q]\) where \(q=0\)), \(P=\{q\}\)
2: For current point \(q\), find its **nearest neighbor**\(r\) in the graph (the first element \(M[q,r]\) that has a non-negative value). If there are no more neighbors, the algorithm ends. 3: Add point \(r\) into the \(P\). Then, \(P=P\cup\{r\}\)
4: Set \(q=r\) as the current point, and GOTO step 2
```  
**Algorithm 1 Complete path** finding algorithm in the precedence graph  
The algorithm is very simple, according to Theorem 2. At each step, we only need to follow the edge to the nearest neighbor of the current point. Finally, all of the edges will form a path from the first point to the last. If the same pattern appears somewhere along the time scale, then it can be declared that an effective cycle has been found. Since there is only one complete path, it is also the shortest path. ```
0: adjacency matrix M
0: hop number \(s_{i}\) of each point \(i\) and a point sequence \(P=\{v_{0},v_{1},...,v_{m}\}\) forming a path. Initialize
1: Set current point \(q\) to the rightmost point in the graph (starting from the element \(M[q,q]\) where \(q=n\)).