# Efficient Coverage Path Planning for a Drone in an Urban Environment
## 5 SST--An Efficient Heuristic Algorithm for the GPP Problem
### Planning Stage  
The planning stage of the suggested SST algorithm is presented in Algorithms 4-6, as well as in Figure 4, as follows:  
```
Input: A probability map \(\mathcal{P}\), first waypoint \(w_{0}\), mission constraints \(\tau_{max}\), visibility graph \(\mathcal{VG}\) Output: A graph \(\mathcal{G}^{h}\)
1: scoreAndSort(\(\mathcal{V},\mathcal{P},\mathcal{O}\))
2:\(\mathcal{VG}\).addVertex(\(w_{0}\))
3:\(\mathcal{G}^{h}\).addVertex(\(w_{0}\))
4:\(\mathcal{W}^{h}\gets w_{0}\)
5:\(\tau_{curr}=0\) [estimated time to perform current trajectory]
6:\(open\_list\leftarrow\mathcal{V}\)
7:while\(open\_list\
eq\emptyset\)do
8:\(\tau_{remain}=\tau_{max}-\tau_{curr}\)
9:\(v^{*}\leftarrow\) chooseNextVertex(\(\mathcal{W}^{h},open\_list,r_{fp},\tau_{remain}\))
10:\(temp\_\mathcal{G}^{h}\leftarrow\) copy(\(\mathcal{G}^{h}\))
11:\(temp\_\mathcal{G}^{h}\).addVertex(\(v^{*}\))
12:\(\tau_{estimated}\leftarrow\) estimatePathLength(\(temp\_\mathcal{G}^{h}\))
13:if\(\tau_{estimated}\leq\tau_{max}\)then
14:\(\mathcal{W}^{h}\leftarrow\mathcal{W}^{h}\cup v^{*}\)
15:\(\mathcal{G}^{h}\gets temp\_\mathcal{G}^{h}\)
16:\(\tau_{curr}\leftarrow\tau_{estimated}\)
17:endif
18:\(open\_list\).remove(\(v^{*}\))
19:if\(\mathcal{W}^{h}\) covers entire free area \(\tau_{f}\) or \(\tau_{curr}==\tau_{max}\)then
20:return\(\mathcal{G}^{h}\)
21:endif
22:endwhile
23:return\(\mathcal{G}^{h}\)
```  
**Algorithm 5**scoreAndSelect  
```
Input: A probability map \(\mathcal{P}\), first waypoint \(w_{0}\), mission constraints \(\tau_{max}\), visibility graph \(\mathcal{VG}\) Output: A graph \(\mathcal{G}^{h}\)
1: scoreAndSort(\(\mathcal{V},\mathcal{P},\mathcal{O}\))
2:\(\mathcal{VG}\).addVertex(\(w_{0}\))
3:\(\mathcal{G}^{h}\).addVertex(\(w_{0}\))
4:\(\mathcal{W}^{h}\gets w_{0}\)
5:\(\tau_{curr}=0\) [estimated time to perform current trajectory]
6:\(open\_list\leftarrow\mathcal{V}\)
7:while\(open\_list\
eq\emptyset\)do
8:\(\tau_{remain}=\tau_{max}-\tau_{curr}\)
9:\(v^{*}\leftarrow\) chooseNextVertex(\(\mathcal{W}^{h},open\_list,r_{fp},\tau_{remain}\))
10:\(temp\_\mathcal{G}^{h}\leftarrow\) copy(\(\mathcal{G}^{h}\))
11:\(temp\_\mathcal{G}^{h}.addVertex(v^{*})\)
12:\(\tau_{estimated}\leftarrow\) estimatePathLength(\(temp\_\mathcal{G}^{h}\))
13:if\(\tau_{estimated}\leq\tau_{max}\)then
14:\(\mathcal{W}^{h}\leftarrow\mathcal{W}^{h}\cup v^{*}\)
15:\(\mathcal{G}^{h}\gets temp\_\mathcal{G}^{h}\)
16:\(\tau_{curr}\leftarrow\tau_{estimated}\)
17:endif
18:\(open\_list\).remove(\(v^{*}\))
19:if\(\mathcal{W}^{h}\) covers entire free area \(\tau_{f}\) or \(\tau_{curr}==\tau_{max}\)then
20:return\(\mathcal{G}^{h}\)
```  
**Algorithm 6**\(open\_list\)  
```
Input: A probability map \(\mathcal{P}\), first waypoint \(w_{0}\), mission constraints \(\tau_{max}\), visibility graph \(\mathcal{VG}\) Output: A graph \(\mathcal{G}^{h}\)
1: scoreAndSort(\(\mathcal{V},\mathcal{P},\mathcal{O}\))
2:\(\mathcal{VG}\).addVertex(\(w_{0}\))
3:\(\mathcal{G}^{h}\).addVertex(\(w_{0}\))
4:\(\mathcal{W}^{h}\gets w_{0}\)
5:\(\tau_{curr}=0\) [estimated time
```
1. scoreAndSelect.The algorithm's first aim is to select trajectory waypoints \(\mathcal{W}^{h}=(w_{1},...,w_{K})\subset\mathcal{V}\) that allow it to explore high-probability areas without exceeding the time-of-flight limit. Furthermore, to represent the connectivity between the selected waypoints, a graph \(\mathcal{G}^{h}\) is constructed with \(\mathcal{W}^{h}\) as its vertices and the shortest path lengths as its weights. This graph will later allow for establishing the shortest path visiting all selected waypoints. The procedure of selecting \(\mathcal{W}^{h}\) out of \(\mathcal{V}\) and the construction of \(\mathcal{G}^{h}\) is presented in Algorithm 5. Each waypoint in \(\mathcal{V}\) is assigned a score based on the probability map and the flight altitude, indicating the potential for finding a landing zone in its environment (Section 5.5.1). The candidate waypoints are then sorted according to their scores in decreasing order.