# Hybrid Path Planning for Efficient Data Collection in UAV-Aided WSNs for Emergency Applications
## 4 Hybrid Algorithm for UAV Path Planning
### Proposed Hybrid Path Planning
(\(X_{e}\),\(Y_{e}\),\(Z_{e}\))
4:\(Iter_{max}=\) number of nodes to complete the roadmap
5: Roadmap constructed by Algorithm 1
6:Output:
7: The optimized path from the point of origin (\(X_{s}\), \(Y_{s}\), \(Z_{s}\)) to the point of destination (\(X_{e}\), \(Y_{e}\), \(Z_{e}\)) /* initializes the network*/
8:begin
9:for (\(i=1\) to \(Iter_{max}\)) do
10:for each employed bee, do
11: Use the food position, i.e., path coordinates generated in **Algorithm 1**
12:endfor
13:for each onlooker bee, do
14: Select new food sources based on the probability values
15: Compute the collision and threat probability using
16: (13) and (14)
17:if the collision is detected as in (13) && threats as in (14), then
18: Avoid that coordinates
19:repeat step 10-13;
20:else
21: Compute Optimized values of UAV's speed //to minimize the flight time using the highest possible speed
22: Compute the turning angles with minimum effect for a smooth path from (17) //smoothness in path minimizes the energy consumption and flight time of the UAV
23: Generate a new food source with optimized parameters
24:endif
25:while UAV is in the region of sensor nodes, do
26: Compute least possible height from sensors as in (15)
27://to minimize the energy of the sensor by reducing the transmission distance
28: Compute the optimized value of UAV's flight time for time-efficient data collection as in (24) //to increase the UAV-to-sensor communication time, optimize the speed
29:endwhile
30: Show the new path coordinates (\(X_{new}\), \(Y_{new}\), \(Z_{new}\))
31:endfor
32:for each scout bee, do
33: Evaluate the fitness of the coordinates used by the onlooker bee
34: Evaluate the fitness of the coordinates used by the employer bee
35:if the coordinates generated by the onlooker bee is better than those of the employer bee, then
36:replace the coordinates of the employer bee
37:else
38:else
39: Use the coordinates generated by the roadmap
31:endif
32:endfor
33: Memorize the best path
34:endforInitially, the UAV follows the roadmap generated by Algorithm 1. The generated path is optimized by considering constraints such as dynamic obstacles and other issues about the complex environment, as discussed in the subsection above. The ABC algorithm imitates the behavior of biological bees. The employed bees are supposed to follow the roadmap, whereas the onlooker bees continue to seek new coordinates and calculate their collision and threat probability using (13) and (14). If collision or any other threats are detected, then the onlooker bees search for new food sources and execute the steps above. If the coordinate is free of any threats and collision, the optimized values of speed, height, and turning angles are computed, as in (15), (17), and (18), to minimize the total flight time and the network energy. The HPP algorithm is shown in Algorithm 2. Figure 3 shows a comprehensive operation flow of the proposed hybrid algorithm. First, the starting and goal points of the application area are initialized. The PRM is used to calculate the shortest and collision-free path from the start point to the goal point. Initially, the shortest path determined by the PRM algorithm is used. However, the ABC algorithm is used to optimize the path coordinates for various environmental constraints. The ABC algorithm uses three different types of bees. In our proposed method, the employer bees follow the path generated by the PRM. The onlooker bees seek new path coordinates and calculate the fitness probabilities for new coordinates. The scout bees compare the fitness value of the onlooker bee to that of the employer bee. If the new coordinate's fitness value is higher than the roadmap's coordinates, new coordinates are selected considering the time and energy minimization of the proposed UWSN; otherwise, the new coordinates are discarded. Hence, static roadmap generation and dynamic path planning are involved in obtaining the shortest and safest paths for emergency environments. Figure 3: Operation flow of the proposed HPP algorithm.