# Efficient Coverage Path Planning for a Drone in an Urban Environment
## 4 Baseline Algorithm  
As GPP is a new problem, we have first developed a solution based on an exhaustive search to serve as a baseline. A naive approach for finding the optimal probability threshold \(\underline{p}\) for the GPP problem presented in Equation (4) is to list all possible candidates for the solution and check whether each meets the problem's requirements. This approach results in a factorial algorithm that is, in principle, computationally infeasible for large problems. As stated before, the value of \(\underline{p}\) and the size of the \(\underline{p}\)-coverage set \(W_{h}\) are inversely proportional. For instance, assume a specific probability threshold \(\underline{p}=p_{0}\) and define the corresponding \(p_{0}\)-covering trajectory \(T_{p_{0}}\). In case \(T_{p_{0}}\) violates the cost constraint, then the minimum \(\underline{p}\) cannot be lower than \(p_{0}\). Alternatively, if \(T_{p_{0}}\) complies with the constraints, it is certain that the minimum \(\underline{p}\) is lower than or equal to \(p_{0}\). Referring to this behavior, a binary search is appropriate for finding the optimal solution. The Exhaustive Search (ES) algorithm, initially developed, iteratively searches for the minimum probability threshold for which the constraints are met. In each iteration, \(\underline{p}\) is fixed, and a corresponding \(\underline{p}\)-covering trajectory is found. Then, \(\underline{p}\) is updated according to whether the found trajectory complies with the constraints until convergence. A detailed description is provided in Algorithm 1. The inputs to the algorithm are a probability map and obstacle locations corresponding to the region \(\mathcal{A}\) at flight altitude \(h\), the required first waypoint, and mission constraints. The output of the algorithm is a trajectory covering a sub-area of \(\mathcal{A}\) at a constant altitude that avoids obstacles and meets the time constraints of the mission. First, a visibility graph [31] is built based on the known obstacle locations. The visibility graph allows for finding collision-free optimal paths between points in the free area \(\pi_{f}\). It is used as an auxiliary graph at a later stage when it is desirable to present the connectivity between waypoints. The visibility graph can be built efficiently using, e.g., the Plane Sweep algorithm in [32]. To determine the search boundaries, two variables \(min\) and \(max\) are initialized with the minimum and the maximum probabilities found in \(\mathcal{P}\). The iterative part begins with calculating the threshold \(\underline{p}\) as the middle of the search boundaries. Considering the probability map, obstacle locations, and the required first waypoint, a corresponding trajectory \(T_{p}\) is then found. Starting at \(w_{0}\), the planned trajectory is \(\underline{p}\)-covering and safe. In case \(\tau\left(T_{\underline{p}}\right)\leq\tau_{max}\), \(T_{\underline{p}}\to T\) since it meets all the constraints and corresponds to the minimal threshold found so far. Finally, the search range is narrowed according to the previous comparison: the upper boundary \(max\) is reduced to \(\underline{p}\) in case the constraints are met, or the lower boundary \(min\) is enlarged to \(\underline{p}\) if the opposite is true. The search continues until the search interval, i.e., the difference between \(max\) and \(min\), is less than some \(\epsilon\).