Access the full text.
Sign up today, get an introductory month for just $19.
L. Du, Shan Ke, Zhen Wang, Jing Tao, Lianqing Yu, Hong Li (2019)
Research on multi-load AGV path planning of weaving workshop based on time priority.Mathematical biosciences and engineering : MBE, 16 4
Wang Yonggui, Qu Tongtong, Liqing Shuang (2019)
Disruption particle swarm optimization algorithm based on exponential decay weight
Zhao Zhi-gan (2014)
Simplified particle swarm optimization algorithm based on stochastic inertia weightApplication Research of Computers
Y. Shi and R. C. Eberhart
A modified particle swarm optimizer,Proceedings of IEEE Congress on Evolutionary Computation
Ameni Azzabi, K. Nouri (2019)
An advanced potential field method proposed for mobile robot path planningTransactions of the Institute of Measurement and Control, 41
(2018)
An adaptive constriction factor particle swarm optimization algorithm using fuzzy inference engine
Xiaoman Cao, Xiangjun Zou, Chunyang Jia, Mingyou Chen, Zeqin Zeng (2019)
RRT-based path planning for an intelligent litchi-picking manipulatorComput. Electron. Agric., 156
S. Quarrie, S. Quarrie, R. Radošević, D. Rančić, A. Kaminska, Jeremy Barnes, M. Leverington, C. Ceoloni, Dejan Dodig (2006)
Dissecting a wheat QTL for yield present in a range of environments: from the QTL to candidate genes.Journal of experimental botany, 57 11
Baoye Song, Zidong Wang, Lei Zou, Lin Xu, F. Alsaadi (2019)
A new approach to smooth global path planning of mobile robots with kinematic constraintsInternational Journal of Machine Learning and Cybernetics, 10
Yuhui Shi, R. Eberhart (2001)
Fuzzy adaptive particle swarm optimizationProceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No.01TH8546), 1
Peng Chen, Qing Li, Chao Zhang, Jiarui Cui, Hao Zhou (2019)
Hybrid chaos-based particle swarm optimization-ant colony optimization algorithm with asynchronous pheromone updating strategy for path planning of landfill inspection robotsInternational Journal of Advanced Robotic Systems, 16
Chengke Xiong, Danfeng Chen, Di Lu, Zheng Zeng, L. Lian (2019)
Path planning of multiple autonomous marine vehicles for adaptive sampling using Voronoi-based ant colony optimizationRobotics Auton. Syst., 115
Liang Yang, Juntong Qi, Dalei Song, Jizhong Xiao, Jianda Han, Xia Yong (2016)
Survey of Robot 3D Path Planning AlgorithmsJournal of Control Science and Engineering, 2016
M. Resende, C. Ribeiro, F. Glover, R. Martí (2010)
Scatter Search and Path-Relinking: Fundamentals, Advances, and Applications
(2016)
Study on path planning of soccer robot based on improved particle swarm algorithm
Jianwei Wu, Deer Bin, Xiaobing Feng, Zhongpu Wen, Yin Zhang (2018)
GA Based Adaptive Singularity-Robust Path Planning of Space Robot for On-Orbit DetectionComplex., 2018
(2020)
“Path planning method for indoor robot based on improved PSO,”
Johnathan Votion, Yongcan Cao (2019)
Diversity-Based Cooperative Multivehicle Path Planning for Risk Management in Costmap EnvironmentsIEEE Transactions on Industrial Electronics, 66
A. Khare, S. Rangnekar (2013)
A review of particle swarm optimization and its applications in Solar Photovoltaic systemAppl. Soft Comput., 13
(2012)
“An eﬀective diﬀerential evolution al-gorithm for collision avoidance of vehicles under IOT (Internet of things),”
A. Sedeño-Noda, Marcos Colebrook (2019)
A biobjective Dijkstra algorithmEur. J. Oper. Res., 276
Jianfei Yang, Lin Li (2017)
Improved Biogeography-Based Optimization Algorithm for Mobile Robot Path Planning
Yuandong Zhao, Zheng Fang (2013)
Particle swarm optimization algorithm with weight function's learning factor: Particle swarm optimization algorithm with weight function's learning factorJournal of Computer Applications, 33
ii) The function and its ﬁrst and second derivatives are continuous at the interpolation point
J. Q. Wang and X. D. Wang (2017)
Particle swarm optimization algorithm with improved inertia weight,Journal of Xi’an Polytechnic University, 31
Biwei Tang, Zhu Zhanxia, Jianjun Luo (2017)
A convergence-guaranteed particle swarm optimization method for mobile robot global path planningAssembly Automation, 37
Yuhui Shi, R. Eberhart (1998)
A modified particle swarm optimizer1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No.98TH8360)
P. Adamu, H. Okagbue, P. Oguntunde (2019)
Fast and Optimal Path Planning Algorithm (FAOPPA) for a Mobile RobotWireless Personal Communications, 106
Yiqing Huang, Zhikun Li, Yan Jiang, Lu Cheng (2019)
Cooperative Path Planning for Multiple Mobile Robots via HAFSA and an Expansion Logic StrategyApplied Sciences
Hindawi Journal of Control Science and Engineering Volume 2020, Article ID 3857894, 12 pages https://doi.org/10.1155/2020/3857894 Research Article An Improved Method of Particle Swarm Optimization for Path Planning of Mobile Robot 1,2 1 1 1 1 Xun Li, Dandan Wu , Jingjing He, Muhammad Bashir, and Ma Liping College of Electronics and Information, Xi’an Polytechnic University, Xi’an, China Bernoulli Institute, University of Groningen, Groningen, Netherlands Correspondence should be addressed to Dandan Wu; nakedbears@163.com Received 6 February 2020; Revised 16 April 2020; Accepted 8 May 2020; Published 25 May 2020 Academic Editor: Carlos-Andre´s Garc´ıa Copyright © 2020 Xun Li et al. .is is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. .e existing particle swarm optimization (PSO) algorithm has the disadvantages of application limitations and slow convergence speed when solving the problem of mobile robot path planning. .is paper proposes an improved PSO integration scheme based on improved details, which integrates uniform distribution, exponential attenuation inertia weight, cubic spline interpolation function, and learning factor of enhanced control. Compared with other standard functions, our improved PSO (IPSO) can achieve better optimal results with less number of iteration steps than the diﬀerent four path planning algorithms developed in the existing literature. IPSO makes the optimal path length with less than 20 iteration steps and reduces the path length and simulation time by 2.8% and 1.1 seconds, respectively. and local search imbalance, low convergence precision, easy 1. Introduction falling into optimal local solution, and poor robustness. Path planning is diﬀerent from motion planning where To obtain better optimization results, a PSO optimiza- dynamics must be considered. Its purpose is to ﬁnd the tion technique is proposed in [12] to converge at the global optimal path of motion in the least amount of time and to minimum, and a custom algorithm is used to generate the model the environment completely [1]. For the path plan- coordinates of the search space. .e coordinate values ning problem of mobile agents, several researchers have generated by the custom algorithm are passed to the PSO proposed many algorithms, which can be classiﬁed into two algorithm, which uses these coordinate values to determine categories, i.e., traditional path planning methods and bionic the shortest path between two given end positions. .us, it is intelligent algorithm-based methods. .e former method not limited to only ﬁnding the optimal value. Still, it can includes the A algorithm [2], Dijkstra [3], RTT [4], and improve the speed of the algorithm. However, the direct artiﬁcial potential ﬁeld method [5]. Bionic intelligent al- transfer of its two-point coordinates is easy to fall into the gorithms include diﬀerential evolution algorithm [6], ge- local optimum, and the obtained optimal value is often netic algorithm [7], ant colony algorithm [8], artiﬁcial ﬁsh considered as the global suboptimal value; the literature in swarm algorithm [9], and PSO [10]. PSO algorithm is widely [13] proposed a random disturbance method. used in the practical application and theoretical research of .e adaptive PSO optimization method introduces a mobile agent path planning due to its strong searchability, disturbing global update mechanism to the optimal global fast convergence speed, and high eﬃciency [11]. .e PSO is a position, which prevents the algorithm stalling. Besides, a population-based randomization technique to ﬁnd the op- new adaptive strategy is proposed to ﬁne-tune the three timal value for the foraging of the birds. PSO has the ad- control parameters in the algorithm. Moreover, the need for vantages of fast search speed, memory, few parameters, and dynamic adjustment and exploration of the three parameters simple structure and has easier implementation at the stage increases the computational complexity of the optimization of validation. Besides, its shortcomings include global search algorithm as well as low execution eﬃciency. .e work in 2 Journal of Control Science and Engineering [14] proposed a modiﬁed particle swarm optimization population for the best companion to learn. .at is, the next (MPSO) with constraints to jointly obtain a smooth path, step of the particle is determined by the experience and the but the method does not improve the eﬃciency of the best experience of the companion: particle diversity, which makes the particles stagnate and fall k+1 k k k k k V � ωV + c r P − X + c r P − X , (1) 1 1 2 2 id id id id qd id into the optimal local solution. .e studies in [15] proposed a fusion of chaotic PSO and ant colony algorithm (ACO). k+1 k k+1 (2) X � X + V , .e algorithm eﬀectively adjusts the particle swarm opti- id id id mization parameters. It reduces the number of iterations of where V is the dth component of the ﬂight velocity vector i d the ant colony algorithm, called the chaotic particle swarm of the particle i of the kth iteration; X indicates the dth i d algorithm, thereby eﬀectively reduces the search time. element of the position vector of the particle i of the kth However, due to the improved algorithm parameters, its iteration; c and c represent the learning factor, which is 1 2 speed and the position updates are proportional, and this used to adjust the learned to the maximum step size; r and can limit the particle global searchability. Moreover, it is a r are two random functions with a range of value from 0 to solution that can fall into the optimal local solution. 1 and are used to increase the randomness searching; and ω .e hybrid genetic particle swarm optimization algo- is the inertia weight to adjust the searchability for the so- rithm (GA-PSO) is proposed in [16] that established a path lution space. Although the classical PSO is simple to im- planning. .e mathematical model of the problem proposed plement and has few adjustment parameters when it is used a time-ﬁrst based particle-ﬁrst iteration mechanism, which in the path planning method, it is prone to poor search- makes the evolution process more directional and acceler- ability, falls into the optimal local solution, and has reduced ates the development of path planning problems. However, particle diversity, low convergence precision, and low ac- the hybrid algorithm has too many parameters that need curacy of path planning. .erefore, this paper systematically control. .is increases the computational complexity and improves the classical PSO algorithm by combining various has reduced the execution eﬃciency of the algorithm. It improved methods. signiﬁes that it is diﬃcult to improve the diversity of particles due to the easy way of falling into the optimal local solution. .erefore, to combine the advantages of the above- 2.2. Improvement of PSO Algorithm Integration mentioned various improved algorithms and improve their defects, this paper proposed a new method to improve the 2.2.1. Uniform Distribution. We aim to ensure that the PSO PSO integration scheme based on improved details, which is algorithm does not lose the randomness of the particles used to solve the global path planning of mobile robots in the when initializing the population and, at the same time, avoid indoor environment. In the proposed algorithm, the navi- the problem of excessive concentration of the initial posi- gation point model is selected as the working area model of tions of the particles, which is not conducive to global search the mobile robot, and the uniform distribution, exponential and postprocessing, especially with the possibility that the search stagnation may occur in the late search. In this paper, attenuation inertia weight, cubic spline interpolation function, and learning factor of enhanced control are in- continuous uniform random distribution is used to initialize troduced to PSO to improve its performance. Finally, the the particles so that the particles are relatively uniformly advancement and eﬀectiveness of the standard test function distributed in the search space to facilitate later search and and obstacle environment are veriﬁed in the paper. .e avoid particles falling into the local optimal solution. .e results show that, compared with other standard functions, formula for uniform position distribution is shown as IPSO achieves better optimal results and more iteration follows: steps. Compared with the other four path planning algo- x − x max min x � , (3) rithms, IPSO reaches the optimal path length with less than n − 1 20 iteration steps and reduces the path length and simulation y − y time by 2.8% and 1.1 seconds, respectively. max min y � , (4) n − 1 2. Improved PSO (IPSO) where x and y are the upper limits of the variables, max max x and y are the lower limits of the variables, and n is min min 2.1.ClassicalPSO. .e fundamental core of the PSO method the number of the decision variables. is to share the information through the individuals in the group so that the movement of the whole group can be transformed from disorder to order in the problem of so- 2.2.2. Exponential Decay Inertia Weight. .e change of the lution space to obtain the optimal solution of the problem. inertia weight w aﬀects the position of the particle. .e larger .e answer to each optimization problem is the “particle” the value of w, the stronger the global searchability and the speed and position update through (1) and (2). .e ﬁrst term weaker the local mining ability. .erefore, good results can of (1) indicates that the next move of the particle is aﬀected be obtained when the values of the w are dynamic (ad- by the magnitude and direction of the last ﬂight speed; the justable) compared to the ﬁxed values. .e value of w can second term means that the following action of the particle vary linearly during the PSO search process, or dynamically originates from its own experience; the third term indicates based on a measure function of PSO performance. By an- that the next move of the particle originates from the alyzing and summarizing the linear decreasing inertia Journal of Control Science and Engineering 3 weight proposed in [17], the improved particle swarm c � cos(ω), (7) optimization algorithm based on the improved inertia weight proposed in [18], and the enhanced method of c � sin(ω), (8) fuzzy inertia weight strategy proposed in [19], this paper presents an improvement in the above-mentioned 1 − ω> 0, methods. .e ﬁxed, predictable, and iterative step adopted (9) 2ω + 2> rand × c + rand ∗ c . in the previous ways is a global transformation that is not 1 1 2 2 conducive to the particle, such as ﬁxed transformation .e cosine function in (7) is a subtraction function in that can narrow the search range of the particle and aﬀect the interval (0, π/2), which has a signiﬁcant value at the the diversity of the particle. .is paper uses the study in beginning of the search, and the value is decreasing in the [20] to introduce the inertia weight of exponential decay latter part of the search. .e sine function in (8) is an which is more in line with the characteristics of the ex- increasing function in the interval (0, π/2) with a small ponential function. By adopting the changes of the pre- value before the quests, and its value increases after steps and poststeps to the search area, its speed can be searching. Not only does it satisfy the condition that the successfully updated at diﬀerent periods. .is eliminates PSO algorithm has better learning ability in the optimi- the premature particles and improves the robustness of zation process, but it also changes the inertia weight and the the algorithm. Henceforth, the global search and local learning factor into one variable, which is convenient for mining ability are maintained, and this can solve the practical application and strengthens the uniformity of the problems mentioned above to some extent. .e expres- algorithm optimization process. Equation (9) is the guiding sion is as follows: condition for selecting and adjusting the PSO parameters lnω − lnω max min given in [22]. (5) A � it − lnω , max MaxIt ω � exp(−A), (6) 2.2.4. Improvement Based on Robot Dynamics Requirements where ω is the minimum weight, ω is the maximum min max (1) Cubic Spline Interpolation. .e experimental results show weight, as well as the current number of iterations, MaxIt is that (see Section 4.2 for details) the path planning of the the maximum number of iterations, and it is the current improved PSO has more turning points with a rough path, number of iterations. which will aﬀect the dynamic characteristics of the robot when it is moved. .erefore, it is necessary to improve the aforementioned improved PSO algorithm further to have a 2.2.3. Improved Learning Factors. .e standard PSO smooth path with the improved robot dynamic adaptability expressed in (1) represents the acceleration weight of each of the algorithm requirements. .e cubic spline curve is particle moving to the optimal local value and the optimal ﬁtted by several interpolation intervals based on cubic global value. Lower values allow the particles to linger polynomials to provide a smooth curve, deﬁned as follows: outside the target area, while the higher values are causing On the range [a, b], n + 1 takes a node, and the node the particles to suddenly rush toward or cover the target coordinates are (x , y ), (x , y ), ..., (x , y ). If the follow- 1 1 2 2 n n area. Several methods have been eﬀectively improved by the ing conditions are met, it is called a cubic spline function. learning factor, although the learning factor and inertia weight weaken the uniformity of the optimization algorithm (i) Within each cell (x , x ), where i � 0, 1, . . ., n, there i i+1 is a cubic polynomial: to a certain extent. Hence, it is not conducive to the global and local search algorithms. 2 3 z � a + b x − x + c x − x + d x − x . (10) i i i i i i i i .e work in [21] analyzes the PSO with a compression factor that considered the learning factor as a function of (ii) .e function and its ﬁrst and second derivatives are inertia weight. .is kind of method has the advantage of continuous at the interpolation point. transforming the three variables involving inertia weight (iii) z (x) commonly uses endpoint conditions that can and learning factor into one variable, which not only facilitates practical application but also enhances the satisfy the following three requirements: uniformity of the algorithm optimization process. (a) Free boundary: the second derivative at the However, the function used is complicated, costly, and endpoint is zero. time-consuming. Besides, the possibility of particle (b) Fixed limitation: the range value of the diﬀer- stagnation in the later search is high, increasing the risk of ential function from the beginning to the end is particles falling into optimal local values. .erefore, speciﬁed. according to the characteristics of high self-learning (c) Nonnode boundary: the third derivative at the ability in the early search period and high demand for 2nd to the last node is continuous. “social learning ability,” this paper adopts the dynamic method to improve the learning factor; its expressions are (2) Particle Coding. Particle coding is the assignment of as shown in (7) and (8). It is shown that this expression is constrained by (9): coordinate positions to several path nodes. .e path node is 4 Journal of Control Science and Engineering the intersection of any two cubic spline intervals. Path nodes Step 4: calculate the ﬁtness value of the particle can be selected arbitrarily or according to the environment. according to (11). Suppose that the coordinates of n path nodes are Step 5: update the velocity and position of the particle (x , y ), (x , y ), ..., (x , y ). .e start and end coor- n1 n1 n2 n2 nn nn according to (1), (2), and (5) to (9), respectively. Update dinate of the trail are (x , y ), (x , y ). Interpolating the s s t t the local optimal value Pbest and the global optimal coordinates of the interpolation points with cubic spline value Gbest. interpolation is on the interval of Step 6: determine whether the updated particle in- (x , y ), (x , y ), . . . , (x , y ). .e path of the particle code 1 1 2 2 m m tersects the obstacle according to (13), and obtain a path planning is the connection of the interpolation points. .is composed of the path node coordinates after updating. paper uses the path node, the interpolation point, and the .e number of iterations is increased by one. link of the start and endpoints of the path as the running Step 7: if the termination condition is met (the trajectory of the robot. threshold error is good enough to be negligible.), then the algorithm ends, and the optimal path is output. (3) Evaluation Function. .is paper provides the shortest Otherwise, it goes to Step 3 and repeats the procedure. way that does not intersect with the obstacle. .e design .e ﬂowchart of the algorithm is shown in Figure 1. evaluation function of our proposed algorithm is as shown in (11), where L is the path length of the mobile agent from the ith path point to the i + 1th path point, 4. Simulation Experiment and Result Analysis which is often used as an index in the path planning, and To verify the eﬀectiveness and feasibility of the improved its mathematical expression is given in (12); x and y are i i algorithm, the improved algorithm of this paper (denoted as the coordinates of the ith path point; x and y are the i+1 i+1 IPSO), classical PSO algorithm (referred to as PSO), liter- coordinates of the i + 1th path point; α is the weight ature [23] stochastic inertia weight PSO algorithm (indicated coeﬃcient and is set to 100 here, which is used to exclude as Rand PSO), literature [24] trigonometric learning factor the illegal path, i.e., the way through the obstacle; and P is PSO algorithm (denoted as TFPSO), and research [25] PSO a penalty function of obstacle avoidance constraint in the with contraction factor algorithm (recorded as NCFPSO), selected indoor environment model, which is used to set the optimal values of the typical functions are compared and up a safe distance. .e calculation formula is as shown in analyzed through path planning experiment. .e simulation (13), where R is the radius of the mth obstacle, m is the experiment environment is carried out on Windows 10, core number of obstacles, and c and d are the center coor- i7, CPU (2.2 GHZ), memory 8 GB, Matlab (2018a). dinates of the obstacle; the smaller the value of P, the higher the safety coeﬃcient of the ﬁnal path. If the trail passes the mth obstacle, it is a number greater than 0. If 4.1.StandardTestFunctionOptimization. At present, several the obstacle is avoided, then the value is 0: researchers work on intelligent bionic algorithms to evaluate and compare the performance of algorithms by ﬁnding the F � L × (1 + α × P), (11) optimal values for the ﬁve typical functions. .e Ackley function is generally used to detect the global convergence rate of the �������������������� � algorithm, the Rastrigin function is used to ﬁnd the optimal 2 2 L � x − x + y − y , (12) i+1 i i+1 i global value of the algorithm, and the Griewank function detects i�1 the ability of the algorithm to jump out of the optimal local ����������������� value. .e Sphere and Rosenbrock functions are unimodal 2 2 x − c + y − d i i functions that are used to solve optimal global solutions. ⎜ ⎜ ⎟⎟ ⎛ ⎜ ⎛ ⎜ ⎞ ⎟⎞ ⎟ ⎝ ⎝ ⎠⎠ (13) P � MAX 1 − , 0 . In this paper, the above ﬁve functions are used as objects m�1 to compare and evaluate the eﬀectiveness of our proposed algorithm. .e basic mathematical of the basic functions properties are shown in Table 1. 3. Improved Algorithm Flow .is section provides the detailed step by step explanation of 4.1.1. Standard Test Function and Parameter Setting. .is how to improve the PSO algorithm, as stated in Section 2. section compares the performance of our proposed algo- rithm with some of the developed algorithms in the current Step 1: the number of path nodes, together with the literature. .e maximum number of iterations of each al- number of interpolation, is determined according to gorithm is set to MaxIt � 1000, the population size is set to the actual environment. Npop � 50, the dimension is set to D � 30, and the lower and Step 2: set the parameters of the particle uniformly and upper limit of the dynamic inertia weight are set as w � min initialize the particle position using (3) and (4), re- 0.4 and w � 0.7, respectively. .e ﬁve algorithms were max spectively. .en, the particle population and velocity run 20 times, and the optimal values, mean values, standard are initialized. deviations, and average simulation run times are computed Step 3: compute the coordinates of m interpolation based on the experimental results for each algorithm, re- points in x and y directions of each particle. spectively. .e performance of our proposed (IPSO) Journal of Control Science and Engineering 5 Start Determine the number of path nodes and interpolation Set and initialize the various parameters, and uniformly initialize the position of the particles according to equations (3) and (4) Number of iterations plus 1 Number of iterations plus 1 Calculate the coordinates of the interpolation point in the x and y directions Calculate the individual fitness value according to equation (11) Update the speed and position of Pbest and Gbest according to equations (1) and (2) and (5) ~ (9), respectively i ≥ NP? Met the end conditions Output optimal path End Figure 1: Flowchart of improved PSO algorithm. Table 1: Standard test function. Optimal Range of independent Function name Expression solution variables ����������� D D Ackley f(x) � −20 exp(−0.2 (1/D) x ) − exp((1/D) cos 2 πx ) + 20 + e 0 (−32, 32) i�1 i i�1 √� D 2 D Griewank f(x) � (1/4000) x − cos(x / i ) + 1 0 (−600, 600) i�1 i i�1 i Rastrigin f(x) � (x − 10 cos 2πx + 10) 0 (−5.12, 5.12) i�1 i D−1 2 2 2 Rosenbrock f(x) � 100(x − x ) + (1 − x ) 0 (−2.048, 2.048) i�1 i+1 i i Sphere f(x) � x 0 (−100, 100) i�1 i algorithm was evaluated using the experimental results of but it can be seen from the test curve in the subgraph of these four aspects and the iterative curve. Figure 2(a) that our proposed IPSO algorithm has the fastest convergence and highest precision among all the four algorithms developed in the literature. .e subgraph 4.1.2. Comparative Analysis of Algorithm Simulation Results, depicted in Figure 2(b) is the iterative curve of the Standard Function Test, and Result Analysis. .e results for Griewank function. Griewank function is a typical non- the ﬁve standard functions test curves are shown in linear multimode stating function with a large search Figure 2. .e test curve for the Ackley function is shown in space and has many local advantages. As can be seen from the subgraph of Figure 2(a). .e Ackley function is an n- the graph shown in Figure 2(b), our proposed IPSO al- dimensional function with several local optimal values. gorithm can obtain the optimal value better than the other .erefore, it is diﬃcult to ﬁnd the optimal global value, developed algorithms in the existing literature, and its 6 Journal of Control Science and Engineering Ackley iteration curve Griewank iterative curve 12 700 0 0 0 100 200 300 400 500 600 700 800 900 1000 0 100 200 300 400 500 600 700 800 900 1000 Number of iterations Number of iterations PSO NCFPSO PSO NCFPSO RandWPSO Improved RandWPSO IPSO TFPSO TFPSO (a) (b) Rastrigin iterative curve Rosenbrock iterative curve 300 9000 200 6000 100 3000 0 0 0 100 200 300 400 500 600 700 800 900 1000 0 100 200 300 400 500 600 700 800 900 1000 Number of iterations Number of iterations PSO NCFPSO PSO NCFPSO RandWPSO IPSO RandWPSO IPSO TFPSO TFPSO (c) (d) Sphere iterative curve 0 100 200 300 400 500 600 700 800 900 1000 Number of iterations PSO NCFPSO RandWPSO IPSO TFPSO (e) Figure 2: (a) Ackley iteration curve. (b) Griewank iteration curve. (c) Rastrigin iteration curve. (d) Rosenbrock iteration curve. (e) Sphere iteration curve. Fitness value Fitness value Fitness value Fitness value Fitness value Journal of Control Science and Engineering 7 convergence speed at the beginning, as the optimization convergence speed is fast. Its optimal value is received at the iteration step of less than 120. .is shows that our process continues, the IPSO algorithm in this paper per- forms better than the other four algorithms at the middle proposed algorithm has better local optimal value bounce ability. .e subgraph shown in Figure 2(c) represents the and later stages. iterative curve of the Rastrigin function. Rastrigin func- tion, which is similar to Griewank function, is a multipeak function. Its algorithm is easy to fall into the local 4.2. Path Planning maximum with an excellent solution. From the subgraph of Figure 2(c), our proposed IPSO algorithm approaches 4.2.1. Experimental Environment and Parameter Setting. .e IPSO algorithm of this paper uses the navigation point the optimal global value in a shorter iterative step when model of [26] to construct the experimental environment compared with the other four algorithms existing in the model and the obstacle expansion treatment. .e experi- literature. Our proposed algorithm converges at 110 it- mental environment is divided into a simple environment eration steps, which veriﬁes its ability to jump out from and a complex environment. .e number of simple envi- the optimal local value. ronmental obstacles is set to 5, the number of path nodes is 3, .e subgraph in Figure 2(d) is the iterative curve of the Rosenbrock function. .e global advantage of the Rose- and the number of interpolation points is set to 100. Sim- ilarly, the number of complex environmental obstacles is set nbrock function lies in a smooth and narrow parabolic valley. .e function optimization algorithm provides limited to 11, the number of path nodes is 5, and the number of interpolation points is set to 100. .e boundary is a nonnode information, and it is challenging to distinguish the search direction. .is implies that it is challenging to solve optimal boundary. Simulation parameter selection: the population size and global value. Nevertheless, it can be seen from the iteration the maximum number of iterations of the ﬁve algorithms are curve that our proposed IPSO algorithm can ﬁnd the op- consistent: Npop � 150, MaxIt � 100; w � 0.4, and timal global value in less than 60 iterations, which is the min fastest among the compared four existing algorithms in the w � 0.9. max literature. .is indicates that our proposed algorithm has better global searchability. .e subgraph shown in Figure 2(e) is the iteration curve of 4.2.2. Path Planning and Algorithm Performance Analysis the Sphere function. From Figure 2(e), our proposed algorithm (1) Simple Environment. In a simple environment, the has shown a certain advantage in terms of convergence speed starting point (■) is the map coordinate system of (0, 0), and and convergence precision that are not obvious. Still, the the endpoint (★) coordinates are (9, 9), as shown in optimal value obtained by our proposed algorithm is the Figure 3(a). smallest, because the Sphere function is a unimodal function It can be seen from Figure 3(a) that the path of the IPSO with a unique global minimum value, which does not make it algorithm is smoother and the dynamics of the robot motion diﬃcult to ﬁnd the optimal value. Hence, the degree of dis- is improved; the path of the classical PSO planning does not crimination of the algorithm is not obvious. Table 2 presents the performance comparison for the test ﬁnd the optimal solution at the beginning of optimization and encounters stagnation along its path. It should be easy result data obtained by the standard functions Ackley, Griewank, Rastrigin, Rosenbrock, Sphere, and our proposed for the algorithm to fall into the optimal local solution. .e ability to ﬁnd the optimal global solution is weak due to poor algorithm for the veriﬁcation. It can be seen from Table 2 particle diversity with small disturbance. .e TFPSO al- that, for the ﬁve functions, except for the Ackley function, gorithm starts to search for a short stagnation phenomenon. the best result is the same as the other four comparison Finally, the localized optimal solution is obtained by the algorithms. However, the other four functions are optimized disturbance of the algorithm, which signiﬁes that the al- by our proposed algorithm, and the results are improved by gorithm has a weak ability to jump out from the optimal at least 45%. After the optimization of the ﬁve functions by local solution. the proposed algorithm in this paper, the average value is Figure 3(b) shows that our proposed IPSO algorithm has increased by at least 0.1%, and the standard deviation is increased by at least 0.2%. .e experimental data shows that the fastest convergence rate and converges at 13 iteration steps; the RandWPSO algorithm converges at around 20 the IPSO algorithm is superior to the other four comparison algorithms in terms of optimal value, average value, and iterative steps; the TFPSO converges at the 48th iteration; the NCFPSO algorithm converges at the 14th iterative step; the standard deviation. However, the average running time is classical PSO converges at the 34th iteration. more than that of the classical PSO. .is is because the Table 3 provides the performance comparison based function of the parameters of our proposed algorithm is average path length and the average simulation run time for improved, while the classical PSO improved the parameters the ﬁve algorithms. As compared with the other four al- by constant values. Moreover, our proposed algorithm will gorithms, the longest path length of our proposed algorithm increase the function to some extent. .e limitation of the is reduced by at least 3.3%, the shortest path length is re- IPSO algorithm in this paper is being time-consuming. Our duced by at least 2.9%, the average path length is reduced by future studies would further consider the issue of achieving a reduced time. Although the IPSO algorithm of this paper at least 5.2%, and the average simulation time is reduced by 1.2 s. optimizes the Rastrigin and Sphere functions with the slower 8 Journal of Control Science and Engineering Table 2: Optimization results of ﬁve functions. Function Performance index PSO RandWPSO TFPSO NCFPSO IPSO Average value 0.34 0.15 0.35 0.17 0.10 Best result 0 0 0 0 0 Ackley Standard deviation 1.45 1.14 1.52 1.22 0.97 Running time (s) 0.31 0.46 0.43 0.51 0.31 Average value 130.56 19.33 45.80 98.19 8.00 Best result 36.73 12.71 23.62 15.93 1.10 Griewank 3 3 3 4 3 1.10 ×10 7.35 ×10 1.40 ×10 1.01 × 10 Standard deviation 9.95 ×10 Running time (s) 0.33 0.46 0.50 0.61 0.40 Average value 179.70 79.53 175.79 52.4226 47.54 Best result 113.62 61.48 118.97 47.55159 34.09 Rastrigin 3 2 3 3 2 Standard deviation 3.64 ×10 6.52 ×10 3.62 ×10 1.10 ×10 2.21 × 10 Running time (s) 0.25 0.34 0.37 0.26 0.24 3 2 3 2 −1 Average value 2.77 ×10 4.38 ×10 4.11 × 10 3.37 ×10 8.91 × 10 2 2 2 2 1 Best result 5.67 ×10 7.95 ×10 6.00 ×10 2.22 ×10 2.86 ×10 Rosenbrock 6 6 6 5 5 Standard deviation 4.51 × 10 2.52 ×10 9.64 ×10 4.73 ×10 2.38 ×10 Running time (s) 0.21 2.40 3.98 0.24 0.23 −1 −2 −2 −2 −3 Average value 2.70 ×10 2.10 ×10 1.20 ×10 2.65 ×10 5.8 ×10 −1 −9 −2 −2 −192 Best result 2.00 ×10 1.51 × 10 2.88 ×10 1.87 ×10 7.97 ×10 Sphere −1 −1 −2 −1 −2 Standard deviation 1.00 ×10 1.71 × 10 8.88 ×10 7.60 ×10 5.3 ×10 Running time (s) 0.88 3.36 5.33 0.95 1.09 Path planning of PSO in simple environment Simple environment iterative curve 9 32 0 2 4 6 8 10 0 10 20 30 40 50 60 70 80 90 100 x Number of iterations PSO IPSO PSO NCFPSO RandWPSO IPSO RandWPSO Start TFPSO Destination TFPSO NCFPSO (a) (b) Figure 3: Experimental comparison of ﬁve algorithms in a simple environment. (a) Simple environment path plan. (b) Simple environment iteration graph. Table 3: Comparison of path length of ﬁve algorithms in simple environment. Algorithm Longest path Shortest path Average path Average time (s) PSO 28.52 15.23 15.67 9.91 RandWPSO 22.89 13.51 13.90 14.10 TFPSO 27.06 13.29 14.36 15.16 NCFPSO 23.55 15.13 15.41 9.81 IPSO 22.14 12.91 13.18 8.71 Fitness value Journal of Control Science and Engineering 9 Path planning of PSO in complex environment Complex environment iterative curve 9 30 8 28 7 26 6 24 5 22 4 20 3 18 2 16 1 14 0 12 0 2 4 6 8 10 0 10 20 30 40 50 60 70 80 90 100 x Number of iterations PSO IPSO PSO NCFPSO RandWPSO Start RandWPSO IPSO TFPSO Destination TFPSO NCFPSO (a) (b) Figure 4: .e ﬁrst experimental comparison of ﬁve algorithms in the complex environment. (a) .e ﬁrst type of complex environment path planning diagram. (b) .e ﬁrst type of complex environment iteration graph. (2) Complex Environment. To verify the universality of the algorithms, the average path is reduced by at least 2.1%, and experiment, two types of experiments were carried out. .e the average simulation running time is reduced by 1.1 s. ﬁrst experiment is carried out from the starting point to the Furthermore, path planning has higher accuracy. endpoint, while the second experiment is conducted from .e second type of experiment: the starting point (■) is the the endpoint to the starting point. origin of the map with the coordinate system of (9, 9), and the .e ﬁrst type of experiment: the starting point (■) is the endpoint (★) coordinates are (0, 0), as shown in Figure 5(a). map coordinate system (0, 0), and the endpoint (★) coor- By considering Table 5, the performance of the path dinates are (9, 9), as shown in Figure 4(a). planning of our proposed algorithm in this paper is as follow: the average path length is reduced by at least 5.2%, It can be seen from Figure 4(a) that the path planning of our proposed algorithm is not only the shortest but the the shortest path length is reduced by at least 1.5%, the smoothest. .e path planning of a complex environment is longest path length is reduced by 7.2%, and the average relatively concentrated. .is is because there are many ob- simulation running time is reduced by 1.2 s. stacles in the complex environment with fewer paths to choose In summary, it is veriﬁed that our proposed IPSO al- from. .e classical PSO and TFPSO appear to be stagnant at gorithm has the shortest path, the highest precision, and the beginning of the algorithm, and the IPSO algorithm is more least processing time when compared with the four algo- prominent. An excellent solution is achieved after the algo- rithms existing in the literature. rithm is optimized for a while. .e optimal local solution is jumped out after its disturbance is settled. It shows that two 4.2.3. Summary of Path Planning. In the simple environ- algorithms (i.e., classical PSO and TFPSO) have small dis- ment, the path planning by the ﬁve algorithms is relatively turbances, few particle diversity, and weak ability to jump out scattered. .is is because there are fewer obstacles and ample from the local optimal solutions. Figure 4(b) presents the results obtained from the complex environment; from the space with many paths available for the algorithm to select. When comparing the ﬁrst type of experiment with the iterative curves shown in Figure 4(b), the IPSO algorithm has the fastest convergence rate and the highest convergence second type experimental path planning diagram in a complex environment, the ﬁve types of experiments in the precision with 22 iteration steps. .e NCFPSO algorithm has 27 iterative steps. .e RandWPSO algorithm has 28 iterations ﬁrst type of experiment are more concentrated when the robot starts running, and appear to be more dispersed in the before it starts to converge. TFPSO iterates 39 times before the left and right algorithms start converging; the PSO algorithm later stages. .is is because the ﬁrst type of experiment is near the starting point. In the presence of obstacles, the starts to converge at around 93 iterative steps. Table 4 compares algorithms avoid the obstacles according to their optimi- the path lengths of ﬁve algorithms in the ﬁrst type of complex zation ability. At the later stages of the optimization, the heterogeneous environment. obstacles at the endpoint are sparse, thereby making the path Table 4 shows that the shortest path of the IPSO algo- rithm is reduced by at least 3% compared with the other four more concentrated. Fitness value 10 Journal of Control Science and Engineering Table 4: .e ﬁrst comparison of path length of ﬁve algorithms in the complex environment. Algorithm Longest path Shortest path Average path Average time (s) PSO 31.21 13.73 15.84 10.89 RandWPSO 22.49 13.07 13.67 15.10 TFPSO 26.50 13.00 14.00 16.22 NCFPSO 26.40 13.07 13.92 10.83 IPSO 22.44 12.84 13.38 9.70 Path planning of PSO in complex environment Complex environment iterative curve 9 30 0 2 4 6 8 10 0 10 20 30 40 50 60 70 80 90 100 x Number of iterations PSO IPSO PSO NCFPSO RandWPSO Start RandWPSO IPSO TFPSO Destination TFPSO NCFPSO (a) (b) Figure 5: .e second experimental comparison of ﬁve algorithms in the complex environment. (a) .e second type of complex envi- ronment path planning diagram. (b) .e second type of complex environment iteration graph. Table 5: .e second comparison of path length of ﬁve algorithms in the complex environment. Algorithm Longest path Shortest path Average path Average time (s) PSO 25.66 13.59 15.30 11.14 RandWPSO 28.86 13.07 13.76 15.07 TFPSO 25.62 13.12 14.41 16.42 NCFPSO 23.41 13.04 13.67 11.07 IPSO 21.72 12.84 12.96 10.00 .e second type of experiment is the opposite of the ﬁrst algorithm. .e introduction of the local optimization and type. .e three-path planning experiment is carried out to exponential decay for inertia weight improves the search- verify the eﬀectiveness of our proposed IPSO algorithm ability of our proposed algorithm and increases the dis- among the algorithms existing in the literature. .e per- turbance of our algorithm, which subsequently improves the formance comparison for the algorithms is based on the diversity of the particles. longest path, the shortest path, the average path, and the average simulation running time. In all the comparisons 5. Conclusion carried out, our proposed IPSO algorithm has performed better than the other four algorithms in the literature. .is is In this paper, particle swarm optimization (PSO) and cubic because the algorithm proposed in this paper introduces a spline interpolation are combined to solve the minimum of uniform distribution initialization strategy. Furthermore, ﬁve test functions and robot path planning problems. In the inertia weight and the learning factor interact in the view of the problems of the classical particle swarm opti- optimization algorithm, which reduces the parameters of the mization algorithm, such as poor searchability, low con- proposed algorithm. Increasing the uniformity of the im- vergence accuracy, easy falling into local optimal solution, proved algorithm can better balance the global search of the poor robustness, and poor path smoothness, the classical Fitness value Journal of Control Science and Engineering 11 environments,” IEEE Transactions on Industrial Electronics, particle swarm optimization algorithm is improved from the vol. 66, no. 8, pp. 6117–6127, 2019. following aspects: (1) .e uniform initialization strategy is [3] A. Sedeño-noda and M. Colebrook, “A biobjective Dijkstra adopted for the population to improve the later searchability algorithm,” European Journal of Operational Research, of our IPSO algorithm. .is prevents the algorithm from vol. 276, no. 1, pp. 106–118, 2019. falling into the local optimal solutions, because the random [4] X. Cao, X. Zou, C. Jia, M. Chen, and Z. Zeng, “RRT-based path initialization of the particles is not evenly distributed, which planning for an intelligent litchi-picking manipulator,” is not conducive to the searchability at the later stages. (2) Computers and Electronics in Agriculture, vol. 156, pp. 105– .e introduction of the exponential decay for inertia weight 118, 2019. makes the particles grow up in the early stage of the search [5] A. Azzabi and K. Nouri, “An advanced potential ﬁeld method and is beneﬁcial to the global search. .e particle step size in proposed for mobile robot path planning,” Transactions of the the later stages of the search is small in the local develop- Institute of Measurement and Control, vol. 41, no. 11, ment, and the optimization accuracy is high. Experimental pp. 3132–3144, 2019. results show that the method increases the disturbance and [6] X. Li and S. R. Qu, “An eﬀective diﬀerential evolution al- diversity of particles to a certain extent. (3) .e use of sine gorithm for collision avoidance of vehicles under IOT (In- and cosine function can control the independent variable as ternet of things),” Journal of Northwestern Polytechnical the inertia weight. .e learning factor makes the three University, vol. 30, no. 5, pp. 729–733, 2012. [7] J. W. Wu, D. Bin, X. B. Feng et al., “GA based adaptive variables become one variable; this reduces the parameters of singularity-robust path planning of space robot for on-orbit the improved algorithm and thus reduces the complexity of detection,” Complexity, vol. 2018, Article ID 3702916, our algorithm. .e interaction of inertia weight and learning 11 pages, 2018. factor is increased, the unity of algorithm optimization is [8] C. Xiong, D. Chen, D. Lu, Z. Zeng, and L. Lian, “Path planning improved, and the performance of the algorithm is im- of multiple autonomous marine vehicles for adaptive sam- proved to a certain extent. (4) .e evaluation function is pling using Voronoi-based ant colony optimization,” Robotics constructed, and a smooth path is planned with cubic spline and Autonomous Systems, vol. 115, pp. 90–103, 2019. interpolation, which improves the accuracy and dynamic [9] Y. Q. Huang, Z. K. Li, Y. Jiang et al., “Cooperative path planning characteristics of the path. However, when compared with for multiple mobile robots via HAFSA and an expansion logic the classical PSO algorithm, the time advantage of the strategy,” Applied Sciences-Basel, vol. 9, no. 4, p. 10, 2019. proposed algorithm is weak, which will be a crucial issue to [10] Li Xun, D. Wu, Z. Zhao et al., “Path planning method for be further studied in future research. Nevertheless, this does indoor robot based on improved PSO,” Computer Measure- not aﬀect the competitiveness of the improved algorithm. ment &Control, vol. 28, no. 3, pp. 206–211, 2020. [11] T. T. Gao, L. Zhang, B. D. Li et al., “Study on path planning of Besides, in the follow-up study, virtual obstacles will be used soccer robot based on improved particle swarm algorithm,” for the simulation experiment of multirobot path planning, Journal of Xi’an Polytechnic University, vol. 30, no. 5, and it will be used in the real environment of an operating pp. 609–615, 2016. system with hardware platform as turnabout and software [12] P. I. Adamu, H. I. Okagbue, and P. E. Oguntunde, “Fast and platform as ROS (robot operation system), to improve the optimal path planning algorithm (FAOPPA) for a mobile practicability of the algorithm. robot,” Wireless Personal Communications, vol. 106, no. 2, pp. 577–592, 2019. Conflicts of Interest [13] B. Tang, Z. Zhanxia, and J. Luo, “A convergence-guaranteed particle swarm optimization method for mobile robot global .e authors declare that they do not have any conﬂicts of path planning,” Assembly Automation, vol. 37, no. 1, interest. pp. 114–129, 2017. [14] B. Song, Z. Wang, L. Zou, L. Xu, and F. E. Alsaadi, “A new approach to smooth global path planning of mobile robots Acknowledgments with kinematic constraints,” International Journal of Machine Learning and Cybernetics, vol. 10, no. 1, pp. 107–119, 2019. .is work was supported by the National Natural Science [15] P. Chen, Q. Li, C. Zhang et al., “Hybrid chaos-based particle Foundation of China (No. 51607133); Shaanxi Natural swarm optimization-ant colony optimization algorithm with Science Basic Research Project (No. 2019JM567); China asynchronous pheromone updating strategy for path plan- Textile Industry Federation Science and Technology Guid- ning of landﬁll inspection robots,” International Journal of ance Project (No. 2018094); and College Student Innovation Advanced Robotic Systems, vol. 16, no. 4, p. 11, 2019. and Entrepreneurship Training Program (No. [16] L.-Z. Du, Z. Wang, S. Ke et al., “Research on multi-load AGV 201910709019). path planning of weaving workshop based on time priority,” Mathematical Biosciences and Engineering, vol. 16, no. 4, pp. 2277–2292, 2019. References [17] Y. Shi and R. C. Eberhart, “A modiﬁed particle swarm op- timizer,” in Proceedings of IEEE Congress on Evolutionary [1] L. Yang, J. Qi, D. Song, J. Xiao, J. Han, and Y. Xia, “Survey of Computation, IEEE Service Center, Piscataway, NJ, USA, robot 3D path planning algorithms,” Journal of Control Sci- pp. 69–73, May 1998. ence and Engineering, vol. 2016, Article ID 7426913, 22 pages, 2016. [18] J. Q. Wang and X. D. Wang, “Particle swarm optimization algorithm with improved inertia weight,” Journal of Xi’an [2] J. Votion and Y. Cao, “Diversity-based cooperative multi- vehicle path planning for risk management in costmap Polytechnic University, vol. 31, no. 6, pp. 835–840, 2017. 12 Journal of Control Science and Engineering [19] Y. Shi and R. Eberhart, “Fuzzy adaptive particle swarm opti- mization,” in Proceedings of the IEEE Congress on Evolutionary Computation, IEEE, San Francisco, USA, pp. 101–106, May 2001. [20] Y. G. Wang, T. T. Qu, and S. Li, “Disruption particle swarm optimization algorithm based on exponential decay weight,” Application Research of Computers, vol. 37, no. 4, pp. 1020–1024, [21] Y. Zhao and Z. Fang, “Particle swarm optimization algorithm with weight function’s learning factor,” Journal of Computer Applications, vol. 33, no. 8, pp. 2265–2268, 2013. [22] M. G. C. Resende, C. C. Ribeiro, F. Glover et al., “Scatter search and path-relinking: fundamentals, advances, and ap- plications,” Handbook of Metaheuristics, vol. 146, pp. 87–107, Springer, Berlin, Germany, 2010. [23] Z. G. Zhao, S. Y. Huang, and W. Q. Wang, “Simpliﬁed particle swarm optimization algorithm based on stochastic inertia weight,” Application Research of Computers, vol. 31, no. 2, pp. 361–391, 2014. [24] A. Khare and S. Rangnekar, “A review of particle swarm optimization and its applications in Solar Photovoltaic sys- tem,” Applied Soft Computing, vol. 13, no. 5, pp. 2997–3006, [25] S. Zhao, J. H. Zhang, and Y. F. Zhu, “An adaptive constriction factor particle swarm optimization algorithm using fuzzy inference engine,” Journal of Qingdao University, vol. 33, no. 3, pp. 9–37, 2018. [26] J. Yang and L. Li, “Improved biogeography-based optimi- zation algorithm for mobile robot path planning,” in Pro- ceedings of 2017 Chinese Intelligent Systems Conference, Singapore, 2018.
Journal of Control Science and Engineering – Hindawi Publishing Corporation
Published: May 25, 2020
You can share this free article with as many people as you like with the url below! We hope you enjoy this feature!
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get an introductory month for just $19.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.