Comparison Study of the PSO and SBPSO on Universal Robot Trajectory Planning

Abstract

Industrial robots were modified over the years. The benefit of robots is making production systems more efficient. Most methods of controlling robots have some limitations, such as stopping the robots. The robot stops by various reasons, such as collisions. The goal of this study is to study the comparison of improving the Artificial Potential Field (APF) by the traditional Particle Swarm Optimization (PSO) algorithm and the Serendipity-Based PSO (SBPSO) algorithm to control the path of a universal robot UR5 with collision avoidance. Already, the metaheuristic algorithm kinds deal with a premature convergence. This paper presents a new approach, which depends on the concept of serendipity and premature convergence applied to the path of the universal manipulator UR5 and also compares it with traditional the PSO. The features of the SBPSO algorithm prototype are formalized in this paper using the concept of serendipity in two dimensions: intelligence and chance. The results showed that the SBPSO is more efficient and has better convergence behavior than the traditional PSO for controlling the trajectory planning of the UR5 manipulator with obstacle avoidance.

1. Introduction

Using robots in manipulation tasks had a significant growth in the context of industrial production in recent years [1]. The aforementioned diffusion of robots in an industrial environment provided, over the years, that various methods were developed in order to monitor and control manipulator and mobile robots [2]. With this, they acquired the ability to operate in dangerous environments for humans, for example, beyond Earth’s atmosphere, in aquatic explorations, and in the transport of materials [3]. The purpose of this paper is to present the simulation of article Swarm Optimization (PSO) and the Serendipity-Based PSO (SBPSO) algorithm to modify APF approach, in order to generate free trajectory of collision of a UR5 universal manipulator robot. These metaheuristics will be used to optimize the repulsion constants of the potential field of the starting point and obstacles and the attraction constant of the end point, which are directly related to the intensity of the force resulting from the potential field.

Particle Swarm Optimization (PSO) is a heuristic algorithm dependent on social behavior of a flock of birds. The method was recommended by Kennedy and Eberhart in 1995 [4]. They had an objective to seek the optimal solution, in a space of search, by exchanging information between individuals of a population to determine which trajectory they should take in the search space. In this paper, the PSO was used because it has a number of advantages including rapid convergence and ease of implementation, but often faces a problem where their particles get “stuck” in great places. This problem is called premature convergence [5]. In this algorithm, individuals called particles function as a set of birds searching for a flight shape and considering the position of each particle within space; this is due to a curve of evolution within society or set of particles. Each particle will have its success defined by the general trend of the population [5].

Many engineering problems are common to study types of its behavior process, as a rule, such as a dynamic system which can been modeled by a set of equations that consider the same variables and is subjected to a certain evolution over time. A set of techniques which has been applied to this kind of problem is succussed on what it involves and is known as bio-inspired computing techniques [6]. These techniques applied to the different domains such as: prediction systems [7,8], power systems [9,10], telecommunications [11,12], intrusion detection systems [13,14], and others. In the context of bio-inspired computing, Swarm Intelligence consists of a set of metaheuristics based on some living beings whose behavior emergencies can result in an ability to resolve.

It is important to mention that the work of the PSO and SBPSO algorithm is to enhance the artificial potential field approach in order to obstacle avoidance collision.

In order to enhance work of the PSO by delaying premature convergence, the serendipity concept will be used. Serendipity is a term used to describe a fortunate situation that happens by chance. Recommendation systems are developed as a solution to the problem of information overload. The accuracy of the recommendations has been the focus of recommendation system research [15,16]. Accuracy, on the other hand, resulted in a problem known as overspecialization. This happens when the system only refers to items connected to the user’s profile. Serendipity is a strategy that can be used to resolve overspecialization. According to [17], a recommendation system provides products based on the user’s interest profile and converges on recommendations when these items do not meet the real expectations of the user. A metaheuristic algorithm converges to a place without considering other more suitable solutions in order to suggest items that may be more suitable. It is possible to observe the correlation between overspecialization and premature convergence. Some approaches in the literature use scout particles with the objective to improve the standard PSO algorithm’s performance [18,19]. These approaches are stochastic, but is a benefit when combined with serendipity techniques. This work proposes Serendipity-Based Particle Swarm Optimization (SBPSO) using a combination of the particles Girl Scouts with serendipity to improve the exploration of the algorithm in robotic searches.

Serendipity, according to the Cambridge Dictionary, “is the act of obtaining important or interesting things by chance.” Unlike other traditional definitions, which exclusively treat serendipity as a synonym for “chance,” serendipity is a mix of chances [20]. In [21], a formal approach was used for multiple categories to present the concept of serendipity. In order to present four occurrences that cause serendipity, logical equations called Serendipity Equations were used. These occurrences are linked to four various kinds of serendipity: (a) pure serendipity; (b) fake serendipity; (c) serendipity with wrong knowledge; and (d) serendipity without an inspiration metaphor.

The contribution of this paper is to obtain the collision-free trajectories by using the PSO and the SBPSO algorithms, also comparing the effect of the PSO algorithm and SBPSO algorithm to modify APF approach on the trajectory of a universal robot UR5.

2. Materials and Methods

2.1. Artificial Potential Field

The elements and resultant of potential energy, contained from an attractive potential field and repulsive potential field. Equations (1) and (2) represent the attractive potential field and attraction force, respectively, by setting the position of end effecter x =${\left(x,y\right)}^T$ and the point of goal coordinate $x_G=\left(x_g,y_g\right)$. The UR5 robot has been attracted to the goal object before reaching it. The goal object has the bigger attraction force.

$${\mathrm{U}}_{\mathrm{att}}\left(\mathrm{x}\right)=\frac{1}{2}{\mathrm{K}}_{\mathrm{att}}.{\mathrm{d}}^2\left(\mathrm{x},{\mathrm{x}}_{\mathrm{g}}\right)$$

(1)

$K_{att}$: Attraction potential field constant.

$\mathrm{d}\left(\mathrm{x},{\mathrm{x}}_{\mathrm{g}}\right)=\Vert {\mathrm{x}}_{\mathrm{g}}-\mathrm{x}\Vert$: Distant between the first coordinate of manipulator and last coordinate of it (i.e., pick and place operation of the end-effector).

The attraction force of the UR5 robot is the negative gradient of attraction potential field

$${\mathrm{F}}_{\mathrm{att}}\left(\mathrm{x}\right)=-\nabla {\mathrm{U}}_{\mathrm{att}}\left(\mathrm{x}\right)={\mathrm{k}}_{\mathrm{att}}.\mathrm{d}\left(\mathrm{x},{\mathrm{x}}_{\mathrm{g}}\right)$$

(2)

The direction of attraction force is a line between first coordinate of the end-effecter and the goal object coordinate.

In Equations (3) and (4), repulsive potential field and repulsive force respectively [22,23]. The repulsive potential field is dependent on distant. When the UR5 manipulator reaches the obstacle’s effect region, it is subjected to repulsion force. The repulsion is greater for the closest (closer) obstacle. The coordinate of obstacle is $x_o=\left(x_o,y_o\right)$; the ${\mathrm{U}}_{\mathrm{rep}}\left(\mathrm{x}\right)$ is generated between the manipulator and obstacle based on the distance.

$$U_{rep}\left(X\right)=\frac{1}{2}{K}_{rep}{\left(\frac{1}{d\left(x,x_o\right)}-\frac{1}{d_o}\right)}^2$$

(3)

where $\mathrm{d}\left(\mathrm{x},{\mathrm{x}}_{\mathrm{o}}\right)\le {\mathrm{d}}_{\mathrm{o}}$. The ${\mathrm{U}}_{\mathrm{rep}}\left(\mathrm{X}\right)=0$ when $\mathrm{d}\left(\mathrm{x},{\mathrm{x}}_{\mathrm{o}}\right)$> ${\mathrm{d}}_{\mathrm{o}}$.

${\mathrm{K}}_{\mathrm{rep}}$: The repulsive potential field constant.

$\mathrm{d}\left(\mathrm{x},{\mathrm{x}}_{\mathrm{o}}\right)=||{\mathrm{x}}_{\mathrm{o}}-\mathrm{x}||$: Distant between the first coordinate of manipulator and obstacle of it (i.e., in the pick and place operation of the end-effector).

${\mathrm{d}}_{\mathrm{o}}$: Influence range of ${\mathrm{U}}_{\mathrm{rep}}\left(\mathrm{x}\right)$.

The repulsive force of the UR5 robot is the negative gradient of repulsion potential field ${\mathrm{U}}_{\mathrm{rep}}\left(\mathrm{X}\right)$.

$${\mathrm{F}}_{\mathrm{Rep}}\left(x\right)=-\nabla {\mathrm{U}}_{\mathrm{Rep}}\left(x\right)=\frac{1}{2}{\mathrm{K}}_{\mathrm{Rep}}\left(\frac{1}{\mathrm{d}\left(x,x_o\right)}-\frac{1}{{\mathrm{d}}_{\mathrm{o}}}\right)\frac{\nabla \mathrm{d}\left(x,x_o\right)}{{\mathrm{d}}^2\left(x,x_o\right)}$$

(4)

when $\mathrm{d}\left(\mathrm{x},{\mathrm{x}}_{\mathrm{o}}\right)\le {\mathrm{d}}_{\mathrm{o}}$ and zero other where.

The direction of repulsive force is the line between manipulator and obstacle object.

In Equations (5) and (6) the resultant potential field and resultant force respectively effecting on the UR5 manipulator.

$$U\left(x\right)=U_{att}\left(x\right)+U_{Rep}\left(x\right)$$

(5)

The resultant force F(x) is

$$\mathrm{F}\left(\mathrm{x}\right)=-\nabla U\left(x\right)=-\nabla U_{att}\left(x\right)-\nabla U_{Rep}\left(x\right)=F_{att}\left(x\right)+F_{Rep}\left(x\right)$$

(6)

${\mathrm{F}}_{\mathrm{Rep}}\left(\mathrm{x}\right)$ is the repulsive force from more than one obstacle and the ${\mathrm{F}}_{\mathrm{att}}\left(\mathrm{x}\right)$ is the attractive force of goal.

2.2. Particle Swarm Optimization (PSO)

The PSO algorithm can be used to solve problems of trajectory planning using a state function value and an Interactive Optimization by Particle Swarms (IPSO) [24,25]. The position at time (t) is updated through x_i(t) and in the future tense (t + 1) will be updated to x_i(t + 1) as in Equation (7)

x_i(t + 1) = x_i(t) + v_i(t + 1)

(7)

The velocity of particles is v_i(t) [12]. Each particle will have a cognitive component, which will be a relationship of the distance between the optimal solution and the social component, which is the collective’s understanding of the particle’s existence. For this problem, the PSO was applied globally (Global best PSO), with Equation (8) updating the particle velocity:

$${\mathrm{v}}_{\mathrm{ij}}(\mathrm{t}+1)={\mathrm{v}}_{\mathrm{ij}}\left(\mathrm{t}\right)+{\mathrm{C}}_1{\mathrm{r}}_1\left(\mathrm{t}\right)\left[{\mathrm{y}}_{\mathrm{ij}}\right(t)-{\mathrm{x}}_{\mathrm{ij}}(\mathrm{t}\left)\right]+{\mathrm{C}}_2{\mathrm{r}}_2\left(\mathrm{t}\right)\left[{\widehat{y}}_{\mathrm{ij}}\right(\mathrm{t})-{\widehat{x}}_{\mathrm{ij}}(\mathrm{t}\left)\right]$$

(8)

v_ij(t) is the particle’s velocity in a dimension at time t. The acceleration parameters are C₁, and C₂. The y_ij and $\widehat{y}$_ij which is the best position from the start [12], provide the information of the best particle. A velocity is assigned to each particle in the PSO algorithm. Particles move around the search space at different speeds, which are constantly changed based on their previous actions. Finally, during the search process, particles have a tendency to go via the best research area [12]. The trajectories of the joints of the handler can be optimized using a strategy which divides the robot into several aptitude functions to perform the optimal fit with modified PSO with crossover operator [26]. The simulation results are presented for manipulator trajectory planning of the UR5 using redundant kinematics mounted on a floating space.

Several simulations of the PSO algorithm were carried out with capability of changing the number of generations and particles. The best result of the algorithm was for 30 particles and for 2000 iterations that had the best values for the APF, and there was a convergence between the average of all particles and the best particle. For the PSO algorithm, the following were used element values:

Quantity of particles = 30 particles

Cognitive and social parameters (learning rates -C₁ and C₂) = 2

Iterations = 2000

Initial population generation = [−1, 1];

Inertia factor (w) = 0.5

The initial steps of traditional PSO algorithm represent in Algorithm 1.

Algorithm 1: The PSO algorithm is presented below

Initialization:

01: initialize the particle cloud

02: repeat

Loops 1:

03: for i = 1 to m

04: if f(xi) < f(pi) then pi = xi

05: if f(xi) < f(g) then g = xi

06: end if

07: end if

Loop.2:

08: for j = 1 to n

09: r1 = rand(), r2 = rand()

10: vij = wvij + c1r1(pi − xij) + c2r2(gj − xij)

11: end to

Function:

12: xi = xi + vi

13: end to

14: until you meet the stop criteria

The PSO algorithm’s stopping criterion is the algorithm’s generations number. In metaheuristic algorithms, elements representing solutions identified in a particular iteration for a given search space are added to the set E. Additionally, e_ij is an element that represents a solution i in iteration j, belonging to set E. The element e*_ij ϵE represents the fitness value of solution i which is the best value discovered in iteration j. A search space’s probable solutions are denoted by the letter S. So, E is a subset of S. Otherwise, this solution is considered an occasional solution given by Equation (9):

CHANCE = S − E

(9)

Chance_ij is a serendipitous element.

When chanceij’s fitness value is greater than element of e*_ij fitness value, the SRD forms occasional solutions according to Equation (10):

$$\mathrm{SRD}=\left[(sr{d}_{ij}\ast fitness\left(\mathrm{chanceij}\right))<\mathrm{fitness}\left(\mathrm{e}*\mathrm{ij}\right)\right]$$

(10)

The concept of serendipity is presented in this work. There are two important components in this work: irregularity and acceptability.

(a) Irregularity, because it is an element in iteration j that does not belong to set E.

(b) Acceptability because it indicates a solution with a higher fitness value than the element e*_ij.

2.3. Serendipity-Based Particle Swarm Optimization

The creation of serendipity-based recommendation mechanisms is a new and unsolved research challenge. “Something excellent or useful” might be considered as a candidate solution to replace after a specific iteration’s number that occurred when the concept of serendipity is applied to metaheuristic algorithms and their optimization applications.

The PSO algorithm has gained a lot of attention from the community’s search to solve optimization problems in the real world because of the simplicity of which it would be implemented, and the high quality of its output PSO is a stochastic approach for modeling birds social behavior. The solution in this type of algorithm is represented by a particle that “flies” over the search space looking for the best solution after a set number of iterations.

Particle motion is based on two types of information: pBest and gBest. pBest guides the particle to the swarm’s optimal location, whereas gBest impacts the particle’s progress to the swarm’s best position. After determining pBest and gBest, each particle uses Equations (11) and (12) to update its position and velocity:

$$V_{id}^{\left(t+1\right)}=w.V_{id}^t+{\mathrm{C}}_1.{\mathrm{r}}_1(p_{id}^t+X_{id}^t)+{\mathrm{C}}_2.{\mathrm{r}}_2(p_{gd}^t+X_{id}^t)$$

(11)

$$V_{id}^{\left(t+1\right)}=X_{id}^t+x_{id}^{\left(t+1\right)}$$

(12)

In Equation (11), the term $w$ represents the inertial velocity of the particle.

$X_{id}^t \mathrm{and} V_{id}^t$ are the position and velocity of particle i at time t.

The best fitness value of particle i and the best fitness value of all particles in the swarm up to time t, respectively, are $p_{id}^t$ and $p_{gd}^t$.

C₁ is a coefficient of the particle self-exploration, while C₂ is a particle’s movement in the direction of the global displacement of the swarm in search space.

r₁ and r₂ are random values in the interval [0, 1].

Serendipity presented as an ability to make lucky discoveries by way of intelligence and chance. In this work, the term “ intelligence“ should be understood as the quality of perceiving an event. This concept of serendipity is useful and interesting since it defines where serendipity can be applied to a traditional PSO algorithm, in addition to intelligence type, to improve the PSO’s behavior through serendipity-inspired options. Three natural techniques to implementing this enhancement are defined. The first is based on point random choice modifications accessible in the conventional PSO method. The second requires the addition of a mechanism for implementing a PSO algorithm using serendipity [27,28]. The third approach is a hybrid of the previous two approaches. Because it is important for an optimization technique and the best accessible solution on the current iteration, in all of these techniques, consider the search space’s “lucky discovery points.”

This work is dependent on the third approach. In [17], s strategy was proposed a to generate serendipity dependent on a perceptual model [29], which combines two strategies used in the recommendation systems [30]: Pasteur’s principle and blind luck. To detect the capabilities and apply insights to seize the moment, Pasteur’s principle is used. The principle uses scout particles in order to inspect regions in the space of unexplored search by the swarm, according to Equations (11) and (12). The blind luck strategy is implemented through the use of Girl Scout particles. They implement the random dimension and complement the space exploration of the traditional PSO generating additional diversity. These strategies are the implementation of the concept of intelligence or “the ready mind” in order to get a new algorithm called Serendipity-Based Particle Swarm Optimization (SBPSO). This algorithm used scout particles to search on peaks or valleys around the best in iterations points. Scout particles slow down the convergence time of the optimization algorithm and can be utilized to enhance algorithm capacity and scanning. It is worth remembering that adding the scout particles can help the swarm behavior. In the SBPSO method, the Girl Scouts are utilized to provide answers that were better than the swarm’s best particle. Equation (13) represents the velocity of a Girl Scout particle k:

$$V_{kd}^{\left(t+1\right)}=w.V_{kd}^t +{\mathrm{C}}_3.{\mathrm{r}}_3(X_{kd}^t+X_{best}^t)$$

(13)

C₃ is the variety coefficient and r₃ is a value random in the interval [−1, 1]. $X_{kd}^t$ is the position of the Girl Scout particle k and $X_{best}^t$ is the best particle’s position in the swarm at time t. Equation (14) represents the position of a scout particle k:

$$X_{kd}^{\left(t+1\right)}=V_{kd}^{\left(t+1\right)}-X_{best}^t$$

(14)

Algorithm 2 describes the initial step of SBPSO algorithm. The position and speed of each swarm particle and each scout particle which are randomly initialized (lines 1–2). The fitness value of each particle is then calculated to determine which particle is the best (lines 4–11) and for the scout particles (lines 12–19). In the next step the best particle will be found and named the new gBest particle (lines 20–26). After this, the particles start the inspection process at the proximity of the gBest particle (lines 27–31). For this, the algorithm creates n adjacent points (AP) are present in Equation (15):

$$\mathrm{AP}{\mathrm{n}}_{ }=best+\alpha ·R$$

(15)

Best: is the best particle current.

$\alpha$ is a real constant positive.

R is a 1× dim matrix with entries randomly distributed in the range [−1, 1], where dim is the current particle’s dimension.

According to Equation (16a), for each AP_n that was created, we define a vector $\overrightarrow{d_n}$ that represents the segment oriented $\overleftarrow{best{\mathrm{AP}}_{\mathrm{n}}}$:

$$\overrightarrow{d_n}=\mathrm{AP}{\mathrm{n}}_{ }-best$$

(16a)

best and AP_n define a single vector $\overrightarrow{d_n}$ which represents a direction, so there are infinite inspection points (IP) with address $\overleftarrow{\mathit{bestI}{P}_n^m}$ which is the same as $\overleftarrow{best{\mathrm{AP}}_{\mathrm{n}}}$. Thus, for each AP_n created, two IPs are chosen dependent on Equation (16b):

$$I{P}_n^m=best \pm \left(\raisebox{1ex}{$\Vert \overrightarrow{u}\Vert $}\!\left/ \!\raisebox{-1ex}{$\Vert \overrightarrow{d_n}\Vert $}\right.\right)·\mathsf{\lambda }·\overrightarrow{d_n}$$

(16b)

$I{P}_n^m$ is an inspection point m defined on the straight line that passes through best and AP_n, $\overrightarrow{u}$ is the vector $\overrightarrow{d_n}$ that has the smallest norm and λ is a non-zero real constant.

Two criteria are defined to find an inspection point that can replace the particle gBest current. The criteria are: (1) IP with fitness value is better than current particle gBest and (2) IP with fitness value is better than others. However, if there is more than one IP that meets these two criteria, a lottery is performed to choose one of them. According to Pasteur’s principle, luck favors the prepared mind. In this work, the concept of “mind prepared” is implemented through inspections around the particle gBest. As a result, there is the implementation of the intelligence dimension. Figure 1 presents an example of the choice of random inspection points in a 2D space.

In Figure 1, the direction of each of the straight lines is stochastic, since they connect the gBest to the inspection point tools. During all iterations, the lines have a reasonable perception of the behavior of the fitness function, even in an n–dimensional space.

Again, the swarm particles’ velocity is calculated, and the scout particles’ position is updated (lines 32–35). Finally, the program assesses the swarm’s state in terms of premature convergence and stagnation (row 36). The SBPSO restarts the position and velocity of the scout particles in (line 38):

Algorithm 2: SBPSO pseudocode using scout particles

Initialization:

01: initialize swarm speed and position

02: initialize speed and position of the Girl Scouts

03: while stop criteria not satisfied of the

loop.1:

04: for all particle i in S do

05: calculate fitness value

Condition:

06: if fit(xid) < fit(pBesti) then pBesti ← xid

07: end if

08: end for

Function:

09: bestswarm← get Best Particle Swarm()

loop.2:

10: for all Girl Scout k in S do

function:

11: determine fitness value

condition:

12: if fit(Girl scoutkd) < fit(pBestkd) then pBestkd← Girl scoutkd

13: end if

14: end for

function

15: best Girl Scout ← getBest Girl Scout()

condition:

16: if fit(bestswarm) < fit(best Girl Scout) and fit(bestswarm) < fit(gBest) then gBest ← bestswarm

17: else if fit(best Girl Scout) < fit(bestswarm) and fit(best Girl Scout) < fit(gBest) then gBest ← best Girl Scout

18: end if

19: end if

20: creates n adjacent points (AP) using Equation (15)

loop.3

21: for all AP of the

22: define n director vectors $\overrightarrow{d}$ using Equation (16)

23: for each vector $\overrightarrow{d}$ do

24: Create two IP using Equation (17)

25: end for

26: end for

27: gBest ← getBest Inspection Point()

Loop.4

28: for all particle i in S do

29: determine speed using Equation (11)

30: update position using Equation (12)

31: end for

Loop.5

32: for each Girl Scout k in S do

33: calculate speed using Equation (13)

34: update position using Equation (14)

35: end for

36: if (swarm stagnated) and (swarm converged) then Resets Girl Scout Position and Speed

37: end if

38: end while

2.4. Methods for Detecting Premature Convergence

The PSO algorithm is a mechanism that can generate good trajectories in a short amount of time. However, the algorithm runs the risk of prematurely converging. The swarm will be converged prematurely when the solution proposal approaches a good location instead of the problem being optimized. Premature convergence is caused by a decrease of variety in the search space, which enables the swarm to become stagnant. After premature convergence begins, the particles continue to shut on each other in a very small region of the search space [27]. In order to avoid swarm stagnation, three strategies for detecting early convergence are proposed in [28]:

1.

Determines the greatest Euclidean distance between the gBest particle and a swarm particle. When this distance is smaller than a threshold distance termed $\delta$ stag, stagnation develops. Equation (17) is a form to present it:

$${\phi }_j=\frac{ma{x}_{iϵ\left[1,\dots ,S\right]}\Vert \mathrm{eij} - \mathrm{e}*\mathrm{ij}\Vert }{\left|{\mathsf{\mu }}_{\max }-{\mathsf{\mu }}_{\min }\right|}$$

(17)

where ‖e_ij − e*_ij‖, is the Euclidean distance between the gBest particle and a particle of the swarm in iteration j. μ_min and μ_max represent the minimum and maximum of particle I, respectively.

2.

Cluster Analysis consists of evaluating the percentage of the particle’s number of a cluster C. If the distance between a particle belongs to C and the gBest particle which is less than a threshold $\delta$ min, the convergence has occurred, when a percentage of particles in C reach a threshold $\delta$ max.

3.

Objective Slope Function considers the position of particles in search space based on its normalized value and the change rate of objective function which is obtained through Equation (18):

$$f_{ratio}=\frac{ f\left(y_j^{^}\right)-f\left(y_{j-1}^{^}\right)}{f\left(y_j^{^}\right)}$$

(18)

where f($y_j^{^}$) s the objective function’s fitness value on iteration j, and f($y_{j-1}^{^}$) is the objective function’s fitness value on iteration j−1. A counter is incremented if the value of $f_{ratio}$ is less than a predefined threshold.

2.5. Computational Experiments

The computational experiments are presented in this section and implementation results of the APF+PSO and APF+SBPSO algorithm are presented to obtain collision-free trajectories as well as the potential surfaces for each algorithm will represent.

A. APF+PSO simulations

Figure 2 plots a graph of aptitudes and generations, where it is feasible to see when the number of particles is equal to 2000 iterations, the best particle, and the average of all particles converge.

The potential field parameters found in the simulation of the PSO algorithm for 30 particles and 2000 iterations are presented in

Table 1. Values of parameters and intensities founded by PSO for 30 particles and 2000 iterations.

Parameter	kr	Ka	Ko
intensity	2.29	5.250	0.489

. Figure 3 shows the lines of the artificial potential field and the collision-free trajectory, in Cartesian space for the simulation performed, using the parameters in Table 1, obtained from the locations of the obstacles.

In Figure 4, the resulting surface of the field is shown. Potential for the scene is shown in Figure 3.

B. APF+SBPSO simulations

In this section, some functions of benchmark used to evaluate the proposed algorithm and the parameters used are represented.

The Benchmark Functions

Some functions chosen are often applied in minimization problems to confirm the stagnation and convergence of the algorithm [28]. In [29,30,31] and several other PSO studies, the functions are described below:

• Sphere function—characterized by being simple, convex and unimodal. Its main function to evaluate the convergence rate of the search process are represented in Equation (19):

$$f_1(x)={{\displaystyle \sum }}_{\mathrm{i}=1}^{\mathrm{d}}{\mathrm{x}}_{\mathrm{i}}^2$$

(19)

2.

Rosenbrock function—has the global minimum in parabolic valley. In this function, the convergence is difficult [32]; this function is represented in Equation (20):

$$f_2(x)={{\displaystyle \sum }}_{i=1}^{d-1}\left[100{\left(x_{i+1}\right)}^2+{\left(x_i\right)}^2\right]$$

(20)

3.

Griewank function—several local minimums regularly distribute and are represented in Equation (21):

$$f_3(x)=\frac{1}{400}{{\displaystyle \sum }}_{i=1}^d{x}_i^2-{{\displaystyle \prod }}^{ }cos(\frac{x_i}{\sqrt{i}})+1$$

(21)

4.

Rastrigin function—it is a highly multimodal function; however, the locations of the various local minima are regularly distributed and represented in Equation (22):

$$f_4(x)={{\displaystyle \sum }}_{i=1}^d(x_i^2-10cos\left(2\pi x_i\right)+10$$

(22)

5.

HappyCat function—is characterized by being unimodal. This feature makes the algorithms of optimization find it difficult to escape from a “black groove” [33] represented in Equation (23):

$$f_5(x)={\left[{\left(\Vert x{\Vert }^2-d\right)}^2\right]}^{\frac{1}{8}}+\frac{1}{d}(\frac{1}{2}{||x||}^2+{{\displaystyle \sum }}_{i=1}^d{x}_i)+\frac{1}{2}$$

(23)

6.

Ackley function—there are several local minimums in the parabolic valley. If the function characterized by having an almost flat outer region represent in Equation (24):

$$f_6(x)=-20\exp (-0.2\sqrt{\frac{1}{d}}{{\displaystyle \sum }}_{i=1}^d{x}_i^2)-exp(\frac{1}{d}{{\displaystyle \sum }}_{i=1}^{d}cos\left(2\pi x_i\right))+20+exp\left(1\right)$$

(24)

For each of the functions presented,

Table 2. Benchmark functions characteristics.

Functions	Search Space	Initialization Range
f1	$-200\le x_i\le 200$	$100\le x_i\le 200$
f2	$-130\le x_i\le 130$	$75\le x_i\le 130$
f3	$-300\le x_i\le 300$	$150\le x_i\le 300$
f4	$-6.10\le x_i\le 6.10$	$3.05\le x_i\le 6.10$
f5	$-4\le x_i\le 4$	$2\le x_i\le 4$
f6	$-30.00\le x_i\le 30.00$	$15\le x_i\le 30.00$

shows the search space boundaries and the initialization ranges.

The values associated with the parameters w, C₁, and C₂, are defined in Equation (11). The standard PSO’s performance might vary, also its modifications [34,35].

To perform a proper comparison, all parameters of the SBPSO and the standard PSO were defined with the same value: w (weight of inertia) which starts at 0.9 and C₁ = C₂ = 2.0 and decays linearly ending at 0.3. The maximum velocity V_max of the particle has been defined related to the dimensions of the search space [25].

Other parameters are specific to SBPSO. They are related to quantity and speed of the scout particles, the detection of premature convergence, and the creation of inspection and adjacent points. The number of Girl Scouts was set to 12 percent of the total number of particles. Equations (13), (15), and (17) have additional parameters: C3 = 1.5, which corresponds to 2% of the search space, and λ = 10⁻⁴.

Two thresholds were used: ${\delta }_{stag}$ and ${\delta }_{conv}$ to detect premature convergence. ${\delta }_{stag}$ was assigned the value 10⁻⁴ and the threshold ${\delta }_{conv}$. corresponds to 6% of the total iterations number. ${\delta }_{conv}$. used to set iterations number whose gBest particle’s fitness value has not improved. All of the above parameters were set after repeated simulations and produced good results in the functions which have been studied.

3. Results

The performance of the SBPSO algorithms is evaluated and makes a comparison study with the traditional PSO algorithm applied on UR5 trajectory planning. The result presents the fact that, in the SBPSO, the result of serendipity combined with scout particles, more active than the traditional PSO.

Figure 5, Figure 6, Figure 7, Figure 8, Figure 9 and Figure 10 show the behavior of the swarm (with 30 particles) in the Sphere, Rosenbrock, Griewank, Rastrigin, HappyCat and Ackley, for 2000 iterations respectively. In the figures below, the traditional PSO stagnated before iteration 2000, but the SBPSO is still active.

Table 3. The comparison between standard PSO algorithm and SBPSO algorithm by using benchmark functions applied on UR5 robot.

Size of Population	Iteration	Fitness Value of Benchmark Functions
		Sphere Function		Rosenbrock Function		Griewak Function		Rastrigin Function		HappyCat Function		Ackley Function
20	1000	PSO	SBPSO	PSO	SBPSO	PSO	SBPSO	PSO	SBPSO	PSO	SBPSO	PSO	SBPSO
		1.2196 × 10−31	3.7821 × 10−156	57.7381	1.4324 × 10−4	0.1692	0	3.9673	0	1.2226 × 10−14	1.3323 × 10−16	1.0284 × 10−10	9.2371 × 10−16
	2000	2.9396 × 10−11	7.3821 × 10−124	150.7192	2.8091 × 10−2	0.0185	0	20.6732	0	2.0678 × 10−5	1.0736 × 10−11	2.1024	8.8818 × 10−16
30	1000	1.9504 × 10−22	3.9011 × 10−129	29.6739	1.0476 × 10−4	0.0287	0	4.6732	0	3.6771 × 10−14	2.2204 × 10−16	0.4030	6.4310 × 10−16
	2000	2.0422 × 10−10	9.7813 × 10−84	131.6743	1.9692 × 10−2	0.0532	0	37.8871	0	1.8586 × 10−6	4.5530 × 10−14	1.2258	9.7320 × 10−16
50	1000	7.6959 × 10−28	2.5243 × 10−31	23.5431	9.9319 × 10−4	0.0659	0	1.9591	0	4.2327 × 10−15	2.3592 × 10−16	6.1342	7.6102 × 10−16
	2000	1.5353 × 10−17	8.9143 × 10−120	64.9304	5.6966 × 10−3	0.0383	0	33.6462	0	3.9029 × 10−5	4.6358 × 10−13	1.8144	8.6098 × 10−16

and

Table 4. Comparison between standard deviation of the traditional PSO and SBPSO with a populations of 20 particles.

Functions	Iteration	PSO	SBPSO
Sphere function	1000	3.1403 × 10−22	3.7821 × 10−156
	2000	1.4253 × 10−6	3.6721 × 10−81
Rosenbrock function	1000	57.7381	1.4324 × 10−4
	2000	150.7192	2.8091 × 10−2
Griewank function	1000	0.1692	0
	2000	0.0185	0
Rastrigin function	1000	3.9673	0
	2000	48.7790	0
HappyCat function	1000	4.6100	0
	1500	19.6670	0
Ackley function	1000	4.1558 × 10−11	0
	2000	4.8007 × 10−11	0

show the size of the population, the iterations number, the best fitness value and standard deviation of benchmark functions.

Figure 11 show the contour path with avoid collision for universal manipulator robot UR5.

4. Conclusions

This paper developed a Serendipity-Based Particle Swarm Optimization (SBPSO) variant of the traditional PSO in order to prevent the premature convergence of optimization procedures. The algorithm based on an approach with two dimensions of the serendipity concept: intelligence and chance. The intelligence dimension implemented by inspections at the adjacencies of the gBest particle. The chance dimension implemented by using the particles to improve search space exploration. After the studies were completed, it was shown that the SBPSO outperformed the standard PSO. To make these comparisons, two criteria were analyzed: convergence and stagnation. In the convergence criterion, when the Griewank and Rastrigin were evaluated, the SBPSO algorithm found the global solutions faster than the PSO algorithm. For the Sphere, Rosenbrock, HappyCat and Ackley functions, none of them found the optimal solutions. However, the SBPSO algorithm found very satisfactory solutions when compared with PSO. The evaluation of the stagnation criterion in the Sphere function showed that when the SBPSO was compared with the traditional PSO, it was delayed at least 21%. For the Rosenbrock function, the stagnation delay was at least 30% of the number of iterations compared to the traditional PSO. To the Griewank function, the SBPSO slowed the stagnation by less 20% when compared to the traditional PSO. For the Rastrigin function, stagnation was delayed at least 34% compared to the traditional PSO. In the HappyCat function, when the SBPSO was compared to the traditional PSO, there was a delay at less than 20% of the maximum iterations number. Finally, in the Ackley function, the SBPSO delayed the stagnation at least 20%, in relation to the traditional PSO algorithm. In these experiments, the SBPSO algorithm gave a better convergence behavior, overcoming some variations in relation to the quality of the solution, such as ability to find the global optimum, the stability of solutions and the ability to restart the swarm movement in stagnation case. In general, the results proved to solve the optimization problem of universal robot UR5 trajectory planning and find the optimal path. In future work, we will apply the SBPSO algorithm to solve more real-world optimization problems, such as vehicle localization, wireless sensor networks, and velocity estimation.