Open Advanced Search
Get 20M+ Full-Text Papers For Less Than $1.50/day.
Start a 14-Day Trial for You or Your Team.
Learn More →
Path Planning of Multirotor UAV Based on the Improved Ant Colony Algorithm
Path Planning of Multirotor UAV Based on the Improved Ant Colony Algorithm
Qi, Duo;Zhang, Zhihao;Zhang, Qirui
Hindawi Journal of Robotics Volume 2022, Article ID 2168964, 9 pages https://doi.org/10.1155/2022/2168964 Research Article Path Planning of Multirotor UAV Based on the Improved Ant Colony Algorithm 1,2 1,2 3 Duo Qi , Zhihao Zhang , and Qirui Zhang Aviation Swarm Technology and Operational Application Laboratory, Air Trac Control and Navigation College, Air Force Engineering University, Xi’an, China Shaanxi Province Laboratory of Meta-Synthesis for Electronic and Information System, Xi’an, China Unit 93525 of PLA, Rikaze City, Xizang Province, China Correspondence should be addressed to Zhihao Zhang; firstname.lastname@example.org Received 29 November 2021; Revised 18 April 2022; Accepted 23 May 2022; Published 9 June 2022 Academic Editor: Ruthber Rodriguez Serrezuela Copyright © 2022 Duo Qi et al. ƒis is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Path planning is an important part of the unmanned aerial vehicle (UAV) to realize its autonomous capabilities. Aiming at the shortcomings of the traditional ant colony algorithm-based trajectory planning method, which has slow convergence speed and easy to fall into the local optimum, a path planning method based on the improved ant colony algorithm is proposed. First, a dynamic adjusting factor is added into the heuristic function to improve the directivity of path selection and search speed. ƒen, the state transition strategy is improved to solve the problem of slow convergence in the initial stage and easy to fall into local optimum in the later stage. Finally, the path in•ection point is smoothly optimized through the cubic B-spline curve. Simulation results show that the improved ant colony algorithm can quickly converge to the optimal path and well adapt to the •ight requirements of multirotor UAV. optimal control method [5, 6], as well as intelligent algo- 1. Introduction rithms such as the genetic algorithm [7, 8], ant colony al- With the continuous progress of science and technology, gorithm [9, 10], and particle swarm optimization algorithm especially the continuous development of microelectronic . technology and microelectromechanical technology, UAV ƒe classical algorithm is generally only suitable for has been widely used in military and civil ˜elds. Compared simple spatial path planning. In the face of complex with large UAVs, small UAVs have a broader application problems, the di™culty of solving them increases expo- space in the ˜elds of police, rescue and disaster relief, tra™c nentially with the increase of dimension, which has certain management, news media, aerial photography, geological limitations. With the development of computer and big data survey, environmental evaluation, pipeline inspection, and technology, intelligent algorithms have more and more so on. Among them, the multirotor small UAV, as a typical obvious advantages of good robustness, positive feedback representative, has developed particularly rapidly in recent mechanism, and self-organization. Taking the ant colony years and received the focus of researchers. algorithm as an example, theoretically, it can ˜nd the op- Path planning is one of the key technologies for UAV to timal solution of the path, which is suitable for path planning realize autonomous •ight. A large number of scholars have in complex environment. However, in practice, we must done research on it and achieved a lot of results. In fact, path consider the problems of how to shorten search time, speed planning is to ˜nd an optimal •ight path from initial point to up convergence, and jump out of local optimal. Li et al.  target point under certain constraints. Common planning introduced a weight factor into the probability transfer methods include classical algorithms such as the A (A-star) function and improved the updating way of information. algorithm [1, 2], arti˜cial potential ˜eld method [3, 4], and ƒe simulation results showed that the convergence speed of 2 Journal of Robotics the improved algorithm is improved, and the optimal path is electronic map are shown in Figure 1. .e map is numbered shorter, but the search results are not stable. Wu et al.  from left to right and top to bottom. .e grid serial number adopted the method of integrating the current optimal track corresponds to coordinates one by one, and the expression pheromone and the historical optimal track update, intro- of the relationship between them is shown in equation (1). duced the pheromone rollback clearing mechanism, and .e result obtained is the center point of the grid. carried out oﬄine calculation, which improved the search x � r × mod(i, R) − 0.5, eﬃciency, but did not signiﬁcantly reduce the number of (1) y � r × (R + 0.5 − ceil(i, R)) − 0.5, iterations. Wang et al.  used the artiﬁcial potential ﬁeld method to improve the heuristic function of the ant colony where r is the grid size, i represents the number of the grid, R algorithm, allocated pheromones reasonably when the al- is the number of rows of the grid matrix, mod () is the gorithm is not running, and improved the volatilization remainder operation function, and ceil () is the rounding up coeﬃcient to ﬁnd the optimal path of the algorithm. operation function. It can be seen that many research studies are all based on In order to prevent the collision between UAV and the traditional ant colony algorithm and have achieved obstacles, when the obstacle is less than one grid, it is ﬁlled certain results. However, the traditional ant colony algo- into a complete grid. At this time, the UAV is treated as a rithm has the shortcomings of slow convergence speed and particle. easy to fall into local optimum, which is not applicable to the .e ﬂight rules of UAV are as follows: it can only appear real ﬂight environment. Aiming at the defects of the basic ant in the white grid and cannot pass through the black grid, but colony algorithm, an improved ant colony algorithm is it can pass through the four corners of the black grid; it is proposed in this study to make it suitable for path planning forbidden to repeat the same grid; and in unit time, it can of multirotor UAV. First, a dynamic adjusting factor is only move between two adjacent grids. We use Euclidean added into the heuristic function to improve the directivity distance to measure the length of the ﬂight path. For ex- of path selection and search speed. .en, the state transition ample, if moving up, down, left, and right, the path length is strategy is improved to solve the problem of slow conver- 1 unit and if moving to the four corners of the grid, the path gence in the initial stage and easy to fall into local optimum length is 1.41 units. in the later stage. At the same time, combined with the existing pheromone volatilization factor update strategy, the overall performance of the algorithm is improved. Finally, 3. Basic Ant Colony Algorithm the path inﬂection point is smoothly optimized through the cubic B-spline curve, so that the path planning of multirotor Ant colony algorithms are inspired by the foraging behavior UAV is more in line with the ﬂight reality. of ant populations, in which each ant in the colony leaves .e study is organized as follows: Section 2 describes the pheromones in its movement path to communicate infor- environment in which the UAV performs its mission. mation to the colony. .e shorter the moving path is, the Section 3 introduces the basic principle and deﬁciency of the higher the pheromone concentration is, and the probability ant colony algorithm. Section 4 improves the shortcomings that the path is selected by ants, which forms the positive of the ant colony algorithm and proposes the UAV track feedback mechanism for ants to ﬁnd the shortest path. .e planning method and smoothing method. In Section 5, the basic principle of the ant colony algorithm is as follows. proposed algorithm is simulated and analyzed, which ver- Ants select paths according to pheromone concentration iﬁes the eﬀectiveness of the proposed algorithm. Finally, the and heuristic function, and the probability of ant k moving full text work is summarized and the next research direction from grid i to grid j can be expressed as is pointed out. ⎧ ⎪ α β α β ⎪ ⎝ ⎠ ⎛ ⎞ τ (t)η (t)/ τ (t)η (t) , s ∈ A , k ij ij is is k 2. Environmental Model P � (2) ij ⎪ s∈A In order to accurately describe the path planning process of 0, s ∉ A UAV, its two-dimensional environment map [15, 16] needs where α is the pheromone heuristic factor and β is the to be modeled. .e conventional environment modeling distance expectation function factor, which aﬀect the im- methods include the grid method [17, 18], geometric in- portance of pheromone and distance heuristic function, formation method, and view method. Considering that the respectively, A indicates the next destinations ants can grid method has the advantages of simple drawing, clear data reach, τ (t) is the pheromone concentration on the moving ij structure, and easy implementation, we select the grid path at time t, and η (t) represents the distance heuristic ij method to complete the UAV ﬂight environment modeling. function. Here, .e grid method decomposes the plane map into a series of grids to facilitate the analysis of map information. .e grid map is composed of 0 and 1 matrices with binary values. In η (t) � , ij ij the matrix, 0 stands for free grid, in which the UAV can enter (3) and exit freely, represented by white grid, and 1 stands for ����������������� obstacle grid, in which the UAV needs to move around, and 2 d � x − x + y − y . ij i j i j represented by black grid. .e grid environment and the Journal of Robotics 3 02468 10 Figure 1: Grid map and electronic map. Each ant will leave a certain amount of pheromone when where d is the Euclidean distance between j and the target jE moving. .erefore, when the algorithm iterates continu- point, iter is the current number of iterations, and iter is max ously, the pheromone content in the path gradually accu- maximum number of iterations. mulates and volatilizes at the same time. When all ants in the population complete each round of iteration, the pheromone content on the path will be updated according to the fol- 4.2. 8e Improved State Transition Rule. In the basic ant lowing rules: colony algorithm, ants mainly rely on the probability function to select the next node. However, in the early stage τ (t + 1) � (1 − ρ)τ (t) + Δτ (t), ij ij ij of the algorithm, the diﬀerence between the pheromone concentrations of the path is very small, which cannot ef- τ (t) � Δτ (t), ij ij fectively guide the ant to choose the path. Based on the initial (4) k�1 transition probability, the convergence speed of the algo- Q/L , k rithm is guaranteed by introducing pseudorandom rules. Δτ � ij .e ant will select the next node j according to the following 0, formula. where ρ is the pheromone volatilization coeﬃcient, Δτ represents the sum of pheromones released on the path ij ⎧ ⎪ max