# Efficient Coverage Path Planning for a Drone in an Urban Environment
## 7 Conclusions and Future Work  
This paper dealt with the global path planning problem that arises when considering the autonomous landing of a drone in a dense urban environment. From the overall problem formulation, searching for a landing site required planning collision-free trajectories, meeting time constraints, and performing almost real-time computations. During the planning process, a probability map of the area of interest was considered, containing the likelihood of each sub-area being suitable for landing. In addition, a DSM was used to identify obstacle locations.  
We first formulated GPP as a minimization problem and showed that it belongs to the NP-hard computational geometry problem class. Then, we developed two computational algorithms: one based on exhaustive search and a family of approximating ones, generically called Score-Select-Traverse (SST). The first is easy to implement but involves a potentially exponential number of computations. The second includes a number of different variations and is the main contribution of this paper.  
The algorithms in the SST family comprise two stages--pre-processing and planning. The pre-processing stage was created to perform time-consuming operations before the beginning of the mission, using only prior knowledge. The planning stage uses the information acquired throughout the search to reduce the area of interest.  
The performance of the algorithms was compared using a simulation study. Not surprisingly, our experiments showed that some variations of the SST algorithm can significantly outperform the baseline heuristic in terms of computational times. Although being best in terms of coverage, ES and SST-AC were seen to be computationally expensive, making them unsuitable for almost real-time performance. On the other hand, the coverage performance of the vanilla SST algorithm was sufficiently close to that of ES, hence providing a good tradeoff between computation times and coverage.  
Further work should probably be directed at deepening the way we dilute the set of candidate waypoints, in particular by considering using previously planned trajectories. To improve the exhaustion of time constraints, a fast-to-compute, tighter upper bound for the trajectory length should be developed. Lastly, since the proposed algorithm contains several parts that can be computed in parallel, the use of a GPU should be considered to reduce computation times in actual implementations.  
Conceptualization, J.S., B.P., E.R., and H.R.; methodology, J.S., B.P., E.R., and H.R.; software, J.S.; validation, J.S. and B.P.; formal analysis, J.S. and B.P.; investigation, J.S., B.P., and H.R.; resources, E.R.; data curation, J.S.; writing--original draft preparation, J.S., B.P., and H.R.; writing--review and editing, B.P. and H.R.; supervision, E.R. All authors have read and agreed to the published version of the manuscript.  
This research received no external funding.  
Not applicable.  
The original contributions presented in this study are included in the article. Further inquiries can be directed to the corresponding author.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**ES** & **SST** & **SST\_AC** & **SST\_CEC** \\ \hline
96.1 & 88.2 & 88.1 & 85.2 \\ \hline SST\_DIL\_100 & SST\_DIL\_1000 & SST\_DIL\_10,000 & \\ \hline
88.2 & 88.0 & 87.3 & \\ \hline \hline \end{tabular}
\end{table}
Table 2: Exhaustion of time constraints [%].  
**Acknowledgments:** We would like to thank [PERSON], head of the Technion Autonomous System Program (TASP), for his continuous support.