In recent years, the rapid advancement of drone technology has revolutionized various fields, including surveillance, logistics, and disaster response. Unmanned Aerial Vehicles (UAVs) offer unparalleled flexibility and efficiency in executing complex tasks. However, optimizing their flight paths in three-dimensional environments remains a significant challenge due to constraints such as limited battery life and obstacle avoidance. Traditional optimization algorithms often struggle with premature convergence and inadequate local search capabilities, leading to suboptimal paths. To address these issues, we propose an Improved Gold Rush Optimizer (IGRO) that integrates the Spider Wasp Optimizer (SWO) and Differential Evolution (DE) algorithms, enhanced with Levy flight strategies. This hybrid approach balances global exploration and local exploitation, enabling efficient path planning for Unmanned Aerial Vehicles in complex terrains.
The core of our methodology involves modeling the flight environment using Gaussian functions to simulate mountainous obstacles, defining constraints for boundary adherence and obstacle avoidance, and formulating an objective function to minimize flight cost. We employ cubic spline interpolation to generate smooth paths, ensuring practicality for real-world drone operations. Through extensive simulations and benchmark testing on the CEC2017 suite, we demonstrate that IGRO outperforms existing algorithms in convergence speed and solution quality. This paper details the algorithmic improvements, mathematical formulations, and experimental results, highlighting the efficacy of IGRO in enhancing drone technology for autonomous navigation.
Unmanned Aerial Vehicle path planning requires robust optimization techniques to handle dynamic and complex environments. The Gold Rush Optimizer (GRO) is a metaheuristic algorithm inspired by the behavior of gold prospectors, where search agents explore the solution space to find optimal solutions. However, GRO tends to converge prematurely in multimodal problems, limiting its effectiveness. Our improved version, IGRO, incorporates key elements from SWO, such as hunting and nesting behaviors, and DE’s mutation and crossover mechanisms. Additionally, Levy flight introduces random long jumps, enhancing diversity and avoiding local optima. This combination ensures that IGRO adapts well to the intricate demands of drone path planning, providing a reliable framework for autonomous Unmanned Aerial Vehicle operations.
The mathematical foundation of IGRO involves several key equations. The original GRO algorithm updates the position of search agents using the following formulas. The distance vector $$ \vec{D_1} $$ is computed as:
$$ \vec{D_1} = C_1 \cdot (X^*(t) – X_i(t)) $$
where $$ X^*(t) $$ is the best solution found so far, and $$ X_i(t) $$ is the current position of agent i. The new position is then updated as:
$$ X_{i}^{new}(t+1) = X_i(t) + A_1 \cdot D_1 $$
The coefficients $$ A_1 $$ and $$ C_1 $$ are calculated using random vectors and a convergence component:
$$ A_1 = l_1 \cdot (2 \cdot r_1 – 1) $$
$$ C_1 = 2 \cdot r_2 $$
Here, $$ r_1 $$ and $$ r_2 $$ are random vectors in [0,1], and $$ l_1 $$ decreases linearly or nonlinearly over iterations, defined as:
$$ l_1 = 2 – \left(2 – \sigma\right) \cdot \left(\frac{iter}{max\_iter}\right)^e $$
with $$ \sigma = 2 $$ and e controlling the convergence rate. For mining and cooperation behaviors, similar update rules are applied, as shown in equations (7) to (11) of the original GRO. In IGRO, we integrate SWO’s position update mechanisms, such as constant motion and random exploration:
$$ SW_i^{t+1} = SW_i^t + \mu_1 \cdot (SW_a^t – SW_b^t) $$
where $$ \mu_1 = r_1 \cdot |n_r| $$, with $$ n_r $$ being a normally distributed random number. Another SWO-based update involves:
$$ SW_i^{t+1} = SW_c^t + \mu_2 \cdot (L + r_2 \cdot (H – L)) $$
where $$ \mu_2 = B \cdot \cos(2\pi l) $$, and $$ B = \frac{1}{1 + e^{-l}} $$. These equations enhance the exploration phase of IGRO. Furthermore, DE’s mutation and crossover are incorporated to refine solutions. The mutation vector $$ \vec{V} $$ is generated as:
$$ \vec{V} = X_{r1} + F \cdot (X_{r2} – X_{r3}) $$
where F is the scaling factor, and $$ X_{r1}, X_{r2}, X_{r3} $$ are randomly selected agents. Crossover produces a trial vector $$ \vec{U} $$:
$$ U_j = \begin{cases}
V_j & \text{if } p \leq Cr \\
X_j & \text{otherwise}
\end{cases} $$
for each dimension j, where Cr is the crossover probability. Selection is based on fitness comparison. Levy flight is implemented to introduce randomness:
$$ L = 0.05 \cdot \frac{u}{|v|^{1/\beta}} $$
with $$ \beta = 0.5 $$, and u, v drawn from normal distributions. This step allows IGRO to escape local optima effectively, crucial for drone path planning in rugged terrains.
For drone path planning, we model the environment using a Gaussian function to represent obstacles like mountains. The height at any point (x,y) is given by:
$$ z(x,y) = \sum_{i=1}^{N} h_i(x,y) = \sum_{i=1}^{N} H_i \cdot \exp\left(-\frac{(x – x_i)^2}{2\sigma_{x_i}^2} – \frac{(y – y_i)^2}{2\sigma_{y_i}^2}\right) $$
where N is the number of peaks, and $$ H_i $$, $$ x_i $$, $$ y_i $$, $$ \sigma_{x_i} $$, $$ \sigma_{y_i} $$ define each peak’s characteristics. The flight path is represented as a series of points, and cubic spline interpolation ensures smoothness. For a segment between points, the spline function is:
$$ f_n(x) = a_n (x – x_n)^3 + b_n (x – x_n)^2 + c_n (x – x_n) + d_n $$
with continuity conditions enforced at each node. The constraints for drone flight include boundary adherence and obstacle avoidance. The boundary constraints are:
$$ 0 \leq x_i \leq x_{max}, \quad 0 \leq y_i \leq y_{max}, \quad 0 \leq z_i \leq z_{max} $$
for all points i. The objective function to minimize is:
$$ fitness = V_c + T_c + E_c $$
where $$ V_c $$ is the total path length cost, $$ T_c $$ is the obstacle avoidance cost, and $$ E_c $$ is the boundary constraint cost. Specifically, $$ V_c $$ is computed as the sum of Euclidean distances between consecutive points:
$$ V_c = \sum_{i=1}^{n} L_i = \sum_{i=1}^{n} \sqrt{(x_{i+1} – x_i)^2 + (y_{i+1} – y_i)^2 + (z_{i+1} – z_i)^2} $$
$$ T_c $$ is set to infinity if the drone’s height is below the obstacle height at any point, and zero otherwise. Similarly, $$ E_c $$ is infinity if the drone violates boundary constraints, and zero otherwise. This formulation ensures that the optimized path is feasible and efficient for Unmanned Aerial Vehicle operations.
To evaluate IGRO’s performance, we conducted tests on the CEC2017 benchmark functions and a custom drone path planning scenario. The CEC2017 suite includes various unimodal and multimodal functions that challenge optimization algorithms. For instance, function F1 is a shifted and rotated bent cigar function, F12 is a composite function with multiple optima, and F16 is a hybrid function. We compared IGRO against GRO, KOA, LSO, and CFOA in 50 dimensions. The results, summarized in the table below, show that IGRO achieves lower average and best values with smaller standard deviations, indicating superior stability and convergence.
| Algorithm | F1 Average | F1 Best | F1 Std | F12 Average | F12 Best | F12 Std | F16 Average | F16 Best | F16 Std |
|---|---|---|---|---|---|---|---|---|---|
| GRO | 5.769e+10 | 4.919e+10 | 1.535e+10 | 2.138e+10 | 1.476e+10 | 1.098e+10 | 6.690e+03 | 6.405e+03 | 5.341e+02 |
| IGRO | 1.070e+10 | 2.008e+08 | 2.766e+10 | 2.382e+09 | 5.349e+07 | 1.122e+10 | 4.649e+03 | 3.828e+03 | 1.248e+03 |
| KOA | 2.145e+11 | 2.145e+11 | 1.313e+03 | 1.298e+11 | 1.298e+11 | 8.252e+07 | 1.205e+04 | 1.205e+04 | 3.276e-11 |
| LSO | 1.245e+10 | 1.379e+09 | 3.484e+10 | 3.840e+09 | 6.107e+07 | 1.286e+10 | 4.842e+03 | 4.224e+03 | 1.251e+03 |
| CFOA | 1.130e+11 | 8.026e+10 | 5.356e+10 | 9.293e+10 | 5.911e+10 | 3.811e+10 | 8.272e+03 | 5.509e+03 | 3.911e+03 |
In the drone path planning simulation, we defined a 100x100x250 flight space with five mountain obstacles modeled by Gaussian functions. The start point was set to [10,10,80] and the goal to [80,90,150]. We used a population size of 100 and compared the convergence behavior and path quality of different algorithms. The table below presents the average fitness values and convergence iterations, demonstrating IGRO’s efficiency.
| Algorithm | Average Convergence Iterations | Average Fitness Value | IGRO Fitness Ratio (%) | IGRO Iteration Ratio (%) |
|---|---|---|---|---|
| IGRO | 39 | 128.5 | 100 | 100 |
| GRO | 84 | 130.0 | 98.8 | 46.4 |
| CFOA | 2 | 293.3 | 43.8 | 1950 |
| KOA | 93 | 137.7 | 93.3 | 41.9 |
| LSO | 70 | 158.5 | 88.1 | 55.7 |
The results indicate that IGRO converges faster and produces smoother, shorter paths compared to other algorithms. For example, CFOA often gets trapped in local optima, leading to longer paths, while IGRO’s Levy flight mechanism enables it to explore diverse regions of the search space. The integration of SWO and DE ensures a balance between exploration and exploitation, making it highly suitable for complex drone navigation tasks. In practical terms, this means that Unmanned Aerial Vehicles equipped with IGRO-based path planning can operate more efficiently in environments like urban areas or natural landscapes, reducing energy consumption and improving mission success rates.
In conclusion, the Improved Gold Rush Optimizer represents a significant advancement in metaheuristic optimization for drone technology. By combining the strengths of SWO and DE with Levy flight, IGRO addresses the limitations of traditional algorithms, such as premature convergence and poor local search. Our experiments on benchmark functions and realistic path planning scenarios confirm its superiority in terms of convergence speed, solution quality, and stability. Future work could focus on adapting IGRO to dynamic environments or multi-objective optimization problems, further enhancing its applicability in autonomous Unmanned Aerial Vehicle systems. As drone technology continues to evolve, algorithms like IGRO will play a crucial role in enabling safe and efficient autonomous operations.