# Hybrid Path Planning for Efficient Data Collection in UAV-Aided WSNs for Emergency Applications
## 3 Formulation
### Prm  
Among the different probabilistic sampling-based algorithms, the PRM [27] is an extremely effective path planning approach due to its probabilistic completeness and remarkable practical performance. The PRM is completed in two steps, i.e., the learning and query phases. In the learning phase, the roadmap of the application environment is constructed in a probabilistic manner. It is represented as an undirected graph \(G=\{V,E\}\), where \(V\) is the set of configurations of UAV in free space, and \(E\) correspond to the path connecting the nodes in the configurations. In the query phase, the constructed roadmap is used to solve path planning issues. Primarily, the graph \(G=\{V,E\}\) is empty. Several random configurations are generated in the free space and added to \(V\). At the starting and ending positions of the UAV, i.e., \(P_{start}\) and \(P_{end}\), respectively, nodes from \(V\) are verified for collision and possible connections and then joined to obtain a feasible path. Let \(\gamma\) be the set of shortest paths between pairs of nodes in \(V\), and \(n^{\prime}\) be the number of total path samples required to obtain the targeted path. Therefore, the shortest path generated by the PRM is expressed as \begin{table}
\begin{tabular}{c c c} \hline \hline
**Existing Work** & **Main Idea** & **Limitation** \\ \hline
[32] & ACO-based path & Not suitable for dynamic and \\  & determination & emergency environment \\
[33] & RRT and RRT* planning & Not suitable for 3D dynamic \\  & exploration & and emergency environment \\
[34] & Spiral decomposition-based & Not suitable for 3D dynamic \\  & path plan & emergency environment \\
[35] & Age-optimal trajectory & Not suitable for 3D dynamic \\  & planning & emergency environment \\
[36] & PSO-based path planning & Not suitable for 3D dynamic \\  & & emergency environment \\
[37] & ACO-based path planning & Not suitable for 3D dynamic \\  & & emergency environment \\
[38] & K-means and simulated & Not suitable for 3D dynamic \\  & annealing based path plan & emergency environment \\
[39] & DL trained by GA-based path & Do not address 3D dynamic \\  & plan & and emergency environment. \\  & lgnores the obstacles and void \\
[40] & DRL and 6G-based path plan & areas of dynamic 3D \\  & & environments \\  & & Offline based algorithm; \\
[41] & Genetic algorithm and & ignores the aspects of \\  & ACO-based & emergency environments \\  & & Considers only \\
[42] & DP-based path plan & one-dimensional sensor \\  & & networks \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Summary of the existing works. \[P_{shortest}=\sum_{i=1}^{n}\gamma\times P_{l}, \tag{1}\]  
where \(P_{l}\) is the path length. To minimize the number of failures during the selection of nodes from \(V\), a new set \(N_{P_{start}}\) is defined that maintains the closest neighbors of \(P_{start}\); it is expressed as  
\[N_{P_{start}}=\big{\{}ReV\big{|}D\big{(}R,R^{\prime}\big{)}\leq D_{max}\big{\}}, \tag{2}\]  
where \(R\) is the nearest neighbor of \(P_{start}\), \(R^{\prime}\) the nearest neighbor of \(R\), and \(D_{max}\) the maximum distance. \(D\) (\(R\), \(R^{\prime}\)) is the Euclidean distance between \(R\) and \(R^{\prime}\), expressed as  
\[D\big{(}R,\ R^{\prime}\big{)}=\Big{|}UAV_{(R^{\prime})}-UAV_{(R)}\Big{|}. \tag{3}\]  
During the expansion step, \(\omega(R)\), the measure of path complexity of the coordinate \(R\), is used. If the value of \(\omega(R)\) is greater than the previous coordinate, then the coordinate in