A multi-strategy improved sparrow search algorithm for indoor AGV path planning

Abstract

To address the problems of weak search ability, easily falling into local optimal solutions and poor path quality of sparrow search algorithm in AGV path planning, a multi-strategy improved sparrow search algorithm (MISSA) is proposed in this paper. MISSA improves the global search ability by improving the discoverer position update operator and introducing the sine cosine algorithm; adopts the adaptive number of vigilantes and adaptive adjustment step size to improve the convergence speed; introduces the Levy flight variation strategy to reduce the probability of falling into any local optimal solution; optimizes the boundary handling mechanism to prevent the loss of population diversity at a later stage; finally, uses the large-scale neighborhood search strategy and path smoothing mechanism for path optimization to further improve the path quality. The superiority-seeking ability of MISSA was verified by 12 standard test functions, and then 30 simulation experiments were conducted in grid maps with two specifications of 20×20 and 30×30. The experimental results showed that, by using MISSA, the path length was reduced by 44.1% and 63.1%, the number of turns was reduced by 68.4% and 78.4%, and the risk degree was reduced by 61.3% and 77.2%, which verifies the superiority of MISSA in path planning. Finally, MISSA was ported to the QBot2e mobile robot for physical verification to prove its feasibility in practical applications.

Keywords

Path planning AGV sparrow search algorithm path smoothing

1 Introduction

Path planning is one of the crucial issues in the work of Automated guided vehicles (AGVs) [1]. The objective is to find the best and collision-free path from the starting point to the target point in a given environment [2]. The path-finding algorithm is the key to solving the path-planning problem [3]. Among them, the algorithm’s ability to find the best path and the quality of the searched path are critical indicators to evaluate the path-finding algorithm.

The traditional path-finding algorithms are the A* algorithm [4], Artificial potential field method [5, 6], Dijkstra algorithm [7], etc. Among them, A* algorithm and Dijkstra’s algorithm are mostly used for global path planning, and artificial potential field method is mostly used for local path planning. With the development of artificial intelligence technology, many intelligent bionic algorithms are widely used in path planning problems, such as the sparrow search algorithm (SSA) [8],genetic algorithm [9], ant colony algorithm [10, 11], gray wolf optimization algorithm [12], and hybrid path planning algorithms [13]. Among them, SSA has good search accuracy, convergence speed, and stability [14] and has been widely used in many fields, such as fault diagnosis, image processing, and UAV trajectory planning in recent years. For example, Fang [15] et al. proposed a new method for LightGBM fault diagnosis based on the optimization of the elite opposite sparrow search algorithm, Wu [16] et al. proposed an image threshold segmentation method based on an improved sparrow search algorithm, Yang [17] et al. apply the sparrow search algorithm to UAV trajectory planning.However, SSA suffers from weak global search capability [18], easily falling into local optimum [19], and poor path quality [20] in solving the AGV path planning problem. To address these problems, many scholars have made improvements. Among them, Li [21] used the K-medoids clustering method to enhance the population exchange and used the adaptive factor to improve the algorithm’s optimality finding ability; Zhang [22] et al. solved the problems of early convergence and population diversity reduction of the algorithm by using FDB selection and progressive search, and verified the excellent performance of the algorithm in path planning applications; Chen [23] et al. fused the A* algorithm with the sparrow search algorithm and used the ray method and Bessel curves to improve path smoothing; Ouyang [24] et al. used the adaptive spiral flight method to reduce the probability of the algorithm falling into a local optimal solution and applied it to robot path planning. Although various improved sparrow search algorithms have been applied to the path planning field, there is still much room for improving the quality of the paths searched for different environmental maps.

In this paper, in order to solve the problems of weak global search capability, easy to fall into local optimum, and poor path quality of sparrow search algorithm in AGV path planning, the sparrow search algorithm is improved from two aspects. On the one hand, the performance of the sparrow search algorithm itself is improved in the following way:

Improving the global search capability of the algorithm with a new finder position update operator and fused sine-cosine algorithm;

Adopting adaptive number of vigilantes and adaptive step size to accelerate the convergence speed of the algorithm;

Introducing Levy flight variation to reduce the probability of falling into a local optimum solution;

By optimizing the boundary processing mechanism, prevent the loss of population diversity in the later stages of the algorithm;

On the other hand, the path quality is improved in the following way:

Using large-scale neighborhood search after obtaining the complete path strategy and path smoothing mechanism is used to improve the path quality and smoothness.

Then we verified the optimization ability of this paper’s algorithm by comparing and analyzing the 12 standard test functions with other intelligent optimization algorithms, and carried out grid map simulation experiments by using MATLAB to verify the superiority of this paper’s algorithm in path planning. Finally, the proposed algorithm was ported to QBot2e mobile robot for physical verification, which proved the feasibility of the improved algorithm in practical applications.

The rest of the paper is organized as follows: The second part introduces the SSA. The third part presents the details of the MISSA improvement. The fourth part verifies the merit-seeking capability of MISSA by 12 standard test functions. The fifth part conducts path planning simulation experiments on different environment maps and performs physical verification. The sixth part summarizes the work of this paper and the outlook.

2 The basic sparrow search algorithm

SSA is proposed based on sparrows’ foraging and anti-feeding behavior. The entire sparrow population consists of three types of individuals: discoverers, joiners, and vigilantes. Among them, discoverers account for 20% of the entire population, responsible for finding food and providing feeding directions for other sparrows; the other 80% are joiners, who use the discoverers to obtain food; and the vigilantes, who can be both discoverers and joiners, account for 10–20% of the whole population. SSA is to find the optimal value of the optimization problem by continuously adjusting the positions of these three sparrows.

In SSA, the discoverers position update formula is: $x_{i, j}^{t + 1} = {\begin{matrix} x_{i, j}^{t} \cdot \exp (- \frac{i}{α \cdot {iter}_{max}}), & if R_{2} < ST \\ x_{i, j}^{t} + Q \cdot L, & if R_{2} > ST \end{matrix}$ (1) where, t denotes the current number of iterations, $x_{i, j}^{t}$ denotes the position of the sparrow at moment t, iter_max denotes the maximum number of iterations, α ∈ [0, 1] and Q is a random number with normal distribution. R₂ ∈ [0, 1] is the warning value and ST ∈ [0.5, 1] is the safety value.

The joiners position update formula is: $x_{i, j}^{t + 1} = {\begin{matrix} Q \cdot \exp (\frac{x_{worst} - x_{i, j}^{t}}{i^{2}}), & if i > \frac{n}{2} \\ x_{p}^{t + 1} + | x_{i, j}^{t} - x_{p}^{t + 1} | \cdot A^{+} \cdot L, & otherwise \end{matrix}$ (2) where, x_p denotes the current optimal position of the discoverer, x_worst denotes the current global worst position. A is a matrix with elements –1 or 1, A⁺ = A^T (AA^T) ^-1.

The vigilantes position update formula is: $x_{i, j}^{t + 1} = {\begin{matrix} x_{best}^{t} + β \cdot | x_{i, j}^{t} - x_{best}^{t} |, & if f_{i} > f_{g} \\ x_{i, j}^{t} + K \cdot (\frac{x_{i, j}^{t} - x_{worst}^{t}}{(f_{i} - f_{ω}) + ɛ}), & if f_{i} = f_{g} \end{matrix}$ (3) where, $x_{best}^{t}$ denotes the current global optimal position, β denotes the step size, which is a random number that follows a normal distribution with mean 0 and variance 1, K ∈ [-1, 1], f_i denotes the fitness value of the i-th sparrow, f_g and f_w denotes the current optimal fitness value and the current worst fitness value, ɛ is a very small constant that prevents zero from appearing in the denominator.

3 Multi-strategy improved sparrow search algorithm

This section optimizes SSA for the problems of SSA in path planning. There are two aspects of optimization. One is to improve the performance of SSA itself, including global search capability, convergence speed and reducing the probability of falling into a local optimum solution; the other is to improve the path quality. In addition, we provide pseudocode to allow simulation platforms to test MISSA.

3.1 Improved discoverer position update formula

In SSA, if R₂ < ST, the discoverers position is updated by the $exp (- \frac{i}{{iter}_{max}})$ operator, but the size of this operator is usually between [0.9,1], which affects the global search capability of the algorithm [25]. Therefore, in this paper, a new update operator is used: $\exp (\frac{t - M}{M}) \cdot \cos (l \cdot \frac{π}{2})$ (4)

where, t denotes the current number of iterations, M denotes the maximum number of iterations, and l is a random number between [–1,1].

The range of values of the new operator is shown in Fig. 1. As the number of iterations increases, the value of the operator is slowly increased. This ensures the search range in the early stage, and at the same time has good search accuracy in the later stage.

Fig. 1

The range of values of the new operator.

If R₂ > ST, the discoverers are updated by adding a normally distributed random number to each dimension. This method affects the convergence speed of the algorithm in applications with an extensive search range, and the update method does not refer to the positions of other individuals, which is not conducive to the exchange of information between populations [26]. The sine cosine algorithm increases the communication between populations when individuals are updated, and has better global optimization ability [27]. Therefore, this paper combines the sine cosine algorithm to update the discoverer position when R₂ > ST, which is given by:

$x_{i, j}^{t + 1} = {\begin{matrix} x_{i, j}^{t} + \sin (r_{2}) \cdot | r_{3} \cdot x_{best} - x_{i, j}^{t} |, & if r_{4} < 0.5 \\ x_{i, j}^{t} + \cos (r_{2}) \cdot | r_{3} \cdot x_{best} - x_{i, j}^{t} |, & if r_{4} > 0.5 \end{matrix}$ (5) where, $r_{1} = 2 - \frac{2 t}{M}$ , r₂ ∈ [0, 2π], r₃ ∈ [0, 2], r₄ ∈ [0, 1].

The formula for updating the position of the improved discoverer is as follows: $x_{i, j}^{t + 1} = {\begin{matrix} x_{i, j}^{t} \cdot \exp (\frac{t - M}{M}) \cdot \cos (l \cdot \frac{π}{2}), & if R_{2} < ST \\ x_{i, j}^{t} + r_{1} \cdot \sin (r_{2}) \cdot | r_{3} \cdot x_{best} - x_{i, j}^{t} |, & if r_{4} < 0.5 and R_{2} > ST \\ x_{i, j}^{t} + r_{1} \cdot \cos (r_{2}) \cdot | r_{3} \cdot x_{best} - x_{i, j}^{t} |, & if r_{4} > 0.5 and R_{2} > ST \end{matrix}$ (6)

3.2 Improved vigilante position update formula

In SSA, 10% – 20% of the sparrows will become vigilantes. Their role is to help the population find a better solution and prevent the population from falling into a local optimum solution [28]. If the number of vigilantes is large, it would improve the global search capability of the algorithm and reduce the probability of falling into local optimal solutions, but the stability and convergence speed of the algorithm would be affected; if the number of vigilantes is small, it would increase the convergence speed and stability of the algorithm, but it might increase the probability of falling into a local optimum [29]. In SSA, the number of vigilantes is fixed, and this kind will affect the convergence speed and the optimality-seeking ability of the algorithm. Therefore, this paper adopts the method of an adaptive number of vigilantes as follows: $SD = {SD}_{max} - round [({SD}_{max} - {SD}_{min}) \cdot \frac{t}{M}]$ (7) where, SD_max and SD_min are the maximum and minimum number of vigilantes, respectively.

In Equation (3), the vigilantes should move quickly to the optimal individual when f_i > f_g, thus speeding up the algorithm’s convergence. However, in SSA, the step size is random, so in order to speed up the convergence speed and convergence accuracy of the algorithm, the adaptive step size adjustment is used in this paper as follows [30]: $β = \sin ({(\frac{t}{M})}^{2} \cdot π)$ (8)

The adaptive step size variation is shown in Fig. 2.

Fig. 2

Step length variation.

In Fig. 2, the adaptive step size gradually increases with the number of iterations at the beginning of the algorithm and starts to decrease gradually in the middle and later stages, which could speed up the convergence speed in the early and late stages of the algorithm and reduce the risk of falling into local optimal solutions in the middle stage.

3.3 Levy flight variation

SSA has the drawback of easily falling into local optimal solutions. In order to reduce the probability of the algorithm falling into an optimal local solution, this paper introduces the Levy flight variant strategy into the sparrow search algorithm. Levy flight [31] are random step wanderings that obey the Levy distribution and can switch between short and occasionally long steps. The step length of Levy flight can be simulated according to the Mantegna algorithm, and the step length can be expressed as: $levy = \frac{μ}{{| ν |}^{1 / - β}}$ (9) where, β is generally taken to be 1.5. μ and ν are positive-terms distributions satisfying $N = (0, σ_{μ}^{2})$ , $N = (0, σ_{ν}^{2})$ with standard deviation σ_μ and σ_ν defined as follows: $σ_{μ} = {(\frac{Γ (1 + β) \cdot \sin (β \cdot \frac{π}{2})}{Γ (\frac{(1 + β)}{2}) \cdot β \cdot 2^{(β - 1) / - 2}})}^{1 / - β}$ (10) $σ_{ν} = 1$ (11) where, Γ denotes the Gamma function.

At the end of each algorithm iteration, individuals with poor adaptation are selected for Levy flight variation. The update is performed as follows: $x_{i, j}^{' t} = x_{i, j}^{t} + | x_{best} - x_{i, j}^{t} | \cdot levy$ (12) where, $x_{i, j}^{' t}$ is the position after mutation.

3.4 Boundary constraint mechanism

After each algorithm iteration, sparrow individuals would exist beyond the search range. In SSA, the sparrow individuals beyond the search range would be arranged on the boundary of the search range, which would cause a large number of sparrow individuals to gather on the search boundary at the later stage of the algorithm, resulting in the loss of population diversity and seriously affecting the convergence speed of the algorithm [32]. To solve this problem, the original boundary handling mechanism of the algorithm is optimized in this paper as follows: ${\begin{matrix} x_{i, j}^{'} = (x_{i, j} - U_{b}) + L_{b}, & if x_{i, j} > U_{b} \\ x_{i, j}^{'} = (x_{i, j} - L_{b}) + U_{b}, & if x_{i, j} < L_{b} \end{matrix}$ (13) where, $x_{i, j}^{'}$ is the new position after the boundary constraint. U_b and L_b are the upper and lower limits of the search range.

If the new location of the individual sparrow is still out of the search range, the location of the sparrow is updated using a random distribution to ensure further that the location of the individual sparrow is within the search range in the following manner: $x_{i, j}^{'} = U_{b} - (U_{b} - L_{b}) \cdot rand$ (14)

3.5 Large-scale neighborhood search

To address the problem of the low search capability of SSA in solving path planning problems, the large-scale neighborhood search strategy (LNS) [33] is introduced in this paper. In this paper, after each iteration of the algorithm, LNS is performed on the optimal individual to further reduce the fitness. The schematic diagram is shown in Fig. 3 (with a 10-dimensional path as an example). Firstly, the path points of the original path are randomly deleted by using the damage operator; then, new path points are reinserted by the repair operator, which is the set of all possible path points in the damaged dimension. The new path obtained after the repair is called the neighborhood solution. The fitness of the neighborhood solution is calculated, and if it is better than the original solution, it isretained.

Fig. 3

Schematic diagram of large neighborhood search strategy.

3.6 Path smoothing

After the complete path is obtained by using SSA, there are often some redundant points, resulting in poor smoothness of the path, which leads to too many turns in practical applications and seriously affects the efficiency of the AGV [34]. Therefore, it is necessary to smooth the path searched by the algorithm. In this paper, we introduce the idea of Dijkstra’s algorithm to optimize the paths. This algorithm is a typical algorithm for solving the shortest path, which is used to calculate the shortest path from a node to other nodes, eliminate the redundant points between two nodes and improve the smoothness of the path.

The schematic diagram of path smoothing in this paper is shown in Fig. 4. Firstly, point A and point C are taken as the i-th node and the i + 2-st node, respectively, with coordinates A (x_i, y_i) and C (x_i+2, y_i+2). Then, determine the obstacles that exist in the range surrounded by points A and C, and the coordinates of the center of the obstacles are D (x_z, y_z). Finally, calculate the distance d between point D and the line connecting point A and point C. If $d ⩾ \frac{\sqrt{2}}{2}$ , it means that the robot can pass safely, i.e., the i + 1st node B can be deleted.

Fig. 4

Schematic diagram of path smoothing.

The effect of smoothing the path is achieved by traversing all the path points from the start of the path and removing the redundant nodes.

The result is shown in Fig. 5, where the original path searched by the algorithm is A → B → C → D. After the path smoothing process, the path becomes A → D. It can be seen that the path after smoothing process not only increases the smoothness but also shortens the path length.

Fig. 5

Path smoothing result.

3.7 Algorithmic process

Algorithm 1 gives the MISSA pseudocode for path planning. Lines 1 through 21 show the iterative process of MISSA. Path smoothing is performed once after each sparrow obtains the latest position as a way to reduce the path length, and the condition is stopped and the optimal value is returned when the maximum number of iterations is reached.

Algorithm 1 Pseudocode for path planning using MISSA
Input: M: the maximum iterations
PD: the number of discoverers
SD: the number of vigilantes
R₂: the alarm value
n: the number of sparrows
Output: x_best, f_g
1.whilet < M do
2. Rank the fitness values and find the current best individual
and the current worst individual.
3. R₂ = rand(1)
4. fori = 1: PD do
5. Using Equation (6) update the discoverer location;
6. Path smoothing;
7. end for
8. fori = (PD+1): n do
9. Using equation (2) update the joiner location;
10. Path smoothing;
11. end for
12. fori = 1: SD do
13. Using Equations (3) and (8) update the vigilantes location;
14. Path smoothing;
15. end for
16. Levy flight variation for less well-adapted individuals;
17. LNS for Optimal Individuals;
18. Get the current new location;
19. If the new location is better than before, update it;
20. t = t+1
21.end while
22.return x_best, f_g

4 Algorithm performance verification and result analysis

This section compares the optimization search results of MISSA with SSA, other improved versions of SSA, and three other intelligent optimization algorithms on 12 standard test functions, and verifies the superiority of MISSA performance through parameter statistics.

4.1 Test functions

In order to verify the optimization-seeking ability of MISSA, 12 standard test functions [35] are selected for simulation analysis in this paper. Table 1 gives the test function expressions, search range, dimensionality, and theoretical optimal values. MISSA is compared with other SSA improved versions (ISSA) [36], SSA, whale optimization algorithm (WOA) [37], gray wolf optimization algorithm (GWO) [38], and particle swarm optimization algorithm (PSO) [39]. The main parameter settings for each algorithm are given in Table 2. Considering chance in experimental results, the population size of each algorithm is set to 100 in this paper, the same initialized population, and each test function is run 30 times independently. The maximum number of iterations is 500, and the optimal value, mean, and standard deviation of the 30 experimental test functions are compared. Simulation environment: MATLAB R2019a, Win10 OS, processor AMD Ryzen5 3500U, CPU 2.40 GHz, memory 8GB.

Table 1
Test functions

Test functions Dimensions Search Range Optimal value

$F_{1} = \sum_{i = 1}^{n} x_{i}^{2}$ 30 [–100,100] 0

$F_{2} = \sum_{i = 1}^{n} | x_{i} | + \prod_{i = 1}^{n} | x_{i} |$ 30 [–10,10] 0

$F_{3} = \sum_{i = 1}^{n} {(\sum_{j = 1}^{i} x_{j})}^{2}$ 30 [–100,100] 0

F₄ = max{ |x_i|, 1 ⩽ i ⩽ n } 30 [–100,100] 0

$F_{5} = \sum_{i = 1}^{n - 1} [100 {(x_{i + 1} - x_{i}^{2})}^{2} + (x_{i} - 1)^{2}]$ 30 [–30,30] 0

$F_{6} = \sum_{i = 1}^{n} {ix}_{i}^{4} + random [0, 1)$ 30 [–1.28,1.28] 0

$F_{7} = \sum_{i = 1}^{n} [x_{i}^{2} - 10 cos (2 π x_{i}) + 10]$ 30 [–5.12,5.12] 0

$F_{8} = \sum_{i = 1}^{n} | x_{i} sin (x_{i}) + 0.1 x_{i} |$ 30 [–10,10] 0

$F_{9} = \sum_{i = 1}^{n} \frac{x_{i}^{2}}{4000} - \sum_{i = 1}^{n} cos \frac{x_{i}}{\sqrt{i}} + 1$ 30 [–600,600] 0

$F_{10} = - 20 exp (- 0.2 \sqrt{\frac{1}{n} \sum_{i = 1}^{n} x_{i}^{2}}) - exp (\frac{1}{n} \sum_{i = 1}^{n} cos (2 π x_{i})) + 20 + e$ 30 [–32,32] 0

$F_{11} = \sum_{i = 1}^{n} [(x_{i} - 1)^{2} + (x_{1} - x_{i}^{2})^{2}]$ 30 [0,10] 0

$F_{12} = {(\frac{1}{500} + \sum_{j = 1}^{25} \frac{1}{j + \sum_{i = 1}^{2} (x_{i} - a_{ij})^{6}})}^{- 1}$ 2 [–65.5,65.5] 1

Test functions	Dimensions	Search Range	Optimal value
$F_{1} = \sum_{i = 1}^{n} x_{i}^{2}$	30	[–100,100]	0
$F_{2} = \sum_{i = 1}^{n} \| x_{i} \| + \prod_{i = 1}^{n} \| x_{i} \|$	30	[–10,10]	0
$F_{3} = \sum_{i = 1}^{n} {(\sum_{j = 1}^{i} x_{j})}^{2}$	30	[–100,100]	0
F₄ = max{ \|x_i\|, 1 ⩽ i ⩽ n }	30	[–100,100]	0
$F_{5} = \sum_{i = 1}^{n - 1} [100 {(x_{i + 1} - x_{i}^{2})}^{2} + (x_{i} - 1)^{2}]$	30	[–30,30]	0
$F_{6} = \sum_{i = 1}^{n} {ix}_{i}^{4} + random [0, 1)$	30	[–1.28,1.28]	0
$F_{7} = \sum_{i = 1}^{n} [x_{i}^{2} - 10 cos (2 π x_{i}) + 10]$	30	[–5.12,5.12]	0
$F_{8} = \sum_{i = 1}^{n} \| x_{i} sin (x_{i}) + 0.1 x_{i} \|$	30	[–10,10]	0
$F_{9} = \sum_{i = 1}^{n} \frac{x_{i}^{2}}{4000} - \sum_{i = 1}^{n} cos \frac{x_{i}}{\sqrt{i}} + 1$	30	[–600,600]	0
$F_{10} = - 20 exp (- 0.2 \sqrt{\frac{1}{n} \sum_{i = 1}^{n} x_{i}^{2}}) - exp (\frac{1}{n} \sum_{i = 1}^{n} cos (2 π x_{i})) + 20 + e$	30	[–32,32]	0
$F_{11} = \sum_{i = 1}^{n} [(x_{i} - 1)^{2} + (x_{1} - x_{i}^{2})^{2}]$	30	[0,10]	0
$F_{12} = {(\frac{1}{500} + \sum_{j = 1}^{25} \frac{1}{j + \sum_{i = 1}^{2} (x_{i} - a_{ij})^{6}})}^{- 1}$	2	[–65.5,65.5]	1

Table 2

Parameter setting

Algorithm	Parameters
MISSA	ST = 0.8, PD = pop× 20 % , SD_max = pop × 20 % , SD_min = pop × 10 %
SSA	ST = 0.8, PD = pop× 20 % , SD = pop × 10 %
PSO	w_max = 0.9, w_min = 0.4, c1 = c2 = 1.49445
GWO	r₁, r₂ ∈ [0, 1], a decrease linearly from 2 to 0
WOA	r₁, r₂ ∈ [0, 1] , p ∈ [0, 1], a decrease linearly from 2 to 0

4.2 Results analysis

Table 3 shows the search results of the five algorithms on the 12 standard test functions. From the analysis of the optimization accuracy, MISSA,ISSA and SSA can find the theoretical optimal values on the seven test functions of F₁ ∼ F₄, F₇ ∼ F₉, and the optimization accuracy is significantly better than the other three algorithms, and MISSA does not find the theoretical optimal values on the three test functions of F₅, F₆, F₁₁, but the optimization accuracy is 1 9 orders of magnitude higher than that of ISSA and SSA. From the average value obtained in 30 experiments, MISSA not only finds the theoretical optimal value in the four test functions of F₂ ∼ F₄, F₈, but also the average value is 0, which is 190–280 orders of magnitude higher than that of SSA, and the average value in F₅, F₆, F₁₁, F₁₂, is also better than that of ISSA and SSA and other three algorithms. From the stability analysis, the standard deviation of MISSA on F₅, F₆, F₁₁, F₁₂ is better than that of ISSA, SSA and the other three algorithms, and the results on the other test functions are consistent with those of ISSA and SSA but better than those of the other three algorithms. Figure 6 shows the convergence curves of the function values of the five algorithms on the 12 test functions, and it can be seen that the convergence speed of MISSA on F₁ ∼ F₁₀ is better than that of SSA and the other three algorithms.

Table 3
Experimental results

Function Index PSO GWO WOA SSA ISSA MISSA

F1 Best 3.28E–01 3.45E–42 1.05E–103 0 0 0

Mean 1.71E+00 6.29E–41 5.46E–96 0 0 0

Std 1.15E+00 7.69E–41 2.46E–95 0 0 0

F2 Best 1.40E+00 1.15E–24 2.25E–62 0 0 0

Mean 3.30E+00 4.62E–24 2.09E–56 1.62E–217 0 0

Std 7.24E–01 2.56E–24 5.86E–56 0 0 0

F3 Best 1.45E+01 2.58E–14 1.99E+04 0 0 0

Mean 5.24E+01 1.82E–11 2.37E+04 2.61E–288 0 0

Std 6.02E+01 4.34E–11 3.23E+03 0 0 0

F4 Best 4.88E–01 2.82E–11 1.73E–14 0 0 0

Mean 1.11E+00 1.98E–10 7.71E+00 1.86E–225 0 0

Std 4.21E–01 1.67E–10 9.45E+00 0 0 0

F5 Best 6.16E+01 2.49E+01 2.62E+01 1.96E–11 2.09E–06 1.78E–15

Mean 2.27E+02 2.64E+01 2.67E+01 8.13E–06 1.13e+00 7.15E–07

Std 1.56E+02 6.76E–01 2.73E–01 1.44E–05 2.53E+00 1.54E–06

F6 Best 3.38E–02 1.48E–04 3.60E–06 1.46E–05 1.24E–05 1.03E–06

Mean 2.93E–01 6.20E–04 1.02E–03 1.68E–04 6.61E–05 4.85E–05

Std 2.79E–01 3.29E–04 9.36E–04 1.31E–04 5.92E–05 4.57E–05

F7 Best 2.12E+01 0 0 0 0 0

Mean 7.82E+01 3.76E–01 0 0 0 0

Std 3.82E+01 1.17E+00 0 0 0 0

F8 Best 5.10E–02 1.22E–23 8.63E–64 0 0 0

Mean 5.59E–01 2.04E–04 5.16E–59 9.17E–191 0 0

Std 2.88E–01 4.55E–04 9.45E–59 0 0 0

F9 Best 3.11E–01 0 0 0 0 0

Mean 5.58E–01 9.80E–04 1.02E–03 0 0 0

Std 1.34E–01 3.74E–03 5.60E–03 0 0 0

F10 Best 1.04E+00 2.22E–14 8.88E–16 8.88E–16 8.88E–16 8.88E–16

Mean 1.83E+00 2.80E–14 4.68E–15 8.88E–16 8.88E–16 8.88E–16

Std 4.24E–01 2.72E–15 2.27E–15 0 0 0

F11 Best 9.48E+00 1.76E+00 1.11E–02 1.871E–11 1.39E–12 8.09E–14

Mean 1.43E+01 3.92E+00 1.13E+00 5.84E–08 2.82E–02 1.60E–07

Std 2.39E+00 1.85E+00 2.02E+00 8.90E–08 7.46E–02 3.15E–07

F12 Best 9.98E–01 9.98E–01 9.98E–01 9.98E–01 9.98E–01 9.98E–01

Mean 1.86E+00 3.48E+00 1.32E+00 5.15E+00 1.39E+00 9.98E–01

Std 5.04E–01 3.80E+00 1.78E+00 5.57E+00 2.13E+00 1.43E–11

Function	Index	PSO	GWO	WOA	SSA	ISSA	MISSA
F1	Best	3.28E–01	3.45E–42	1.05E–103	0	0	0
	Mean	1.71E+00	6.29E–41	5.46E–96	0	0	0
	Std	1.15E+00	7.69E–41	2.46E–95	0	0	0
F2	Best	1.40E+00	1.15E–24	2.25E–62	0	0	0
	Mean	3.30E+00	4.62E–24	2.09E–56	1.62E–217	0	0
	Std	7.24E–01	2.56E–24	5.86E–56	0	0	0
F3	Best	1.45E+01	2.58E–14	1.99E+04	0	0	0
	Mean	5.24E+01	1.82E–11	2.37E+04	2.61E–288	0	0
	Std	6.02E+01	4.34E–11	3.23E+03	0	0	0
F4	Best	4.88E–01	2.82E–11	1.73E–14	0	0	0
	Mean	1.11E+00	1.98E–10	7.71E+00	1.86E–225	0	0
	Std	4.21E–01	1.67E–10	9.45E+00	0	0	0
F5	Best	6.16E+01	2.49E+01	2.62E+01	1.96E–11	2.09E–06	1.78E–15
	Mean	2.27E+02	2.64E+01	2.67E+01	8.13E–06	1.13e+00	7.15E–07
	Std	1.56E+02	6.76E–01	2.73E–01	1.44E–05	2.53E+00	1.54E–06
F6	Best	3.38E–02	1.48E–04	3.60E–06	1.46E–05	1.24E–05	1.03E–06
	Mean	2.93E–01	6.20E–04	1.02E–03	1.68E–04	6.61E–05	4.85E–05
	Std	2.79E–01	3.29E–04	9.36E–04	1.31E–04	5.92E–05	4.57E–05
F7	Best	2.12E+01	0	0	0	0	0
	Mean	7.82E+01	3.76E–01	0	0	0	0
	Std	3.82E+01	1.17E+00	0	0	0	0
F8	Best	5.10E–02	1.22E–23	8.63E–64	0	0	0
	Mean	5.59E–01	2.04E–04	5.16E–59	9.17E–191	0	0
	Std	2.88E–01	4.55E–04	9.45E–59	0	0	0
F9	Best	3.11E–01	0	0	0	0	0
	Mean	5.58E–01	9.80E–04	1.02E–03	0	0	0
	Std	1.34E–01	3.74E–03	5.60E–03	0	0	0
F10	Best	1.04E+00	2.22E–14	8.88E–16	8.88E–16	8.88E–16	8.88E–16
	Mean	1.83E+00	2.80E–14	4.68E–15	8.88E–16	8.88E–16	8.88E–16
	Std	4.24E–01	2.72E–15	2.27E–15	0	0	0
F11	Best	9.48E+00	1.76E+00	1.11E–02	1.871E–11	1.39E–12	8.09E–14
	Mean	1.43E+01	3.92E+00	1.13E+00	5.84E–08	2.82E–02	1.60E–07
	Std	2.39E+00	1.85E+00	2.02E+00	8.90E–08	7.46E–02	3.15E–07
F12	Best	9.98E–01	9.98E–01	9.98E–01	9.98E–01	9.98E–01	9.98E–01
	Mean	1.86E+00	3.48E+00	1.32E+00	5.15E+00	1.39E+00	9.98E–01
	Std	5.04E–01	3.80E+00	1.78E+00	5.57E+00	2.13E+00	1.43E–11

Fig. 6

Convergence curve of test functions.

In a comprehensive analysis, the MISSA given in this paper outperforms SSA in terms of optimization accuracy, convergence speed and stability performance, and has better optimization capability.

The mean and standard deviation of the 30 independent runs alone do not fully illustrate the superiority of MISSA [40]; statistical tests are required. To reflect fairness, this paper uses Wilcoxon rank sum test to verify whether the results of each run of MISSA are significantly different from other algorithms at the p = 5% significance level. While p < 5%,indicating that there is a significant difference between the two algorithms; while p > 5%, indicating that the difference between the two algorithms is not obvious, i.e., the two algorithms are comparable in terms of their performance of optimization search.

From Table 4, it can be seen that most of the p-values between MISSA and the three algorithms GWO, WOA and PSO are less than 5% in the 12 standard test functions, indicating that there is a significant difference between MISSA and these three algorithms. p-values between MISSA and ISSA are less than 5% in three functions, and the significant difference in the other functions is not obvious, and the optimization performance is comparable. p-values between MISSA and SSA are less than 5% in the seven the p-value is less than 5% on the number of functions, indicating that the superiority of MISSA is statistically significant.

Table 4

Wilcoxon rank test p values

	MISSA-ISSA	MISSA-SSA	MISSA-WOA	MISSA-GWO	MISSA-PSO
F1	N/N	N/N	1.21E–12	1.21E–12	1.21E–12
F2	N/N	1.46E–04	1.21E–12	1.21E–12	1.21E–12
F3	N/N	3.34E–01	1.21E–12	1.21E–12	1.21E–12
F4	N/N	1.1E–02	1.21E–12	1.21E–12	1.21E–12
F5	4.08E–11	6.91E–04	3.02E–11	3.02E–11	3.02E–11
F6	9.71E–01	1.87E–05	1.43E–08	3.34E–11	3.02E–11
F7	N/N	N/N	N/N	1.91E–06	1.21E–12
F8	N/N	1.27E–05	1.21E–12	1.21E–12	1.21E–12
F9	N/N	N/N	3.34E–01	1.61E–01	1.21E–12
F10	N/N	N/N	3.04E–10	3.17E–13	1.21E–12
F11	8.12E–04	3.2E–03	3.02E–11	3.02E–11	3.02E–11
F12	3.16E–10	7.8E–03	1.22E–01	1.29E–09	5.89E–05

5 Simulation and experimental verification

This section utilizes the simulation results obtained by MISSA on two different specifications of grid maps to simulate and compare other algorithms by using three evaluation indicators. MISSA is then ported to actual AGV for practical application to verify the feasibility and superiority of the algorithm.

5.1 Environmental maps

In this paper, two sizes of grid maps, 20×20 and 30×30, are used as the experimental environment maps. As shown in Fig. 7. The length of each grid is 1, where the black area represents the obstacle, the white area represents the passable area, and the starting and ending points of the path are at the positions (0,0) and (20,20) or (30,30) respectively.

5.2 Path evaluation indicators

The most direct evaluation index of the path planning problem is the path length, but a single evaluation index does not indicate the superiority of the algorithm. Therefore, this paper adds three evaluation indexes, namely risk degree, number of turns, and turn angle.

The path planning problem calculates the path length by the fitness function. The expression of the fitness function is: $f = \sum_{i = 1}^{n} \sqrt{(x_{i + 1} - x_{i})^{2} + (y_{i + 1} - y_{i})^{2}}$ (15) where, n is the total number of path points, (x, y) is the coordinates of the path points.

Fig. 7

Environmental maps.

The number of turns and the angle of turns are the indicators to evaluate the smoothness of the path. A smooth path can increase the efficiency of AGV but also reduce the wear and tear of AGV itself.

In the traditional path planning problem, there would be a situation that the path intersects with the boundary of the obstacle area, and there would be a certain risk potential when the AGV carries out the trajectory tracking, so this paper introduces the risk degree as an index to evaluate the path safety. Risk degree refers to the number of times that the planned path intersects with the boundary of the obstacle area. In Fig. 8(a), the path intersects with the obstacle boundary once, which means the risk degree is 1; In Fig. 8(b), the path intersects with the obstacle boundary twice, which means the risk degree is 2. The lower the total risk degree of the whole path, the higher of the path safety.

Fig. 8

Schematic diagram of risk degree.

5.3 Simulation results and analysis

In this paper, path search was performed on two maps using SSA, MISSA, and reference [8] algorithms (ISSA), respectively. To avoid experimental chance, each algorithm is executed 30 times and evaluated comprehensively according to the path evaluation metrics. Simulation environment: MATLAB R2019a, Win10 OS, processor AMD Ryzen5 3500U, CPU 2.40 GHz, memory 8GB. The parameter settings for each algorithm are shown in Table 5.

Table 5
Parameter setting

Algorithm Parameters

MISSA ST = 0.8, PD = pop× 20 % , SD_max = pop × 20 % , SD_min = pop × 10 %

ISSA ST = 0.8, PD = pop× 20 % , SD = pop × 10 %

SSA ST = 0.8, PD = pop× 20 % , SD = pop × 10 %

Algorithm	Parameters
MISSA	ST = 0.8, PD = pop× 20 % , SD_max = pop × 20 % , SD_min = pop × 10 %
ISSA	ST = 0.8, PD = pop× 20 % , SD = pop × 10 %
SSA	ST = 0.8, PD = pop× 20 % , SD = pop × 10 %

5.3.1 20×20 environment map

Figure 9 shows the shortest paths obtained by the three algorithms under the 20×20 environment map, and Fig. 10 shows the convergence of MISSA compared with ISSA. It can be seen from Fig. 9 that the paths searched by SSA are of low quality, with a high number of turns, too many redundant nodes, and high danger, which is not conducive to the practical application of AGVs. MISSA compares with the shortest paths obtained by SSA and ISSA. The path length obtained by MISSA is shorter, with fewer turns and lower risk, which shows the superior performance of MISSA.

Fig. 9

Three algorithms for shortest path in 20×20 environment map.

Fig. 10

Comparison of algorithm convergence curves.

Table 6 shows the results of 30 simulations of the 20×20 environment map. Table 6 shows that MISSA outperforms SSA and ISSA in terms of path length, number of turns, turn angle, and risk degree. By comparison, compared with SSA and ISSA, the path length obtained by MISSA is reduced by 44.1% and 1.9%, the number of turns is reduced by 68.4% and 17%, the turn angle is reduced by 79.1% and 7.0%, and the risk degree is reduced by 61.3% and 51.1%, respectively. The path quality obtained by MISSA is higher in comprehensive analysis.

Table 6

Simulation results of 20×20 environment map

		SSA	ISSA	MISSA
Path length	Worst	63.2132	33.2652	30.4555
	Best	40.6274	28.492	28.4136
	Mean	52.1909	29.7632	29.1910
Number of turns	Max	32	13	10
	Min	15	5	5
	Mean	23.1	8.8	7.3
turn angle	Max	2070	548.1301	451.3972
	Min	990	163.0725	135
	Mean	1510.5	340.3345	316.4193
risk degree	Max	11	8	8
	Min	3	3	1
	Mean	7.4	5.8667	2.8667
Iteration number	Max	–	79	198
	Min	–	2	21
	Mean	–	28.2667	100.8667

Table 7

Simulation results of 30 × 30 environment map

		SSA	ISSA	MISSA
Path length	Worst	124.2843	51.8255	45.1197
	Best	84.1838	37.0548	36.9441
	Mean	106.333	41.6750	39.1860
Number of turns	Max	49	20	11
	Min	30	11	7
	Mean	41.3667	15.5	8.9333
turn angle	Max	3465	756.8699	693.0696
	Min	1890	366.3597	241.9275
	Mean	2937	544.9167	418.4463
risk degree	Max	18	13	8
	Min	8	4	0
	Mean	13.8667	9.1333	3.1667
Iteration number	Max	–	191	196
	Min	3	14	16
	Mean	–	65.3333	126.9667

5.3.2 30×30 environment map

In order to further verify the superiority of MISSA, an environmental map with higher complexity is used in this paper. Figure 11 shows the shortest paths obtained by the three algorithms on the 30×30 environment map. Figure 12 shows the convergence of MISSA compared with ISSA. From Fig. 11, it can be seen that SSA has the same disadvantages of poor quality of paths, more turns, too many redundant nodes and high danger in complex environment maps, and the paths obtained by MISSA have significantly better turns and risk than the paths of SSA and ISSA, with better path smoothness and higher safety factor.

Fig. 11

Three algorithms for shortest path in 30 × 30 environment map.

Fig. 12

Comparison of algorithm convergence curve.

Through comprehensive analysis of 30 simulation results compared with SSA and ISSA, the path length obtained by MISSA is reduced by 63.1% and 6.0%, the number of turns is reduced by 78.4% and 42.4%, the turn angle is reduced by 85.8% and 23.2%, and the risk degree is reduced by 77.2% and 65.3%, respectively. By comparing the simulation results of the two environment maps, it is proved that MISSA is superior in the complex environment map.

5.4 Experimental verification

To demonstrate that MISSA is also feasible in a real-world environment, this paper applies MISSA to QBot2e, an open high-performance mobile robot designed by Quanser Canada.

This paper randomly places multiple obstacles as environment maps in an indoor laboratory, and path-planning and trajectory-tracking experiments are conducted. A grid map is first created so that QBot2e is aware of the obstacles around it. A depth map of the environment is generated using QBot2e’s Microsoft Kinect sensor and combined with the robot’s position and orientation for map construction, as shown in Fig. 13.

Fig. 13

Experimental environment.

The depth map of the environment is processed into a raster map required for robot path planning using image processing techniques, and three algorithms, SSA, ISSA and MISSA, are ported to the mobile robot QBot2e, and finally the starting point and end point are selected for path planning. Figure 14 shows the planning results.

Fig. 14

Actual environment map path comparison.

From the planning results, it can be seen that the paths obtained by MISSA outperform the SSA and ISSA in terms of path length, number of turns and turn angle, indicating that MISSA has certain superiority. The path points obtained from the algorithm planning are sent to the robot one by one, and by comparing them with the robot’s position, the robot is controlled to move using a PID controller to track the trajectory until the robot reaches the target point. Considering the small friction between the robot and the laboratory floor, in order to prevent the robot from slipping and generating position deviation during the trajectory tracking process, this paper limits the robot’s moving speed, but does not affect the overall operation effect. By tracking the path in Fig. 14, the actual running route is basically consistent with the algorithm planning route. The actual operation effect is shown in Fig. 15. The practicality of MISSA in practical situations is illustrated through physical experimental verification.

Fig. 15

Actual operation effect.

6 Conclusions

In this paper, MISSA is proposed to address the shortcomings of SSA in AGV path planning. Firstly, the algorithm’s optimization ability is increased by improving the position updating formula, introducing the Levy flight variation strategy, and optimizing the boundary processing mechanism; then, the path quality is improved by adopting large-scale neighborhood search strategy and path smoothing mechanism. Through simulation experiments and physical verification, the feasibility and practical value of MISSA in the application of AGV path planning are proved, and it provides an effective solution to the AGV path planning problem.

The focus of this paper is mainly on global single-objective path planning, and in the future, it could be considered to be applied to multi-AGV coordinated path planning and multi-objective path planning, in addition, this paper does not involve the study of path planning in dynamic environments, and in the future, it could be considered to integrate this algorithm with local path planning algorithms, to realize the path planning that includes dynamic obstacles.

Footnotes

Acknowledgments

This work was supported by National Natural Science Foundation of China under Grant 62103127, Youth Natural Science Foundation of Hebei Province under Grant F2020201048, Funded by Science and Technology Project of Hebei Education Department under Grant BJK2023057 and Advanced Talents Incubation Program of the Hebei University under Grant 521000981366.

References

Wang

and Mao

, Summary of agv path planning, 2019 3rd International Conference on Electronic Information Technology and Computer Engineering (EITCE), IEEE, 2019, 332–335.

Patle

B.K.

, Pandey

, Parhi

D.R.K.

, et al., A review: On path planning strategies for navigation of mobile robot, Defence Technology 15(4) (2019), 582–606.

Gasparetto

, Boscariol

, Lanzutti

, et al., Path planning and trajectory planning algorithms: A general overview, Motion and Operation Planning of Robotic Systems: Background and Practical Approaches, 2015, 3–27.

Liu

, Zhang

, et al., Novel best path selection approach based on hybrid improved A* algorithm and reinforcement learning, Applied Intelligence 51 (2021), 9015–9029.

Orozco-Rosas

, Montiel

and Sepúlveda

, Mobile robot path planning using membrane evolutionary artificial potential field, Applied Soft Computing 77 (2019), 236–251.

Orozco-Rosas

, Picos

, Pantrigo

J.J.

, et al., Mobile robot path planning using a QAPF learning algorithm for known and unknown environments, IEEE Access 10 (2022), 84648–84663.

Liu

, Lin

, Yao

, et al., Path planning for smart car based on Dijkstra algorithm and dynamic window approach, Wireless Communications and Mobile Computing, 2021, 1–12.

Zhang

, He

and Yang

, A bioinspired path planning approach for mobile robots based on improved sparrow search algorithm, Advances in Manufacturing, 10(1) (2022), 114–130.

Lamini

, Benhlima

and Elbekri

, Genetic algorithm based approach for autonomous mobile robot path planning, Procedia Computer Science 127 (2018), 180–189.

10.

Zhou

, Geng

, Qi

, et al., Research and experiment on global path planning for indoor AGV via improved ACO and fuzzy DWA, Mathematical Biosciences and Engineering 20(11) (2023), 19152–19173.

11.

Kumar

, Singh

and Tiwari

, Path planning for the autonomous robots using modified grey wolf optimization approach, Journal of Intelligent & Fuzzy Systems 40(5) (2021), 9453–9470.

12.

Kumar

, Singh

and Tiwari

, Path planning for the autonomous robots using modified grey wolf optimization approach, Journal of Intelligent & Fuzzy Systems 40(5) (2021), 9453–9470.

13.

Orozco-Rosas

, Picos

and Montiel

, Hybrid path planning algorithm based on membrane pseudo-bacterial potential field for autonomous mobile robots, IEEE Access 7 (2019), 156787–156803.

14.

Xue

and Shen

, A novel swarm intelligence optimization approach: sparrow search algorithm, Systems Science & Control Engineering 8(1) (2020), 22–34.

15.

Fang

, Shen

and Xue

, A new elite opposite sparrow search algorithm-based optimized LightGBM approach for fault diagnosis, Journal of Ambient Intelligence and Humanized Computing, (2022), 1–19.

16.

and Yuan

, Threshold image segmentation based on improved sparrow search algorithm, Multimedia Tools and Applications 81(23) (2022), 33513–33546.

17.

Yang

, Yan

, Zhu

, et al., Improved sparrow algorithm based on game predatory mechanism and suicide mechanism, Computational Intelligence and Neuroscience 2022 (2022).

18.

Geng

, Sun

, Wang

, et al., A modified adaptive sparrow search algorithm based on chaotic reverse learning and spiral search for global optimization, Neural Computing and Applications (2023), 1–18.

19.

Yan

, Yang

, Zhu

, et al., Improved sparrow search algorithm based on iterative local search, Computational Intelligence and Neuroscience 2021 (2021).

20.

Liu

, Liang

, Guo

, et al., Dynamic Path Planning of Mobile Robot Based on Improved Sparrow Search Algorithm, Biomimetics 8(2) (2023), 182.

21.

, Robot path planning based on improved sparrow algorithm, In: Journal of Physics: Conference Series, IOP Publishing 1861(1) (2021), 012017.

22.

Zhang

and Zhang

, An improved sparrow search based intelligent navigational algorithm for local path planning of mobile robot, Journal of Ambient Intelligence and Humanized Computing 2022 (2022), 1–13.

23.

Chen

, Wang

, Lin

, et al., Global Path Planning Method by Fusion of A-star Algorithm and Sparrow Search Algorithm, In: 2022 IEEE 11th Data Driven Control and Learning Systems Conference (DDCLS), IEEE 2022 (2022), 205–209.

24.

Ouyang

, Qiu

and Zhu

, Adaptive spiral flying sparrow search algorithm, Scientific Programming 2021 (2021), 1–16.

25.

Guangyang

, Jiawen

, Qian

, et al., Multi-chaotic Sparrow Search Algorithm Based on Learning Mechanism, Journal of Frontiers of Computer Science and Technology 17(5) (2023), 1057–1074.

26.

Zhou

, Wang

, Zhang

, et al., Application of a hybrid improved sparrow search algorithm for the prediction and control of dissolved oxygen in the aquaculture industry, Applied Intelligence 53(7) (2023), 8482–8502.

27.

Mirjalili

SCA: a sine cosine algorithm for solving optimization problems, Knowledge-Based Systems 96 (2016), 120–133.

28.

and Wang

, Multi-objective sparrow search algorithm: A novel algorithm for solving complex multi-objective optimisation problems, Expert Systems with Applications 210 (2022), 118414.

29.

Zhang

and Ding

, A stochastic configuration network based on chaotic sparrow search algorithm, Knowledge-Based Systems 220 (2021), 106924.

30.

Tang

, Zhou

, Han

, et al., A Chaos Sparrow Search Algorithm with Logarithmic Spiral and Adaptive Step for Engineering Problems, CMES-Computer Modeling in Engineering & Sciences 130(1) (2022).

31.

Houssein

E.H.

, Saad

M.R.

, Hashim

F.A.

, et al., Lévy flight distribution: A new metaheuristic algorithm for solving engineering optimization problems, Engineering Applications of Artificial Intelligence 94 (2020), 103731.

32.

Liang

, Chen

, Wu

, et al., A novel modified sparrow search algorithm with application in side lobe level reduction of linear antenna array, Wireless Communications and Mobile Computing 2021 (2021), 1–25.

33.

, Li

and Li

, Simulated annealing with large-neighborhood search for two-echelon location routing problem, Chinese Journal of Engineering 39(6) (2017), 953–961.

34.

Zhang

, Zhang

and Zhang

, Path planning of coal mine rescue robot based on improved A* algorithm, Coal Geology & Exploratio 50(12) (2022), 185–193.

35.

Momin

and Yang

X.S.

, A literature survey of benchmark functions for global optimization problems, Journal of Mathematical Modelling and Numerical Optimisation 4(2) (2013), 150–194.

36.

Chen

Jiajun

, Fan

and Xiaowen

, Study on intelligent vehicle path planning with improved sparrow search algorithm, Journal of Chongqing University of Technology (Natural Science) 37(4) (2023), 50–56.

37.

Mirjalili

and Lewis

, The whale optimization algorithm, Advances in Engineering Software 95 (2016), 51–67.

38.

Mirjalili

, Mirjalili

S.M.

and Lewis

, Grey wolf optimizer, Advances in Engineering Software 69 (2014), 46–61.

39.

Kennedy

and Eberhart

, Particle swarm optimization, Proceedings of ICNN’95-international conference on neural networks, IEEE, 4 (1995), 1942–1948.

40.

Yang

, Liu

, et al., A novel adaptive sparrow search algorithm based on chaotic mapping and t-distribution mutation, Applied Sciences 11(23) (2021), 11192.

A multi-strategy improved sparrow search algorithm for indoor AGV path planning

Abstract

Keywords

1 Introduction

2 The basic sparrow search algorithm

3.1 Improved discoverer position update formula

4 Algorithm performance verification and result analysis

4.1 Test functions

5.1 Environmental maps

5.2 Path evaluation indicators

Table 5 Parameter setting Algorithm Parameters MISSA ST = 0.8, PD = pop× 20 % , SDmax = pop × 20 % , SDmin = pop × 10 % ISSA ST = 0.8, PD = pop× 20 % , SD = pop × 10 % SSA ST = 0.8, PD = pop× 20 % , SD = pop × 10 %

Footnotes

Acknowledgments

References

Table 5
Parameter setting

Algorithm Parameters

MISSA ST = 0.8, PD = pop× 20 % , SD_max = pop × 20 % , SD_min = pop × 10 %

ISSA ST = 0.8, PD = pop× 20 % , SD = pop × 10 %

SSA ST = 0.8, PD = pop× 20 % , SD = pop × 10 %