Abstract
In this paper, a bioinspired path planning approach for mobile robots is proposed. The approach is based on the sparrow search algorithm, which is an intelligent optimization algorithm inspired by the group wisdom, foraging, and anti-predation behaviors of sparrows. To obtain high-quality paths and fast convergence, an improved sparrow search algorithm is proposed with three new strategies. First, a linear path strategy is proposed, which can transform the polyline in the corner of the path into a smooth line, to enable the robot to reach the goal faster. Then, a new neighborhood search strategy is used to improve the fitness value of the global optimal individual, and a new position update function is used to speed up the convergence. Finally, a new multi-index comprehensive evaluation method is designed to evaluate these algorithms. Experimental results show that the proposed algorithm has a shorter path and faster convergence than other state-of-the-art studies.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
1 Introduction
Mobile robots are widely used in aerospace, entertainment, agriculture, military, mining, and rescue operations [1]. The path planning method plays a key role in the application of mobile robots. Its main purpose is to find a safe and collision-free optimal or suboptimal path from the starting position to the target position in a workspace with obstacles, according to certain performance indicators (walking path, planning time, path smoothness).
There are many classical path planning methods, such as the cell decomposition method [2,3,4], artificial potential field (APF) algorithm [5], Astar algorithm (A*) [6, 7], probabilistic road map (PRM) algorithm [8], and rapidly exploring random tree (RRT) algorithm [9, 10]. Montiel et al. [11] proposed a new bacterial potential field algorithm based on APF, which had good performance in determining the optimal path time. Jose and Pratihar [12] used Astar for path planning and a genetic algorithm (GA) for task allocation, and completed task allocation and collision-free path planning tasks for three robots at 90 points in a factory. Yan et al. [13] proposed an improved probabilistic road map algorithm that performed well for path planning in narrow passages in the map. Classical algorithms have the advantages of simple principles, but they have certain problems. It is worth noting that some classical methods are deterministic algorithms that are easily trapped in local optimal solutions in complex situations. In addition, the algorithm may not reach the end point in a complex environment. The path generated may be too rough, which would cause collisions between robots and obstacles. The algorithm may converge slowly in a complex environment.
Unlike traditional methods, the biological mechanisms of animals have been optimized through millions of years of natural evolution, and hence their behaviors can perform many intelligent tasks accurately and robustly. Therefore, we have a good reason to learn from nature to improve path-planning technologies. In recent years, researchers have proposed bioinspired algorithms, such as the gray wolf optimization (GWO) algorithm [14], ant lion optimization (ALO) algorithm [15], whale optimization algorithm (WOA) [16], and sparrow search algorithm (SSA) [17]. The GWO originated from the predation behavior and social hierarchy of gray wolf populations. Gray wolves follow a strict social hierarchy. Xu et al. [18] proposed an improved GWO that used a 2-opt dynamic elite mechanism. Through the optimal route selection of tourist attractions, the effectiveness of the proposed method is verified, and the deficiencies of the basic gray GWO are solved. The ALO simulates the hunting mechanism of antlion hunting ants to achieve global optimization. Tian et al. [19] proposed an improved ALO, which integrated a chaotic mutation mechanism and improved the iterative search process, and applied the algorithm to the parameter identification of a hydraulic turbine governing system. The WOA simulates the social behavior of humpback whales and introduces bubble-net hunting strategies. Yildiz [20] proposed a hybrid optimization algorithm based on the Nelder–Mead local search algorithm and the WOA, and applied the proposed algorithm to solve production optimization problems. The SSA is inspired by the foraging behavior and anti-predation behavior of sparrows. Xue and Shen [17] proposed a basic SSA and verified the superiority of this algorithm compared with other algorithms through test results on 19 benchmark functions, and finally applied the algorithm to two engineering examples. To understand the advantages and disadvantages of each algorithm more clearly, this article summarizes the advantages and disadvantages of some methods and the direction of improvement, as listed in Table 1 [5,6,7,8,9,10, 14,15,16,17, 21,22,23,24]. In summary, this article proposes an algorithm for obtaining high-quality paths with rapid convergence.
To obtain high-quality paths and fast convergence, a new bioinspired path planning method is proposed in this work, the main aspect of which is an ISSA. First, to solve the problem of many corners in the path planned by the traditional algorithm, a linear path strategy (LPS) is proposed, which uses the method of turning the polyline in the corner section of the path into a straight line to smooth the generated path. Then, a new position update function of the SSA is improved to speed up the convergence of the search algorithm. The neighborhood search strategy is used to improve the fitness value of the global optimal individual. Finally, a multi-index comprehensive evaluation method is presented to evaluate the performance of our ISSA and other search algorithms.
The remainder of this paper is organized as follows. Section 2 describes the modeling of a mobile robot working environment. Section 3 proposes the ISSA and a multi-index comprehensive evaluation algorithm. Section 4 shows the results of the experiments with the ISSA and other algorithms. Section 5 uses the proposed path evaluation algorithm to comprehensively evaluate the experimental path of each algorithm. Section 6 concludes the paper with a summary of the main results of this study and a discussion of future works.
2 Environment modeling
In this study, the grid method was used to model the map environment. On a two-dimensional map, a mobile robot is regarded as a circle with radius \(R_{{\text{r}}}\), as shown in Fig. 1. To simplify the problem, the mobile robot is regarded as a mass point, and the obstacle is expanded by \(R_{{\text{s}}}\). \(R_{{\text{s}}}\) is obtained by
where \(\sigma\) represents the safety distance, which is artificially chosen to prevent the mobile robot from contacting obstacles.
As shown in Fig. 2, two mobile robot working environments, Environments 1 and 2, were established, with a map size of 20×20. Compared with Environment 1, Environment 2 has more obstacles and more complex terrain, which is a challenge for mobile robot path planning methods. The starting point of the planned path is grid (0, 0), represented by a red circle, and the end point is grid (20, 20), represented by a green square.
3 Method
3.1 Basic SSA
The SSA simulates the foraging process of sparrow flocks [17]. The foraging process of sparrow flocks is a discoverer-joiner model, with a superimposed reconnaissance and early warning mechanism. There are three distinct sparrow populations: discoverers, joiners, and scouts. Among the sparrows, individuals who can easily find food serve as discoverers, and other individuals serve as joiners. The discoverer has a high fitness value, a wide search range, and guides the population to search and forage. To obtain better fitness, the joiner follows the discoverer to forage. At the same time, a certain proportion of individuals in the population are selected as scouts to observe surrounding companions and dangerous predators, thereby improving their predation and risk prevention abilities.
In the model, the location update formula of the discoverer is given by
where \(t\) represents the current iteration number, and \(X_{i}\) represents the position information of the \(i\)th sparrow. \(a\) is a random number in the range of \(\left( {0,1} \right]\). \(R\left( {R \in \left[ {0,1} \right]} \right)\) and \(S\left( {S \in \left[ {0.5,1} \right]} \right)\) represent warning and safety parameters, respectively, where \(R\) is a random number and \(S\) is a given constant. When \(R < S\), no danger is found in the population; the search environment is safe; and the discoverer can conduct a wide range of searches. When \(R \geqslant S\), the scouts find danger, adjust the search strategy, and quickly move closer to the safe area. \(Q\) is a random number that follows the normal distribution. \(\bf{\varvec {L}}\) represents an all-one matrix of dimensions \(1 \times d\).
The location update formula of the joiner is given by
where \(X_{{\text{b}}}\) is the current best position of the discoverer and \(X_{{\text{r}}}\) represents the current worst position in the world. \({\varvec{A}}\) represents a matrix of dimensions \(1 \times d\), where each element has a value of 1 or −1 and \({\varvec{A}}^{ + } = {\varvec{A}}^{\text {T}} \left( {{\varvec{AA}}^{\text {T}} } \right)^{ - 1}\).
The location update formula of the scout is shown as
where \(X_{{\text{B}}}\) is the current global optimal position. \(\beta\) is a step-length control parameter, a random number drawn on a normal distribution with a mean value of 0 and a variance of 1. \(K\) is a random number in the range of \(\left[ { - 1,1} \right]\). \(f_{i}\) represents the current individual fitness value of the sparrow. \(f_{{\text{B}}}\) and \(f_{{\text{R}}}\) represent the current global optimal and worst fitness values, respectively. \(\varepsilon\) is a very small constant.
When the iteration ends, the optimization result is output. The overall SSA execution flowchart is shown in Fig. 3.
3.2 ISSA
Based on the SSA, we propose a new algorithm, the ISSA. There are three improvements in the ISSA: LPS strategies, neighborhood search strategy, and an improved location update formula. The LPS strategy was used to calculate the fitness function to linearize the path. The population is updated using the improved position-update formula. The neighborhood search strategy is used after the location update formula to reduce the fitness value of the global optimal individual. Table 2 shows the similarities and differences between the SSA and ISSA. Figure 4 shows the execution flowchart of the ISSA.
3.2.1 LPS
In Ref. [25], a sequential LPS is proposed. However, the strategy checks whether the path and obstacles intersect, and uses the method of whether each obstacle index is the same as the path index. With many obstacles, the strategy cannot be easily implemented. This study proposes a high-efficiency LPS used within the SSA to improve the path quality and reduce the path acquisition time.
The LPS is divided into two stages: obstacle detection and path connection. Due to the fact that the LPS is used inside the algorithm, a judgment method with a large number of calculations cannot be used. It can be explained that iterations will increase the execution time of the LPS. The LPS is outlined as follows.
-
Step 1 Start from the starting point, extract three points in order.
-
Step 2 Find the coordinate range between the first and third points.
-
Step 3 Determine whether there are obstacles in this range.
-
Step 4 If there is no obstacle, remove the second point from the path; if there is an obstacle, terminate the cycle and continue to linearize the path.
The execution process of the strategy is illustrated in Fig. 5. Table 3 lists the pseudo-code of the LPS. In the schematic diagram, we separated the grids in the grid map by a certain distance for the sake of clarity. The following diagrams follow this rule. Note that there are no gaps among the grids in the actual grid map.
3.2.2 Neighborhood search strategy
In the SSA, the global optimal individual in the population plays a role in leading the direction of the population exploration, such that the global optimal individual has a great influence on the entire group. Thus, a neighborhood search is performed on individuals with optimal fitness to reduce their fitness value. The neighborhood search strategy can be divided into the following three steps.
-
Step 1 Get the dimensionality of the path.
-
Step 2 Randomly search each dimension of the path and calculate the fitness value of the path after searching.
-
Step 3 Judgment. If the path fitness value is lower after the search, replace the previous path with the searched path. If the path fitness is higher after the search, the search result is discarded and the original path is retained.
The implementation process of the neighborhood search strategy is shown in Fig. 6. This strategy searches for the dimension of 1 point and finds a 1* point. By calculating the fitness value, the 1* point constitutes a path with a lower fitness value, thereby replacing 1 point in the previous path with a 1* point. Table 4 presents pseudo code of the neighborhood search strategy process.
3.2.3 Improve location update formula
In the position update formula of the basic SSA, the iteration process is \(X_{i}^{t} \to X_{i}^{t + 1}\); that is, the position of the sparrow at the next moment depends on the position of the sparrow at the previous moment. But this presents a problem. If the fitness value of the individual \(X_{i}^{{}}\) at time \(t\) is not the optimal fitness of the individual, that is, the position of the individual at time \(t\) is not the best at time \(1 - t\), then the updated position of the individual at time \(t\) is poor, compared with the position updated by the individual with the best fitness at time \(1 - t\). Therefore, the basic SSA is improved in this work to address this problem, by updating the individual with the optimal fitness of \(1 - t\). The position update formula of the SSA is modified to Eqs. (5)–(7).
The improved position update formula for the discoverer is given by
where \(X_\text{e}^{t}\) represents the position of individual \(i\) with the optimal fitness value at time \(1 - t\).
The improved position update formula of the joiner is given by
The improved position update formula for the scout is given by
3.3 Comprehensive path evaluation method
3.3.1 Path evaluation index
Adopting a mobile robot to plan and execute the path with the best time as the goal, it is proposed to use multiple indicators to comprehensively evaluate the path. We select four indicators as the basis for path evaluation: the shortest distance value, the total rotation angle value, the risk degree, and the shortest path acquisition time.
The shortest distance value is the length of the optimal path obtained by the algorithm. The total rotation angle value is the sum of the angles of the path planned by the algorithm. An angle diagram is shown in Fig. 7.
The risk degree is the number of intersections between the planned path and obstacles in the grid map. As shown in Fig. 8, if the intersection of the mobile robot’s trajectory and the obstacle is 1, the risk degree is 1, and if the intersection of the mobile robot’s trajectory and the obstacle is 2, the risk degree is 2.
The shortest path acquisition time is the program execution time to generate the shortest path. Some studies [26, 27] used the execution time of the algorithm program as the path acquisition time, which is unrealistic. In general, the number of iterations required to obtain the shortest path is less than the number of iterations set by the algorithm; therefore, some portion of the number of iterations does not affect the generation of the shortest path. To describe the shortest path acquisition time more accurately, we introduce the concept of the number of shortest path iterations (\(N\)), which refers to the number of iterations for the algorithm to obtain the shortest path. Therefore, the shortest path acquisition time (\(T\)) is calculated using
where \(T_{{\text{c}}}\) indicates the execution time of the algorithm and \(t_{{{\text{max}}}}\) represents the maximum number of iterations set by the algorithm.
3.3.2 Comprehensive path evaluation algorithm
Because the improved algorithm achieves good performance on one index while it may be worse on other indexes, it is necessary to weight each index of the path to comprehensively evaluate the path quality. However, many studies ignore the comprehensive evaluation and conduct a single-index evaluation [28,29,30,31,32,33]. In this paper, by improving the technique for order preference by similarity to an ideal solution, a comprehensive path evaluation algorithm applied is proposed. The comprehensive path evaluation process is divided into four parts: index normalization, index standardization, determination of index weight, and finally calculation of scores and normalization. The execution process of the algorithm is illustrated in Fig. 9.
-
(i)
Positive indicators
To increase the path score, the better the quality, the more positive is the index. Because the four indicators are all extremely small, they can be transformed and shown as
where \(x_{i,j}\) represents the original data; the row (a total of \(n\) rows) in the original data represents the algorithm, that is, the evaluation object; the column (a total of \(m\) columns) represents the evaluation index; \(x_{i,j}^{p}\) represents the normalized data; and \({\text{max}}_{j}\) represents the maximum value of index \(j\).
-
(ii)
Standardization of indicators
Owing to the different dimensions of the four indicators in this study, the influence of the dimensions was eliminated by
where \(X_{i,j}\) represents the standardized data.
-
(iii)
Determination of index weight
The analytic hierarchy process is used to determine the weights between the path evaluation indicators. The weight determination process is shown as follows.
-
Step 1 Establish a hierarchical structure diagram
The weight determination problem is decomposed into two layers: the first layer is the target layer \(O\), which is the weight of the four indicators; the second layer is the criterion layer, including the shortest distance \(C_{1}\), the total turning angle \(C_{2}\), the risk degree \(C_{3}\), and the shortest path acquisition time \(C_{4}\). A hierarchical structure diagram is constructed, as shown in Fig. 10.
-
Step 2 Determining judgment matrix
The mobile robot scene in this study is as follows: the mobile robot can turn four wheels with differential speed and medium load. To determine the judgment matrix, the judgment matrix is assigned a value according to the degree of influence of each index on the path quality, as shown in Table 5. The order of importance of the indicators in this study is as follows: the shortest path distance is the most important, followed by the shortest path acquisition time, the total rotation angle of the path, and the path risk degree. After the obstacles are enlarged, although the path of the mobile robot and the obstacles on the map have intersections, there is still a safe distance \(\sigma\) between the obstacles and the mobile robot, and thus we believe that the importance of the path risk degree ranks last.
-
Step 3 Consistency test
The above judgment matrix cannot be used directly, and a consistency test is required. Set \(R_{{\text{C}}}\) as the consistency test parameter, the test formula is given by
where \(I_{\text{R}}\) is the random consistency index, which can be obtained from a lookup table, and \(I_{{\text{C}}}\) is the consistency index, which is calculated by
where \(\lambda_{{{\text{max}}}}\) is the maximum eigenvalue of the judgment matrix and \(d\) is the dimension of the judgment matrix.
It is generally considered that if \(R_{{\text{C}}} < 0.1\), the consistency of the judgment matrix is acceptable. \(R_{{\text{C}}} = 0.022 \,2 (< 0.1)\) is calculated to judge that the matrix passes the consistency test.
-
Step 4 Get the index weight
Index weights were calculated using the arithmetic mean, geometric mean, and eigenvalue methods. To eliminate the error caused by the calculation method, the calculation results of the three methods were averaged by taking their arithmetic mean. The index weights are presented in Table 6.
The formula for calculating the weight using the arithmetic mean method is shown as
where \(w_{i}\) represents the weight of the \(i\)th indicator; \(n\) represents the number of indicators; and \(a_{i,j}\) represents the importance of the \(i\)th indicator relative to the \(j\)th indicator in the judgment matrix.
The calculation formula for the geometric mean method for calculating the weight is shown as
-
(iv)
Score calculation and normalization
The evaluation algorithm proposed in this paper integrates classic evaluation methods and is innovatively applied to the path evaluation of mobile robots.
The formula for calculating the maximum value of each evaluation index is given by
where \(i = 1,2, \cdots ,m\).
The formula for calculating the minimum value of each evaluation index is given by
The calculation formula for the distance between the \(i\)th evaluation object and the maximum value is shown as
The calculation formula for the distance between the \(i\)th evaluation object and the minimum value is shown as
Using Eqs. (15)–(18), we can calculate the score of the \(i\)-th (i=1,2,···,n) evaluation object without normalization, shown as
It can be seen from Eq. (19) that \(0 \leqslant S_{i} \leqslant 1\), and the larger \(S_{i}\), the closer it is to the maximum value. The score \(S_{i}\) was normalized using
4 Experiment
To demonstrate the superiority of the proposed algorithm, ISSA, compared with other popular algorithms, experiments were carried out under the same environment and parameters. We compare the ISSA with the basic SSA, ACO, and ACO fused with a GA to evaluate the performance of the algorithm.
In this study, ISSA, SSA, ACO, and ACO+GA were all simulated using the same software and hardware platform, and the programming environment was MATLAB R2019b (MathWorks Co., USA). To establish a fair comparison of the algorithms, the basic parameters of each algorithm were set to the same value, as shown in Table 7.
To verify the effectiveness of the proposed ISSA, two maps with different difficulty levels, Environment 1 and Environment 2, were used. The experimental results for Environments 1 and 2 are shown in Figs. 11 and 12, respectively. The results of the path planning of the four algorithms in this article in Environments 1 and 2 can also be observed through a video, which is included in the supplementary information.
The code for the experiment and discussion in this article is published on the GitHub platform. The code can be accessed via the following link: https://github.com/herryCccc/Mobile-robot-path-planning.
Figure 11 shows the shortest path diagram and the shortest path convergence process planned by ACO, ACO + GA, SSA, and ISSA in Environment 1. Obviously, ISSA has better results than the other algorithms in terms of path length, path smoothness, and the number of shortest path convergences. This shows that ISSA performs well in Environment 1. Figure 12 shows the shortest path diagram and the convergence process of the shortest path planned by ACO, ACO + GA, SSA, and ISSA in Environment 2. For more complex map conditions, ISSA still performs better than ACO, ACO+GA, and SSA.
5 Discussion
To evaluate the robustness of ISSA, we repeated the four algorithms of ACO, ACO+GA, SSA, and ISSA 100 times on Environments 1 and 2. The four indicators of the shortest distance, total rotation angle, risk degree, and the shortest path acquisition time of the four algorithms were collected.
The repetitive experimental results of the four indicators of the four algorithms in Environment 1 are shown in Figs. 13–16. It can be seen from Figs. 13 and 14 that the shortest distance and the total rotation angle of the path planned by ISSA are significantly better than those of the other algorithms. However, from Figs. 15 and 16, the path risk and shortest path acquisition time are not optimal for ISSA. We surmise that this is because a shorter path will cause the path to get closer to the obstacle. As the LPS and neighborhood search strategies are added to the basic SSA, the shortest path acquisition time is slightly increased compared with SSA. As ISSA shows different performances with respect to different indicators, it also reflects the importance of comprehensive path evaluation.
The repetitive experimental results of the four indicators of the four algorithms of Environment 2 are shown in Figs. 17–20. The results show that ISSA surpasses the other algorithms regarding three indicators: the shortest distance, total rotation angle, and shortest path acquisition time. It is worth noting that ISSA surpasses SSA in the shortest path acquisition time. This is because, for more difficult maps, the performance of ACO, ACO+GA, and SSA to obtain the optimal path decreases, whereas the performance of ISSA remains unchanged, which also indicates that ISSA is robust to environmental changes. However, it can be seen from Fig. 19 that the risk degree of the path planned by ISSA is still high. This is because the process of shortening the path also increases the risk.
Because ISSA shows different performances (better or worse) with respect to different indicators, it is necessary to comprehensively evaluate the path planned by ISSA. Through the test results of ACO, ACO+GA, SSA, and ISSA for the mobile robot in Environments 1 and 2, we count the maximum, minimum, and average values of each indicator, and plot the data in Tables 8 and 9. In Environment 1, ISSA has the best performance for the shortest distance and total rotation angle. However, SSA has better scores in the shortest path acquisition time and risk degree. In Environment 2, ISSA also has the best performance for the shortest distance and total rotation angle. Additionally, it surpasses SSA in the minimum and average values of the shortest path acquisition time. However, it is inferior to the other algorithms in terms of path risk, as explained earlier.
The proposed evaluation algorithm is used to process the data and obtain comprehensive scores of the paths planned by ACO, ACO+GA, SSA, and ISSA for Environments 1 and 2, as shown in Table 10. It can be concluded from Table 10 that ISSA has the highest comprehensive score in Environments 1 and 2. In Environment 1, the ISSA score is increased by 190% relative to the SSA score, whereas in environment 2, the ISSA score is improved with respect to the SSA score by 102%. Therefore, it can be concluded that the comprehensive performance of the proposed algorithm surpasses that of the other algorithms. Moreover, the proposed algorithm surpasses the other algorithms in terms of the shortest path and convergence speed.
6 Conclusions
In mobile robot path planning, traditional algorithms easily fall into local optima and exhibit slow convergence. ISSA, an improved algorithm based on the LPS, neighborhood search strategy, and improved location update formula, is proposed in this study to address the aforementioned challenges. This algorithm has the characteristics of fast convergence and strong optimization ability. Experiments were conducted in two different environments to verify the performance of the algorithm. Because of the different performance of the path planned by each algorithm with respect to each index, this work proposes a comprehensive evaluation algorithm to evaluate the quality of the path planned by each algorithm. The experimental results show that the proposed algorithm represents significant progress compared with the current algorithm. In the future work, it will be very meaningful to apply ISSA to actual robot path planning. In addition, we will also use ISSA for dynamic obstacles and multirobot path planning.
References
Patle BK, Ganesh BL, Anish P et al (2019) A review: on path planning strategies for navigation of mobile robot. Def Technol 15:582–606
Gonzalez R, Kloetzer M, Mahulea C (2017) Comparative study of trajectories resulted from cell decomposition path planning approaches. In: 2017 21st international conference on system theory, control and computing, Sinaia, pp 49–54
Zhang Z, Yang X (2019) Bio-inspired motion planning for reaching movement of a manipulator based on intrinsic tau jerk guidance. Adv Manuf 7:315–325
Yang K, Tang Y, Zhang Z (2021) Parameter identification and state-of-charge estimation for lithium-ion batteries using separated time scales and extended Kalman filter. Energies 14(4):1054. https://doi.org/10.3390/en14041054
Lee K, Choi D, Kim D (2021) Incorporation of potential fields and motion primitives for the collision avoidance of unmanned aircraft. Appl Sci Basel 11(7):3103. https://doi.org/10.3390/app11073103
Guruji AK, Agarwal H, Parsediya DK (2016) Time-efficient A* algorithm for robot path planning. In: The 3rd international conference on innovations in automation and mechatronics engineering, Elsevier, Vallabh Vidhyanagar, pp 144–149
Chen C, Cai J, Wang Z et al (2020) An improved A* algorithm for searching the minimum dose path in nuclear facilities. Prog Nucl Energy 126:103394. https://doi.org/10.1016/j.pnucene.2020.103394
Chen G, Luo N, Liu D et al (2021) Path planning for manipulators based on an improved probabilistic roadmap method. Robot Comput Integr Manuf 72:102196. https://doi.org/10.1016/j.rcim.2021.102196
Sun Y, Zhang C, Sun P et al (2020) Safe and smooth motion planning for mecanum wheeled robot using improved RRT and cubic spline. Arab J Sci Eng 45:3075–3090
Wu X, Xu L, Zhen R et al (2019) Biased sampling potentially guided intelligent bidirectional RRT algorithm for UAV path planning in 3D environment. Math Probl Eng 2019:5157403. https://doi.org/10.1155/2019/5157403
Montiel O, Orozco-Rosas U, Sepúlveda R (2015) Path planning for mobile robots using bacterial potential field for avoiding static and dynamic obstacles. Expert Syst Appl 42:5177–5191
Jose K, Pratihar DK (2016) Task allocation and collision-free path planning of centralized multi-robots system for industrial plant inspection using heuristic methods. Robot Auton Syst 80:34–42
Yan F, Liu YS, Xiao JZ (2013) Path planning in complex 3D environments using a probabilistic roadmap method. Int J Autom Comput 10:525–533
Mirjalili S, Mirjalili SM, Lewis A (2014) Grey wolf optimizer. Adv Eng Softw 69:46–61
Mirjalili S (2015) The ant lion optimizer. Adv Eng Softw 83:80–98
Mirjalili S, Lewis A (2016) The whale optimization algorithm. Adv Eng Softw 95:51–67
Xue J, Shen B (2020) A novel swarm intelligence optimization approach: sparrow search algorithm. Syst Sci Control Eng 8:22–34
Xu R, Cao M, Huang M et al (2018) Research on the quasi-TSP problem based on the improved grey wolf optimization algorithm: a case study of tourism. Geogr Geo Inf Sci 34:14–21
Tian T, Liu C, Guo Q et al (2018) An improved ant lion optimization algorithm and its application in hydraulic turbine governing system parameter identification. Energies 11:95. https://doi.org/10.3390/en11010095
Yildiz AR (2019) A novel hybrid whale-Nelder-Mead algorithm for optimization of design and manufacturing problems. Int J Adv Manuf Technol 105:5091–5104
Wang X, Shi H, Zhang C (2016) Path planning for intelligent parking system based on improved ant colony optimization. IEEE Access 8:65267–65273
Niu H, Ji Z, Savvaris A et al (2020) Energy efficient path planning for nnmanned surface vehicle in spatially-temporally variant environment. Ocean Eng 196:106766. https://doi.org/10.1016/j.oceaneng.2019.106766
Zhang C, Ding S (2021) A stochastic configuration network based on chaotic sparrow search algorithm. Knowl Based Syst 220:106924. https://doi.org/10.1016/j.knosys.2021.106924
Liu G, Shu C, Liang Z et al (2021) A modified sparrow search algorithm with application in 3D route planning for UAV. Sensors 21:1224. https://doi.org/10.3390/s21041224
Raouf F, Mohammed B, Tamer R et al (2020) Enhancing path quality of real-time path planning algorithms for mobile robots: a sequential linear paths approach. IEEE Access 8:167090–167104
Ajeil FH, Ibraheem KI, Sahib MA et al (2018) Multi-objective path planning of an autonomous mobile robot using hybrid PSO-MFB optimization algorithm. Appl Soft Comput 89:106076. https://doi.org/10.1016/j.asoc.2020.106076
Li X, Huang Y, Zhou Y et al (2018) Robot path planning using improved artificial bee colony algorithm. In: 2018 IEEE 3rd advanced information technology, electronic and automation control conference, Chongqing, China, pp 603–607
Zhang D, You X, Liu S et al (2020) Dynamic multi-role adaptive collaborative ant colony optimization for robot path planning. IEEE Access 8:129958–129974
Zinage V, Ghosh S (2020) Directional sampling-based generalized shape expansion for accelerated motion planning in 2-D obstacle-cluttered environments. IEEE Contr Syst Lett 5:1067–1072
Huang Y, Li Z, Jiang Y et al (2019) Cooperative path planning for multiple mobile robots via HAFSA and an expansion logic strategy. Appl Sci Basel 9:672. https://doi.org/10.3390/app9040672
Alaa T, Mohamed E, Aboul EH et al (2019) Intelligent Bézier curve-based path planning model using chaotic particle swarm optimization algorithm. Cluster Comput 22:4745–4766
Hassani I, Maalej I, Rekik C (2018) Robot path planning with avoiding obstacles in known environment using free segments and turning points algorithm. Math Probl Eng 2018:2163278. https://doi.org/10.1155/2018/2163278
Wang Z, Xiang X (2018) Improved A star algorithm for path planning of marine robot. In: 2018 37th Chinese control conference. IEEE, Wuhan, China, pp 5410–5414
Acknowledgements
This research was jointly supported by the National Key R&D Program of China (Grant No. 2018YFB1309200) and the Opening Project of Shanghai Robot Industry R&D and Transformation Functional Platform.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhang, Z., He, R. & Yang, K. A bioinspired path planning approach for mobile robots based on improved sparrow search algorithm. Adv. Manuf. 10, 114–130 (2022). https://doi.org/10.1007/s40436-021-00366-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40436-021-00366-x