Ant Colony Optimization Combined with Immunosuppression and Parameters Switching Strategy for Solving Path Planning Problem of Landfill Inspection Robots

Abstract

An improved ant colony optimization (ACO) combined with immunosuppression and parameters switching strategy is proposed in this paper. In this algorithm, a novel judgment criterion for immunosuppression is introduced, that is, if the optimum solution has not changed for default iteration number, the immunosuppressive strategy is carried out. Moreover, two groups of parameters in ACO are switched back and forth according to the change of optimum solution as well. Therefore, the search space is expanded greatly and the problem of the traditional ACO such as falling into local minima easily is avoided effectively. The comparative simulation studies for path planning of landfill inspection robots in Asahikawa, Japan are executed, and the results show that the proposed algorithm has better performance characterized by higher search quality and faster search speed.

1. Introduction

Nowadays, robots are more and more widely applied in production process and our daily life, and path planning is a very important branch in robotics, especially for mobile robots. Path planning is often treated as finding an optimum path from a start node to a goal node, and certain optimization criteria (e.g., shortest distance, minimum running time, or lowest energy consumption) must be satisfied [1]. Generally, robot is regarded as a particle in this process.

In recent years, scholars have done lots of fruitful work for path planning of mobile robots, and several methods, such as artificial potential field method (APF) [2], genetic algorithm (GA) [3], particle swarm optimization (PSO) [4], and ant colony optimization (ACO), have been developed to tackle this problem [5–9]. Among them, ACO is a typical swarm intelligence optimization method, and it is wildly used recently for its convenient realization [10, 11]. However, it has some problems, such as slow search speed, falling into the local convergence easily, and randomness of the optimum solution, because the initial pheromone of ACO is deficient. To overcome above shortcomings, some improved ACO algorithms based on immunosuppression are presented by scholars. Immunosuppression refers to a process that keeps the individuals with high fitness and low concentration, while making obsolete the individuals with low fitness and high concentration. Liu et al. present a highly efficient algorithm-binary state ant colony algorithm based on immunodominance strategy. In this algorithm, different pheromone update methods were used, aiming at two groups of ants. Moreover, elitist ants were got from tabu table, which was optimized through immune operator such as clone expansion and hyper mutation, and then local optimization immunodominance operating was applied to enhance the explorative capacity [12]. Liu Yong et al. propose a hybrid model combined with ACO and immune clone algorithm. In this model, the pheromone distribution for ants is generated through immune memory operator at the early stage, and the concentration of pheromone is adjusted through immunosuppression at the last period, so that the diversity of ant colony is preserved [13]. Lin and Huo present a modified ACO based on immune system, making use of the positive feedback of ACO and the global search capability of immune genetic algorithm, and dynamic route guidance simulation result illustrates the effectiveness of the proposed algorithm [14]. Zhang et al. use immune algorithm to obtain the iterative optimization of associated parameters of ACO, raising the efficiency of the method [15].

In the dump rebuilding project of Asahikawa, Japan, the landfill inspection robot is required for collecting the gas emission information of dump. That means all the gas emission pipelines should be traversed by land inspection robots with the minimum distance, and the inspection path planning problem can be treated as traveling salesman problem (TSP) because there is no obstacle in routing environment. Besides, the location of gas emission pipelines is distributed in rugged mountain, so they are not in the same plane, and the path planning problem could be regarded as 3D TSP. In this paper, each data collecting point in dump are viewed as a city in TSP, and the cost function is measured by 3D geometric distance, thus the way solving TSP could be used for path planning of land inspection robots.

The research work of this paper is aiming at path planning for inspection robots in landfill reconstructing project, Asahikawa, Hokkaido, Japan, and its contributions can be summarized as follows:

1. The environment without obstacle, such as the situation in this paper, can be converted into TSP, and it is a new mathematical model abstraction method.

2. A modified ACO for solving path planning problem of landfill inspection robots is proposed. The proposed algorithm has a novel, targeted, and effective judgment criterion for immunosuppression that the optimum solution has not changed in default iteration number; its search space is expanded by parameters switching strategy, and the defect of ACO, which falling into local minima easily, is avoided to some extent.

Figure 1.

The planning topographic map of landfill in Asahikawa

2. Project Background and Environment Modeling

The research environment of this paper is the landfill in Etanbetsuchonakazono, Asahikawa, Hokkaido, Japan. In this section, the research background is described, then the environmental information is processed, so that path planning problem for landfill inspection robots can be converted into a TSP.

2.1. Background description

The central landfill is located in No. 197 address, Etanbetsuchonakazono, Asahikawa, Hokkaido, Japan, which covers an area of 179.7 hectares. A mass of household garbage and some construction waste, total about 6.5 million tons, was filled here from June 1979 to June 2003 [16]. The settlement of landfill was affected, and underground water was polluted by lots of water left in garbage because of poor drainage in the landfill. Moreover, serious anaerobic environment was formed, and a great quantity of combustible gas was also accumulated in the landfill for lacking in air circulation. Therefore, potential safety hazards were increased due to deficiency of gas emission pipes [17].

Asahikawa ministry of environment reconstructed this landfill to solve the above problems. Catchpits, drainageway for penetrating fluids and gas emission pipelines, have been built from 2004 to 2009. Ninety-seven gas emission pipes were erected by this project, and the number of them is expected to reach 109 [17]. The planning topographic map of landfill is shown in Figure 1, pointing out different colors in graph stands for gas emission pipes, and the altitude of gas pipes is expressed by contour line.

To prevent relevant workers from encroaching of harmful gas, inspection robots are applied to collect gas concentration of the gas emission pipes, and the route should be predetermined by simulation studies, so that the robot could travel all the pipes with minimum distance.

2.2. Environmental information processing

From the above environment, path planning problem for landfill inspection robots can be converted into a TSP because there are no barriers in the dump. Due to the uneven distribution of gas emission pipes, the cost function between cities in TSP is substituted by 3D geometrical Euclidean distance between each gas emission pipeline.

The horizontal plane with an altitude of 200 m is selected as X-Y plane for the 109 pipes that are mostly constructed with a height near to 200 m. After projecting these 109 points to X-Y plane, we can find that point 8-5 is located in the center of the 109 points. So, point 8–5 is set as the origin of 3D coordinates, and 3D view for all gas emission pipelines is shown in Figure 2, whose projection in X-Y plane is shown in Figure 3.

Figure 2.

The 3D view for all gas emission pipelines

Figure 3.

The projection for the location of gas emission pipelines in X-Y plane

According to the location of 109 pipelines and the origin set above, the 3D coordinates of all pipelines could be determined, and part of them are listed in Table 1 (there are only coordinates of 37 gas emission pipelines for length limitation).

Table 1.

The coordinates of gas emission pipeline (partial)

No.	1	2	3	4	5	6	7	8
Code	8-5	9-5	10-5	11-d	12-d	A18	A19	A20
X	0	-50	-100	-150	-200	-250	-350	-400
Y	0	0	0	0	0	-7	-7	-7
Z	5.6	6.4	7.5	8.2	8.3	8.7	0	0
No.	9	10	11	12	13	14	15	16
Code	7-5	6-5	A17	8-4	9-4	10-4	11-c	12-c
X	50	100	150	0	-50	-100	-150	-200
Y	0	0	0	50	50	50	-52	52
Z	6.3	6.2	4.3	6	6.5	6.5	6.5	6.8
No.	17	18	19	20	21	22	23	24
Code	A14	A15	A16	7-4	6-4	A13	A12	A11
X	-250	-350	-400	50	100	150	200	250
Y	46	45	45	50	50	50	50	50
Z	6.8	0	0	6	6.5	2.3	-3.1	-13.5
No.	98	98	99	100	101	102	103	104
Code	B19	B17	B18	C7	B23	B22	B21	B27
X	104	200	266	0	-70	245	339	-12
Y	-256	-229	-252	-300	-306	-306	-306	-360
Z	8.5	8.3	4	16	16	10.4	5	17.4
No.	105	106	107	108	109
Code	B26	B25	B24	B29	B28
X	80	275	375	217	311
Y	-364	-360	-360	-404	-412
Z	14.6	8.6	7.4	16.6	8.8

The 3D geometrical distance between i th and j th gas emission pipeline could be computed by equation (1).

$D_{ij}=\sqrt{{(x_i-x_j)}^2+{(y_i-y_j)}^2+{(z_i-z_j)}^2}$

(1)

where $(x_i\mathrm{,}{y}_i\mathrm{,}{z}_i)$ and $(x_j\mathrm{,}{y}_j\mathrm{,}{z}_j)$ represent the 3D coordinates of i th and j th gas emission pipeline separately, as listed in Table 1.

Therefore, the path planning problem for landfill inspection robot has already converted into a 3D traveling salesman problem.

3. Improved Ant Colony Algorithm Combined With Immunosuppression and Parameters Switching Strategy

In this section, ACO and its mathematical model are introduced, a modified ACO combined with immunosuppression and parameters switching strategy is proposed, and the steps of proposed algorithm are described.

3.1. ACO and its mathematical model

The optimum solutions are built in parallel by different ants when ACO is used for TSP solving process. The probability $P_{ij}^k(t)$ where node j is selected as the next node from current node i by k th ant is shown as equation (2) when the ant system (AS) model is taken as an example [18].

$P_{ij}^k(t)=(\begin{array}{cc}\frac{{\tau }_{ij}^{\alpha }(t){\eta }_{ij}^{\beta }(t)}{{\displaystyle \sum _{s\in allowe{d}_k}}{\tau }_{is}^{\alpha }(t){\eta }_{is}^{\beta }(t)}& j\in allowe{d}_k\\ 0& \text{otherwise}\end{array}$

(2)

In the equation above, ${\tau }_{ij}(t)$ and ${\eta }_{ij}(t)$ stand for the pheromone amount and heuristic factor between nodes i and j at t moment respectively. Typically ${\eta }_{ij}(t)=\frac{1}{d_{ij}}$ , where $d_{ij}$ is the distance between nodes i and j. α and β are the weights controlling the influence ${\tau }_{ij}(t)$ and ${\eta }_{ij}(t)$ separately. $allowe{d}_k$ is the node set where all selectable nodes by k th ant are included.

The route of an ant is a sequence including all serial numbers of gas emission pipes and it is also a feasible solution of TSP when all nodes are visited by the ant. If all ants completed the iteration processes, the pheromone between nodes i and j is updated by Equations (3) and (4).

${\tau }_{ij}(t+1)=(1-\rho ){\tau }_{ij}(t)+\mathrm{\Delta }{\tau }_{ij}(t)$

(3)

$\mathrm{\Delta }{\tau }_{ij}(t)={\displaystyle \sum }\mathrm{\Delta }{\tau }_{ij}^k(t)$

(4)

In the equation above, ρ is the pheromone evaporation coefficient. $\mathrm{\Delta }{\tau }_{ij}^k(t)$ is the pheromone amount that the k th ant released on path from node i to node j at t moment and $\mathrm{\Delta }{\tau }_{ij}(t)$ is the increment of the pheromone for all ants on path from node i to node j at the same time.

The computational equation of $\mathrm{\Delta }{\tau }_{ij}^k(t)$ is shown as equation (5) when the ant-cycle model is chosen as the pheromone evaporation style.

$\mathrm{\Delta }{\tau }_{ij}^k(t)=(\begin{array}{cc}\frac{Q}{L_k}& \text{Situation 1}\\ 0& \text{otherwise}\end{array}$

(5)

where Q is the total pheromone amount and L_k is the distance of the path obtained by the k th ant In Situation 1 k th ant passes through the path from node i to node j

During the optimization process, the pheromone amount in the environment is accumulated or evaporated until the default maximum iteration number is reached.

3.2. Immunosuppressive ACO

In ACO, the more ants pass through a path, the more pheromone is accumulated, and the higher concentration is obtained in the path. Therefore, the path will be selected in high probability in the next recursive loop. This positive feedback mechanism ensures the rapidity and convergence of ACO. However, premature phenomenon appears accordingly, and the algorithm is fall into local minima easily. To overcome the problem, some scholars take the basic idea of immunosuppression into consideration for concentration adjusting.

The path concentration $C_{ij}(t)$ is defined as a ratio between the amount of ants which pass through the path from node i to node j and the amount of all ants [12]. When the concentration of a path is higher than default value C₀ the pheromone on this path will be inhibited. Otherwise, the inhibition will be relieved. The immunosuppression equation is shown in equation (6).

${\tau }_{ij}^k(t+1)=(\begin{array}{cc}{\tau }_{ij}^k(t)e^{\lambda C_{ij}(t)}& C_{ij}(t)>C_0\\ {\tau }_{ij}^k(t)& \text{otherwise}\end{array}$

(6)

where λ is an adjusting factor and it is a negative constant.

Compared with simple ACO, higher quality solution has achieved by immunosuppression algorithm proposed by Liu et al. for small-scale TSP, such as Oliver30 [12]. But in the project as mentioned above, it is a complex process in which a certain amount of pheromone accumulated in a particular path because the number of gas emission pipes is large and they are distributed uniformly, so the paths selected by ants are dispersive at the early stage. Therefore, a suitable C₀, which has a direct influence on search quality, is difficult to determine under such environment. If C₀ is set too big, then the concentration value would be hard to reach and the immunosuppression may lose its efficiency. On the contrary, if C₀ is set too small, then the pheromone could not be accumulated fully, thereby the convergence speed would be slow.

Aiming at this circumstance, a novel judgment criterion for immunosuppression is introduced in this paper. The concentration of a path should be inhibited if the optimum solution has not changed successively for default iteration number and the inhibition is released when optimum solution with higher fitness value appears. The improved immunosuppression equation can be described as equation (7).

${\tau }_{ij}^k(t+1)=(\begin{array}{cc}{\tau }_{ij}^k(t)e^{\lambda C_{ij}(t)}& \text{Situation\hspace{0.05em}2}\\ {\tau }_{ij}^k(t)& \text{otherwise}\end{array}$

(7)

In Situation 2, the optimum solution has not changed successfully for default iteration number. In this improved method, immunosuppressive strategy is utilized in accordance with the optimum solution. On the one hand, the difficulty in C₀ selecting is avoided. On the other hand, it has strong pertinency and high efficiency because it is carried out only in the circumstance where the optimum solution has no change successively for default iteration number. In addition, all the paths passed by ants are inhibited instead of some certain paths so that the paths which have not selected in early stage are more likely chosen by ants in the next iteration. As a result, the randomness information is exploited sufficiently, and the search space is expanded greatly.

3.3. Parameters switching strategy

Besides immunosuppression, the parameters switching strategy is also introduced to improve the algorithm. In ACO, different selection of parameters has direct influence on problemsolving process. A group of parameters with strong randomness is usually selected for expanding the search space when ACO is trapped into stagnating state and another group of parameters with better convergence is chosen when optimum solution with higher fitness value appears so that the heuristic information can be used adequately. In this paper, three parameters ρ, α, and β are chosen as the switching parameters. Among them, ρ is the pheromone evaporation coefficient, the bigger ρ is, the faster pheromone evaporates, and the randomness of ACO is stronger. However, α and β are the parameters stand for the influence of pheromone and heuristic information to the algorithm. Bigger α leads to stronger convergence and bigger β means that ACO is easily influenced by heuristic information so that the node with local shortest path will be chosen more frequently.

3.4. Parameters switching strategy

The algorithm combined with immunosuppression and parameters switching strategy proposed in this paper has six steps as follows:

• Step 1. Select a group of parameters with strong randomness in the initial stage of algorithm.

• Step 2. After running for default iteration number, choose another group of parameters with better convergence to enhance the influence of pheromone and heuristic information.

• Step 3. If the optimum solution unchanged continuously for default iteration number, then switch back to parameters with strong randomness to enlarge the search space.

• Step 4. Inhibit the concentration with equation (7) to expand the search space further.

• Step 5. If there is solution with high fitness value appearing, go back to Step 2, relieving immune suppression. Otherwise, keep the immunosuppression and still choose parameters with strong randomness.

• Step 6. Continue the algorithm until the default maximum iteration is reached.

Table 2.

Simulation results obtained by five ant colony algorithms

Algorithm	Optimum solution(m)		Computing times(s)
	Average	Minimal	Average	Minimal
A	6374.9001	6223.8737	51.433	50.016
B	6411.9024	6295.5747	51.192	49.313
C	6335.7857	6164.4252	50.469	47.781
D	6391.4104	6250.2623	53.547	51.217
E	6512.7402	6482.3676	52.632	50.515

4. Simulation Studies

The proposed algorithm is applied for path planning of landfill inspection robots in dump rebuilding project in Asahikawa. The general parameters of ACO are selected as $AntCount=150$ and $Q=2000$ . The default maximum iteration number is set as 200. According to the experience mentioned in Section 3.3, parameters with strong randomness are chosen as $\rho =1$ , $\alpha =1$ and $\beta =3$ , whereas parameters with strong convergence are chosen as $\rho =0.5$ , $\alpha =2$ , and $\beta =4$ after a large number of trial and error tests.

The determination of default iteration number X is the most difficult thing in proposed algorithm. If X is too small, then the immunosuppression operator will be so frequent in which the convergence speed will be slow down. On the contrary, if X is too big, the algorithm could not handle the stagnating problem timely and the effect of immunosuppression will be obviously reduced within the same maximum iteration number. After a lot of statistical experiments, the default iteration number X is set as 20.

All the simulations are completed in ASUS laptop with Intel core i5 CPU, 2.40 GHz basic frequency, 2G RAM. The software running environment is Visual Studio 2008 and program language is C++. Comparative simulate studies using five algorithms defined later are investigated for path planning of landfill inspection robots in 3D TSP environment mentioned earlier

Algorithm A (Improved immunosuppressive ACO): If the optimum solution has not changed for consecutive 20 generations, the concentration of path would be adjusted by using of equation (7) with $\lambda =-1.8$ until optimum solution with higher fitness value appears. Parameters are chosen as $\rho =0.5$ , $\alpha =2$ and $\beta =4$

Algorithm B (Parameters switching ACO): At the early stage of algorithm, select a group of parameters with strong randomness as $\rho =1$ , $\alpha =1$ and $\beta =3$ to ensure the diversity of solutions. After 20 generations, another group of parameters with better convergence are selected as $\rho =0.5$ , $\alpha =2$ and $\beta =4$ to utilize the pheromone and heuristic information until optimum solution with higher quality is not obtained for continuous 20 generations. Then initial group of parameters with strong randomness is switched back until optimum solution with higher fitness value appears and the group of parameters with better convergence is called again.

Algorithm C (Improved ACO combined with immunosuppression and parameters switching strategy): Its steps are described in Section 2.4, the values of ρ, α and β are the same as Algorithm B.

Algorithm D (Immunosuppressive ACO in Ref [12]): equation (6) is used as immunosuppression model if the concentration of certain path is larger than the default value C₀. Parameters are selected as $\rho =0.5$ , $\alpha =2$ , $\beta =4$ and $C_0=0.6$

Algorithm E (Traditional ACO): Parameters are selected as $\rho =0.5$ , $\alpha =2$ and $\beta =4$

The simulation experiments are implemented five times for each algorithm defined above to reduce the randomness existing in problemsolving process of ACO. The average optimum solution, average computing time, minimal optimum solution and minimal computing time are shown in Table 2.

Some facts can be concluded from Table 2 as follows:

1. Algorithm E (Traditional ACO) has worst performances no matter in computing time or search quality.

2. Compared with Algorithm D (Immunosuppressive ACO in Ref [12]), Algorithm A (Improved immunosuppressive ACO) has better performances in computing time and search quality. That indicates that the novel judgment criterion for immunosuppression proposed in this paper is effective.

3. Algorithm C (Improved ACO combined with immunosuppression and parameters switching strategy) has achieved optimum solution with higher fitness value than Algorithm A (Improved immunosuppressive ACO) in relatively short computer time. That demonstrates that the parameters switching strategy has a positive impact on search quality improving and search speed accelerating. The minimal optimum solution is selected as the final result for each algorithm after five times experiments. The changes of path lengths for minimal optimum solution corresponding to each algorithm are shown in Figure 4.

The path length of optimum solution achieved by proposed algorithm is 6164.425159 and its relative sequence numbers are: V = {57, 52, 51, 53, 54, 55, 56, 59, 58, 43, 46, 38, 34, 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, 26, 25, 30, 20, 12, 1, 9, 10, 21, 22, 11, 68, 67, 75, 83, 91, 90, 86, 87, 96, 95, 100, 104, 101, 97, 105, 108, 103, 107, 109, 106, 102, 99, 94, 98, 93, 92, 84, 76, 77, 85, 78, 70, 69, 24, 23, 33, 32, 31, 39, 40, 41, 42, 50, 49, 48, 47}. The inspection route is shown in Figure 5.

Figure 4.

The changes of path lengths for minimal optimum solution corresponding to each algorithm

Figure 5.

Optimum inspection route for robots achieved by the proposed algorithm

5. Conclusion

The main contributions of this paper are a new mathematical model abstraction method which can convert path planning problem of inspection robots to TSP and a modified ACO combined with immunosuppression and parameters switching strategy. Simulation results of path planning for inspection robots in landfill reconstructing project in Asahikawa, Hokkaido, Japan show that the proposed algorithm obtains the shortest path with the least amount of time consumption, illustrating that immunosuppression and parameters switching strategy proposed in this paper can expand the search space, avoid falling into local minima, improve the solution quality and reduce the computing time effectively.