# Efficient Coverage Path Planning for a Drone in an Urban Environment
## 4 Baseline Algorithm
```
Input: Probability map \(\mathcal{P}\), obstacle locations \(\mathcal{O}\), first waypoint \(w_{0}\), mission constraints \(\tau_{max}\) Output: Trajectory \(T\)
1:\(\mathcal{VG}\) = buildVisibilityGraph(\(\mathcal{O}\))
2:\(min,max\leftarrow\) min_prob(\(\mathcal{P}\)), max_prob(\(\mathcal{P}\)) {initialization}
3:\(diff\gets max-min\)
4:while\(\mathrm{diff}\geq\epsilon\)do
5:\(p\leftarrow\) updateThreshold(\(min,max\))
6:\(T_{\underline{p}}\leftarrow\) planTrajectory(\(\mathcal{P}\), \(\mathcal{VG}\), \(w_{0}\), \(\underline{p}\))
7:if\(\tau(T_{\underline{p}})\leq\tau_{max}\)then
8:\(T\gets T_{\underline{p}}\)
9:\(max\leftarrow\underline{p}\) {continue the search in the lower half of the range}
10:else
11:\(min\leftarrow\underline{p}\) {continue the search in the upper half of the range}
12:endif
13:\(diff\gets max-min\)
14:endwhile
15:return\(T\)
```  
**Algorithm 1**Exhaustive Search  
Inspired by [7; 8], the process of planning a \(\underline{p}\)-covering trajectory presented in Algorithm 2 consists of two main parts: waypoint selection and efficient waypoint arrangement. See Figure 3 for a graphical representation. For a given threshold \(\underline{p}\), the POIs are described by the set \(\Gamma(\underline{p})\). As Equation (2) states, multiple cells are included in the camera footprint when passing through a single waypoint. It is then possible to find a minimum set of strategic waypoints \(W^{h}\), which is \(\underline{p}\)-covering and guarantees complete and effective coverage of all the POIs. For this purpose, the POIs are clustered such that the size of each cluster does not exceed the camera footprint size. The set \(W^{h}\) is then built by collecting the centers of the clusters so that visiting all \(w_{k}\in W^{h}\) guarantees \(\underline{p}\)-coverage. Among the different clustering methods examined, the single-pass algorithm described in [33] proved to be the fastest. ```
Input: Probability map \(\mathcal{P}\), visibility graph \(\mathcal{VG}\), first waypoint \(w_{0}\), threshold \(\underline{p}\) Output: Trajectory \(T\)
1:\(POI\leftarrow\) applyThreshold(\(\mathcal{P}\), \(\underline{p}\))
2:\(W^{h}\leftarrow\)ClusterPOI(\(POI\))
3:\(W^{h}\).add(\(w_{0}\))
4:\(G\leftarrow\)buildGraph(\(W^{h}\), \(\mathcal{VG}\))
5:\(T_{\underline{p}}\leftarrow\) solveOLTSP(\(G\), \(I\), \(R\))
6:return\(T\underline{p}\)
```  
**Algorithm 2**planTrajectory  
To construct an efficient path that visits all the waypoints, a complete graph \(G\) with vertices \(W^{h}\) is built, with the shortest path lengths as its weights. The visibility graph guarantees that the shortest path between each pair of waypoints is collision-free. Based on the complete graph, the visiting order is determined by solving an OLTSP in which the goal is to find the shortest path that visits each waypoint exactly once without returningto the starting position. In particular, the near-optimal algorithm presented in [27] is used with the nearest-neighbor (NN) algorithm [25] as an initialization heuristic. The algorithm is based on local-search operations with two input parameters: the number of iterations \(I\) and the number of repetitions \(R\). The resulting algorithm generates a trajectory that complies with the entire set of constraints and corresponds to the smallest feasible probability threshold.