# Efficient Coverage Path Planning for a Drone in an Urban Environment
## 6 Performance Evaluation
### Experimental Results  
Seventy sub-areas of differing sizes were randomly selected from the search area to evaluate the algorithm's performance. The scenarios described in Section 6.1 were tested at each flight altitude with a time constraint of \(\tau_{max}=300\) s. The probability maps were generated so that cells associated with obstacles were set to have probability zero, while the remaining cells' probabilities were set by randomly positioning several Gaussian distributions over the search region so that their centers were randomized with a uniform distribution. Moreover, three internal parameters used by the algorithms were set as follows: \(I=10,000\), \(R=5\) (Algorithms 2 and 4), and \(overlappingFactor=0.375\) (Algorithm 6). An example of a single instance solved by each of the seven considered algorithms is pictured in Figure 5.  
The algorithm performance was measured using two metrics. The first one is coverage. As the optimization criterion (Equation (4)) describes, the goal is to maximize the covered area while concentrating on areas with high probabilities. In order to quantify the coverage obtained by each algorithm, a threshold \(p_{thresh}\) was applied to the input probability map, creating a discrete map \(\mathcal{DM}(p_{thresh})\) indicating the cells with probabilities greater than this threshold. Let \(\mathcal{VM}(T)\) denote the visiting map, where cells covered by the planned trajectory are equal to 1, and 0 otherwise. The coverage of a trajectory \(T\) as a function of \(p_{thresh}\) is given by the following:  
\[coverage(p_{thresh})=\frac{\sum\mathbbm{1}\left\{c_{mn}\in\mathcal{VM}(T)\ \&\ c_{mn}\in\mathcal{DM}(p_{thresh})\right\}}{\sum\mathbbm{1}\left\{c_{mn} \in\mathcal{DM}(p_{thresh})\right\}} \tag{10}\]  
Results of the coverage performance are shown in Figure 6. As expected, the ES algorithm achieved the best results in terms of coverage. Its wide search space allowed positioning the trajectory waypoints such that high-probability areas were efficiently covered. Among the SST algorithms, the vanilla version produced the closest results to the ES algorithm. It can be seen that for high probabilities (\(p_{thresh}\geq 0.85\)), its average coverage ratio is similar to that achieved by ES, and as the threshold decreases, the gap grows up to  
Figure 5: The planned trajectories solved by each of the examined algorithms. The size of the map is 770 m \(\times\) 770 m, and the flight altitude is 150 m. Green and red areas are of high and low probabilities, respectively; black areas represent NFZ. 5% for probabilities larger than 0.5. SST-AC and SST-DIL-10,000 produced results close to SST, while SST-DIL-100 performed the worst. The second aspect of performance is computation times. Since the GPP has to be solved several times during the mission of autonomous landing, it is crucial to keep computation times reasonable. A comparison of the average computation time of each tested algorithm is presented in Table 1. The average computation times of ES and SST-AC are the maximal obtained and are greater than one minute, which implies that these algorithms are not suitable for solving the problem discussed. For the SST variations with dilution, one can conclude that for small values of \(N\), the dilution operation indeed decreases computation times (at the price of lower coverage); however, as \(N\) increases, it can cause an increase in computation times. Compared to ES, vanilla SST shows a 93% reduction in average planning computation time. In addition, we examined the impact of problem parameters on performance. The impact of the search area size was tested by varying its size from \(\frac{1}{16}MN\) to \(MN\) where \(MN=1500\times 1500\) [m\({}^{2}\)]. Ten probability maps were randomly generated and then trimmed to six different sizes for a total of 60 scenarios. All other parameters, including flight altitude, time constraint, initial waypoint, and obstacle locations, remained constant across all scenarios.