# Cubic Spline Interpolation-Based Robot Path Planning Using a Chaotic Adaptive Particle Swarm Optimization Algorithm

Authors: Jianfang Lian; Wentao Yu; Kui Xiao; Weirong Liu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This paper proposed a cubic spline interpolation-based path planning method to maintain the smoothness of moving the robot’s path. Several path nodes were selected as control points for cubic spline interpolation. A full path was formed by interpolating on the path of the starting point, control points, and target point. In this paper, a novel chaotic adaptive particle swarm optimization (CAPSO) algorithm has been proposed to optimize the control points in cubic spline interpolation. In order to improve the global search ability of the algorithm, the position updating equation of the particle swarm optimization (PSO) is modified by the beetle foraging strategy. Then, the trigonometric function is adopted for the adaptive adjustment of the control parameters for CAPSO to weigh global and local search capabilities. At the beginning of the algorithm, particles can explore better regions in the global scope with a larger speed step to improve the searchability of the algorithm. At the later stage of the search, particles do fine search around the extremum points to accelerate the convergence speed of the algorithm. The chaotic map is also used to replace the random parameter of the PSO to improve the diversity of particle swarm and maintain the original random characteristics. Since all chaotic maps are different, the performance of six benchmark functions was tested to choose the most suitable one. The CAPSO algorithm was tested for different number of control points and various obstacles. The simulation results verified the effectiveness of the proposed algorithm compared with other algorithms. And experiments proved the feasibility of the proposed model in different dynamic environments.


---

## Body

## 1. Introduction

Human beings always have an urge to complete all the works and jobs automatically through automated machines, which inspires the researchers to focus on the design of mobile robots. Path planning is one of the most critical skills for mobile robots. It has been used in different applications such as robot rescue [1], robot service [2], and robot patrol [3]. The main goal of path planning is to find the shortest and smooth path between the starting and target points. However, it is hard to find the shortest and smooth collision-free path for robots because of the complex robot working environment.In general, the existing robot path planning methods can be classified into two categories: classical algorithms and heuristic optimization algorithm. The main classical algorithms include cell decomposition, artificial potential field, and sampling-based methods [4]. However, classic methods are very time consuming and require ample storage memory [5]. Thus, heuristic optimization algorithms [6, 7] are used frequently to optimize the path planning problem, such as differential evolutionary (DE) algorithm [8], genetic algorithm (GA) [9], A∗ algorithm [10], artificial bee colony (ABC) algorithm [11], annealing (SA) [12], particle swarm optimization (PSO) [13], and ant colony optimization (ACO) [14].GA is an optimization algorithm based on natural genetics, which includes natural selection, crossover, and variation [9]. Premature convergence may occur because genetic algorithms operate in grid maps and do not control population diversity. Therefore, in the robot path planning application, GA is integrated with other algorithms such as artificial potential field method, artificial bee population algorithm, etc., to achieve better results [15]. However, the main disadvantage of improved genetic algorithms in the robot path planning field is that it takes a long time.TheA∗ algorithm is an effective and direct method to search path in a static environment. However, when the A∗ algorithm was used to search in the neighborhood of the current node, the path beyond the threshold length is abandoned due to the local path length limitation, resulting in the final path being not optimal. Also, if there are not enough sample points to build the graph, the search success rate may be low. Nevertheless, increasing the number of sampling points increases costs. Hence, there are many improved A∗ algorithms to improve the optimal range of robot paths and search success rates [16]. These improved A∗ algorithms are very inefficient in dynamic environments. Because when the environment changes, such as new barriers, the A∗ algorithm and the improved A∗ algorithms must research from the current node to the end of the path. Hence, if the environment changes and the robot's current position is still quite a long distance from the final target, then the A∗ algorithm and the improved A∗ algorithms will take a lot of time to redraw its path.The ABC algorithm is based on a simulation of the foraging behavior of the bee colony [11]. ABC is easy to implement. ABC also has some drawbacks like early convergence, stagnation, and slow convergence. The ABC performs very well while exploring the feasible search space, but it shows poor performance for exploitation. Besides, ABC is first applied to solve the problems of function optimization, while the path planning of a mobile robot is a combinatorial optimization problem. Therefore, there are some difficulties in algorithm construction.SA is a stochastic global optimization algorithm simulated by Kirkpatrick. The convergence probability of SA algorithm is 1 [12]. This characteristic can guarantee the achievement of global optimization when it is used for robot global path planning while it has the disadvantages of slow convergence speed. The ACO is a random search optimization algorithm with characteristics of positive feedback and parallel computing, which applies to various problems such as traveling salesman problem [17], quadratic programming problem [18], and production scheduling problem [19]. However, the optimal path of ant colony algorithm planning is time-consuming.Traditional robot path planning attempts to find an optimal path, which may contain some sharp turns and polygonal lines. However, this algorithm is not flexible because it adds extra workload by moving the robot along the sharp turn by stopping, rotating, or restarting, even switching between different modes. Therefore, traditional robot path planning is time-consuming and labor-intensive for specific tasks requiring smooth motion.Spline interpolation curve is a smooth curve passing through a series of given points. Quadratic spline interpolation is a quadratic polynomial interpolation. When the coefficient of the highest degree term is 0, the quadratic spline interpolation curve is a straight line [20]. Therefore, the quadratic interpolation is not applicable. However, cubic spline interpolation has the convergence property of the first and second derivatives. When the highest term coefficient of cubic function is 0, the cubic spline interpolation curve is still a curve, and the interpolation effect should be better. In addition, compared with high-order interpolation, cubic spline interpolation has the advantages of simple calculation and good stability.Cubic spline interpolation has been widely applied. For example, cubic spline interpolation was used to control the quality of air temperature [21]. By interpolating the temperature observations for each altitude segment, suspicious values in the temperature observation data can be more effectively marked. Also, cubic spline interpolation was used to simulate the trajectory of the UAV [22] and study the path smoothness of the manipulator. In [23], the cubic spline interpolation was applied in the temperature compensation aspect of alcohol concentration measurement results.In this paper, the moving robot’s path can be drawn as a series of line segments that join the path nodes. The cubic spline function was used to interpolate on the path of the starting point, control points, and target point. Thus, a full path that was formed by connecting all interpolation points was obtained. The control points’ position determines the length of the path, the number of which determines the number of spline curves and the maximum turnings of the path. Therefore, these control points are used to optimize the path of mobile robots. Heuristic optimization algorithms are an alternative to optimize control points.Particle swarm optimization (PSO) is a computational technology. Like other evolutionary algorithms, PSO achieves the search for optimal spatial solutions through individual collaboration and competition. However, compared with evolutionary algorithms, PSO is simple and easy to implement. Moreover, PSO needs to adjust relatively few parameters, which is convenient and practical. PSO has been widely used in many applications. For example, the PSO algorithm is applied to deal with mathematical problems [24], which shows excellent performance in solving some classical function optimization problems and even some nonlinear functions. Also, the PSO algorithm is introduced into the fault diagnosis to propose a novel intelligent diagnosis method, which is applied to diagnose the faults of the motor bearing [25]. Then, PSO is also used to solve the problem of optimal deployment of wireless sensor network (WSN) nodes and to solve many problems caused by the optimized deployment of static nodes [26].However, in some cases, particle swarm optimization cannot find a global optimal solution due to particle depletion. Moreover, the search strategy of the particle swarm algorithm is mainly based on a random walk, so it cannot always successfully find the optimal solution. To date, some variants of PSO have been presented to improve the original version PSO. Most of the current existing PSOs can be roughly divided into three categories: parameter selection, hybrid versions, and topology structure, respectively [27].The proper selection of control parameters, such as inertia weight and acceleration coefficient, can significantly influence the convergence of PSO. In [28], Jiao et al. proposed a new inertia weight particle swarm optimization (IWPSO) algorithm, which uses Boltzmann search (BPSO) to adaptively adjust inertia weight C1 and C2 in the velocity update equation. The IWPSO algorithm can guide particles to find the most promising regions in the search space. In [29], Melin et al. proposed a parameter self-tuning based on fuzzy logic. They proposed a method of dynamically adjusting the iterative coefficients of the inertia weights C1 and C2 using fuzzy control, where the iterative coefficients are the learning factors. However, the design of such algorithms is very complicated, which increases the workload. Moreover, the optimization accuracy of these algorithms is not improved, and the global search ability of the algorithm is weak.Many studies improve the performance of particle swarm optimization algorithms by combining particle swarm optimization with other search techniques, such as differential evolution (DE) [30], artificial potential field (APF) [31], genetic algorithm (GA) [32], and neighborhood search [33]. In [34], Ding et al. combined a quantum-behavior PSO with the simplex algorithm to solve the load flow problem. However, these algorithms are inherently complex, so the combination of these algorithms with particle swarm optimization algorithms will be more complicated and time-consuming.Different types of topology structures have been studied in the literature to enhance the performance of PSO. In [35], Kong et al. presents a simplified particle swarm optimization (SPSO). SPSO is an improved particle swarm optimization algorithm that combines the particle updating formula into one and introduces the group of optimal terms. The algorithm performance has been improved to a certain extent. However, too many different terms in the algorithm affect the algorithm performance, and the searchability of the algorithm cannot keep up with the convergence speed after the updating formula is merged.In [36], Nagra et al. presented a dynamic multiswarm particle swarm optimizer (DMSPSO). Different from PSO, the swarms in DMSPSO are dynamic, and DMSPSO often regroups with different regrouping plans and exchanges information between subgroups. Multipopulation particle swarm optimization (MPSO) is introduced into a niche generation and evolution strategy [37]. Firstly, PSO containing N particles is divided into two niche subpopulations to generate independent search space. These niche subpopulations are not isolated in space, and all the particles evolve within their subpopulations, according to PSO. When evolution ends, the two subpopulations will chase different extremes. However, this kind of algorithm is complex and time-consuming.Chaos concept is an alternative strategy to solve the problem of particle depletion, which has many excellent extrinsic properties, such as periodicity, ergodicity, and pseudorandomness. These excellent properties are important to ensure that the generated solutions by the algorithm can be diverse enough to reach every mode in the multimodal objective search space potentially. Hence, chaos search can escape more easily from a local optimal solution than the standard stochastic search. Also, chaotic systems have been widely used in various applications, and it was already combined with some optimization algorithms [38]. This combination may generate solutions that are more flexible and diverse than standard optimization algorithms [39]. To date, there are some widely used chaotic maps, such as Singer map [40], Kent map [41], Logistic map [42], and Sine map [43].In this paper, a cubic spline interpolation-based path planning method has been proposed to maintain the smoothness of moving the robot’s path. Several path nodes were selected as control points for cubic spline interpolation. A full path was formed by interpolating on the path of the starting point, control points, and target point. The main contribution is to use chaotic adaptive particle swarm optimization (CAPSO) algorithm to present a novel algorithm that is used to optimize control points in cubic spline interpolation. The fitness function of CAPSO synthesizes two evaluation functions that consider path length after cubic spline interpolation and obstacle risk degree separately. The main improvement of the CAPSO algorithm is illustrated below.To strengthen the global searchability of the algorithm, we introduced the beetle foraging strategy to modify the particle position update formula of PSO. In [44], Jiang and Li proposed the beetle antennae search algorithm according to beetle foraging strategy. The beetle antennae search algorithm is extremely simple and efficient. Therefore, CAPSO improves the searching ability without affecting the convergence speed.Besides, the parameterω in PSO is used to balance the search capabilities of local and global search of particles in the swarm [45]. The parameter C1 symbolizes self-cognition, and C2 symbolizes social influence. It is advisable to take a higher value of C1 in the beginning than C2 and gradually reversing during the search. The three control parameters in the PSO algorithm are adaptively adjusted by using the trigonometric function. C1 and ω are both adjusted between linear decrement and nonlinear decrement while C2 is adjusted between linear increase and nonlinear increase; thus, at the beginning of the algorithm, particles can explore better regions in the global scope with a larger speed step to improve the searchability of the algorithm. At the later stage of the search, particles do excellent search around the extremum points to accelerate the convergence speed of the algorithm.Since the traversal of chaotic variables is not repeated within a specific range, chaotic maps are used instead of random parameters in the PSO algorithm. After chaotic processing, the diversity of particle group traversal is optimized, and the original random characteristics of the standard PSO algorithm are retained, which is able to effectively prevent the PSO from plunging into local optimal and make the particles proceed with searching in other regions of the solution space. As different chaotic maps may lead to different behaviors of the proposed algorithm, we tested the performance of six benchmark functions to choose the most suitable one. We also tested the influence of the number of control points on path planning. Experiments have been conducted to compare the proposed algorithms with PSO, SA, GA, DE, and some other improved PSO algorithms in different environments. Experiments also tested the feasibility of the proposed model in different dynamic environments.The rest of this paper is organized as follows. Section2 introduces the background. Section 3 introduces the problem formulation for robot path planning. Section 4 introduces the chaotic adaptive particle swarm optimization algorithm, and Section 5 introduces the application of CAPSO algorithm in path planning. Section 6 introduces experiments and result analysis. Finally, Section 7 summarizes the whole paper.


## 2. Background

### 2.1. Particle Swarm Optimization

PSO is inspired by the social behavior of some biological organisms, especially the group’s ability of some animal species to locate a desirable position in the given area. In the PSO algorithm, each particle has a memory that tracks the best position of the previous iteration: the particle’s optimal positionpbest and the particle’s global optimal position gbest, each with a velocity Vi and position Xi. The speed update method for the ith particle at t + 1 iteration is(1)vit+1=ωvit+c1r1tpbestt−xit+c2r2tgbestt−xit,where vit+1 is the new velocity of the particle at time t + 1, xit is the position of the current particle at time t, ω represents the weight, C1 and C2 are the learning factors, and r1 and r2 are random numbers of [0, 1], which increases the randomness of particle flight. The position update method for the ith particle at t + 1 iteration is(2)xit+1=xit+vit+1.In this paper, the particle coding is coordinates of several path nodes in the environment. The update of particle positions in two successive iterations is shown in Figure1.Figure 1
The update of particle positions in two successive iterations.


### 2.2. Cubic Spline Interpolation

The path of the mobile robot should be smooth to reduce the shaft wear of real robots’ wheels and energy consumption. We used cubic spline interpolation to achieve this goal. And cubic spline interpolation is to form a smooth curve through a series of shape points. Take (n + 1) nodes on the interval [a, b]:(3)a=x0<x1<⋯<xn=b.A functionf(x) on [a, b] becomes an interpolated cubic spline function if the following two conditions are met.In each intervalxi−1,xi, f(x) is a cubic polynomial function.(4)fix=ai+bix−xi+cix−xi2+dix−xi3,where fx is continuous in the interval [a, b].(5)fx0=y0,…,fxn+1=yn+1,(6)f−=f+xi=yi,i=1,2,…,n,where f′x is continuous in the interval [a, b].(7)f−′xi=f+′xi,i=1,2,…,n,where f″x is continuous in the interval [a, b].(8)f−″xi=f+″xi,i=1,2,…,n.In this paper, cubic spline interpolation is used to interpolate at the starting point, three path nodes, and the target point. Thus, a completely smooth path is formed by connecting all interpolation points.


## 2.1. Particle Swarm Optimization

PSO is inspired by the social behavior of some biological organisms, especially the group’s ability of some animal species to locate a desirable position in the given area. In the PSO algorithm, each particle has a memory that tracks the best position of the previous iteration: the particle’s optimal positionpbest and the particle’s global optimal position gbest, each with a velocity Vi and position Xi. The speed update method for the ith particle at t + 1 iteration is(1)vit+1=ωvit+c1r1tpbestt−xit+c2r2tgbestt−xit,where vit+1 is the new velocity of the particle at time t + 1, xit is the position of the current particle at time t, ω represents the weight, C1 and C2 are the learning factors, and r1 and r2 are random numbers of [0, 1], which increases the randomness of particle flight. The position update method for the ith particle at t + 1 iteration is(2)xit+1=xit+vit+1.In this paper, the particle coding is coordinates of several path nodes in the environment. The update of particle positions in two successive iterations is shown in Figure1.Figure 1
The update of particle positions in two successive iterations.


## 2.2. Cubic Spline Interpolation

The path of the mobile robot should be smooth to reduce the shaft wear of real robots’ wheels and energy consumption. We used cubic spline interpolation to achieve this goal. And cubic spline interpolation is to form a smooth curve through a series of shape points. Take (n + 1) nodes on the interval [a, b]:(3)a=x0<x1<⋯<xn=b.A functionf(x) on [a, b] becomes an interpolated cubic spline function if the following two conditions are met.In each intervalxi−1,xi, f(x) is a cubic polynomial function.(4)fix=ai+bix−xi+cix−xi2+dix−xi3,where fx is continuous in the interval [a, b].(5)fx0=y0,…,fxn+1=yn+1,(6)f−=f+xi=yi,i=1,2,…,n,where f′x is continuous in the interval [a, b].(7)f−′xi=f+′xi,i=1,2,…,n,where f″x is continuous in the interval [a, b].(8)f−″xi=f+″xi,i=1,2,…,n.In this paper, cubic spline interpolation is used to interpolate at the starting point, three path nodes, and the target point. Thus, a completely smooth path is formed by connecting all interpolation points.


## 3. Problem Formulation for Robot Path Planning

Given a robot and a two-dimensional workplace including obstacles and danger sources, path planning problem is typically stated as follows: to find an optimal collision-free path from starting and ending points according to some performance merits, such as the length, the time, the smoothness, and the energy. In this paper, we pay attention to the length and the risk degree (safety). To model the path planning problem, we model the workplace of robots first. The length can be expressed as a mathematical formula:(9)minPt=∑i=1dxi+1−xi2+yi+1−yi2,where xi,yi is a path node after interpolation, and there is a total of d path nodes after interpolation. In this paper, the interpolation points of each spline curve are 1000. The number of curves is (n + 1), where n is the number of control points. Thus, the number of path nodes d is (1000 ∗ (n + 1)). Pt is the sum of the lengths of adjacent path nodes after interpolation at time t, which represents the length of the path at time t.For the risk degree, we suppose the obstacle is a rigid body, denoted byOk. For the sake of simplicity, these obstacles are represented by circles, and the center is Ok, where k is the number of obstacles in the problem. Even with an irregular obstacle, we can seek its circumscribed circle. To obtain a collision-free path, the safety distance dsafe between the path and the obstacle should be greater than the threshold dmin, which represents the minimum distance between the path and the obstacle.(10)dsafe=xi−Oxk2+yi−Oyk2−γOk,where Oxk and Oyk represent the horizontal and vertical coordinates of the kth obstacle, respectively, and γOk represents the radius of the kth obstacle. The path is feasible only when dsafe < dmin; otherwise, it is not feasible. The risk degree can be expressed in a mathematical formula:(11)Pt=infeasible path,dsafe<dmin,feasible path,dsafe<dmin.The objective function of the algorithm is to achieve the above two objectives. The fitness function of CAPSO is in the following mathematical formula:(12)MinPts.t.Pt∈C2Pt∈Pfree,where C2represents a set of second-order differentiable functions and Pfree represents a set of collision-free paths satisfying the constraint of formula (11).


## 4. Chaotic Adaptive Particle Swarm Optimization Algorithm

Although the PSO algorithm proved efficient for solving different optimization problems, it still has drawbacks. In some cases, particle swarm optimization cannot find a global optimal solution due to particle depletion. Besides, at the beginning of the optimization process, particles can almost walk randomly in the entire search space, while particles can walk faster randomly in the search space, which may lead to the algorithm selecting the suboptimal solution. In other words, the search strategy of the particle swarm algorithm is mainly based on a random walk, so it cannot always successfully find the optimal solution. CAPSO makes the following improvements.


### 4.1. Modification Based on Chaotic Map

A chaotic system is similar to a random system, but it is different from the random phenomena that arise from the random term or coefficient of the system itself. For a real random system, the value from a given moment does not know the determining value of any subsequent moment, i.e., the system is unpredictable in the short term. For a chaotic system, due to its sensitivity to the dependence of the original value, its short-term behavior is completely certain, but its inherent randomness makes it impossible to predict the exact operation in the long run. Therefore, chaotic systems have better dynamics and statistical properties, which is crucial to ensure that chaotic variables can traverse all states within a specific range without repeating. In other words, the chaotic orbital passes every state point in the chaotic region in a finite time. These dynamic characteristics are essential to ensure that the solutions generated by the particle swarm algorithm are sufficiently diverse. In this paper, the one-dimensional chaotic map is used to replace the random parameterr1 and r2 in (1), allowing for the required mix between exploitation and exploration. Because different chaotic maps may lead to different behaviors of the proposed algorithm, this paper uses four well-known chaotic maps, namely, Kent, Sine, Singer, and Logistic, which constitute four different algorithms: CAPSO-Kent, CAPSO-Sine, CAPSO-Singer, and CAPSO-Logistic. By comparing the advantages and disadvantages of the four algorithms for path planning, a mapping is selected as the optimal alternative.


#### 4.1.1. Singer Map

The definition of this map is as follows:(13)xk+1=μ7.86xk−23.31xk2+28.75xk3−13.3xk4,where µ is a parameter of 0.9 to 1.08; in this paper, a is set to 1.01.


#### 4.1.2. Sine Map

The definition of this map is as follows:(14)xk+1=a4sinπxk,where 0 < a < 4; in this paper, a is set to 4.


#### 4.1.3. Kent Map

The definition of this map is as follows:(15)xk+1=xka,0<x<a,1−xk1−a,a<x<1,where 0 < a < 4.5; in this paper, a is set to 0.3.


#### 4.1.4. Logistic Map

The definition of this map is as follows:(16)xk+1=axk1−xk,where 3.1 < a < 3.99; in this paper, a is set to 3.99.The speed update method for theith particle at t + 1 iteration is(17)vit+1=ωvit+c1xk+1pbestt−xit+c2xk+1gbestt−xit.Figure2 shows the chaotic value histogram of the above four maps with random initial values over 4096 iterations. The ordinate in the figure shows the number of times the chaotic value appears in 4096 cycles. As can be seen from the figure, values 0 to 1 in the Kent map occur relatively evenly over the 4096 cycles, while in the Sine map and Logistic map, value 0 and value 1 appear more frequently over the 4096 cycles. In Singer map, values from 0.75 to 0.98 appear more frequently over the 4096 cycles. We use chaotic maps to update r1 and r2 random numbers to improve the diversity of the particle swarm. In other words, we want chaos values to be traversed rather than one value constantly appearing. Hence, we choose Kent map as the optimal alternative. Also, experiments verified to select Kent map is best suitable for the algorithm.Figure 2
(a) Kent chaotic value histogram. (b) Sine chaotic value histogram. (c) Logistic chaotic value histogram. (d) Singer chaotic value histogram.
(a)
(b)
(c)
(d)


### 4.2. Beetle Search Strategy-Based Location Update

In order to improve the searchability of the algorithm, we introduced the beetle search strategy into the position update formula of the particle swarm algorithm. The beetle’s antennae have two essential functions: one is to detect the surrounding environment. For example, when an obstacle is encountered, the antennae can sense its size, shape, and stiffness. The second is to capture the taste of food. When a higher concentration of odor is detected on one side of the antennae, the beetles will rotate in the same direction. Otherwise, they will turn to the other side. According to this simple principle, beetles can effectively find food.The main advantage of the beetle search strategy is that its design is simple and can solve optimization problems in a short time. The beetle search strategy is as follows:Step 1 generates a random vector and normalizes it:(18)dir=randsn,1,(19)dir=dirnormdir.Step 2 calculates the position of the left and right whiskers separately:(20)xlt=xt+d0∗dir2,xrt=xt−d0∗dir2,d0=stepc,where d0 is the search step size of the antennae and the ratio of the step size step to the search step size d0 is a fixed constant, that is, c is a constant. Step can be a fixed value and a variable value. This article sets it to a variable step size as a mathematical formula:(21)step=eta∗step,eta can be a constant or a variable. The eta variable in this article is a mathematical formula (19).(22)eta=step1∗step1step01/1+10∗k/kmax,kmax is the maximum number of iterations and k is current iteration times. Both step 0 and step 1 are constants. eta is the coefficient of step size change and less than 1. In formula (22), eta decreases with the increase of k. A large search step size means a large search area. Thus, at the beginning of the algorithm, the larger search step size can explore better areas in the global scope, and in the late stage of the search, the smaller step size can do a good search near the extremum point.Step 3 calculates the odor intensity of the left and right whiskers separately:(23)fleft=fxl,fright=fxr.Step 4 compares the odor intensity of the left and right whiskers and updates the position of the beetle:(24)xbt+1=xbt+step∗signxlt−xrt,flt≤frt,xbt−step∗signxlt−xrt,flt>frt,which is(25)xbt+1=xbt−step∗dir∗signflt−frt.In order to improve the global search ability of the algorithm, The position of the particle in CAPSO is updated as follows:(26)xit+1=xit+Mνit+1+1−Mxbt,where M is a constant; in this paper, M is set to 0.34.


### 4.3. Trigonometric Function Adaptation

PSO includes three parts: current motion influence, individual particle influence, and particle swarm influence. The first part is controlled by the weighting factorω. The second and third parts are controlled by the acceleration factors C1 and C2. A larger ω is useful for jumping out of the local optimal, while a smaller ω is suitable for the algorithm to converge. The optimal value of the particle swarm is crucial in the early stage of algorithm optimization, while the optimal value of particle individual is significant in the later stage. Therefore, in this paper, the inertia weight factor and the acceleration factor are adaptively adjusted by using the trigonometric function at each stage of the algorithm operation.(27)ωk=ωmax−ωmin2∗cosπ∗kkmax+ωmax+ωmin2,where kmax is the number of final iterations; k is the number of iterations of the algorithm; and ωk is the inertia weighting factor corresponding to the kth iteration. In this paper, kmax is set to 100, ωmax is set to 0.9, and ωmin is set to 0.4. The changes in the weighting factor in the algorithm operation are shown in Figure 3, where the maximum number of iterations is 500.(28)C1k=cosπ∗kkmax+a,(29)C2k=−cosπ∗kkmax+a,where a is set to 1.5. The changes in the three parameters in the algorithm operation are shown in Figure 1, where the maximum number of iterations is 500.Figure 3
(a) The variation diagram ofω in algorithm operation. (b) The variation diagram of C1 and C2 in algorithm operation.
(a)
(b)The parameterω in PSO is used to balance the search capabilities of local and global search of particles in the swarm. The parameter C1 symbolizes self-cognition, and C2 symbolizes social influence. It is advisable to take a higher value of C1 in the beginning than C2 and gradually reversing during the search. In other words, a higher value of C1, a higher value of ω, and a lesser value of C1 are advisable at the beginning of the algorithm, while a lesser value of C1, a lesser value of ω, and a higher value of C2 are advisable at the later stage of the search. The three control parameters in the PSO algorithm are adaptively adjusted by using the trigonometric function. C1 and ω are both adjusted between linear decrement and nonlinear decrement while C2 is adjusted between linear increase and nonlinear increase.As shown in Figure3, at the beginning of the algorithm, A > B, E > F > G > K > L. Also, C > D, M > N > O > P > Q at the later stage of the search. Thus, changing to the trigonometric functions make it better compared to the linear adaptation and constant. At the beginning of the algorithm, particles can explore better regions in the global scope with a more massive speed step to improve the searchability of the algorithm. At the later stage of the search, particles do excellent search around the extremum points to accelerate the convergence speed of the algorithm.


## 4.1. Modification Based on Chaotic Map

A chaotic system is similar to a random system, but it is different from the random phenomena that arise from the random term or coefficient of the system itself. For a real random system, the value from a given moment does not know the determining value of any subsequent moment, i.e., the system is unpredictable in the short term. For a chaotic system, due to its sensitivity to the dependence of the original value, its short-term behavior is completely certain, but its inherent randomness makes it impossible to predict the exact operation in the long run. Therefore, chaotic systems have better dynamics and statistical properties, which is crucial to ensure that chaotic variables can traverse all states within a specific range without repeating. In other words, the chaotic orbital passes every state point in the chaotic region in a finite time. These dynamic characteristics are essential to ensure that the solutions generated by the particle swarm algorithm are sufficiently diverse. In this paper, the one-dimensional chaotic map is used to replace the random parameterr1 and r2 in (1), allowing for the required mix between exploitation and exploration. Because different chaotic maps may lead to different behaviors of the proposed algorithm, this paper uses four well-known chaotic maps, namely, Kent, Sine, Singer, and Logistic, which constitute four different algorithms: CAPSO-Kent, CAPSO-Sine, CAPSO-Singer, and CAPSO-Logistic. By comparing the advantages and disadvantages of the four algorithms for path planning, a mapping is selected as the optimal alternative.


### 4.1.1. Singer Map

The definition of this map is as follows:(13)xk+1=μ7.86xk−23.31xk2+28.75xk3−13.3xk4,where µ is a parameter of 0.9 to 1.08; in this paper, a is set to 1.01.


### 4.1.2. Sine Map

The definition of this map is as follows:(14)xk+1=a4sinπxk,where 0 < a < 4; in this paper, a is set to 4.


### 4.1.3. Kent Map

The definition of this map is as follows:(15)xk+1=xka,0<x<a,1−xk1−a,a<x<1,where 0 < a < 4.5; in this paper, a is set to 0.3.


### 4.1.4. Logistic Map

The definition of this map is as follows:(16)xk+1=axk1−xk,where 3.1 < a < 3.99; in this paper, a is set to 3.99.The speed update method for theith particle at t + 1 iteration is(17)vit+1=ωvit+c1xk+1pbestt−xit+c2xk+1gbestt−xit.Figure2 shows the chaotic value histogram of the above four maps with random initial values over 4096 iterations. The ordinate in the figure shows the number of times the chaotic value appears in 4096 cycles. As can be seen from the figure, values 0 to 1 in the Kent map occur relatively evenly over the 4096 cycles, while in the Sine map and Logistic map, value 0 and value 1 appear more frequently over the 4096 cycles. In Singer map, values from 0.75 to 0.98 appear more frequently over the 4096 cycles. We use chaotic maps to update r1 and r2 random numbers to improve the diversity of the particle swarm. In other words, we want chaos values to be traversed rather than one value constantly appearing. Hence, we choose Kent map as the optimal alternative. Also, experiments verified to select Kent map is best suitable for the algorithm.Figure 2
(a) Kent chaotic value histogram. (b) Sine chaotic value histogram. (c) Logistic chaotic value histogram. (d) Singer chaotic value histogram.
(a)
(b)
(c)
(d)


## 4.1.1. Singer Map

The definition of this map is as follows:(13)xk+1=μ7.86xk−23.31xk2+28.75xk3−13.3xk4,where µ is a parameter of 0.9 to 1.08; in this paper, a is set to 1.01.


## 4.1.2. Sine Map

The definition of this map is as follows:(14)xk+1=a4sinπxk,where 0 < a < 4; in this paper, a is set to 4.


## 4.1.3. Kent Map

The definition of this map is as follows:(15)xk+1=xka,0<x<a,1−xk1−a,a<x<1,where 0 < a < 4.5; in this paper, a is set to 0.3.


## 4.1.4. Logistic Map

The definition of this map is as follows:(16)xk+1=axk1−xk,where 3.1 < a < 3.99; in this paper, a is set to 3.99.The speed update method for theith particle at t + 1 iteration is(17)vit+1=ωvit+c1xk+1pbestt−xit+c2xk+1gbestt−xit.Figure2 shows the chaotic value histogram of the above four maps with random initial values over 4096 iterations. The ordinate in the figure shows the number of times the chaotic value appears in 4096 cycles. As can be seen from the figure, values 0 to 1 in the Kent map occur relatively evenly over the 4096 cycles, while in the Sine map and Logistic map, value 0 and value 1 appear more frequently over the 4096 cycles. In Singer map, values from 0.75 to 0.98 appear more frequently over the 4096 cycles. We use chaotic maps to update r1 and r2 random numbers to improve the diversity of the particle swarm. In other words, we want chaos values to be traversed rather than one value constantly appearing. Hence, we choose Kent map as the optimal alternative. Also, experiments verified to select Kent map is best suitable for the algorithm.Figure 2
(a) Kent chaotic value histogram. (b) Sine chaotic value histogram. (c) Logistic chaotic value histogram. (d) Singer chaotic value histogram.
(a)
(b)
(c)
(d)


## 4.2. Beetle Search Strategy-Based Location Update

In order to improve the searchability of the algorithm, we introduced the beetle search strategy into the position update formula of the particle swarm algorithm. The beetle’s antennae have two essential functions: one is to detect the surrounding environment. For example, when an obstacle is encountered, the antennae can sense its size, shape, and stiffness. The second is to capture the taste of food. When a higher concentration of odor is detected on one side of the antennae, the beetles will rotate in the same direction. Otherwise, they will turn to the other side. According to this simple principle, beetles can effectively find food.The main advantage of the beetle search strategy is that its design is simple and can solve optimization problems in a short time. The beetle search strategy is as follows:Step 1 generates a random vector and normalizes it:(18)dir=randsn,1,(19)dir=dirnormdir.Step 2 calculates the position of the left and right whiskers separately:(20)xlt=xt+d0∗dir2,xrt=xt−d0∗dir2,d0=stepc,where d0 is the search step size of the antennae and the ratio of the step size step to the search step size d0 is a fixed constant, that is, c is a constant. Step can be a fixed value and a variable value. This article sets it to a variable step size as a mathematical formula:(21)step=eta∗step,eta can be a constant or a variable. The eta variable in this article is a mathematical formula (19).(22)eta=step1∗step1step01/1+10∗k/kmax,kmax is the maximum number of iterations and k is current iteration times. Both step 0 and step 1 are constants. eta is the coefficient of step size change and less than 1. In formula (22), eta decreases with the increase of k. A large search step size means a large search area. Thus, at the beginning of the algorithm, the larger search step size can explore better areas in the global scope, and in the late stage of the search, the smaller step size can do a good search near the extremum point.Step 3 calculates the odor intensity of the left and right whiskers separately:(23)fleft=fxl,fright=fxr.Step 4 compares the odor intensity of the left and right whiskers and updates the position of the beetle:(24)xbt+1=xbt+step∗signxlt−xrt,flt≤frt,xbt−step∗signxlt−xrt,flt>frt,which is(25)xbt+1=xbt−step∗dir∗signflt−frt.In order to improve the global search ability of the algorithm, The position of the particle in CAPSO is updated as follows:(26)xit+1=xit+Mνit+1+1−Mxbt,where M is a constant; in this paper, M is set to 0.34.


## 4.3. Trigonometric Function Adaptation

PSO includes three parts: current motion influence, individual particle influence, and particle swarm influence. The first part is controlled by the weighting factorω. The second and third parts are controlled by the acceleration factors C1 and C2. A larger ω is useful for jumping out of the local optimal, while a smaller ω is suitable for the algorithm to converge. The optimal value of the particle swarm is crucial in the early stage of algorithm optimization, while the optimal value of particle individual is significant in the later stage. Therefore, in this paper, the inertia weight factor and the acceleration factor are adaptively adjusted by using the trigonometric function at each stage of the algorithm operation.(27)ωk=ωmax−ωmin2∗cosπ∗kkmax+ωmax+ωmin2,where kmax is the number of final iterations; k is the number of iterations of the algorithm; and ωk is the inertia weighting factor corresponding to the kth iteration. In this paper, kmax is set to 100, ωmax is set to 0.9, and ωmin is set to 0.4. The changes in the weighting factor in the algorithm operation are shown in Figure 3, where the maximum number of iterations is 500.(28)C1k=cosπ∗kkmax+a,(29)C2k=−cosπ∗kkmax+a,where a is set to 1.5. The changes in the three parameters in the algorithm operation are shown in Figure 1, where the maximum number of iterations is 500.Figure 3
(a) The variation diagram ofω in algorithm operation. (b) The variation diagram of C1 and C2 in algorithm operation.
(a)
(b)The parameterω in PSO is used to balance the search capabilities of local and global search of particles in the swarm. The parameter C1 symbolizes self-cognition, and C2 symbolizes social influence. It is advisable to take a higher value of C1 in the beginning than C2 and gradually reversing during the search. In other words, a higher value of C1, a higher value of ω, and a lesser value of C1 are advisable at the beginning of the algorithm, while a lesser value of C1, a lesser value of ω, and a higher value of C2 are advisable at the later stage of the search. The three control parameters in the PSO algorithm are adaptively adjusted by using the trigonometric function. C1 and ω are both adjusted between linear decrement and nonlinear decrement while C2 is adjusted between linear increase and nonlinear increase.As shown in Figure3, at the beginning of the algorithm, A > B, E > F > G > K > L. Also, C > D, M > N > O > P > Q at the later stage of the search. Thus, changing to the trigonometric functions make it better compared to the linear adaptation and constant. At the beginning of the algorithm, particles can explore better regions in the global scope with a more massive speed step to improve the searchability of the algorithm. At the later stage of the search, particles do excellent search around the extremum points to accelerate the convergence speed of the algorithm.


## 5. The Application of CAPSO Algorithm in Path Planning

Through the introduction of the above sections, this section proposes the CAPSO algorithm and wants to compare the traditional PSO algorithm, and the CAPSO algorithm has a higher global searchability and search speed. Figure4 shows the flowchart of CAPSO in robot path planning.Figure 4
Flowchart of robot path planning based on CAPSO algorithm.The path planning process based on the CAPSO algorithm is as follows:Step 1: initialize the particle group, including the population sizeN and the velocity Xi position of each particle Vi.Step 2: calculate the fitness value of each particle fit[i].Step 3: for each particle, compare its fitness value fit[i] with the individual extremumpbest[i]. If fit[i] < pbest[i], replace pbest[i] with fit[i].Step 4: for each particle, compare its fitness value fit[i] with the global extremum gbest. If fit[i] < gbest[i], replace gbest[i] with fit[i].Step 5: iteratively update the position of the particle according to formula (26).Step 6: use the chaotic map to updater1.Step 7: iteratively update the velocity of the particle according to updated formula (17).Step 8: boundary condition processing.Step 9: update parameters according to formulae (27)–(29).Step 10: determine whether the algorithm termination condition is satisfied: if yes, end and output the optimization result; otherwise, return to Step 2.


## 6. Experiments

In this section, the performance of the proposed CAPSO algorithm is evaluated by experiments, and the optimal path planning method based on CAPSO is obtained. In the first section, the experimental environment and parameter settings are given. In the second section, the performances of CAPSO algorithms with different chaotic maps were tested. In the second section, the performance of the CAPSO algorithm for selecting chaotic optimal substitution and traditional heuristic algorithms was tested. In the third section, the performance of the CAPSO algorithm for selecting chaotic optimal replacement and improved PSO algorithms was tested.


### 6.1. Experimental Environment and Parameter Settings

The environment or workplace was two-dimensional. In order to get an unbiased comparison of CPU time, all experiments were performed on the same PC. In the environment 1, the domains ofx and y were between 0 and 15. Meanwhile, the positions of the start point and the endpoint were (1.5, 6.5) and (7.2, 1.2), respectively, so the straight-line distance between the start point and the endpoint is 7.7833. There are five circular obstacles scattered in the environment. They are located on [xobs; yobs], where xobs = 2.13.65.06.0 and yobs = 5.22.54.52.0. The radius of the obstacles is set to 0.70.71.00.7.In environment 2, the domains ofx and y were between −5 and 30. Meanwhile, the positions of the start point and the endpoint were (0, 0) and (20, 20), respectively, so the straight-line distance between the start point and the endpoint is 28.2843. There are nine rectangular obstacles scattered in the environment. Their outer circle is located on [xobs; yobs], where xobs = 344.571011.515.517 and yobs = 31795125916. The radius of the obstacles robs is set to 1.41423.53561.58111.41414.47211.11801.11802.2360.In environment 3, we set up 100 random collision-free obstacles. The domains ofx and y were between −200 and 1300. Meanwhile, the positions of the start point and the endpoint were (0, 0) and (1000, 1000), respectively, so the straight-line distance between the start point and the endpoint is 1414.21365.In environment 4, the domains ofx and y were between −4 and 24. Meanwhile, the positions of the start point and the endpoint were (0, 0) and (12, 13), respectively, so the straight-line distance between the start point and the endpoint is 17.6918. There are nine rectangular obstacles scattered in the environment. Their outer circle is located on [xobs; yobs], where xobs = 2257799.510.5 and yobs = 2862.7510.58110.5. The radius of the obstacles robs is set to 1.41423.53561.58111.41414.47211.11801.11802.2360.In environment 5, first, we set up 50 random collision-free obstacles and then randomly selected random obstacles to make them disappear. The domains ofx and y were between 50 and 1100. Meanwhile, the positions of the start point and the endpoint were (0, 0) and (1000, 1000), respectively, so the straight-line distance between the start point and the endpoint is 1414.21365.In environment 6, first, we set up four static obstacles and four dynamic obstacles which move in a straight line, respectively. The domains ofx and y were between 0 and 12. Meanwhile, the positions of the start point and the endpoint were (0, 0) and (12, 10), respectively, so the straight-line distance between the start point and the endpoint is 15.6205.In environment 7, we set up 30 random collision-free obstacles and then randomly selected random obstacles to make them disappear. Besides, the destination vertex is randomly transformed three times during the algorithm run.The parameters of the CAPSO algorithm are as follows: the number of particles is Pop, which is set to 30. The maximum velocity of the particles is VelMax, which is set to 5.12. The minimum velocity VelMin is set to −5.12. c is set to 20, and the step is set to 200; Step 0 and Step 1 are set to 0.29 and 0.24, respectively.


### 6.2. First Experiment: Comparison between Different CAPSO Algorithms

In this section, three groups of test functions with different characteristics are used to benchmark the performance of the proposed different CAPSO algorithms, which are unimodal functions [46, 47], multimodal functions [48, 49], and fixed-dimension multimodal functions [50, 51]. The specific form of the function is given in Table 1, where Dim represents the dimension of the function, Range represents the range of independent variables, that is, the range of population, and fmin represents the minimum value of the function.Table 1
Description of benchmark functions.
Characteristic
Function
Dim
Range
f
min
Unimodal functions
F
1
x
=
∑
i
=
1
n
x
i
2
30
[−30, 30]
0
F
2
x
=
∑
i
=
1
n
x
i
+
∏
i
=
1
n
x
i
30
[−30, 30]
0
F
3
x
i
=
∑
i
=
1
n
x
i
2
−
10
cos
2
π
x
i
+
10
30
[−5.12, 5.12]
0
Multimodal functions
F
4
x
=
−
20
exp
−
0.2
1
/
n
∑
i
=
j
n
x
i
2
−
exp
1
/
n
∑
i
=
1
n
cos
2
π
i
+
20
+
e
30
[−32, 32]
0
Fixed-dimension multimodal functions
F
5
x
=
4
x
1
2
−
2.1
x
1
4
+
1
/
3
x
1
6
+
x
1
x
2
−
4
x
2
2
+
4
x
1
4
2
[−5, 5]
0
F
6
x
=
−
∑
i
=
1
4
C
i
exp
−
∑
j
=
1
3
a
i
j
x
j
−
p
i
j
3
[−1, 3]Figure5 shows the two-dimensional versions of a unimodal function, multimodal function, and fixed-dimension multimodal function, respectively. The unimodal test function has only one global optimal solution, which is helpful to find the global optimal solution in the search space, and it can test the convergence speed and efficiency of the algorithm thoroughly, while the multimodal function and the fixed-dimension multimodal test function have multiple local optimal solutions, which can be used to test the algorithm to avoid the performance of the optimal local solution, and the fixed-dimension multimodal function compared with unimodal test function is more challenging. Convergence curves of CAPSO-Kent, CAPSO-Sine, CAPSO-Singer, and CAPSO-Logistic are compared in Figure 6 for all of the test functions. The figure shows that CAPSO-Kent has good processing ability for unimodal functions, multimodal functions, and fixed-dimension functions, and the processing process is very stable. Especially when solving more complex fixed-dimension functions, CAPSO-Kent shows a more obvious advantage than other algorithms. Therefore, we choose the Kent map to represent r1 and r2.Figure 5
(a) 2D version of unimodal function; (b) 2D version of multimodal function; (c) 2D version of fixed-dimension multimodal function.
(a)
(b)
(c)Figure 6
(a–f) Comparison of convergence curves of different CAPSO algorithms obtained in the benchmark function (F1–F6).
(a)
(b)
(c)
(d)
(e)
(f)


### 6.3. Second Experiment: Different Numbers of Control Points

This experiment aims to test the influence of the number of control points on the proposed algorithm CAPSO with Kent map. In this experiment, the number of control points ranged from one to ten control points. The population size was 30. Figure7 shows the results of experiment 2. Also, Figure 8 shows the convergence curve of the CAPSO algorithm when the number of control points ranged from one to nine and when the population size was 30.Figure 7
Path planning results of CAPSO under different numbers (n = 1∼9) of control points in environment 1.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)Figure 8
Convergence curves of CAPSO with different numbers of control points in environment 1.As shown, the best results were achieved when the number of control points was small, i.e.,n = 3 or 4, and the results dramatically decreased when the value of n was more than five, and the worst results were achieved when n = 8 and n = 9. The larger the number of control points, the larger the search space. Hence, the larger population is required to obtain good results. Also, when the number of control points is small, too few turns of the curve will limit the choice of paths such as n = 1 or n = 2. Therefore, three to six control points are relatively mature. When the number of obstacles increases sharply, the number of control points can be increased appropriately.


### 6.4. Third Experiment: CAPSO versus Traditional Heuristic Algorithms in Path Planning

This section tested the path planning of robots in environment 2 based on GA [9], SA [12], PSO [13], and CAPSO algorithms. For a fair comparison, the population size in all algorithms, the number of control points, and the maximum number of iterations are set to 30, 3, and 500, respectively. Each experiment ran 15000 objective function evaluations, equivalent to 500 iterations using 30 population sizes. For each algorithm, a total of 25 runs were performed for each experiment. Figure 9(a) shows the best paths in environment 2 generated by the CAPSO, PSO, GA, DE, and SA during 25 trials. The yellow square and green pentacle in Figure 9(a) are the start point and endpoint of the path, respectively. Also, Figure 9(b) shows the convergence curves of the best fitness values during 25 trials.Figure 9
(a) Comparison of path planning results in environment 2. (b) Convergence curves of different algorithms in environment 2.
(a)
(b)Based on the three factors of solution quality, stability, and convergence speed, the performances of these algorithms were compared. The solution quality can be expressed by the average optimal fitness value, which is defined as the average of 25 optimal fitness values produced by 25 trials. The smaller the average optimal fitness value is, the higher the solution quality is. The stability of the algorithm is determined by the standard deviation. The smaller the standard deviation is, the more stable the algorithm is. The convergence speed of the algorithm is determined by the number of iterations required for the algorithm to converge to the optimal or suboptimal solution. Given the maximum number of iterations, the fewer iterations the algorithm converge to the optimal solution, the faster the convergence speed.As we can see, although path planners based on five algorithms can successfully generate a collision-avoidance path, CAPSO found the near-optimal path and performs better. The path planners based on DE and SA have slow convergence speed. In contrast, the path planners based on PSO, CAPSO, and GA have fast convergence speed. Moreover, the solution quality of path planners based on DE and SA is inferior to that based on PSO, CAPSO, and GA.In 25 trials, the complete performance analysis for the best performance of different algorithms in path planning is presented in Table2. From the statistical data in Table 2, it can be seen that the CAPSO-based path planner has the smallest average fitness value, execution time, and standard deviation, which further proves the high searchability, simplicity, and robustness of CAPSO. In addition, the number of optimal iterations of CAPSO is the smallest, which further proves the rapid convergence of CAPSO. Compared with other algorithms, the CAPSO algorithm has the shortest execution time. From the six statistics listed in Tables 3 and 4, we proved the high searchability, simplicity, and robustness of CAPSO. Also, CAPSO is not time-consuming. All in all, the performance of CAPSO is better than the other five tested algorithms.Table 2
Path planning results in environment 2.
Algorithms
Best fitness value
Mean fitness value
Worst fitness value
Average execution time
Standard deviation
Number of optimal iterations
DE
32.8655
33.8655
35.0157
12.3581
1.1001
329
GA
31.4532
32.4532
33.6302
5.6875
1.0895
50
SA
32.2260
35.9860
34.1927
26.1047
0.9834
396
PSO
30.0592
32.0592
31.8083
5.0907
0.8744
50
CAPSO
29.7213
29.9821
31.1723
4.7042
0.7255
44Table 3
Path planning results in environment 3.
Algorithms
Best fitness value
Mean fitness value
Worst fitness value
Average execution time
Standard deviation
Number of optimal iterations
CAPSO
1414.43
1429.83
1416.24
15.1812
0.9064
46
DEPSO
1695.77
1731.87
1697.76
41.0869
0.9968
73
FAPSO
1726.20
1823.28
1728.99
19.0295
1.3953
35
SPSO
1722.87
1802.55
1725.90
16.9308
1.5131
45
IWPSO
1814.76
1888.91
1816.82
26.6719
1.0275
74
MPSO
1610.44
1710.44
1613.83
19.4110
1.7239
80Table 4
Path planning results in environment 4.
Algorithms
Best fitness value
Mean fitness value
Worst fitness value
Average execution time
Standard deviation
Number of optimal iterations
CAPSO
18.4155
19.7854
20.0875
7.1129
0.8360
46
DEPSO
19.0657
20.8703
20.8497
15.9505
0. 8920
39
FAPSO
20.5181
22.4203
22.5167
13.9275
0.9993
35
SPSO
20.5665
22.8267
22.7347
9.4258
1.0841
41
IWPSO
20.3603
21.5655
22.3353
9.1382
0.9875
42
MPSO
18.8765
20.5745
21.2343
7.72038
1.1789
21


### 6.5. Fourth Experiment: CAPSO versus Improved PSO Algorithms in Path Planning

The experiment was divided into two parts according to two types of environments (environment 3 and environment 4). This section tested the path planning of robots based on FAPSO [29], IWPSO [28], DEPSO [30], SPSO [35], MPSO [37], and CAPSO algorithms.(1)
Example 1.In this example, the population size in all algorithms, the number of control points, and the maximum number of iterations are set to 30, 7, and 100, respectively. Each experiment ran 3000 objective function evaluations, equivalent to 100 iterations using 30 population sizes. For each algorithm, a total of 25 runs were performed for each experiment. Figure 10(a) shows the best paths in environment 3 generated by the CAPSO (green line), DEPSO (black line), MPSO (red line), SPSO (rose red line), FAPSO (blue line), and IWPSO (yellow line) during 25 trials. The yellow square and green pentacle in Figure 10(a) are the start point and endpoint of the path, respectively. Also, Figure 10(b) shows the convergence curves of the best fitness values during 25 trials.(2)
Example 2. In this example, the population size in all algorithms, the number of control points, and the maximum number of iterations are set to 30, 4, and 200, respectively. Each experiment ran 6000 objective function evaluations, equivalent to 200 iterations using 30 population sizes. For each algorithm, a total of 25 runs were performed for each experiment. Figure 11(a) shows the best paths in environment 4 generated by the CAPSO (red-brown line), DEPSO (orange line), MPSO (purple line), SPSO (blue line), FAPSO (green line), and IWPSO (black line) during 25 trials. The yellow square and green pentacle in Figure 11(a) are the start point and endpoint of the path, respectively. And Figure 11(b) shows the convergence curves of best fitness values during 25 trials.Figure 10
(a) Comparison of path planning results in environment 3. (b) Convergence curves of different algorithms in environment 3.
(a)
(b)Figure 11
(a) Comparison of path planning results in environment 4. (b) Convergence curves of different algorithms in environment 4.
(a)
(b)As shown in Figures10 and 11, although path planners based on six algorithms can successfully generate a collision-avoidance path, CAPSO found the near-optimal path and performs better. Also, all paths are smooth and there are no large corners.In 25 trials, the mean fitness value and standard deviation in environment 3 and environment 4 are shown in Tables3 and 4. From the statistical data in Tables 3 and 4, we can see that the CAPSO-based path planner has the smallest average fitness value, execution time, and standard deviation, which further proves the high searchability, simplicity, and robustness of CAPSO. In addition, the number of optimal iterations of CAPSO is the smallest, which further proves the rapid convergence of CAPSO. Also, CAPSO is the algorithm with the shortest time compared with other algorithms. From the six statistics listed in Tables 3 and 4, we proved the high searchability, simplicity, and robustness of CAPSO. Also, CAPSO is not time-consuming. All in all, the performance of CAPSO is better than the other five tested algorithms.


### 6.6. Fifth Experiment: CAPSO Algorithms in Dynamic Path Planning under Environment 5

This section tested the feasibility of the proposed model in the dynamic environment 5. Figures12(a)–12(d) show the best paths in environment 5 generated by the CAPSO. Figure 13 shows the convergence curves of the best fitness values.Figure 12
(a–d) Dynamic Path planning results in environment 5.
(a)
(b)
(c)
(d)Figure 13
Convergence curves of CAPSO algorithms in environment 5.As we can see, the overall path is globally optimal; at the same time, the local path is smoother at each stage, the corner is small and gentle, and it conforms to the mobile control of the robot, and there is no obstacle unobstructed near the target point.


### 6.7. Sixth Experiment: CAPSO Algorithms in Dynamic Path Planning under Environment 6

This section tested the feasibility of the proposed model in dynamic environment 6, which contains four static obstacles and four dynamic obstacles. Static obstacles are represented by filling graphs, while dynamic obstacles are represented by hollow blue circles. Figures14(a)–14(f) show the best paths in environment 6 generated by CAPSO.Figure 14
(a–f) Dynamic path planning results in environment 6.
(a)
(b)
(c)
(d)
(e)
(f)As we can see, the overall path is globally optimal; at the same time, the local path is smoother at each stage, the corner is small and gentle, and it conforms to the mobile control of the robot, and there is no obstacle unobstructed near the target point.


### 6.8. Sixth Experiment: CAPSO Algorithms in Dynamic Path Planning under Environment 7

This section tested the feasibility of the proposed model in dynamic environment 7, which contains four dynamic obstacles and dynamic object vertex. Obstacles are represented by hollow blue and red circles. Figures15(a)–15(d) show the best paths in environment 7 generated by CAPSO.Figure 15
(a–d) Dynamic path planning results in environment 7.
(a)
(b)
(c)
(d)As we can see, the overall path is globally optimal; at the same time, the local path is smoother at each stage, the corner is small and gentle, and it conforms to the mobile control of the robot, and there is no obstacle unobstructed near the target point.


## 6.1. Experimental Environment and Parameter Settings

The environment or workplace was two-dimensional. In order to get an unbiased comparison of CPU time, all experiments were performed on the same PC. In the environment 1, the domains ofx and y were between 0 and 15. Meanwhile, the positions of the start point and the endpoint were (1.5, 6.5) and (7.2, 1.2), respectively, so the straight-line distance between the start point and the endpoint is 7.7833. There are five circular obstacles scattered in the environment. They are located on [xobs; yobs], where xobs = 2.13.65.06.0 and yobs = 5.22.54.52.0. The radius of the obstacles is set to 0.70.71.00.7.In environment 2, the domains ofx and y were between −5 and 30. Meanwhile, the positions of the start point and the endpoint were (0, 0) and (20, 20), respectively, so the straight-line distance between the start point and the endpoint is 28.2843. There are nine rectangular obstacles scattered in the environment. Their outer circle is located on [xobs; yobs], where xobs = 344.571011.515.517 and yobs = 31795125916. The radius of the obstacles robs is set to 1.41423.53561.58111.41414.47211.11801.11802.2360.In environment 3, we set up 100 random collision-free obstacles. The domains ofx and y were between −200 and 1300. Meanwhile, the positions of the start point and the endpoint were (0, 0) and (1000, 1000), respectively, so the straight-line distance between the start point and the endpoint is 1414.21365.In environment 4, the domains ofx and y were between −4 and 24. Meanwhile, the positions of the start point and the endpoint were (0, 0) and (12, 13), respectively, so the straight-line distance between the start point and the endpoint is 17.6918. There are nine rectangular obstacles scattered in the environment. Their outer circle is located on [xobs; yobs], where xobs = 2257799.510.5 and yobs = 2862.7510.58110.5. The radius of the obstacles robs is set to 1.41423.53561.58111.41414.47211.11801.11802.2360.In environment 5, first, we set up 50 random collision-free obstacles and then randomly selected random obstacles to make them disappear. The domains ofx and y were between 50 and 1100. Meanwhile, the positions of the start point and the endpoint were (0, 0) and (1000, 1000), respectively, so the straight-line distance between the start point and the endpoint is 1414.21365.In environment 6, first, we set up four static obstacles and four dynamic obstacles which move in a straight line, respectively. The domains ofx and y were between 0 and 12. Meanwhile, the positions of the start point and the endpoint were (0, 0) and (12, 10), respectively, so the straight-line distance between the start point and the endpoint is 15.6205.In environment 7, we set up 30 random collision-free obstacles and then randomly selected random obstacles to make them disappear. Besides, the destination vertex is randomly transformed three times during the algorithm run.The parameters of the CAPSO algorithm are as follows: the number of particles is Pop, which is set to 30. The maximum velocity of the particles is VelMax, which is set to 5.12. The minimum velocity VelMin is set to −5.12. c is set to 20, and the step is set to 200; Step 0 and Step 1 are set to 0.29 and 0.24, respectively.


## 6.2. First Experiment: Comparison between Different CAPSO Algorithms

In this section, three groups of test functions with different characteristics are used to benchmark the performance of the proposed different CAPSO algorithms, which are unimodal functions [46, 47], multimodal functions [48, 49], and fixed-dimension multimodal functions [50, 51]. The specific form of the function is given in Table 1, where Dim represents the dimension of the function, Range represents the range of independent variables, that is, the range of population, and fmin represents the minimum value of the function.Table 1
Description of benchmark functions.
Characteristic
Function
Dim
Range
f
min
Unimodal functions
F
1
x
=
∑
i
=
1
n
x
i
2
30
[−30, 30]
0
F
2
x
=
∑
i
=
1
n
x
i
+
∏
i
=
1
n
x
i
30
[−30, 30]
0
F
3
x
i
=
∑
i
=
1
n
x
i
2
−
10
cos
2
π
x
i
+
10
30
[−5.12, 5.12]
0
Multimodal functions
F
4
x
=
−
20
exp
−
0.2
1
/
n
∑
i
=
j
n
x
i
2
−
exp
1
/
n
∑
i
=
1
n
cos
2
π
i
+
20
+
e
30
[−32, 32]
0
Fixed-dimension multimodal functions
F
5
x
=
4
x
1
2
−
2.1
x
1
4
+
1
/
3
x
1
6
+
x
1
x
2
−
4
x
2
2
+
4
x
1
4
2
[−5, 5]
0
F
6
x
=
−
∑
i
=
1
4
C
i
exp
−
∑
j
=
1
3
a
i
j
x
j
−
p
i
j
3
[−1, 3]Figure5 shows the two-dimensional versions of a unimodal function, multimodal function, and fixed-dimension multimodal function, respectively. The unimodal test function has only one global optimal solution, which is helpful to find the global optimal solution in the search space, and it can test the convergence speed and efficiency of the algorithm thoroughly, while the multimodal function and the fixed-dimension multimodal test function have multiple local optimal solutions, which can be used to test the algorithm to avoid the performance of the optimal local solution, and the fixed-dimension multimodal function compared with unimodal test function is more challenging. Convergence curves of CAPSO-Kent, CAPSO-Sine, CAPSO-Singer, and CAPSO-Logistic are compared in Figure 6 for all of the test functions. The figure shows that CAPSO-Kent has good processing ability for unimodal functions, multimodal functions, and fixed-dimension functions, and the processing process is very stable. Especially when solving more complex fixed-dimension functions, CAPSO-Kent shows a more obvious advantage than other algorithms. Therefore, we choose the Kent map to represent r1 and r2.Figure 5
(a) 2D version of unimodal function; (b) 2D version of multimodal function; (c) 2D version of fixed-dimension multimodal function.
(a)
(b)
(c)Figure 6
(a–f) Comparison of convergence curves of different CAPSO algorithms obtained in the benchmark function (F1–F6).
(a)
(b)
(c)
(d)
(e)
(f)


## 6.3. Second Experiment: Different Numbers of Control Points

This experiment aims to test the influence of the number of control points on the proposed algorithm CAPSO with Kent map. In this experiment, the number of control points ranged from one to ten control points. The population size was 30. Figure7 shows the results of experiment 2. Also, Figure 8 shows the convergence curve of the CAPSO algorithm when the number of control points ranged from one to nine and when the population size was 30.Figure 7
Path planning results of CAPSO under different numbers (n = 1∼9) of control points in environment 1.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)Figure 8
Convergence curves of CAPSO with different numbers of control points in environment 1.As shown, the best results were achieved when the number of control points was small, i.e.,n = 3 or 4, and the results dramatically decreased when the value of n was more than five, and the worst results were achieved when n = 8 and n = 9. The larger the number of control points, the larger the search space. Hence, the larger population is required to obtain good results. Also, when the number of control points is small, too few turns of the curve will limit the choice of paths such as n = 1 or n = 2. Therefore, three to six control points are relatively mature. When the number of obstacles increases sharply, the number of control points can be increased appropriately.


## 6.4. Third Experiment: CAPSO versus Traditional Heuristic Algorithms in Path Planning

This section tested the path planning of robots in environment 2 based on GA [9], SA [12], PSO [13], and CAPSO algorithms. For a fair comparison, the population size in all algorithms, the number of control points, and the maximum number of iterations are set to 30, 3, and 500, respectively. Each experiment ran 15000 objective function evaluations, equivalent to 500 iterations using 30 population sizes. For each algorithm, a total of 25 runs were performed for each experiment. Figure 9(a) shows the best paths in environment 2 generated by the CAPSO, PSO, GA, DE, and SA during 25 trials. The yellow square and green pentacle in Figure 9(a) are the start point and endpoint of the path, respectively. Also, Figure 9(b) shows the convergence curves of the best fitness values during 25 trials.Figure 9
(a) Comparison of path planning results in environment 2. (b) Convergence curves of different algorithms in environment 2.
(a)
(b)Based on the three factors of solution quality, stability, and convergence speed, the performances of these algorithms were compared. The solution quality can be expressed by the average optimal fitness value, which is defined as the average of 25 optimal fitness values produced by 25 trials. The smaller the average optimal fitness value is, the higher the solution quality is. The stability of the algorithm is determined by the standard deviation. The smaller the standard deviation is, the more stable the algorithm is. The convergence speed of the algorithm is determined by the number of iterations required for the algorithm to converge to the optimal or suboptimal solution. Given the maximum number of iterations, the fewer iterations the algorithm converge to the optimal solution, the faster the convergence speed.As we can see, although path planners based on five algorithms can successfully generate a collision-avoidance path, CAPSO found the near-optimal path and performs better. The path planners based on DE and SA have slow convergence speed. In contrast, the path planners based on PSO, CAPSO, and GA have fast convergence speed. Moreover, the solution quality of path planners based on DE and SA is inferior to that based on PSO, CAPSO, and GA.In 25 trials, the complete performance analysis for the best performance of different algorithms in path planning is presented in Table2. From the statistical data in Table 2, it can be seen that the CAPSO-based path planner has the smallest average fitness value, execution time, and standard deviation, which further proves the high searchability, simplicity, and robustness of CAPSO. In addition, the number of optimal iterations of CAPSO is the smallest, which further proves the rapid convergence of CAPSO. Compared with other algorithms, the CAPSO algorithm has the shortest execution time. From the six statistics listed in Tables 3 and 4, we proved the high searchability, simplicity, and robustness of CAPSO. Also, CAPSO is not time-consuming. All in all, the performance of CAPSO is better than the other five tested algorithms.Table 2
Path planning results in environment 2.
Algorithms
Best fitness value
Mean fitness value
Worst fitness value
Average execution time
Standard deviation
Number of optimal iterations
DE
32.8655
33.8655
35.0157
12.3581
1.1001
329
GA
31.4532
32.4532
33.6302
5.6875
1.0895
50
SA
32.2260
35.9860
34.1927
26.1047
0.9834
396
PSO
30.0592
32.0592
31.8083
5.0907
0.8744
50
CAPSO
29.7213
29.9821
31.1723
4.7042
0.7255
44Table 3
Path planning results in environment 3.
Algorithms
Best fitness value
Mean fitness value
Worst fitness value
Average execution time
Standard deviation
Number of optimal iterations
CAPSO
1414.43
1429.83
1416.24
15.1812
0.9064
46
DEPSO
1695.77
1731.87
1697.76
41.0869
0.9968
73
FAPSO
1726.20
1823.28
1728.99
19.0295
1.3953
35
SPSO
1722.87
1802.55
1725.90
16.9308
1.5131
45
IWPSO
1814.76
1888.91
1816.82
26.6719
1.0275
74
MPSO
1610.44
1710.44
1613.83
19.4110
1.7239
80Table 4
Path planning results in environment 4.
Algorithms
Best fitness value
Mean fitness value
Worst fitness value
Average execution time
Standard deviation
Number of optimal iterations
CAPSO
18.4155
19.7854
20.0875
7.1129
0.8360
46
DEPSO
19.0657
20.8703
20.8497
15.9505
0. 8920
39
FAPSO
20.5181
22.4203
22.5167
13.9275
0.9993
35
SPSO
20.5665
22.8267
22.7347
9.4258
1.0841
41
IWPSO
20.3603
21.5655
22.3353
9.1382
0.9875
42
MPSO
18.8765
20.5745
21.2343
7.72038
1.1789
21


## 6.5. Fourth Experiment: CAPSO versus Improved PSO Algorithms in Path Planning

The experiment was divided into two parts according to two types of environments (environment 3 and environment 4). This section tested the path planning of robots based on FAPSO [29], IWPSO [28], DEPSO [30], SPSO [35], MPSO [37], and CAPSO algorithms.(1)
Example 1.In this example, the population size in all algorithms, the number of control points, and the maximum number of iterations are set to 30, 7, and 100, respectively. Each experiment ran 3000 objective function evaluations, equivalent to 100 iterations using 30 population sizes. For each algorithm, a total of 25 runs were performed for each experiment. Figure 10(a) shows the best paths in environment 3 generated by the CAPSO (green line), DEPSO (black line), MPSO (red line), SPSO (rose red line), FAPSO (blue line), and IWPSO (yellow line) during 25 trials. The yellow square and green pentacle in Figure 10(a) are the start point and endpoint of the path, respectively. Also, Figure 10(b) shows the convergence curves of the best fitness values during 25 trials.(2)
Example 2. In this example, the population size in all algorithms, the number of control points, and the maximum number of iterations are set to 30, 4, and 200, respectively. Each experiment ran 6000 objective function evaluations, equivalent to 200 iterations using 30 population sizes. For each algorithm, a total of 25 runs were performed for each experiment. Figure 11(a) shows the best paths in environment 4 generated by the CAPSO (red-brown line), DEPSO (orange line), MPSO (purple line), SPSO (blue line), FAPSO (green line), and IWPSO (black line) during 25 trials. The yellow square and green pentacle in Figure 11(a) are the start point and endpoint of the path, respectively. And Figure 11(b) shows the convergence curves of best fitness values during 25 trials.Figure 10
(a) Comparison of path planning results in environment 3. (b) Convergence curves of different algorithms in environment 3.
(a)
(b)Figure 11
(a) Comparison of path planning results in environment 4. (b) Convergence curves of different algorithms in environment 4.
(a)
(b)As shown in Figures10 and 11, although path planners based on six algorithms can successfully generate a collision-avoidance path, CAPSO found the near-optimal path and performs better. Also, all paths are smooth and there are no large corners.In 25 trials, the mean fitness value and standard deviation in environment 3 and environment 4 are shown in Tables3 and 4. From the statistical data in Tables 3 and 4, we can see that the CAPSO-based path planner has the smallest average fitness value, execution time, and standard deviation, which further proves the high searchability, simplicity, and robustness of CAPSO. In addition, the number of optimal iterations of CAPSO is the smallest, which further proves the rapid convergence of CAPSO. Also, CAPSO is the algorithm with the shortest time compared with other algorithms. From the six statistics listed in Tables 3 and 4, we proved the high searchability, simplicity, and robustness of CAPSO. Also, CAPSO is not time-consuming. All in all, the performance of CAPSO is better than the other five tested algorithms.


## 6.6. Fifth Experiment: CAPSO Algorithms in Dynamic Path Planning under Environment 5

This section tested the feasibility of the proposed model in the dynamic environment 5. Figures12(a)–12(d) show the best paths in environment 5 generated by the CAPSO. Figure 13 shows the convergence curves of the best fitness values.Figure 12
(a–d) Dynamic Path planning results in environment 5.
(a)
(b)
(c)
(d)Figure 13
Convergence curves of CAPSO algorithms in environment 5.As we can see, the overall path is globally optimal; at the same time, the local path is smoother at each stage, the corner is small and gentle, and it conforms to the mobile control of the robot, and there is no obstacle unobstructed near the target point.


## 6.7. Sixth Experiment: CAPSO Algorithms in Dynamic Path Planning under Environment 6

This section tested the feasibility of the proposed model in dynamic environment 6, which contains four static obstacles and four dynamic obstacles. Static obstacles are represented by filling graphs, while dynamic obstacles are represented by hollow blue circles. Figures14(a)–14(f) show the best paths in environment 6 generated by CAPSO.Figure 14
(a–f) Dynamic path planning results in environment 6.
(a)
(b)
(c)
(d)
(e)
(f)As we can see, the overall path is globally optimal; at the same time, the local path is smoother at each stage, the corner is small and gentle, and it conforms to the mobile control of the robot, and there is no obstacle unobstructed near the target point.


## 6.8. Sixth Experiment: CAPSO Algorithms in Dynamic Path Planning under Environment 7

This section tested the feasibility of the proposed model in dynamic environment 7, which contains four dynamic obstacles and dynamic object vertex. Obstacles are represented by hollow blue and red circles. Figures15(a)–15(d) show the best paths in environment 7 generated by CAPSO.Figure 15
(a–d) Dynamic path planning results in environment 7.
(a)
(b)
(c)
(d)As we can see, the overall path is globally optimal; at the same time, the local path is smoother at each stage, the corner is small and gentle, and it conforms to the mobile control of the robot, and there is no obstacle unobstructed near the target point.


## 7. Conclusions

This paper used the chaotic adaptive particle swarm optimization (CAPSO) algorithm to present a novel algorithm which is used to optimize Cubic spline interpolation to get the shortest, smooth, and collision-free path. The main improvement of this algorithm is illustrated below. The CAPSO is an improved PSO algorithm. It introduces the beetle foraging strategy to modify the particle position updating equation to strengthen the global search ability of the algorithm. Then, the three control parameters in the PSO algorithm are adaptively adjusted by using the trigonometric function to make CAPSO adaptively adapt control parameters between linearly decreasing and nonlinearly decreasing strategies so that control parameters of CAPSO reach the optimal level in the iterative process. Also, the chaotic map is used to replace the random parameter of the PSO to improve the diversity of particle swarm and maintain the original random characteristics. Experiments show that the Kent map is the most suitable. With CAPSO, the global search ability and search speed are improved, and optimal robot path planning under static environment is realized. Moreover, experiments verified the feasibility of the proposed model in different dynamic environments. The simulation results proved the effectiveness and robustness of the proposed algorithm.



---

*Source: 1849240-2020-02-20.xml*