Sage Journals: Discover world-class research

Abstract

Robots are coming to help us in different harsh environments such as deep sea or coal mine. Waste landfill is the place like these with casualty risk, gas poisoning, and explosion hazards. It is reasonable to use robots to fulfill tasks like burying operation, transportation, and inspection. In these assignments, one important issue is to obtain appropriate paths for robots especially in some complex applications. In this context, a novel hybrid swarm intelligence algorithm, ant colony optimization enhanced by chaos-based particle swarm optimization, is proposed in this article to deal with the path planning problem for landfill inspection robots in Asahikawa, Japan. In chaos-based particle swarm optimization, Chebyshev chaotic sequence is used to generate the random factors for particle swarm optimization updating formula so as to effectively adjust particle swarm optimization parameters. This improved model is applied to optimize and determine the hyper parameters for ant colony optimization. In addition, an improved pheromone updating strategy which combines the global asynchronous feature and “Elitist Strategy” is employed in ant colony optimization in order to use global information more appropriately. Therefore, the iteration number of ant colony optimization invoked by chaos-based particle swarm optimization can be reduced reasonably so as to decrease the search time effectively. Comparative simulation experiments show that the chaos-based particle swarm optimization-ant colony optimization has a rapid search speed and can obtain solutions with similar qualities.

Keywords

Landfill robots path planning PSO ACO chaos pheromone iterations

Introduction

Waste management plays an import role in environmental protection, energy reuse, sustainable development, and people’s daily life. Landfill site is the crucial component in the waste management process with the functions of organizing, burying, or even cleaning and reusing the garbage. However, due to the fact that the kinds of waste are very complex and some of them may be harmful to people, landfills pose a serious threat to the staff working in them and the residents living near them.¹ Even worse, arisen from the chemical reactions of the waste burying underground, harmful gas would be generated and groundwater may be polluted. Therefore, pipes are constructed in many landfills to capture and analyze the gas. In our project, a real landfill in Asahikawa, Japan, is modeled as a traveling salesman problem (TSP) on the basis of actual situation: pipes distributed in the landfill and the robot with complicated sensors² needing to traverse them. This robot is required to deal with inspections by solving the TSP, then generating suitable paths. In the landfill, all the pipes and anchor points are in a wireless sensor network with terminals which support broadband signals and basic data transmission. Another matched terminal is also embedded in the robot. By this equipment, the robot is able to perceive the direction, distance, and location of the next point in TSP route. These would be the inputs for proportional–integral–derivative or neural network-based controllers. Then, the controller can generate the angle, velocity, and accelerated velocity for actuators. In this context, we introduce an improved ant colony optimization (ACO) to solve the TSP, enabling the robot to find the feasible route, travel around the landfill, and fulfill the task appropriately.

ACO^3,4 has shown excellent performance on several combinatorial optimization problems such as scheduling problem,^5
–7 assignment problem,⁸ network coding problem,⁹ and the path planning tasks for robots or unmanned aerial vehicles.¹⁰ The determination of parameters for ACO is an extremely important task which is closely correlated with the algorithm’s solving ability. Scholars all around the world carried out several research works on the parameter tuning issue for ACO. Gambardella and Dorigo adjusted the status transition parameter q ₀ (in ant colony system) according to the problem size¹¹; Favuzza et al. also regulated q ₀ by iteration number¹²; and Watanabe and Matsui tuned the search region by an adaptive swarm-size-adjustment method.¹³ In particular, some researchers try to employ particle swarm optimization (PSO)¹⁴ to optimize the parameters for ACO, and some achievements have been obtained.^15
–17 These improved ACOs can effectively deal with lots of practical problems represented by TSP and path planning tasks.¹⁸

In algorithms like ACO optimized by PSO,¹⁴ genetic algorithm (GA),¹⁹ or other swarm intelligence techniques,²⁰ due to the fact that ACO needs to be invoked by another algorithm many times, the search time is relatively long especially in some TSP instances with a large number of nodes. For a robot path planning problem, we often need a quick response and a shorter execution time. The inner mechanism of those approaches mentioned above^15
–17 are almost the same. In this method, ACO parameters are optimized by PSO and classical pheromone updating strategy is used. That is, the accumulation status of pheromone on the map regarding to each ACO parameter set would be cleared again and again in the evolutionary process of PSO. This may lead to the loss of global information and a long-time offline optimization. We try to use global information more sufficiently by introducing an improved pheromone updating strategy. That is recording the pheromone status on the map and reusing them during the optimization instead of clearing them. We call it “asynchronous strategy.” This method is also enhanced by “Elitist Strategy” which means emphasizing the influence of the best ant (the individual with the current shortest solution). In addition, the use of chaotic sequence can improve the performance of PSO random factors due to its randomness and ergodicity. This hybrid algorithm can significantly reduce the iteration number of ACO invoked by each particle in PSO, thereby shortening the algorithm’s running time.

This article is organized as follows. In the second section, related works such as path planning, TSP, ACO, and PSO are described briefly. The proposed hybrid chaos-based particle swarm optimization (CPSO)-ACO algorithm is elaborated in the third section. For details about the practical scenario, the landfill inspection task of a robot is illustrated in the fourth section. This task is solved by CPSO-ACO model. Comparative simulation experiments are carried out in the fifth section. The conclusion is given in the last section.

Related work

Path planning

Path planning is an important problem in robotics area. In this task, a safe and appropriate route should be obtained for the robots automatically. According to the actual needs of different tasks and specific robot situations,²¹ the planner should obtain a suitable path online or offline.

Generally, the bodies and transformations of robots would be modeled at first. The representation of robotic space is closely correlated with graph-based modeling and searching. Common geometric modeling strategies include grid method,²² visibility graph method,²³ and Voronoi diagram method.^24,25 Wybe Dijkstra,²⁶ A^*,²⁷ D^*,²⁸ and artificial potential field²⁹ methods are typical graph search algorithms.

Sampling-based methods can be regarded as the mainstream approaches which are widely utilized in many real-word motion planning applications.^30,31 Instead of constructing explicit configuration space, sampling-based algorithms design a number of samples and consider the collision detection as a black box, thereby determining the motion trails in grids or other geometric space.^22,24 Typical sampling-based methods include probabilistic road-map method (PRM)³² and rapidly-exploring random trees (RRTs).³³

Another group of methods are based on model and optimization.³⁴ Some of them utilized linear optimization or continuous optimization to generate the path, for example, convex optimization.³⁵ Others adopted heuristic algorithm to solve combinatorial optimization problems. Heuristic algorithm for combinatorial optimization is the main topic of this article.

Mostly, the heuristic computation methods use techniques arisen from artificial intelligence, such as machine learning algorithms³⁶ and evolutionary computation algorithms.¹⁹ Some popular intelligent computation algorithms such as GA¹⁹ and PSO¹⁴ are regarded as the most effective group of strategies for combinatorial optimization problems. These strategies can also effectively deal with lots of control tasks for robots such as their gestures and actions.³⁷ If we can transform the path planning task into some constrained optimization problems, those heuristic intelligence techniques can effectively solve the path planning issue. In this article, path planning problem is exactly converted into the typical NP-hard combinatorial optimization problem, TSP.

There are also case-based methods which try to generate the path by prior knowledge.³⁸ In this strategy, existing environment and route information should be collected as a “case library.” With this case library, the planners will match the current task to some existing tasks, then generate the new paths and combine or adjust them.³⁹

Traveling salesman problem

TSP is a classical problem in operational research and mathematical area. In this problem, a sale man needs to travel around a number of cities. All the cities should be traversed only one time. Each path between two points is defined clearly. An appropriate solution for this problem would be a traveling route, or in other words, a sequence of city serial numbers. Ideally, the best solution of TSP is the route with the minimum cost, normally the shortest sum-distance of the route. The major variants of TSP include asymmetric TSP and multiple traveling salesmen problem.

ACO is regarded as the most effective method for TSP.^11,40 In these years, with the significant development of deep learning techniques, some researchers try to use deep neural networks to deal with combinatorial optimization problems represented by TSP and they also obtain valuable achievements. However, since most neural networks-based strategies⁴¹ need the gradient to train models and most non-deterministic polynomial complete problem (NP) like TSP do not have mathematical expressions, these methods often have weak generalized performance. It is reasonable to believe that heuristic methods or the evolutionary computation methods are still the mainstream methods for combinatorial optimization.

ACO

Inspired by the foraging behavior of ants, ACO can excellently deal with lots of optimization tasks including TSP. During the search process for food source, ants can exchange information between each other by releasing the pheromone. Assuming that the amount of pheromone released by one ant is limited, the pheromone left on edge [i, j] is normally less in a long route and more in a short route. After a number of round trips, the colony of ants can intelligently choose those routes with more pheromone and higher fitness.

Take the basic model, ant system algorithm as an example, each artificial ant corresponds to one route, or a city sequence. Each city appears only one time in this sequence. At the beginning, we can initialize the ants randomly. During the evolutionary process, the ant k can determine its next city j from the current city i by the following formula

P_{i j}^{k} (t) = {\begin{array}{l} \frac{{[τ_{i j} (t)]}^{α} {[η_{i j} (t)]}^{β}}{\sum {[τ_{i s} (t)]}^{α} {[η_{i s} (t)]}^{β}}, j, s \in {allowed}_{k} \\ 0, otherwise \end{array}

where $P_{i j}^{k} (t)$ is the probability, t is the iteration number; $τ_{i j} (t)$ is the amount of pheromone on edge [i, j]; α and β are two hyper parameters which illustrate the importance of path quality and visibility; ${allowed}_{k}$ contains the cities which can be visited by ant k; and $η_{i j} (t)$ is heuristic factor as equation (2)

η_{i j} (t) = \frac{1}{d_{i j}}

where $d_{i j}$ is the distance or the cost of edge [i, j] and $τ_{i j}$ can be adjusted by the following equation

τ_{i j} (t + 1) = ρ τ_{i j} (t) + Δ τ_{i j} (t, t + 1)

where ρ is the evaporation coefficient. $Δ τ_{i j} (t, t + 1)$ can be calculated by the following equations

Δ τ_{i j} (t, t + 1) = \sum_{k = 1}^{K} τ_{i j}^{k} (t, t + 1)

τ_{i, j}^{k} (t, t + 1) = {\begin{array}{l} \frac{Q}{L_{k}}, if  ant k passed  through  edge [i, j] \\ 0, otherwise \end{array}

where Q is total amount of pheromone, L_k is total length of the tour (route) k, and K is the number of ants.

The total amount of pheromones, Q, is major related to the environment such as the number of cities and the total distance. It can be determined by experiments. The number of cities is also the major factor which affects K (AntCount). Based on the past experience, AntCount can be determined among 0.5 to 1.5 times the number of cities.

According to the formulas above, ant colony can update from one generation to another until they obtain the appropriate solution.

Based on ant system model, other improved modes represented by ant colony system⁴² and max-min ant system⁴³ are proposed, respectively. In these years, ACO is also widely applied in topology optimization for complex nets and track planning for unmanned aerial vehicles or robots. In ACO models, the determination of hyper parameters directly impacts their performances including intensification and diversification in the search process.

PSO

Similar to ACO, PSO is another useful bioinspired algorithm.¹⁴ This algorithm mainly imitates the behavior of birds. In this algorithm, the individuals (bird or particle) search the better solutions in local area. These particles need to cooperate and compete with each other so as to make sure the colony can move to the global optimal solution gradually.

In PSO, we can initialize the ith solution x_i as an N-dimensional set $x_{i} = (x_{i 1}, x_{i 2}, \dots, x_{i n})$ with N-dimensional velocity $v_{i} = (v_{i 1}, v_{i 2}, \dots, v_{i N})$ . The velocity can be updated as the following equation

\begin{array}{l} v_{i d} (t + 1) = ω v_{i d} (t) + c_{1} r_{1} (t) (p b e s t_{i d} - x_{i d} (t)) \\ + c_{2} r_{2} (t) (g b e s t_{d} - x_{i d} (t)) \end{array}

where $d = 1, 2, \dots, N$ , $i = 1, 2, \dots, M$ , M is the swarm size of particle, k is the iteration number, and $ω$ is inertia weight which illustrates the influence of $v_{i d} (t)$ to $v_{i d} (t + 1)$ and has a direct impact on search step size. PSO with a bigger $ω$ would have a bigger search range but a lower precision; a smaller $ω$ can produce higher search precision, but the optimization time would be prolonged. As analyzed by many researchers, the good scope of $ω$ is between 0.4 and 0.9. c ₁ is the weight regulating the movement of the particle close to its best position ( $p b e s t_{i d}$ ), and c ₂ is the weight regulating the movement of the particle close to the current best position ( $g b e s t_{d}$ ). Normally, c ₁ and c ₂ can be selected from [0, 2]. $r_{1} (k)$ and $r_{2} (k)$ are two random numbers among [0, 1].

When the velocity is determined, we can get the position of particle i as below

x_{i} (k + 1) = x (k) + v_{i} (k + 1)

After a number of iterations as mentioned above, this group of particles will be close to the global optimal solution.

Apart from function optimization, PSO is also regarded as one of the most effective parameter optimization methods for mainstream machine learning and evolutionary computation models such as support vector machine (SVM) and ACO.

Hybrid CPSO-ACO algorithm

Previous PSO-ACO algorithm

Generally speaking, the common PSO-ACO model for TSP can be summarized as Algorithm 1.

Algorithm 1.

PSO-ACO.

Input: Hyper parameters of PSO; Information of TSP nodes (Coordinate value, Latitude and longitude etc.).
Output: A sequence of TSP nodes; Length of TSP tour; Hyper parameters for ACO.
1: Initialize D-dimensional particles P_i and their velocity V_i (i=1,2,…, I, I is the number of particles) related with D parameters of ACO;

m = 0

; M, N are the maximum numbers of iterations in PSO and ACO respectively;
2: while

m < M

do
3: ACO is invoked by PSO,

i = 0

;
4: while

i < I

do
5:

n = 0

;
6: while

n < N

do
7: ACO deals with TSP as (1)-(5) with P_i ;
8:

n = n + 1

;
9: Clear the pheromones;
10: The achieved TSP result is used to evaluate P_i ;
11: Update the velocity of PSO, V_i , as (6);
12: Update the location of PSO, P_i , as (7);
13:

i = i + 1

;
14:

m = m + 1

;
15: return The optimal solution of TSP and the related P_i .

In Algorithm 1, time overhead for a complicated TSP which needs a certain number of ACO cycles would be very large. In this article, we try to reduce the algorithm running time based on the improvements as follows:

asynchronous pheromone updating strategy and

chaos-based PSO optimization.

Improved pheromones updating method: Global asynchronous method combined with “Elitist Strategy”

In previous PSO-ACO, pheromones in the TSP map will be cleared when particle P_i (also the parameter set for ACO) is changed into $P_{i + 1}$ . This is the reason why ACO optimization process needs a certain number of cycles so as to perceive comprehensive environmental information. It is reasonable to believe that the ACO cycles can be reduced in a limited number if pheromones can be maintained when the parameters are changed. In this article, we use an improved pheromone updating strategy: global asynchronous method combined with “Elitist Strategy.”⁴⁴

The asynchrony denotes that the pheromones could be kept stable instead of updating if the algorithm does not find a better solution as below equation

\begin{array}{l} τ_{i j} (t + 1) = {\begin{array}{l} ρ \times τ_{i j} (t) + Δ τ_{i j} (t, t + 1), \\ if  a  better  solution  is  obtained \\ τ_{i j} (t), otherwise \end{array} \end{array}

where $τ_{i j} (t, t + 1)$ can be computed as equations (4) and (5).

If the algorithm gets a solution with better fitness after n iterations, the pheromone updating formula can be written as

τ_{i j} (t + n) = ρ \times τ_{i j 1} (t) + τ_{i j} {(t)}^{*}

where $τ_{i j 1} (t)$ is the amount of pheromone accumulated as the basic updating style as equations (3) to (5). $τ_{i j} {(t)}^{*}$ is the extra increment from the “Elite Ant,” which is the globally best tour obtained by ants. This is the so-called “Elitist Strategy.” It can be calculated as below equation

τ_{i j}^{k} (t, t + 1) = {\begin{array}{l} \frac{Q}{G_{k}}, if  [i, j]  is  in the  best route \\ 0, otherwise \end{array}

where G_k is the length of the globally best tour (the shortest route).

The introduction of chaos

Generally, chaos refers to a random-like and unpredictable dynamic system which is constituted by a series of states. A chaotic variable normally has features as follows:

It is sensitive to the initial value.

The states are random and unpredictable.

The variable will experience all the states as certain patterns in a limited range.

The ergodicity and randomness of chaotic systems can help PSO to improve search performance and avoid local optimum. There are many chaotic PSO methods. The model in the work of Alatas et al.⁴⁵ initialized particles by chaotic sequences; Daneshyari⁴⁶ generated random factors in PSO; Liu et al.⁴⁷ utilized chaotic search for particles with high fitness in PSO. Among these methods, generating factors (such as the random number in equation (6)) are most common and simplest way.⁴⁸ Typical discrete chaotic maps include logistic map,⁴⁹ tent map,⁵⁰ Chebyshev map,⁵¹ and so on. Compared with logistic and tent maps with the distribution range from 0 to 1, Chebyshev map has a wider distribution, from −1 to 1. In this article, two Chebyshev chaotic sequences are employed to produce the random factors $r_{1} (t)$ and $r_{2} (t)$ .

The Chebyshev mapping model with degree n can be demonstrated as follows

T_{n} (x) = \cos (n * arc \cos x) (- 1 \leq x \leq 1)

Then, we can obtain the recurrent equations as below

T_{0} (x) = 1

T_{1} (x) = x

T_{2} (x) = 2 x^{2} - 1

T_{n + 1} (x) = 2 x T_{n} (x) - T_{n - 1} (x) (n \geq 2)

The new velocity updating formula can be written as follows

\begin{array}{l} v_{i d} (t + 1) = ω v_{i d} (t) + c_{1} | C h 1_{(t)} (x_{0}) | (p b e s t_{i d} - x_{i d} (t)) \\ + c_{2} | C h 2_{(t)} (y_{0}) | (g b e s t_{d} - x_{i d} (t)) \end{array}

where $C h 1_{(t)}$ and $C h 2_{(t)}$ are two values generated by Chebyshev chaotic sequences; x ₀ and y ₀ are two initial values for Chebyshev polynomials.

Hybrid CPSO-ACO model

The proposed hybrid CPSO-ACO algorithm can be illustrated as Algorithm 2.

Algorithm 2.

Hybrid CPSO-ACO.

Input: Hyper parameters of PSO; Information of TSP nodes (Coordinate value, Latitude and longitude etc.).
Output: A sequence of TSP nodes; Length of TSP tour.
1: Initialize D-dimensional particles P_i and their velocity V_i (i=1,2,…, I, I is the number of particles) related with D parameters of ACO;

m = 0

; M is the maximum number of iterations in PSO;
2: while

m < M

do
3: ACO is invoked by PSO,

i = 0

;
4: while

i < I

do
5:

n = 0

;
6: while

n < N

do
7: ACO solves TSP by asynchronous method;
8:

n = n + 1

;
9: The achieved TSP result is used to evaluate P_i ;
10: Update the velocity of PSO: V_i as (16);
11: Update the Location of PSO: P_i , as (7);
12:

i = i + 1

;
13:

m = m + 1

;
14: return The optimal solution of TSP.

Different from Algorithm 1, pheromones in the map are relatively stable in Algorithm 2. N is the number of cycles corresponding to a particular particle P_i and it can be reduced significantly with the improvements such as asynchronous pheromone updating strategy and chaotic random factors introduced in this section.

Experimental analysis on Ch150 problem

We carried out a group of experiments using PSO-ACO (algorithm (a), also Algorithm 1 in section “Previous PSO-ACO algorithm”), PSO-ACO with asynchronous updating method (algorithm (b)), and hybrid CPSO-ACO algorithm proposed in this article (algorithm (c), also Algorithm 2 in section “Hybrid CPSO-ACO model”) to evaluate the improvements in this article. All these three algorithms are utilized to deal with typical TSP instance, Ch150 problem from TSPLIB presented by Heidelberg University (Universitaet Heidelberg).⁵² Ch150 is symmetric Churritz TSP with 150 cities which are recorded as 150 coordinate points and measured by two-dimensional (2-D) Euclidean distance. The optimal solution on Ch150 is 6528 so far.

As analyzed in the second section, $ω$ = 0.5, c ₁ = 1.5, c ₂ = 1.3, ParticleCount = 30, AntCount = 75, Q = 2000, and M = 30. In algorithm (a), N = 50; in algorithms (b) and (c), N = 3. Our development environment is Visual Studio 2010 on a 32-bit windows 7 system. All the experiments are carried out on a PC with Intel core (TM) i5 CPU @ 2.4 GHz processor and 2 GB RAM. The experiments are repeated five times. Results are recorded in Table 1.

Table 1.

Statistical results on Ch150.

	Path length (m)			Running time (s)
	Average value	Optimal value	Standard deviation	Average value	Standard deviation
(a)	6974.4	6652	290.0	7013.0	240.6
(b)	7045.6	6690	628.9	860.0	27.4
(c)	6943.0	6652	589.2	900.4	45.5

As shown in Table 1, algorithms (a) and (c) obtained the same shortest route which is better than algorithm (b). Algorithm (c) has a better average route length but a weaker stability than algorithm (a). The running time of algorithms (b) and (c) is far less than algorithm (a). Compared with previous algorithms, the proposed CPSO-ACO model can improve the solution quality to some extent and reduce the running time significantly.

The optimal routes obtained by these three algorithms are demonstrated in Figures 1 to 3.

Figure 1.

The shortest route obtained by algorithm (a).

Figure 2.

The shortest route obtained by algorithm (b).

Figure 3.

The shortest route obtained by algorithm (c).

As shown in these figures, crossover situation appears in all the routes and algorithm (c) archived a better solution than algorithm (b).

Path planning for landfill inspection robots in Asahikawa, Japan

The proposed hybrid CPSO-ACO model is applied to deal with path planning task of landfill inspection robot in Asahikawa, Japan.^53,54 It should be mentioned that in this work, considering chassis height of the car-like robot and actual road conditions, we deal with the problem as an ideal TSP. The main constraint of CPSO-ACO is that the robot can only inspect each pipe just once during one optimization. In our future work, we will take more considerations on other constraints like terrain restrictions on special regions, time and energy consumption constraints, and so on.

This landfill is built on a hill with 109 gas pipes in order to release and deal with the harmful gases underground. For the purpose of detecting gas composition (some of them may be dangerous to human) in different regions, the robot needs to traverse all the pipes in the landfill by certain control strategies⁵⁵ designed appropriately. A lower cost is expected. That is, the length of robot route is the shorter the better. Details of this project and relative node information are recorded.^53,54 We got those three-dimensional (3-D) coordinate values from local documents and maps.

Traversing all the pipes is the major assignment of the robot. It has the same aim and role as the salesman in TSP. In addition, there is no obvious obstacle in the landfill for our robot since it is designed like a mobile vehicle with a higher chassis. Moreover, after leveling and compression, the path between two pipes is relatively smooth. This is the reason why our environment can be transformed into TSP. We just use the Euclid distance between every two nodes in the 3-D space at present. The calculation formula is written as below

D_{i j} = \sqrt{{(x_{i} - x_{j})}^{2} + {(y_{i} - y_{j})}^{2} + {(z_{i} - z_{j})}^{2}}

where $D_{i j}$ is the distance between nodes i ( $x_{i}, y_{i}, z_{i}$ ) and j ( $x_{j}, y_{j}, z_{j}$ ).

Then, path planning task can be transformed into a 3-D TSP problem, as shown in Figures 4 and 5. In the further work, we will consider more factors such as the slope friction and robot poses so as to fitting the real environment more appropriately.^18,56

Figure 4.

TSP representation of the landfill environment (3-D view). TSP: traveling salesman problem; 3-D: three-dimensional.

Figure 5.

TSP representation of the landfill environment (2-D overlooking view). TSP: traveling salesman problem; 2-D: two-dimensional.

In this project, we optimize three ACO parameters: $ρ$ , α, and $β$ . These three parameters normally have a more complex adjusting process and more direct impact to optimization results. Then, the particles in our model can be constituted by these three parameters. A numerical uniform distribution method is used to generate particles. $ρ$ , α, and $β$ are selected from [0, 1], [0, 3], and [0, 5], respectively. As for other parameters of ACO such as AntCount and Q, we set them after a series of experiments according to the previous experience analyzed in the second section and the problem size, AntCount = 50, Q = 2000.

The number of PSO parameters is less than ACO. Generally speaking, a minute change in PSO parameters has a relatively small impact to its performance. In the CPSO-ACO model, ParticleCount = 3, $ω$ = 0.5, and c ₁ = c ₂ = 2; the iteration number of ACO corresponding to a particle, N, is reduced into 3. The maximum iteration number of PSO, M, is set at 30. Considering the principles illustrated in the second section, we determine these parameters by experiments.

We use the same development environment as mentioned in the third section, Visual Studio 2010 on a 32-bit windows 7 system. All the experiments are carried out on a PC with Intel core (TM) i5 CPU @ 2.4 GHz processor and 2 GB RAM. Each group of experiments is repeated five times. The statistical results are listed in Table 2.

Table 2.

Simulation results obtained by proposed CPSO-ACO.

Option	Path length (m)	Running time (s)
1	6305.55	82.15
2	6223.06	72.92
3	6264.95	68.62
4	6366.62	73.17
5	6163.06	73.39
Average value	6264.65	74.05
Optimum value	6163.06	68.62

CPSO-ACO: chaos-based particle swarm optimization-ant colony optimization.

As shown in Table 2, the length of the shortest route achieved by CPSO-ACO is 6163.06. The relative serial numbers are: 57-52-51-53-54-55-56-59-58-43-34-38-46-39-31-30-25-26-35-44-45-36-27-15-16-17-28-37-29-18-19-8-7-65-64-6-5-4-62-63-72-73-89-82-88-81-80-79-71-74-66-60-61-2-3-14-13-67-75-76-84-92-91-83-97-90-86-87-96-101-95-100-104-105-108-106-109-107-103-102-99-94-98-93-85-77-78-70-69-68-11-10-9-1-12-20-21-22-23-24-33-32-40-41-42-50-49-48-47. This optimal route is shown in Figures 6 and 7.

Figure 6.

The optimal route obtained by proposed CPSO-ACO (3-D view). CPSO-ACO: chaos-based particle swarm optimization-ant colony optimization; 3-D: three-dimensional.

Figure 7.

The optimal route obtained by proposed CPSO-ACO (2-D overlooking view). CPSO-ACO: chaos-based particle swarm optimization-ant colony optimization; 2-D: two-dimensional.

Comparative study

In order to evaluate the performance of proposed CPSO-ACO model, two groups of experiments are conducted in this article with similar search time scales or similar search qualities, respectively. The algorithms in the study by Min et al. and Xia et al.^15,16 are selected as the comparisons.

$A l g o r i t h m A$ : In this algorithm, $ρ$ is fixed at a constant; α and $β$ are optimized by PSO and constitute the 2-D particles.¹⁵

$A l g o r i t h m B$ : Three parameters, α, $β$ , and $ρ$ , are optimized by PSO; 3-D particles are constructed in this algorithm.¹⁶

$A l g o r i t h m C$ : PSO-ACO model with asynchronous pheromone updating strategy. We also adjust three parameters in this algorithm.

$A l g o r i t h m D$ : The hybrid CPSO-ACO model proposed in this article. α, $β$ , and $ρ$ are optimized by CPSO.

The major promotion of CPSO-ACO model is that the iteration number of ACO invoked by PSO can be reduced greatly on the condition that asynchronous pheromone updating method and chaos sequence are introduced.

For those TSPs with a large number of nodes, the advantage would be more obvious since more cycles are needed to perceive global environment in previous PSO-ACO. According to the complexity of the problem, dozens or even hundreds of cycles would be used in PSO-ACO models proposed by Min et al.¹⁵ and Xia et al.¹⁶ In our CPSO-ACO model, the ACO cycle number, N, can be reduced significantly.

Similar search qualities

We use the same experimental setup as mentioned in the third section; the parameters are set as Table 3 (as analyzed in the second section); all the experiments are repeated five times. For $A l g o r i t h m A$ and $A l g o r i t h m B$ , the higher the value of N, the better the solution is. A number of experiments are carried out to determine N in $A l g o r i t h m A$ and $A l g o r i t h m B$ so as to make sure these two algorithms can archive solutions with similar qualities.

Table 3.

Parameter setting (similar search qualities).

Algorithm	AntCount	Q	ParticleCount	w	C ₁	C ₂	N
A	50	2000	3	0.5	2	2	20
B	50	2000	3	0.5	2	2	25
C	50	2000	3	0.5	2	2	3
D	50	2000	3	0.5	2	2	3

Experimental results are recorded in Table 4. The average running time of $A l g o r i t h m D$ is 42.50% of that of $A l g o r i t h m A$ and 31.28% of that of $A l g o r i t h m B$ . It is reasonable to conclude that the improvements proposed in this article can lower time overhead obviously. Compared with $A l g o r i t h m C$ , $A l g o r i t h m D$ has a better search quality by the introduction of chaos.

Table 4.

Experimental results of four algorithms (similar search qualities).

	Path length (m)		Running time (s)
Algorithm	Average value	Optimal value	Average value	Optimal value
A	6263.04	6214.13	174.22	166.94
B	6265.32	6240.35	236.75	167.32
C	6279.29	6220.65	71.45	67.98
D	6264.65	6163.06	74.05	68.62

Similar time scales

Another group of experiments is also carried out in similar time scales. Parameters are set in Table 5. Especially, N is set at 3 for all the four algorithms. By setting as this, the running time of $A l g o r i t h m A$ and $A l g o r i t h m B$ can be reduced in a similar time scale to $A l g o r i t h m C$ and $A l g o r i t h m D$ , respectively.

Table 5.

Parameter setting (similar time scales).

Algorithm	AntCount	Q	ParticleCount	w	C ₁	C ₂	N
A, B, C, D	50	2000	3	0.5	2	2	3

Statistical results are recorded in Table 6. As shown in Table 6, the average length of the route obtained by $A l g o r i t h m D$ is 97.78% of that obtained by $A l g o r i t h m A$ , 97.66% of that obtained by $A l g o r i t h m B$ , and 99.77% of $A l g o r i t h m C$ .

Table 6.

Experimental results of four algorithms (similar time scales).

	Path length (m)		Running time (s)
Algorithm	Average value	Optimal value	Average value	Optimal value
A	6406.86	6367.53	73.41	70.84
B	6414.48	6382.36	72.78	65.86
C	6279.29	6220.65	71.45	67.98
D	6264.65	6163.06	74.05	68.62

As mentioned above, the proposed algorithm can reduce time cost effectively. In the similar running times, it is able to improve search quality.

Conclusion

According to actual situation, a real robot path planning task in landfill harsh environment is transformed into a 3-D TSP which is solved by the proposed algorithm: CPSO-ACO. Compared with previous PSO-ACO, there are two improvements in CPSO-ACO: (1) Novel pheromone updating method, global asynchronous method combined with “Elitist Strategy,” is applied in ACO; and (2) PSO random factors are generated by Chebyshev chaotic sequences.

Experimental results show that the proposed CPSO-ACO has two characteristics in the performance on TSP task: (1) Keeping acceptable solution quality, it can reduce running time outstandingly; (2) It can obtain better solutions on the same time scale.

The further work about this article can be conducted as follows: (1) the algorithm could be further improved by introducing more heuristic information and adaptively adjusting certain parameters like w; (2) more practical factors such as slope, friction, and robot poses should be considered so as to fit the environment appropriately; (3) several advanced machine learning strategies such as statistical learning⁵⁷ and reinforcement learning⁵⁸ could be introduced; (4) more mathematical analyses could be carried out for the proposed method in order to achieve possible theoretical properties, including convergence, stability, and computation complexity; and (5) more statistical experiments could be conducted on other similar problems so as to demonstrate the performance and properties of the model.

Footnotes

Acknowledgements

The authors are extremely grateful to College of Design and Manufacturing Technology, Muroran Institute of Technology, Japan, for accepting one of our co-authors, Peng Chen as an international exchanging student and providing him all the conveniences. The authors also deeply appreciate Professor Hanajima Naohiko for his scientific and rigorous guidance to Peng Chen.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by National Nature Science Foundation of China under Grants 61603034 and 61801019, Beijing Municipal Natural Science Foundation (3182027), and Fundamental Research Funds for the Central Universities, China, FRF-GF-17-B44.

ORCID iD

Peng Chen

References

Vrijheid

Dolk

Armstrong

. Hazard potential ranking of hazardous waste landfill sites and risk of congenital anomalies. Occup Environ Med 2002; 59(11): 768–776.

Chen

Wang

. A trace gas sensor using mid-infrared quantum cascaded laser at 4. 8 mu m to detect carbon monoxide. Spectrosc Spect Anal 2014; 34(3): 838–842.

Colorni

Dorigo

Maniezzo

. An investigation of some properties of an ‘ant algorithm’. In: Maünner

Manderick

(eds) PPSN, Volume 92, Brussels, Belgium, 28–30 September 1992, pp. 509–520. Elsevier Publishing.

Dorigo

Maniezzo

Colorni

. Ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern B Cybern 1996; 26(1): 29–41.

Jia

Wang

Leung

JYT

. An ACO algorithm for makespan minimization in parallel batch machines with non-identical job sizes and incompatible job families. Appl Soft Comput 2016; 38: 395–404.

Liu

Chen

. Optimisation of partial collaborative transportation scheduling in supply chain management with 3pl using ACO. Exp Syst Appl 2017; 71: 173–191.

Colorni

Dorigo

Maniezzo

. Ant system for job-shop scheduling. Belgian J Operat Res Stat Comput Sci 1994; 34(1): 39–53.

Maniezzo

Colorni

. The ant system applied to the quadratic assignment problem. IEEE Trans Knowl Data Eng 1999; 11(5): 769–778.

Wang

Xing

. A modified ant colony optimization algorithm for network coding resource minimization. IEEE Trans Evol Comput 2016; 20(3): 325–342.

10.

Duan

Wei

Dong

. Multiple UCAVS cooperative air combat simulation platform based on PSO, ACO, and game theory. IEEE Aero El Sys Mag 2013; 28(11): 12–19.

11.

Gambardella

Dorigo

. Solving symmetric and asymmetric TSPS by ant colonies. In: Proceedings of IEEE international conference on evolutionary computation, Nagoya, Japan, Japan, 20–22 May 1996. pp. 622–627. IEEE.

12.

Favuzza

Graditi

Sanseverino

. Adaptive and dynamic ant colony search algorithm for optimal distribution systems reinforcement strategy. Appl Intell 2006; 24(1): 31–42.

13.

Watanabe

Matsui

. Improving the performance of ACO algorithms by adaptive control of candidate set. In: Proceedings of the 2003 congress on evolutionary computation, CEC’03, volume 2, Canberra, ACT, Australia, Australia, 8–12 December 2003, pp. 1355–1362. IEEE.

14.

Kennedy

. Particle swarm optimization. In: Proceedings of 1995 IEEE international conference on neural networks (ed. IEEE Australia Council), volume 4, Perth, Australia, 27 November–1 December 1995, pp. 1942–1948. USA: IEEE.

15.

Min

Zhang

. Solving traveling salesman problems by an ACO-and-PSO-based hybrid algorithm. J Jilin Univ Inf Sci Ed 2006; 24(4): 402–405.

16.

Xia

Wang

. A kind of ant colony parameter adaptive optimization algorithm based on particle swarm optimization thought. J Shandong Univ (Eng Sci) 2010; 40(3): 26–30.

17.

Chai

Liu

. Application of an ant colony algorithm in tsp based on particle swarm. Comput Simulat 2009; 26(8): 89–91.

18.

Zhang

Chen

. Ant colony optimization combined with immunosuppression and parameters switching strategy for solving path planning problem of landfill inspection robots. Int J Adv Robot Syst 2016; 13(3): 130.

19.

Tanese

. Distributed genetic algorithms for function optimization. PhD Thesis, University of Michigan, Ann Arbor, 1989.

20.

Chen

Xie

Jin

. A wireless sensor data-based coal mine gas monitoring algorithm with least squares support vector machines optimized by swarm intelligence techniques. Int J Distrib Sens N 2018; 14(5): 1–21.

21.

Zhang

Shi

Zhao

. Path optimization algorithm and its robustness for bevel tip flexible needle. Int J Adv Robot Syst 2018; 15(5): 1–11.

22.

Choi

Park

. Complete coverage navigation of cleaning robots using triangular-cell-based map. IEEE Trans Ind Elect 2004; 51(3): 718–726.

23.

Oommen

Iyengar

Rao

NSV

. Robot navigation in unknown terrains using learned visibility graphs. part I: the disjoint convex obstacle case. IEEE J Robot Autom 1987; 3(6): 672–681.

24.

Takahashi

Schilling

. Motion planning in a plane using generalized Voronoi diagrams. IEEE Trans Robot Autom 1989; 5(2): 143–150.

25.

Sud

Andersen

Curtis

. Real-time path planning in dynamic virtual environments using multiagent navigation graphs. IEEE Trans Vis Comput Gr 2008; 14(3): 526–538.

26.

Wybe Dijkstra

. A note on two problems in connexion with graphs. Numer Math 1959; 1: 269–271.

27.

Hart

Nilsson

Raphael

. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cyb 1968; 4(2): 100–107.

28.

Stentz

. Optimal and efficient path planning for partially-known environments. In: Proceedings of the 1994 IEEE international conference on robotics and automation (ed. IEEE Computer Society), Vol. 4, San Diego, CA, USA, 8–13 May 1994, pp. 3310–3317. USA: IEEE. DOI: 10.1109/ROBOT.1994.351061.

29.

Khatib

. Real-time obstacle avoidance for manipulators and mobile robots. New York: Springer New York, 1990. pp. 396–404. ISBN 978-1-4613-8997-2.

30.

LaValle

. Planning algorithms. Cambridge: Cambridge University Press, 2006.

31.

Karaman

Frazzoli

. Sampling-based algorithms for optimal motion planning. Int J Rob Res 2011; 30(7): 846–894.

32.

Kavraki

Svestka

Latombe

. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans Robot Autom 1996; 12(4): 566–580.

33.

LaValle

Kuffner

Jr . Randomized kinodynamic planning. Int J Robot Res 2001; 20(5): 378–400.

34.

Liu

Lee

Varnhagen

. Path planning for autonomous vehicles using model predictive control. In: Intelligent vehicles symposium (ed. EEE Intelligent Transportation Systems Society), Los Angeles, CA, USA, 11–14 June 2017, pp. 174–179. IEEE.

35.

Schulman

Duan

. Motion planning with sequential convex optimization and convex collision checking. Int J Robot Res 2014; 33(9): 1251–1270.

36.

Luo

Wang

P W

. Towards enhancing stacked extreme learning machine with sparse autoencoder by correntropy. J Frankl Inst 2017; 355(4): 1945–1966.

37.

Zhang

. Control design for nonlinear flexible wings of a robotic aircraft. IEEE Trans Contr Syst Trans 2017; 25(1): 351–357.

38.

Hofner

Schmidt

. Path planning and guidance techniques for an autonomous mobile cleaning robot. Robot Auton Syst 1995; 14(2-3): 199–212.

39.

Ram

Santamaria

. Continuous case-based reasoning. Artif Int 1997; 90(1-2): 25–77.

40.

Colorni

Dorigo

Maniezzo

. Distributed optimization by ant colonies. In: Proceedings of the first European conference on artificial life: toward a practice of autonomous systems (ed. Varela

Bourgine

), Paris, France, 11–13 December 1991, pp. 134–142. MIT Press.

41.

Yang

Liu

. An adaptive RBF neural network control method for a class of nonlinear systems. IEEE/CAA J Autom Sinica 2018; 5(2): 457–462.

42.

Dorigo

Gambardella

. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evolut Comput 1997; 1(1): 53–66.

43.

Stutzle

Hoos

. Max-min ant system and local search for the traveling salesman problem. In: Proceedings of the IEEE international conference on evolutionary computation (ed. IEEE Neural Network Council and Evolut Programming Soc), Indianapolis, IN, 13–16 April 1997, pp. 309–314. IEEE.

44.

Zhang

Chen

. Improved ant colony optimization algorithm based on particle swarm optimization. Cont Decis 2013; 28(6): 873–878.

45.

Alatas

Akin

Ozer

. Chaos embedded particle swarm optimization algorithms. Chaos Solitons Fractals 2009; 40(4): 1715–1734. Available at: http://www.sciencedirect.com/science/article/pii/S096007790700803X.

46.

Daneshyari

. Chaotic neural network controlled by particle swarm with decaying chaotic inertia weight for pattern recognition. Neural Comput Appl 2010; 19(4): 637–645.

47.

Liu

Wang

Jin

. Improved particle swarm optimization combined with chaos. Chaos Solitons Fract 2005; 25(5): 1261–1271.

48.

Zhang

. Path planning of mobile robots based on specialized genetic algorithm and improved particle swarm optimization. In: Proceedings of the Chinese control conference (ed. Li

Zhao

), Hefei, China, 25–27 July 2012, pp. 7204–7208. IEEE.

49.

Wang

Zhao

. An improved chaotic motion path planner for autonomous mobile robots based on a logistic map. Int J Adv Robot Syst 2013; 10(6): 1.

50.

Kuang

Jin

. A novel chaotic artificial bee colony algorithm based on tent map. In: 2014 IEEE Congress on evolutionary computation (CEC), Beijing, China, 6–11 July 2014, pp. 235–241. IEEE.

51.

Chatterjee

Roy

Das

. Secure biometric-based authentication scheme using Chebyshev chaotic map for multi-server environment. IEEE Trans Dependable Sec Comput 2018; 15(5): 824–839.

52.

Reinelt

. TSPLIB 95. Heidelberg: Heidelberg University, 2013.

53.

MCANFDS. Summary for the Nakazono final disposal site. In: Proceedings of Monitoring Committee of Asahikawa Nakazono Final Disposal Site. Asahikawa: Monitoring Committee of Asahikawa Nakazono Final Disposal Site, 2010, pp. 1–10.

54.

Kamata

Tobita

Matsufuji

. Stabilizing treatment and closure work for Nakazono final disposal site in Asahikawa city. JWMA 2011; 64(301): 282–285.

55.

Yan

Sun

. Adaptive neural network control of a flapping wing micro aerial vehicle with disturbance observer. IEEE Trans Cybern 2017; 47(10): 3452–3465.

56.

Zhang

Qing

Chen

. Improved ant colony optimization based on particle swarm optimization and its application. J Univ Sci Technol B 2013; 35(7): 955–960.

57.

Luo

Zhang

Laurence

. A kernel machine-based secure data sensing and fusion scheme in wireless sensor networks for the cyber-physical systems. Future Gener Comp Sy 2016; 61(C): 85–96.

58.

Wang

Zhang

Wei

. PDP: parallel dynamic programming. IEEE/CAA J Autom Sinica 2017; 4(1): 1–5.

Hybrid chaos-based particle swarm optimization-ant colony optimization algorithm with asynchronous pheromone updating strategy for path planning of landfill inspection robots

Abstract

Keywords

Introduction

Related work

Path planning

Traveling salesman problem

ACO

PSO

Hybrid CPSO-ACO algorithm

Previous PSO-ACO algorithm

Improved pheromones updating method: Global asynchronous method combined with “Elitist Strategy”

The introduction of chaos

Hybrid CPSO-ACO model

Experimental analysis on Ch150 problem

Path planning for landfill inspection robots in Asahikawa, Japan

Comparative study

Similar search qualities

Similar time scales

Conclusion

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

ORCID iD

References