Robot path planning based on shuffled frog leaping algorithm combined with genetic algorithm

3.1 Establish environmental model

In order to search the optimal path of mobile robot successfully, it is necessary to model the working environment of mobile robot reasonably. The establishment of the environment model should not only specify the working environment, starting node and ending node of the mobile robot, but also describe the obstacles that the algorithm may encounter in the process of path search. Choosing a suitable method to model the working environment of mobile robot cannot only improve the optimization ability of the algorithm, but also reduce unnecessary calculation. We got inspiration from reference [28–30] and then made map like Fig. 1. Figure 1 shows a two-dimensional working environment of the mobile robot, including obstacles, starting and ending points of the path. The quadrilateral represents the starting point of the path, the pentagon represents the end point of the path, and the circle represents the obstacle.The starting point and ending point of the robot are represented by (x _sp , y _sp ) and (x _ep , y _ep ), respectively.

OPEN IN VIEWER

Fig. 1

Schematic diagram of enviroment model.

Cubic spline interpolation [31, 32] is a piecewise interpolation method, which forms a smooth curve through a series of interpolation point intervals based on cubic polynomials. The moving path curve fitted by cubic spline interpolation method is smoother, which can ensure that the robot has better dynamic characteristics when it stops or turns suddenly. This is an unparalleled advantage of using straight line and arc to fit the path of mobile robot. In this paper, the cubic spline interpolation method is introduced into the ISFLA to solve the robot path planning problem. In ISFLA, in order to use cubic spline interpolation to obtain a smooth path, it is necessary to correspond the spline nodes to a series of path nodes. Any two path nodes can generate a smooth curve through cubic spline function. The function can be expressed as: S _i  (x) = a _i x³ + b _i x² + c _i x + d _i  (i = 1, 2, …, n). There are four coefficients: a _i , b _i , c _i , d _i in the formula, and there are 4n in the whole interval. Any cubic equation can construct the corresponding cubic spline function by determining the values of these coefficients.

The number of path nodes represents the maximum turning times of the robot in the whole path movement process. Therefore, this paper takes all path nodes on a path as an individual code. Suppose that the coordinates of k known path nodes are (x₁, y₁) , (x₂, y₂) , …, (x _k , y _k ), respectively. The coordinates of the start node and the end node of the path are (x _sp , y _sp ) and (x _ep , y _ep ), respectively. Using the cubic spline interpolation method, l interpolation points can be obtained between the start node, the path node and the end node of the above path. The coordinates of l interpolation points are (x₁, y₁) , (x₂, y₂) , …, (x _l , y _l ), respectively. At this time, the curve composed of the starting node of the path, k path nodes, the ending node of the path and l interpolation point is the travel path of the robot.

3.3 Construction of fitness function

After initializing the population generation, it is necessary to build a fitness function to evaluate the performance of each individual. The tasks of path planning in this paper are as follows: (1) Find the shortest effective path between the starting point and the ending point of the map environment. (2) There are l obstacles with random positions and different sizes in the map environment. The robot needs to avoid these obstacles. Therefore, the fitness function in this paper takes the path length and whether it collides with obstacles as the evaluation indicators. The calculation equation of fitness function value is shown in Equation (3). F = 1 L · ( 1 + o · u )(3) where o represents the penalty coefficient to filter out the poor paths. u represents the number of times that the generated path collides with obstacles in the map environment. If there is no collision between the generated path and the obstacle, u = 0. At this time, the fitness function value is the reciprocal of the robot path length. If the generated path collides with the obstacle, u > 0. After amplification of the penalty coefficient o, a larger value will be obtained. The more times the generated path collides with obstacles, the smaller the fitness function value. L represents the path length of the robot, which can be calculated according to the following Equation (4). L = ∑ i = 1 k - 1 ( x i + 1 - x i ) 2 + ( y i + 1 - y i ) 2(4) where (x _i , y _i ) and (x_i+1, y_i+1) represent the two-dimensional coordinates of the i and i + 1 nodes. k indicates the number of nodes that the generation path passes through.

Population initialization is an essential part of SFLA. The generation of initial population will affect the global performance of the whole algorithm. Therefore, the key is to construct an initial population with high-quality solutions. After the SFLA generates the initial population in a random way, the quality of the generated initial solution is poor due to the blindness of the method. This reduces the convergence efficiency to some extent. Therefore, after the population initialization step is completed, selection, crossover and mutation operators are introduced to improve the quality of the initial solution. And maintain the diversity of the population and accelerate the convergence speed.

3.5 Location update strategy based on central frog

The update method of SFLA has some shortcomings. When the worst frog of the memeplex jumps to the best position of the memeplex and the global best position, if it cannot get a better fitness value, the worst frog of the memeplex will randomly choose a position to jump. We know that in the process of searching for food, individuals can share all the information carried by other individuals and benefit from the whole search process. However, the update method of SFLA cannot make full use of the information carried by other frogs, resulting in the algorithm falling into local optimization. Therefore, this paper proposes a location update strategy based on central frog.

The basic idea of this update strategy is as follows. If the worst frog x _w of the memeplex is updated by the global best frog x _g , the fitness function value of x _g is still not better than x _w . Then frog x _z in the center of memplex will update it again. So as to make full use of all the information carried by the memeplex. Suppose each memeplex has n frogs, the central frog of memeplex is x _z , and the specific calculation method of central frog x _z is shown in Equation (6). x z = { x n + 1 2 n is an odd number x n 2 + 1 n is an even number(6) Use the central frog x _z to update the worst frog x _w . The specific equation is shown in Equation (7). x new = x w + r × ( x z - x w )(7) By proposing the update strategy of the central frog, the global information in each memeplex is effectively used. Instead of simply updating by memeplex optimal frog and global optimal frog. This can avoid ISFLA falling into local optimization.

The flow chart of the ISFLA is shown in Fig. 2. And the main steps of ISFLA are as follows.

OPEN IN VIEWER

Fig. 2

ISFLA flow chart.

Step 1: Establish the environment map, determine the starting point (x _sp , y _sp ) and ending point (x _ep , y _ep ) of the robot. Determine the number of path nodes k and the number of cubic spline interpolation points l according to the environment information.

Step 2: Set the initialization parameters of the algorithm. The initialization parameters include the total number of frogs N, the number of memeplexes m, the number of frogs n in each memeplex, current iteration number Iter, maximum iteration number Iter _ max, iteration rate β, the selection rate gap, the crossover rate P _c , and the mutation rate P _m , etc.

Step 3: Population initialization. N frogs are randomly generated in the definition domain as the initial population, in which the coordinate of the i-th frog in the d-dimensional space is x _i  =  (x_1i, x_2i, …, x _di ).

Step 4: Selection, crossover and mutation operators are introduced to process the initialized population.

Step 5: Use cubic spline interpolation method to insert l insertion points between the path start point, k path nodes and the path end point. Calculate the generation path length according to Equation (4).

Step 6: Perform collision detection. If it collides with an obstacle, a penalty is added to the fitness function.

Step 7: Calculate the fitness values of all individuals according to Equation (3) and arrange them in descending order.

Step 8: Divide the N frogs into m memeplex, with n frogs in each memeplex.

Step 9: Update the worst frog x _w with the best frog x _b of the memeplex. If the new position is better than the original position, replace the original position with the new position. Otherwise, the global optimal frog x _g is used to update the worst frog x _w . If the new position is still worse than the original position, the worst frog x _w is updated with the central frog x _z of the memeplex. If the new position is better than the original position, the original position is replaced with the new position. Otherwise, a new position is randomly generated to replace the original position.

Step 10: After all memeplexes complete local search, all frogs will be shuffled.

Step 11: Judge whether the current iteration number Iter has reached β · Iter _ max. If not, go to Step 4 again for selection, crossover and mutation. If reached, proceed to the Step 12.

Step 12: Judge whether the current iteration number Iter reaches the maximum iteration number Iter _ max. If so, output the optimal solution. If not, go to Step 7 for the next iteration. This is repeated until the end condition of the algorithm is met.

4.1 Parameter setting and analysis

In order to eliminate the differences of different algorithms in the experiment as much as possible and ensure the fairness of the experiment. In this paper, some parameters are set uniformly. Each algorithm runs 20 times in seven different maps, and the maximum iteration number Iter _ max is 500. Each algorithm has 150 populations, 5 processing nodes and 150 interpolation points. Other relevant parameters will refer to the settings in reference [38].

In addition, in order to improve the performance of ISFLA, it is necessary to discuss its parameter settings. These parameters include crossover rate (P _c ), mutation rate (P _m ), size of memeplex (m), number of memeplex (n) and iteration rate of GA (β). The default parameter is set to P _c  = 0.5, P _m  = 0.05, m = 30, n = 5, β = 0.2. In the experiment, the probability of P _c is generally distributed at (0.1, 0.9), and the probability of P _m is set at (0.01,0.09). We randomly selected Map 2 to test it to determine the best parameters of ISFLA. The schematic diagram of the environment model is shown in Fig. 1.

Under the condition that other parameters are the same, Table 1 gives the path length statistical results of ISFLA running 20 times independently in Map 2 with different parameters. In order to better carry out parameter analysis, we have made outstanding effects on the optimal results.

It can be seen from Table 1 that when only parameter P _c is changed, the L_min and L_avg of ISFLA do not get better with the increase or decrease of the standard parameter value. Even when P _c  = 0.4, the L_avg reaches the maximum in the five groups of data. When P _c  = 0.7, the L_std is also the worst in the data. It shows that the stability of ISFLA hasn’t been improved with the increase or decrease of standard parameters. In contrast, when P _c  = 0.5, the L_min, L_avg and L_std of ISFLA are the optimal solutions, so it is most appropriate to set the parameter P _c to 0.5. Similarly, by analyzing the data in Table 2, it is not difficult to see that the stability of ISFLA has not been improved with the increase or decrease of standard parameter values. When P _m  = 0.05, although the L_min value of ISFLA is not the optimal value, it is also second only to the solution when P _m  = 0.04. At this time, the L_max, L_avg and L_std are the optimal solutions. From the comprehensive situation, it is most appropriate to set the parameter P _m to 0.05.

Table 3 shows several groups of experimental data about the size and number of memeplexes. It can be seen from the data that with the increase of the number of memeplexes, the running time of ISFLA increases correspondingly. When the number of memeplexes n = 10, the running time is much longer than the original SFLA. Therefore, when the population is divided into 10 memeplexes or more, it is not suitable for parameter selection. When the population is divided into two or three memeplexes, the robustness of the algorithm is difficult to be satisfied. Based on the data in Table 3, only when the number of memeplexes n = 5, L_min, L_max, L_avg and R_time of ISFLA have good performance. Therefore, m = 10, n = 5 are selected as the final parameter.

Table 4 introduces the algorithm performance under different iteration rate. It can be seen from the path planning results that as the number of iteration increases, more time is consumed. This is because each genetic operation needs to calculate the fitness value, which increases the operation time. When the iteration rate β = 0.6, L_min and L_std of ISFLA are optimal, but the running time is too long, so it is not suitable to be used as the final parameter. When β = 0.2, the difference between L_min and the optimal solution is very small, L_max and L_avg are the optimal solutions, and R_time is the shortest. By comprehensive comparison, β = 0.2 is the most appropriate iteration rate.

To sum up, in order to improve the performance of ISFLA, this paper has conducted experimental analysis on four parameters such as crossover rate and mutation rate. Under the comprehensive consideration of different evaluation standards, this paper selects P _c  = 0.5, P _m  = 0.05, m = 30, n = 5, β = 0.2 as the final experimental parameter to participate in ISFLA.

The performance of the five algorithms can be evaluated by comparing their path planning performance in the map. All obstacle models in the map are circular, and the number of interpolation points is 150. Table 5 shows the path length statistical results of the five algorithms running independently for 20 times in seven maps. In order to facilitate observation and better analyze the data, the optimal data in the table has been highlighted.

Figure 3 shows the L_min comparison diagram of each algorithm in Map 1-Map 7. Figure 4 shows the iteration curve of each algorithm in Map 1. It can be seen from Table 5 and Fig. 3 (a) that although the SFLA finds the suboptimal solution of L_min, the L_std of the path is the worst. This is because the SFLA randomly generates uneven initial solutions, and the output optimal solutions are also quite different, resulting in poor stability of the SFLA. The L_avg and L_std of ISFLA are better than the other four algorithms, indicating that ISFLA has the best robustness, while the SFLA is the worst. Figure 4 shows the iteration curve of each algorithm in Map 1. It can be seen from Fig. 4 that in the first 100 iterations of the algorithm, the quality of ABC, PSO and SFLA solutions is poor, and there are many infeasible solutions. SFLA tends to converge at 100 iterations, which indicates that the algorithm falls into local optimization. And in the last 400 iterations, it failed to jump out of the local optimum. The solution of ISFLA is of high quality and the convergence speed of the algorithm is very fast. It shows that the location update strategy based on central frog is effective.

OPEN IN VIEWER

Fig. 3

Comparison of minimum paths of algorithms in Map 1-Map 7(a-g).

OPEN IN VIEWER

Fig. 4

First 100 (a)and last 400(b) iteration curves of each algorithm in Map 1.

Figure 3 (b) shows the path planning results of each algorithm in Map 2. Among them, the L_min of SFLA and SMA is the optimal solution, followed by ISFLA. The L_avg of the path planned by ISFLA is the smallest, followed by SMA, and ABC is the worst, indicating that the stability of ISFLA in Map 2 is the best, and ABC is the worst.

Figure 3 (c) shows the path planning results of each algorithm in Map 3. It can be seen from Table 5 that the L_min of ISFLA is the optimal solution, followed by SFLA. Although ABC regularizes a smooth path, it is quite different from other algorithms. In terms of L_avg, which planned by ISFLA is the smallest, followed by SMA, and SFLA is the worst.

Figure 3 (d) shows the path planning results of each algorithm in Map 4. In Fig. 3 (d), the L_min planned by ABC is not smooth and has turning points, and the effect is the worst. The L_min of ISFLA is the optimal solution. From the results of L_avg and L_std, the stability of ISFLA is also the best among the five algorithms, SMA is the second, and ABC is the worst.

Figure 3 (e), Fig. 3 (f) and 3 (g) show the path planning results of the algorithms in Maps 5, 6 and 7, respectively. The results of the three maps are similar. The optimal solution of the L_min is still ISFLA, and the worst solution is ABC. But the L_std of ABC is the best, followed by ISFLA. This is because the L_max and the L_min planned by ABC are very close, resulting in a small final L_avg. However, the L_avg is still the worst of the five algorithms, and the best result is ISFLA, indicating that the stability of ISFLA is the best. Figure 5 shows the iteration curve of each algorithm in Map 6. As can be seen from Fig. 5, each algorithm gradually converges during the first 100 iterations. However, at the late stage of algorithm iteration, ABC and PSO all fall into local optimization. When ISFLA reaches 150 iterations, it has completely converged and obtained the optimal solution. The convergence speed of the algorithm is very fast, followed by SFLA. It shows that the improved strategy of fusion GA is effective. The comprehensive simulation results show that ISFLA performs well on seven different maps. It is superior to the other four algorithms in the minimum and average path length, and ISFLA has good robustness. Experimental results show that the fusion of GA and improved update strategy can improve the performance of the algorithm.

OPEN IN VIEWER

Fig. 5

First 100 (a)and last 400(b) iteration curves of each algorithm in Map 6.