Hybridizing Particle Swarm Optimization and Differential Evolution for the Mobile Robot Global Path Planning

Abstract

Global path planning is a challenging issue in the filed of mobile robotics due to its complexity and the nature of non-deterministic polynomial-time hard (NP-hard). Particle swarm optimization (PSO) has gained increasing popularity in global path planning due to its simplicity and high convergence speed. However, since the basic PSO has difficulties balancing exploration and exploitation, and suffers from stagnation, its efficiency in solving global path planning may be restricted. Aiming at overcoming these drawbacks and solving the global path planning problem efficiently, this paper proposes a hybrid PSO algorithm that hybridizes PSO and differential evolution (DE) algorithms. To dynamically adjust the exploration and exploitation abilities of the hybrid PSO, a novel PSO, the nonlinear time-varying PSO (NTVPSO), is proposed for updating the velocities and positions of particles in the hybrid PSO. In an attempt to avoid stagnation, a modified DE, the ranking-based self-adaptive DE (RBSADE), is developed to evolve the personal best experience of particles in the hybrid PSO. The proposed algorithm is compared with four state-of-the-art evolutionary algorithms. Simulation results show that the proposed algorithm is highly competitive in terms of path optimality and can be considered as a vital alternative for solving global path planning.

Keywords

Mobile Robot Global Path Planning Particle Swarm Optimization Differential Evolution Hybrid Particle Swarm Optimization Evolutionary Computation

1 Introduction

Over the past few decades, mobile robotics has been successfully applied in industry, military and security environments to perform crucial unmanned missions such as planet exploration, surveillance and landmine detection [39]. A fundamental issue of mobile robotics is path planning, which aims to find an optimal or sub-optimal obstacle-free path from a starting location to a destination location, while optimizing some performance criteria. Due to its widespread application in different areas such as computer games, animation, assembly planning and computational biology, path planning has drawn increasing research interest since the mid-1960s [36].

Generally, path planning can be categorized into global path planning (GPP) and local path planning (LPP), with respect to whether full knowledge of the environment is available or not [39]. GPP, executed offline, determines an obstacle-free path while being aware of complete information pertaining to the environment [35, 39]. LPP, also called online path planning, generates an efficient path by using no or partial information of the environment [35, 39]. This paper focuses on the GPP problem, which is good at generating an efficient path offline. For simplicity, the GPP problem is referred to as the path planning problem throughout the rest of this paper.

To date, path planning has been intensively studied in the literature and numerous path planning methods have been proposed. However, owing to its non-deterministic polynomial-time hard (NP-hard) nature, efficiently solving the path planning problem remains a challenge [5, 6, 14, 21, 35, 36, 39]. Thanks to their population-based nature and good search ability for producing high-quality solutions within a tractable time, even for complex problems [39], evolutionary algorithms (EAs) such as the genetic algorithm [1], simulated annealing [28] and artificial neural network [9] have been proposed in the field of path planning in recent years.

As one of the most powerful EAs, due to its simplicity and high convergence speed, the particle swarm optimization (PSO) algorithm has been widely implemented to solve path planning [12, 19, 32, 36]. Nevertheless, since the basic PSO algorithm cannot balance exploration and exploitation sufficiently, it is easily trapped in a local optimum [2]. Furthermore, the basic PSO may also suffer from stagnation when no particle can find a position that is better than its previous best positions [16]. In order to enhance the performance of PSO, it is essential to overcome these two shortcomings.

The differential evolution (DE) algorithm is another promising evolutionary algorithm that emerged as a highly competitive algorithm more than a decade ago [4]. Due to its simplicity, reliability, high performance and easy implementation, a considerable amount of research has been dedicated to applying DE to solve different optimization problems [8, 20, 38]. It is well-known that different generation strategies (i.e., mutation and crossover operators) and control parameters (i.e., scaling factor and crossover rate) significantly influence the performance of DE [8, 20, 38]. However, how to set generation strategies and control parameters are problem-dependent, which results in difficulties when designing an efficient DE algorithm [8, 38].

Since both PSO and DE are EAs that deal with population evolution, it is natural to mix these two algorithms together to leverage their advantages when developing an integrated method for efficiently solving optimization problems. Motivated by this idea, some research such as [11, 16, 17, 24, 33, 34] has been devoted to hybridizing PSO and DE in order to improve the performance of hybrid algorithms.

In this study, we also combine PSO with DE and propose a hybrid PSO-DE algorithm, the HNTVPSO-RBSADE, for mobile robot global path planning. In the proposed hybrid PSO algorithm, a novel PSO, called NTVPSO, is first developed to update the velocities and positions of particles. Then, after each iteration, a modified DE algorithm, called RBSADE, is proposed to evolve the personal best positions of particles in order to force particles to jump out of stagnation. In order to sufficiently balance the exploration and exploitation capabilities of particles, a new self-adaptive mechanism is proposed to adaptively adjust the three control parameters (inertia weight and cognitive and social acceleration parameters) of particles in NTVPSO. To improve the performance and easily adjust the control parameters of RBSADE, a ranking-based mutation operator and a self-adaptive strategy are developed in RBSADE.

To verify the proposed algorithm for solving mobile robot global path planning, it is compared to JADE [35], the time-varying particle swarm optimization (TVPSO) method [15], the gravitational search (GS) method [18] and the modified genetic algorithm (mGA) [25] under different simulation scenarios. For rigorous verification, path optimality and computation time are examined and compared for each algorithm. The simulation results confirm that the proposed algorithm outperforms the algorithms it is compared to in terms of path optimality. Moreover, the computation time of the proposed algorithm is also comparable with that of the other algorithms.

The remainder of the paper is organized as follows. Section 2 formulates the path planning problem and introduces the scheme for encoding the path, as well as the constraint handling technique. Section 3 presents the HNTVPSO-RBSADE algorithm and analytical investigations pertaining to this algorithm. Section 4 presents the framework for applying HNTVPSO-RBSADE to solve mobile robot global path planning. Simulations and comparisons are performed in section 5. Section 6 summarizes the paper by way of a conclusion and options for future work.

2 Statement of the Path Planning Problem

2.1 Modelling of the workspace

This paper focuses on finding an obstacle-free path for a mobile robot working in a 2-D complex workspace. The model presented in [13] is adopted to establish the workspace, due to its simplicity and small sensitivity to the shapes of obstacles. As shown in Fig. 1, a global coordinate system o - xy is established, where st and ta denote the start location and the destination location of a robot, respectively. The x -axis of the global coordinate system coincides with line st - ta and the y -axis of the global coordinate system is perpendicular to line st - ta. In the global coordinate system, line st - ta is equally divided into n + 1 subsections by n points, where n is a predefined parameter. After drawing n vertical lines l₁, l₂,…, l_n, as shown in Fig. 1, a point-to-point path, denoted as ph = [st, p₁, p₂,…,p_n, ta], is constructed by random sampling on vertical lines l₁, l₂,…, l_n. All obstacles in the workspace are assumed to be static and are represented by polygons. The robot is considered a mass point and obstacles are enlarged according to the size of the robot to compensate [9, 39].

Figure 1.

The illustration of the 2-D workspace

2.2 Formulation of the path planning problem

As searching for the best path is often associated with finding the shortest and safest path, as in [9, 13, 18, 36, 37], path length and path safety are considered as being two performance criteria of the path planning problem in this paper. Let p₀ and p_n+1 denote the start location and the destination location of a robot, respectively. The path planning problem can be mathematically formulated as [18, 37]:

{\begin{matrix} finding: p h = [s t = p_{0}, p_{1}, p_{2},…, p_{n}, t a = p_{n + 1}] \\ minimize: J_{c o s t} = w_{1} \cdot J_{L} + w_{2} \cdot \frac{1}{J_{S}} \\ s.t. p_{i} p_{i + 1} \in semi - free workspace, 0 \leq i \leq n \end{matrix}

(1)

where J_L and J_S denote path length and path safety, respectively, and w₁ and w₂ are two weighting parameters indicating the relative importance of J_L and J_S (w₁ = w₂ = 1 in this paper).

To generate a point-to-point path, J_L is calculated as [6]:

J_{L} = \sum_{i = 0}^{n} d i s (p_{i}, p_{i + 1})

(2)

where dis(p_i, p_i+1) denotes the Euclidean distance between waypoint p_i and waypoint p_i+1.

J_L is the summation of the minimum distance of each path segment from the nearest obstacle along the path, which is calculated as [6]:

J_{S} = \sum_{i = 0}^{n} \min_{1 \leq j \leq N o b} {M i n d i s (p_{i} p_{i + 1}, O_{j})}

(3)

where Nob denotes the number of obstacles. Mindis(p_i p_i+1,O_j) represents the minimum distance between path segment p_i p_i+1 and obstacle O_j.

2.3 Path encoding scheme

As stated in section 2.1, a path is constructed by a set of waypoints p₁, p₂,…, p_n, while a set of lines l₁, l₂,…, l_n determines the x -axis values of these points. Since the set of lines l₁, l₂,…, l_n is given beforehand during the construction of the workspace, values of p₁,…, p_n lie only with the y -axis values decided by l₁, l₂,…, l_n. These y -axis values, denoted as (y_{p
₁},y_{p
₂},…,y_{p
_n}), are applied in order to encode the path [13, 36]. The following saturation strategy is used to modify y_{p
_i} (i = 1,2,…,n) when y_{p
_i} is outside of the workspace as follows:

y_{p_{i}} = {\begin{matrix} \frac{w i d t h}{2}, if y_{p_{i}} > \frac{w i d t h}{2} \\ \frac{- w i d t h}{2}, if y_{p_{i}} < \frac{- w i d t h}{2} \\ y_{p_{i}}, otherwise \end{matrix}

(4)

where width represents the width of the workspace as shown in Fig. 1.

2.4 Handling constraint and evaluating path

From (1), it can be seen that the path planning problem is a constrained optimization problem. In order to solve the constraint problem easily and efficiently, the task of how to handle the constraint must be addressed. As the constraint of the path planning problem is to generate an obstacle-free path, it is reasonable to evaluate the constraint violation degree of each candidate path by counting its collision times with obstacles [36]. Given Nob obstacles, the total constraint violation degree of candidate path m₁ is calculated as [36]:

\begin{array}{l} v i o l a t i o n_{m_{1}} = \frac{1}{N o b} \sum_{j = 1}^{N o b} v i o l_{m_{1} j} \\ v i o l_{m_{1} j} = {\begin{matrix} 1 & if m_{1} collides with obstacle j \\ 0 & otherwise \end{matrix} \end{array}

(5)

After calculating the constraint violation degree and the fitness value of each candidate path, the feasibility-based rule [7, 27] is used to evaluate and select the elite path between any two candidate paths. The feasibility-based rule is described as: (1) for any two paths with the same constraint violation degree, the path with better fitness is preferred; (2) for any two paths with different constraint violation degrees, the path with a smaller constraint violation degree is preferred.

Since the fitness and constraint violation information of each candidate path are considered separately in the feasibility-based rule, no additional parameter is needed to transform the constrained path planning problem into an unconstrained one, which decreases optimization difficulty. Additionally, although the non-feasible paths collide with some obstacles, they may also contain high-quality path segments. When these high-quality path segments are considered, the diversity of the paths and the possibility of finding high-quality paths are increased. This is one main reason why non-feasible solutions are considered in the feasibility-based rule.

3 The Optimization Method

3.1 Review of the basic PSO

Inspired by birds flocking and fish schooling, Kennedy and Eberhart first proposed PSO in 1995 [10]. Each particle in PSO represents a potential solution to an optimization problem and is associated with a velocity that is dynamically adjusted according to its own flight experience, as well as those of its companions. Therefore, each particle is attracted to a stochastically weighted average of its personal best position and the global best position of the swarm. In the basic PSO algorithm, from iteration k to iteration k + 1, each particle updates its velocity and position as follows [10]:

V_{m}^{k + 1} = w V_{m}^{k} + c_{1} r_{1} (p b e s t_{m}^{k} - X_{m}^{k}) + c_{2} r_{2} (g b e s t^{k} - X_{m}^{k})

(6)

X_{m}^{k + 1} = X_{m}^{k} + V_{m}^{k + 1}

(7)

where V^k_m and X^k_m denote the velocity and position vectors of particle m at iteration k; w is a real coefficient denoting the inertia weight; c₁ and c₂ are two positive real coefficients representing the cognitive and social acceleration parameters; r₁ and r₂ are two random numbers uniformly distributed in [0,1]; pbest^k_m denotes the personal best position of particle m at iteration k and gbest^k denotes the global best position of the swarm at iteration k.

3.2 Review of the conventional DE

DE is a population-based algorithm that initializes a population of SP individuals in a D-dimensional search space. Each individual, known as either a genome or chromosome, denotes a potential solution to an optimization problem. After mutation, crossover and selection operators, an offspring is allowed to the next generation only if it improves on the fitness of the parent [23].

The mutation operator modifies an individual via random changes in order to generate a new offspring, which aims to add some diversification into the population to avoid the local optimum [23]. At iteration k, for each parent x_i(k), a trial vector v_i(k) is generated by mutating three (or more) individuals as follows:

v_{i} (k) = x_{i_{3}} (k) + F_{i} (x_{i_{1}} (k) - x_{i_{2}} (k))

(8)

where x_{i
₁}(k), x_{i
₂}(k) and x_{i
₃}(k) are randomly selected from the current swarm with i ≠ i₁ ≠ i₂ ≠ i₃ and F_i denotes the scaling vector that is applied to control the amplification of the differential variation.

The crossover operator follows a discrete recombination approach, where elements from the parent vector x_i(k) are combined with those from the trial vector v_i(k) to produce a new offspring u_i(k). The aim of the crossover operator is to explore new areas of the search space [23]. Using the binomial recombination, each element in u_i(k) is obtained as follows:

u_{i j} (k) = {\begin{array}{l} v_{i j} (k), if r n d_{i j} [0,1] \leq C R or j = j_{r n d} \\ x_{i j} (k), otherwise \end{array}

(9)

where j(j = 1,2,…,D) refers to a specific dimension; x_ij, v_ij(k) and u_ij(k) are the jth elements of x_i(k), v_i(k) and u_i(k), respectively; j_rnd indicates a random integer in [1,D]; rnd_ij is a random number uniformly distributed in 0,1 and CR represents the crossover rate.

The selection operator is a one-to-one spawning strategy in which the new offspring u_i(k) competes against the parent x_i(k) and the better one will be selected for the next generation. In a minimization optimization problem, the selection operator is given as follows:

x_{i} (k + 1) = {\begin{array}{l} u_{i} (k), if f (u_{i} (k)) \leq f (x_{i} (k)) \\ x_{i} (k), otherwise \end{array}

(10)

where f(u_i(k)) and f(x_i(k)) denote the fitness values of u_i(k) and x_i(k), respectively.

3.3 The proposed HNTVPSO-RBSADE

Since the proposed HNTVPSO-RBSADE algorithm incorporates NTVPSO and RBSADE, NTVPSO and RBSADE are first presented separately below. Then, the HNTVPSO-RBSADE-based framework is presented in this subsection.

3.3.1 Nonlinear time-varying PSO (NTVPSO)

When using PSO to solve optimization problems, it is necessary to properly control the exploration and exploitation abilities of PSO in order to efficiently find an optimal solution [2, 22]. Ideally, on the one hand, in the early stage of the evolution, the exploration ability of PSO needs to be strengthened so that particles can wander through the entire search space, rather than clustering around the current population-best solution [2, 22]. On the other hand, in the later stage of the evolution, the exploitation capability of PSO must be promoted so that particles can search carefully in a local region to find optimal solutions efficiently [2, 22].

Proverbially, the exploration and exploitation capabilities of PSO heavily depend on its three control parameters. The basic philosophies concerning how the three control parameters influence such abilities of PSO can be summarized as follows: (1) a large inertia weight enhances exploration, while a small inertia weight facilitates exploitation [22, 26]; (2) a large cognitive component, compared to the social component, results in the wandering of particles through the entire search space, which strengthens exploration [22, 26]; (3) a large social component, compared with the cognitive component, leads particles to a local search, which strengthens exploitation [22, 26].

Considering all of the concerns noted above, this paper proposes a novel PSO called NTVPSO. The main purpose of this PSO is to adaptively balance the exploration and exploitation capabilities of NTVPSO, so that the performance of the algorithm can be improved. In order to achieve this goal, a novel self-adaptive mechanism that is used to update the three control parameters of each particle in NTVPSO is proposed as follows:

w = \frac{w_{m a x} - w_{m i n}}{\exp (δ_{m} \cdot β_{m} \cdot k)} + w_{m i n}

(11)

c_{1} = \frac{c_{1 s} - c_{1 f}}{\exp (δ_{c 1} \cdot β_{m} \cdot k)} + c_{1 f}

(12)

c_{2} = \frac{c_{2 s} - c_{2 f}}{\exp (- δ_{c 2} \cdot β_{m} \cdot k)} + c_{2 f}

(13)

δ_{m} = \frac{w_{m a x} - w_{m i n}}{k_{m a x}}

(14)

δ_{c 1} = \frac{c_{1 s} - c_{1 f}}{k_{m a x}}

(15)

δ_{c 2} = \frac{c_{2 s} - c_{2 f}}{k_{m a x}}

(16)

β_{m} = \frac{‖ V_{m}^{k - 1} ‖ + ‖ V_{m}^{k} ‖}{2 ‖ V_{m}^{k - 1} ‖ + Δ}

(17)

where w_max and w_min denote the upper and lower bounds of w; c_1s and c_1f denote the initial and final values of c₁; c_2s and c_2f represent the initial and final values of c₂; k_max represents the maximum iteration number; ‖V^k-1_m‖ and ‖V^k_m‖ denote the L₂-norm of the velocity vector of particle m at iteration (k - 1) and iteration k. Δ is a very small positive value in case the denominator of β_m becomes zero (Δ = 1e - 25 in this paper). Note that w_max > w_min, c_1s > c_1f and c_2s<c_2f in NTVPSO. Furthermore, note that particles in NTVPSO update their velocities and positions based on (6) and (7).

3.3.2 Parametric analysis for NTVPSO

From (11) to (13), with increasing iteration number k, it is clear that w and c₁ decrease, while c₂ increases in NTVPSO. Therefore, according to the aforementioned basic philosophies, NTVPSO is likely to start the search with a high exploration tendency, which will be reduced over time, so that exploitation may be favoured in the late stage of the evolution. Note that following the update rule of a fixed β_m, the balance between exploration and exploitation varies only with respect to the iteration number k.

We also adapt the balance of the search in NTVPSO using an additional parameter β_m. From (11) and (12), it is trivial that w and c₁ decrease as β_m increases. On the other hand, the variation in c₂ becomes larger as β_m increases, as shown in (13). This implies that, for large β_m, the exploration capability of NTVPSO tends to be retained, compared to the case where there is small β_m. In contrast, the exploitation ability of the algorithm takes over the exploration ability more rapidly as β_m decreases.

Briefly, by utilizing the proposed self-adaptive strategy defined from (11) to (17) in NTVPSO, the three control parameters of particles are adaptively adjusted, complying with the basic philosophies of PSO improvement. Therefore, the NTVPSO algorithm is expected to improve the ability for finding high-quality solutions. Fig. 2 demonstrates the tendency of these changes in the three control parameters with respect to different values of β_m. Note that w_max = 0.9, w_min = 0.1, c_1s = c_2f = 2.5, c_1f = c_2s = 0.5 and k_max = 100 in Fig. 2.

3.3.3 Ranking-based self-adaptive DE (RBSADE)

In the conventional DE algorithm, the three different individuals used for the mutation operator are randomly selected from the current swarm. However, it is natural that good species always contain good genetic information, making them more likely to be utilized for mutating better offspring. Based on this consideration, this paper develops a modified DE called RBSADE, in which a ranking-based strategy is developed to select the good species. In the ranking-based strategy, all parent individuals at the current iteration are first sorted in ascending order according to their fitness values and constraint violation degrees. Then, at the current iteration, the ranking value of the i th parent individual is assigned as follows:

Figure 2.

Changes of the three control parameters under different β_m in NTVPSO

R V_{i} = S P - i

(18)

where i =1,2,…,SP and SP denotes the size of the swarm.

After calculating the ranking value of each parent individual, the selection probability that the ith individual is allowed to participate in the mutation operator is calculated as follows:

p_{i} = \frac{R V_{i}}{S P}

(19)

It is clear from the ranking-based strategy that the better genetic information a parent contains, the higher the probability that it will be selected for participating in the mutation operator and the more likely a better offspring will be produced. After calculating the selection probability of each parent individual at the current iteration, the roulette-wheel mechanism is applied to select three different individuals from the current swarm to mutate a new offspring according to the mutation operator given in (8).

In order to decrease the difficulties in controlling the crossover rate, the self-adaptive strategy proposed in [31] is applied to dynamically update the crossover rate of each individual in RBSADE as follows:

C R_{i} (k + 1) = {\begin{array}{l} C R_{i} (k), if f (u_{i} (k)) \leq f (x_{i} (k)) \\ N (0.5,0.1), otherwise \end{array}

(20)

where N(0.5,0.1) is a random number generated by a normal distribution of mean 0.5 and standard deviation 0.1. When f(u_i(k)) ⩽ f(x_i(k)) for individual i, it means the current crossover rate of the individual has a higher possibility to improve the quality of the candidate solutions at the next iteration. Hence, keeping the current crossover rate may obtain better solutions [31]. When the trial vector u_i(k) is worse than the current vector x_i(k), it implies that the current crossover rate of the individual has a lower chance of generating better candidate solutions. Therefore, changing the current crossover rate may be more suitable for the evolution process [31].

To adaptively adjust the scaling vector F_i, a new self-adaptive strategy is developed to update each element of F_i by using a diversity measure as follows:

F_{i, j} = 1 - d i v_{i, j} (k)

(21)

d i v_{i, j} (k) = \frac{\sum_{i = 1}^{S P} \sqrt{E}}{S P \cdot m a x (\sqrt{E})}

(22)

E = \sum_{j = 1}^{D} {[x_{i, j} (k) - {\bar{x}}_{j} (k)]}^{2}

(23)

{\bar{x}}_{j} (k) = \frac{1}{S P} \sum_{i = 1}^{S P} x_{i, j} (k)

(24)

where F_i,j is the j th element of scaling vector F_i; SP denotes the size of the swarm; div_i,j(k) represents the normalized diversity for the j th dimension of the i th parent individual at iteration k; ${\bar{x}}_{j} (k)$ is the average of the j th dimension over all parent individuals. One advantage of the developed self-adaptive strategy is that the mutation step-size F_i(x_{i
₁}(k)-x_{i
₂}(k)) can be adaptively controlled based on the diversity measure, without adding any additional parameters, which consequently releases the burden of controlling scaling vector F_i.

3.3.4 The framework of the HNTVPSO-RBSADE algorithm

Let NP denote the size of the swarm and BP = {pbest^k₁,…,pbest^k_NP} define the personal best experience set of particles at iteration k. The algorithmic scheme of HNTVPSO-RBSADE is illustrated in Table 1.

Table 1.
The algorithmic scheme of HNTVPSO-RBSADE

1. Randomly generate an initial swarm 2. Gain gbest and BP for the initial swarm 3. while not exit condition do 4. Evaluate and sort BP 5. for i = 1: NP do 6. Calculate selection probability p_i for pbest_i in BP by (18) and (19) 7. end for 8. for i = 1: NP do 9. Select three different individuals for pbest_i from BP by the roulette-wheel 10. Mutation crossover to generate v_i by (8) 11. Crossover operator to generate u_i by (9) 12. Selection operator to obtain better pbest_i by (10) 13. Update CR_i by (20) 14. Update F_i by (21)–(24) 15. Update velocity of particle i by (6) 16. Update position of particle i by (7) 17. Update w, c₁ and c₂ of particle i by (11)–(17) 18. end for 20. Update gbest and BP for the current swarm 21. end while

3.4 Convergence analysis of HNTVPSO-RBSADE

When designing a PSO algorithm, the convergence of the algorithm is of great importance [3, 29]. Since each dimension of the velocity and position vectors of each particle is updated independently from one another in (6) and (7), HNTVPSO-RBSADE can be simplified into a one-dimensional case in order to analyse its convergence. Without loss of generality, by omitting the subscript m in (6) and (7) for simplicity, the one-dimensional HNTVPSO-RBSADE can be rewritten into matrix form as follows:

[\begin{matrix} X (k + 1) \\ V (k + 1) \end{matrix}] = A [\begin{matrix} X (k) \\ V (k) \end{matrix}] + B P

(25)

where:

A = [\begin{matrix} 1 - φ & w \\ - φ & w \end{matrix}]

(26)

B = {[φ φ]}^{T}

(27)

φ_{1} = c_{1} r_{1}

(28)

φ_{2} = c_{2} r_{2}

(29)

φ = φ_{1} + φ_{2}

(30)

P = \frac{φ_{1} \cdot p b e s t + φ_{2} \cdot g b e s t}{φ_{1} + φ_{2}}

(31)

Solving |λE - A| = 0 where E is the identity matrix with the same size as A, the characteristic equation of the dynamic system (25) is derived as follows:

λ^{2} - (w + 1 - φ) \cdot λ + w = 0

(32)

where two roots, denoted as λ_1,2, are obtained as follows:

λ_{1,2} = \frac{1 + w - φ \pm \sqrt{{(1 + w - φ)}^{2} - 4 w}}{2}

(33)

In the context of dynamic system theory, the necessary and sufficient condition for the convergence of system (25) is that magnitudes of λ₁ and λ₂ should be less than 1 [30]. Thus, the system (25) converges, if and only if:

Max {| λ_{1} |, | λ_{2} |} < 1

(34)

Since it appears from (33) that λ₁ and λ₂ are two real or complex numbers, we will discuss two cases separately where λ_1,2 are two real and complex numbers in order to analyse the convergence of system (25).

The case where λ_1,2 are two complex numbers, denoted as λ_1,2 ∈ ℂ.

Lemma 1. For the system (25), λ_1,2 ∈ ℂ, if and only if:

{\begin{array}{l} w - 2 \sqrt{w} + 1 < φ < w + 2 \sqrt{w} + 1 \\ w \geq 0 \end{array}

(35)

Proof. For system (25), it is obvious that:

λ_{1,2} \in C \Leftrightarrow {(1 + w - φ)}^{2} - 4 w < 0

(36)

Solving the right-hand side of (36) using the classic approach, Lemma 1 can be easily proven. □

Now, let us find conditions on φ and w guaranteeing the convergence of system (25) in the case where λ_1,2 ∈ ℂ. It is trivial that the system converges if and only if Max{|λ₁|,|λ₂|}<1.

Lemma 2. In the case where λ_1,2 ∈ ℂ, the system (25) converges, if and only if:

{\begin{array}{l} w - 2 \sqrt{w} + 1 < φ < w + 2 \sqrt{w} + 1 \\ 0 \leq w < 1 \end{array}

(37)

Proof. Note that the magnitude of a complex number Z can be calculated as |Z| = √Z²_r + Z²_c, where Z_r and Z_c denote the real and imaginary parts of Z. Thus, for λ_1,2 ∈ ℂ, it is clear that:

\begin{array}{l} Max {| λ_{1} |, | λ_{2} |} = | λ_{1} | = | λ_{2} | = \sqrt{w} \end{array}

(38)

Therefore:

Max {| λ_{1} |, | λ_{2} |} < 1 \Leftrightarrow \sqrt{w} < 1

(39)

In the case where λ_1,2 ∈ ℂ, according to Lemma 1, (35) must be satisfied. Hence, when considering the conditions λ_1,2 ∈ ℂ and Max{|λ₁|,|λ₂|}<1, for λ_1,2 ∈ ℂ, the system (25) converges, if and only if:

{\begin{array}{l} w - 2 \sqrt{w} + 1 < φ < w + 2 \sqrt{w} + 1 \\ 0 \leq w < 1 \end{array}

(40)

Fig. 3 shows the convergent region of the system (25), i.e., HNTVPSO-RBSADE, in the case where λ_1,2 ∈ ℂ.

Figure 3.

Convergent region of HNTVPSO-RBSADE in the case where λ_1,2 ∈ ℂ

The case where λ₁ and λ₂ are two real numbers, denoted as λ_1,2 ∈ ℝ.

Lemma 3. For the system (25), λ_1,2 ∈ ℝ, if and only if:

{\begin{array}{l} φ \in R, w < 0 \\ φ \leq w - 2 \sqrt{w} + 1 or φ \geq w + 2 \sqrt{w} + 1, w \geq 0 \end{array}

(41)

Proof. For system (25), it is clear that:

λ_{1,2} \in R \Leftrightarrow {(1 + w - φ)}^{2} - 4 w \geq 0

(42)

Solving the right-hand side of (42) using the classic approach, Lemma 3 can be easily proven. □

Now, let us find conditions on φ and w guaranteeing the convergence of the system (25) in the case where λ_1,2 ∈ ℝ. According to (33) and (34), in the case where λ_1,2 ∈ ℝ, Max{|λ₁|, |λ₂|}<1 holds, if and only if:

- 1 < \frac{1 + w - φ \pm \sqrt{{(1 + w - φ)}^{2} - 4 w}}{2} < 1

(43)

Hence:

- 3 - w + φ < \pm \sqrt{{(1 + w - φ)}^{2} - 4 w} < 1 - w + φ

(44)

As λ_1,2 ∈ ℝ, it is clear that:

(44) \Leftrightarrow {\begin{array}{l} - 3 - w + φ < - \sqrt{{(1 + w - φ)}^{2} - 4 w} \\ \sqrt{{(1 + w - φ)}^{2} - 4 w} < 1 - w + φ \end{array}

(45)

Solving the right-hand inequalities in (45), yields:

(44) \Leftrightarrow {\begin{array}{l} 2 w + 2 - φ > 0 \\ φ > 0 \end{array}

(46)

According to Lemma 3, (41) must be satisfied in the case where λ_1,2 ∈ ℝ. Considering both the conditions that λ_1,2 ∈ ℝ and Max{|λ₁|, |λ₂|}<1, in the case where λ_1,2 ∈ ℝ, the system (25) converges, if and only if:

{\begin{array}{l} 0 < φ < 2 w + 2, - 1 < w < 0 \\ 0 < φ \leq w - 2 \sqrt{w} + 1 or w + 2 \sqrt{w} + 1 \leq φ < 2 w + 2, 0 \leq w < 1 \end{array}

(47)

Considering both cases where λ_1,2 ∈ ℂ and λ_1,2 ∈ ℂ together, the system (25), i.e., HNTVPSO-RBSADE, converges, if and only if:

{\begin{array}{l} 0 < φ < 2 w + 2 \\ - 1 < w < 1 \end{array}

(48)

Fig. 4 shows the convergent region of HNVPSO-RBSADE in both cases where λ_1,2 ∈ ℝ and λ_1,2 ∈ ℂ, which is a triangle area. Only if a parameter selection of w and φ is located in this area does HNTVPSO-RBSADE converge. Fig. 5 illustrates the 3-D representation of the value of Max{|λ₁|,|λ₂|}.

Figure 4.

Convergent region of HNTVPSO-RBSADE

Now, let us find the equilibrium point of HNTVPSO-RBSADE. Calculating limits on both sides of (25) yields the following:

{\begin{array}{l} \lim_{k \to \infty} X (k + 1) = w \lim_{k \to \infty} V (k) + φ \lim_{k \to \infty} (P - X (k)) \\ \lim_{k \to \infty} V (k + 1) = \lim_{k \to \infty} X (k) + \lim_{k \to \infty} V (k) \end{array}

(49)

When HNTVPSO-RBSADE converges, $\lim_{k \to \infty} X (k + 1) = \lim_{k \to \infty} X (k)$ and $\lim_{k \to \infty} V (k + 1) = \lim_{k \to \infty} V (k)$ . Therefore, substituting these two equations into (49) yields:

{\begin{array}{l} \lim_{k \to \infty} X (k) = P = \frac{φ_{1} \cdot p b e s t + φ_{2} \cdot g b e s t}{φ_{1} + φ_{2}} \\ \lim_{k \to \infty} V (k) = 0 \end{array}

(50)

where φ = φ₁ + φ₂, φ₁ = c₁r₁ and φ₂ = c₂r₂. pbest denotes the personal best position of the particle and gbest represents the global best position of the swarm.

Figure 5.

3-D representation of the value of Max{|λ₁|, |λ₂|}

3.5 Convergence behaviour of particles in HNTVPSO-RBSADE

Prior to particles converging to the equilibrium point given in (50), they may oscillate in different ways around the equilibrium point as a result of the different values of w and φ. Since different convergence oscillations may influence the quality of the final solution found by particles [29], it is necessary to investigate the different convergence oscillations of particles. Four typical oscillations of particles in HNTVPSO-RBSADE are shown in Fig. 6.

Non-oscillatory behaviour, as shown in Fig. 6(a), leads particles to only search on one side of the equilibrium point, which will be useful when the search space is bounded. Particles exhibit non-oscillatory convergence behaviour when λ₁ and λ₂ are two real roots and at least one of them is positive, which is equivalent to 0⩽(1 + w - φ)²-4w and 0 < 1 + w - φ. Harmonic oscillation behaviour, as shown in Fig. 6(b), may be beneficial for the exploitation stage, since particles smoothly oscillate around the equilibrium point. Harmonic oscillation behaviour occurs when two roots, λ₁ and λ₂ are complex, that is, (1 + w - φ)²-4w < 0. Zigzagging convergence, as shown in Fig. 6(c), may also facilitate exploitation as particles zigzag around the equilibrium point, which may be useful when the search space is rugged. Particles exhibit zigzagging convergence behaviour when at least one of λ₁ and λ₂ has a negative real part, i.e., w < 0 or 1 + w - φ < 0. The combined harmonic with zigzagging behaviour, as shown in Fig. 6(d), can be beneficial for the transition from exploration to exploitation, due to its mixed nature, which emerges when at least one of the two complex roots λ₁ and λ₂ has a negative real part, i.e., (1 + w - φ)² - 4w < 0 ∩ w < 0 ∪ (1 + w - φ)² - 4w < 0 ∩ 1 + w - φ < 0.

If the boundaries of coefficients associated with these oscillations are known beforehand, one may easily design an adaptive method to change the values of these coefficients, so that the convergence of PSO can be guaranteed and the quality of the final solution searched by particles can be improved.

Figure 6.

Convergence behaviour of particles in HNTVPSO-RBSADE

3.6 Convergence of HNTVPSO-RBSADE without considering its stochastic nature

Due to the stochastic nature of HNTVPSO-RBSADE it is difficult to rigorously establish the exact relationship between its stochastic nature and its convergence property. Thus it is necessary to first analyse the convergence of HNTVPSO-RBSADE without considering its stochastic nature Note that the stochastic nature of HNTVPSO-RBSADE is attributed to the existence of the two random numbers r₁ and r₂.

Lemma 4 Without considering its stochastic nature HNTVPSO-RBSADE converges only if:

{\begin{array}{l} 2 w + 2 > c_{1} + c_{2} \\ - 1 < w < 1 \\ c_{1}, c_{2} > 0 \end{array}

(51)

Proof Since φ = φ₁ + φ₂ = c₁r₁ + c₂r₂ the necessary and sufficient condition given by (48) can be rewritten as:

{\begin{array}{l} 0 < c_{1} r_{1} + c_{2} r_{2} < 2 w + 2 \\ - 1 < w < 1 \end{array}

(52)

Since c₁ and c₂ are two positive parameters, and r₁ and r₂ are two random numbers uniformly distributed in [0,1], we have c₁ ⩾ c₁r₁ and c₂ ⩾ c₂r₂. Therefore:

{\begin{array}{l} 2 w + 2 > c_{1} + c_{2} \\ - 1 < w < 1 \\ c_{1}, c_{2} > 0 \end{array} \Rightarrow {\begin{array}{l} 0 < r_{1} c_{1} + r_{2} c_{2} < 2 w + 2 \\ - 1 < w < 1 \end{array}

(53)

Since the right-hand side inequality in (53) is the necessary and sufficient condition for the convergence of HNTVPSO-RBSADE, it is trivial that Lemma 4 holds. □

3.7 The parameter selection principle of HNTVPSO-RBSADE

After analytically investigating the convergence of HNTVPSO-RBSADE, we still need to discover how to set the initial and final values of w, c₁ and c₂ to guarantee the convergence of HNTVPSO-RBSADE. In the following lemma, an alternative parameter selection principle for how to set the initial and final values of w, c₁ and c₂ to guarantee the convergence of HNTVPSO-RBSADE is provided.

Figure 7.

Convergent position and velocity trajectories of the particle in HNTVPSO-RBSADE under the suggested parameter selection

Lemma 5. The HNTVPSO-RBSADE algorithm converges only if the initial and final values of its three control parameters satisfy the following:

{\begin{array}{l} 2 w_{m i n} + 2 > c_{1 s} + c_{1 f} \\ 1 > w_{m a x} > w_{m i n} > - 1 \\ c_{1 s} = c_{2 f} > c_{1 f} = c_{2 s} > 0 \end{array}

(54)

Proof. When c_1s = c_2f and c_1f = c_2s, it appears from (12), (13), (15) and (16) that c₁ + c₂ = c_1s + c_1f for any particle at any iteration in HNTVPSO-RBSADE. From (11) and (13), it is clear that w_m ⩽ w ⩽ w_max, c_1f ⩽ c₁ ⩽ c_1s and c_2s ⩽ c₂ ⩽ c_2f for any particle at any iteration in HNTVPSO-RBSADE. Therefore:

{\begin{array}{l} 2 w_{m i n} + 2 > c_{1 s} + c_{1 f} \\ 1 > w_{m a x} > w_{m i n} > - 1 \\ c_{1 s} = c_{2 f} > c_{1 f} = c_{2 s} > 0 \end{array} \Rightarrow {\begin{array}{l} 2 w + 2 > c_{1} + c_{2} \\ - 1 < w < 1 \\ c_{1}, c_{2} > 0 \end{array}

(55)

The right-hand side inequality in (55) is the sufficient condition for the convergence of HNTVPSO-RBSADE, which is proved in Lemma 4. This completes the proof for Lemma 5. □

Since w_max, w_min, c_1s, c_1f, c_2s and c_2f are predefined parameters, the convergent condition given by (54) can be easily satisfied by setting proper values of these parameters. Fig. 7 shows the convergent position and velocity trajectories of the particle in HNTVPSO-RBSADE under the suggested parameter selection: w_max = 0.9, w_min = 0.4, c_1s = c_2f = 2 and c_1f = c_2s = 0.1.

4 Apply HNTVPSO-RBSADE to Solve Global Path Planning

The algorithmic scheme of applying HNTVPSO-RBSADE to solve mobile robot global path planning is illustrated in Table 2. Note that the evolution will not exit until the iteration number reaches the maximum iteration number. In Table 2, BP = {pbest^k₁,…,pbest^k_NP} denotes the personal best experience set of particles at iteration k.

Table 2.
The HNTVPSO-RBSADE-based framework for global path planning

Randomly generate an initial swarm

Update gbest for the initial swarm

Update BP for the initial swarm

while not exit condition do

Evaluate and sort BP by the feasibility-based rule

Calculate selection probability for each individual in BP by (18) and (19)

for m = 1: NP do

Select three different individuals for pbest_m from BP

Mutation crossover to generate v_m by (8)

Crossover operator to generate u_m by (9)

Selection operator to get better pbest_m by (10)

Update CR_m by (20)

Update F_m by (21)–(24)

Update velocity vector of particle m by (6)

Update position vector of particle m by (7)

Modify position vector of particle m by (4)

Calculate fitness value of particle m by (1)–(3)

Calculate constraint violation of particle m by (5)

Update w, c₁ and c₂ of particle m by (11)–(17)

end for

Update gbest and BP for the current swarm

end while

Output gbest to navigate the robot

5 Simulations and Analysis

In order to validate the proposed method, it is compared with JADE [35], TVPSO [15], GS [18] and mGA [25]. The simulation parameters for each method are shown in Table 3. To fully investigate the performance of the proposed method, four numerical simulations and a Monte-Carlo experiment with 50 independent runs are conducted. In each simulation, the optimal path of each method is obtained after 200 iterations of 40 particles using MATLAB 2012B software on a Windows 8 personal computer with i3-2350@2.30GHz and 2GB RAM. For rigorous comparison, the path optimality and the computation time of each method are examined and compared. Path optimality is measured by the fitness value of the optimal path. Note that this paper focuses on the numerical value of the path fitness, which is calculated by J_L + 1/J_S, as given in (1), where J_L and J_S denote the path length and path safety.

Table 3.
The simulation parameters for each method

Method Simulation parameters

Proposed w_max = 0.9 w_min = 0.4 c_1s = c_2f = 2 c_1f = c_2s = 0.1

TVPSO [15] w_max = 0.7 w_min = 0.4 c_1s = 5c_1f = 2.5 c_2f = 5c_2s = 2.5

GS [18] c₁ = c₂ = 0.5 c_max = 5 c_min = 1

mGA [25] cr = 0.5

JADE [35] c₁ = 0.1

Method	Simulation parameters
Proposed	w_max = 0.9	w_min = 0.4	c_1s = c_2f = 2	c_1f = c_2s = 0.1
TVPSO [15]	w_max = 0.7	w_min = 0.4	c_1s = 5c_1f = 2.5	c_2f = 5c_2s = 2.5
GS [18]	c₁ = c₂ = 0.5	c_max = 5	c_min = 1
mGA [25]	cr = 0.5
JADE [35]	c₁ = 0.1

5.1 Numerical simulations

This subsection shows four numerical simulations that are all executed in a 100m x 100m workspace. From the first simulation to the last, there are, respectively, 8, 5, 17 and 11 obstacles in the workspace. Line st - ta is equally divided into 8, 12, 12 and 13 subsections from the first simulation to the last. The obtained paths of the five methods for the four simulations are demonstrated in Fig. 8. Fig. 9 displays the evolution curves of the five methods for the four simulations. The simulation results of the five methods for the four simulations are shown in Tables 4–7.

From Fig. 8, it is clear that each method is efficient at finding an obstacle-free path in each simulation. From Table 4 through to Table 7, it can be seen that Proposed method ≻ JADE ≻ GS ≻ mGA ≻ TVPSO in terms of path optimality and TVPSO ≻ Proposed method ≻ mGA ≻ GS ≻ JADE with respect to computation time. Here, “≻” denotes “dominate” or “outperform”. Although TVPSO is the fastest algorithm, it exhibits the worst performance at finding an optimal path. Though the proposed method is the second fastest algorithm, it is the best one at finding an optimal path. It is worth noting that the difference in computation time between TVPSO and the proposed method is around 2s in each simulation. Considering all of the concerns raised, it can be concluded that the proposed method performs superior to the other four methods in terms of establishing path optimality. Furthermore, the computation time of the proposed method is comparable with those of the other four methods.

From Table 4 through to Table 7, it is also interesting to note that the computation time of each method changes significantly from the first simulation to the last. For example, the computation time of the proposed method varies from 24.59s, 35.44s, 79.33s to 72.25s from the first simulation to the last. This is because the number of obstacles and the number of subsections of line st - ta are different in each simulation. Based on the computation time of a specific method from the first simulation to the last, as shown in Tables 4–7, it is found that when the workspace contains more obstacles and st - ta is divided into more subsections, the path planner will take a longer time to generate an efficient path. This is because when the workspace contains more obstacles and line st - ta is divided into more subsections, the complexity of the workspace and the number of waypoints along a candidate path are increased. Thus, the path planner will take longer to calculate the cost and the constraint violation degree of a candidate path, in addition to updating the position information of waypoints of a candidate path.

Table 4.
Simulation results for the first numerical simulation

Method Optimal path length (m) Optimal path safety (m) Optimal path fitness Computation time (s)

TVPSO 129.42 8.73 129.53 22.72

mGA 129.37 9.10 129.49 26.11

GS 127.10 11.47 127.18 28.02

JADE 125.27 10.81 125.36 30.12

Proposed 121.97 10.57 122.07 24.59

Method	Optimal path length (m)	Optimal path safety (m)	Optimal path fitness	Computation time (s)
TVPSO	129.42	8.73	129.53	22.72
mGA	129.37	9.10	129.49	26.11
GS	127.10	11.47	127.18	28.02
JADE	125.27	10.81	125.36	30.12
Proposed	121.97	10.57	122.07	24.59

Table 5.

Simulation results for the second numerical simulation

Method	Optimal path length (m)	Optimal path safety (m)	Optimal path fitness	Computation time (s)
TVPSO	141.80	23.06	141.84	34.50
mGA	129.85	23.17	129.89	36.46
GS	127.46	21.27	127.51	38.55
JADE	125.68	20.86	125.73	40.41
Proposed	122.09	22.56	122.14	35.44

From Fig. 9, it can be observed that the cost curves of some methods for some numerical simulations initially rise in the early part of the evolution. This happens because, in this paper, the feasibility-based rule [7, 27] is used to evaluate and select the elite path between any two candidate paths. Since the initial swarm of each method is randomly generated, the initial global best path of a method may collide with some obstacles, which implies that the initial global best path of the method is not feasible. In this case, with the evolution continuing, if any particle in the method searches for a new solution that has a smaller constraint violation degree but a larger path fitness value than those of the initial global best path, the initial global best path will be replaced by the newly-found solution, based on the feasibility-based rule. Therefore, in this case, the cost curve of the method will initially rise in the early phase of the evolution. However, with the evolution continuing, the cost curves of all methods will either keep dropping or will remain unchanged in the late phase of the evolution, as shown in Fig. 9. This is because each method can search for a feasible global best path in the late phase of the evolution. The feasible global best path can only be replaced by feasible solutions that have smaller fitness values than those of the feasible global best path, according to the feasibility-based rule.

Figure 8.

Optimal paths of all methods for the four numerical simulations

Table 6.

Simulation results for the third numerical simulation

Method	Optimal path length (m)	Optimal path safety (m)	Optimal path fitness	Computation time (s)
TVPSO	143.07	21.04	143.12	77.35
mGA	139.44	17.92	139.49	81.24
GS	124.25	17.94	124.31	82.78
JADE	122.09	20.66	122.14	84.34
Proposed	118.61	15.58	118.68	79.73

Table 7.

Simulation results for the fourth numerical simulation

Method	Optimal path length (m)	Optimal path safety (m)	Optimal path fitness	Computation time (s)
TVPSO	137.98	17.08	138.03	71.23
mGA	131.56	15.50	131.63	74.50
GS	117.36	22.98	117.40	76.36
JADE	116.75	20.06	116.80	79.14
Proposed	113.91	17.75	113.97	72.25

5.2 Monte-Carlo experiment

A Monte-Carlo experiment with 50 independent runs is carried out to further study the performance of the proposed method in this subsection. In each run of the Monte-Carlo experiment, the workspace is a 100mx100m area that contains 18 obstacles. Each obstacle has four vertexes that are randomly and uniformly distributed in the workspace. Line st - ta is equally divided into 15 subsections in each run of the Monte-Carlo experiment. After performing 50 independent runs, the statistical results, with respect to the fitness value of the optimal path and the computation time of each method, are reported see Table 8 and Table 9. The results corresponding to the statistical results shown in Table 8 and Table 9 are visualized in Fig. 10.

Figure 9.

Evolution curves of all methods for the four numerical simulations

From Table 8, it is clear that Proposed method ≻ JADE ≻ GS ≻ mGA ≻ TVPSO in terms of the best, worst and average fitness value of the optimal path. Compared with TVPSO, the proposed method improves 9.75% on the average fitness value of the optimal path. From Table 9, it is obvious that TVPSO ≻ Proposed method ≻ mGA ≻ GS ≻ JADE in terms of the best, worst and average computation time. Compared to the proposed method, TVPSO improves 1.38% on the average computation time. However, despite the best performance of TVPSO concerning computation time, TVPSO has the worst performance in terms of path optimality. Although the proposed method ranks second with respect to computation time, it is the most efficient for producing optimal path. Since the difference in average computation time between the proposed method and TVPSO is less than 2s in the Monte-Carlo experiment, it can be concluded that the proposed method generally outperforms the other four methods in the context of finding the optimal path. In addition, the computation time of the proposed method is comparable with those of the other methods compared.

Table 8.

Statistical results of the fitness value for the optimal paths by different methods in the Monte-Carlo experiment

	Proposed	JADE	GS	mGA	TVPSO
Best	121.63	126.60	127.71	132.54	137.78
Wost	136.25	141.64	143.77	145.66	147.87
Average	128.86	134.35	135.85	139.33	142.78
Std.Dev.	4.3630	4.5799	4.7780	4.5306	3.2588

Table 9.

Statistical results of computation time by different methods in the Monte-Carlo experiment

	TVPSO	Proposed	mGA	GS	JADE
Best	102.31	104.09	106.46	107.24	109.28
Wost	105.34	106.10	109.28	110.56	112.30
Average	103.72	105.17	107.79	108.75	110.71
Std.Dev.	0.8610	0.5897	0.7786	0.9736	0.8851

Figure 10.

Simulation results for the fitness value of the optimal paths and the computation time of different methods in the Monte-Carlo experiment

6 Conclusion and Future Work

In this study, a hybrid PSO algorithm called HNTVPSO-RBSADE, which combines NTVPSO with RBSADE, is proposed to solve mobile robot global path planning. In the proposed algorithm, particles first follow the moving rules defined in NTVPSO to update their velocities and positions. Then, the RBSADE algorithm is developed to evolve the personal best positions of particles in order to avoid particles becoming stagnant. By fine-tuning the three control parameters, the exploration and exploitation capabilities of NTVPSO can be well-balanced. Consequently, NTVPSO promotes particles to search for high-quality paths. In order to enhance the performance and easily adjust the control parameters of RBSADE, a rank-based mutation operator and a self-adaptive strategy are developed in RBSADE. Since the convergence of HNTVPSO-RBSADE remains important, this paper first analytically investigates the convergence of HNTVPSO-RBSADE through standard results yielded by dynamic system theory. Then, a parameter selection principle is proposed to guarantee the convergence of HNTVPSO-RBSADE.

The proposed algorithm is tested using four numerical simulations and a Monte-Carlo experiment with multiple runs against four evolutionary algorithms. The simulation results reveal that the proposed algorithm outperforms the other four algorithms in terms of path optimality; furthermore, the computation time of the proposed algorithm is comparable with those of the other algorithms compared.

There are some issues that deserve future study. The first is how to theoretically analyse the optimality of the equilibrium point of HNTVPSO-RBSADE. Since the three control parameters also influence the convergence speed of the PSO algorithm, the second issue concerns the analysis of the sensitivity of the convergence speed of the proposed PSO algorithm to the three control parameters. Furthermore, since there does not exist a widely-accepted criterion for selecting an optimum number of waypoints along a candidate path [35], our work has to predefine the number of subsections that line st - ta is divided into, which remains problem-dependent. Thus, developing a strategy that can autonomously choose the number of dividing subsections for line st - ta can be considered as a future study. In order to generate a higher quality global path, more performance criteria, such as path length, path safety and the path smoothness must be considered when addressing the path planning problem in future research. Moreover, for further verifying the proposed method, we are considering comparing the proposed method with other non-evolutionary methods under more complex environments in the near future. Finally, we are also considering the possibility of extending the proposed method into 3-D path planning, since such an approach is more practical for real-world applications.

Footnotes

Acknowledgements

The authors express their sincere and heartfelt thanks to the editor and reviewers for their constructive suggestions to improve the quality of this paper. This work is financially supported by the Chinese National Science Foundation under Grant No.11472213. The authors declare that we have no conflicts of interest regarding this work.

References

Ahmed

Faez

Deb

Kalyanmoy

. Multi-objective optimal path planning using elitist non-dominated sorting genetic algorithms. Soft Computing, 17(7): 1283–1299, 2012.

Akbari

Reza

Ziarati

Koorush

. A rank based particle swarm optimization algorithm with dynamic adaptation. Journal of Computational and Applied Mathematics, 235(8):2694–2714, 2011.

Bonyadi

Mohammad Reza

Michalewicz

Zbigniew

. A locally convergent rotationally invariant particle swarm optimization algorithm. Swarm Intelligence, 8(3):159–198, 2014.

Das

Swagatam

Suganthan

Ponnuthurai Nagaratnam

. Differential evolution: A survey of the state-of-the-art. IEEE Transactions on Evolutionary Computation, 15(1):4–31, 2011.

Davoodi

Mansoor

Panahi

Fatemeh

Mohades

Ali

Hashemi

Seyed Naser

. Multi-objective path planning in discrete space. Applied Soft Computing Journal, 13(1):709–720, 2013.

Davoodi

Mansoor

Panahi

Fatemeh

Mohades

Ali

Hashemi

Seyed Naser

. Clear and smooth path planning. Applied Soft Computing, 32:568–579, 2015.

Deb

Kalyanmoy

Pratap

Amrit

Agarwal

Sameer

Meyarivan

, A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182–197, 2002.

Coelho

Leandro dos Santos

Bora

Teodoro Cardoso

Mariani

Viviana Cocco

. Differential evolution based on truncated L{é}vy-type flights and population diversity measure to solve economic load dispatch problems. International Journal of Electrical Power {&} Energy Systems, 57(0):178–188, 2014.

Duan

Haibin

Huang

Linzhi

. Imperialist competitive algorithm optimized artificial neural networks for UCAV global path planning. Neurocomputing, 125:166–171, 2014.

10.

Eberhart

Kennedy

, A new optimizer using particle swarm theory. MHS'95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, pages 39–43, 1995.

11.

Epitropakis

M G

Plagianakos

V P

Vrahatis

M N

. Evolving cognitive and social experience in Particle Swarm Optimization through Differential Evolution: A hybrid approach. Information Sciences, 216:50–92, 2012.

12.

Geng

Gong

D W

Zhang

. PSO-Based Robot Path Planning for Multisurvivor Rescue in Limited Survival Time. Mathematical Problems in Engineering, 2014(2014), 2014.

13.

Gong

Dun-Wei

Zhang

Jian-Hua

Zhang

Yong

. Multi-objective Particle Swarm Optimization for Robot Path Planning in Environment with Danger Sources. Journal of Computers, 6(8):1554–1561, 2011.

14.

Kala

Rahul

. Multi-robot path planning using co-evolutionary genetic programming. Expert Systems with Applications, 39(3):3817–3831, 2012.

15.

Khalili-Damghani

Kaveh

Abtahi

Amir-Reza

Tavana

Madjid

. A new multi-objective particle swarm optimization method for solving reliability redundancy allocation problems. Reliability Engineering & System Safety, 111:58–75, 2013.

16.

Liu

Hui

Cai

Zixing

Wang

Yong

. Hybridizing particle swarm optimization with differential evolution for constrained numerical and engineering optimization. Applied Soft Computing Journal, 10(2):629–640, 2010.

17.

Liu

Xinying

Wang

Shuhong

Qiu

Jie

Zhu

Jian Guo

Guo

Youguang

Lin

Zhi Wei

. Robust optimization in HTS cable based on design for six sigma. IEEE Transactions on Magnetics, 44(6):978–981, 2008.

18.

Pei

Duan

HaiBin

. Path planning of unmanned aerial vehicle based on improved gravitational search algorithm. Science China Technological Sciences, 55(10):2712–2719, 2012.

19.

Hongwei

Lifang

. Research of biogeography particle swarm optimization for robot path planning. Neurocomputing, 148:91–99, 2015.

20.

Neri

Ferrante

Tirronen

Ville

. Recent advances in differential evolution: A survey and experimental analysis, volume 33. 2010.

21.

Hong

Xing

Alexander

Takacs

. An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots. Neurocomputing, 120:509–517, 2013.

22.

Ratnaweera

Asanga

Halgamuge

Saman K.

Watson

Harry C.

, Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients. IEEE Transactions on Evolutionary Computation, 8(3):240–255, 2004.

23.

Salman

Ayed

Engelbrecht

Andries P.

Omran

Mahamed G H

. Empirical analysis of self-adaptive differential evolution. European Journal of Operational Research, 183(2):785–804, 2007.

24.

Sarkar

Soham

Das

Swagatam

. A hybrid particle swarm with differential evolution operator approach (DEPSO) for linear array synthesis. Swarm, Evolutionary, and Memetic Computing, pages 416–423, 2010.

25.

Shiltagh

Nadia Adnan

Jalal

Lana Dalawr

. Path Planning of Intelligent Mobile Robot Using Modified Genetic Algorithm. International Journal of Soft Computing and Engineering, 3(2):31–36, 2013.

26.

Shi

Yuhui

Eberhart

Russell C.

, Parameter Selection in Particle Swarm Optimization. Evolutionary Programming VII SE - 57, 1447:591–600, 1998.

27.

Sun

Chao-Li

Zeng

Jian-Chao

Pan

Jeng-Shyang

. A modified particle swarm optimization with feasibility-based rules for mixed-variable optimization problems. International Journal of Innovative Computing, Information and Control, 7(6):3081–3096, 2011.

28.

Tavares

R.S.

Martins

T.C.

Tsuzuki

M.S.G.

, Simulated annealing with adaptive neighborhood: A case study in off-line robot path planning. Expert Systems with Applications, 38(4):2951–2965, 2011.

29.

Trelea

I. C.

The particle swarm optimization algorithm: Convergence analysis and parameter selection. Inform Process Lett;, 85:317–325, 2003.

30.

Van Den Bergh

Engelbrecht

Andries P.

, A study of particle swarm optimization particle trajectories. Information Sciences, 176(8):937–971, 2006.

31.

Wang

Hui

Rahnamayan

Shahryar

Sun

Hui

Omran

Mahamed G H

. Gaussian Bare-Bones Differential Evolution. IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics: A publication of the IEEE Systems, Man, and Cybernetics Society, 43(2):634–647, 2012.

32.

Wang

Xueyuan

Zhang

Gexiang

Zhao

Junbo

Rong

Haina

Ipate

Florentin

Lefticaru

Raluca

. A Modified Membrane-Inspired Algorithm Based on Particle Swarm Optimization for Mobile Robot Path Planning. International Journal of Computers Communications & Control, 10(5):732–746, 2015.

33.

Xin

Bin

Chen

Jie

Zhang

Juan

Fang

Hao

Peng

Zhi Hong

. Hybridizing differential evolution and particle swarm optimization to design powerful optimizers: A review and taxonomy. IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews, 42(5):744–767, 2012.

34.

Rui

Venayagamoorthy

Ganesh K.

Wunsch

Donald C.

, Modeling of gene regulatory networks with hybrid differential evolution and particle swarm optimization. Neural Networks, 20(8):917–927, 2007.

35.

Yang

Peng

Tang

Lozano

Jose A

. Path Planning for Single Unmanned Aerial Vehicle by Separately Evolving Waypoints. IEEE Transactions on Robotics, 31(5):1130–1146, 2015.

36.

Zhang

Yong

Gong

Dun-Wei

Zhang

Jian-Hua

. Robot path planning in uncertain environment using multi-objective particle swarm optimization. Neurocomputing, 103:172–185, 2013.

37.

Zhu

Weiren

Duan

Haibin

. Chaotic predator-prey biogeography-based optimization approach for UCAV path planning. Aerospace Science and Technology, 32(1):153–161, 2014.

38.

Zhu

Tang

Yang

Fang

Jian-An

Zhang

Wenbing

. Adaptive population tuning scheme for differential evolution. Information Sciences, 223(2999):164–191, 2013.

39.

Zhu

Zexuan

Wang

Fangxiao

Shan

Sun

Yiwen

. Global Path Planning of Mobile Robots Using a Memetic Algorithm. International Journal of Systems Science, 46(11):1982–1993, 2015.

Hybridizing Particle Swarm Optimization and Differential Evolution for the Mobile Robot Global Path Planning

Abstract

Keywords

1 Introduction

2 Statement of the Path Planning Problem

2.1 Modelling of the workspace

3.1 Review of the basic PSO

3.3.1 Nonlinear time-varying PSO (NTVPSO)

3.3.3 Ranking-based self-adaptive DE (RBSADE)

Table 3. The simulation parameters for each method Method Simulation parameters Proposed w max = 0.9 w min = 0.4 c1s = c2f = 2 c1f = c2s = 0.1 TVPSO [15] w max = 0.7 w min = 0.4 c1s = 5c1f = 2.5 c2f = 5c2s = 2.5 GS [18] c1 = c2 = 0.5 c max = 5 c min = 1 mGA [25] cr = 0.5 JADE [35] c1 = 0.1

Footnotes

Acknowledgements

References