Keywords

1 Introduction

With the rapid development of automatic control and artificial intelligence, the unmanned aerial vehicle (UAV) is widely used in various scenarios, such as disaster rescue, exploration of unknown environment, precise attacking targets in the battlefield and the coverage exploration task [1]. The development of this field can greatly improve the efficiency of task completion and avoid unnecessary casualties, which is of great significance for the military and civil applications.

Many researches have conducted intensive study on UAV path planning with the goal of enabling the UAV to complete complex tasks independently. UAV path planning corresponding to the allocation task is shown in Fig. 1. At present, swarm intelligence (SI) optimization with advantages of scalability, parallel processing and compatibility for the UAV group, such as ant colony optimization (ACO) [2], particle swarm optimization (PSO) [3], differential evolution (DE) [4], fruit fly optimization algorithm (FOA) [5] and gray wolf optimization (GWO) [6] has been applied in the field of UAV path planning extensively.

Fig. 1.
figure 1

UAVs path planning of the allocation task.

Full size image

For the scene of auxiliary information acquisition by UAVs in wireless sensor network, K-means and improved max-min ACO are combined for UAV path planning [7]. In [8], the pheromone update is implemented after the selection of ants by metropolis criterion to improve the convergence speed of ACO and avoid local optimum. In [9], ACO is utilized for UAV path planning in the presence of U-type obstacles. The waypoints that have been visited can be accessed again. [10] studies path planning of the UAV in urban environment, which focuses on the risk assessment. Based on the proposed risk cost map, an improved A* algorithm and ACO are proposed.

As far as PSO is concerned, [11] utilizes the spatial refined voting to solve the local optimum and convergence problems of PSO, and applies the proposed algorithm to path planning for the UAV group in the rendezvous task. With the similar background of the formation rendezvous mission, the elite keeping strategy distributed cooperative PSO is proposed in [12], which considers the optimal solution of sub-swarm and cooperation cost. In [13], an improved PSO algorithm is applied to 3D UAV group path planning, which utilizes the chao-based Logistic map to generate random initialization and the adaptive linear-varying strategy to adjust parameters of PSO. Controller area network bus is utilized to solve the real-time problem of PSO based UAV path planning in [14]. [15] combines the exploration of PSO with the exploitation of symbiotic organizations search [16]. In order to avoid local optimum, Metropolis criterion is introduced into PSO in [15], and the parameters in PSO are linear variation.

Corresponding to DE, in order to obtain the optimal path, the adaptive selection mutation constrained DE which consists of constraint violation to determine the feasibility of individuals is proposed in [17]. In [18], the DE algorithm combined with model predictive control is proposed to solve the problem of UAV path planning in partially known environment. The DE based on the knee point is proposed in [19] to enhance the convergence speed of traditional DE. [20] combines 2 improved DE algorithms, and applies different DE algorithms according to different fitness to enhance exploration and exploitation capabilities.

In terms of FOA, according to the oilfield inspection, [21] proposes the optimal reference point based FOA. In the path planning part, the cost function is equivalent to the smell concentration judgment function in FOA, and the reference point is able to improve the convergence speed of FOA. The multiple swarm FOA (MSFOA) is proposed in [22]. MSFOA divides all fruit flies into multiple swarms to expand the search space and increase the exploration of the algorithm. In order to avoid local optimum, optimal solutions of other swarms are introduced when the offspring are produced. In [23], the quantum behavior-based enhanced FOA (QFOA) is proposed, which utilizes the quantum behavior theory to replace random search in the original FOA, in order to jump out of the local optimal. Finally, the application of QFOA in 3D UAV path planning is given in [23].

GWO is an emerging intelligence optimization technic in recent years. In [24], a simplified GWO and modified SOS algorithm is proposed, in order to combine the exploration of GWO and the exploitation of SOS with low complexity. In addition, the GWO algorithm based on reinforcement learning is proposed in [25], which is divided into four steps: exploration, exploitation, geometric adjustment and optimization adjustment. The exploration is completed by the GWO, and the next three steps are implemented by Q-learning.

This paper summarizes various UAV path planning algorithms based on SI optimization in recent years, and analyzes the characteristics and application scenarios of different algorithms. In the rest of the paper: Sect. 2 illustrates mathematical model of multi-constraint optimization in UAV path planning. Section 3 give recent developments of UAV path planning based on SI optimization. Section 4 carries out features comparison and analysis application scenarios. Finally, Section 5 concludes the paper.

2 Multi-constrained Optimization in UAV Path Planning

Fig. 2.
figure 2

UAV path planning diagram.

Full size image

As shown in Fig. 2, the entire UAV path planning need task allocation, determine constraints, construct objective function, search for optimal solution and path smoothing generally. For the multi-tasks situation, the task allocation is processed for each UAV individual to satisfy the requirements of minimum fuel consumption or minimum complement time. After that, the determination of constraints and construction of the corresponding objective function according to the actual environment and the capability of UAVs are implemented. The appropriate mathematical tools are utilized to obtain the optimal solution. Finally, path smoothing is essential for generating a feasible UAV path. In the process of UAV path planning, searching for optimal solution is the most critical and tricky part. This determines that collision of UAV individuals, whether the UAVs pass through the high threat area, and the degree of satisfaction for various constrains.

Fig. 3.
figure 3

UAV path planning diagram.

Full size image

Searching the optimal solution in path planning is essentially an optimization problem with multiple constraints. For example, for the allocation task scenario in the UAV group, its mathematical model can be expressed as [1]:

$$\begin{aligned} \begin{aligned}&\mathrm{min}\sum _{k=1}^{h}J_{k}(L_{1},L_{2},...,L_{n}/E) \\&\mathrm{s.t.}~~f(L_{1},L_{2},...,L_{n}/E)=0, \\&~~~~~~g(L_{1},L_{2},...,L_{n}/E)\ge 0. \end{aligned} \end{aligned}$$
(1)

where h is the number of objective functions, \(J_{k}\) is the kth objective function, the distinct constrains are f and g respectively, \(L_{i}\) is the ith UAV path to be optimized, and E is the environmental factor. SI optimization which is inspired by biological swarm behavior can be utilized to solve the optimization problem such as Eq. 1. The diagram of most SI optimization is shown in Fig. 3. In recent years, the research of UAV path planning based on SI optimization mainly focuses on the following aspects.

3 Recent Developments of UAV Path Planning Based on Swarm Intelligence Optimization

3.1 Ant Colony Optimization (ACO)

Dorigo M. proposed ACO in 1996 [2], which simulates the foraging behavior of ant colony. Each ant individual leaves pheromone on its walking path, while other ants choose the path by the concentration of pheromone. In order to avoid local optimum, ACO introduces evaporation mechanism: the pheromone on the map will evaporate to a certain extent over time. The pheromone updating formula is

$$\begin{aligned} \begin{aligned} \tau _{ij}(t+1)=(1-\rho )\tau _{ij}(t)+\varDelta \tau _{ij}. \end{aligned} \end{aligned}$$
(2)

With the large pheromone evaporation coefficient \(\rho \), ACO tends to exploration. Alternatively, the exploitation is processed in the ACO. The UAV path planning based on ACO need the map with grid form, several ants are sent out in parallel, and the forward direction is determined according to the pheromone concentration and transition probability [7,8,9,10]. However, the path obtained from the grid form map is likely not the optimal solution. In addition, there are many parameters in the ACO algorithm, which means a lot of parameters selection, with purpose to improve the performance of ACO based UAV path planning.

3.2 Particle Swarm Optimization (PSO)

PSO is inspired by the behavior of the bird swarm, and each particle moves in its solution space at the certain speed [3]. When updating the particle velocity in the each iteration, inertia, particle’s previous best value and group’s previous best value are considered mutually. These three factors jointly determine the exploration and exploitation of PSO. The update formula of PSO is

$$\begin{aligned} {\left\{ \begin{array}{ll} &{}v_{ij}(t+1)=v_{ij}(t)+c_{1}r_{1}(t)[p_{ij}(t)-x_{ij}(t)]+c_{2}r_{2}(t)[p_{gj}(t)-x_{ij}(t)],\\ &{}x_{ij}(t+1)=x_{ij}(t)+v_{ij}(t+1), \end{array}\right. } \end{aligned}$$
(3)

where the speed of exploration and exploitation is influenced by the acceleration coefficients \(c_{1}\) and \(c_{2}\) collectively. The UAV path planning based on PSO needs to determine the particle dimension corresponding to the number of waypoints, randomly generate the initial position of particles, and iterate according to Eq. 3 [11,12,13,14,15]. The PSO based UAV path planning needs to fix the number of waypoints in advance and cannot adjust in the iterative processing, that means the PSO is difficult to balance the computational complexity and optimality for the complex environment. Similarly, the selection of parameters will affect the exploration and exploitation ability of PSO.

3.3 Differential Evolution (DE)

Storn R. proposed DE in 1996 [4]. Unlike the genetic algorithm, the mutation operation of DE can generate more diverse individuals to avoid local optimum. Compared with other swarm intelligent optimization, DE is easy to achieve, so it is suitable for the situation with high real-time requirements. The mutation formula of DE with DE/rand/1/bin strategy is

$$\begin{aligned} {\boldsymbol{v}}_{i,G+1}={\boldsymbol{x}}_{r_{1},G}+F\cdot ({\boldsymbol{x}}_{r_{2},G}-{\boldsymbol{x}}_{r_{3},G}), \end{aligned}$$
(4)

where the value of constant factor F controls DE to perform exploration or exploitation. The UAV path planning based on DE includes initialization, mutation, crossover and selection operations [17,18,19,20]. Improving the convergence speed, exploration and exploitation ability are also the key factors to advance the performance of DE. Its disadvantage is similar to PSO, which requires fixed amount of waypoints.

3.4 Fruit Fly Optimization Algorithm (FOA)

FOA imitates the foraging behavior of fruit flies [5]. Individuals implement the olfactory search according to the smell concentration, and then determine the location of food by vision. FOA has few parameters, which is suitable for the real system implementation. The iterative formula is

$$\begin{aligned} {\left\{ \begin{array}{ll} &{}X_{i}=X\_axis+RandomValue,\\ &{}~Y_{i}=Y\_axis+RandomValue, \end{array}\right. } \end{aligned}$$
(5)

where the probability distribution of RandomValue decides the FOA to execute exploration or exploitation. The olfactory search and visual search are carried out successively to realize the UAV path planning based on FOA [7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23]. There are few parameters in PSO, so it does not need intricate parameter selection process. However, the selection of RandomValue distribution in the olfactory search affects its convergence speed and search ability.

3.5 Grey Wolf Optimization (GWO)

GWO is inspired by gray wolves hunting activities with the characteristics of effective convergence, few parameters and easy implementation [6]. The gray wolf community has a strict principle of hierarchy, and the inferior gray wolves such as \(\omega \) wolves must obey orders of leaders. The main processes of GWO are encircling the prey and hunting, which can be expressed as

$$\begin{aligned} {\left\{ \begin{array}{ll} &{}\vec {X}(t+1)=\vec {X}_{p}(t)-\vec {A}\cdot \vec {D},\\ &{}\vec {X}(t+1)=\frac{\vec {X}_{1}+\vec {X}_{2}+\vec {X}_{3}}{3}. \end{array}\right. } \end{aligned}$$
(6)

For \(\left| A\right| >1\), GWO tends to carry out the exploration, while for \(\left| A\right| <1\), GWO tends to the exploitation. The UAV path planning approach based on GWO [24, 25] is similar to the above. In order to avoid local optimal, the positions of \(\alpha \) wolves, \(\beta \) wolves and \(\delta \) wolves are considered collectively during updating. However, this strategy weakens the exploitation ability, hence balancing the exploration and exploitation in the UAV path planning based on GWO is also a factor to enhance the performance of this algorithm.

4 Features Comparison and Application Scenarios

For most of current UAV path planning algorithms based on SI optimization, the improvement direction focuses on speeding up the convergence of algorithms and avoiding local optimum. Next, various UAV path planning algorithms based on SI optimization in recent years are compared in terms of application dimension, avoiding local optimum, applicability for UAV group and real-time performance in Table 1.

According to the analysis in Table 1, the applicable scenarios of various path planning algorithms based on SI optimization is given as follow: For the intricate environment, the algorithms supporting 3D environment in Table 1 can be utilized for UAV path planning. The algorithms which apply to the UAV group are available for multi-UAVs scenarios, due to the collision avoidance between UAV individuals is considered. Given the real-time performance, [14] and [19] are good options.

Table 1. Features comparison of SI optimization based UAV path planning, where stands for support, \(\times \) stands for unsupport.
Full size table

5 Conclusions

In this paper, the UAV path planning based on SI optimization in recent years is summarized, including ACO, PSO, DE, FOA and GWO. In addition, multi-constrained optimization in UAV path planning is described with respect to the mathematical model. Moreover, the performance of different algorithms is compared in terms of application dimension, avoiding local optimum, applicability for UAV group and real-time performance. Finally, this paper gives the practical application scenarios for different algorithms.