Robot path planning based on tabu particle swarm optimization integrating cauchy mutation

Authors: lishu  qin
zhentao  fan
Venue: IEEE_org_ICIST_2024_Conference
Published: 2024-07-31 15:41:44

Abstract: In view of the shortcomings of the traditional Particle Swarm Optimization (PSO) in robot path planning, such as long path planning time, slow convergence speed, insufficient search ability in the middle and late stages, and easy to fall into local optimum. Inspired by the Tabu Search (TS) algorithm and Cauchy Mutation Perturbation, this paper proposes a Tabu Particle Swarm Optimization (PSOTS) based on Cauchy Mutation. Firstly, the beta distribution random number strategy is used to adaptively adjust the inertia weight to improve the search accuracy of the algorithm in the middle and late stages. Secondly, the Cauchy mutation perturbation is introduced in the particle swarm optimization (PSO) stage to update the position of particles, so as to reduce the possibility of particles falling into the local optimum.Finally, in the middle and late stages of the search, the roulette method was used to select some particles and adopt the Tabu Search (TS)
algorithm, so as to enhance the local search ability of the particles in the middle and late stages. Through the test of CEC benchmark function, compared with the traditional particle swarm optimization (PSO) algorithm, it is proved that it has excellent performance with fewer iterations and running time, and compared with the test results of specific obstacle environments, PSOTS can effectively generate the optimal path with high smoothness and shorter length, and improve the convergence speed and stability of PSO, which proves its 
superiority in solving robot path planning problems.

Main paper: 
 introduction: 
 The path planning of mobile robots is a very hot research topic at present, and it is widely used in the fields of deep-sea mining vehicle navigation [1] , robotic arm operation [2] , laser cutting [3] , unmanned aerial vehicles (UAVs) [4] , and unmanned vehicles [5] . Path planning refers to the robot's ability to find a collision-free optimal or suboptimal path from the current position to the target location under the constraints of mechanical conditions and complex environments [6] . Considering the type and number of robots, environmental complexity, static or dynamic obstacles, etc. It is a challenging task to plan a path with a short path and a high degree of smoothness without colliding with obstacles and other robots. To solve such problems, scholars have established environmental models to simulate the actual engineering environment, relied on path search algorithms to find feasible paths that meet the constraints, and obtained the optimal path through fitness function screening [7] .Path planning algorithms can be broadly divided into two categories, namely traditional methods and intelligent optimization algorithms. Traditional path planning algorithms include A-star algorithm [8] , Dijkstra algorithm [9] , D-star algorithm [10] , and Fast Search Random Tree Algorithm (RRT). [11] and Artificial Potential Fields (APF) [12] . Among them, Astar, Dijkstra, and D-star are path planning algorithms based on graph theory. For this type of approach, a suitable mesh model needs to be built. However, in the grid method, the mesh size is susceptible to environmental constraints. In addition, for complex environments, graph-theoretic algorithms are computationally expensive and inefficient [13] . The RRT algorithm can quickly generate barrier-free paths, but it cannot guarantee the optimal solution of paths, and the path smoothness is insufficient. The advantage of the APF algorithm is that the planning speed is fast, but when the attraction and repulsion are equal, it will fall into a situation where the target is unreachable, making it impossible for the robot to move towards the target position. Traditional methods are based on mathematical models and can be applied to any environment, but they tend to fall into local minima.The path planning problem of mobile robots is an NP-Hard problem. To solve this problem, many scholars have adopted heuristic algorithms combined with intelligent optimization, including gray wolf algorithm (GWO) [14] , ant colony algorithm(ACO) [15] ,particle swarm optimization (PSO) [16] , differential evolution algorithm (DE) [17] , reinforcement learning (RL) [18] , genetic algorithm (GA) [19] , etc. For most of the path planning literature, only single-objective optimization is carried out on the path length factor, and the path smoothness and safety factors are not considered, resulting in the problems of unsatisfactory planning path, insufficient energy, and long search time [20] .For the research of particle swarm optimization, many scholars have innovated in two aspects. On the one hand, it is an improvement of the particle swarm optimization itself, including the parameter adaptive strategy, the redefinition of the velocity function, the perturbation strategy, etc., the purpose of which is to make the particles jump out of the local optimum, improve the search ability and convergence speed. Focus on the early and middle stages of particle search for improvements; On the other hand, it is the combination of particle swarm optimization and other algorithms, which can be combined with genetic algorithm (GA), differential evolution (DE), reinforcement learning (RL), etc. using the advantages of other algorithms to make up for the lack of search ability of particle swarm algorithm.In order to solve the above problems, this paper proposes a Tabu Particle Swarm Optimization algorithm (PSOTS) Integrating Cauchy Mutation, which is applied to the twodimensional environment. The algorithm improves the adaptive strategy of inertia weight 𝜔, and adopts the Cauchy mutation strategy in the particle update stage to reduce the probability of particles falling into the local optimum. In order to improve the mid-to-late search ability of the algorithm, the Tabu Search (TS) algorithm was applied to the mid-to-late stage of particle search. In addition, the corresponding fitness functions are designed for the two factors of path length and angle change.The major contributions of this paper are summarized as follows:• An adaptive strategy is adopted for the inertia weights to improve the global search ability of particles.• The Cauchy Mutation is applied to the particle position update stage to reduce the probability of particles falling into the local optimum.• The Tabu Search Algorithm (TS) and Particle Swarm Optimization (PSO) were combined to improve the convergence speed and mid-to-late search ability of the traditional particle swarm algorithm.• The simulation tool is used to verify the effectiveness of the algorithm in different environments, and compared with the traditional particle swarm optimization to prove its superiority.The remaining sections of this paper are organized as follows. Section 2 describes the related work of particle swarm optimization. Section 3 is the global modeling of the obstacle environment and the formulation of the fitness function. Section 4 briefly introduces the traditional particle swarm optimization and tabu search algorithm. Section 5 presents the improved algorithm in detail. Section 6 is the simulation experiment part. Finally, section 7 deals with conclusion and future work.Li et al. [21] proposed a Fermat-based Grouped Particle Swarm Optimization (FP-GPSO) algorithm to simultaneously determine the aerial launch position and optimize the generated multi-segment path for the path planning problem of composite UAV paths. Zhao et al. [22] proposed an unmanned vehicle path planning method based on Adaptive Particle Swarm Optimization (APSO). Firstly, the map simplification strategy (MSS) is adopted to simplify the search space, and then the search of particles is coordinated by three adaptive factors and the Levy flight strategy, and the safety check strategy and dynamic obstacle avoidance strategy are proposed to ensure the safety of the global path. Tao et al. [23] proposed a twopopulation PSO algorithm (BPPSO) with a stochastic perturbation strategy, which divides particles into two subpopulations. The first population enhances the global search capability by taking into account the mass of the particles and the optimal solution of the randomly selected particles when updating the speed. The second population uses a linear cognitive coefficient adjustment strategy to enhance the local search. Xu et al. [24] proposed a nonlinear dissipative particle swarm algorithm. The algorithm dissipates particles in a nonlinear increment way, which avoids a large amount of unnecessary dissipation at the beginning of the iteration, and invests more effort in dissipation at the end of the iteration, which improves the operation efficiency and global search ability of the algorithm. Wang et al. [25] proposed an improved immune particle swarm algorithm. Among them, the adaptive information dynamic adjustment strategy is introduced to dynamically adjust the main link index, which improves the global searchability and convergence of particles, and is conducive to the robot to quickly identify the optimal path.Lin et al. [26] combined the cultural algorithm with the particle swarm optimization and introduced a probabilistic method based on improved metropolitan rules to update the inertia weights, which solved the path planning problem of multiple AGVs. Zhao et al. [27] proposed a new multi-objective Cauchy Mutant Cat Population Optimization (MOCMCSO) and Artificial Potential Field Method (APFM) to solve the multiobjective optimization problem of the shortest global path length and the smallest total rotation angle change. Wu et al. [28] proposed a new path planning algorithm combining ant colony optimization and particle swarm optimization. First, the simulated annealing algorithm is combined with the particle swarm for global search. The ant colony algorithm is used for local searches at a later stage. Mohammed et al. [29] combined Informed Rapid Exploration Random Tree (RRT*) and particle swarm optimization (PSO) algorithms. The informed RRT* algorithm can quickly construct the optimal path, which, combined with the particle swarm algorithm, increases the speed of algorithm convergence. Huang et al. [30] proposed an APSO algorithm combining A* and PSO to calculate the optimal path, and used the redundant point removal strategy to preliminarily optimize the path planned by the A* algorithm to obtain the key node set. After that, the improved PSO optimization key node set is used to obtain the global path.In this paper, the grid method is used to describe the working environment of a mobile robot. As shown in Figure 1 , the white grid represents the feasible node, the purple grid represents the obstacle node, the green grid represents the starting point, and the yellow grid represents the end point. The raster method can represent the complex working environment of the robot in a concise two-dimensional vector. Therefore, this paper creates a 20×20 mesh model with random obstacle nodes. All grids are arranged in left-to-right, bottom-to-top order, and each grid has a unique ordinal number. The starting node is the 0th grid, and the number 0 represents the starting point. The terminating node is the 399th raster, and the number 399 indicates the end point. In the path planning problem, to find the optimal path, it is necessary to meet the constraints such as path length, safe obstacle avoidance, and turning angle limitations. The fitness function combines these constraints to transform the path planning problem into an optimization problem. The fitness function is used as the basis for evaluating the quality of particles, which determines the speed and direction of particle update iteration. With reference to Ref. [31] , the fitness function is designed in the following form: 11 ()length smooth fx fitness f f  ==  +  ()where fitness is the fitness function, () fx is the objective function, length f is the fitness function of the path length, smooth f is the fitness function of the path smoothness, and  ,  are the weights of the two fitness functions. It should be noted that the fitness function is the reciprocal of the objective function, so the smaller the objective function, the higher the particle fitness. length f and smooth f are defined as follows:1 2 length smooth f length f smooth    =     =   (2)where length is the path length, smooth is the path smoothness, and ) ( )EQUATIONIts smoothness can be calculated using Eq. ( 4): i i i i i smooth        =       =  =       (5)The angles between adjacent segments are obtained by the inverse cosine function, as follows equation ( 6)-( 8):EQUATION( )EQUATIONIV. TRADITIONAL ALGORITHMSThe particle swarm optimization (PSO) was proposed by James Kennedy and Russell Eberhart [1] . In the PSO algorithm, the initial particle population is randomly generated, and the local and global best particles are selected based on the fitness function values of each particle. At each iteration, the PSO algorithm updates the particle position based on Equation ( 9) and (10) . After the position of each particle is updated, a fitness function is calculated based on the results obtained, the global optimal particle is determined, and the cycle continues until the termination condition is true.EQUATIONEQUATION)Where 1 c , 2 c are the acceleration coefficients;  is the inertia weight, which is adaptive in this paper, as shown in Equation ( 11); i indicates the current number of iterations; d represents dimensions; pbest represents the local optimal position; gbest represents the global optimal position.The Tabu Search Algorithm (TS) simulates the human mind, and its core idea is to prohibit the repetition of previous actions. Its main advantages include two points:1) The addition of the taboo table and the "amnesty criterion" makes the algorithm accept some inferior solutions in the search process, so as to jump out of the trap of local optimality.2) The new solution is not randomly generated from the neighborhood of the current solution, but is the best solution that is not taboo.For the adaptive adjustment of inertia weight 𝜔 , exponential function 𝑒 -𝑡 𝑡𝑚𝑎𝑥 and beta distribution random numbers are introduced. The improved inertia weight expression is as follows:( / ) min max min ( ) ( , ) t tmax e betarnd p q      - = + -  + Where t is the current number of iterations; max t is the maximum number of iterations; max  is the initial inertia weight, and the value is 0.9; min  is the inertia weight when the maximum number of iteration is reached, and the value is 0.4;  is the inertia adjustment factor, and the value is 0.1;( ) , betarnd p q is a beta distribution, where 2 p = , 5 q = .Where the inertia weight  decreases nonlinearly with the increase of the number of iterations. The addition of the random number of beta distribution makes the value distribution of inertia weight more reasonable, and improves the global search ability and later search accuracy in the early stage.The classical PSO algorithm does not fully take into account the information of other suboptimal solution particles when updating the population position, so the population diversity cannot be guaranteed. In this paper, the Cauchy mutation operator is introduced on the basis of the classical particle swarm algorithm. In the stage of updating the position of particles, the particles in the population undergo the mutation process under the influence of the Cauchy mutation operator. EQUATION)Where  is a random number of the standard normal distribution, and its probability density function is:EQUATIONThe variation value for the current dimension is set to standard deviation ( ) ( ) tan 0.5 rand, where rand is a random number between 0 and 1, which conforms to a uniform distribution.Cauchy mutation can produce a large random number space, make the particle distribution more uniform, expand the search range of particles, avoid falling into the local optimal solution, and improve the global convergence ability. This section describes the steps and flowchart for the improved algorithm. Figure 3 is a flowchart of the improved algorithm, and the steps of the improved algorithm are as follows:Step1: Initialize parameters of PSO algorithm and TS algorithm.Step2: Randomly generate initial population, set velocity and position of each particle.Step3: Update velocity and position of each particle according to equations ( 9) and (10) .Step4: All particles perform particle swarm algorithm.Step5: Determine whether pbest and gbest are updated. If not, go to the next step, otherwise go to step 3.Step6: Update the population by cauchy mutation.Step7: Roulette pick up particles to compose population 2 and the remainder is population 1.Step8: Population 1 performs particle swarm search.Step9: Population 2 performs tabu search.Step10: Compare results of particle swarm search and tabu search. Output better result. I shows the parameters of the improved algorithm.In order to verify the optimization effect of the improved algorithm, two test functions are used to test the algorithm.Where the function ( )1Fx is a multimodal function and the function ( )2Fx is a unimodal function. The name, formula, search space, and theoretical minimum of the test function are given in TABLE II . TABLE III shows the parameters of the comparison algorithms.Each function experiment was performed 50 times, and the results obtained were averaged. In terms of the effectiveness of the improved algorithm (PSOTS), compared with the ordinary particle swarm optimization (PSO), the test results are shown in TABLE IV, and the convergence curve of the test function is shown in Figure 4 . Analysis of TABLE IV shows that for test function 𝐹 1 (𝑥), the global optimal solution obtained by the improved method (PSOTS) is -12666.67, while the global optimal solution obtained by the traditional method (PSO) is -10986.07, and the improved algorithm (PSOTS) is closer to the theoretical optimal solution of the function, which proves that the improved method has higher solution accuracy and is easier to jump out of the local optimum. At the same time, compared with the fastest convergence algebra, the improved method (PSOTS) requires 62 generations to complete convergence, while the traditional method (PSO) needs 147 generations to complete convergence, indicating that the convergence speed of the improved method is faster.For test function 𝐹 2 (𝑥), the global optimal solution obtained by the two algorithms is the same, but the improved algorithm (PSOTS) is fully converged in the 172nd generation, and the traditional algorithm (PSO) is fully converged in the 208th generation, indicating that the convergence speed of the improved method is faster when the solution accuracy is the same.In summary, the improved method has higher solving accuracy, faster convergence speed, easier to get rid of local optimum, and better global convergenceIn order to verify the performance of the proposed algorithm, a comparative experiment is designed, and eight raster obstacle environments are created. According to the number of obstacles in the environment, the area of the total environment, and the complexity of the shape, the eight environments are divided into two categories: simple environment and complex environment, and each category contains four environments.The performance of Ordinary Particle Swarm Optimization (PSO) and Improved Particle Swarm Optimization (PSOTS) in the same obstacle environment is compared. The green line represents the path planned by the improved algorithm, and the blue line represents the path planned by the traditional particle swarm algorithm. Analyzing the data in TABLE V, it can be seen that on the average path length, Compared with the ordinary particle swarm algorithm, the improved algorithm is reduced by 0.8211 and reduce 2.8%, indicating that the path of the improved algorithm is shorter, and in terms of smoothness, the improved algorithm is reduced by 650 and reduce 12% compared with the ordinary particle swarm algorithm, indicating that the path of the improved algorithm is smoother, and in terms of particle fitness, the improved algorithm is 0.0012 higher than that of the ordinary particle swarm, indicating that the particle fitness of the improved algorithm is higher, and it is proved that the improved algorithm has a better effect of planning the path in a simple environment. TABLE VI obtains the average values of path length, smoothness, fitness values and objective functions of the two algorithms in the above four complex environments.Analyzing the data in TABLE VI, it can be seen that the average path length of the improved algorithm is 1.8787 and reduce 5.9% lower than that of the ordinary particle swarm algorithm, indicating that the path planned by the improved algorithm is shorter. In terms of smoothness, the improved algorithm is reduced by 487 and reduce 2.7% compared with the ordinary particle swarm algorithm, indicating that the path of the improved algorithm is smoother, and in terms of particle fitness, the improved algorithm is 0.0019 higher than that of the ordinary particle swarm algorithm, indicating that the particle fitness of the improved algorithm is higher, and it is proved that the improved algorithm has a good effect on path planning in complex environments.Compare the results of the path planned by the improved algorithm in the complex environments and simple environments. It can be found that with the increase of environmental complexity, the reduction rate of the path length planned by the improved algorithm is greater, and the particle fitness is also higher. The results show that the higher the complexity of the environment, the stronger the path planning ability of the improved algorithm.In this experiment, we create an obstacle environment which the Common Particle Swarm Optimization (PSO) and the Improved Particle Swarm Optimization (PSOTS) obtain the same path. The path is shown in Figure 7 . Figure 8 shows the iterative curve of the two algorithms under environment 9.Comparing the iteration curve Figure 8 , it can be seen that the ordinary particle swarm optimization (PSO) is fully converged in the 80th generation iteration, while the improved algorithm (PSOTS) is completely converged in the 68th generation iteration, which proves that the improved method is better than the particle swarm optimization in terms of convergence speed.At the 0th iteration, the objective function value of the ordinary particle swarm algorithm is 32.6661, and the fitness is 0.0306. The objective function value of the improved algorithm is 30.8687, and the fitness is 0.0324. The results show that the initialized particles obtained by the improved algorithm have better effects and higher fitness values.The longest horizontal segment of the iteration curves of the two algorithms is compared, that is, the fitness remains unchanged temporarily. The longest time of ordinary particle swarm is from the 10th generation iteration to the 44th generation iteration, which lasts for 34 generations, while the improved algorithm lasts only 30 generations from the 19th generation to the 49th generation, which proves that the improved algorithm is superior to the ordinary particle swarm in the ability to jump out of the local optimum.Comparing the iterative curves of the two algorithms from the 40th generation to the 60th generation, the objective function value of the ordinary particle swarm algorithm decreased from 27.1493 in the 40th generation to 26.5252 in the 60th generation, a decrease of 0.6241, while the improved algorithm decreased from 27.598 in the 40th generation to 26.6493 in the 60th generation, a decrease of 0.9487, which proves that the improved algorithm has stronger search ability in the middle and late stages. This experiment is designed to further demonstrate the superiority of the improved algorithm in convergence speed and solution speed on the basis of test function experiments.In this paper, we propose a tabu particle swarm optimization based on cauchy mutation to improve the search ability of particle swarm optimization. Firstly, the adaptive strategy is used to balance the global and local search capabilities for the inertia weights ω , and improve the search accuracy in the middle and late stages. In addition, the cauchy mutation is introduced in the stage of particle update position, which reduces the possibility of particles falling into local optimum. Finally, the tabu search algorithm was used in the middle and late stages of the search, which enhanced the local search ability in the middle and late stages. Through the CEC test function experiment and the same path experiment, it is proved that the improved algorithm is better than the ordinary particle swarm optimization in terms of convergence speed and calculation accuracy. In different obstacle experiments, the path length and smoothness of the improved algorithm are shorter, which proves the superiority of the improved algorithm PSOTS in the path planning problem.In more complex raster environments such as 30×30 and 40×40, etc. the adaptability of the improved algorithm is worth exploring. At the same time, the obstacle avoidance of dynamic obstacles is also one of the future issues. 
 
 Appendix:  



Reviews: review: title: title: This paper can be accepted.
main_review: main_review: Innovation: A Tabu particle swarm optimization algorithm (PSOTS) based on Cauchy variation is proposed. This algorithm improves the performance of PSO in robot path planning by adaptive adjustment of inertia weights, introduction of Cauchy variation perturbation and combination of tabu search algorithm, which has certain innovation.
Advantages:
1. The adaptive strategy is adopted to adjust the inertia weight ω to improve the global search ability of particles.
2. Apply Cauchy variation in the particle position update stage to reduce the probability of particles falling into local optimal.
3. Combine Tabu search algorithm (TS) and particle swarm optimization algorithm (PSO) to improve the convergence speed and late search ability of traditional particle swarm algorithm.
4. The effectiveness of the algorithm in different environments is verified by simulation experiments, and its superiority is proved by comparison with the traditional particle swarm optimization algorithm.
Cons:
1. Simple environment modeling: Although the grid method is simple and intuitive to describe the working environment of robots, the description of the complex environment may not be accurate enough, and the randomly generated obstacle nodes may not fully reflect the complexity of the actual environment, which affects the effectiveness verification of the algorithm in practical applications to a certain extent.
2. Single comparison algorithm: In the experiment, it is only compared with traditional particle swarm optimization algorithm, and lacks comparison with other advanced intelligent optimization algorithms, which is difficult to fully reflect the advanced nature of the improved algorithm in the field of path planning.
title: title: Accept after modification
main_review: main_review: This paper primarily propose a tabu particle swarm optimization based on cauchy mutation to improve the search ability of particle swarm optimization. Generally speaking, the overall narrative of the article is complete. However, I still have some questions as follows: 

1.The initial three paragraphs of the introduction focus extensively on path planning, a topic that does not constitute the primary keyword of this paper. The extensive discussion of traditional path planning algorithms may be disproportionate. It would be beneficial to enhance the discussion regarding the current state of research on Particle Swarm Optimization (PSO) to better emphasize the unique contributions of this paper. It is recommended to revise the introduction to more clearly delineate the paper's focal points.
2.The HIGHLIGHT section of the paper is suggested to be further improved and should be compared with the current state of existing research to highlight the contribution of the paper.
The HIGHLIGHT section of the manuscript could be further refined to more effectively showcase the paper's contributions. It would be advantageous to draw comparisons with the existing body of research to better illustrate the paper's significance and advancements. 
3.The RELATE WORK section, which is typically included in the introduction, appears to be misplaced. Additionally, the table in the SIMULATION EXPERIMENTS section is presented in an unappealing manner. A revision of the article's layout is recommended to enhance clarity and professionalism.
4.The purpose of Figures 5 and 6 seems to indicate differences in path planning between PSO and PSOTS. However, the demonstration of PSOTS's superiority over traditional PSO is not entirely clear. A more thorough analysis of the simulation experiments is recommended to better substantiate the advantages of PSOTS.
5.The conclusion should not merely restate the abstract but should provide a comprehensive summary of the paper's findings and implications. It is suggested that the conclusion be optimized to reflect the paper's contributions more effectively.
title: title: Minor revision
main_review: main_review: This paper proposes a Tabu Particle Swarm Optimization algorithm (PSOTS) Integrating Cauchy Mutation, which is applied to the two-dimensional environment.
1. The abstract is too long.
2. The novelties (4 items) in introduction should be concise.
Overall, the writing and language should be improved and polished.