Mobile robot path planning using an improved ant colony optimization

Abstract

Ant colony algorithm is an intelligent optimization algorithm that is widely used in path planning for mobile robot due to its advantages, such as good feedback information, strong robustness and better distributed computing. However, it has some problems such as the slow convergence and the prematurity. This article introduces an improved ant colony algorithm that uses a stimulating probability to help the ant in its selection of the next grid and employs new heuristic information based on the principle of unlimited step length to expand the vision field and to increase the visibility accuracy; and also the improved algorithm adopts new pheromone updating rule and dynamic adjustment of the evaporation rate to accelerate the convergence speed and to enlarge the search space. Simulation results prove that the proposed algorithm overcomes the shortcomings of the conventional algorithms.

Introduction

Path planning is an important topic in navigation aspect for mobile robotics. ¹ The aim of path planning is to find an optimal collision-free path between a starting point and a target in a given environment. In recent years, many scientists made lots of researches on path planning and put forward some methods, such as the dynamic window approach, ² potential field method, ^1,3 fuzzy logic, ^4,5 the A* algorithm, ⁶ the D* algorithm, ⁷ simulated annealing algorithm, ⁸ genetic algorithm ^9,10 and neural networks. ¹¹ However, these techniques were shown some drawbacks, such as poor robustness, local minimum and lack of adaptation.

In the early 1990s, Italian scholar Marco Dhad introduced the ant colony algorithm, ¹² which is a meta-heuristic evolutionary algorithm that belongs to the swarm intelligence family; and it was inspired by the foraging behaviour of real ants in nature.

The ant colony algorithm has been successfully used in solving lots of combinatorial optimization problems, and it becomes in leading spot among other swarm intelligent systems. Based on the good impact left in solving the quadratic assignment problem, ¹³ the job shop scheduling problem, ¹⁴ the travelling salesman problem, ¹⁵ the network routing selecting problem ¹⁶ and the vehicle routing problem, ¹⁷ also due to its advantages such as parallel processing, distributed computing and strong robustness, the ant colony algorithm has been gradually applied in the field of mobile robot navigation. ^18,19

Despite the fact that the ant colony algorithm has shown several good performances in the path planning task, it still unable to deal with the shortcomings, such as long search time, easy stagnation, slow convergence speed and local optimization. In order to increase the performance quality of the algorithm, many researchers have proposed some improvements. Dong et al. adjusted the heuristic information in real time during the searching process ²⁰ ; Zaho et al. designed two fuzzy controllers to optimize three parameters α, β and γ and produced a new evaluation criterion to select the best path ²¹ ; Zaho and Fu adopted an improved two-way parallel searching strategy to accelerate the searching speed and used a new method that rationally distributes the initial pheromone to increase the convergence speed ²² ; Châari et al. presented a new hybrid ant colony-genetic algorithm approach for fast path selection and global solution ²³ ; Huang and Zheng proposed an improved ant colony algorithm based on rolling window to show good analytical and disposing ability of dead ends in the path planning process ²⁴ ; and Cheng et al. combined ant colony algorithm with simulated annealing algorithm to improve the pheromone updating method. ²⁵

According to many studies, the transition rule in the ant colony algorithm is the key to find the shortest path; in this article, we improve this transition rule by assigning a stimulating probability (sp) that helps the ant in choosing a safe grid with much exits towards the target, and we make it adaptable for large scale based on global heuristic information; also, we establish a modified pheromone updating rule and a new dynamic evaporation strategy to increase the global search capability and to accelerate the convergence.

The article is organized as follows. Section ‘Environment modelling’ describes the grid modelling method. In ‘Ant colony algorithm’ section, the basic ant colony algorithm is addressed. In ‘Improved ant colony algorithm’ section, the improved ant colony algorithm is presented. ‘Simulation results’ section discusses the simulation results. ‘Conclusion’ section concludes the article.

Environment modelling

Usually, there are three common methods of environment modelling which are the grid method, the geometric method and the topological graph. We planned the mobile robot movement in grid platform where the working area is divided into grid cells of binary information that indicates the obstacle grids by ‘1’ and the free grids by ‘0’. The grid platform is a two-dimensional environment, placed into orthogonal reference coordinate system XOY to compute the coordinate of each grid. By assuming that the entire grids label with integers and their lengths equal to the unit length of the coordinates, we got the following coordinate of the grid labelled ‘i’

$\{\begin{array}{c}{x}_i=\text{mod}\left(i-1,N_x\right)+0.5\\ y_i=\text{int}\left(\frac{\left(i-1\right)}{N_y}\right)+0.5\end{array}$

1

where N_x is the number of grids in each row, N_y is the number of grids in each column, mod is a remainder operation and int is an integer operation.

Figure 1 shows an example of a grid map that has 10 grids in each row and 10 grids in each column; the black grids represent obstacles and the white ones represent the free space. From Figure 2, the robot can move in eight directions which are forward, backward, right, left, right-up, right-down, left-up and left-down.

Figure 1.

Grid map.

Figure 2.

Possible directions of motion.

Ant colony algorithm

Ant colony algorithm is an evolutionary intelligent heuristic search algorithm for solving optimization problems. It was developed based on the behaviour of ants in finding their short path from their living place to the food source.

During the process of exploring the environment randomly in search of food, each ant releases an amount of pheromone on the path where it passed; once the food is found, the ants tend to travel towards the trail where the pheromone concentration is high, because they can sense the strength of the pheromone. While the ants keep heading to the strong pheromone trail, the pheromone concentration will increase which will make more ants attracted to the path and will increase the pheromone concentration on that path even more and so on. This kind of behaviour represents the principle used by ants to select their optimal path.

At each time t, an ant k moves from its current grid i to an unvisited grid j based on the distance between them and the amount of pheromone on the edge that connects them. If there is more than one unvisited grid, the ant k will choose its next grid according to the following transition probability

$p_{ij}^k\left(t\right)=\{\begin{array}{cc}\frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }\cdot {\left[{\eta }_{ij}\left(t\right)\right]}^{\beta }}{{\displaystyle \sum _{s\in {\text{ allowed}}_k}{\left[{\tau }_{is}\left(t\right)\right]}^{\alpha }\cdot {\left[{\eta }_{is}\left(t\right)\right]}^{\beta }}}& j\in {\text{ allowed}}_k\\ 0& \text{otherwise}\end{array}$

2

where α and β are weighting parameters that show the relative influence of the pheromone and the heuristic information (visibility) during the path selection process, respectively, allowed _k is the set of grids not visited by ant k, τ_ij represents the pheromone concentration on the path: grid i to grid j and η_ij denotes the visibility of the grid j from the grid i as follows

${\eta }_{ij}=\frac{1}{d_{ij}}$

3

where d_ij is the distance between two neighbour grids, and it is defined as

$d_{ij}=\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}$

4

Once all the ants finished their tours, the pheromone levels on all the arcs will be updated by volatilizing the old pheromone and adding the pheromones deposited by each ant. The pheromone updating formula is given by

${\tau }_{ij}\left(t+1\right)=\left(1-\rho \right){\tau }_{ij}\left(t\right)+{\displaystyle \sum _{k=1}^m\Delta {\tau }_{ij}^k}$

5

where ρ is the pheromone evaporating rate, m is the number of ants and Δτ^k represents the amount of pheromone left by the ant k at the current iteration, which can be expressed as follows

$\Delta {\tau }_{ij}^k=\{\begin{array}{c}\frac{Q}{L_k}\text{ edge }(i,j)\text{ is used in tour}\\ 0\text{ otherwise}\end{array}$

6

where L_k is the length of the path that was found by the ant k and Q is a constant.

Improved ant colony algorithm

In the conventional ant colony algorithm, the probabilistic selection does not always guarantee an optimal solution, and sometimes in the early stages of optimization, the algorithm falls into local optimum; and also due to the limited heuristic search, the algorithm has a poor convergence speed. In order to enhance the performance of the original ant colony algorithm and overcome its defects, we introduce the following improvements.

Stimulating probability

The sp is a combinatorial operation; we adopted to make it easy for an ant to pick the best next grid, which has to be an accessible grid with more than one exit towards the target. This probability depends on the number of obstacles surrounding the grid. So, the less obstacles are around the grid, the bigger the probability is and the more attractive the grid is. To determine the sp, we need to have the following combinations.

C(8, N _obs), which is the number of the possible distributions of the obstacles around a certain grid j. It can be calculated as follows

$C\left(8,N_{\text{obs}}\right)=\frac{8!}{\left(8-N_{\text{obs}}\right)!N_{\text{obs}}!}$

7

C(8 − N _obs − 1,1), which represents the number of exits, from where the ant k can leave the grid j, and it is expressed as

$C\left(8-N_{\text{obs}}-1,1\right)=\frac{\left(8-N_{\text{obs}}-1\right)!}{\left(8-N_{\text{obs}}-1-1\right)!}$

8

where C(a,b) = a!/(a − b)!b! is a mathematic combination, N _obs is the number of obstacles around the grid j, eight is the maximum number of obstacles and ! refers to the factorial.

Remark 1

In the calculation of the number of exits, we must cancel the one from where the ant k will access the grid j.

Remark 2

C(8, N _obs) = C(8,8 − N _obs).

The sp that makes the ant k in the grid i more attracted to the grid j is defined by

${\text{sp}}_{ij}^k=\frac{C\left(8-N_{\text{obs}}-1,1\right)}{C\left(8,N_{\text{obs}}\right)}$

9

The resulting transition rule is described by the following equation

$p_{ij}^k\left(t\right)=\{\begin{array}{cc}\frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }\cdot {\left[{\eta }_{ij}\left(t\right)\right]}^{\beta }\cdot {\text{sp}}_{ij}}{{\displaystyle \sum _{s\in {\text{ allowed}}_k}{\left[{\tau }_{is}\left(t\right)\right]}^{\alpha }\cdot {\left[{\eta }_{is}\left(t\right)\right]}^{\beta }\cdot {\text{sp}}_{is}}}& j\in {\text{ allowed}}_k\\ 0& \text{otherwise}\end{array}$

10

Global heuristic information

In the original ant colony algorithm, the step length is fixed to the distance between two adjacent grids, which reduces the candidate grids and the search diversity, leading to a slow convergence speed and a stagnation behaviour that makes the algorithm unable to find the shortest path. To avoid these problems, we adopted the principle of free step length, ²⁶ where new global information was established based on an unlimited heuristic search and an expanded vision field (all the grids in the vision field of the mobile robot are involved in the selection process of the next grid).

Lets assume that i and j are the current and the next grid, respectively, S and E are the starting and the ending (target) grid, respectively, and d represents the distance between each one of them as d(S, i), d(i, E), d(S, j), d(j, E), d(i, j), and d(S, E). Our heuristic information is addressed as follows.

At the initial moment, the direction of motion of ants must be towards the target grid as follows

${\eta }_{SE}\left(0\right)=\frac{1}{d\left(S,E\right)}$

11

After the initial moment, we increase the diversity of the heuristic search; however, we must keep the direction of the search to the grid target as follows

If d(S, i) < d(S, j) and d(i, E) > d(j, E), then

${\eta }_{ij}\left(t\right)=\frac{d\left(i,j\right)}{d\left(j,E\right)}$

12

If d(S, i) < d(S, j) and d(i, E) < d(     j, E), then

${\eta }_{ij}\left(t\right)=\frac{d\left(i,j\right)}{d\left(S,E\right)}$

13

If d(S, i) > d(S, j), then

${\eta }_{ij}\left(t\right)=\frac{1}{d\left(S,E\right)}\cdot \frac{d\left(j,E\right)}{d\left(i,j\right)}$

14

The distance d is calculated according to equation (4).

Improved pheromone updating rule

The amount of pheromone is one of the necessary factors in choosing the best grids that lead to a short path; however, it contains a certain intensity of bad pheromone which is produced by the worst ants, and it can make other ants move to grids where the goal is inaccessible or can cause a premature solution of the algorithm. In order to achieve a good performance, for each iteration, we increased the pheromone concentration in the best local path and decreased it in the worst local path using the following updating rule

${\tau }_{ij}\left(t+1\right)=\left(1-\rho \right){\tau }_{ij}\left(t\right)+{\displaystyle \sum _{k=1}^m\Delta {\tau }_{ij}^k\left(t\right)}+\Delta {\tau }_{ij}^{\text{best}}-\Delta {\tau }_{\mathit{\text{ij}}}^{\text{worst}}$

15

where

$\Delta {\tau }_{ij}^{\text{best}}=\{\begin{array}{c}{\text{sp}}_{\text{max}}\cdot n_{\text{best}}\cdot \frac{Q}{L_{\text{best}}}\text{edge }(i,j)\text{ is local best path}\\ 0\text{ otherwise}\end{array}$

16

$\Delta {\tau }_{ij}^{\text{worst}}=\{\begin{array}{c}{\text{sp}}_{\text{min}}\cdot n_{\text{worst}}\cdot \frac{Q}{L_{\text{worst}}}\text{edge }(i,j)\text{ is local worst path}\\ 0\text{ otherwise}\end{array}$

17

where sp_max and sp_min are the maximum and the minimum of the sp, respectively, n _best and n _worst are the numbers of the best and the worst ants, respectively, and L _best and L _worst are the lengths of the best and the worst local path, respectively.

Remark 3

In the free step length principle, when the ant picks the next grid, sometimes there will be some secondary grids between the current grid and the next grid where the ant had left an amount of pheromone; but since the ant is passing by (not staying), the amount of pheromone in those grids will be poor, which will not be considered in the pheromone updating process.

Dynamic evaporation strategy

In the traditional ant colony algorithm, the evaporation rate is a constant in the range (0,1), and it has a direct impact on the global search ability and the convergence speed of the algorithm. If ρ is too small, the pheromone will evaporate very slowly which reduces the global search ability and brings the algorithm to local convergence. If ρ is too large, the global search will be improved and the convergence speed will be reduced.

To guarantee a good balance between expanding the search space and accelerating the convergence speed, we adjusted the pheromone evaporation rate dynamically where, in the beginning of the algorithm, we set the evaporation rate to a large value in order to ameliorate the global search ability, and then it will be changed according to the following equation

$\rho \left(t\right)=\frac{T\cdot t\cdot \frac{1}{n}{\displaystyle \sum _{k=1}^n{\text{sp}}^k}\cdot \left({\tau }_{\text{max}}-{\tau }_{\text{min}}\right)}{T-1}+\frac{\frac{1}{n}{\displaystyle \sum _{k=1}^n{\text{sp}}^k}.\left(T\cdot {\tau }_{\text{min}}-{\tau }_{\text{max}}\right)}{T-1}$

18

where t and T are the current and the maximum iterations, respectively, n is the number of ants, sp ^k denotes the sp of the ant k and τ _max and τ _min refer to the maximum and minimum amount of pheromone, respectively.

Simulation results

To verify the effectiveness and the validity of our improved ant colony algorithm, we performed MATLAB simulation for both the basic and the enhanced algorithms in two different grid maps of the sizes 20 × 20 and 30 × 30, respectively. The parameters were set as follows: the population size n = 30, the maximum iteration T = 100, α = 1, β = 5 and Q = 2. In both maps, the starting grid S is at the left bottom corner and the ending grid E is at the right upper corner.

The simulation results are shown in Figures 3 to 6, in which Figures 3 and 5 represent the optimal path and Figures 4 and 6 show the convergent curve of the optimal path. The solid line denotes the improved algorithm and dotted line represents the original algorithm.

Figure 3.

Optimal path planning.

Figure 4.

Convergent curve.

Figure 5.

Optimal path planning.

Figure 6.

Convergent curve.

From all the simulation figures, it is obvious that our improved ant colony algorithm has the better performance characteristics over the traditional algorithm like the shorter path and the faster convergence.

Table 1 shows a comparison between the results of the original and the improved algorithm in both maps.

Table 1.

Statistic results of the algorithms in both maps.

Map	Traditional algorithm		Improved algorithm
	Iterations	Path length (m)	Iterations	Path length (m)
1	25	31.841	10	28.7612
2	40	46.8605	25	43.6874

Conclusion

In this article, an improved ant colony algorithm was proposed and compared to the original one based on the performance delivered while solving the mobile robot path planning problem in grid maps. The improvement was in four aspects as follows: introduction of sp in the transition rule to pick a safe and accessible grid, global heuristic information using the free step length principle to increase the visibility accuracy and the search efficiency, enhanced pheromone updating rule and dynamic evaporation strategy to increase the global search ability and the convergence speed. The simulation results prove that the improved ant colony algorithm is significantly superior over the classic ant colony algorithm in terms of short path and fast convergence.

It is obvious that the results achieved in this article prove the potential of the proposed ant colony algorithm in solving the path planning problem in static environment. Future goals are to perform the path planning in dynamic environment and to focus on the experimental validation of the proposed algorithm.