Xu Depeng, Le Ziying, Li Mengshan
College of Physics and Electronic Information, Gannan Normal University, Ganzhou, Jiangxi, China
Correspondence to: Li Mengshan, College of Physics and Electronic Information, Gannan Normal University, Ganzhou, Jiangxi, China.
Email:  
Copyright © 2019 The Author(s). Published by Scientific & Academic Publishing.
This work is licensed under the Creative Commons Attribution International License (CC BY).
http://creativecommons.org/licenses/by/4.0/
Abstract
With the rapid development of UAV technology and the popularization of UAV, UAV has begun to be widely used in various fields, but in view of the dense and complex flight environment, the security problems are constantly emerging. Based on the security problems in UAV flight, this paper proposes an A*BC algorithm for its route planning. The artificial bee colony algorithm is used to improve the A* algorithm. Combined with the advantages of the two algorithms, the UAV can quickly reach the target point while avoiding obstacles.
Keywords:
UAV, Security, A * algorithm, ABC algorithm
Cite this paper: Xu Depeng, Le Ziying, Li Mengshan, Research and Simulation of UAV Security Strategy Based on A*BC Algorithm, Computer Science and Engineering, Vol. 9 No. 1, 2019, pp. 15. doi: 10.5923/j.computer.20190901.01.
1. Introduction
The Unmanned Aerial Vehicle (UAV) is a kind of vehicle which is controlled by radio remote control equipment or the control program of its own. From the initial successful research and development to now, it has achieved rapid development in the application of technology. With the gradual maturity of UAV technology, the manufacturing cost and entry threshold are lowered, and it has gradually expanded from the initial military field to the consumer field. However, with the wide application of UAV technology, there are many security problems. As for the security problems caused by dense urban obstacles, route planning has become the key to the unmanned aerial vehicle research.UAV route planning is to plan one or more optimal or feasible flight routes from the initial point to the target point under a variety of constraints and restrictions. Among many route planning algorithms, A* algorithm [13], ant colony algorithm [4], genetic algorithm [57], neural network algorithm [8] and other algorithms have been widely studied and applied. However, these algorithms all have certain limitations in UAV route planning [910].In this paper, A UAV route planning method based on A*BC algorithm is introduced. The route planning is divided into large direction route planning and local small direction route planning, so that the UAV can safely fly towards the target point and improve obstacle avoidance efficiency at the same time. Among them, the A* algorithm is applied to the largedirection route planning, and artificial bee colony algorithm is used to replan local routes when obstacles need to be avoided in the flight process, effectively improving the reliability and efficiency of UAV route planning.
2. UAV Route Planning
2.1. Problem Description
Nowadays, with the popularization of UAV technology, UAV is mainly used in cities. However, dense obstacles in urban environment seriously threaten the flight safety. Then, it is necessary to make the unmanned aerial vehicle avoid obstacles accurately and reach the target point safely in the dense obstacle environment through route planning. FIG. 1 is the environmental schematic diagram constructed in this paper, in which the green point is the starting point of the UAV, the yellow point is the target point, and the black rectangular area is the static obstacle in the city.  Figure 1. Environment schematic 
2.2. Dynamic Grid Model of Unmanned Aerial Vehicle
Currently, unmanned aerial vehicles are mainly divided into three platforms, multirotor UAV and fixedwing UAV, according to the platform configuration. Among them, multirotor is often used in urban complex environment due to its simple operation and good mobility. Therefore, this paper adopts this one as the operating object, and takes the unmanned aerial vehicle as a maneuverable particle without considering the minimum turning radius and size. The idea of rasterization is used to define the flight interval of the particle UAV, and a raster model with the particle as the center moving in 8 directions is constructed. Figure 2 shows the raster model of UAV movement.  Figure 2. Dynamic grid model of unmanned aerial vehicle 
3. A*BC Algorithm for UAV Route Planning
In the process of UAV flight, obstacles encountered are generally divided into two categories: one is static obstacles, such as buildings, billboards, etc., and the other is dynamic obstacles, whose positions will change, such as birds and other flying objects. In the face of static obstacles, unmanned aerial vehicle only needs to make global route planning based on environmental information, but static obstacles cannot exist in the real environment. The randomness and unpredictability of dynamic obstacles have a greater impact on the flight safety of UAV. In view of such a dense and complex environment, UAV must carry out local route replanning on the basis of global route planning, so as to effectively avoid obstacles and ensure the flight safety.
3.1. General Direction A* Algorithm
In the global route planning, the global optimality of the route between the starting point and the target point should be considered. In this paper, A* heuristic algorithm is used to guide the UAV flight in the large direction. When using A* algorithm, we first define the following evaluation function for A* algorithm:  (1) 
In formula (1), is the evaluation function of the current node n, representing the total cost function of the optimal path from the initial node to the target node through the current node, is the actual cost function of the UAV starting node to the current node n, and is the estimated cost function of the current node n to the target node.
3.2. Local Direction Artificial Bee Colony Algorithms
Artificial bee colony algorithm [11], an optimization method imitating bee behavior, belongs to swarm intelligence algorithm. In 2005, it was proposed by Karaboga group of Ergiyes University in Turkey to solve the problem of multivariable function optimization. There are three main types of artificial bee colony in ABC algorithm: lead bee, follower bee and scout bee. The honey source sought by the bee colony is equivalent to the feasible solution of the optimal path. Detective bees are used to explore the source of honey. The number of lead bees and follower bees corresponds to the source of honey. The number of lead bees and follower bees is equal. And ABC algorithm has a role conversion mechanism, according to the behavior of individual bee colony, the role type of individual bee colony can be changed.In smalldirection route replanning, this paper uses artificial bee colony algorithm (ABC algorithm) to carry out UAV local route planning. When using artificial bee colony algorithm for route planning, there are the following steps:1. Initialization of honey source: In ABC algorithm, the honey source in the environment should be initialized first. The number of SN feasible solutions is determined by the number of leading bees. The formula for calculating the initial position of the honey source I is as follows:  (2) 
In formula (2), each solution is a Ddimensional vector, denotes the upper limit of the search space, and denotes the lower limit of the search space.2. Renewal search of new honey source: At the beginning of the search, leading bees to search around the current honey source is not equal to the new honey source of the current honey source.3. The following bee chooses the leading bee: When the following bee chooses the leading bee, it chooses the roulette way. The richer the honey source is, the higher the probability of choosing the honey source is.4. Producing scout bees: In ABC algorithm, there is a control parameter limit, which is used to record the number of times each solution is updated. In the search process, if the honey source I has not been improved after the limit iteration, the honey source is abandoned, and the corresponding leading bee of the honey source is transformed into a scout bee, and a new honey source is searched in the search space according to step 2.
3.3. UAV Flight Path Planning Algorithm
Through the experimental analysis of the current algorithms commonly used for UAV route planning, it is found that there are obvious shortcomings when using a single algorithm for route planning, but the advantages and disadvantages of the algorithms can be complemented, and the path planning algorithm can be improved to improve the feasibility in the urban dense obstacle environment. Through the analysis of A* algorithm and artificial bee colony algorithm, an A* BC algorithm is designed.In the A*BC algorithm, when the A* algorithm is used to guide the largedirection route, the realtime target points are set locally, and the artificial bee colony algorithm is used to replan the route and avoid obstacles, which can improve the safety and efficiency of UAV flight.A*BC algorithm is used to plan the path from the starting point to the target point in the following ways:  (3) 
Among them, and are the dynamic factors representing the current path planning algorithm. When planning the path from the starting point to the target point, ; while when UAV evades the current obstacle or dead zone, that is, when carrying out path replanning in the local small direction, is the total cost function of path planning of A* heuristic algorithm, and is the optimal path search function of artificial bee colony algorithm, and:  (4) 
In Formula (4), and means to find a new honey source which is not equal to I among SN honey sources.A*BC algorithm has the following steps:1. Target point initialization: Initialize the location of the target point in the global environment, and use A* algorithm to make the UAV fly towards the target point, and the total cost of the next target is always less than the total cost of the current target point, that is, , so that the planning direction is always at the minimum cost.2. Setting local target points: When facing dead zone or special obstacles during flight, setting local target points as the initial honey source of artificial bee colony algorithm.3. Path replanning: Realtime path replanning is carried out using artificial bee colony algorithm. If the bee colony reaches the local target point, it will continue to fly along the general path planned by A* algorithm. Otherwise, the local target point will be reset for path replanning.Figure 3 shows the workflow diagram of the A*BC algorithm.  Figure 3. A*BC algorithm route planning flow chart 
4. Simulation and Analysis
A* algorithm has global guidance, but in the flight process, the complex urban environment is easy to fall into the dead cycle of the algorithm, which leads to the inability to find the optimal path. Artificial bee colony algorithm has slow convergence speed, easy to fall into local optimum and low efficiency. The A*BC algorithm proposed in this paper can make unmanned aerial vehicle fly efficiently and reasonably in dense obstacle avoidance. It can not only make UAV reach its destination safely, but also save algorithm time. The following figure shows the simulation of route planning of three algorithms:  Figure 4. A* algorithm route planning simulation 
 Figure 5. Route planning simulation of artificial bee colony algorithm 
 Figure 6. Route planning simulation of A*BC algorithm 
It can be seen from the simulation chart of route planning of A* algorithm that when there are many optimal paths, A* algorithm can’t select the optimal solution completely and correctly. If the path between itself and the target points encounters obstacles, UAV will easily fall into local dead zone, which leads to the inability to plan the feasible flight path. In the face of complex obstacle environment, although the A* algorithm takes less time to plan the route, it is more likely to lead to the safety problems of UAV.In the simulation chart of route planning of artificial bee colony algorithm, the bee colony searches the honey source continuously to find the optimal path. Because the bee colony needs to go out constantly to find the new honey source, the convergence speed is slow. Although the optimal path can be found, the algorithm takes a long time.In the route simulation planning chart of A*BC algorithm, UAV reaches the target point by planning the optimal path, and according to table 1, you can know that the overall timeconsuming of the A*BC algorithm is shorter, which is better than the other two algorithms.Table 1. Timeconsuming comparison of three algorithms 
 

To sum up, by comparing the path planning of these three algorithms, we can see that A*BC algorithm is more suitable for unmanned aerial vehicles to fly safely in dense obstacle environment in city.
5. Conclusions
With the development of UAV technology, the use of unmanned aerial vehicle is becoming more and more popular. For the complex flight environment with dense obstacles, the flight safety deserves attention. By combining the advantages of A* algorithm and artificial bee colony algorithm, the A* BC algorithm proposed in this paper can help UAV to avoid obstacles effectively and plan better path, and solve some flight safety problems.
ACKNOWLEDGMENTS
The authors gratefully acknowledge the support from the National Natural Science Foundation of China (Grant Numbers: 51663001, 61741202 and 61741103).
References
[1]  FENG Guoqiang, ZHAO Xiaolin, GAO Guangen, KOU Lei, Path planning of UAVs using A* ant colony algorithm, Flight Dynamics, 2018, 36(5), 4952,57. https://doi.org/10.13645/j.cnki.f.d.20180614.001. 
[2]  ROBERT J S, PEGGY G I S, CLICKSTEIN, et al. Robust algorithm for algorithm for realtime route planning. IEEE Transactions on Aerospace and Electronic System, 2000, 36(3): 869878. 
[3]  Yao J F, Lin C, Xie X B. Path planning for virtual human motion using improved A* star algorithm, Proceedings of the 7th International Conference on Information Technology: New Generations. Las Vegas, NV: IEEE, 2010: 11541158. 
[4]  YE W, MA D W, FAN H D. Algorithm for low altitude penetration aircraft path planning with improved ant colony algorithm. Chinese Journal of Aeronautics, 2005, 18(4): 304309. 
[5]  Li Nan, Zhang Jianhua. UAV route planning based on improved genetic algorithm [J]. Computer simulation, 2016, 33 (4): 9194. 
[6]  Taharwa I A, Sheta A, Weshah M A. A mobile robot path planning using genetic algorithm in static environment. Journal of Computer Science, 2008, 4(4): 341344. 
[7]  FENG Wenyong, YANG Canjun, CHEN Ying. Research of genetic algorithm for the global path planning for ACR prototype system. Control Theory & Applications, 2002, 19(2): 282286. 
[8]  YANG S X, LUO C M. A neural network approach to complete coverage path planning. IEEE Transactions on Systems, Man & Cybernetics, 2004, 34(1): 718725. 
[9]  Wang Hongwei, Ma Yong, Xie Yong. Mobile Robot Optimal Path Planning Based on Smoothing A* Algorithm. Jourmal of Tongji University, Natural Science, 2010, 38(11): 16471650. 
[10]  Allaire F C J, Tarbouchi M.FPGA Implementation of Genetic Algorithm for UAV RealTime Path Planning. J Intell Robot Syst, 2009, 54: 495510. 
[11]  Karaboga, D., Basturk, B.. Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems. LNCS: Advances in Soft Computing: Foundations of Fuzzy Logic and Soft Computing, 2007, 45(29): 789798. 