Two-Dimension Path Planning Method Based on Improved Ant Colony Algorithm
Rong Wang*, Hong Jiang

Abstract

Nowadays, path planning has become an important field of research focus. Considering that the ant colony algorithm has numerous advantages such as the distributed computing and the characteristics of heuristic search, how to combine the algorithm with two-dimension path planning effectively is much important. In this paper, an improved ant colony algorithm is used in resolving this path planning problem, which can improve convergence rate by using this improved algorithm. MAKLINK graph is adopted to establish the two-dimensional space model at first, after that the Dijkstra algorithm is selected as the initial planning algorithm to get an initial path, immediately following, optimizing the select parameters relating on the ant colony algorithm and its improved algorithm. After making the initial parameter, the authors plan out an optimal path from start to finish in a known environment through ant colony algorithm and its improved algorithm. Finally, Matlab is applied as software tool for coding and simulation validation. Numerical experiments show that the improved algorithm can play a more appropriate path planning than the origin algorithm in the completely observable.

Keywords

Share and Cite:

Wang, R. and Jiang, H. (2015) Two-Dimension Path Planning Method Based on Improved Ant Colony Algorithm. Advances in Pure Mathematics, 5, 571-578. doi: 10.4236/apm.2015.59053.

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 1. Node schematic.

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.

Figure 7. Change of fitness value.

Figure 8. Result of path planning.

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.

Conflicts of Interest

The authors declare no conflicts of interest.

 [1] Chu, K., Kim, J., Jo, K. and Sunwoo, M. (2015) Real-Time Path Planning of Autonomous Vehicles for Unstructured Road Navigation. International Journal of Automotive Technology, 16, 653-668. [2] Wahle, J., Annen, O., Schuster, Ch., Neubert, L. and Schreckenberg, M. (2001) A Dynamic Route Guidance System Based on Real Traffic Data. European Journey of Operational Research, 131, 302-308. [3] Liu, S. and Sun, D. (2014) A Dynamic Priority Based Path Planning for Cooperation of Multiple Mobile Robots in Formation Forming. Robotic and Computer-Integrated Manufacturing, 30, 589-596. http://dx.doi.org/10.1016/j.rcim.2014.04.002 [4] Nikolos, I.K. and Valavanis, K.P. (2003) Evolutionary Algorithm Based Offline/Online Pathplanner for UAV Navigation. IEEE Transactions on System, Man, and Cybernetics—Part B. Cybernetics, 33, 898-912. http://dx.doi.org/10.1109/TSMCB.2002.804370 [5] Saska, M. and Macas, M. (2006) Robot Path Planning Using Particle Swarm Optimization of Ferguson Splines. IEEE Conference on Emerging Technologies and Factory Automation, Prague, 20-22 September 2006, 833-839. http://dx.doi.org/10.1109/etfa.2006.355416 [6] Althoefer, K. (1997) Neuro-Fuzzy Motion Planning for Robotic Manipulators. Ph.D. Thesis, King’s College, London, [7] Yang, B. and Liu, W.J. (2009) A Improved Method of Robot's Path Planning Based Visibilty Graph. Computer Knowledge and Technology, 5, 434-435. [8] Fan, X. and Luo, X. (2003) Optimal Path Planning for Mobile Robots Based on Intensified Ant Colony Optimization Algorithm. Proceedings of IEEE International Conference on Robotics, Intelligent Systems and Signal Processing, 1, 131-136. [9] Zhang, Y.L. and Niu, X.M. (2011) Simulation Research on Mobile Robot Path Planning Based on Ant Colony Optimization. Computer Simulation, 28, 231-234. [10] Dorigo, M. and Gambardella, L.M. (1997) Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1, 53-66. http://dx.doi.org/10.1109/4235.585892 [11] Mandloi, M. and Bhatia, V. (2015) Congestion Control Based Ant Colony Optimization Algorithm for Large MIMO Detection. Expert Systems with Applications, 42, 3662-3669. http://dx.doi.org/10.1016/j.eswa.2014.12.035 [12] Dorigo, M. (1992) Optimization Learning and Natural Algorithms. Dipartimento di Elettronica, Politecnico di Milano, Milano. [13] Ruiz, E. and Albareda-Sambola, M. (2015) A Biased Random-Key Genetic Algorithm for the Capacitated Minimum Spanning Tree Problem. Computers and Operations Research, 57, 95-108. http://dx.doi.org/10.1016/j.cor.2014.11.011 [14] Fischer, A. and Helmberg, C. (2013) The Symmetric Quadratic Traveling Salesman Problem. Mathematical Programming, 142, 205-254. http://dx.doi.org/10.1007/s10107-012-0568-1 [15] Wu, W.T. and Song, Y.C. (2012) Chaotic Prediction of Network Traffic Based on Neural Network Optimized by Ant Colony Optimization Algorithm. Computer Engineering and Applications, 97-101. [16] Chen, K.-Y. (2014) Development of Optimal Path Planning Based on Ant Colony and Wireless Sensor Network Localization Techniques for an Autonomous Mobile Service Robot. Electronics and Electrical Engineering, 953-958. [17] Bullnheimer, B. and Hartl, R.F. (1999) A New Rank Based Version of the Ant System: A Computational Study. Central European Journal for Operations Research and Economics, 25-38.