# Efficient Coverage Path Planning for a Drone in an Urban Environment
## 5 SST--An Efficient Heuristic Algorithm for the GPP Problem
### Planning Stage
The subset of waypoints \(\mathcal{W}^{h}\subset\mathcal{V}\) that will ultimately form the trajectory is chosen from \(\mathcal{V}\) in an iterative manner. In each iteration, a waypoint \(v^{*}\in\mathcal{V}\) is selected and added to a temporal copy of \(\mathcal{G}^{h}\). An upper bound is then calculated for the length of the path visiting every vertex in the temporal graph, as described in Section 5.5.3. In case the path length meets the time constraint, the set \(\mathcal{W}^{h}\) and the graph \(\mathcal{G}^{h}\) are updated, as well as the value of \(\tau_{curr}\) presenting the current path length estimation. The process terminates in one of the following cases:  
* All candidate waypoints have been examined. * The waypoints in \(\mathcal{W}^{h}\) cover the entire free area \(\pi_{f}\). * The mission constraint has been met by \(\tau_{curr}\). To determine the next waypoint \(v^{*}\) to add to \(\mathcal{W}^{h}\) (Algorithm 6), two parameters are considered:  
* _min_dist_ is the minimal distance allowed between two waypoints to avoid redundancy in the data collected during the flight. Its value depends on the flight altitude (footprint size) and a parameter that defines how much overlap is allowed between footprints. * _max_dist_ is the difference between the allowed trajectory length and the currently estimated trajectory length. \(v^{*}\) is the waypoint with the highest score that has not been examined yet where the following holds:  
\[min\_dist\leq dist(v)\leq max\_dist. \tag{6}\]Here, _dist_ is defined as follows: \[dist(v)=\min_{w\in\mathcal{W}^{h}}d(v,w)\] (7) and \(d(v,w)\) is the Euclidean distance between the waypoints \(v\) and \(w\). To build a complete graph with the shortest path lengths as its weights, adding a new vertex to the graph \(\mathcal{G}^{h}\) requires finding the shortest path from the new vertex to each of the existing vertices. To calculate these paths, the new vertex \(v^{*}\) is first connected to the visibility graph \(\mathcal{VG}\), where the shortest paths are found. 2. **solveOLTSP. ** Given the graph \(\mathcal{G}^{h}\), the final step of trajectory planning is to find the shortest path starting at \(w_{0}\) and traversing all its vertices. This problem is an instance of the OLTSP and, similarly to the ES algorithm, is solved using a random mixed local search algorithm with NN as an initialization heuristic. 3. **Post-Processing** The local paths found during the construction of \(\mathcal{G}^{h}\) are optimal regarding the graph \(\mathcal{VG}\), i.e., according to the obstacles at the lowest altitude. Assuming obstacles at altitude \(h_{i}\) are contained in the obstacles at \(h_{i+1}\) where \(h_{i}>h_{i+1}\), there might be redundant detours around obstacles that are not present at the current altitude. To avoid this, a post-processing procedure checks for possible shortcuts. Denote the waypoints in \(T\) that originated in \(\mathcal{W}^{h}\) as \(w_{k},\ k=1,..,K\). The trajectory must pass through these waypoints, which cannot be eliminated. Denote the rest of the waypoints in \(T\) as \(v_{q},\ q=1,...,Q\). These waypoints are a part of the local paths, which are used to avoid obstacles and can be eliminated if a valid shortcut is found. A valid shortcut means eliminating a waypoint \(v_{q}\) from \(T\) that ends with an edge connecting its adjacent waypoints in the free space \(\pi_{f}\). By editing the trajectory in this way, the safeness of \(T\) is not violated as well as the mission constraints, since the edges' weights are the Euclidean distances and the triangle inequality holds. It should be pointed out that the manner in which \(\mathcal{W}^{h}\) is constructed results in a set that does not necessarily fulfill Definition 1 and hence, cannot be determined as a \(p\)-coverage. However, it exhausts the mission constraints by covering as many cells as possible while prioritizing those with a high probability.