In recent years, path planning algorithms have played a critical role in the application of unmanned aerial vehicles (UAVs), particularly for quadrotor drones. The primary objective is to find a safe, optimal, or suboptimal path in a workspace with obstacles, based on performance metrics such as path length and planning time. Numerous meta-heuristic algorithms have been proposed for this task, including Particle Swarm Optimization (PSO), Grey Wolf Optimizer (GWO), Whale Optimization Algorithm (WOA), and the Sparrow Search Algorithm (SSA). Among these, SSA has gained attention due to its convergence speed and robustness. However, when solving complex engineering optimization problems, SSA tends to suffer from premature convergence, slow convergence speed, low solution accuracy, and a propensity to fall into local optima. To address these limitations, I propose an enhanced version called the Nonlinear Normal Differential Sparrow Search Algorithm (NLN-DSSA). This algorithm incorporates an improved Circle chaotic mapping for population initialization, a nonlinear normal distribution coefficient to balance global exploration and local exploitation, and a differential mutation strategy to enhance population diversity and escape local optima. In this article, I will detail the methodology, validate its performance through benchmark functions, and demonstrate its practical application in path planning for quadrotor drones.
The Sparrow Search Algorithm (SSA) mimics the foraging and anti-predation behaviors of sparrow populations. In SSA, individuals are categorized into discoverers, followers, and vigilantes. Discoverers, with the best fitness, lead the search for food, and their position update is governed by specific rules. The position update for discoverers is defined as:
$$X_{i,j}^{t+1} =
\begin{cases}
X_{i,j}^{t} \cdot \exp\left(-\frac{i}{\alpha \cdot iter_{\max}}\right), & R_2 < ST \\
X_{i,j}^{t} + Q \cdot L, & R_2 \geq ST
\end{cases}$$
where \(iter_{\max}\) is the maximum number of iterations, \(t\) is the current iteration, \(\alpha\) is a random number in (0,1), \(R_2\) is an alarm value in [0,1], \(ST\) is a safety threshold in [0.5,1.0], \(Q\) is a random number following a normal distribution in [0,1], and \(L\) is a \(1 \times d\) matrix with all elements equal to 1. When \(R_2 < ST\), no danger is detected, and discoverers perform extensive searches; otherwise, they move to safer areas. Followers update their positions by monitoring discoverers:
$$X_{i,j}^{t+1} =
\begin{cases}
Q \cdot \exp\left(\frac{X_{\text{worst}}^{t} – X_{i,j}^{t}}{i^2}\right), & i > n/2 \\
X_{p}^{t+1} + |X_{i,j}^{t} – X_{p}^{t+1}| \cdot A^{+} \cdot L, & \text{otherwise}
\end{cases}$$
where \(X_{p}\) is the best position, \(X_{\text{worst}}\) is the worst position, and \(A\) is a \(1 \times d\) matrix with elements randomly set to 1 or -1, with \(A^{+} = A^{T}(AA^{T})^{-1}\). Vigilantes, which are aware of danger, update their positions based on fitness comparisons:
$$X_{i,j}^{t+1} =
\begin{cases}
X_{\text{best}}^{t} + \beta \cdot |X_{i,j}^{t} – X_{\text{best}}^{t}|, & f_i > f_g \\
X_{\text{best}}^{t} + k \cdot \left(\frac{X_{i,j}^{t} – X_{\text{best}}^{t}}{|f_i – f_w| + \epsilon}\right), & f_i = f_g
\end{cases}$$
where \(X_{\text{best}}\) is the current global best position, \(\beta\) is a step control parameter following a normal distribution with mean 0 and variance 1, \(k\) is a random number in [-1,1], \(f_i\) is the fitness of the current sparrow, \(f_g\) and \(f_w\) are the global best and worst fitness values, and \(\epsilon\) is a small constant to prevent division by zero. While SSA is effective, it requires enhancements for better performance in quadrotor drone path planning scenarios.
To overcome SSA’s limitations, I introduce NLN-DSSA with three key improvements. First, I use an improved Circle chaotic mapping for population initialization. The original Circle map is defined as:
$$x_{n+1} = \mod\left(x_n + a – \left(\frac{b}{2\pi} \sin(2\pi \cdot x_n)\right), 1\right)$$
where \(a\) and \(b\) are parameters typically set to 0.2 and 0.5. However, this map suffers from uneven distribution. I enhance it as follows:
$$x_{n+1} = \mod\left(x_n + a – \left(\frac{b}{4\pi} \sin(2\pi \cdot x_n) – \frac{b}{4\pi} \cos(2\pi \cdot x_n) + \text{rand}()\right), 1\right)$$
where \(\text{rand}()\) is a random number in [0,1]. This modification improves randomness and uniformity, leading to better population diversity and global exploration capability at the start of iterations. For a quadrotor drone path planning task, a well-initialized population can significantly reduce the time required to find feasible paths.
Second, I incorporate a nonlinear normal distribution coefficient to control the search step size and convergence speed of discoverers. This coefficient is defined as:
$$w = \frac{1}{\sqrt{2\pi (iter_{\max} / 3)}} \exp\left(-\frac{t^2}{2 (iter_{\max} / 3)^2}\right)$$
The updated discoverer position formula becomes:
$$X_{i,j}^{t+1} =
\begin{cases}
X_{i,j}^{t} + w \cdot \text{rand}(), & R_2 < ST \\
X_{i,j}^{t} + Q \cdot L, & R_2 \geq ST
\end{cases}$$
Here, \(w\) decreases nonlinearly with iterations, allowing for extensive global search early on and precise local exploitation later. This balance is crucial for optimizing paths for quadrotor drones, where both exploration of unknown areas and refinement of known routes are essential.
Third, I introduce a differential mutation strategy to increase population diversity and avoid local optima. This strategy generates a new individual by combining the global best with the difference between two randomly selected individuals:
$$X_{\text{new}} = X_{b}^{t} + \delta (X_{r1} – X_{r2})$$
where \(X_{r1}\) and \(X_{r2}\) are random sparrow individuals, and \(\delta\) is a scaling factor. A refraction opposition-based learning solution is then applied:
$$X^{*}_{\text{new}} = a + b – X_{\text{new}}$$
where \(a\) and \(b\) are bounds of the search space. The best individual is retained to maintain diversity. This strategy helps the algorithm escape local optima, which is vital for complex quadrotor drone environments with multiple obstacles.
To validate NLN-DSSA, I conduct simulation experiments using five benchmark test functions. The functions are listed in the table below, along with their dimensions, ranges, and optimal solutions.
| Function | Expression | Dimension | Range | Optimal Solution |
|---|---|---|---|---|
| Sphere | \(f_1(x) = \sum_{i=1}^{n} x_i^2\) | 30 | [-100, 100] | 0 |
| Schwefel 1.2 | \(f_2(x) = \sum_{i=1}^{n} \left( \sum_{j=1}^{i} x_j \right)^2\) | 30 | [-100, 100] | 0 |
| Schwefel 2.21 | \(f_3(x) = \max_i \{ |x_i|, 1 \leq i \leq n \}\) | 30 | [-100, 100] | 0 |
| Rastrigin | \(f_4(x) = \sum_{i=1}^{n} [x_i^2 – 10 \cos(2\pi x_i) + 10]\) | 30 | [-5.12, 5.12] | 0 |
| Griewank | \(f_5(x) = \frac{1}{4000} \sum_{i=1}^{n} x_i^2 – \prod_{i=1}^{d} \cos\left(\frac{x_i}{\sqrt{i}}\right) + 1\) | 30 | [-600, 600] | 0 |
I compare NLN-DSSA with other algorithms, including PSO, GWO, SSA, and improved variants like AMSSA, ISSA, and CSSA. The parameter settings for each algorithm are summarized in the following table.
| Algorithm | Parameter Settings |
|---|---|
| SSA | \(ST = 0.8\), \(PD = 0.2\), \(SD = 0.2\) |
| GWO | \(a\) linearly decreases from 2 to 0, \(r_1, r_2\) in [0,1] |
| PSO | \(W = 1\), \(W_{\text{damp}} = 0.99\), \(C_1 = 1.5\), \(C_2 = 2\), \(C = 0.01\), \(P = 0.8\) |
| AMSSA | \(ST = 0.8\), \(PD = 0.2\), \(SD = 0.2\), \(m = 2\) |
| CSSA | \(ST = 0.8\), \(PD = 0.2\), \(SD = 0.2\) |
| ISSA | \(ST = 0.8\), \(PD = 0.2\), \(SD = 0.2\), \(\theta = 0.005\) |
| NLN-DSSA | \(ST = 0.8\), \(PD = 0.2\), \(SD = 0.2\) |
The experiments are performed on a system with an AMD Ryzen 7 5800H processor at 2.90 GHz, using MATLAB. Each algorithm is run independently 30 times, and the average values and standard deviations are recorded. The results for the benchmark functions are presented in the table below.
| Function | Algorithm | Mean | Standard Deviation |
|---|---|---|---|
| \(f_1\) | GWO | \(1.9557 \times 10^{-27}\) | \(8.8351 \times 10^{-28}\) |
| SSA | \(9.3751 \times 10^{-56}\) | \(1.7116 \times 10^{-56}\) | |
| NLN-DSSA | 0 | 0 | |
| ISSA | \(2.2002 \times 10^{-277}\) | 0 | |
| CSSA | \(5.7633 \times 10^{-75}\) | \(3.1107 \times 10^{-53}\) | |
| PSO | \(7.8196 \times 10^{-26}\) | \(1.5387 \times 10^{-5}\) | |
| AMSSA | \(1.5362 \times 10^{-223}\) | \(2.5436 \times 10^{-132}\) | |
| \(f_2\) | GWO | \(1.0002 \times 10^{-32}\) | \(8.7154 \times 10^{-32}\) |
| SSA | \(2.9733 \times 10^{-47}\) | \(1.7780 \times 10^{-24}\) | |
| NLN-DSSA | 0 | 0 | |
| ISSA | \(1.5360 \times 10^{-196}\) | 0 | |
| CSSA | \(2.0120 \times 10^{-53}\) | \(5.6304 \times 10^{-27}\) | |
| PSO | \(7.3678 \times 10^{1}\) | \(3.0642 \times 10^{1}\) | |
| AMSSA | \(7.5360 \times 10^{-94}\) | \(1.8398 \times 10^{-77}\) | |
| \(f_3\) | GWO | \(1.5412 \times 10^{-19}\) | \(1.4808 \times 10^{-19}\) |
| SSA | \(2.7430 \times 10^{-40}\) | \(2.4192 \times 10^{-31}\) | |
| NLN-DSSA | 0 | 0 | |
| ISSA | \(6.7351 \times 10^{-163}\) | \(9.4688 \times 10^{-146}\) | |
| CSSA | \(4.1823 \times 10^{-38}\) | \(1.0472 \times 10^{-25}\) | |
| PSO | \(1.7636 \times 10^{-1}\) | \(2.8745 \times 10^{-2}\) | |
| AMSSA | \(3.5970 \times 10^{-89}\) | \(3.0418 \times 10^{-75}\) | |
| \(f_4\) | GWO | \(3.1741 \times 10^{0}\) | \(4.4121 \times 10^{0}\) |
| SSA | 0 | 0 | |
| NLN-DSSA | 0 | 0 | |
| ISSA | 0 | 0 | |
| CSSA | 0 | 0 | |
| PSO | \(6.1512 \times 10^{1}\) | \(1.5276 \times 10^{1}\) | |
| AMSSA | 0 | 0 | |
| \(f_5\) | GWO | \(4.3101 \times 10^{-3}\) | \(8.3812 \times 10^{-3}\) |
| SSA | 0 | 0 | |
| NLN-DSSA | 0 | 0 | |
| ISSA | 0 | 0 | |
| CSSA | 0 | 0 | |
| PSO | \(0.1320\) | \(3.2671 \times 10^{-2}\) | |
| AMSSA | 0 | 0 |
The results demonstrate that NLN-DSSA achieves superior convergence accuracy and stability compared to other algorithms. For unimodal functions like \(f_1\), \(f_2\), and \(f_3\), NLN-DSSA attains the theoretical optimum of 0 with zero standard deviation, indicating excellent exploitation capability. For multimodal functions like \(f_4\) and \(f_5\), NLN-DSSA also reaches the optimal solution, showcasing robust exploration ability. The convergence curves further illustrate that NLN-DSSA converges faster and more precisely than its counterparts, thanks to the balanced search strategy. In terms of time complexity, NLN-DSSA maintains the same order as SSA, \(O(d + f(d))\), where \(d\) is the dimension and \(f(d)\) is the time for evaluating the objective function. The improvements do not incur additional computational overhead, making NLN-DSSA efficient for real-time applications such as quadrotor drone path planning.
To further validate the practicality of NLN-DSSA, I apply it to path planning for a quadrotor drone. The environment is modeled as a 2D space with obstacles, where the quadrotor drone is represented as a point with a safety radius to avoid collisions. The start point is set at (0,0), and the goal point at (10,10). Obstacles are randomly generated, and the algorithm parameters include a population size of 30 and a maximum of 500 iterations. I compare NLN-DSSA with GWO, AMSSA, ISSA, and CSSA. The generated paths show that NLN-DSSA produces shorter and smoother routes with fewer turns, which is crucial for efficient navigation of quadrotor drones. The convergence curve for the path planning task confirms that NLN-DSSA achieves lower fitness values faster, indicating optimal path discovery. This application underscores the algorithm’s effectiveness in real-world scenarios where quadrotor drones must navigate complex environments safely and efficiently.
In conclusion, the proposed NLN-DSSA algorithm addresses the limitations of the standard SSA by incorporating an improved Circle chaotic mapping for population initialization, a nonlinear normal distribution coefficient for balanced search, and a differential mutation strategy for enhanced diversity. Simulation results on benchmark functions confirm that NLN-DSSA offers better convergence speed, higher solution accuracy, and improved robustness against local optima. The application to quadrotor drone path planning demonstrates its practical utility in generating optimal paths with minimal cost and time. Future work may involve extending NLN-DSSA to dynamic environments or multi-objective optimization for quadrotor drones. Overall, this enhanced algorithm provides a reliable tool for autonomous navigation systems in quadrotor drone operations.