Global Path Planning of AUV Based on Improved Ant
Global Path Planning of AUV Based on Improved Ant
Colony Optimization Algorithm
Zhang Guang-lei Jia He-ming
College of Automation College of Mechanical and Electrical Engineering
Harbin Engineering University Northeast Forestry University Harbin, Heilongjiang Province,China
Harbin, Heilongjiang Province,China
jiaheminglucky99@https://www.wendangku.net/doc/6b10862674.html,
Abstract - In order to solv e path planning problem for autonomous underwater vehicle(AUV) in the horizontal plane, a new method based on quadtree and improv ed ant colony algorithm is presented in this paper. Two dimensional horizontal area model can be built by quadtree. An improv ed ant colony algorithm is adopted for high efficiency path planning based on this model. Quadtree not only records all of the area information but also co mpresses area information efficiently. Improv ed ant colony algorithm can find a path that maintains a safe distance from obstacles, which improv es the usefulness for the planning path. Simulation experiments illustrated that the designed method can get a good balance between efficiency and usefulness of the planning path and find a path efficiently in the two dimensional horizontal area.
Index Terms - autonomous underwater vehicle, path planning, ant colony algorithm, quadtree method
I. I NTRODUCTION
Driving an AUV along a desired path accurately is one of the most important issues in many marine applications, including discovering offshore oil fields, scientific investigation of deep sea, exploitation of underwater resources, long range survey, oceanographic mapping, underwater pipelines tracking, military missions and so on[1-4]. With the application of AUV in industry more widely, the requirements to the vehicle intelligence have been also increased, that is the AUV has the ability to interact with the surrounding environment when they in movement. One of the important issues is to plan an optimal path for collision avoidance when AUV navigate through the complex environment, which represents the intelligent level of AUV .
So far, we have explored many effective solutions for path planning, which can be divided into two categories: traditional methods and intelligent methods, topological method, geometric method, the artificial potential field method, cell decomposition method, a lot of complex issues can be solved by one or severals together[5-7]. But most of the above methods focus on improving the efficiency of algorithm execution or shorten the length of the path planning, which have the following problems: (1) it may not be an efficient algorithm for path planning for large areas; (2) the path which be planned can not guaranteed to keep a safe distance to the obstacles, that cause the less safety and practicality.
In this paper, an improved ant colony algorithm is proposed, which uses the distance between AUV and the obstacle and the terminal point, builds the heuristic information. Meanwhile introduce the concept called penalty
factor, which be added to the path that ants have found to eliminate the paths more close to the obstacles, while retaining the global optimum path planning with obstacles. So we can get a path which can keep a safe distance to obstacles and at a meantime the path is shortest. In order to improve the search efficiency in large areas of the algorithm, we get environmental information modeling by using the quadtree, which can compressed information of the environment efficiently and reduce the scale of the problem of path planning.
II. E NVIRONMENTAL MODELING There are many different types of quadtree, we use the linear quadtree in this article, which have the advantage only to record the leaf nodes coding, but not record the intermediate node encoding and hierarchical relationships. So it can improve the utilization of storage space.
A. Linear Quadtree Model
The following rules are adopted to get non-uniform segmentations of two-dimensional region to establish the linear-quadtree-model: (1) Take the whole region as a root node, coded as 0. (2) Halve the root node region along the X, Y directions, sub-root node is divided into 4 sub-node, each node corresponds to a promoter region, the child nodes position in accordance with the order from west to east, from north to south, respectively appended 1, 2, 3, 4 to the root node encoding after the formation of the encoding of each node, respectively named the encoding of the child nodes 01,02,03,04. Child node can be divided by: the obstacle nodes, free nodes and mixed nodes. Within the space of obstacle nodes, there are all obstacles, but there is no obstacle within the free node, the nodes contain both obstacles and free space nodes are called mixed nodes.
(3) If the mixed node exists, by the rules (2) continue to break down mixed node until all nodes are free nodes and the node obstacles so far. Using above rules, the quadtree decomposition instance can be clearly shown in Fig.1, white areas on behalf of the free node, node of the black areas on behalf of obstacles, the gray area representing the mixed node. The fig.1 (a) shows a linear quadtree decomposition process, the figure (b) shows the final decomposition renderings.
978-1-4673-0364-4/12/$31.00 ?2012 IEEE
Proceeding of the IEEE
International Conference on Automation and Logistics
Zhengzhou, China, August 2012
606
(a) Linear quadtree (b) Decomposition results decomposition process
Fig.1 Example of quadtree decomposition
B. Neighborhood to Determinethe Linear Quadtree Node
Lost connection between the leaf node to generate a linear quadtree, this relationship is difficult to pass the leaf nodes encoding the intuitive method to determine the relationship between the free leaf node in the path planning is very important. So before the path planning process, we should re-establish the connection relationship of the free leaf node, that is to determine the neighborhood of each free leaf node.
In this paper, we only consider the neighborhood adjacent to the edge node, namely the horizontal and vertical directions of the four neighborhood are north of the domain, the south domain, west of the domain and the east domain.
Boundary node is a node such as which has at least a neighborhood node of four neighborhood does not exist. The non-boundary node have four neighborhood nodes. The neighborhood of the same size refers to the neighborhood demand by a node is the same size and the size of the node. Conversely, if the size is not the same is not the same size neighborhood[8-10]. The reference of Quadtree coding can be divided into four collections as the following: North- set N = {1,2}, South-set S = {3,4}, the West-set W = {1,3} and East- set E = {2,4}.
C. Non-Boundary Nodes to Determine the Neighborhood of the Same Size
For a node Q, we encode it 12...n q q q ,ie. 12...n Q q q q =.If Q is a non-boundary node, the four neighborhood is determined by the following rules:
If 1n q =, the east domain coding for the Q at +1 (encoding the last one plus one) to get the coding of the neighborhood, encoding of the south of the domain is Q+2; North of the domain from the end of the encoded left scan until you find i q ,the first one （i q ） does not belong to the north-collection coding, encoding the rightmost n-i coded bits plus 2, i q minus 2, and the remaining codings bit values remain unchanged. We take the new coding as the code of the neighborhood.
Similarly, as to the west of the domain, from the end of the beginning to the left of the coding scan until you find the first code (i q ) does not belong to the west, add 1 to the right code
from n-i to1 ,then i q minus 1, and the coding bit values left unchanged, take the new coding as the code of the neighborhood. If 2n q =, west of the domain encoding as Q-1, the south of the encoding of the domain as Q +2, the way we named north domain the same as when 1n q =.
As to east domain, we start to scan from left at the end of coding until you find the first one (i q ) does not belong to the north set, encoding the right from n-i to 1, coding bits minus 1, i q plus 1, and the coding bit values left unchanged, take the new coding as the code of the neighborhood. If 3n q =and north of the domain coding for the Q-2, east of the encoding of the domain Q +1, the way we named west domain the same as when 1n q =.
As to south domain, we scan from the left to the end of the coding until you find the encoded bit(i q ) do not belong to the south set, encoding the rightmost n-i encoded bit minus 2, plus 2 other encoding bit values remain unchanged. the new coding for the coding of the neighborhood by, west of the domain encoding for Q-1, north of the domain encoding method for Q-2, east of the domain with the same. South domain is with the same.
D. Determine the Different Neighborhood of Non-boundary Nodes
Neighborhood of non-boundary node is not the same as the determination is identified based on the same size neighborhood, assuming the same size neighborhood in view of the symmetry of the node neighborhood relations, neighborhood is not the same size is determined by the following rules:
For a non-boundary node Q on section of the same size neighborhood encoding P, find ancestors encoding at all levels of P, truncated coding P. The specific rules: remove encoding P, finally a new encoding, use this code to traverse the entire free leaf node set, view the existence of the leaf nodes of the encoding, if there is, then find the same size neighborhood, otherwise the new coding continue the process, until the length of coding become 1.
E. Determination of the Neighborhood of Boundary Nodes
For node Q, if all of its encoded bit value belong to the same set of benchmark system, then we called Q is the boundary nodes, that is for i q (i = 1 ... n), if i q N ∈,then Q is a boundary node, its north domain, other neighborhood identified with the same method as the previous two sections, Similarly i q S ∈,i q W ∈,i q E ∈.
In summary, the neighborhood can get a free leaf node, as shown in Fig.1(b), leaf node 0233, the application of rules shows that the north of the domain for 0231, the south domain 04, west of the domain for 01, The east field is 0234.
III. IMPROVED ANT COLONY ALGORITHM
Traditional ant colony algorithm is evolved by the ant algorithm, which is characterized as follows: (1) Ants using a
pseudo-random proportional rule to select the next position; (2)
Each movement of the ant step should be carried out to a local
pheromone update; (3) When all ants from the starting point to reach the terminal, select the optimal path from the ants search
607
path, and only global information on the optimal path elements update[11].
Traditional ant colony algorithm can not guarantee a safe path planning, in order to maintain a safe distance and the length of the shortest path and the obstacles of traditional ant colony algorithm has been improved, which is mainly reflected in the following areas: the use of artificial potential the field concept to construct a new heuristic information; the introduction of the concept of penalty factor and the ants search the path to the imposition of the penalty factor; modify the global pheromone update rule. A. New Heuristic Information
Basic algorithm of the heuristic information can be calculated as follows:
1
()=
kd kd
t d η (1) where ()kd t ηis the position k of the heuristic information;
kd d represents position k to the end of d, straight-line distance.
The value of heuristic information and location-to-end
distance is inversely proportional relationship with the
position gradually near the end of larger in order to guide the
ants towards the end of movement. But its existence to the
following issues: (1) does not contain the location and the
distance between the obstacle and can not lead ants away from
the obstacle, the search to a safe path; (2) its value changes are
uneven, when the position and the end of distance greater than
1, its value changes slowly, and when the distance is less than 100, the value of rapid change, leading to poor effect of the heuristic information to guide. In response to these issues, drawing on the concept of
artificial potential field of attraction and repulsion, re-construct the heuristic information
()()(1)()kd att safe t V k V k ηλλ=?+?? (2) where ()att V k and ()safe V k denote the position k of the gravitational heuristics and heuristic information security; λ (01λ<<) indicates the relative importance of gravitational and safety of the heuristic-information. Expression for the gravitational heuristic is
()()1max ()
goal att goal n P
d k V k d n ∈=?
(3)
where P denotes the set of optional location information in the area of path planning, ()goal d k and ()goal d n denoted position k
and n to the end of the distance, ()goal d k to do with the global maximum ratio normalized.
Expression safe V is of heuristic information security
()
()1max ()
safe n P R k V k R n ∈=? (4) where ()R k denote its repulsion to the nearest position k of the obstacles , its similar to gravity heuristic information processing. Normalization ()R k is
02
00
111(),()()()
()0,()obs obs obs obs d k d d k d d k R k d k d ?
??
that the path should be the minimum distance of the distance of obstacles, that is safe distance, ()obs d k denote position k to obstacles. New heuristic was a mixture of gravity and heuristic information security by a certain percentage, and thus can guide the ants to avoid towards the end of movement away from the obstacle too close to the location because of the way of using the maximum ratio and normalized ()goal d k and ()R k ,which makes the gravity and security of the
heuristic information is not dramatic changes, ultimately make a new heuristic to overcome the lack of the uneven changes in
the heuristic information.
B. Penalty Factor
Even with the new heuristic, ant colony algorithm using
pseudo-random proportional rule to find the path, the ant may
search for unsafe path, in order to eliminate these unsafe path,
the concept of penalty factor, the penalty factor is applied to
the path length coefficient, and its expression is:
0,1,p p p d d d d d d
δ?
where 0d denote safe distance, p d representatives of a given
path from the shortest distance of the obstacles to
meet δsatisfy 1δ≥. Assuming that any ant k to find the
length of the path k LT ,the path length and path of the shortest
distance from the obstacle, the integrated path distance k
L is
k k L LT δ=? (7)
It can be seen that if 0p d d C. New Global Pheromone Updating Rule All ants at the same time from the starting point in the basic algorithm, when the ants to reach the terminal, according to the ants search out the length of the path, choose the shortest path to the global pheromone update, and then all the ants re-starting from the starting point to continue the process. The program the following problems: (1) some ants may arrive early end, but must wait for the other ants, can not be immediately re-start a new search process; (2) only for each shortest path in the global pheromone update, easy to 608 algorithm into a local optimal solution. In ord er to solve these problems, further improving the efficiency of the algorithm, the global pheromone update rule for the following changes: when any ant k to reach the terminal, using the formula (1) to calculate the integrated path length, global optimal solution for comparison, if it is better than the optimal solution, then use it to upd ate the optimal solution, and then using the following formula to upd ate the path of the ants search to pheromone, and then immed iately start a path starting from the starting point of search, without waiting for the other ants to reach the terminal. ()(1)()()ij ij ij k k k τρτρτ=??+?Δ (8) where ()ij k τdenotes ant k search path (i, j) pheromone residues; ρpheromone evaporation coefficient( 01ρ<<); ()ij k τΔsaid the pheromone increment, the calculation formula is: ()elite ij k L k L τΔ= (9) where elite L denote the global optimal path length, k L said that the path length of ant k search path. Asynchronous search methods, that the ants to reach the terminal immediately after the next round of search, effectively improving the search efficiency. On each path by a certain global pheromone update, to avoid the algorithm into a local optimal solution. D. Algorithm processes Improve the operation of the algorithm process is as follows, the initial moment of ants all in the starting point node, then the ants continue to use the current location of that subsection, improved formula search near the location of collection, and select one as the next location, all ants repeat this process towards the end of the parallel search path, and any ant to reach the terminal node, use the new global pheromone updating rule to update the pheromone, and then the ants in the starting point node, re-start a new search, repeat the process until algorithm termination condition. The algorithm termination condition has not been updated for consecutive M times the global optimal solution. After the end of the algorithm, the global optimal solution path as a result, the flow chart of the algorithm is shown in Fig. 2. Fig. 2 Improved ant colony algorithm process IV. S IMULATION ANALYSIS Two simulation experiments are d esigned to valid ate the algorithm effectiveness in this paper. In the area of 60m *60m, qua d tree mo d eling area through improve d ant colony algorithm is compared with the basic ant colony algorithm to verify security of the planning paths: in the area of 1000m *1000m, we contrast the quad tree grid method and the basic ant colony algorithm for hybrid planning strategy to the quad tree and the mixed strategy of improved ant colony algorithm, we can vertify the efficiency of the combination of ant colony algorithm for path planning in the large-size area. As shown in fig. 3, in the area 60m *60m diagram (a) and (b) show the basic ant colony algorithm and improved ant colony algorithm for planning the path, in which the starting point located at the bottom left, upper right corner end. Figure 4 shows the shortest distance of each location away from obstructions in the path (in figure 3), we set up the distance to the obstacles for 5m,we can see from the graph, the traditional ant colony algorithm for path planning can not keep safe distance to the obstacles, while the improved ant colony algorithm for path planning can keep a safe distance to the obstacles, and so it can plan the path safely. 609 (a)Traditional ant colony (b) Improved ant colony Fig.3 The effect of two ant colony algorithm for planning paths Fig.4 Comparison curves of the path security Fig. 5 shows the effect of the two planning methods in the area of 1000m 1000m path planning map, the lower-left corner of the map as a starting point, the upper right corner as the end point, by comparison of figure (a) and figure (b) show that, relative to the basic ant swarm optimization, improved ant colony algorithm path planning in large-size area is safe. Table I shows the different environmental modeling method in Fig. 5. We can see from 1000m*1000m large-size regional modeling results, the number of nodes of the quadtree method of modeling is far less than the number of nodes of the grid method, quadtree law in regard to the gate grid method, information on the environment for effective compression. Table I I shows the two planning methods used in figure 5 shows the quadtree and improved ant colony algorithm mixed planning strategy of consuming about 1.1% of the mixed strategy of the grid method and the basic ant colony algorithm, therefore, quad trees and improved ant colony algorithm for hybrid planning strategy to improve the efficiency of path planning of large-size region. (a) Grid method + basic ant colony algorithm (b) The quadtree + improved Ant Colony Algorithm Fig.5 The effect of two methods of path planning TABLE I Comparison of Two Methods of Environmental Modeling Environmental modeling Free nodes number Obstacles nodes number Total Grid method 95000 50000 1000000 Quadtree 4300 3200 7500 TABLE I I Two Path Planning Method to Perform Efficient Path planning method Time (ms) Grid method + basic ant colony algorithm 120384 The quadtree + Improved Ant Colony Algorithm 1396 V. C ONCLUSION This paper presents the path planning method combining quadtree and improved ant colony algorithm. Basic ant colony algorithm has been improved , making the improved ant colony algorithm for planning the path and the obstacles to maintain a safe distance, and the use of the quadtree to model the environment, complete preservation of the environment information at the same time greatly compresse d environmental information, the two metho d s are a combination that not only can guarantee the security of the planned path, you can also improve the efficiency of large-size local path planning. Finally, simulation results illustrate the effectiveness of the proposed method. R EFERENCES [1] Caccia. M, Bono. R and Bruzzone G. Berge, “Variable-configuration UUVs for marine science applications,” IEEE Robotics and Automation Magazine , vol. 6, pp. 22-23, 1999. [2] Bandyopadhyay. P. R, “Trends in biorobotic autonomous undersea vehicles,” IEEE Journal of Oceanic Engineering , vol. 30, pp. 109-139, 2005. [3] Li-jun Zhang, Xue Qi, Yong-jie Pang, “Adaptive output feedback control based on DRFNN for AUV,” Ocean Engineering , vol 36, n 9, pp. 716-722, 2009. [4] Jia He-ming, Zhang Li-jun et al, “Three-dimensional path tracking control of underactuated AUV based on discrete-time sliding modeprediction,” Control and Decision , vol 26, n10, pp 1452-1458, 2011. [5] Ding Fu-guang, Jiao Peng, Bian Xin-qian, Wang Hong-jian, “AUV local path planning based on virtual potential field,” Proceedings of the IEEE International Conference on Mechatronics and Automation , Canada, 2005:1711-1716. [6] Zhang Qiao-rong, “A hierarchical global path planning approach for AUV based on genetic algorithm,” Proceedings of the IEEE International Conference on Mechatronics and Automation , Luoyang, 2006:1745-1750. [7] Zhu Da-qi, Yang Yuan-yuan, Yan Ming-zhong, “Path planning algorithm for AUV based on a Fuzzy-PSO in dynamic environments,” 2011 Eighth International Conference on Fuzzy Systems and Knowledge Discovery , 2011: 525-530. [8] Shi Bin,“The research of automatic route selection on virtual scenarios,” Harbin: Harbin Engineering University, 2008: 5-16. [9] Gong Jian-ya,“Linearity quad-tree code based on natural number,” ACTA GEODAETICA ET CARTOGRAPHICA SINICA . vol 21, n 2, pp 90-98, 1992. [10] X iao Le-bin, Gong Jian-hua, Xie Chuan-jie,“A new algorithm of searching neighborhood based on linear quadtrees and linear octree,” ACTA GEODAETICA ET CARTOGRAPHICA SINICA . vol 27, n 3, pp 195-203, 1998. [11] L EE J W, LEE J J ,“Novel ant colony optimization algorithm with path crossover and heterogeneous ants for path planning ,” Industrial Technology (ICIT). Chile, 2010: 559-564. 610