Keywords

1 Introduction

Robot path planning is a very important part in the field of robotics, because it gives robots the ability to move, so that it can handle a variety of tasks that need to move between two points [1].

Given the start and goal position for robot in a 2D environment with static obstacles, the goal of path planning is to search for an optimal or suboptimal collision-free path so that robots can move from the start point to the target point without collision with obstacles [2]. Based on the mastery of the environment, path planning can be divided into global path planning and local path planning.

There has been lots of research on motion planning since the pioneering work presented by N. J. Nilsson in late 1960 s [3]. Thus far, various motion planning algorithms have been presented such as Probabilistic Roadmaps [4, 5], Rapidly Exploring Random Trees [6, 7], and Potential Fields [8, 9], etc. These algorithms can be divided into deterministic and undeterministic algorithms. Deterministic algorithms must find the optimal solution when the problem has an optimal solution, otherwise they return information that there is no optimal solution. However, as the size of the problem becomes more complex, the complexity of modeling the problem and the amount of computation required by the algorithm grows exponentially. Besides, since practical engineering problems usually have many locally optimal solutions, it is difficult for these deterministic algorithms to cope with increasingly difficult problems. Unlike deterministic algorithms, meta-heuristic algorithms can find an approximate solution in case the exact solution cannot be found. This can significantly reduce the amount of computation. Also, meta-heuristic algorithms introduce stochasticity, which gives it the ability to get rid of the local optimum problem. These advantages provide important implications for metaheuristic algorithms to solve global optimization problems. In the past decades, researchers have proposed various Swarm intelligence algorithms, including: Particle Swarm Optimization Algorithm [10], Krill Herd Optimization Algorithm [11], Beetle Antenna Search Algorithm [12], etc. The sparrow search algorithm [13] is a novel metaheuristic optimization algorithm recently proposed with faster convergence, fewer control parameters, and simpler computation, but like other swarm intelligence algorithms, it tends to converge early when solving complex optimization problems, thus falling into the local optima.

In this paper, a novel SSA-based path planning algorithm is proposed. The algorithm incorporates random opposition-based learning strategy and linear decreasing mechanism and is utilized to optimize the control points of Bezier curve, which is used to generate an optimal feasible path. The Bezier curve requires only a few control points to generate a smooth curve, which makes the dimension of the path planning problem not increase exponentially with the complexity of the environment and greatly reduces the complexity of the path planning problem. The superiority of the proposed algorithm is verified by benchmark function experiments, and the smooth optimal path of the robot is designed more stably in the contrast experiments of the path planning problem.

The remaining of the article is arranged as follows: Sect. 2 explains basic SSA algorithm. Section 3 presents the proposed algorithm ROSSA. The description of robot path planning problem and Bezier curve are discussed and contrast experiments with PSO and SSA are conducted in Sect. 4. Finally, Sect. 5 gives the conclusion.

2 Sparrow Search Algorithm(SSA)

SSA is a novel swarm intelligence-based optimization algorithm inspired by the foraging and anti-predatory behaviors of a sparrow population. It has three phases: producer phase, scrounger phase and scouter phase. The key steps of the SSA algorithm are following:

Initialization: First of all, SSA initializes all the parameters and random population of sparrow as follows:

$$\begin{aligned} X_{i, j}=rand\times \left( UB_{j}-LB_{j}\right) \end{aligned}$$
(1)

where \(i=1,2,...,pop\), \(j=1,2,...,dim\). \(LB_{j}\) and \(UB_{j}\) are lower and upper bounds of search spaceseparately. \(rand\in (0,1)\) is a random number.

Producer phase: After initialization, sparrows in the top 10%–20% fitness values (producers) start to search for a better solution in the search space. In this phase, the location of the sparrow is updated by

$$\begin{aligned} X_{i, j}^{t+1}=\left\{ \begin{array}{ll} X_{i, j}^{t} \cdot \exp \left( \frac{-i}{\alpha \cdot T}\right) &{} \quad if R_{2} \le ST \\ X_{i, j}^{t}+Q \cdot L &{} \quad if R_{2} \ge ST \end{array}\right. \end{aligned}$$
(2)

where t represents the current iteration. \(\alpha \) is a random number in the range (0, 1). T is the max iteration. Q obeys normal distribution. \(R_{2} \in [0,1]\), \(ST\in [0.5,1]\) are the alarm value and the safety threshold respectively.

Scrounger phase: The rest of population are called scroungers. The movement of scrounger individuals can be defined as:

$$\begin{aligned} X_{i, j}^{t+1}=\left\{ \begin{array}{cc} Q \cdot \exp \left( \frac{x_{worst}^{t}-X_{i, j}^{t}}{i^{2}}\right) &{} \quad i>n / 2 \\ X_{p}^{t}+\left| X_{i j}^{t}-X_{p}^{t}\right| \cdot A^{+} \cdot L &{} \quad otherwise \end{array}\right. \end{aligned}$$
(3)

where \(X_{p}\) is the best position occupied by the producer. \(X_{worst}\) denotes the current global worst location. A represents a matrix of \(1\times d\) for which each element inside is randomly assigned 1 or –1, and \(A^{+}=A^{T}\left( \mathrm {~A} A^{T}\right) ^{-1}\).

Scout phase: Randomly select 10%–20% of population as scout. The update formula of scout is described as follows:

$$\begin{aligned} X_{i, j}^{t+1}=\left\{ \begin{array}{ll} X_{best}^{t}+\beta \cdot \left| X_{i, j}^{t}-X_{best}^{t}\right| &{} \quad f_{i}>f_{g} \\ X_{i, j}^{t}+K \cdot \left( \frac{\mid x_{l, j}^{t}-X_{worst}^{t}}{\left( f_{i}-f_{worst}\right) +\varepsilon }\right) &{} \quad f_{i}=f_{g} \end{array}\right. \end{aligned}$$
(4)

where \(X_{best}\) is the current global optimal location. b is the step control parameter that obeys a normal distribution. \(K\in [-1,1]\) is a random number. \(f_{i}\) represents the fitness value of sparrow i. \(f_{g}\) and \(f_{w}\) denote the current global best and worst fitness values, respectively. \(\varepsilon \) is a constant used to avoid the denominator being 0.

3 Improvement

3.1 Opposition-based Learning(OBL)

OBL was first proposed by Tizhoosh [14], and a large amount of variants of opposition-based learning were proposed, such as quasi-opposition [15], quasi-reflection [16], comprehensive opposition [17], etc. Studies showed that considering both random outcomes and their opposite results is more advantageous than considering only random results [18]. The concept of opposition-based learning is based on opposite numbers. It is expressed as follows: Let \(x\in [a,b]\) be a real number. Then its opposite number, \(\breve{x}\), is given by following equation:

$$\begin{aligned} \breve{x}=a+b-x \end{aligned}$$
(5)

In higher dimensional space, the extended definition is defined as follows:

Let \({x}\left( {x}_{1}, \ldots , {x}_{d}\right) \) be a point in d-dimensional space and \(x_{i}\in [a_{i},b_{i}]\), \(i=1,2, \ldots , d\). The opposite point of x, \(\breve{x}\left( \breve{x}_{1}, \ldots , \breve{x}_{d}\right) \), can be expressed as:

$$\begin{aligned} \breve{x}_{i}=a_{i}+b_{i}-x_{i} \end{aligned}$$
(6)

Different from basic opposite point, this paper uses a variant strategy called random opposite point [19], which is defined by:

$$\begin{aligned} \breve{x}_{i}=\left\{ \begin{array}{ll} a_{i}+b_{i}-x_{i} &{} \quad rand \ge R \\ x_{i} &{} \quad otherwise \end{array}\right. \end{aligned}$$
(7)

It is reported that by this reverse strategy there are more possible positions than the base reverse strategy, further increasing the diversity of the population.

3.2 Random Opposition-based Sparrow Search Algorithm(ROSSA)

SSA has the disadvantage that when the search is close to the global optimum, the population diversity decreases and it is easy to fall into the local optimum solution [20]. This paper uses random opposition-based strategy to improve SSA. First, a random OBL strategy is used to generate the opposite initial solution when initializing the population, and an elite strategy is used to select better individuals from the initial population and the opposite initial population to form the final initial population. This gives the algorithm an advantage at the beginning. Meanwhile, the producers in SSA searches the whole search space, and random opposition-based strategy can effectively increase the population diversity and optimize the global search ability.

Both producers and scouters in SSA can enhance the global exploration ability of the algorithm, but their proportion is fixed, which does not balance well between global exploration and local exploitation in the first and second stages of SSA algorithm. Therefore, this paper adopts a linear decreasing strategy to control the number of both producers and scouters, which is beneficial to the convergence of the algorithm. The decreasing formula is as follows.

$$\begin{aligned} p=p_{\max }-\left( p_{\max }-p_{\min }\right) \cdot \frac{t}{T} \end{aligned}$$
(8)

where p is the proportion of producers and scouters, \(p_{max}\) and \(p_{min}\) denote the maximum and minimum number of p. In this paper, the maximum and minimum values of both are taken as 0.4 and 0.1, respectively.

The main flow of ROSSA is shown in Algorithm 1.

figure a

3.3 Benchmark Test

To verify the advancedness of the proposed algorithm, PSO, KH, SSA and ROSSA are used to solve these test functions, which are shown in Table 1. In the tests, the population size is set to 30, the total number of iterations is set to 500, and the dimension of each test function are 30. The other properties of the functions are shown in the following table. 30 simulation experiments were conducted for each test function separately, and the mean and variance obtained from 30 experiments were counted as shown in Table 2.

Table 1. benchmark functions
Full size table
Table 2. Test results
Full size table

Among them, F1–F6 are unimodal test functions, which are mainly used to test the exploitation ability of the algorithm. The results of these 6 unimodal functions show that ROSSA has the best effect of finding the best solution for unimodal functions, and can obtain the global optimal solution to all of these 6 functions, and the stability of ROSSA is better than other 3 algorithms.

F7–F11 are multimodal test functions, which have multiple local optimal solutions, and the intelligent optimization algorithm is easy to fall into the local optimum when solving, so the multimodal test functions are mainly used to test the exploration ability of the algorithm. In solving F7, all four algorithms have unsatisfactory results for this function on average, but SSA and ROSSA can explore better positions; in solving F8, F9 and F10, SSA and ROSSA outperform the other two algorithms; in solving F11, both SSA and ROSSA have the ability to find excellent solutions, but ROSSA has a slight advantage. In summary, ROSSA performs better than the other three algorithms in the benchmark function experiments.

Figure 1 shows the convergence curves of the partial functions of each algorithm. The horizontal axis represents the number of update generations and the vertical axis represents the log of the fitness value. It can be seen that, ROSSA has better convergence speed, accuracy and stability.

Fig. 1.
figure 1

Convergence curves of partial functions: (a) F1, (b) F8, (c) F11.

Full size image

4 ROSSA for Path Planning Problems

4.1 Problem Description

In this paper, ROSSA is used to solve the robot path planning problem. The target environment is a two-dimensional plane with static obstacles. Each individual in the algorithm denotes a path, represented by N control points as \(p[p_1,p_2,\ldots ,p_N]\), where p1 is the starting point and \(p_N\) is the end point. In the implementation, the SSA individuals are represented as \([x_2,y_2,x_3,y_3,\ldots ,x_{(N-1)},\) \(y_{(N-1)}]\) for coding. In the actual environment, obstacles have various shapes. In this paper, for the simplification of the environment model, the circumcircle of the obstacle is used to simplify modeling.

4.2 Bezier Curve

Bezier curve was first proposed by engineer P.E. Bezier [21] and is widely used in practices such as computer graphics and mechanical design [22]. Bezier curve is generated by a series of control points and these points are not on the curve except for the start and end points. Given a set of control points \(P_{0},...,P_{n}\), the corresponding Bezier curve can be expressed as

$$\begin{aligned} P(t)=\sum _{i=0}^{n} P_{i} B_{i, n}(t), \quad t \in [0,1] \end{aligned}$$
(9)

where t is the normalized time variable, \(B_{i,n}\) is the Bernstein basis polynomials, which represents the base function in the expression of a Bezier curve:

$$\begin{aligned} B_{i, n}(t)=C_{n}^{i} t^{i}(1-t)^{n-i} \quad i=0,1, \ldots n \end{aligned}$$
(10)

In this way, a smooth curve can be created with only a small number of control points.

4.3 Fitness Function

The purpose of this paper is to find an optimal path for the robot that satisfies the constraints, where the constraints include (1) feasibility, (2) optimality, and (3) safety.

  1. 1.

    Feasibility

    Feasibility is the most important goal of path planning. If the path collides with an obstacle, the fitness should be large, which is set here to 10000:

    $$\begin{aligned} f_{feasible}=\left\{ \begin{array}{ll} 0 &{} \quad if \quad feasible \\ 10000 &{} \quad otherwise \end{array}\right. \end{aligned}$$
    (11)
  2. 2.

    Shortest distance

    The second target is to minimize the length of the solution generated by the algorithm. For simplicity, we choose 100 points on the path and calculate the Euclidean distance between two adjacent points:

    $$\begin{aligned} f_{length}=\sum _{i=1}^{n-1}\left\| p_{i+1}-p_{i}\right\| \end{aligned}$$
    (12)
  3. 3.

    Safety An excellent path should be as far away from obstacles as possible. If the distance between the path and the obstacle is less than the safe distance, \(d_{safe}\), it will be penalized:

    $$\begin{aligned} f_{safe}\left( o_{j}\right) =\left\{ \begin{array}{lr} \left( 1-\frac{d_{\min }\left( o_{j}\right) }{d_{safe}\left( o_{j}\right) }\right) ^{2} &{} \quad if \quad d_{\min }\left( o_{j}\right) \le d_{safe}\left( o_{j}\right) \\ 0 &{} otherwise \end{array}\right. \end{aligned}$$
    (13)
    $$\begin{aligned} f_{risk}=\max \left( f_{safe}\right) \end{aligned}$$
    (14)

    where \(d_{min}(o_{j})\) means the minimum distance of the path from the obstacle j. \(d_{safe}(o_{j})\) can be expressed as follow:

    $$\begin{aligned} d_{safe}\left( o_{j}\right) =k r_{o_{j}} \end{aligned}$$
    (15)

    where k indicates the scale factor and \(r_{o_j}\) denotes the radius of obstacle j.

Considering the above factors, the fitness function of the robot path planning problem can be expressed as:

$$\begin{aligned} f=f_{feasible}+w_{1} * f_{length}+w_{2} * f_{risk} \end{aligned}$$
(16)

4.4 Comparision

The parameters of the path planning model are set as follows: the map is \(500\times 500\), as shown in Fig. 2. The number of control points is 5, the robot moves from (10,10) to (490,490).

Fig. 2.
figure 2

Environments.

Full size image

The objective function of this path planning model is solved using PSO, SSA and ROSSA respectively to obtain the desired paths. The population size is set to 30, each individual is a path, the maximum number of iterations is 500, and 30 simulation experiments are conducted. Figure 3 shows the convergence curves of the three algorithms and related data are shown in Table 3.

Fig. 3.
figure 3

Convergence curve of each environment.

Full size image
Table 3. Performance comparison of three algorithms
Full size table

The comparison in Fig. 3 and Table 3 show that the ROSSA algorithm outperforms the PSO and SSA algorithms for the path planning problem. As can be seen from Fig. 3, due to the opposition-based initialization of ROSSA, the initial solution of ROSSA is in a more optimal position. Meanwhile, the rapid convergence to the better position and the continuous approximation to the optimum can stabilize the convergence to the optimal value. Table 3 shows that the average and minimum fitness values obtained by the ROSSA algorithm are lower than those of the PSO and SSA algorithms, and that it is able to solve the path planning problem stably, resulting in a safe and feasible trajectory that is optimal and satisfies the constraints.

5 Conclusions

In this paper, an improved SSA is used to solve the path planning problem. The random OBL strategy and a linear decreasing strategy are introduced into the basic SSA. These strategies are used to increase the population diversity, balance the local exploitation and global exploration ability of the algorithm, and avoid the algorithm from falling into local optimum. The results of benchmark function test show that the proposed algorithm has a significant improvement in the performance of convergence speed, accuracy and stability. The path planning simulation results show that the path planning based on ROSSA can effectively find the optimal path and steadily plan a feasible and efficient path.