# Efficient Coverage Path Planning for a Drone in an Urban Environment
## 3 System Model and Problem Definition
### Exact Formulation  
Define a cost function \(\tau(\cdot)\) over all safe trajectories \(T\). The cost function measures a property of the trajectory that one would like to control. For definiteness, a total traveling time constraint is assumed here; hence, let \(\tau_{max}\) be the maximal time-of-flight allowed for the trajectory.  
With these definitions, the GPP can be translated into the problem of finding the minimum value of \(p\) such that there exists a safe, p-covering trajectory for which \(\tau(T)=t_{end}-t_{0}\leq\tau_{max}\):  
\[\min p\] (4) s.t. for some \[T\] \[\tau(T)\leq\tau_{max}\] \[\forall(m,n)\in\Gamma(p):\ c_{m,n}\subset\mathcal{F}(T)\] \[T\in\pi_{f}\]  
The first constraint guarantees that the desired cost is not violated. For a given \(p\), the second constraint requires \(T\) to be p-covering. Finally, the third constraint promises the safeness of \(T\).  
Notice that for \(\underline{p}\approx 1\), the \(\underline{p}\)-coverage set \(W^{h}\) will be relatively small, and hence, one would expect to meet the upper bound \(\tau_{max}\) of the cost function. As \(\underline{p}\) gets smaller, the number of cells to be visited increases, and so eventually, the upper bound might not be met by any feasible trajectory. The problem, therefore, captures the desirable property of visiting as many cells as possible while concentrating on the higher probability ones.  
Theorem 1: _GPP is an NP-hard problem._  
Proof: To prove the NP-hardness of the problem, we use a known NP-hard problem, the Orienteering Problem (OP) [30], and reduce it to the GPP problem in a polynomial time. The OP is formulated as follows. Given \(n\) nodes in the Euclidean plane \([v_{1},..,v_{i}..,v_{n}]\), each with a score \(s(i)\geq 0\), find a route of maximum score through these nodes beginning at \(v_{1}\) and ending at \(v_{n}\) of length no greater than \(T_{MAX}\).  
Consider an instance \(\mathcal{P}\) of the OP. We reduce it to a GPP problem by the following operations.  
Place the nodes on a grid such that a single cell does not contain more than one node.
2. Convert the scores to probabilities by normalizing them.
3. Generate a probability map \(\mathcal{M}\) out of the grid by assigning the score values to cells containing nodes and 0 otherwise.
4. To ensure the selection of \(v_{N}\) and its position at the end of the path, set \(p(v_{N})=\infty\) and \(dist(v_{N},v_{i})=\infty\)\(\forall i\).
5. Set the required initial waypoint as \(v_{1}\).  
Define \(\mathcal{P}^{\prime}\) as a GPP problem with a probability map \(\mathcal{M}\), initial position \(v_{1}\), and time constraint \(T_{MAX}\). With the assumption of a single-cell size footprint, the minimization of \(p\) in \(\mathcal{P}^{\prime}\) is equivalent to the maximization of the total score in \(\mathcal{P}\).  
The optimization problem considered above provides a mathematical formulation of the GPP problem. In Sections 4 and 5, two alternative approaches for solving the GPP problem that trade the simplicity of exhaustive search with a more complex and efficient algorithm will be discussed.