In recent years, drone technology has advanced rapidly, offering advantages such as low operational costs and quick response times. Unmanned Aerial Vehicles (UAVs) are widely used in military and civilian applications due to their ability to perform complex flight missions autonomously. Path planning is a critical research area in drone technology, enabling UAVs to navigate efficiently from a start point to a destination while avoiding threats and minimizing energy consumption. This process ensures that the UAV adheres to its constraints, such as turning angles and climb/descent rates, to achieve a safe and optimal path.
Path planning methods are broadly categorized into traditional algorithms and intelligent optimization algorithms. Traditional approaches, like the A* algorithm, Rapidly-exploring Random Trees (RRT), and artificial potential field methods, often produce paths with large turns that require smoothing. As the environment scale increases, these methods can become computationally intensive, reducing efficiency. In contrast, intelligent optimization algorithms, inspired by natural behaviors, offer faster convergence, flexibility, and ease of implementation. Examples include Particle Swarm Optimization (PSO), Genetic Algorithms (GA), and Whale Optimization Algorithm (WOA). These algorithms incorporate constraints and objectives into a cost function, allowing them to handle complex UAV path planning problems effectively.
Among intelligent algorithms, the Harris Hawk Optimization (HHO) algorithm, introduced in 2019, simulates the cooperative hunting behavior of Harris hawks. It features simple principles, few parameters, and easy implementation. However, HHO suffers from low convergence accuracy, slow convergence speed, and a tendency to fall into local optima. To address these issues, this paper proposes an enhanced HHO algorithm, termed the Division-based Enhanced Harris Hawk Optimization (DEHHO), for UAV path planning. The improvements include a potential energy wave learning strategy to enhance global exploration, a division mechanism to adjust prey escape opportunities based on population quality, and an elite time-varying Lévy flight to balance exploration and exploitation. Simulation results demonstrate that DEHHO outperforms existing algorithms in terms of convergence precision and stability, making it suitable for solving complex path planning problems in drone technology.
Problem Formulation for UAV Path Planning
In UAV path planning, the environment must be mathematically modeled to represent terrain constraints and obstacles. This modeling provides height data and threat information, forming the basis for path optimization. We use a threat-equivalent terrain model to simulate the flight environment, which captures realistic terrain variations while facilitating algorithm implementation. The mathematical model for the threat-equivalent terrain is given by:
$$ z(x, y) = \sum_{i=1}^{p} h(i) \exp\left(-\left(\frac{x – x_{ci}}{x_{ki}}\right)^2 – \left(\frac{y – y_{ci}}{y_{ki}}\right)^2\right) $$
where \( z(x, y) \) is the terrain height at coordinates \( (x, y) \), \( p \) is the number of peaks, \( h(i) \) is the height of the \( i \)-th peak, \( (x_{ci}, y_{ci}) \) are the coordinates of the peak center, and \( (x_{ki}, y_{ki}) \) are attenuation coefficients inversely related to slope steepness. This model generates a realistic 3D environment with multiple peaks, as shown in the provided figure.
For obstacles such as buildings, trees, or poles, we use cylindrical models to simplify collision avoidance. The cylinder’s radius corresponds to the obstacle’s maximum cross-sectional radius, and its height represents the obstacle’s height. The threat region for an obstacle is defined as:
$$ \begin{cases} (x – O_x)^2 + (y – O_y)^2 \leq O_r^2 \\ z \leq O_h \end{cases} $$
where \( (O_x, O_y) \) is the center of the cylinder’s base, \( O_r \) is the radius, and \( O_h \) is the height. This approach ensures that the UAV avoids obstacles efficiently without excessive computational overhead.
The cost function for path planning combines multiple objectives: path length, safety from threats, and smoothness. Let \( p_i = (x_i, y_i, z_i) \) represent a path point, and \( \text{Path} = \{p_0, p_1, \dots, p_n\} \) be the sequence of points from start \( p_0 \) to goal \( p_n \). The path length cost \( C_1 \) is the Euclidean distance between consecutive points:
$$ C_1 = \sum_{i=0}^{n-1} \sqrt{(x_{i+1} – x_i)^2 + (y_{i+1} – y_i)^2 + (z_{i+1} – z_i)^2} $$
The threat cost \( C_2 \) accounts for terrain collisions. We sample five points between consecutive path segments and compute the height difference relative to a safe height \( h_{\text{safe}} \):
$$ C_2 = \sum_{i=0}^{n-1} \sum_{j=1}^{5} T_j, \quad T_j = \begin{cases} 0 & \text{if } h_j \geq z_j + h_{\text{safe}} \\ T & \text{otherwise} \end{cases} $$
where \( h_j \) is the height of the \( j \)-th sample point, \( z_j \) is the terrain height, and \( T \) is a large constant penalizing unsafe paths. The smoothness cost \( C_3 \) ensures that turning angles \( \phi_i \) and climb/descent angles \( \theta_i \) remain within limits \( \phi_{\max} \) and \( \theta_{\max} \):
$$ C_3 = \sum_{i=1}^{n-1} S_i, \quad S_i = \begin{cases} 0 & \text{if } \phi_i \leq \phi_{\max} \text{ and } \theta_i \leq \theta_{\max} \\ T & \text{otherwise} \end{cases} $$
The total cost function is a weighted sum:
$$ C = \alpha_1 C_1 + \alpha_2 C_2 + \alpha_3 C_3 $$
where \( \alpha_1, \alpha_2, \alpha_3 \) are weights prioritizing each objective. This cost function guides the optimization algorithm toward feasible and optimal paths for Unmanned Aerial Vehicles.
Basic Harris Hawk Optimization Algorithm
The Harris Hawk Optimization algorithm mimics the hunting behavior of Harris hawks, which involves exploration and exploitation phases. The algorithm uses prey escape energy \( E \) to switch between these phases. Initially, the hawks explore the search space broadly; as energy decreases, they exploit promising areas. The escape energy is updated as:
$$ E = 2E_0 \left(1 – \frac{t}{T}\right) $$
where \( E_0 \) is a random initial energy in \( (0,1) \), \( t \) is the current iteration, and \( T \) is the maximum iterations. If \( |E| \geq 1 \), the algorithm enters the exploration phase; otherwise, it proceeds to exploitation.
In the exploration phase, hawks update their positions based on random locations or the average group position:
$$ h_i(t+1) = \begin{cases} h_{\text{rand}}(t) – r_1 |h_{\text{rand}}(t) – 2r_2 h_i(t)| & \text{if } q \geq 0.5 \\ (h_{\text{rabbit}}(t) – h_m(t)) – r_3 (\text{lb} + r_4 (\text{ub} – \text{lb})) & \text{if } q < 0.5 \end{cases} $$
where \( h_i(t) \) is the position of the \( i \)-th hawk, \( h_{\text{rand}}(t) \) is a random hawk’s position, \( h_{\text{rabbit}}(t) \) is the best position (prey), \( h_m(t) \) is the average position, \( q, r_1, r_2, r_3, r_4 \) are random numbers in \( (0,1) \), and \( \text{ub}, \text{lb} \) are the search space bounds.
In the exploitation phase, the algorithm models four strategies based on prey escape energy \( E \) and a random escape chance \( r \): soft siege, hard siege, progressive soft siege, and progressive hard siege. For example, the soft siege strategy (when \( 0.5 \leq |E| < 1 \) and \( r \geq 0.5 \)) updates positions as:
$$ h_i(t+1) = \Delta h(t) – E |J h_{\text{rabbit}}(t) – h_i(t)| $$
where \( \Delta h(t) = h_{\text{rabbit}}(t) – h_i(t) \) and \( J \) is a random jump strength in \( (0,2) \). The progressive strategies incorporate Lévy flights to handle prey escape attempts:
$$ Z = Y + S \times \text{LF}(d) $$
where \( \text{LF}(d) \) is the Lévy flight function in \( d \)-dimensional space, and \( S \) is a random vector. The Lévy flight is defined as:
$$ \text{LF}(d) = 0.01 \times \frac{u \times \sigma}{|v|^{1/\beta}}, \quad \sigma = \left( \frac{\Gamma(1+\beta) \times \sin(\pi \beta / 2)}{\Gamma((1+\beta)/2) \times \beta \times 2^{(\beta-1)/2}} \right)^{1/\beta} $$
with \( u, v \) as random numbers, \( \beta = 1.5 \), and \( \Gamma \) as the gamma function. Despite its advantages, the basic HHO algorithm has limitations in convergence and local optima avoidance, necessitating improvements for drone technology applications.
Enhanced Harris Hawk Optimization Algorithm
To enhance the HHO algorithm for UAV path planning, we introduce three key strategies: potential energy wave learning, a division mechanism, and elite time-varying Lévy flight. These improvements address the issues of limited exploration, blind strategy selection, and inefficient convergence.
Potential Energy Wave Learning Strategy
The original HHO algorithm spends only about 15.43% of iterations in exploration, limiting global search capability. We propose a potential energy wave learning strategy inspired by spring motion. Each hawk \( h \) projects to a point \( h_p \) on the line between start and goal, representing zero potential energy. The hawk oscillates around this point with decaying amplitude, simulating energy loss. The learned position \( h^* \) is computed as:
$$ h^* = h_p + (h – h_p) e^{-\xi t} \sin\left(2\pi \frac{t}{T}\right) $$
where \( \xi \) is a decay coefficient controlling exploration scope. A greedy selection retains the better position between \( h \) and \( h^* \):
$$ h(t+1) = \begin{cases} h^* & \text{if } F(h^*) \leq F(h) \\ h & \text{otherwise} \end{cases} $$
This strategy enhances exploration diversity without altering the phase selection mechanism, improving the quality of initial solutions for Unmanned Aerial Vehicle path planning.
Division Mechanism
In the exploitation phase, the escape chance \( r \) is randomly generated, leading to blind strategy selection. We introduce a division mechanism that ranks hawks based on fitness and assigns \( r \) as:
$$ r_i = \frac{\text{rank}(h_i(t))}{N} $$
where \( \text{rank}(h_i(t)) \) is the ascending fitness rank of hawk \( i \), and \( N \) is the population size. Hawks with \( r_i \geq 0.5 \) are classified as inferior \( G_{\text{worse}} \) and use siege strategies to approach the prey quickly. Those with \( r_i < 0.5 \) are superior \( G_{\text{better}} \) and use progressive siege strategies with Lévy flights for refinement. This approach ensures that strategies are tailored to individual hawk quality, reducing redundant computations and improving convergence efficiency in drone technology applications.
Elite Time-Varying Lévy Flight
The original Lévy flight in HHO is applied to inferior positions, reducing its effectiveness. We propose an elite time-varying Lévy flight that uses the best position for random walks and incorporates a time-varying weight. The updated position \( Z’ \) is:
$$ Z’ = h(t) + \left(1 – \frac{t}{T}\right) \omega + S \times \text{LF}(d) $$
where \( \omega \) is a small constant preventing late-stage inactivity. The progressive siege strategies are modified as:
$$ h(t+1) = \begin{cases} Y & \text{if } F(Y) < F(h(t)) \\ Z’ & \text{if } F(Z’) < F(h(t)) \\ h(t) & \text{otherwise} \end{cases} $$
This strategy preserves elite solutions, enhances local exploitation, and adapts to different search stages, balancing exploration and exploitation for UAV path planning.
Simulation Experiments and Analysis
We evaluate the DEHHO algorithm in a 3D environment with threat terrain and obstacles. The simulation parameters are listed in Table 1 and Table 2. The start point is (1, 20, 30), the goal is (200, 160, 40), and we set 200 iterations, a population size of 30, and 12 path points. The cost weights are \( \alpha_1 = 1, \alpha_2 = 1, \alpha_3 = 1 \).
| Center Point | Peak Height (m) | X-axis Attenuation | Y-axis Attenuation |
|---|---|---|---|
| (45, 30) | 55 | 20 | 20 |
| (60, 160) | 50 | 15 | 15 |
| (80, 100) | 70 | 30 | 30 |
| (90, 175) | 60 | 20 | 20 |
| (100, 35) | 30 | 20 | 20 |
| (125, 75) | 40 | 15 | 15 |
| (150, 120) | 70 | 30 | 30 |
| (160, 40) | 70 | 20 | 20 |
| Center Point | Height (m) | Radius (m) |
|---|---|---|
| (50, 130) | 50 | 10 |
| (105, 140) | 70 | 10 |
| (110, 90) | 80 | 7 |
| (130, 30) | 50 | 15 |
| (170, 65) | 60 | 8 |
We compare DEHHO with GWO, HHO, IHHO (Improved HHO), DHHO (with division mechanism only), and EHHO (with potential energy wave learning and elite Lévy flight). The results, including best cost, average cost, and standard deviation over 20 runs, are summarized in Table 3.
| Algorithm | Best Cost | Average Cost | Standard Deviation |
|---|---|---|---|
| GWO | 274.6988 | 303.2898 | 22.4183 |
| HHO | 265.0343 | 279.3091 | 6.5737 |
| IHHO | 263.1098 | 269.7578 | 5.1099 |
| DHHO | 264.9905 | 269.4481 | 4.4984 |
| EHHO | 260.8794 | 267.0641 | 3.6722 |
| DEHHO | 257.7634 | 258.5828 | 0.9903 |
DEHHO achieves the lowest average cost (258.5828) and standard deviation (0.9903), indicating superior convergence precision and stability. The convergence curves show that DEHHO reaches lower costs faster than other algorithms. The box plot analysis confirms that DEHHO has the smallest interquartile range and median, demonstrating consistent performance. These results validate the effectiveness of the proposed strategies for UAV path planning in complex environments.
Conclusion
This paper presents an enhanced Harris Hawk Optimization algorithm for Unmanned Aerial Vehicle path planning. The DEHHO algorithm incorporates a potential energy wave learning strategy to improve global exploration, a division mechanism to optimize strategy selection, and an elite time-varying Lévy flight to enhance local exploitation. Simulation results in a 3D environment with threats and obstacles show that DEHHO outperforms existing algorithms in terms of convergence accuracy, speed, and stability. The proposed approach efficiently solves path planning problems for drone technology, ensuring safe and optimal paths. Future work will focus on extending DEHHO to dynamic environments and multi-UAV coordination.