A Cauchy mutant pigeon-inspired optimization–based multi-unmanned aerial vehicle path planning method

Abstract

To improve the performance of multi-unmanned aerial vehicle path planning in plateau narrow area, a control strategy based on Cauchy mutant pigeon-inspired optimization algorithm is proposed in this article. The Cauchy mutation operator is chosen to improve the pigeon-inspired optimization algorithm by comparing and analyzing the changing trend of fitness function of the local optimum position and the global optimum position when dealing with unmanned aerial vehicle path planning problems. The plateau topography model and plateau wind field model are established. Furthermore, a variety of control constrains of unmanned aerial vehicles are summarized and modeled. By combining with relative positions and total flight duration, a cooperative path planning strategy for unmanned aerial vehicle group is put forward. Finally, the simulation results show that the proposed Cauchy mutant pigeon-inspired optimization method gives better robustness and cooperative path planning strategy which are effective and advanced as compared with traditional pigeon-inspired optimization algorithm.

Keywords

Unmanned aerial vehicle path planning pigeon-inspired optimization algorithm Cauchy mutant

Introduction

Path planning is the first step in a moving multi-agent mission system. To distinguish from path management, path planning aims to find a set of waypoints from a start position to a target position to instruct agents moving.¹ While path management aims to generate feasible trajectories based on waypoints which are parameterized by time and could be described by twice-differentiable polynomials. Path management is necessary for most of the intelligent agents, for example, unmanned aerial vehicles (UAVs), which are unable to move along zigzags paths which are simply generated by connecting the waypoints.

Two decades ago, path planning problem focus on the ground moving robot mission with known threat locations. The path planning method based on randomly sampling search algorithms such as rapidly exploring random tree, probabilistic roadmap and Voronoi diagram approach are able to give a near optimal solution.^2–4 Unfortunately in some complex environments, for example, when unpredictable obstacles exist, these randomly sampling search algorithms usually cannot construct feasible paths for robots. As a result, this contradiction promotes the motivation to work out more practical path planning strategy. To implement path planning in complex environment effectively and efficiently, about a decade ago many traditional heuristic algorithms, such as spares A* algorithm, D* algorithm and model predictive control (MPC), are utilized to develop more advanced path planning strategies.^5–9

In recent decade, three-dimensional (3D) UAV cooperative mission path planning problem attracts prime attention since the traditional heuristic-based path planning methods suffer more and more challenges that resulted from realistic mission requirements, physical constrains of devices and complex environmental threats. The traditional heuristic path planning strategies are unable to give an optimal or sub-optimal solution rapidly and accurately in the new difficult mission settings, they have slow search speed and easily fall into local areas. To find paths timely and effectively with minimum fuel consumption and collision free in 3D cluttered complex environment, artificial intelligence (AI)–based path planning method attracts wide publicity. This kind of algorithms are inspired from nature including simulated annealing (SA), genetic strategy (GS) algorithm, ant colony (AC) algorithm, artificial neural network (ANN) algorithm, pigeon-inspired optimization (PIO) algorithm, bat strategy algorithm (BA) and artificial bee colony (ABC) algorithm. These AI algorithms can work out the near optimal paths in 3D complex cluttered environment with fast convergence speed, but sometimes, the research process may also fall into local optimization.^10–18 To improve the optimality of solutions obtained by AI-based path planning algorithm, many researchers dedicate their efforts. Wu et al.’s¹⁹ metropolis criterion which is based on probability theory is utilized to obtain new individuals for traditional particle swarm optimization (PSO) algorithm. In an advanced path planning strategy, chromosome-encoding strategy is proposed for conventional genetic algorithm to guarantee a feasible path to avoid the searching circulation. While a call back mechanism is designed in for traditional bee colony algorithm to give a shortest and safest path.^20,21

In this article, multi-UAV co-operative path planning problem in plateau narrow area is defined. By comparing with other 3D sceneries, mountainous plateau environment provides more challenges for UAV path planning, for example, dangerous peaks and unpredictable meteorological factors like atmospheric turbulence, wind shear and so forth.²² These disadvantages will seriously affect the stability of UAV co-operative flight. When implementing path planning in this extremely complex workspace, an AI path planning algorithm with fast convergence speed is urgently required. A new kind of swarm intelligence optimization algorithm based on pigeon homing behavior algorithm is proposed in Duan and Qiao,¹² called PIO algorithm. The most remarkable advantage of PIO algorithm is its fast convergence speed.

The algorithm consists of two independent computing sections: geomagnetic navigation section and landmark navigation section, which simulates the navigation mechanism of pigeons using different navigation tools at different stages in the process of finding their destination. Specifically, pigeons first adjust their direction through geomagnetic field and solar altitude, and then they will judge the direction and location by the landmark information adjacent to the destination. Inspired by the process by which pigeons find their nest and the similarity of the process with UAV path planning process, that is, both have multi-objective optimization problems with known starting and ending points, it is feasible to apply the pigeon’s behavior model for the path planning of UAVs.

However, due to the high complexity of plateau narrow area and its internal attribution, PIO algorithm is easy to fall into local optimum in the early stage of operation, resulting in unsatisfactory results. The best way to avoid local optimum is to increase the diversity of population. In this article, mutation operator is employed for map and compass operator. Normally, mutation operator is used in genetic operation to ensure population diversity, which is similar to the process of biological variation. Mutation operation could create a new individual by changing some information of an original individual. In general, mutation operators²³ include bit element mutation, boundary mutation, uniform mutation, Cauchy mutation and so on.

By comparing and analyzing the changing trend of fitness function of the local optimum position and the global optimum position when solving UAV path planning problems, Cauchy mutation operator is chosen to improve the PIO algorithm, the new algorithm is called Cauchy mutation PIO (CM-PIO) algorithm. This improved PIO algorithm can effectively extend the search area by mutation operation and could ensure that the pigeons can fly to the global optimal solution quickly. It can also reduce the risk that the solution will fall into the local optimal. Cauchy mutation operator aims to change the individual’s state value by selecting random numbers obeying Cauchy distribution, and to realize individual variation. In addition, considering the length and location information of each UAV path, a cooperative path planning strategy for multiple UAV is designed.

The main contributions in this article are as follows:

The integrated model of multi-UAV co-operation path planning problem is established including plateau topography model, plateau wind field model, a variety of constrains of UAV, including maximal flight length, minimal length of leg, maximal turning angle, maximal climb/dive angle and maximal flight altitude and the expression of fitness function.

For the reason that conventional PIO algorithm easily falls into a local optimal area when solving multi-UAV co-operative path planning problem in plateau narrow area, during PIO iteration process, Cauchy mutation operator is added into map and compass operator. This improved PIO algorithm (CM-PIO algorithm) is able to provide better solution than conventional one.

Based on the proposed CM-PIO algorithm, a co-operative path planning strategy for multiple UAVs is presented, where a coordination coefficient is designed to consider the length and location information of each UAV path.

The organization of this article are as follows: section “Problem formulation” defines the complete problem formulation constraints, that is, UAV parameters, terrain constraints, wind field model, the cost of path and multi-objective optimization model which is followed by section “PIO Algorithm,” which discusses the PIO algorithm. Section “CM-PIO-based path planning” defines the CM-PIO-based path planning of UAVs. In section “Cooperative path planning strategy,” the path planning strategy is discussed. Section “Simulation results and discussion,” defines the simulation results and its discussion. Finally, section “Conclusion” concludes the whole article.

Problem formulation

UAV’s parameters

Each UAVs have their own parameters, taken from Hebecker et al.²⁴ and Jian et al.,²⁵ such as maximum range limit, the shortest route limit, maximum turning angle limit, maximum climb/dive angle limit and maximum flight altitude limit.

Maximal flight length

The maximal flight length of UAV is limited by the amount of fuel. Besides, when UAV flies through a wind field, the drag becomes larger and causes an increment in the consumption of fuel. However, when passing through the mountain areas, the UAVs have the action of climbing or descending. In this case, the energy consumption of the UAV is higher. So, the maximal flight length will be limited. Assuming that the maximal flight length is $L_{max}$ and a complete path is divided into $n$ sections. $l_{i}$ , represents the length of section i, the flight length should satisfy

\sum_{i = 1}^{n} l_{i} \leq L_{max}

(1)

Minimal length of leg

When UAV flies in a leg, it needs some time to adjust their altitude to reach the next leg. To ensure flight safety and quality, the length of leg must be more than the smallest value. The length of every legs should satisfy

{\begin{matrix} l_{i} = \sqrt{{(x_{i} - x_{i - 1})}^{2} + {(y_{i} - y_{i - 1})}^{2} + {(z_{i} - z_{i - 1})}^{2}} \\ l_{i} \geq l_{min} (i = 1, 2, . . ., n) \end{matrix}

(2)

Maximal turning angle

The maximal angle between the directions in current leg and next leg are called the maximal turning angle. To avoid mountains, sometimes UAVs have to change their flight direction. But, the maximal turning angle of UAV is limited by its maneuverability. The real turning angle must be smaller than their maximal turning angle. Assuming $a_{i}$ and $a_{i + 1}$ represent the projection of the sections i and $i + 1$ , respectivley. The legs on horizontal plane, $φ_{max}$ , represents the maximal turning angle. $a_{i}$ and $a_{i + 1}$ should satisfy

\frac{a_{i}^{T} a_{i + 1}}{| a_{i} | | a_{i + 1} |} \geq \cos φ_{max}, i = 1, 2, \dots, n - 1

(3)

Maximal climb/dive angle

Maximal climb/dive angle refers to the maximal angle to which UAV is able to climb or dive relative to horizontal flight, and the maximal climb/dive angle is expressed as $ϑ_{max}$ . Assuming $p_{i}$ and $p_{i + 1}$ represent the ith waypoint and $(i + 1) th$ waypoint with the coordinates $(x_{i}, y_{i}, z_{i})$ and $(x_{i + 1}, y_{i + 1}, z_{i + 1})$ , respectively. While, $p'_{i}$ and $p'_{i + 1}$ represents the projection of $p_{i}$ and $p_{i + 1}$ on horizontal plane, the following relationship should be satisfied as

\frac{| z_{i + 1} - z_{i} |}{\sqrt{{(x_{i + 1} - x_{i})}^{2} + {(y_{i + 1} - y_{i})}^{2}}} \leq \tan ϑ_{max}

(4)

Maximal flight altitude

When flying at low temperature environment, which is one of the main features of plateau, performance engine always suffers degradation. The maximal flight altitude of UAV is lower than that in plain areas. Assuming the maximal altitude is $H_{max}$ , the real-time altitude $H_{i}$ cannot exceed its maximal altitude, that is

H_{i} < H_{max}

(5)

Terrain constraint

A function commonly used in terrain simulation is used to generate datum terrain and peak terrain in Chao.²⁶ The expression of datum terrain function is

\begin{matrix} Z_{1} (x, y) = \sin (y + a) + b \cdot \sin (x) + c \cdot \cos (d \sqrt{x^{2} + y^{2}}) \\ + e \cdot \cos (x) + f \cdot \sin (f \sqrt{x^{2} + y^{2}}) + g \cdot \cos (y) \end{matrix}

(6)

where $a, b, c, d, e, f, g$ are all constants, $x$ and y are the horizontal coordinates and $Z_{1}$ is the altitude at a certain horizontal position. The values of $a, b, c, d, e, f, g$ are relative to the degree of height fluctuation.

The expression of peak terrain function is

Z_{2} (x, y) = \sum_{i = 1}^{i = N} h_{i} \exp [- {(\frac{x - x_{0 i}}{x_{si}})}^{2} - {(\frac{y - y_{0 i}}{y_{si}})}^{2}] + Z_{0}

(7)

where $(x_{0 i}, y_{0 i})$ represents the position of the center of ith peak projecting on the ground plane. $h_{i}$ is the altitude of the peak i. $(x_{si}, y_{si})$ represents the decline scale along the $x$ direction and $y$ direction of the peak i. While, $Z_{0}$ represents the base altitude. $N$ represents the number of peaks.

Combining the datum terrain function and peak terrain function, the plateau terrain will be described as

Z (x, y) = max (Z_{1}, Z_{2})

(8)

which is depicted in Figure 1.

Figure 1.

The 3D plateau terrain.

Wind field model

When UAVs fly in plateau mountainous area, their speeds and altitudes will be disturbed by wind. As a result, it is difficult to maintain a fixed formation of flight and even brings disadvantage to the flight safety. In this research, the wind field is taken as a threat area and the spherical model is used to represent the wind field which is written as

(x - x_{k 0})^{2} + (y - y_{k 0})^{2} + (z - z_{k 0})^{2} \leq {r_{k}}^{2}

(9)

where $(x_{k 0}, y_{k 0}, z_{k 0})$ is the center of $k$ the wind field, $r_{k}$ represents the radius of its spherical model. In the co-operative path planning process, the wind field should be avoided as far as possible.

The cost of path

The cost of path is an important index to evaluate the quality of a planned path. The purpose of path planning is to find a suitable path with the lowest cost of path. Based on the actual flight environment and the UAV’s performance, the cost of path is classified into three sectors: distance cost, altitude changing cost and threat cost.

Distance cost

The limited amount of fuel must be taken into account in path planning. So, the flight distance should be shortened as far as possible. Assuming that a complete path is composed of $n$ legs, the distance cost is expressed as

f_{L} = \sum_{i = 1}^{n} l_{i}

(10)

where $l_{i}$ represents the length of $i$ , the leg of the path.

Altitude changing cost

When UAVs fly near a peak, some height changing actions have to be implemented to avoid the peaks. But this maneuver will cause fuel consumption. In addition, low temperature makes the engine perform worst, frequent maneuver may bring risk for the flight safety. Therefore, frequent altitude change should be avoided as far as possible.

The altitude changing cost can be expressed as

f_{H} = \sqrt{\frac{1}{n} \sum_{i = 0}^{n} {(z_{i} - \frac{1}{n + 1} \sum_{i = 0}^{n} z_{i})}^{2}}

(11)

Threat cost

The threat cost is related to the distance between the UAV and the threat area. The closer the UAV is to the threat area, the bigger the threat cost is. The main threat areas considered in this article are terrain threat and wind field threat. The threat cost is defined as

f_{safe} = {\begin{matrix} \frac{K}{avgR}, path not through the threat area \\ ε, path through the threat area \end{matrix}

(12)

where

avgR = \frac{\sum_{i = 1}^{n} r_{i}}{n}

(13)

where $K$ is a constant whose value is relative to the real flight space, $ε$ is penalty coefficient, which is generally a big number, $n$ is the number of legs, $r_{i}$ is the distance between $i$ , the leg of path and the center of the threat area.

Multi-objective optimization model

Considering the parameters of UAV and the cost of path, a multi-objective optimization model for UAV path planning can be obtained using the fitness function that can be expressed as

{\begin{matrix} min f_{g} (x) = min [f_{1} (x), f_{2} (x), f_{3} (x)] \\ f_{1} (x) = f_{L} (x), f_{2} (x) = f_{H} (x), f_{3} (x) = f_{safe} (x) \end{matrix}

(14)

and the constraint function is written as

{\begin{matrix} \sum_{i = 1}^{n} l_{i} \leq l_{max}, & i = 1, 2, . . . n \\ l_{i} \geq l_{min}, & i = 1, 2, . . . n \\ φ_{i} \leq φ_{max}, & i = 1, 2, . . . n \\ ϑ_{i} \leq ϑ_{max}, & i = 1, 2, . . . n \\ H_{i} < H_{max}, & i = 1, 2, . . . n \end{matrix}

(15)

For the multi-objective function, it is difficult to find a solution that satisfies the minimal value of each evaluation function at the same time. It is necessary to synthesize all the cost values by appropriate weights to coordinate every performance. The fitness function of UAV path planning is constructed as

f (x) = k_{1} f_{1} (x) + k_{2} f_{2} (x) + k_{3} f_{3} (x)

(16)

The weights in the formula can be adjusted according to the actual mission requirements and flight environment requirements. When the desired mission time is short, the distance cost weight will be increased. While if the desired flight path of UAV is smooth, the altitude changing cost will be increased.

PIO algorithm

PIO algorithm is divided into two independent stages. In the first stage, the pigeon updates the position and speed of the individual by map and compass operator principle. In the second stage, the pigeon updates the state by landmark operator principle.

The description of PIO algorithm is as follows: Assume that the search area of PIO algorithm is a “D” dimensional space, and there are “M” pigeons in the group, in which the position of the ith pigeon represents one of the solutions of the optimization problem. Each individual pigeon will constantly adjust its position according to certain rules. With the help of fitness function, the fitness of each individual can be calculated. The individual position will be continuously updated in each iteration, and finally the optimal solution will be found. The position of the ith pigeon in the “D” dimension space can be expressed as $X_{i} = (X_{i 1}, X_{i 2}, . . ., X_{iD})$ , velocity can be expressed as $V_{i} = (V_{i 1}, V_{i 2}, . . . ., V_{iD})$ , where $i = 1, 2, . . ., N$ .

In the first stage, each individual states are updated according to the information of the best individual in the population by updating position according to formula (16) and updating the speed according to formula (17)

V_{i}^{N_{c}} = V_{i}^{N_{c} - 1} \cdot e^{- R \times N_{c}} + rand \cdot (X_{gbest} - X_{i}^{N_{c} - 1})

(17)

X_{i}^{N_{c}} = X_{i}^{N_{c} - 1} + V_{i}^{N_{c}}

(18)

where $N_{c}$ represents the current iterations, $R$ represents the map and compass factor. $rand$ is a random value from 0 to 1. After $N_{c} - 1$ iteration, the optimal position $X_{gbest}$ in the whole population is obtained by comparing the position of all the (pigeons) or UAVs. The maximal iteration in the first stage is set as $N_{c 1 max}$ . After $N_{c 1 max}$ iterations obtained by map and compass factor, the position and speed that update the rules of pigeon group will change, and the whole process enters the second stage.

In the second stage, when the pigeons approach target position, their states will be updated according to the landmark information. Some individuals will follow other individuals who are near the landmark, while some far from the landmark that will be abandoned because they have no ability to find the optimal path. In the calculation process, the number of pigeons will be halved in each iteration by abandoning pigeons that have poor adaptability and then look for the central location $X_{center}$ in the remaining population, regarding it as the landmark for flight. The state changes according to the following formulas

X_{center}^{N_{c} - 1} = \frac{\sum_{i = 1}^{N^{N_{c} - 1}} X_{i}^{N_{c} - 1} F (X_{i}^{N_{c} - 1})}{N^{N_{c} - 1} \sum_{i = 1}^{N^{N_{c} - 1}} F (X_{i}^{N_{c} - 1})}

(19)

N^{N_{c}} = \frac{N^{N_{c} - 1}}{2}

(20)

X_{i}^{N_{c}} = X_{i}^{N_{c} - 1} + rand (X_{center}^{N_{c} - 1} - X_{i}^{N_{c} - 1})

(21)

where F is related to the fitness function. It could be expressed as

F (X_{i}^{N_{c} - 1}) = fitness (X_{i}^{N_{c} - 1}), fitness (X_{i}^{N_{c} - 1}) > 0

(22)

The maximal iteration in the second stage is $N_{c 2 max}$ . After the $N_{c 2 max}$ iteration of landmark operator, the optimization process is finished and the optimal solution is obtained as its output.

CM-PIO-based path planning

Cauchy distribution is a continuous probability distribution without variance and mathematical expectation. If the random variable $x$ satisfies the probability density function, it is called Cauchy distribution.

The probability density function of Cauchy distribution is

f (x; x_{0}, y) = \frac{1}{π} [\frac{γ}{{(x - x_{0})}^{2} + γ^{2}}], x \in (- \infty, + \infty)

(23)

In equation (22), $x_{0}$ is the peak value of the distribution and $γ$ is the width corresponding to half of the maximum value. When $γ = 1$ and $x_{0} = 0$ , the random variable satisfies the standard Cauchy distribution, it is recorded as $X ~ C (1, 0)$ . The corresponding cumulative distribution function is an incremental function as

F (x; 0, 1) = \frac{1}{π} \arctan (x) + \frac{1}{2}, x \in (- \infty, + \infty)

(24)

Cauchy mutation map and compass operators

In the traditional PIO, map and compass operators are mainly used to find the global optimal individuals in the search space, and then positions and speeds of the pigeon swarm will be changed by referring to the optimal individuals. While choosing the Cauchy mutation $c_{1}$ as the maps and compass operators can not only expand the search area, but also reduce the risk of falling into local optimum.

The Cauchy weight coefficient $c_{1}$ obeys the Cauchy distribution

\frac{1}{π} \arctan (c_{1}) + \frac{1}{2} = rand

(25)

where $rand$ is a random value from 0 to 1, $c_{1}$ could be expressed as

c_{1} = \tan [π (rand - 1 / 2)]

(26)

In each iteration, the position of the individual pigeon is updated by the following rule

X'_{i} = X_{i 0} + c_{1} (X_{i 0} - X_{gbest})

(27)

where $X_{i 0}$ is the calculated position of $i$ , the pigeon. $X_{gbest}$ is the optimal individual with the optimal fitness after $N_{c} - 1$ iterations. While $X'_{i}$ is the position of $i$ , the pigeon after update. The position of the $i$ pigeon at next iteration will be

X_{i} = {\begin{matrix} {X'}_{i}, f (X_{i 0}) > f ({X'}_{i}) \\ X_{i 0}, f ({X'}_{i}) > f (X_{i 0}) \end{matrix}

(28)

As for Cauchy mutation map and compass operators $c_{1}$ , when it is positive, the updated position $X'_{i}$ will be farther from the global optimal position $X_{gbest}$ and vice versa. By adding Cauchy mutation, half of the individuals in the population will diffuse outward to find a better location, while the other half will be not. Comparing the undated positions with the original position, the individual with better fitness can be retained, which can not only ensure the quality of optimization but also improve the diversity of the population.

Cauchy mutation landmark operators

In the tradition PIO algorithm, the scale of population will be reduced by half at each iteration in the landmark operator stage, with pigeon moving toward the central position of the pigeon swarm. Unfortunately, this rapid reduction of population will lead to premature convergence of the algorithm, which will have a negative impact on the optimization of the landmark operator stage. To avoid the premature convergence or missing the optimal solution, the traditional landmark operator is replaced by a Cauchy function, updating the individual position relying on the optimal position in the population. The Cauchy function is described as

F (x; 0, 1) = \frac{2}{π} \arctan (x), x \in (0, + \infty)

(29)

Cauchy weight coefficient $c_{2}$ obeys Cauchy distribution, which is

{\begin{matrix} \frac{2}{π} \arctan (c_{2}) = rand \\ c_{2} = \tan (\frac{2}{π} rand) \end{matrix}

(30)

where $c_{2}$ is a positive constant. The rule for updating individual position could be expressed as

X_{i 0}^{N_{c}} = X_{i 0}^{N_{c} - 1} + c_{2} (X_{gbest} - X_{i 0}^{N_{c} - 1})

(31)

where $X_{i 0}^{N_{c} - 1}$ is the position of ith individual in $N_{c} - 1$ iteration, $X_{gbest}$ is the position of global optimal individual.

In the Cauchy mutant landmark operator stage, all individuals gradually approach the global optimal solution because of the positive constant $c_{2}$ . A suitable Cauchy mutant can make the pigeon swarm effectively move with the appropriate speed and direction and guarantee the stable convergence of the algorithm.

Cooperative path planning strategy

Assuming three UAVs take off from different locations at a same time and fly to one specific area for a mission. During the flight process, the three UAVs are required to keep safety distance and reach the target area within a similar duration.

Figure 2 depicts a scenario for multiple UAV cooperative path planning. Basically, each UAV must avoid flying in threatening area. The figure shows the shortest safe distance $D$ between each two UAVs. So, the distance between any two planned paths must be less than this safe distance D. In addition, UAV1, UAV2 and UAV3 are required to meet the time constraints²⁷ by adjusting the lengths of paths.

Figure 2.

A background setting for cooperative path planning.

Therefore, in addition to care about the parameters of UAV, multi-UAV path planning also care about the space and time relationships between all UAVs which may give some constraints to cooperative path planning.

First, a sufficiently safe distance $d_{safe}$ between two adjacent UAVs must be kept during the flight. Assuming that the position of UAV1 is $x_{1} (t)$ at the moment $t$ and that of UAV2 is $x_{2} (t)$ . The flight distance between the two UAVs should satisfy the following relationship

‖ x_{1} (t) - x_{2} (t) ‖ \geq d_{safe}

(32)

When all UAVs generally approach the target area, and their distances get closer and closer, so the safe distance should be set different value in different stages as

d_{safe} = {\begin{matrix} D, t \leq T \\ d, t > T \end{matrix}

(33)

where $T$ is 80% of the total flight time, $D$ and $d$ are set according to the specific planning area.

Moreover, both UAVs are desired to reach their desired target position simultaneously. According to the allowed speed range and length of path, the shortest time and the longest time for each UAV to reach the target point will be calculated. Assuming the allowed speed range of $UA V_{i}$ is $V_{i} = [V_{i min}, V_{i max}]$ and the length of path is $L_{i}$ , the flight duration will satisfy

T_{1} \in [T_{1 min}, T_{1 max}] = [\frac{L_{1}}{V_{1 max}}, \frac{L_{1}}{V_{1 min}}]

(34)

The temporal cooperation rule for two UAVs is

max [T_{1 min}, T_{2 min}] < min [T_{1 max}, T_{2 max}]

(35)

In this case, the two UAVs will have the possibility to simultaneously arrival to the target position.

To meet the spatial requirement and the temporal requirement of UAV group, two coordination coefficients are added to each UAV’s path evaluation function. They could be expressed as

f_{co} = f_{space} + f_{time}

(36)

f_{space} = {\begin{matrix} d, & meet spatial requirment \\ 0, & not meet spatial requirment \end{matrix}

(37)

f_{time} = {\begin{matrix} \frac{N}{T_{1} - T_{2}}, & meet spatial requirment \\ 0, & not meet temporal requirment \end{matrix}

(38)

where $f_{space}$ is the spatial coordination coefficient, $d$ is the distance between two UAVs, $f_{time}$ is the temporal coordination coefficient, $N$ is a constant. $T_{1}$ and $T_{2}$ are the required time for UAV1 and UAV2 to arrive the targeted position.

In terms of the proposed strategy for cooperative path planning problem, each UAV is represented by a sub-population, and each sub-population evolves independently. Only when evaluating the individual fitness, the information between sub-populations will be communicated. In the multi-population’s co-evolution process, the optimal individuals of each population are selected to communicate with other populations. This co-evolution process is shown in Figure 3.

Figure 3.

Co-evolution process in coordination path planning.

The path planning process for each UAV will refer to other UAV’s paths and calculating the spatial and temporal coordination coefficients between UAVs. Finally, more suitable path will be selected which not only have advanced fitness but also meet the cooperation requirement.

The specific steps of CM-PIO cooperative path planning strategy are presented as following:

Step 1. Define the area for path planning of every UAV.

Step 2. Initialize the algorithm parameters including the scale of population $M$ , the dimensions of area $D$ , map and compass factors $R$ , maximal iteration $N_{c 1 max}$ and $N_{c 2 max}$ in the first stage and second stage, respectively, the weight coefficients and so on.

Step 3. Individual coding rules randomly generates $M$ individuals with positions and speeds which are within the allowed range of $[v_{min}, v_{max}]$ .

Step 4. Find $m$ , the most optimal individuals in each population, by fitness function. And then combining with the information of other populations, find the ith individual with the biggest cooperation coefficient marked as $x_{igbest}$ in each population.

Step 5. Update the individual’s positions and speeds in each population by the Cauchy mutation map and compass operator.

Step 6. Compare the current iteration in map and compass operator stage with the maximal iteration $N_{c 1 max}$ . If the current iteration is bigger than the maximal iteration $N_{c 1 max}$ , the operation will enter the landmark operator stage. Otherwise, return to step 4.

Step 7. Update the individual’s positions by landmark operators.

Step 8. Compare the current iteration in landmark operator stage with the maximal iteration $N_{c 2 max}$ . If the current iteration is bigger than the maximum iteration $N_{c 2 max}$ , the operation finishes. Otherwise, return to step 7.

The diagram of multi-UAV coordination path planning strategy is shown in Figure 4.

Figure 4.

Procedure of CM-PIO cooperative path planning strategy.

Simulation results and discussion

The simulation results is carried out on MATLAB/2014a. Providing a path consisting of 11 waypoints and 10 path sections. Flight space is set as $20 km \times 20 km \times 5 km$ . There are three fixed-wing UAVs with same parameters involved in the experiment.

Simulation parameters

The parameters of UAV are presented in Table 1.

Table 1.

Parameters of UAV.

Parameters	Symbol	Value	Unit
Maximum turning angle	$φ_{max}$	120	°
Max flight distance	$L_{max}$	50	km
Shortest route	$l_{min}$	0.2	km
Max flight altitude limit	$H_{max}$	1.2	km
Max climb/dive angle	$ϑ_{max}$	80	°
Cruising speed	$V_{c}$	50	m/s
Min speed	$V_{min}$	40	m/s
Max speed	$V_{max}$	60	m/s

UAV: unmanned aerial vehicle.

Based on the field investigation and topographic analysis of the mountainous area in the Qinghai-Tibet plateau, the parameters of the datum terrain are indicated as $a = 10$ , $b = 0.2$ , $c = 0.1$ , $d = 0.6$ , $e = 1$ , $f = 1$ and $g = 0.1$ .

The parameters of the peak terrain are shown in Table 2.

Table 2.

Parameters of the peak terrain.

Number	Center position $(x_{0}, y_{0})$	Altitude, h (km)	Decline scale along $x$ axis $(x_{s})$	Decline scale along $y$ axis $(y_{s})$
1	(5, 4)	0.8	2	2
2	(11.5, 9)	1.5	3	3
3	(5, 16)	1.2	2.5	1.5
4	(15, 16)	0.7	2	1.5

The parameters of wind field model are shown in Table 3.

Table 3.

Parameters of wind field model.

Number	Parameter	Center position	Unit
1	Center	(6, 14, 0.8)	km
1	Radius	1	km
2	Center	(15, 12, 0.6)	km
2	Radius	0.5	km

The parameters of proposed CM-PIO algorithm are presented in Table 4.

Table 4.

Parameters of proposed CM-PIO.

Symbol	Parameters	Value
$N_{c 1 max}$	Max iteration for stage 1	100
$N_{c 2 max}$	Max iteration for stage 2	50
$M$	Number of individuals on a population	50
$D$	Dimension	9
$(v_{min}, v_{max})$	Range of evolution speed	(–1.2, 1.2)

CM-PIO: Cauchy mutant pigeon-inspired optimization.

For the fitness function, weights of distance cost, altitude changing cost and threat cost are $k_{1} = 0.4$ , $k_{2} = 0.2$ and $k_{3} = 0.4$ , respectively. In terms of minimal safe distance in cooperative path planning, setting $D = 500 m$ , $d = 100 m$ . The temporal cooperative coefficient is set as $N = 300$ .

The coordinates of start and target points for each UAV are shown in Table 5.

Table 5.

Coordinates of start point and target point for each UAV.

No. of UAVs	Start point	Target point	Unit
UAV1	(0, 0, 0)	(20, 19.8, 1)	km
UAV2	(0, 2, 0)	(19.8, 19.8, 1)	km
UAV3	(0, 6, 0)	(19.8, 20, 1)	km

UAV: unmanned aerial vehicle.

Results of CM-PIO-based path planning method

To verify the robustness of the proposed path planning algorithm, the paths planned by traditional PIO algorithm are also presented in Figure 5. The cone represents the peak, the sphere areas near the peak represent the wind field, the solid line represents the optimal path planned by CM-PIO algorithm and the dash line represents the optimal path planned by PSO algorithm. Each path includes 11 waypoints which are represented by circles.

Figure 5.

The paths planned by CM-PIO and PIO.

It can be seen from Figure 5 that both algorithms can plan feasible paths. Although, the route planned by PIO algorithm can avoid the threat of mountain peaks, the total distances are longer and the altitude near the peak and wind field suffer greatly changing, which will increase the risk of collision. The paths planned by CM-PIO is shorter, smoother, lower cost and safer. Figure 6 illustrates the change in the fitness of the optimal paths of three UAVs, by PIO and CM-PIO. It can be seen that CM-PIO can find the optimal path faster and more excellent. Besides, the Cauchy mutant could create the most optimal individual when the traditional PIO has fallen in to the local optimum.

Figure 6.

Fitness of optimal individual changing with iteration.

Results of cooperative path planning strategy

It can be seen in Figure 7 that without cooperative planning the path of UAV2 and the path of UAV3 are close and have intersection. To ensure the spatial requirement, cooperative path planning is needed. Figure 8 shows the fitness of optimal individuals changing with iteration planned by CM-PIO cooperative planning strategy and Figure 9 shows coordination coefficient $f_{co}$ changing with iteration. Table 6 shows the length of the planned path with and without coordination planning. Combining the above data it can be seen that proposed CM-PIO cooperative path planning strategy could not only meet the coordination requirements but also finds optimal individuals with advanced fitness.

Figure 7.

The paths with and without cooperative planning.

Figure 8.

Fitness of CM-PIO cooperative plan changing with iteration.

Figure 9.

Coordination coefficients of three paths changing with iteration.

Table 6.

Length of planned paths.

Number	Plan without cooperation (km)	Plan with cooperation (km)
UAV1	30.765	30.765
UAV2	28.564	28.793
UAV3	24.614	26.004

UAV: unmanned aerial vehicle.

Conclusion

For the path planning problem of the UAV group in plateau area, first the problem was modeled as a multi-objective optimization problem and then CM-PIO algorithm is designed to find the optimal path for each UAV. Compared with the traditional PIO algorithm, the result shows that the solution of proposed method has better robustness. Finally, considering the spatial constrain and temporal constrain of multi-UAV cooperation path planning problem, the CM-PIO cooperation path planning strategy was designed. The simulation results show the proposed method could not only find optimal individuals with advanced fitness but also meet the coordination requirements.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship and/or publication of this article.

ORCID iD

Bo Hang Wang

References

Yang

Xiao

, et al. A literature review of UAV 3D path planning. In: Proceedings of the 11th world congress on intelligent control and automation, Shenyang, China, 29 June–4 July 2014.

Yang

Sukkarieh

. Real-time continuous curvature path planning of UAVs in cluttered environments. In: Proceedings of the 5th international symposium on mechatronics and its applications (ISMA 2008), Amman, Jordan, 27–29 May 2008, pp. 1–6. New York: IEEE.

Yan

Liu

Xiao

. Path planning in complex 3D environments using a probabilistic roadmap method. Int J Autom Comput 2013; 10(6): 525–533.

Aurenhammer

. Voronoi diagrams—a survey of a fundamental geometric data struct. ACM Comput Surv 1991; 23: 345–405.

Jatmiko

Mursanto

Kusumoputro

, et al. Modified PSO algorithm based on flow of wind for odor source localization problems in dynamic environments. Wseas Trans Syst 2008; 7(2): 106–113.

Ergezer

Leblebicioğlu

. 3D path planning for multiple UAVs for maximum information collection. J Intell Robot Syst 2014; 73(1–4): 737–762.

Yao

Lin

Xie

, et al. Path planning for virtual human motion using improved A* star algorithm. In: Proceedings of the 7th international conference on information technology: new generations, Las Vegas, NV, 12–14 April 2010, pp. 154–1158. New York: IEEE.

Xie

Manyi

, et al. Path planning for UAV based on improved heuristic A*algorithm. In: Proceedings of the 9th international conference on electronic measurement & instruments, Beijing, China, 16–19 August 2009, pp. 488–493. New York: IEEE.

Deng

Jiang

Inoue

. Mobile robot path planning by SVM and lyapunov function compensation. Meas Control 2009; 42: 234–237.

10.

Jolai

Asefi

Rabiee

, et al. Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem. Sci Iran 2013; 20(3): 861–872.

11.

Kim

. Fitness switching genetic algorithm for solving combinatorial optimization problems with rare feasible solutions. J Supercomput 2016; 72(9): 3549–3571.

12.

Duan

Qiao

. Pigeon-inspired optimization: a new swarm intelligence optimizer for air robot path planning. Int J Intell Comput Cybern 2014; 7(1): 24–37.

13.

Wang

Jiang

. Two-dimension path planning method based on improved ant colony algorithm. Adv Pure Math 2015; 5(9): 571–578.

14.

Sheikhan

Hemmati

. PSO-optimized hopfield neural network-based multipath routing for mobile ad-hoc networks. Int J Comput Intell Syst 2012; 5(3): 568–581.

15.

Wang

Guo

Duan

, et al. A bat algorithm with mutation for UCAV path planning. Sci World J 2012; 2012: 418946.

16.

Contreras-Cruz

Ayala-Ramirez

Hernandez-Belmonte

. Mobile robot path planning using artificial bee colony and evolutionary programming. Appl Soft Comput 2015; 30: 319–328.

17.

Gao

Liu

. A modified artificial bee colony algorithm. Comput Oper Res 2012; 39(3): 687–697.

18.

You

Ding

, et al. A new optimization-driven path planning method with probabilistic completeness for wheeled mobile robots. Meas Control 2019; 52: 317–325.

19.

Bai

Xie

, et al. A hybrid algorithm of particle swarm optimization, metropolis criterion and RTS smoother for path planning of UAVs. Appl Soft Comput 2018; 73: 735–747.

20.

Ding

Chao

, et al. Efficient path planning method based on genetic algorithm combining path network. In: Proceedings of the 4th international conference on genetic and evolutionary computing, Shenzhen, China, 13–15 December 2010.

21.

Shahrabi

Khameneh

. Application of a hybrid system of probabilistic neural networks and artificial bee colony algorithm for prediction of brand share in the market. Ind Eng Manag Syst 2016; 15(4): 324–334.

22.

Wang

Ali

. An overview of various kinds of wind effects on unmanned aerial vehicle. Meas Control 2019; 52: 731–739.

23.

Wei

Zhi

Huizhu

. Adaptive mutation particle swarm optimization based on q-Gaussian distribution. J Shenyang Univ Technol 2012; 34(3): 354–360.

24.

Hebecker

Buchholz

Ortmeier

. Model-based local path planning for UAVs. J Intell Robot Syst 2015; 78(1): 127–142.

25.

Jian

Zhongxi

Yanyan

. Path planning method based on maneuverability constraints of UAV. Comput Inf Technol 2011; 19(12): 1–5.

26.

Chao

. Research on cooperative formation keeping control for multi-UAV. Shenyang, China: Shenyang Aerospace University, 2016.

27.

Wang

Jiang

. Multi-UAV route planning based on time collaboration. Mach Electron 2016; 34(2): 7–11.