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 [1-3], ant colony algorithm [4], genetic algorithm [5-7], neural network algorithm [8] and other algorithms have been widely studied and applied. However, these algorithms all have certain limitations in UAV route planning [9-10].

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 large-direction 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, multi-rotor UAV and fixed-wing UAV, according to the platform configuration. Among them, multi-rotor 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 small-direction route re-planning, 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 D-dimensional 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 large-direction route, the real-time target points are set locally, and the artificial bee colony algorithm is used to re-plan 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 re-planning 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 re-planning: Real-time path re-planning 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 re-planning.

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 time-consuming of the A*BC algorithm is shorter, which is better than the other two algorithms.

Table 1. Time-consuming 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).