# Efficient Coverage Path Planning for a Drone in an Urban Environment
## 6 Performance Evaluation
### Experimental Results
Figure 7a shows that for ES and most SST algorithms, the computation time increases with area size. As the number of candidate waypoints is a function of the size of the free area, this is the expected result. However, for the SST variations with dilution (N = 100, 1000), the opposite is true--computation time decreases with the increase in area size. We can explain this result as follows: the dilution operation results in the candidate waypoints being farther apart in large areas compared to small areas, making it possible to include fewer waypoints in the trajectory for the same time (length) constraint. This affects the solution of OLTSP and decreases computation times. Figure 7b shows how the search area size affects the coverage performance. As expected, the coverage ratio decreases with \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Algorithms** & **20 m** & **40 m** & **70 m** & **100 m** & **150 m** & **Avg.** \\ \hline ES & 1049.0 & 404.1 & 218.1 & 149.8 & 151.2 & 394.4 \\ SST & 41.4 & 29.1 & 22.4 & 19.7 & 17.0 & 25.9 \\ SST-AC & 425.6 & 386.2 & 385.3 & 383.6 & 378.4 & 391.8 \\ SST-CEC & 120.7 & 55.3 & 47.2 & 46.9 & 47.9 & 63.6 \\ SST-DIL-100 & 7.9 & 7.7 & 7.3 & 6.8 & 5.9 & 7.1 \\ SST-DIL-1000 & 27.7 & 23.8 & 18.5 & 14.1 & 10.9 & 19.0 \\ SST-DIL-10,000 & 81.4 & 64.5 & 40.5 & 29.8 & 24.1 & 48.1 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Planning stage average computation time [s]. Figure 6: Average coverage ratio vs. threshold, calculated according to Equation (10). the increase of area size since the area to be explored expands, whereas the time (length) constraint remains unchanged. The second parameter examined was the number of obstacle vertices. For this purpose, we created a scenario including 15 obstacles randomly chosen from the original \(1500\times 1500\) [m\({}^{2}\)] search area, then iteratively added more obstacles, creating 13 areas with increasing number of obstacle vertices. For each search area, five different probability maps were generated for a total of 65 scenarios. In this case as well, all other parameters remained constant. Figure 8 depicts the impact of the number of obstacle vertices on the algorithms' performance. For an increasing number of obstacle vertices, there is a moderate increase in both computation time and coverage ratio. The computation time is affected by the number of obstacles as it determines the number of vertices in the visibility graph \(\mathcal{VG}\) and hence influences the performance of calculating the shortest path. However, the presence of obstacles can neither improve the coverage ratio--as they reduce the free space--nor worsen it, since in this case, they extend the way to cells with high probabilities. Finally, Table 2 introduces how much each algorithm's output trajectories exhausted the time constraint. As expected, the ES algorithm, which has the largest search space, produced trajectories that exhaust most of the time within the time limit provided. In addition to the smaller search space, there are two more reasons for the shorter trajectories produced by the SST algorithms. First, as discussed in Section 5.5.3, the upper bound given by the NN heuristic might be loose, causing early termination of the waypoints' selection step. Secondly, the trajectory is planned according to obstacles at the lowest altitude and then is shortened using detours. Figure 8: Algorithm performance for varying numbers of obstacle vertices. (**a**) Computation time as function of the number of obstacle vertices. (**b**) Coverage as a function of the number of obstacle vertices. Figure 7: Algorithm performance for varying map sizes. (**a**) Computation time as function of the map size. (**b**) Coverage as a function of the map size.