Two-Dimension Path Planning Method Based on Improved Ant Colony Algorithm ()
1. Introduction
The essence of road traffic navigation problem [1] is the optimal path planning problem [2] [3] that is planning out a reasonable path from start to finish under the known road network topological structure. In consideration of convenient communication and complicated road condition in the modern traffic, how to plan out an optimal path effectively and quickly is much significant. At present, shortest path search already can’t meet the needs of travel; the optimal two-dimension path planning is not only requiring finding a shortest path, but also requiring strict requirement of real-time. In the process of navigation, planning out a reasonable route and improving the calculation response speed seem to be particularly important in the view of the application. A large number of experts and scholars have carried on the thorough research on this question. How to plan out a reasonable path in time is very practical significance of the research question. There are numerous researches on path planning algorithms. Many techniques are offered, such as genetic algorithm [4] , particle swarm optimization [5] , neural network [6] , visibility graph [7] and colony optimization [8] . Q. B. Zhu [9] applied ant colony algorithm to path planning by modeling the environment with grid method. The results demonstrate that ant colony algorithm is a good solution for path planning problem. The reminder of this paper is organized as follows. In Section 2, we introduce the principle of ant colony algorithm; the model of dimension path planning will be introduced in Section 3. We propose the improved ant colony algorithm in playing a more appropriate path planning in Section 3. In Section 4, some significant parameters are selected in this problem. Planning experimental results are presenting through ant colony algorithm and its improved algorithm. We conclude this paper in Section 5.
2. Ant Colony Algorithm
Ant colony algorithm [10] [11] is a new kind of evolutionary algorithm which is brought forward by Dorigo M., it comes from the study of ants searching for food problem. Ant colony algorithm is a kind of adaptive distributed algorithm [12] , it is also a kind of random search algorithm [13] . Ants in the process of feeding are through a legacy chemicals on the path to communicate and collaborate, the chemicals called pheromones are volatile. The stronger the pheromone is, the shorter the corresponding path distance is. When a path pheromone concentration is higher, the greater the probability of the ants to find this path are, and ant will release a certain amount of pheromone to enhance this path pheromone concentration, thus it is constitutes a kind of positive feedback phenomenon of learning information. Under the action of this positive feedback, the ants will eventually find the best path from the nest to food source. Nevertheless biologists found that path pheromone concentration will decay as time goes on gradually.
2.1. The Basic Idea of Ant Colony Algorithm
The basic step in solving the optimization problem applying ant colony algorithm is: the ant walk paths are delegated with feasible solutions of optimization problem, the entire ant group staying on all paths constitutes the solution space of optimization problems. Released pheromone amounts in short path is more than others, with the passage of time, the accumulation of pheromone concentration on the shorter path is increasing gradually, more and more ants will choose these paths. Ultimately, the ants will focus on the best path under the action of the positive feedback.
Ant colony algorithm has played an important role in solving the traveling salesman problem [14] , the shortest path search [15] [16] , scheduling problem [17] , etc.
2.2. The Basic Principle of Ant Colony Algorithm
Without loss of generality, supposing that the number for a whole ants group are m, network topology for the road node numbers are n, the distance between the road node i and j is 
, at the t moment, the pheromone concentration between the node i and j is
, each pheromone concentration in every road node is set with 
in the initial time.
The 
ant decides the next choice node according to the various sections of the pheromone concentration, supposing 
shows the probability that is the ant moves from node i to node j in the t moment, calculating formula is that:
(1)
: pheromone concentration between the node i to node j, the value will gradually decay with the passage of time;
: expectations of the node i to node j, it represents a kind of local heuristic information, some local experience can guide a better path, it stands the reciprocal of distance 
to the node i and j in the paper;
: This value can be adjust through experiments, represents for importance degree of
;
: It represents importance degree of 
that can be adjust through experiments；
: sets of the next node when ants from one node to another node. This value is dynamically changing. At the time n, the next equation is the updating pheromone concentration formula when ants completing a path searching from the start to the end:
(2)
In the formula, ![]()
is the path pheromone concentration variation, indicated as:
![]()
(3)
![]()
represents the k ant releases the pheromone concentration from the node i to the node j.
3. The Model of Solving the Path Planning
This paper will introduce MAKLINK graph theory, a two-dimension path planning model is established to initialize the network topology, two-dimension path planning feasible region is generated by several MAKLINK lines in that MAKLINK graph. Among that, MAKLINK lines show not only that connection lines between two adjacent obstacles vertex where connection lines are not intersecting but also the lines between obstacles vertex and its boundary.
3.1. The Divide Model in Link Nodes
A suboptimal routing road ![]()
can be planned with the Dijkstra algorithm on the MAKLINK graph, ![]()
is free link line that is corresponding to node. On the assumption that ![]()
and ![]()
are two endpoints of![]()
, the other nodes can be shown with following formula:
![]()
(4)
Of which, ![]()
is scale parameter, d is the number of nodes in link divide.
The Formula (4) shows that Dijkstra algorithm will get the initial path through the link line, as long as a new set of parameters ![]()
is given, you can get a new path from start to finish, ant colony algorithm is aimed to choose the best parameters in![]()
.
It is required to disperse work space before using ant colony algorithm. Due to the initialization of the freedom of choice link line length is differ, the method of the link line division is named fixed distance classification method. Setting the length is![]()
, division number at link L is:
![]()
(5)
If the ![]()
is odd number, midpoint is also a path point, ![]()
will be added one. In consideration of the link line ![]()
is divided by![]()
, so the link line ![]()
arriving at the link line ![]()
has ![]()
roads to choose .
Ant colony algorithm is used to obtain the path parameter set![]()
, which is aimed at find the shortest path in the discretizable spaces. Let us suppose that there is m ants from start S to finish T. Circular path is![]()
. ![]()
represents that the path point is located in position j at the link line d. With the moving of the every ant, ant will choose the node j from link line ![]()
to link line ![]()
through following formula:
![]()
(6)
i is the whole points in link lines, q is a random number between [0,1], ![]()
is a adjustable parameter in [0,1], ![]()
is heuristic value, ![]()
is pheromone.
As for the calculation method of j, firstly calculating the select probability from the link line node ![]()
to the next j, then using roulette selection to elect the next node j according to the probability![]()
, design formula of ![]()
is:
![]()
(7)
3.2. Update the Pheromone
Pheromone update includes real-time pheromone update and path pheromone update. Over here real-time pheromone update demands each ant must update the node pheromone after selecting a node, namely:
![]()
(8)
![]()
is initial value of pheromones, ![]()
is a adjustable parameter ranging of [0,1].
It is completed the iterative search when all the ants move from the initial point to the finish line. In order to select a shortest path length when all the ants move to the end, pheromone on each road should be updated, the formula is:
![]()
(9)
![]()
, ![]()
is the length of the shortest path, ![]()
is a adjustable parameter in [0,1].
3.3. Improved Ant Colony Algorithm
When an ant is searching for the node ![]()
to the next node![]()
, the traditional algorithm is calculating the probability of the next node which is one of all optional nodes that is based on pheromone and distance calculation and then choose the![]()
, assuming that optional sections of node are![]()
. Each node selection is to reduce the total length from the current node to the end, so if you select the angle line node ![]()
![]()
to ![]()
that comparing the angle of starting and ending angle they are consistent or similar, the ![]()
node is to give priority to the node. As shown in Figure 1. In this paper, we will use this method to finding the next node![]()
.
4. The Analysis of the Experiment Results
4.1. The Influence of m Parameter (the Number of Ants) on the Results
To explore the ant number influence on the optimal path, we had analyzed six different sets of ant species, the Figure 2 shows that when the number of ants are selected 5, 10 or15 respectively, as the number of ants increasing, the shortest path planning will reduce on the contrary, the Figure 3 shows that when m is 30 or 50, with the increasing of the ant species, the shortest path distance is also gradually increased with the increase of number of ant species. When m is 15, it can play a optimal path planning.
![]()
Figure 2. Influence of the number of ants (one).
![]()
Figure 3. Influence of the number of ants (two).
4.2. The Influence of Parameter (Importance Factor of Influence with Pheromones) on the Results
The Figure 4 shows that when the pheromone of importance factor is 1 and pheromone importance factor is 2, difference in path planning is not obvious, however when the a = 1, the convergence speed of path planning is faster than a = 2, so in this paper, a = 1 finally is elected to important parameter for the pheromone factor.
4.3. The Influence of Parameter (Importance Factor of Heuristic Function) on the Results
The Figure 5 shows that when importance factor of the heuristic function is b = 1, the path planning results are volatile, to the contrary, when the parameter is b = 2, the result is stabilized. Therefore in this paper, we choose b = 2 as the importance factor of heuristic function which could deservebetter path planning than other factors.
4.4. The Influence of Parameter (Pheromone Volatilization Factor) on the Results
The Figure 6 shows that choosing r = 0.1, as the addition number of iterations, the shortest path is gradually converged, when r = 0.2 or 0.3, the results of path planning is fluctuating with the increase of iterations. Therefore in this paper we select r = 0.1 which can play a more ideal path planning.
![]()
Figure 4. Importance factor of influence with pheromones.
![]()
Figure 5. Importance factor of heuristic function.
![]()
Figure 6. Influence of pheromone volatilization factor.
4.5. Results Analysis
The optimum calculation parameters can be chosen in this paper, as a whole, the number of ants is 15, pheromone importance factor is a = 1, importance factor inspired by the function is 2, pheromone volatilization factor is 0.1, the number of iterations is 500. Figure 7 and Figure 8 show the convergence speed of two algorithms and optimal path plans. The Figure 7 shows that improved algorithm has a certainly better effect comparing with the original algorithm. Before improvement, the optimal distance of two-dimension path planning is 175.5889 kilometers, after improvement, the optimal distance of two-dimension path planning is 164.5734 kilometers. Figure 8 shows the improved ant colony algorithm and the original planning are together planning the path. The red figure shows that is programming optimal path by improved ant colony algorithm, blue figure is using the original algorithm. Obviously, improved ant colony algorithm can plan out a better path than the original algorithm.
5. Conclusions
In this paper, an improved ant colony algorithm is applied for two-dimension path planning; through the algorithm we can plan out optimal paths from start to end. Comparing the improved algorithm to the original ant colony algorithm, comparison of the simulation result shows that improved algorithm can plan a more optimal routing than the original algorithm.
However the simulation is based on the environment such as the known obstacle conditions, path planning in the actual situation maybe just be part of the perception of environmental conditions. How to plan out an optimal path from start to end under the condition of local environment perception is the requirement to be further research content.