Path planning of multiple UAVs using MMACO and DE algorithm in dynamic environment

Abstract

Cooperative path planning of multiple unmanned aerial vehicles is a complex task. The collision avoidance and coordination between multiple unmanned aerial vehicles is a global optimal issue. This research addresses the path planning of multi-colonies with multiple unmanned aerial vehicles in dynamic environment. To observe the model of whole scenario, we combine maximum–minimum ant colony optimization and differential evolution to make metaheuristic optimization algorithm. Our designed algorithm, controls the deficiencies of present classical ant colony optimization and maximum–minimum ant colony optimization, has the contradiction among the excessive information and global optimization. Moreover, in our proposed algorithm, maximum–minimum ant colony optimization is used to lemmatize the pheromone and only best ant of each colony is able to construct the path. However, the path escape by maximum–minimum ant colony optimization and it treated as the object for differential evolution constraints. Now, it is ensuring to find the best global colony, which provides optimal solution for the entire colony. Furthermore, the proposed approach has an ability to increase the robustness while preserving the global convergence speed. Finally, the simulation experiment results are performed under the rough dynamic environment containing some high peaks and mountains.

Keywords

Maximum–minimum ant colony optimization ant colony optimization unmanned aerial vehicle differential evolution and path planning

Introduction

From the last few decades, the advancement in the field of aeronautics and astronautics has widely increased. The unmanned aerial vehicle (UAV) is the best invention of this domain.^1–3 In this era, UAVs have been widely used for the military missions but it can widely use for the applications in rescue, surveillance and mapping scenarios. Moreover, we can also use UAVs for long missions, such as in remote sensing and dangerous areas, where accurate and flexible maneuvering is required.⁴ In order to enhance the performance of combat scenarios and reduce the overall mission accomplishment time, a swarm of UAVs takes part.⁵ The path-planning process is an important area of interest in the usage of multiple UAVs (M-UAVs).⁶ It requires an optimal path or route from the initial position (base station) to the targeted position while avoiding obstacles and consuming minimum fuel.⁷ Optimization issues are encountered to real-world problems in different areas such as mathematics, engineering, science and economics. Scientific algorithms are used to resolve these optimizations issues; it may require more extensive calculations as the problem size gets bigger. Thus, we need optimization techniques that require less memory and computational power but give better outcomes. From the last three decades, scientist made stochastic-based different bio-inspired optimization algorithms which are more accurate and efficient to compare with the analytical methods.^8–12

The autonomous flight control is one of the most essential feature in modern control UAVs to adapt the dynamic environment and to find the most suitable and optimal route for the mission.¹³ When using M-UAVs, we also have to deal with additional problems like simultaneous arrival and collision avoidance and so on. One way to solve these problems is to use classical algorithms because they are quite efficient, but they require a lot of time and calculations.¹⁴ On the other hand, many scientists have made evolutionary bio-inspired algorithms such as ant colony optimization (ACO) by Colorni et al.,¹⁵ particle swarm optimization (PSO) by Kennedy and Eberhart,¹⁶ differential evolution (DE) by Storn and Price¹⁷ and genetic algorithm (GA) by John Holland.¹⁸ These algorithms are quite efficient as well as reliable and quicker in finding the optimal solution to complete the mission requirement robustly. The combination of these methods has emerged to have quicker convergence speed and superior solutions. Examples of these hybrid algorithms include those between PSO and GA,^19,20 PSO and DE^21–23 and ACO and DE.^24–26

However, in this research, our main concern is on ACO; it follows the hunting behavior of actual ant colonies to solve the optimization problems. It consists of synthetic ant colonies which work together to find the best possible solution. The ants convey the information to each other using virtual pheromones. While ACO is a very effective method, proven by its widespread usage, it has some disadvantages, too. Its convergence speed is slow, and it can fall into local optimum. Occasionally, it comes up with identical outcomes that lower the probability of getting the best result.

Cekmez et al.²⁷ present a multi-colony ACO to counter the previous aforementioned issues of slow convergence speed and local optimum. In contrast to normal ACO, the authors suggest to use multiple ant colonies. They utilize different pheromone tables for every colony to explore the area completely. However, in every iteration, each colony provides varied outcomes. After that, all colonies interchange their optimal solution with the surrounding colonies. Then, every colony modifies their pheromone tables with the acquired data. Shao et al.²⁸ also discuss a similar path-planning problem concerning M-UAVs. They explore a distributed cooperative particle swarm optimization (DCPSO) method intended for secure navigation of each UAV.

Dewangan et al.²⁹ used a grey wolf optimization (GWO) technique to resolve the three-dimensional (3D) path-planning problem of UAV. In addition, the major task is to search the most reasonable path and to avoid collision and other obstacles. In Gu et al.,³⁰ M-UAVs trajectory planning is done using PSO with (receding horizon) framework. Moreover, obstacle avoidance–based approach is developed to eliminate collision between UAVs. Furthermore, a decentralized control hierarchy for an individual UAV is proposed to control individual UAV. An intelligent Bézier curve–based model for path planning is proposed in Tharwat et al.³¹ The main aim of the designed algorithm is to search the shortest and smooth path between the start point and the targeted point. Beside this, chaotic particle swarm optimization (CPSO) strategy has also been applied to enhance the control points of the Bézier curve.

The inspiration of this research work has been taken from the work in the previous literature;^26,27 the presented study states the issues of UAV path planning by taking the benefit of smart bio-inspired optimization algorithms, in the presence of dynamic environment. In this research, we design a novel maximum–minimum ant colony optimization (MMACO) with DE to make a metaheuristic hybrid algorithm. Although combining these two algorithms increases the complexity of the system, but it will surely provide a globally optimal solution for the path planning of multi-colonies with M-UAVs.

The primary achievements of this research are as follows:

A multi-colonies optimization having different sub–ant colonies exists in the entire ant colony, where each sub-colony performed independently to explore the overall area.

Three different colonies have been made, and each colony is independent to find the optimal or shortest distance to reach the targeted area.

To enhance the performance of the entire colony, each colony needs to share its knowledge with others.

To find the best and the shortest route from the initial point to the targeted area from a colony in which the upgradation of route and lemmatized the number of participants are done by MMACO.

Finally, DE will globally determine which is the most suitable sub-colony to reach the targeted area in optimal time.

The reminder of this manuscript is structured as follows. In section “Problem statement,” we define the problem statement and mission requirement. Cooperative path planning, collision avoidance and coordination between UAVs are discussed in section “Cooperative path planning.” It is followed by section “Hybrid MMACO-DE algorithm,” in which our designed hybrid MMACO-DE algorithm is discussed. Section “Simulation results and discussions” presents the simulation results and discussion. Finally, the overall manuscript is concluded in section “Conclusion.”

Problem statement

The M-UAVs path-planning problem is shown in Figure 1. To consider three UAVs take off from three different locations of an entire colony. The termed different locations are called as sub-colonies, that is, 1, 2 and 3, target the designated area. Moreover, there are some obstacles in the form of mountains and high rocks in the route, due to these aforementioned threats in the fly zone need to escape from them robustly. Furthermore, during the whole scenario, UAVs are required to maintain safe distance to avoid collision and arrive at their targeted area by time synchronization to adjust the length and the route of the complete tour.

Figure 1.

Multiple UAVs path-planning scenario.

Mission requirement

Our main concern is to find which colony is most suitable to target the designated area optimally.

Cooperative path planning

To compare with the path planning of individual UAV, M-UAVs required perfect coordination between neighbor UAVs, to meet with the specific point or area without any collision. The requirements to achieve the mission and physical parameters are different from a single UAV. The cooperation and coordination between several UAVs bring different co-constraints, that is, timing coordination and avoidance to collide with each other. In this study, we mainly focus on collision avoidance and coordination between UAVs.

Collision avoidance

An additional requirement of path planning is to avoid collision and to minimize the threat of collision, which is also termed as air coordination or formation. In our scenario, the 3D map is used and we must ensure that all UAVs’ altitude must change according to the given condition of the unavoidable mountain peaks in the route. Due to the above route, we must maintain safe distance between the UAVs and apply some proper coordination strategy.¹³ The path-planning constraints of M-UAVs also maintain the time and space correlation between all UAVs route. We consider short safe distance $d_{ss}$ between UAVs in our scenario to avoid collision. The distance of flight between UAVs must satisfy the relationship

d_{ss} (t) \leq ‖ y_{1} (t) - y_{2} (t) - y_{3} (t) ‖

(1)

where $y_{1} (t), y_{2} (t)$ and $y_{3} (t)$ are the positions of UAV1 to UAV3, respectively. As per the mission requirements, when UAVs approach to the targeted area, they get closer and closer to each other. At that time, the safe distance will settle between different iterations at different stages, which is rewritten as

d_{ss} (t) = {\begin{matrix} D, t \leq T_{l, m} \\ d, t > T_{l, m} \end{matrix}

(2)

where $T_{l, m}$ is about 85% of the full flight duration; $D$ and $d$ will adjust according to the specific planning area conditions.

Coordination between UAVs

To meet with the spatial and temporal requirements for the group of UAVs, we introduce two coordinate coefficients that must add in each UAV as a function of its path or route. It is expressed as

f_{co} = f_{s} f_{t}

(3)

Therefore, $f_{s}$ and $f_{t}$ are the coefficients of spatial and temporal coordinates. It is expressed as

f_{s} = {\begin{matrix} d, meet spatial reqiurements \\ 0, otherwise no \end{matrix}

(4)

f_{t} = {\begin{matrix} \frac{N}{(T_{1} - T_{2}) a n d s o o n \dots}, & m e e t s p a t i a l r e q i u r e m e n t s \\ 0, & o t h e r w i s e n o \end{matrix}

(5)

where $T_{1}, T_{2}$ and $T_{3}$ are the expected arrival time of all three UAVs to the destination and $N$ is the constant. Now, in terms of the proposed hybrid control strategy based on path-planning algorithm, each sub-colony UAV is performed independently to explore the overall area.¹³ At the same time, when we evaluate the fitness of each aircraft, the information between all UAVs must communicate with each other. In the M-UAVs evolution, DE will deal this and set the optimized path for an individual one. The path-planning coordination of complete scenario is presented in Figure 2.

Figure 2.

Path-planning coordination between UAVs.

For the path-planning scenario, each UAV communicates with other UAV and calculates its spatial and temporal coordination coefficient. Finally, the proposed algorithm will select the most suitable path, which will not only meet the fitness but also our mission requirements.

Hybrid MMACO-DE algorithm

In this section, we design an improved metaheuristic hybrid algorithm to resolve the path-planning issues in a 3D environment. The metaheuristic algorithm consists of MMACO and DE. The main aim is to design this algorithm and to apply it in the scenario of multi-colonies path planning of M-UAVs. In order to enhance the effectiveness of path planning, UAVs must arrive at the targeted area using the shortest path, complete the mission and improve the reliability of the whole scenario. First, we apply the classical model of ACO and after that speed up the whole strategy by applying our hybrid metaheuristic algorithm. Finally, only the most optimal colony will be selected to complete the mission requirement.

As shown in Figure 3, the entire ant colony divided into three sub-colonies, where each sub-colony is restricted only best ant to construct and update the route. Moreover, each colony executes as an independent agent, to fulfill path-planning task more robustly. The main objective is to find the most optimal distance from the entire colony, that is, which sub-colony is most suitable to reach the targeted area. Figure 3 represents the block of MMACO-DE strategy; it also shows the knowledge sharing between multi-colonies path planning of M-UAVs.

Figure 3.

Block diagram of MMACO-DE algorithm.

Basic ACO algorithm

The natural representation of basic ACO algorithm depends on ant colonies. Real ants are proficient to find the shortest path from a food source to their colony. They hunt the food without any visual clues by manipulating and updating the pheromone data. Ants walk on the earth, deposit the pheromone and track in probability the pheromone earlier dropped by the former ants.³² The advantage of the algorithm is that in the end all ants follow the shortest path. A procedure where ants utilize their pheromones to search for a shortest path between colony and food source is presented in Figure 4 below.

Figure 4.

Real ant’s food hunting procedure.

The action of real ants is inspired by the ACO, where a set of virtual ants collaborate with each other. For the solution of problem by interchanging the information through pheromones placed on the edges of the grid boundaries.

Improved ACO algorithm

The parallel process of ACO in general comprises two essential practices: adaptability and collaboration. In adaptability, the contender solutions are carried out to readapt their organizations on the source of collecting the information. On the other hand, in collaboration stage, the contender offer interchanges the information to offer the best possible solution. The first ACO strategy applied to the traveling salesperson problem (TSP) is to discover the minimum closed-loop path between two cities or node. Even though the UAV path planning is to discover the best optimistic flight path, UAV is able to complete the desired task and avoid the unwanted threats, that is, mountain peaks and different threats.³³

ACO provides flexible route to solve M-UAVs path-planning issue under hazardous battlefield environment. The scenario is designed for the nth UAV in the path planning of ith UAVs, let m ants participate from the initial position, the ants choose the next nodes in the grid according to the adaptability rule. Hence, additional ants mean UAV route is tracked by the higher probability that a route chosen by the other ants. The above process of ACO assures that mostly all ants walk along the shortest UAV route in the end. The main features of ACO related to the ant characteristic are the heuristic function and pheromone denoted as ɳ and τ. In this research, we investigate the shortest path between the colonies and the targeted destination node between two cities termed as $a$ and $b$ , respectively. Now, define the transformation probability from node $a$ to $b$ from $l th$ ant and $e$ is the edge in the grid rewritten as¹⁵

p_{n, ab} (t) = {\begin{matrix} \frac{{(τ_{n, ab} (t))}^{α} {(η_{ab} (t))}^{β}}{\sum_{e \in accep t_{l}} {(τ_{n, ab} (t))}^{α} {(η_{ae} (t))}^{β}} & if b \in accep t_{l} \\ 0 & otherwise \end{matrix}

(6)

where the term $accep t_{l}$ is the flexible domain of the $l th$ ant. The parameters $α$ and $β$ control the comparative significance of the trail pheromone versus reflectivity.

The sum of pheromone by the nth UAVs ant between the node $a$ to $b$ is written as

τ_{n, ab} (t) = τ_{n, ab} . \frac{i - 1}{\sum τ_{j, b}^{p}}

(7)

The sum of pheromone trail $τ$ provides the clue to the ants to select the upcoming node. In ACO, ants drop their pheromone on the edge of the boundaries they passed. Ants allocate for the nth UAV will able to select the node, which have relatively greater pheromone than ith UAVs. The experimental desirability from node $a$ to $b$ is expressed as

η_{ab} = \frac{1}{d_{b, da}}

(8)

where $d_{b, da}$ denotes the distance between node a, node $b$ and destination area, that may clue the ants situated at node $a$ tend to select the nodes that are closest to the destination area. In addition, the ants in the procedure built their routes, the trail values of the route edges $(a, b)$ and the pheromone updated using the following equation

τ_{n, b}^{p} (t + 1) = (1 - ρ) \cdot τ_{n, b}^{p} (t) + Δ τ_{n, b}^{p}

(9)

where $ρ \subset (0, 1)$ is the local pheromone decline constraint, it represents the rate of evaporation between time $t$ and $t + 1$ , respectively

τ_{n, b}^{p} (t) = \sum_{l = 1} Δ τ_{n, b, l}^{p}

(10)

Now, $Δ τ_{n, b, l}^{p}$ is the amount of pheromone trail exist on the boundaries or edge of $(a, b)$ and the node $b$ by the $l th$ ant of the nth UAV lie among $t$ and $t + 1$ . In the traditional ant hierarchy structure, it is expressed as

Δ τ_{n, b, l}^{p} = {\begin{matrix} \frac{Q}{j_{n, l}}, & if n th ant uses (a, b) \\ 0, & otherwise \end{matrix}

(11)

where $Q$ is the constant and $j_{n, l}$ denotes the route cost of the $l th$ ant.

maximum–minimum ACO

To increase the performance of classical ant system, improve the issues related to the initial stagnation. In order to fasten the convergence speed, the following enhancement in the algorithm is established in the ACO strategy.³² Now, the m ants are allocated for the nth UAV, and a number of routes are created in individual iteration.¹³The mean cost $\bar{m}$ of the routes is calculated by

j_{n, \bar{m}} (t) = \frac{1}{m} \sum_{l = 1}^{m} j_{n, l} (t)

(12)

If and only if the route cost of the lth ant in the nth iteration fulfills $j_{n, \min} (t) \geq j_{n, l} (t)$ , the lth ant updates the pheromone using equation (11). The separate solution among the best iteration and best global ant is to update the trail pheromone, and hunt stagnation could proceed further. This type of stagnation must escape the probability of choosing the upcoming resolution; it will directly depend upon the pheromone trails. Although by limiting, the effects of pheromone trails during it can easily reject the variance among the pheromone trails at the implementation of this strategy. To accomplish this mission, ACO executes maximum and minimum pheromone trails for all the pheromone trails termed as $τ_{\max}$ and $τ_{\min}$ . Now, improving the trail pheromones in the last of iteration, the following equation is used to update or advance the pheromone points

τ_{a, b} (t) = {\begin{matrix} τ_{\max}; τ_{a, b} (t) \geq τ_{\max} \\ τ_{a, b} (t); τ_{\max} \geq τ_{a, b} (t) \geq τ_{\min} \\ τ_{\min}; τ_{\min} (t) > τ_{a, b} (t) \end{matrix}

(13)

DE

DE is the best and versatile optimization method; it formerly designed as an algorithm for the global continuous optimization. It consists of three basic constraints named as mutation, crossover and selection operator. Initially, it generates some random solution to search the target. After that, it enlarges the alteration vector concerning two population vectors. First, it generates the trail mutation and hereinafter it joins the trail mutation and the target ones to produce an updated individual. If an updated individual has good fitness results, it will accept and replace it with the previous individual.³³

In this research, we check the pheromone on the route that left by the ants in MMACO as the objective in DE. To solve the path-planning issues, the best ant of each colony represents the colony and only the best ant will be able to update the pheromone trails for the whole scenario. Some modifications are done in the model of MMACO strategy to divide the whole colony into three different colonies, and the colony number is termed as $col$ that restricts the total number of ants m. The pheromone left between two nodes is denoted as $τ = (τ_{n})$ ; n = 1, 2, 3 … colonies, respectively. Now, the DE mutation method is applied on it and the upgraded trail spreading is created using the equation

τ_{1 n} = τ_{1 r} + f * (τ_{2 r} - τ_{3 r}); n = 1, 2, 3 \dots colonies

(14)

where $r$ is the positive integer, by taking three-pheromone trails for three different colonies that is randomly chosen by the ant colonies, the real constant factor $f$ . It helps to control the differential variation $(τ_{2 r} - τ_{3 r})$ . In order to increase the variation of pheromone trail among two nodes, by initializing the benefit of DE crossover operator to make a new pheromone trail $τ_{1 n}$ that produced by the mutation, it joins with the present target pheromone trail $τ_{n}$ .^26,33 Now, the designed MMACO-DE strategy produces a new matrix to store the pheromone which is rewritten as

\begin{matrix} τ_{2 n} & = (\begin{matrix} τ_{2_{n}}^{1, 1} & \dots & τ_{2_{n}}^{1, i} \\ ⋮ & ⋱ & ⋮ \\ τ_{2_{n}}^{i, 1} & \dots & τ_{2_{n}}^{i, i} \end{matrix}); n = 1, \dots, \\ Colony that can be expressed as \\ τ_{2_{n}}^{ab} = {\begin{matrix} τ_{n}^{ab}, if r and b \leq CR \\ τ_{l_{n}}, if r and b > CR \end{matrix} \end{matrix}

(15)

where $τ_{n}^{ab}$ is the amount of pheromone between two nodes or cities a and b of the nth ant colonies. Afterward, the mutation $τ_{2_{n}}^{ab}$ is the nth AC pheromone trial between both the cities. Subsequent to this crossover process to $τ_{n}^{ab}$ and $τ_{1 n}^{ab}$ and the positive integer number randb, cross over constant $CR$ value lies in between 0 and 1. The greater the value of crossover the higher the possibility of crossover process. If the value of $CR = 0$ , it means that no DE process will occur. Now, it is clear that the newly produced pheromone matrix $τ_{2 n}$ will confidently get at least one component from the mutation pheromone process $τ_{1 n}$ . On the other hand, the pheromone trail will not update at all, resulting in weakening pheromone exchange among all the ant colonies or entire ant colony.^25,26,33

For the 3D path planning of UAVs, all the ants in each colony develop their own route using the transition probability $p_{a, b}$ that is calculated by the pheromone matrix $τ_{n}$ . The term $L_{best_1 n}$ is the shortest route between the entire routes find by the ants. After that, we will compare the original and the newly generated pheromone. Next to this in Duan et al.,²⁶ the author made a single solution for this and called the selection as “the greedy” model. It states that if the updated pheromone trail has the better value than the previous one, it will accept this and reverse into the matrix of pheromone trail for the next iterations. Else, the original pheromone will take place among both the cities of ant colonies. Now, the crossover process to the pheromone trail is rewritten as

τ'_{n, (t)} = {\begin{matrix} τ_{2_{n}, (t), if L_{best_2 n} < L_{best_1 n}} \\ τ_{n, (t), if L_{best_2 n} < L_{best_1 n}} \end{matrix}

(16)

where the original pheromone left by the nth ant colonies is termed as $τ_{n, (t)}$ , for the tth number of iteration. Now, the updated pheromone trails of the nth ant colony after DE mutation and crossover process. Now, the $τ'_{n, (t)}$ is equivalent to the pheromone matrix; it has high value that lies in between $τ_{n, (t)}$ and $τ_{2 n, (t)}$ . The shortest route $L_{best_1 n}$ is found by the $τ_{n, (t)}$ original pheromone ant colony, whereas $L_{best_2 n}$ is length of optimal route found by the $τ_{2 n, (t)}$ , that is, the updated value of the pheromone of the nth ant colony. After the selection process, the nth ant colony which create their routes using pheromone trails $τ'_{n, (t)}$ or $τ_{2 n, (t)}$ discharge their pheromone concern the route they already covered and update the selected pheromone trail $τ'_{n, (t)}$ to become new trail pheromone as $τ_{n, (t + 1)}$ .^26,33 After that, pass the updated pheromone to each ant colony for the next iteration to search new and more feasible path exploration. The overall flow of the proposed hybrid algorithm is defined below in Figure 5.

Figure 5.

Flowchart of the designed hybrid algorithm.

Following are the steps of our proposed hybrid algorithm:

Step 1: Initiate all the constraints of ACO, that is, set the number of and maximum number of iterations along with the maximum number of ants utilize to explore the path-planning scenario.

Step 2: Divide the entire ant colony into three different located ant colonies or sub-colonies. However, the number of ants in each colony logged col_m(n), for the ith colonies.

Step 3: Initialize the edge pheromone for every sub-colony path where ants are allowed to construct the route and to move to the next node.

Step 4: Check whether the ants reached at the target node or not; if no, repeat step 3; if yes, proceed to the next step.

Step 5: Now calculate the route covered by the ants and making condition best ant update the route for every colony. Also calculate the cost from city a to b of the lth ant that belongs to the nth UAV.

Step 6: Mutation and crossover process is applied on the original trail pheromone $τ_{n}$ and every ant colony best ant is passed from their past iteration and produced the new trial pheromone $τ_{2 n}$ .

Step 7: Set $n = 1$ for each ant colony of the nth ant colony; finally, it arrives the target point to construct the route as per trail pheromone $τ_{n}$ . Calculate the distance of route travel by the each ant and select the best shortest path, and save it as $L_{best_2 n}$ .

Step 8: Now, separate each ant of the nth ant colony that visits the entire nodes in 3D dimensional path to increase the trail pheromone $τ_{2 n}$ . Calculate the tour distance reach by each ant and select the shortest one and denote it with $L_{best_2 n}$ .

Step 9: Compare $L_{best_1 n}$ and $L_{best_2 n}$ and start the DE selection operation, set as $τ_{n}$ or $τ_{2 n}$ . If $L_{best_1 n}$ is greater than $L_{best_2 n}$ , select yes; otherwise, no for the next step.

Step 10: Two conditions are there; if in the previous step, condition is yes, it will allow to explore new path and update the pheromone; otherwise, do not need it. Selection process of DE will select the route.

Step 11: Return to Step 6 till $N_{c} \geq N_{c \max}$ .

Step 12: The designed proposed algorithm gives the best optimal route in 3D environment.

Simulation results and discussions

The simulations of path planning via multi-colonies with M-UAVs using MMACO-DE algorithm are divided into two different scenarios. Now, complete the overall scenario constraints of each UAV including the length or distance of flight, attitude angle, altitude and 3D land environment. When UAV fly from one point to the nearest way point, it requires some time to fine tune its attitude and altitude to reach at the nearest node. The length between two nodes or way points are calculated using the formula

{\begin{matrix} L_{i} = \sqrt{{(x_{i} - x_{1 i})}^{2} + {(y_{i} - y_{1 i})}^{2} + {(z_{i} - z_{1 i})}^{2}} \\ L_{i} \geq L_{\max}; (i = 1, 2, 3, \dots) \end{matrix}

(17)

In equation (17), $L_{i}$ is the distance between two nearest nodes and $L_{\max}$ is the maximum flight distance. To escape from the threats, that is, high peaks and mountains, UAV needs to change its flight path. By adjusting the attitude angles of UAV, that limits its maneuverability and practically their real attitude angles are smaller than the maximum attitude angles. In terms of maneuverability, the roll angle is calculated by

\cos φ_{\max} \leq (a_{i} * a_{i + 1} / | a_{i} | | a_{i + 1} |); (i = 1, 2, 3, \dots)

(18)

where $a_{i}, a_{i + 1}$ is the trajectory between two nodes and $φ_{\max}$ is the maximum roll angle of UAV. When UAV is flying in hilly areas, in order to avoid from collision from the high peaks, it needs to change its altitude. To consider the maximum allowed altitude of UAV $Z_{\max}$ and the real-time altitude $Z_{i}$ now, the real altitude should not greater than the maximum allowed altitude, that is, $Z_{\max} > Z_{i}$ .

In order to find the possibility and efficiency of the designed hybrid algorithm for path planning of multi-colonies with M-UAVs, two different simulation scenarios were simulated. Both these simulations were performed in Simulink MATLAB 2016, along with the programming on an Intel Core i7 8th generation. The initial parameters for both scenarios are set to be $α = 2, β = 3, ρ = 0.75, N_{c \max} = 25, Q = 10, τ_{\min} = 0.1, τ_{\max} = 1, m = 10$ . In both the simulations scenarios, the 3D land environment is about 20 km longitudinal, 20 km wider and about 2 km in altitude. The dynamic 3D environment constraints are defined in Table 1.

Table 1.

Constraints of dynamic environment.

No. of terrains	Peak center (xo, yo)	Highest altitude (Z) in km	Declining scale at x axes (xs)	Declining scale at y axes (ys)
1	(16, 4)	0.7098	1.5	2.5
2	(5, 4)	0.8009	2.5	1.5
3	(11.5, 9)	1.5	3	3
4	(15, 16)	0.7017	2	1.5
5	(5, 16)	1.2	2.5	1.5

Scenario 1

In order to verify the effectiveness of our prosed algorithm first, we compare our proposed hybrid algorithm with classical ACO. In this case, two different algorithms are initiated from the same base station and to reach at the designated area by applying cooperative path-planning methodology of UAV. The path-planning optimization results are shown in Figure 6(a) and (b), respectively, and it is clearly evident that our designed algorithm reaches at the destination using the optimal route. Figure 7 shows the estimation costs of both the algorithms, and Table 2 defines the overall comparison of these strategies.

Figure 6.

(a and b) Different views of path-planning scenario by comparing ACO and MMACO-DE.

Figure 7.

Estimation costs of ACO and MMACO-DE.

Table 2.

Comparison of ACO and our proposed algorithm.

Algorithm	Start point	End point	Length of distance in km
ACO	(0, 0, 0)	(20, 20, 1)	29.121
MMACO-DE	(0, 0, 0)	(19.8, 19.8, 1)	25.122

ACO: ant colony optimization; MMACO-DE: maximum–minimum ant colony optimization and differential evolution.

Scenario 2

In this case, three best (ants) UAVs that belong to three different colonies for an aerial combat formation of path planning are assigned to reach at the targeted area simultaneously. All the initial parameters in this case are same except the number of colonies, that is, $col = 3$ . Moreover, in this case, the air collision avoidance and coordination between all UAVs reflected robustly in order to escape from collision and to reach at the destination node using cooperative path-planning constraints. Figure 8 shows the simulated path-planning scenario of multi-colonies with M-UAVs achieved perfectly. Figure 9 presents the estimation costs of different colonies, and Table 3 presents the comparison of all colonies. Finally, Figure 10 presents the best-optimized route found by our designed algorithm. The simulation results show that the proposed MMACO-DE strategy can successfully find the global optimize route and fulfill the mission requirement successfully.

Figure 8.

(a and b) Different views of path-planning scenario using multi-colonies with multiple UAVs.

Figure 9.

Estimation costs of different colonies.

Table 3.

Comparison of proposed algorithm using three different takeoff points.

Entire colony divisions	Start point	End point	Length of distance in km
Colony 1 (UAV 1)	(0, 0, 0)	(20, 19.8, 1)	30.124
Colony 2 (UAV 2)	(0, 5, 0)	(19.8, 19.8, 1)	27.221
Colony 3 (UAV 3)	(0, 10, 0)	(19.8, 20, 1)	23.54

UAV: unmanned aerial vehicle.

Figure 10.

The best-optimized route determined by our designed algorithm.

Conclusion

This study uses hybrid metaheuristic algorithm obtained via MMACO in combination with DE strategy. The proposed algorithm provides optimal 3D route for the path planning of M-UAVs. As seen in the simulation, the ant colony is further divided into small colonies to explore optimal colony for mission completion. The above designed hybrid algorithm offers a platform for multi-colonies path-planning concept that is implemented for the real-world scenario.

Footnotes

Acknowledgements

The authors thank the reviewers and editors for giving valuable comments, which are very helpful for improving this manuscript.

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) disclosed receipt of the following financial support for the research, authorship and/or publication of this article: This research is supported by China National Nature Science Foundation with grant number 61374165.

ORCID iD

Zain Anwar Ali

References

Ong

Y-S

Lim

Chen

. Research frontier—memetic computation—past, present & future. IEEE Comput Intell M 2010; 5(2): 24–31.

Mairaj

Baba

Javaid

. Application specific drone simulators: recent advances and challenges. Simul Model Pract Th 2019; 94: 100–117.

Dash

Watt

Paul

TSH

, et al. Taking a closer look at invasive alien plant research: a review of the current state, opportunities, and future directions for UAVs. Methods Ecol Evol 2019; 10(12): 2020–2033.

Shakhatreh

Sawalmeh

Al-Fuqaha

, et al. Unmanned aerial vehicles (UAVs): a survey on civil applications and key research challenges. IEEE Access 2019; 7: 48572–48634.

Lorenz

Ehrenstrom

Ullmann

, et al. Assessing control devices for the supervisory control of autonomous wingmen. In: 2019 systems and information engineering design symposium (SIEDS), Charlottesville, VA, 26 April 2019, pp. 1–6. New York: IEEE.

Zhao

Zhang

Zhao

. Robust path planning for avoiding obstacles using time-environment dynamic map. Meas Control 2020; 53: 214–221.

Ege

Ankarali

. Feedback motion planning of unmanned surface vehicles via random sequential composition. T I Meas Control 2019; 41: 0142331218822698.

Dhaliwal

Pattnaik

. Performance comparison of bio-inspired optimization algorithms for Sierpinski gasket fractal antenna design. Neural Comput Appl 2016; 27(3): 585–592.

Mirjalili

Gandomi

Mirjalili

, et al. Salp Swarm Algorithm: a bio-inspired optimizer for engineering design problems. Adv Eng Softw 2017; 114: 163–191.

10.

Sahlol

Suen

Zawbaa

, et al. Bio-inspired BAT optimization algorithm for handwritten Arabic characters recognition. In: 2016 IEEE congress on evolutionary computation (CEC), Vancouver, BC, Canada, 24–29 July 2016, pp. 1749–1756. New York: IEEE.

11.

Marini

Walczak

. Particle swarm optimization (PSO). A tutorial. Chemometr Intell Lab 2015; 149: 153–165.

12.

Qiu

Duan

. Multi-objective pigeon-inspired optimization for brushless direct current motor parameter design. Sci China Technol Sc 2015; 58(11): 1915–1923.

13.

Duan

Zhang

, et al. Max-min adaptive ant colony optimization approach to multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments. J Bionic Eng 2009; 6(2): 161–173.

14.

May

Stahl

Taisch

, et al. Multi-objective genetic algorithm for energy-efficient job shop scheduling. Int J Prod Res 2015; 53(23): 7071–7089.

15.

Colorni

Dorigo

Maniezzo

. Distributed optimization by ant colonies. In: Actes de la première conférence européenne sur la vie artificielle, Paris, 11–13 December 1991, pp. 134–142. Amsterdam: Elsevier Publishing.

16.

Kennedy

Eberhart

. Particle swarm optimization. Proceedings of IEEE international conference on neural networks, Perth, WA, Australia, 27 November–1 December 1995, pp. 1942–1948. New York: IEEE.

17.

Storn

Price

. Differential evolution —a simple and efficient adaptive scheme for global optimization over continuous spaces: technical report TR-95-012. Berkeley, CA: International Computer Science, 1995.

18.

Melanie

Holland

John H.

Forrest

. “When will a genetic algorithm outperform hill climbing.” In: Advances in neural information processing systems 1994 pp. 51–58.

19.

Yao

Wang

. Dynamic Adaptive Ant Lion Optimizer applied to route planning for unmanned aerial vehicle. Soft Comput 2017; 21(18): 5475–5488.

20.

Bagherian

Alos

. 3D UAV trajectory planning using evolutionary algorithms: a comparison study. Aeronaut J 2015; 119(1220): 1271–1285.

21.

Zhang

Liu

, et al. Formation reconfiguration based on distributed cooperative coevolutionary for multi-UAV. In: 2016 12th world congress on intelligent control and automation (WCICA), Guilin, China, 12–15 June 2016, pp. 2308–2311. New York: IEEE.

22.

da Silva

Arantes J

da Silva

Arantes M

Motta

Toledo CF

, et al. Heuristic and genetic algorithm approaches for UAV path planning under critical situation. Int J Artif Intell T 2017; 26(1): 1760008.

23.

da Silva

Arantes J

da Silva

Arantes M

Motta

Toledo CF

, et al. A multi-population genetic algorithm for UAV path re-planning under critical situation. In: 2015 IEEE 27th international conference on tools with artificial intelligence (ICTAI), Vietri sul Mare, 9–11 November 2015, pp. 486–493. New York: IEEE.

24.

Zhang

Duan

. An improved constrained differential evolution algorithm for unmanned aerial vehicle global route planning. Appl Soft Comput 2015; 26: 270–284.

25.

Duan

Shi

, et al. Interactive learning environment for bio-inspired optimization algorithms for UAV path planning. IEEE T Educ 2015; 58: 276–281.

26.

Duan

Zhang

, et al. Three-dimension path planning for UCAV using hybrid meta-heuristic ACO-DE algorithm. Simul Model Pract Th 2010; 18(8): 1104–1115.

27.

Cekmez

Ozsiginan

Sahingoz

. Multi-UAV path planning with multi colony ant optimization. In: Abraham

Muhuri

Muda

, et al. (eds) International conference on intelligent systems design and applications. Cham: Springer, 2017, pp. 407–417.

28.

Shao

Yan

Zhou

, et al. Path planning for multi-UAV formation rendezvous based on distributed cooperative particle swarm optimization. Appl Sci 2019; 9: 2621.

29.

Dewangan

Shukla

Wilfred

Godfrey W

. Three dimensional path planning using Grey wolf optimizer for UAVs. Appl Intell 2019; 49(6): 2201–2217.

30.

Zhang

Chen

, et al. Real-time decentralized cooperative robust trajectory planning for multiple UCAVs air-to-ground target attack. Proc IMechE, Part G: J Aerospace Engineering 2015; 229(4): 581–600.

31.

Tharwat

Elhoseny

Hassanien

, et al. Intelligent Bézier curve-based path planning model using Chaotic Particle Swarm Optimization algorithm. Cluster Comput 2019; 22(2): 4745–4766.

32.

Dorigo

. Ant colony optimization. In: Onwubolu

Babu

(eds) New optimization techniques in engineering. Berlin: Springer-Verlag, 1991, pp. 101–117.

33.

Duan

. Bio-inspired computation in unmanned aerial vehicles. Berlin: Springer, 2014.