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

Abstract

When the shuffled frog leaping algorithm (SFLA) is used to solve the robot path planning problem in obstacle environment, the quality of the initial solution is not high, and the algorithm is easy to fall into local optimization. Herein, an improved SFLA named ISFLA combined with genetic algorithm is proposed. By introducing selection, crossover and mutation operators in genetic algorithm, the ISFLA not only improves the solution quality of the SFLA, but also accelerates its convergence speed. Moreover, the ISFLA also proposes a location update strategy based on the central frog, which makes full use of the global information to avoid the algorithm falling into local optimization. By comparing ISFLA with other algorithms including SFLA in the map environment of different obstacles, it is confirmed that ISFLA can effectively improve the minimum path optimization and robustness in the simulation experiments of mobile robots.

Keywords

Robot path planning shuffled frog leaping algorithm genetic algorithm location update strategy

1 Introduction

Memetic algorithms (MAs) [1, 2] is a special heuristic search method derived from the adaptive model of natural systems. The model combines the convergence adaptation of the population with the individual learning in the life cycle of the members. The word MAs comes from "memes", which can be understood as cultural genes. Different from genes, cultural genes have the characteristics of inheritance and transmission. The combination mechanism of global search and local search of meme algorithm makes its search efficiency several orders of magnitude faster than that of traditional intelligent algorithm in some problem areas. It has been applied to a wide range of optimization problems with satisfactory results.

The SFLA proposed by Eusuff and Lansey in 2003 [3] is also a member of MAs family, which simulates the jumping and foraging behavior of a group of frogs in the pond. It combines the advantages of MAs based on memes convergence and particle swarm optimization (PSO) based on group behavior. The algorithm has the characteristics of simple concept, less adjustment parameters, fast computing speed, strong global search and optimization ability, easy to implement and so on. At present, many scholars have applied it to the research of path planning problems [4, 5].

Paikray [6] proposed an improved SFLA for multi robot path planning in clutter environment to avoid premature convergence and falling into local optimization. By evaluating the optimal follow-up position of the robot in the environment, a collision free smooth optimal path is generated. Hidalgo-Paniagua [7] proposed a multi-objective method based on SFLA to solve the path planning problem. They considered path security, path length and path smoothness as objectives, and used 8 real-world scenarios for experimental evaluation. For the robot path planning problem, Singh [8] proposed a hybrid algorithm of teaching learning based optimization algorithm and SFLA. Thus, the search efficiency is improved and the convergence speed is accelerated. In addition to the application of SFLA in path planning, there are many other algorithms that are also committed to solving such problems. Such as PSO [9 –11], artificial bee colony algorithm (ABC) [12, 13], slime mould algorithm (SMA) [14], genetic algorithm (GA) [15 –17], etc.

Among the above algorithms, ABC is a bionic swarm intelligence algorithm proposed by Karaboga in 2005. Due to its advantages of fast search speed, few parameters and easy implementation, it has been successfully applied in many fields, such as task scheduling [18], image processing [19], solving TSP problems [20, 21]. In fact, the ABC is inspired by the process of bees looking for honey sources. When the algorithm solves the path planning problem, the honey source represents a feasible path, and the income degree of the honey source represents the constraints of the problem (such as time, path length, obstacle avoidance, etc). PSO is a swarm intelligence optimization algorithm proposed by Eberhart and Kennedy in 1995, which is used to simulate the swarm behavior of birds. It has the advantages of fast convergence, few parameters and simple implementation. In recent years, PSO has been widely used in various robot optimization problems, such as controller optimization, autonomous navigation, mobile robot path planning and so on. SMA is an optimization algorithm based on the foraging behavior of slime moulds. Slime moulds will oscillate and contract when they find food in the process of foraging. At the same time, a vein network of different thickness will be formed between multiple honey sources, and the thickness of the vein network is related to the quality of honey sources. In addition, slime moulds still have a certain probability to search unknown areas when they obtain honey sources.

Compared with the above algorithms, SFLA has the advantages of fast computing speed when dealing with the path planning problem, but it also has some shortcomings. For example, in the experiment of using SFLA to solve the robot path planning problem, we found that if the initial solution quality of the population is good, the path planned by SFLA can converge quickly. Otherwise, the convergence speed of the path will be reduced. That is, SFLA will generate a population randomly in the initialization phase, which will lead to uneven quality of the population solution, thus affecting the subsequent convergence speed of the algorithm. It is not difficult to see that the initial solution of the population is of great significance to the results of path planning. In addition, we found that the original SFLA location update strategy also had some defects. That is, its location update strategy is not detailed enough, and only part of the information in memplex is used. The failure to effectively use the meme information in each memeplex results in a waste of information resources, which makes the algorithm easy to fall into local optimization. Therefore, we can further improve the existing location update strategy to obtain better results.

In this context, we proposes an improved SFLA robot path planning algorithm based on fusion GA, called ISFLA. The first contribution of our work is, after the initialization of the population, selection, crossover and mutation operators are introduced. Thus, the quality of the initial solution is improved, and the convergence speed of the algorithm is accelerated. The second contribution is to improve the location update strategy of SFLA. On the basis of the original location update strategy, the center frog update strategy is added, which effectively uses the global information of the population and avoids the algorithm from falling into local optimization.

The rest of the paper is organized as follows: the second part introduces the SFLA. The third part introduces the details of ISFLA strategy improvement. The fourth part carries on the experimental simulation in different map environments, and compares the improved algorithm with other algorithms. The fifth part summarizes the work of this paper and puts forward some suggestions for improvement in the future.

2 Shuffled frog leaping algorithm

SFLA belongs to swarm intelligence optimization algorithm. Each frog in the algorithm represents a solution to the problem. The basic mathematical model of SFLA is as follows.

a) 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). By calculating the fitness value of each frog, all frogs are arranged in descending order according to the fitness value.

b) Population division

Divide the whole population into a memeplexes, each memeplex contains b frogs, which satisfies the relation N = a × b. In the iteration process, the first frog is placed in the first memeplex, the second frog is placed in the second memeplex, and the allocation is carried out in this order until the a-th frog is placed in the a-th memeplex. Then the (a + 1)-th frog is placed in the first memeplex, the (a + 2)-th frog is placed in the second memeplex. And so on, until all frogs are allocated. In each memeplex, the frogs with the best and worst fitness are recorded as x_b and x_w, respectively. while the frogs with the best fitness in the whole population are recorded as x_g.

c) Local search

Local search for each memeplex, that is, update x_w in the memeplex. The update strategy is as follows. ${\begin{matrix} s_{i} = r \times (x_{b} - x_{w}), (s_{min} \leq s_{i} \leq s_{max}) \\ x_{new} = x_{w} + s_{i} \end{matrix}$ (1) where s_i represents the i-th update step of x_w in the memeplex. r is the random number between (0,1). s_max and s_min are the maximum and minimum steps allowed for the frog to move. x_new is the new frog generated by updating x_w. If the fitness value of x_new is better than that of x_w, x_new is used to replace x_w. Otherwise, replace x_b with x_g to obtain a new Equation (2), and update x_w. ${\begin{matrix} s_{i} = r \times (x_{g} - x_{w}), (s_{min} \leq s_{i} \leq s_{max}) \\ x_{new} = x_{w} + s_{i} \end{matrix}$ (2)

If the fitness value of x_new is better than x_w, use x_new instead of x_w. Otherwise, a new frog is randomly generated in the definition domain to replace the original x_w. Each memeplex repeats the above local search until the specified number of local searches is reached.

c) Shuffling process

When all memeplexes have completed the local search, all frogs will be shuffled. The population division and local search are performed again. Repeat the operation until the end condition of the algorithm is met.

Based on swarm intelligence heuristic computing technology, SFLA has efficient computing performance and good global search capability. At present, it has been used to solve various problems. For example, Tang [22] proposed lévy flight-based SFLA for continuous optimization problems. The attractor based on lévy flight is introduced into the local search process, and the interactive learning rules are used in the global search process to improve the search ability of the algorithm. Huang [23] proposed a discrete SFLA based on heuristic information. Taking the traveling salesman problem as a test problem, four improved search strategies are designed to improve the performance of the algorithm. Elattar [24] proposed an improved SFLA. By improving the local search mechanism and global search mechanism of the original SFLA, the combined heat, emission and economic dispatch of wind and solar power generation is solved. Li [25] proposed a new improved SFLA called chaotic catfish effect SFLA. Chaos technology is introduced into the local "refine search" mechanism to improve the local search ability, and the global convergence is improved by stimulating the frog to jump out of the local steady state. Cai [26] studied the distributed hybrid flowshop scheduling problem with multiprocessor tasks, and proposed a dynamic SFLA to minimize the maximum completion time. Chen [27] designed a multi strategy driven SFLA that integrates horizontal and vertical cross search for multi threshold image segmentation. Horizontal cross search enables different frogs to exchange information, and enhances the exploration ability of each frog. At the same time, vertical cross search can help frogs jump out of the local optimum.

3 Improved shuffled frog leaping algorithm for robot path planning

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.

Fig. 1

Schematic diagram of enviroment model.

3.2 Cubic spline interpolation

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_ix³ + b_ix² + c_ix + 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 = \frac{1}{L \cdot (1 + o \cdot 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 = \sum_{i = 1}^{k - 1} \sqrt{{(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.

3.4 Improvement strategy of fusion genetic algorithm

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.4.1 Selection operation

The operation of selecting the superior individuals from the group and eliminating the inferior individuals is called selection. For the path planning of mobile robot, this paper adopts roulette selection method [33, 34]. The selection probability of each individual is proportional to its fitness value. The optimal individual can be retained and the individual quality of the initial population solution can be improved. Assuming that the fitness value of individual i is F_i, the probability P_i of selecting i is expressed as Equation (5). $P_{i} = \frac{F_{i}}{\sum_{i = 1}^{N} F_{i}} (i = 1, 2, \dots, N)$ (5) where N represents the population number. Equation (5) shows that the greater the fitness value of individual i, the greater the probability of being selected.

3.4.2 Crossover operation

The recombination and mutation of biological genetic genes play a central role in the process of biological convergence in nature, and the essence of crossover operation is to simulate the process of individual gene recombination. In this paper, the single point crossover method [35, 36] is adopted for the crossover operation. The specific steps are as follows: when the crossover conditions are met, in addition to the start node and the end node, a path node in two individuals is randomly selected as the crossover point. Then the two individuals carry out the crossover operation at the crossover point. The following is further illustrated by examples. Assuming that the two individuals participating in the crossover operation are p ={ sp, p₁, …, p_i, …, p_n, ep } and q ={ sp, q₁, …, q_i, …, q_n, ep }, respectively. p_i and q_i are the intersections. When p and q crossover at the intersection of p_i and q_i, the two new individuals generated are p_new ={ sp, p₁, …, q_i, …, q_n, ep } and q_new ={ sp, q₁, …, p_i, …, p_n, ep }, respectively.

3.4.3 Mutation operation

The basic content of mutation operation is to change the gene value at some loci of individual string in the population. In this paper, random mutation method [37] is used for mutation operation. The specific steps are as follows: when the mutation conditions are met, a position other than the starting point and the ending point in the path is randomly selected as the mutation point. A new individual is regenerated at the mutation point according to the random search strategy in population initialization. Then a smooth path is generated by cubic spline interpolation method to complete the mutation operation. The example is as follows: assuming that the individual participating in the mutation operation is j ={ sp, j₁, …, j_i, …, j_n, ep } and j_i is the mutation point. The new individual generated by using the random search strategy in population initialization is k ={ sp, k₁, …, k_i, …, k_n, ep }. Replace k_i in the generated new individual k with j_i in the mutation operation individual j, so as to generate a new individual j_new ={ sp, j₁, …, k_i, …, j_n, ep }. By introducing random mutation operation, the diversity of the initial population can be maintained.

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} = {\begin{matrix} x_{\frac{n + 1}{2}} & n is an odd number \\ x_{\frac{n}{2} + 1} & n is an even number \end{matrix}$ (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 \times (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.

3.6 Main procedures of improved shuffled frog leaping algorithm

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

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 Experimental results and analysis

In order to verify the effectiveness of ISFLA, this paper designed seven groups of experiments under different environmental maps. The small square in the map represents the starting point and the small five pointed star represents the ending point. At the same time, the superiority of ISFLA is tested by comparing with ABC, PSO, SFLA and SMA. In order to find a collision free shortest path in the map environment, the minimum path length (L_min), the maximum path length (L_max), the average path length (L_avg), the standard deviation of path length (L_std) and the average running time (R_time) in the experiment are used as evaluation criteria. Finally, the performance of the algorithm is analyzed according to the statistical results.

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.

Table 1
Path planning results under different crossover rates

P _c L _min L _max L _avg L _std

0.4 15.7615 15.8504 16.0050 0.0644

0.5 15.7556 15.8822 15.8256 0.0461

0.65 15.7652 16.2043 15.8613 0.0924

0.7 15.7591 16.7264 15.8850 0.2060

0.85 15.7570 15.9810 15.8333 0.0551

P _c	L _min	L _max	L _avg	L _std
0.4	15.7615	15.8504	16.0050	0.0644
0.5	15.7556	15.8822	15.8256	0.0461
0.65	15.7652	16.2043	15.8613	0.0924
0.7	15.7591	16.7264	15.8850	0.2060
0.85	15.7570	15.9810	15.8333	0.0551

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 2

Path planning results under different mutation rates

P _m	L _min	L _max	L _avg	L _std
0.04	15.7542	15.9839	15.8386	0.0620
0.05	15.7556	15.8822	15.8256	0.0461
0.065	15.7642	16.7013	15.8921	0.1927
0.07	15.7595	15.9542	15.8452	0.0562
0.085	15.7567	15.9659	15.8605	0.0554

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 3

Path planning results under different number and size of memeplex

m	n	L _min	L _max	L _avg	L _std	R_time
75	2	15.7546	15.9945	15.8616	0.0577	51.3683
50	3	15.7573	17.1859	15.9505	0.3106	55.5518
30	5	15.7556	15.8822	15.8256	0.0461	65.7216
15	10	15.7606	15.9729	15.8519	0.0488	95.3745
10	15	15.7623	15.9189	15.8425	0.0427	123.8874

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.

Table 4

Path planning results under different iteration rate β

β	L _min	L _max	L _avg	L _std	R_time
0.2	15.7556	15.8822	15.8256	0.0461	65.7216
0.3	15.7536	15.9569	15.8425	0.0465	73.9073
0.4	15.7530	16.0104	15.8586	0.0781	80.3830
0.5	15.7681	16.0444	15.8651	0.0489	84.0030
0.6	15.7524	15.9457	15.8481	0.0436	90.0380

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.

4.2 Experiments in different map environments

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.

Table 5
Path planning performance of each algorithm in different map environments

ABC PSO SFLA SMA ISFLA

Map1 L _min 7.4759 7.4392 7.4195 7.4402 7.4157

L _max 7.7826 7.7890 7.7814 7.8129 7.7432

L _avg 7.5989 7.5312 7.6165 7.7360 7.4458

L _std 0.0935 0.1248 0.1568 0.0715 0.0708

Map2 L _min 15.4284 14.3269 14.3028 14.3028 14.3059

L _max 16.5377 16.3621 16.6857 15.3626 14.5561

L _avg 15.8888 14.4508 14.8374 14.3718 14.3212

L _std 0.3421 0.4501 0.8084 0.2338 0.0553

Map3 L _min 16.0016 15.8151 15.7706 15.7842 15.7556

L _max 16.2594 16.5895 18.6174 16.0357 15.8822

L _avg 16.1030 15.9418 16.1756 15.8646 15.8256

L _std 0.0568 0.1661 0.6436 0.0679 0.0461

Map4 L _min 23.1353 21.5756 21.4970 21.5302 21.4922

L _max 23.3973 24.3694 27.3036 23.2571 21.6154

L _avg 23.3298 22.3926 23.2465 22.8897 21.5226

L _std 0.0535 0.9720 1.5496 0.7099 0.0289

Map5 L _min 17.5383 14.5884 14.5330 17.5185 14.5171

L _max 17.5626 17.6263 20.9882 18.2417 15.3751

L _avg 17.8450 15.2269 15.8284 17.7441 14.6549

L _std 0.0670 1.0995 2.1054 0.2642 0.2370

Map6 L _min 16.8985 14.5477 14.5090 14.5572 14.4934

L _max 16.9465 25.6437 35.0113 17.0447 15.6811

L _avg 16.9169 17.3427 18.7935 15.5520 14.5830

L _std 0.0140 3.4316 5.9422 1.0989 0.2652

Map7 L _min 17.9694 14.5969 14.5417 14.5408 14.5135

L _max 17.9871 95.3578 18.0044 18.4595 14.9089

L _avg 17.9741 19.9232 15.1698 17.9045 14.5653

L _std 0.0042 18.3215 1.0199 0.8067 0.1143

		ABC	PSO	SFLA	SMA	ISFLA
Map1	L _min	7.4759	7.4392	7.4195	7.4402	7.4157
	L _max	7.7826	7.7890	7.7814	7.8129	7.7432
	L _avg	7.5989	7.5312	7.6165	7.7360	7.4458
	L _std	0.0935	0.1248	0.1568	0.0715	0.0708
Map2	L _min	15.4284	14.3269	14.3028	14.3028	14.3059
	L _max	16.5377	16.3621	16.6857	15.3626	14.5561
	L _avg	15.8888	14.4508	14.8374	14.3718	14.3212
	L _std	0.3421	0.4501	0.8084	0.2338	0.0553
Map3	L _min	16.0016	15.8151	15.7706	15.7842	15.7556
	L _max	16.2594	16.5895	18.6174	16.0357	15.8822
	L _avg	16.1030	15.9418	16.1756	15.8646	15.8256
	L _std	0.0568	0.1661	0.6436	0.0679	0.0461
Map4	L _min	23.1353	21.5756	21.4970	21.5302	21.4922
	L _max	23.3973	24.3694	27.3036	23.2571	21.6154
	L _avg	23.3298	22.3926	23.2465	22.8897	21.5226
	L _std	0.0535	0.9720	1.5496	0.7099	0.0289
Map5	L _min	17.5383	14.5884	14.5330	17.5185	14.5171
	L _max	17.5626	17.6263	20.9882	18.2417	15.3751
	L _avg	17.8450	15.2269	15.8284	17.7441	14.6549
	L _std	0.0670	1.0995	2.1054	0.2642	0.2370
Map6	L _min	16.8985	14.5477	14.5090	14.5572	14.4934
	L _max	16.9465	25.6437	35.0113	17.0447	15.6811
	L _avg	16.9169	17.3427	18.7935	15.5520	14.5830
	L _std	0.0140	3.4316	5.9422	1.0989	0.2652
Map7	L _min	17.9694	14.5969	14.5417	14.5408	14.5135
	L _max	17.9871	95.3578	18.0044	18.4595	14.9089
	L _avg	17.9741	19.9232	15.1698	17.9045	14.5653
	L _std	0.0042	18.3215	1.0199	0.8067	0.1143

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.

Fig. 3

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

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.

Fig. 5

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

5 Conclusions and future works

In summary, the ISFLA combined with GA is proposed to solve the problems of low initial solution quality and easy to fall into local optimization in robot path planning existing in the SFLA. The ISFLA screens and optimizes the initial solution by introducing the selection, crossover and mutation operators of GA. This approach improves the quality of the initial solution after population initialization, thereby increasing the convergence speed of the SFLA. Subsequently, this paper designs a location update strategy based on the center frog. By updating the worst frog in the memeplex once more, the information carried by each frog in the memeplex is fully utilized to avoid the algorithm falling into local optimization. Furthermore, seven maps of different obstacle environments are designed to validate ISFLA. The final experimental results show the effectiveness of the improved strategy, and the path planned by ISFLA is shorter and has better robustness. However, the improvement of the SFLA still has some shortcomings, such as improving the update strategy of the SFLA will lead to an increase in the computational cost. In addition, this paper only considers the robot path planning problem in the static obstacle environment, but there are most cases with complex dynamic obstacles in practical applications. Therefore, the next research direction is to solve the optimal path planning problem of robots in complex dynamic environments.

Footnotes

Acknowledgments

This work is supported by the Xuzhou Science and Technology Program (KC21001), National Natural Science Foundation of China (62173166).

References

Wilson

A.J.

, Pallavi

D.R.

, Ramachandran

, Chinnasamy

and Sowmiya

, A review on memetic algorithms and its developments, Electrical and Automation Engineering 1(1) (2022), 7–12.

Berahhou

, Benadada

and Bouanane

, Memetic algorithm for thedynamic vehicle routing problem with simultaneous delivery and pickup, International Journal of Industrial Engineering Computations 13(4) (2022), 587–600.

Eusuff

M.M.

and Lansey

K.E.

, Optimization of water distributionnetwork design using the shuffled frog leaping algorithm, Journal of Water Resources Planning and Management 129(3) (2003), 210–225.

Ab Wahab

M.N.

, Nefti-Meziani

and Atyabi

, A comparative reviewon mobile robot path planning: Classical or meta-heuristic methods? Annual Reviews in Control 50 (2020), 233–252.

Hassanzadeh

, Madani

and Badamchizadeh

M.A.

, Mobile robot path planning based on shuffled frog leaping optimization algorithm, In: 2010 IEEE International Conference on Automation Science and Engineering (2010), 680–685.

Paikray

H.K.

, Das

P.K.

, Panda

and Balabantaray

B.K.

, Improved shuffled frog leaping algorithm for path planning of multiple mobile-robot, In: 2019 2nd International Conference on Innovations in Electronics, Signal Processing and Communication (IESC) (2019), 132–137.

Hidalgo-Paniagua

, Vega-Rodríguez

M.A.

, Ferruz

and Pavón

, MOSFLA-MRPP: multi-objective shuffled frog-leapingalgorithm applied to mobile robot path planning, Engineering Applications of Artificial Intelligence 44 (2015), 123–136.

Singh

, Sharma

and Sharma

, Shuffled teaching learning-basedalgorithm for solving robot path planning problem, International Journal of Metaheuristics 7(3) (2020), 265–283.

, Cao

M.Y.

and Song

B.Y.

, A new approach to smooth pathplanning of mobile robot based on quartic Bezier transition curveand improved PSO algorithm, Neurocomputing 473 (2022), 98–106.

10.

Song

B.Y.

, Wang

Z.D.

and Zou

, An improved PSO algorithm forsmooth path planning of mobile robots usingcontinuous high-degree Bezier curve, Applied Soft Computing 100 (2021), 106960.

11.

Zhang

, Zhang

Y.J.

and Li

Y.F.

, Mobile robot path planning basedon improved localized particle swarm optimization, IEEE Sensors Journal 21(5) (2020), 6962–6972.

12.

Contreras-Cruz

M.A.

, Ayala-Ramirez

and Hernandez-Belmonte

U.H.

, Mobile robot path planning using artificial bee colony andevolutionary programming, Applied Soft Computing 30(2015), 319–328.

13.

, Mo

H.W.

and Sun

, Group path planning based on variabledimension ABC algorithm, International Journal of u-ande-Service, Science and Technology 9(1) (2016), 81–90.

14.

Jones

, A morphological adaptation approach to path planninginspired by slime mould, International Journal of GeneralSystems 44(3) (2015), 279–291.

15.

Lamini

, Benhlima

and Elbekri

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

16.

Zhang

Z.J.

, Lu

, Zhao

M.L.

, Luan

S.Y.

and Bu

, Robot path planning based on genetic algorithm with hybrid initialization method, Journal of Intelligent & Fuzzy Systems 42(3) (2022), 2041–2056.

17.

Elhoseny

, Shehab

and Yuan

X.H.

, Optimizing robot path indynamic environments using genetic algorithm and bezier curve, Journal of Intelligent & Fuzzy Systems 33(4) (2017), 2305–2316.

18.

Jena

R.K.

, Task scheduling in cloud environment: a multi-objectiveABC framework, Journal of Information & Optimization Sciences 38(1) (2017), 1–19.

19.

Cuevas

, Artificial bee colony (ABC) algorithm and its use indigital image processing, Inteligencia Artificial 18(55) (2015), 50–68.

20.

Shah

K.S.

and Soni

U.H.

, Travelling salesman problem (TSP) forvehicle route optimization in MANETs using ABC algorithm, International Journal for Research in Applied Science and Engineering Techhnology 2 (2014), 459–468.

21.

Hasan

L.S.

, Artificial bee colony algorithm and bat algorithm forsolving travel salesman problem, Webology 19(1) (2022), 4185–4193.

22.

Tang

D.Y.

, Yang

, Dong

S.B.

and Liu

, A lévy flight-basedshuffled frog leaping algorithm and its applications for continuousoptimization problems, Applied Soft Computing 49 (2016), 641–662.

23.

Huang

, Shen

X.N.

and You

, A discrete shuffled frog-leapingalgorithm based on heuristic information for traveling salesmanproblem, Applied Soft Computing 102 (2021), 107085.

24.

Elattar

E.E.

, Environmental economic dispatch with heat optimizationin the presence of renewable energy based on modified shuffle frogleaping algorithm, Inteligencia Artificial 171 (2019), 256–269.

25.

R.B.

, Jiang

Z.Q.

, Li

A.Q.

, Yu

and Ji

C.M.

, An improved shuffled frog leaping algorithm and its application in the optimization of cascade reservoir operation, Hydrological Sciences Journal 63(15-16) (2018), 2020–2034.

26.

Cai

J.C.

, Zhuo

and Lei

D.M.

, Dynamic shuffled frog leaping algorithm for distributed hybrid flow shop scheduling with multiprocessor tasks, Engineering Applications of Artificial Intelligence 90 (2020), 103540.

27.

Chen

, Wang

M.J.

, Wang

A.A.

, Shi

B.B.

, Hu

Z.Y.

, Zhang

, Chen

H.L.

, Mafarja

and Turabieh

, Multi-threshold image segmentation using a multi-strategy shuffled frog leaping algorithm, Expert Systems with Applications 194 (2022), 116511.

28.

Dian

, Zhong

, Guo

, Liu

and Guo

, A smooth path planning method for mobile robot using a BES-incorporated modified QPSO algorithm, Expert Systems with Applications 208 (2022), 118256.

29.

Qadir

, Zafar

M.H.

, Moosavi

S.K.R.

, Le

K.N.

and Mahmud

M.P.

, Autonomous UAV path-planning optimization using metaheuristic approach for predisaster assessment, IEEE Internet of Things Journal 9 (2021), 12505–12514.

30.

, Gai

, Zhang

and Zhong

, A novel hybrid grey wolf optimizer algorithm for unmanned aerial vehicle (UAV) path planning, Knowledge-Based Systems 194 (2020), 105530.

31.

Sun

Y.X.

, Zhang

C.R.

, Sun

P.C

and Liu

, Safe and smooth motion planning for Mecanum-wheeled robot using improved RRT and cubicspline, Arabian Journal for Science and Engineering 45(4) (2020), 3075–3090.

32.

Gupta

, Sharma

D.K.

and Shivani

, A new hybrid image enlargementmethod using singular value decomposition and cubic splineinterpolation, Multimedia Tools and Applications 81(3) (2022), 4241–4254.

33.

Qian

W.W.

, Chai

J.R.

, Xu

Z.G.

and Zhang

Z.Y.

, Differential evolution algorithm with multiple mutation strategies based on roulette wheel selection, Applied Intelligence 48(10) (2018), 3612–3629.

34.

Halim

, Yousaf

M.N.

, Waqas

, Sulaiman

, Abbas

, Hussainand

and Hanif

, An effective genetic algorithm-based feature selection method for intrusion detection systems, Computers & Security 110 (2021), 102448.

35.

Magalhaes-Mendes

, A comparative study of crossover operators forgenetic algorithms to solve the job shop scheduling problem, WSEAS Transactions on Computers 12(4) (2013), 164–173.

36.

Xue

, Zhu

, Liang

and Słowik

, Adaptive crossoveroperator based multi-objective binary genetic algorithm for featureselection in classification, Knowledge-Based Systems 227(2021), 107218.

37.

Ferrandez

S.M.

, Harbison

, Weber

, Sturges

and Rich

, Optimization of a truck-drone in tandem delivery network usingk-means and genetic algorithm, Journal of Industrial Engineering and Management 9(2) (2016), 374–388.

38.

Agarwal

and Bharti

P.S.

, Implementing modified swarm intelligence algorithm based on Slime moulds for path planning and obstacle avoidance problem in mobile robots, Applied Soft Computing 107 (2021), 107372.

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

Abstract

Keywords

1 Introduction

2 Shuffled frog leaping algorithm

3.1 Establish environmental model

3.3 Construction of fitness function

3.4.1 Selection operation

3.4.3 Mutation operation

3.5 Location update strategy based on central frog

4.1 Parameter setting and analysis

Table 1 Path planning results under different crossover rates P c L min L max L avg L std 0.4 15.7615 15.8504 16.0050 0.0644 0.5 15.7556 15.8822 15.8256 0.0461 0.65 15.7652 16.2043 15.8613 0.0924 0.7 15.7591 16.7264 15.8850 0.2060 0.85 15.7570 15.9810 15.8333 0.0551

Footnotes

Acknowledgments

References

Table 1
Path planning results under different crossover rates

P _c L _min L _max L _avg L _std

0.4 15.7615 15.8504 16.0050 0.0644

0.5 15.7556 15.8822 15.8256 0.0461

0.65 15.7652 16.2043 15.8613 0.0924

0.7 15.7591 16.7264 15.8850 0.2060

0.85 15.7570 15.9810 15.8333 0.0551