Bio-Inspired Multi-UAV Path Planning Heuristics: A Review

Abstract

Despite the rapid advances in autonomous guidance and navigation techniques for unmanned aerial vehicle (UAV) systems, there are still many challenges in finding an optimal path planning algorithm that allows outlining a collision-free navigation route from the vehicle’s current position to a goal point. The challenges grow as the number of UAVs involved in the mission increases. Therefore, this work provides a comprehensive systematic review of the literature on the path planning algorithms for multi-UAV systems. In particular, the review focuses on biologically inspired (bio-inspired) algorithms due to their potential in overcoming the challenges associated with multi-UAV path planning problems. It presents a taxonomy for classifying existing algorithms and describes their evolution in the literature. The work offers a structured and accessible presentation of bio-inspired path planning algorithms for researchers in this subject, especially as no previous review exists with a similar scope. This classification is significant as it facilitates studying bio-inspired multi-UAV path planning algorithms under one framework, shows the main design features of the algorithms clearly to assist in a detailed comparison between them, understanding current research trends, and anticipating future directions. Our review showed that bio-inspired algorithms have a high potential to approach the multi-UAV path planning problem and identified challenges and future research directions that could help improve this dynamic research area.

1. Introduction

The need for small autonomous unmanned aerial vehicles (UAVs) has significantly increased since such UAVs can handle dull, dirty, and dangerous tasks for humans. They are applied in many fields [1] including firefighting, precision agriculture, and asset inspection. UAV operational experience proves that their technology offers great advantages, such as performing at superior precision, acquiring high-quality data, maneuvering with extreme capabilities, and reducing operational risk. On the other hand, limited battery lifetime, slow speed, and light payload are among the main concerns that deter wider adoption of UAVs by more public and private sectors [2].

To overcome the above limitations, the focus is shifting to collaborative UAV systems. In fact, most of the UAV applications, such as reconnaissance and disaster response, are better handled by a multiple UAV (multi-UAV) system. A multi-UAV system is more efficient and capable to accomplish difficult missions and cover wider areas than a single UAV system [3]. Additionally, in a single-UAV system, a UAV going down during the mission represents a failure, while an out-of-control UAV is not a problem for multi-UAV systems. Thus, a multi-UAV system is more reliable than a system with a single robot, as multiple robots provide additional redundancy. Furthermore, using sizable UAVs to augment a single-UAV system extends area coverage only to a point. Conversely, multi-UAV systems may quickly expand their operational range [4,5]. Despite these advantages, multi-UAV systems are associated with more challenges due to the need for coordination and communication between the fleet members especially while navigating through the environment to ensure collision-free area coverage [6].

Although the UAV flight control architecture is well established, there are still many challenges in designing autonomous navigation systems for UAVs that can find the shortest path between two points while optimizing a set of performance measures. The trade-offs between feasibility, safety, power consumption, and the computation limitation and highly non-linear dynamics that characterize these devices are what make the UAV path planning problem a daunting task [7]. Therefore, a plethora of path-planning algorithms for UAVs has been proposed, e.g., [8,9,10,11,12,13], based on classical and bio-inspired approaches.

Bio-inspired approaches are showing a remarkable increase in utilization to overcome the multi-UAV path planning problem, with a counterpart decrease in classical algorithms’ popularity [9,14]. Classical path planning approaches, such as the cell decomposition approach [15] and artificial potential field [16], are limited by their high processing cost, long running time, and inability to respond to environmental uncertainty [9,14]. On the other hand, bio-inspired heuristics have demonstrated the capacity to overcome these shortcomings [17,18] since they can learn and adapt similar to biological systems, enabling them to handle environmental uncertainty [8,9,11], especially in parallel processing environments [14]. The recent reviews of UAV path planning systems emphasize the fact that bio-inspiration is one of the main approaches that can give good quality solutions for complex and dynamic environments while handling UAV’s constraints [13]. However, previous reviews have not focused on bio-inspired approaches specifically for the UAV path planning problem. Moreover, most reviews cover various path-planning techniques for general UAV systems, and only two papers [12,13] addressed multi-UAV path planning as a distinct problem from single-UAV path planning. These reviews omitted important aspects of many existing algorithms, such as their scope and mode. To fill these gaps, this paper presents a systematic review of the literature on the bio-inspired algorithms for the multi-UAV path planning problem.

Table 1. Discussion of previous literature reviews.

Ref.	Year	Discussion			Focus
		Bio-Inspiration	Multi-UAV	Mission Type
[8]	2020	Only PSO	Not considered	Not considered	They analyzed the previous work based on Path length; Optimality; Completeness; Cost efficient; Time efficient; Energy-efficient; Robustness; Collision avoidance
[9]	2019	Not considered	Considered multi-robot only	Not considered	They analyzed the previous work based on environment (goal and obstacle), hybrid approach or not, multi-robot, real-time, simulation result, and Kinematic analysis
[10]	2020	Not considered	Not considered	Not considered	They classified the previous work based on task, centralized/decentralized, environment known or unknown, real-time, collision avoidance among UAVs, connectivity, formation, synchronicity, heading, and coordination
[11]	2018	Not considered	Not considered	Not considered	They reviewed pertinent research concerning the various Computational Intelligence algorithms used in UAV path-planning, the categories of time domain in UAV path-planning, namely offline and online, and the types of environment models, namely 2D and 3D.
[12]	2022	Not considered	Consider multi-UAV	Not considered	They discussed different path-planning approaches in terms of contributions and limitations only
[13]	2022	PSO, ACO, Artificial Bee Colony, PIO, GWO, Differential Evolution algorithm, GA	Considered multi-UAV	Not considered	They discussed classical methods, heuristics, meta-heuristics, machine learning, and hybrid algorithms of path planning. They analyzed the approaches based on targeted objectives, considered constraints, and environments

shows a comparison of the previous surveys.

The scope of this paper is limited to bio-inspired algorithms and does not include other types of algorithms that can support multi-UAV path planning. Additionally, it does not aim to provide a comprehensive analysis of all the studies related to multi-UAV path planning using bio-inspired algorithms, but rather to provide a brief overview of each algorithm, how it works, and how it has been evaluated.

This paper makes several significant contributions. First, it reviews the previous literature on bio-inspired multi-UAV path planning algorithms and presents a structured classification of them. This classification is significant as it facilitates studying bio-inspired multi-UAV path planning algorithms under one framework. Second, it shows the main design features of the algorithms clearly and assists in a detailed comparison between them. Third, it helps in understanding current research trends and anticipating future directions. Fourth, it provides a standard set of terminologies for multi-UAV path planning algorithms to establish a solid framework for this rapidly evolving area of research.

This review defines the various problems, and algorithms used in bio-inspired multi-UAV path planning. The research questions that guided this work are:

• What are the different bio-inspired approaches used in multi-UAV path planning?
• What are the most commonly considered factors in bio-inspired approaches for multi-UAV path planning?
• What are the most frequently used techniques for implementing coordination schemes, planning modes, and navigation scope in bio-inspired multi-UAV path planning?
• What are the limitations and challenges of developing and implementing bio-inspired multi-UAV path planning algorithms?
• What key research directions need to be addressed to overcome these limitations and challenges?

The remainder of this paper is organized as follows. Section 2 describes the multi-UAV path planning problem and algorithms. In Section 3, we present the proposed systematic review (SR) methodology. In Section 4, we present the SR of the current literature on bio-inspired multi-UAV path planning algorithms. Section 5 discusses and analyzes the current research trends of the surveyed literature, followed by conclusions and future research directions in Section 6.

2. Background

2.1. The Multi-UAV Path Planning Problem

Path planning is an important task of any navigation system, which usually encompasses three functions: localization, mapping, and path planning [18,19]. In the robotics context, path planning involves finding a route that enables a robot to move from a starting location to a goal [9,19]. The problem is an NP-hard problem (nondeterministic polynomial-time) [18,20]. The multi-robot path planning problem can be defined as follows: given a set of m robots in a k-dimensional workspace, each with an initial starting configuration (e.g., position) and the desired goal configuration, determine the path each robot should take to reach its goal while avoiding collisions with obstacles and other robots in the workspace [5]. While single-robot path planning finds an optimal or suboptimal path for the robot from the initial position to the target position based on optimization criteria [21], multi-robot path planning aims to find a path for each robot, between specific start and goal locations, while optimizing the overall system global cost function [22]. The problem grows in complexity as more robots participate in the mission [22,23,24]. Furthermore, unlike single-robot path planning, multi-robot path planning needs to deal with the robot collision problem as a moving robot might be seen as a dynamic impediment [25].

Since a UAV is viewed as a flying robot, the discussion of multi-robot problems also applies to multi-UAV systems [26] but with an added layer of complexity due to their flying and limited resources features. The multi-UAV path planning problem is usually viewed as a form of the multiple Traveling Salesman Problem (TSP). The TSP with multiple UAVs can be seen as a task allocation problem to optimize a certain set of performance measures by assigning each target, or group of targets, to one UAV [27]. Performance can be measured based on the ability to find the shortest, cheapest, or safest paths to help achieve a system-wide goal [7]. Another well-known problem that has been extended to multi-UAVs is Vehicle Routing Problem (VRP). VRP is a generalization of the TSP problem [28]. The TSP and the VRP are both NP-Hard routing problems [29]. The primary distinction between a TSP and a VRP is that the salesperson must return to the initial location after visiting several points [30]. VRP is typically employed when delivering products from a central depot to consumers who have ordered those products [28]. Some applications consider a hybrid model that includes ground vehicles to support UAV routes [31] such as the study [32,33].

Figure 1 shows the main parameters that are usually used to describe the multi-UAV path planning problem which includes:

• Origin/starting point/source: It is also known as the depot in the traveling salesman problem (TSP) [34,35]. It represents the current location of the UAV or the initial location from where the UAV should start traveling. A path planning problem for a single UAV system usually requires one starting location, however, for a multi-UAV system, there might be a shared starting location or several starting locations.
• Goal/end point/destination/target: It represents the final location where the UAV should stop. There can be one or more goals. Goals can be known or unknown in advance. They can be static, i.e., stationary throughout the mission, or dynamic. i.e., change their locations over time [4]. The schemes of goals can be one following:
  • One shared goal for all UAVs: There is one goal, and all UAVs will have to visit this goal.
  • Multiple goals, one for each UAV(One-for-each): Each UAV is allowed to visit exactly one goal.
  • Multiple goals for each UAV (Multi-for each): There are multiple sets of goals, and each set can be visited by precisely one UAV. In this case, the sets are assigned at an initial phase for each UAV [24]. or each UAV searches for its goals set [36,37]. Alternatively, sets of goals can be overlapping, as shown in Figure 2.
• UAVs: A multi-UAV system can be composed of homogenous vehicles, i.e., with identical features and capabilities, or heterogeneous vehicles, i.e., with different capabilities [38]. A key feature, especially for a multi-UAV system, is collision avoidance (CA). CA is an important capability when there are obstacles or multiple UAVs in the environment. However, CA adds a layer of complexity and challenges, hence, sometimes it is ignored based on certain assumptions [39]. In 3D environments, in particular, CA is an issue that should be explicitly handled either by an altitude layering approach which means that each UAV flies at a different altitude [40,41], or through a safe distance approach where the distance between any two UAVs should not exceed a safe distance [10].
• Environment (Env.): It is the workspace in which a UAV navigates which can be embodied in two-dimensional (2D) or three-dimensional (3D) planes. A map representation is usually developed for the environment which can be known, unknown, or partially known [10,42]. A known map accurately represents the environment and encapsulates all of its details, such as the surrounding area and obstacles, while a map with approximate or uncertain information is considered partially known. On the other hand, in an unknown environment, where a UAV can only acquire further knowledge about the surroundings during navigation, the map is considered unknown [43]. Another primary characteristic of the environment affecting path planning problems is its evolution which can be static or dynamic [4]. A static environment comprises unchanging settings while a dynamic environment includes moving objects, usually obstacles or other UAVs [44], which change the environment geometry [45]. Dynamicity of the environment can be handled by either replanning the initial path or calculating the probability of the target position in different cells or time frames. However, replanning the initial path can encounter limitations when certain thresholds have been exceeded, such as in [46,47].

2.2. Multi-UAV Path Planning Algorithms

The open challenges related to time efficiency and computational burden associated with the multi-UAV path planning problem have attracted researchers to set up different approaches that encompass traditional and bio-inspired techniques. These techniques differ mainly in the choices of how these techniques implement coordination scheme, planning mode, navigation scope, and objective function, as shown in Figure 3:

• Mode: The path planning mode can be offline or online. An offline planner constructs the path before motion begins. In contrast, an online planner incrementally constructs the plan while the UAV is in motion [48,49]. Typically, it is recommended to combine the two approaches to maximize their strengths [17].
• Coordination: The coordination process in a multi-UAV system describes the control structure and communications scheme between the vehicles.
  • Control can occur in a centralized or decentralized manner [50,51]. In centralized planning approaches, a single control agent acts as a leader to ensure coordination among the entire team of UAVs [18,51]. This central agent (e.g., a control station) usually has global knowledge about network status and each robot’s interactions [18,50]. Decentralized architectures can be further divided into distributed architectures and hierarchical architectures. In hierarchical coordination, multiple-leader robots operate as central nodes for smaller groups of robots. Then, each leader coordinates with other leaders’ space [50,52].
  • On the other hand, distributed approaches lack a central agent; instead, the individual agents plan and adjust their paths. The decisions are distributed on the robot team’s side, not determined by a base station [18,51,52,53]. Hence, distributed systems are more robust and fault-tolerant than centralized approaches [18]. Specific applications follow a hybrid approach to leverage the advantages of both centralized and distributed methods [53].
  • It is worth noting that the terms decentralized and distributed are used interchangeably in the literature (e.g., the study [53]), although referring to distinct elements of the decision-making policy of the system: authority and responsibility. As a result, we can have a decentralized system in which the responsibility is not distributed equally but in a hierarchal scheme, as illustrated before.
  • Communications allow sharing of information between robots to enhance their perception of the environment and inform the decision-making required for motion planning [4]. Communications can be categorized based on how the robots exchange information to direct/explicit and indirect/implicit communications. In explicit communications, robots share information directly, which might take the form of unicast or broadcast messages, while in implicit communications a robot learns about other robots in the system by observing its environment [50].
• Scope: Based on the information scale considered while generating the path, planners can be classified as global, local, or hybrid/mixed [19,48]. If information about the entire environment is used to plan the path, the planners are considered global. Global planners are known for their efficiency when the environment map is perfectly known and the environment is static, therefore, they are also known as static planners. In contrast, local path planners only consider the area surrounding the vehicle, they are essential when no environment map is available or when the environment is dynamic, thus they are known as dynamic or reactive planners [3,4,8,9,42]. In hybrid path planning, both types are used together; a local planner takes the path from a global planner and then dynamically adjusts it according to obstacles in the environment [54].
• Objective function: An optimization criterion that is defined by the objective function is required for finding a path. An objective function can be a multi-objective, single-objective, or single-objective with weights (where multi-objective weights are balanced and transformed to single-objective weights) function that should be maximized or maximized [55]. There are many standard optimization objectives in cooperative path planning, and the common ones: are cost minimization, payoff optimization, performance optimization, and risk minimization, such as threats or flight altitude. The objective function may have different formulations in different scenarios [10].

3. Review Methodology

This study involved a comprehensive search using the Web of Science (WoS) database [56] to find publications on multi-UAV path planning based on bio-inspired algorithms from 2013 through 2021. We started by retrieving all English publications that include multi-UAV/multi-drone and path planning/pathfinding among their keywords, as shown in Listing 1.

Listing 1. Query used to retrieve literature studies.

(((ALL = (Multi* AND UAV AND path AND planning)) AND LANGUAGE: (English)) OR

((ALL = (Multi* AND UAV AND path AND finding)) AND LANGUAGE: (English)) OR

((ALL = (Multi* AND drone AND path AND finding)) AND LANGUAGE: (English)) OR

((ALL = (Multi* AND drone AND path AND planning)) AND LANGUAGE: (English)))

Initial search results returned 623 items to which we applied our selection criteria for the first filtering process. Figure 4 shows our research methods, the review process, and the filtering procedures. In this figure, we followed the PRISMA guidelines [57].

In the first filtering process, the resulting records or publications were revised and excluded from our survey based on the following criteria:

• The article was published between 2013 and 2021.
• Conference papers, posters, or demos as these publications do not provide adequate information about contributions due to a lack of supplied content to evaluate.
• Articles with an unavailable full text through WoS.

The first revision cycle ended with 287 search results. Then, we carried out a second screening procedure in which we manually reviewed each research paper to exclude articles. From the resulting list, publications encompassing one or more of the following criteria were excluded:

• Survey papers.
• Articles that do not consider UAVs as an agent in the system.
• The proposed algorithm is not a bio-inspired algorithm or any algorithm that is hybridized with a bio-inspired algorithm.
• The article did not include path planning as the main topic or one of the achieved contributions.
• Articles focusing on UAV hardware—The paper’s contribution is limited to UAV manufacturing, i.e., the design of hardware, mechanical, and electronic components of UAVs.
• Articles focusing on single-UAV path planning. The paper contributes only to single-path planning systems.
• Articles focusing on navigation functions other than path planning, such as mapping or localization techniques.
• Articles focusing only on developing a simulation tool or a framework for UAVs.

After scanning article titles, abstracts, keywords, and conclusions during the second revision round, we were left with 287 articles. Next, we screened the remaining papers again in a fine-grained stage, this time reading the entire body. Finally, we read the full text of the remaining 38 articles in the third revision cycle. We eliminated 10 more articles because we found that one or more of the exclusion criteria above applied to them. The remaining 28 articles were considered for review. At this point, data was extracted from each relevant publication based on the main factors described in Section 1 and archived according to the format shown in

Table 2. Data archiving format for each publication.

Attribute			Value/Description
Paper info	Title		The paper title
	Year		The year when the paper was published in WoS
Proposed approach	Name		The specific title and acronym used in the paper to refer to the proposed approach.
	Type		Original, enhanced, or hybrid
	Application domain		The context in which the path planning was applied in the proposed approach
Problem	Origin		One or multiple
	Goal		One or multiple
			Known or unknown or probability known
			Static or dynamic
	UAVs	Team	Homogeneous or heterogeneous
		CA	With UAVs With obstacles With both UAVs and obstacles None
	Environment	Representation	2D or 3D
		Map	Known, unknown, or partially known
		Evolution	Static, dynamic, or hybrid
			Dynamic element (obstacles, other UAVs, or both)
Algorithm	Coordination	Communication	Explicit or implicit
		Control	Centralized, decentralized, or distributed
	Scope		Local, global, or hybrid
	Planning mode		Online, offline or hybrid
	Objective function	Type	Single, single with weighted-sum or multi
		Criteria	Minimize or maximize
		Constraints	List of problem constraints
Evaluation	Approach		Real system or simulation
	Benchmarks		List of benchmark algorithms used in the evaluation against the paper’s proposed approach
	Performance measures		The indicators used to assess the achievements of the proposed approach

. For each publication, we recorded the article title and publication date, the given name of the proposed algorithm, and its acronym if any. Additionally, for each algorithm, we specified whether it is an original algorithm or an enhancement of an original algorithm, or a hybridization from different algorithms. We also noted the considered application domain whether civil, military, or other.

After that, we focused on more detailed information about each examined path planning problem including whether the considered UAV team is homogeneous or heterogeneous and do UAVs fly from a shared starting point and arrive at a shared goal or instead there are multiple sources or destinations. Whether the environment is static or dynamic has also been recorded. We considered environmental dynamics if the targets or obstacles changed positions or new targets or obstacles were added during the execution of the mission; otherwise, the environment was considered static. We also noted dynamic elements such as obstacles or targets changing position and moving. Information about collision avoidance features has also been considered and whether it included collisions with both other UAVs and obstacles or only one of them.

Additionally, for each study, we recorded whether the approach is conducted in a 2D or 3D environment. In the case of a 3D environment, we examined the method for handling the z coordinate. The factors related to the algorithm which include its coordination approach (i.e., centralized versus distributed), the planning approach (online, offline, or hybrid), and whether the algorithm scope was local, global, or hybrid have also been studied. Moreover, we noted the objective function. We classified objective functions as multi-objective, single-objective, and single-objective with weights (where multi-objective weights are balanced and transformed to single-objective weights). We also recorded the values to be minimized or maximized with the objective function. Furthermore, we listed any constraints included in the problem formulation. We also recorded any tools used in the paper for implementation and whether the authors conducted simulation or/and real-life experiments using physical UAVs. Moreover, we listed the benchmark algorithm used in evaluating the approach.

4. Bio-Inspired Multi-UAV Path Planning Algorithms

Although many bio-inspired algorithms were introduced decades ago, such as the basic genetic algorithm (GA) which was coined in the 1960s, they were not applied to multi-robot path planning systems until 2013 [8]. Undoubtedly, fewer studies have applied these algorithms to the multi-UAV path planning problem. Interestingly, some bio-inspired algorithms, such as ant colony optimization (ACO), and pigeon-inspired optimization (PIO), were initially proposed for the path planning problem in particular.

Our survey revealed that the entire retrieved collection of bio-inspired multi-UAV path planning algorithms originated from eight algorithms: particle swarm optimization (PSO), genetic algorithms (GA), gray wolf optimization (GWO), ant colony optimization (ACO), pigeon-inspired optimization (PIO), fruit fly optimization (FOA), life-cycle swarm optimization (LSO), and intelligent water drops (IWD). We called these algorithms original algorithms since they have been applied to the multi-UAV path planning problem without tailoring them to this specific problem and to distinguish them from the initial proposals of the algorithms regardless of their application area which we referenced as basic algorithms. The other algorithms are either a variant of one of the above eight algorithms proposed to better deal with the complexity of the multi-UAV path planning problem, we called them enhanced algorithms or hybridization of two or more algorithms from previous work, we called this group hybrid algorithms. However, a small set of algorithms has not followed any the of aforementioned approaches, we called them others. Figure 5 shows our categorization of the reviewed bio-inspired multi-UAV path planning algorithms.

4.1. PSO and Its Variants

PSO algorithm is a stochastic population-based metaheuristic algorithm developed by Eberhart and Kennedy [58,59] in 1995 to simulate social and cognitive behaviors. The algorithm is inspired by the social behavior of fish schools or bird flocks. While searching for food, the behavior of each member in these groups, referred to as a particle, is affected by its past experiences and by the group member nearest to the food. The group reaches its end goal, i.e., food sources, by communicating its search findings. Due to its effectiveness, PSO has become a fast-growing optimization method for handling various problems in science and engineering, including the path planning problem. However, it suffers from two disadvantages where it can easily stuck into local optima and it has a low convergence rate [60,61]. Although PSO has a simple structure, few parameters, and is easy to implement [62], it is not suitable for discrete problems [63]. For discrete PSO, new forms of “motion” and “velocity” are required [63]. Additionally, in the PSO search space, there is no mechanism for significant rapid movement which leads to leading to poor performance [60].

4.1.1. Original PSO

Interestingly, the original PSO algorithm was only applied in multi-UAV path planning after some improved versions of it had been already used. Original PSO was first applied, in 2020, by Teng et al. [64] during a surveillance mission to detect illegal drones. A multi-UAV centralized surveillance system was developed to generate optimal 3D trajectories using a single-objective function, which considers energy consumption, flight risk, and area priorities with the associated cost for each component. A simulation study was conducted using several UAVs to show that the fitness value converges to a stable value as the number of iterations and particles increases. Figure 6 presents the main steps in the PSO algorithm which comprises a group of particles in which each particle is a possible solution. Initially, the particles are set to random candidate solutions, and the PSO algorithm allows global information sharing. Therefore, each particle’s movement is guided by its own best-known position (local) in the search space and the global best-known position [65].

4.1.2. Enhanced PSO

In 2017, Liu et al. [37] studied the problem of using multiple UAVs to search for moving targets with sensing capabilities in an uncertain 2D environment. They developed a coverage search path planning optimization model and a hybrid PSO to tackle the problem to optimize the opportunity for cumulative target discovery. In the enhanced algorithm, the particles not only update their speeds and positions but also undertake pairwise crossover operations to make offspring particles and replace the present particles. For information sharing and path coordination, an explicit approach was followed where all UAVs utilize the same search map to display current environment data, and continually update the search map. A simulation study was conducted to compare the enhanced PSO with the original PSO which found that the enhanced version revealed more targets than the original algorithm under the same conditions.

In 2019, Liu et al. [66] proposed another enhanced PSO algorithm to improve the original PSO and overcome the disadvantages of local optima and slow convergence. The enhanced algorithm generates 4D paths for multiple UAVs sharing the exact arrival time at a shared destination. The objective function considers multiple factors including obstacle and threat avoidance, estimated arrival time (ETA), safety distance, and UAV self-constraints. The influence of UAVs number on path length and the distance between UAVs was examined using a simulation study which revealed that the proposed approach provides better results as the number of UAVs increases when compared to the A star (A*) [67], and Tau Theory [68] algorithms.

In the same year, Yan et al. [69] used multiple heterogeneous UAVs carrying different resources to perform search and attack missions where several UAVs (coalition) can attack a target simultaneously. They addressed the coupled task allocation and path planning problems by a distributed cooperative PSO algorithm. The algorithm generates flyable and safe trajectories for a UAV coalition to achieve simultaneous arrival. The particles of each subpopulation of the PSO algorithm distribute their values so that other subpopulations can modify the fitness of their particles accordingly. They used weights to balance the reward of the target and the cost of the UAV coalition to maximize the system’s utility.

Zhen et al. [70], in 2020, proposed another PSO enhancement on a multi-UAV path planning mission from a shared source to a shared target point based on a multi-objective function, optimizing the length, height, and turning angle of the path. The proposed algorithm enhanced the original PSO by adding a vibration function to avoid collisions between UAV paths and improving the selection of the global best position using a reference point method. A 3D modeling method that combines the polar coordinates with a continuous 2D path planning method was developed to reduce the particle dimension and the number of iterations. The simulation experiments that were conducted to compare the performance of the proposed approach with other enhanced PSO algorithms, the multi-objective PSO [71] and the nondominated sorting genetic algorithm [72], showed the superior performance of the proposed algorithm.

4.1.3. Hybrid PSO

Shen et al. [46] developed a PSO-based multi-UAV path planning algorithm for detecting ship air pollution in a dynamic environment. To minimize the challenges in such a dynamic environment, the algorithm considered a 2D world, neglected collision avoidance, and used a threshold to decide whether to replan the path. The algorithm incorporated a tabu table and a minimum ring method into PSO to improve its optimization ability. A single-objective cost function with weights was used to minimize the total cost of the flight electricity for the UAV fleet and the time of each UAV’s formation detection. The main considered constraints include the consumed power by a UAV should not exceed its remaining power, and the remaining power should enable it to fly to the nearest charging point. The proposed approach achieved better optimization than the original PSO in a simulated environment of three UAVs.

Shao et al. [65] evaluated an improved PSO (IPSO) when combined with Gauss pseudo-spectral method (GPM). They developed a hierarchical hybrid optimization scheme where the first layer uses IPSO to find a feasible path with the shortest possible length. The IPSO proposed three main improvements to the original PSO, which include adaptive adjustments to acceleration coefficients, maximum velocity, and particle positions. The second layer utilizes GPM to plan a trajectory for each UAV with the minimum flying time and considering the constraints involved in collision avoidance between UAVs and obstacle avoidance with no-fly zones. Numerical simulation using the three UAVs showed that both PSO and IPSO could guarantee viable paths, however, the IPSO fitness value was smoother and converged faster than that of the original PSO. Additionally, trajectories generated by IPSO-GPM are all flyable and have better obstacle avoidance than the original GPM. Furthermore, the proposed schemes have faster running times when compared to the original schemes.

Ahmed et al. [73] proposed a distributed trajectory planner based on PSO and the Bresenham algorithm [74] to generate optimal trajectories for a multi-UAV surveillance system. The PSO was used to generate the optimal trajectories, while the Bresenham algorithm ensured full coverage of the operational area.

In an attempt to further hybridize PSO to enhance its performance, Wang and Liu [75] merged PSO with the artificial potential field algorithm [76] to study the hybrid mode of path planning for a multi-UAV monitoring mission after an earthquake based on virtual reality technology. In their method, the environment constituted a 3D flight space and multi-degree freedom navigation. The initial path planning took place with the Dijkstra algorithm before its optimization using the hybrid PSO. The evaluation of the proposed hybrid algorithm against the multitarget tracking algorithm and ACO showed its efficiency. Table 3 summarizes reviewed path planning approaches for multi-UAV systems based on the PSO algorithm and its variants.

4.2. GA and Its Variants

GAs are one of the oldest search-based optimization algorithms [40]. This algorithm has a population that includes individuals characterized by genes. Each individual is set to a fitness value given an objective function. The best individuals are chosen according to their fitness value, and a crossover between these individuals occurs. The crossover process allows the best individuals to pass their genes, and a mutation process is added to ensure diversity in the new generation of individuals. Despite the known advantages of GA, such as parallel capabilities, global optimization, and application to a wide range of functions, it has some limitations, such as no guarantee of an optimal solution and a low convergence rate [9,77], which wastes time and makes it unsuitable for optimizing multi-UAV path planning applications [78]. However, GA has potential due to its parallel nature. It provides a wide range of possibilities for acceleration over several cores or machines and can take advantage of enormous quantities of capacity when available, as demonstrated in recent research articles [79].

Table 3. Comparison of the reviewed multi-UAV bio-inspired algorithms.

Ref.	Approach Type	Problem										Algorithm				Objective Function Type	Evaluation
		Origin	Goal			UAVs		Environment
		One/Multiple	One/Multiple	(S/D)	Known	Team	CA	Representation	Map	Obstacles		Communication	Control	Scope	Planning		Approach
										S/D	K
PSO
[37]	En	M	M/E	D	P	HO	-	2D	PK	-	-	-	-	L	On	S-WS	Sim
[69]	En	M	1	S	UK	HT	U + O	3D	PK	S	K	E	D	Hd	Hd	S-WS	Sim
[66]	En	M	1	S	K	HO	U + O	4D	K	S	K	-	-	G	Off	M	Sim
[64]	Ori	M	M/E	S	K	HO	U + O	3D	K	S	K	E	C	G	Off	M	Sim
[70]	En	1	1	S	K	HO	U + O	3D	K	S	K	-	-	G	Off	M	Sim
[46]	Hd	M	M/E	D	UK	HO	-	2D	PK	-	-	E	C	Hd	Hd	S-WS	Sim
[65]	Hd	M	1/E	S	K	HO	U + O	3D	K	S	K	-	-	G	Off	SGL	Sim
[73]	Hd	1	M/E	S	K	HO	U + O	3D	K	S	K	E	Dist	G	Off	M	Sim
[75]	Hd	M	M/E/O	S	K	HO	O	3D	PK	S/D	K + UK	-	-	Hd	Hd	SGL	Sim
GA
[36]	En	M	1/E	S	K	HO	U + O	3D	K	S	K	-	-	G	Off	M	Sim
[80]	En	M	M/E	S	K	HO	U + O	3D	K	S	K	E	C	G	Off	S-WS	Sim
[81]	Ori	1	M/E	S	UL	HT	U	3D	PK	-	-	-	-	Hd	Hd	M	Sim
[82]	En	M	M/E/O	S	K	HT	U	3D	PK	-	-	E	Dist	G	Off	S-WS	Sim + R
[83]	Hd	M	M/E	S	K	HO	U + O	3D	K	S	K	-	-	G	Off	SGL	R
[84]	Ori	M	M/E	S	K	HO	U	2D	K	-	-	-	-	G	Off	M	Sim
[78]	Hd	M	M/E	S	K	HO	-	2D	K	-	-	-	-	G	Off	SGL	Sim
GWO
[85]	Ori	M	1	S	K	HO	O	2D	PK	D	K + UK	-	-	L	On	M	Sim
[86]	Ori	M	1/E	S	K	HO	U + O	3D	K	S	K	-	-	G	Off	SGL	Sim
[87]	En	M	1	S	K	HO	U + O	3D	K	S	K	E	Dist	G	Off	S-WS	Sim
[88]	Hd	M	1/E	S	K	HO	U + O	3D	k	S	K	-	-	G	Off	S-WS	Sim
ACO
[89]	En	M	M/E	S/D	P	HO	-	2D	-	-	-	I	-	G	Off	SGL	Sim
[90]	En	M	M/E	S	UK	HT	U + O	3D	PK	D	UK	E	Dist	Hd	Hd	M	Sim
[24]	Hd	M	M/E	S	UK	HT	-	3D	PK	N	N	E	C	Hd	Hd	SGL	Sim
PIO
[6]	En	M	1/E	S	K	HO	U + O	3D	K	S	K	E	Dist	G	Off	SGL	Sim
[47]	En	M	M/E	D	P	HO	U + O	2D	PK	S	K	E	Dist	L	On	M	Sim
FOA
[91]	En	1	M	S	UK	HO	O	3D	PK	S	S	-	-	-	Hd	Hd	S-WS
LSO
[92]	Ori	M	1/E	S	K	HT	O	3D	K	S	K	E	C	G	Off	S-WS	Sim
Evolutionary
[93]	Hd	-	1	D	P	HO	U	3D	PK	-	-	-	-	Hd	Hd	S-WS	Sim

Ori: Original; En: enhanced; Hd: hybrid; M: multiple; M/E: multiple goals for each UAV; 1/E: one goal for each UAV; M/E/O: multiple goals for each UAV with overlapping; S: static; D: dynamic; P: probability known; UK: unknown; K: known; PK: partially known; HO: homogeneous; HT: heterogeneous; O: Obstacles; U: UAV; U + O: UAVs and Obstacles; E: explicit; I: implicit; C: centralized; Dist: distributed; Off: offline; On: online; SGL: single-objective; S-WS: single-objective (weighted sum); Sim: simulation; “-“: not mentioned.

Table 3. Comparison of the reviewed multi-UAV bio-inspired algorithms.

Ref.	Approach Type	Problem										Algorithm				Objective Function Type	Evaluation
		Origin	Goal			UAVs		Environment
		One/Multiple	One/Multiple	(S/D)	Known	Team	CA	Representation	Map	Obstacles		Communication	Control	Scope	Planning		Approach
										S/D	K
PSO
[37]	En	M	M/E	D	P	HO	-	2D	PK	-	-	-	-	L	On	S-WS	Sim
[69]	En	M	1	S	UK	HT	U + O	3D	PK	S	K	E	D	Hd	Hd	S-WS	Sim
[66]	En	M	1	S	K	HO	U + O	4D	K	S	K	-	-	G	Off	M	Sim
[64]	Ori	M	M/E	S	K	HO	U + O	3D	K	S	K	E	C	G	Off	M	Sim
[70]	En	1	1	S	K	HO	U + O	3D	K	S	K	-	-	G	Off	M	Sim
[46]	Hd	M	M/E	D	UK	HO	-	2D	PK	-	-	E	C	Hd	Hd	S-WS	Sim
[65]	Hd	M	1/E	S	K	HO	U + O	3D	K	S	K	-	-	G	Off	SGL	Sim
[73]	Hd	1	M/E	S	K	HO	U + O	3D	K	S	K	E	Dist	G	Off	M	Sim
[75]	Hd	M	M/E/O	S	K	HO	O	3D	PK	S/D	K + UK	-	-	Hd	Hd	SGL	Sim
GA
[36]	En	M	1/E	S	K	HO	U + O	3D	K	S	K	-	-	G	Off	M	Sim
[80]	En	M	M/E	S	K	HO	U + O	3D	K	S	K	E	C	G	Off	S-WS	Sim
[81]	Ori	1	M/E	S	UL	HT	U	3D	PK	-	-	-	-	Hd	Hd	M	Sim
[82]	En	M	M/E/O	S	K	HT	U	3D	PK	-	-	E	Dist	G	Off	S-WS	Sim + R
[83]	Hd	M	M/E	S	K	HO	U + O	3D	K	S	K	-	-	G	Off	SGL	R
[84]	Ori	M	M/E	S	K	HO	U	2D	K	-	-	-	-	G	Off	M	Sim
[78]	Hd	M	M/E	S	K	HO	-	2D	K	-	-	-	-	G	Off	SGL	Sim
GWO
[85]	Ori	M	1	S	K	HO	O	2D	PK	D	K + UK	-	-	L	On	M	Sim
[86]	Ori	M	1/E	S	K	HO	U + O	3D	K	S	K	-	-	G	Off	SGL	Sim
[87]	En	M	1	S	K	HO	U + O	3D	K	S	K	E	Dist	G	Off	S-WS	Sim
[88]	Hd	M	1/E	S	K	HO	U + O	3D	k	S	K	-	-	G	Off	S-WS	Sim
ACO
[89]	En	M	M/E	S/D	P	HO	-	2D	-	-	-	I	-	G	Off	SGL	Sim
[90]	En	M	M/E	S	UK	HT	U + O	3D	PK	D	UK	E	Dist	Hd	Hd	M	Sim
[24]	Hd	M	M/E	S	UK	HT	-	3D	PK	N	N	E	C	Hd	Hd	SGL	Sim
PIO
[6]	En	M	1/E	S	K	HO	U + O	3D	K	S	K	E	Dist	G	Off	SGL	Sim
[47]	En	M	M/E	D	P	HO	U + O	2D	PK	S	K	E	Dist	L	On	M	Sim
FOA
[91]	En	1	M	S	UK	HO	O	3D	PK	S	S	-	-	-	Hd	Hd	S-WS
LSO
[92]	Ori	M	1/E	S	K	HT	O	3D	K	S	K	E	C	G	Off	S-WS	Sim
Evolutionary
[93]	Hd	-	1	D	P	HO	U	3D	PK	-	-	-	-	Hd	Hd	S-WS	Sim

Ori: Original; En: enhanced; Hd: hybrid; M: multiple; M/E: multiple goals for each UAV; 1/E: one goal for each UAV; M/E/O: multiple goals for each UAV with overlapping; S: static; D: dynamic; P: probability known; UK: unknown; K: known; PK: partially known; HO: homogeneous; HT: heterogeneous; O: Obstacles; U: UAV; U + O: UAVs and Obstacles; E: explicit; I: implicit; C: centralized; Dist: distributed; Off: offline; On: online; SGL: single-objective; S-WS: single-objective (weighted sum); Sim: simulation; “-“: not mentioned.

4.2.1. Original GA

The original GA follows the same steps as the basic GA. However, the original encodes the UAVs’ serial numbers or numbers in the chromosome representation. The best chromosomes are found at the last generation of mutation and crossover, representing the UAVs’ paths. Figure 7 shows a flow chart of the path planning GA algorithm for multi-UAV applications [81]. A couple of original GA studies were proposed. In 2017, Wilhelm et al. [81] developed a path planner for a heterogeneous multi-UAV system based on GA to search for a target of interest (TOI) in a surveillance mission. A multi-objective function was adapted to maximize the covered distance while ensuring that the inspection of POIs was well distributed. Simulation scenarios with different numbers of UAVs and TOI locations results indicated that the proposed GA-based algorithm provided additional surveillance of the TOI while reducing the overall mission time. However, the proposed algorithm was not evaluated against other path planning algorithms.

In 2019, Cao et al. [84] proposed a GA-based path planning algorithm for cooperative reconnaissance missions of multiple UAVs. They considered the problem when each UAV has a different base, i.e., start point, and used graph theory to transform this problem into the shortest path combinatorial optimization problem. The objective function was to minimize the residence time for effective detection of enemy radars. The suggested scheme was tested in a simulated reconnaissance mission of sixty-eight targets, eight UAVs, and four bases to demonstrate its efficiency. However, all of the survey work based on the original GA did not consider obstacle avoidance in the system. Moreover, the benchmarking of the studies falls short in terms of the algorithms considered for evaluation against the proposed algorithm.

4.2.2. Enhanced GA

Three studies proposed enhancing GA to approach the multi-UAV path planning problem. In 2014, Ergezer et al. [36] introduced an enhanced GA for path planning in a multi-UAV system that visits desired regions to collect images while avoiding forbidden regions in a 3D environment. The enhanced GA defines evolutionary operators as innovative mutation operators and uses a single-objective function with a weighted sum to maximize visual information collected from the desired region, minimize the distance to the final point, minimize the dissipated energy, and minimize the collision penalty with undesired regions. The approach underwent testing using simulation and showed that it could generate feasible paths while avoiding undesired regions. Nevertheless, no assessment of the effect of changing different variable values on the system performance has been conducted.

In 2016, Cakici et al. [80] modified the approach in [36] to include a real-world platform and more realistic flying pathways. They evaluated their approach using simulation scenarios and real experiments using small UAVs. Their evaluation section showed that the proposed approach proved beneficial for multi-UAV missions to maximize the collected amount of information from the desired regions. However, both approaches have not considered benchmarking with other known path planning algorithms.

In another enhancement based on GA, Wu, and Cui [82], in 2018, introduced a planning algorithm for a fleet of heterogeneous UAVs to execute sequential operations, including classification, attack, and verification on several known targets. They modified the genes of the chromosome of the original GA [94] to adapt to the heterogeneous characteristic of UAVs. The objective function involved finding the minimum time for UAVs to accomplish the required tasks on all targets attached to the cost function and the total length of generated trajectories. They conducted real experiments and compared their proposal with a centralized GA [95] and found that the enhanced algorithm could find good feasible solutions, improve the operating rate and avoid single-point failures.

4.2.3. Hybrid GA

One of the first GA hybrids approaches for multi-UAV path planning was in 2018 when Lee et al. developed a mini-drone and proposed a genetic vector field (GVF) algorithm for multi-agent path planning [83] with collision avoidance with neighboring agents or surrounding obstacles. The GVF uses a modified GA to globally optimize target assignment and utilizes a vector field algorithm [96] to generate a collision-free path to the target. The proposed path planning algorithm was evaluated based on real experiments using four agents in an outdoor environment. The findings indicated that the GVF can generate optimal paths for each agent.

In 2021, motivated by the poor convergence speeds of many influential algorithms, Pan et al. [78] developed a multi-UAV path planning algorithm to visit several distributed sensor nodes in challenging scenarios. They proposed a deep learning algorithm (DL) trained by a GA. The DL-GA algorithm produces an optimized path based on an objective function that minimizes the total distance of all UAVs. The numerical experiments showed that DL-GA could successfully design paths for multi-UAVs at a reduced total distance, solving time, and the number of required UAVs for the mission. Table 3 summarizes existing path planning approaches for multi-UAV systems based on GA and its variants.

4.2.4. Other Evolutionary Algorithms

Evolutionary algorithms are metaheuristics that rely on natural selection and genetic variation to solve problems. This type of metaheuristic is used to solve a problem through the processes of breeding and mutation. Du et al. [93] proposed an approach to solving multi-UAV path planning for a missing tourist mission using a new hybrid evolutionary algorithm. Specifically, multiple UAVs search the target area to find missing tourists. They formulated a UAV search problem for minimizing the time required to detect missing tourists and proposed a method for estimating tourist location probabilities that changed with topographic features, weather conditions, and time. Furthermore, they extended a hybrid evolutionary algorithm to include sub-algorithms for optimizing the UAV paths in each solution. The sub-algorithm produces a search path using NEH heuristics and tabu search methods for an individual UAV.

Figure 8 shows how the main algorithm evolves the solutions using migration and mutation operators. The migration operator, inspired by the biogeography-based optimization metaheuristic, used a propagation operator similar to that of the water wave optimization metaheuristic. The authors conducted a computational complexity analysis of their algorithm. Additionally, unlike the majority of approaches in the literature, they evaluated the performance of their approach against multiple benchmarks. These benchmarks comprised greedy, a partially observable Markov decision process-based heuristic, a method based on a Gaussian mixture model and receding horizon control, ACO, PSO-GA, the artificial bee colony algorithm, a hybrid max-min ant system combined with tabu search, and a symbiotic organism search optimization algorithm. According to their findings, the expected detection times proved significantly shorter, validating the proposed search planning framework’s effectiveness and efficiency in solving the problem. Additionally, their proposed framework produced the shortest median expected detection time. Table 3 summarizes existing methods that used evolutionary algorithms and their variants to approach the multi-UAV path planning problem.

4.3. GWO and Its Variants

GWO is a swarm intelligence-based algorithm created by Mirjalili et al. [97] in 2014. The GWO algorithm took its inspiration from gray wolves, which constantly seek the most efficient technique to hunt prey. A GWO algorithm employs the same method, following a group hierarchy to organize the various functions within a wolf group. GWO classifies group members into four categories based on the wolf’s involvement in progressing the hunting process. Alpha, beta, delta, and omega comprise the four groups, with alpha constituting the best solution for hunting. The basic GWO research divides the population into four groups to reflect the natural dominance order of gray wolves. The optimal fitness solution is denoted by the symbol alpha ($\alpha$). Beta ($\beta$) is the second-best fitness solution, and delta ($\Delta$) is the third. Omega ($\omega$) is the final fitness solution. The top three fitness solutions direct all optimization processes; omega wolves seek the global optimum by sticking to these three wolves [83]. The four wolf packs and their locations are established, and the distances to the target prey are determined. Then, the three best solutions are found: alpha, beta, and delta. Moreover, each omega wolf participates in the search process by guiding the three best solutions and updating their positions. Each wolf is associated with a potential solution and receives updates throughout the search process. Additionally, GWO employs operations regulated by two parameters to sustain exploration (searching for the target) and exploitation (converging on the target) to avoid trapping in local optima [98,99].

4.3.1. Original GWO

Original GWO follows the steps of the basic GWO. In the original GWO, the basic GWO search process creates a random population of gray wolves for each UAV. At the end of iterations of the search process for each UAV, the best gray wolf agent is retrieved, representing each UAV’s optimized path. Figure 9 shows multi-UAV path planning using a GWO algorithm [85]. From the proposals of basic GWO in the multi-UAV path planning problem, two can be considered original. In 2018, Radmanesh et al. [85] applied GWO to multi-UAV path planning in a 2D world. They proposed a novel approach utilizing the formulation of dynamic Bayesian, DBVF, and GWO to solve path planning and collision avoidance problems in multi-UAV missions in the presence of fixed and moving obstacles in an uncertain environment. The UAVs sought to reach a shared goal position using the shortest and safest path obtained through GWO. The objective is to minimize the total weight of the path, which comprised a combination of the distance from the goal position and the risk of collisions with intruder aircraft. Radmanesh et al.’s work rank among the few studies in this review that considered a dynamic environment and a large number of UAVs.

In 2019, Dewangan et al. [86] applied GWO to a multi-UAV path planning problem in a 3D world. The primary purpose involved finding an optimal trajectory with minimal path length cost for each UAV while avoiding static obstacles. Intensive benchmarking was conducted to evaluate the proposed approach against Dijkstra, A*, D*, the intelligent BAT algorithm [100], Biogeography-based optimization [101], PSO, glow-worm swarm optimization [102], whale optimization algorithm [103], and the sine cosine algorithm [104]. The simulation results found that GWO converges faster than the other algorithms, especially in complex maps. It also can avoid local optima and utilizes a smaller number of parameters. Both studies, [85], evaluated the influence of different variables on the execution time or the time needed to find a solution.

4.3.2. Enhanced GWO

An enhancement to GWO was developed in 2020 by Xu et al. [87] who presented an optimized multi-UAV cooperative path planning method under a complex confrontation environment to execute a strike mission where UAVs take off from different areas to go to a mission area. The enhancement includes improving population initialization and updating the decay factor and the individual position formula. It also includes introducing a multi-constraint objective optimization model for multiple UAVs to capture the different constraints, such as space and time, threat, and fuel consumption modeling. It associated weights with radar threat cost, missile threat cost, terrain threat cost, and fuel cost. The summation of all previous factors with their weights represented the cost function the algorithm sought to minimize. When benchmarked against GA, PSO, and original GWO the simulation results demonstrated the effectiveness of the enhanced algorithm in path planning for multi-UAV missions and its speedy convergence which outpaced the benchmarks.

4.3.3. Hybrid GWO

In 2020, Yang [88] introduced a multi-population chaotic GWO (MP-CGWO) as an enhanced GWO for path planning in a multi-UAV mission that undertakes a cooperative strike on a known target. The enhancement involves modifying the original GWO initialization phase to an equal rather than random division of coordinates and adding a chaotic local search to prevent local optima. The multi-objective cost function includes fuel consumption, maximum climb/slide angle, peak threat, flying altitude, and multi-UAV cooperation time. A 3D digital elevation model was used to represent the world and conduct simulation experiments to evaluate the approach against differential evolution (DE) [105], PSO, and GWO algorithms. The results verified the effectiveness of MP-CGWO in realizing multi-UAV cooperative path planning with better stability and search accuracy. Table 3 summarizes existing path planning approaches for multi-UAV systems based on the GWO algorithm and its variants.

4.4. ACO and Its Variants

The ACO algorithm is an intelligent population-based algorithm developed in 1992 by Dorigo [9,106] to approach combinatorial optimization problems. The basic ACO algorithm took its inspiration from the ability of ants to find the shortest path between food sources and their nest. Each ant leaves a trail of pheromones on the path to a food source, and later, other ants follow this trail to maximize their chance of finding food. The intensity of a deposited pheromone is inversely proportional to the path length, meaning that the ant with the shortest path will leave a high concentration of pheromone, leading other ants to follow it. In the ACO algorithm, the first step involves setting the main parameters, and the initial pheromone value is set. Next, the algorithm iterates until the termination condition is reached. During each iteration, ants search for a solution, and the pheromone concentration updates at the end of the loop. The updating process will involve increasing or decreasing the amount of pheromone. The latter reportedly reflects the evaporation of the pheromone, and it is applied to paths not taken by any ant during the iteration. In each step of the search, each ant has a transition probability that balances exploration (ignoring a path’s pheromone and following a greedy mechanism) and exploitation (following paths with high pheromone concentration). Since its introduction, the ACO algorithm has been applied in various fields of science and engineering, including job-shop scheduling, vehicle routing, quadratic assignment problems, and graph coloring [9]. Despite the known advantages of ACO, such as parallelism and rapid feedback [107], it suffers from slow convergence speed, which wastes time and makes it unsuitable for optimizing multi-UAV path planning applications [108].

4.4.1. Original ACO

The multi-UAV path planning ACO algorithm [9,108], presented in Figure 10, follows a similar approach to basic ACO to generate the best-found trajectory for all UAVs. The main difference is that each ant will construct a solution considering one UAV. Each ant has its trajectory, and all possible UAV trajectories form the ant population. Each population of ants has the same position, navigation, vision, communication, and interaction capabilities as the UAV platform [108]. Initially, each ant will begin from the UAV start locations. During the solution construction phase for a specific UAV, each ant will simulate the movement of the UAV and move according to a transition rule. After iterating through the UAVs, each ant will construct a solution. Once the entire population of ants has completed this process, the best solutions obtained within the present population are identified and preserved. Following this, the pheromone updating process occurs. Finally, the ACO algorithm returns the best global solution if the main loop reaches an end condition. However, we could not locate a study that applied the original multi-UAV path planning ACO.

4.4.2. Enhanced ACO

Several papers enhanced ACO for the multi-UAV path planning problem. In 2018, Perez-Carabaza et al. [89] enhanced ACO to address the path planning problem of multi-UAV with moving targets and straight-segment trajectories. The enhancement included a new heuristic function specifically designed for minimum time search (MTS) problems. The approach did not consider obstacles or UAV collision avoidance. However, it considered both dynamic and static goals assuming that the probability distribution function models the available target location information before the search begins. The objective function involved minimizing each trajectory’s expected target (ET) detection time. For the evaluation, several scenarios ranging from static to complex dynamic were implemented. Additionally, statistical comparisons with other techniques for MTS (ad hoc heuristics, cross-entropy optimization, a Bayesian optimization algorithm, and a GA) were conducted. The comparisons show that the proposed approach outperformed the other approaches.

In 2018, Ziyang et al. used an enhanced online ACO, to implement a multi-UAV cooperative search-attack mission [90]. The UAVs executing the algorithm were heterogeneous, and some UAVs executed search missions while others executed attack missions. When executing a search mission, each UAV aimed to find more targets and search more grids. When executing an attack mission, each UAV preferred to attack targets with higher values. The paper divided the global optimization problem into local optimization problems. The planning process comprises two phases: waypoint generation and path generation. In the first phase, an improved distributed ACO algorithm generates waypoints. The connected waypoints generate a flyable path in the second phase. However, if a threat is discovered during flight, the algorithm replans the path to avoid the threat. The authors analyzed the convergence performance of their algorithm against a distributed search-attack mission self-organization algorithm, basic intelligent self-organized algorithm, and intelligent self-organized algorithm. Additionally, they analyzed the external responsiveness and internal scalability of their algorithm and found that the convergence rate was higher or similar to the benchmarks and had suitable internal scalability and external responsiveness.

4.4.3. Hybrid ACO

In 2020, Zhang et al. [24] addressed the issue of cooperative mission planning for several UAVs on a battlefield by implementing a three stages approach that generates complete paths for multiple UAVs. First, targets are clustered into subgroups. Then, a fuzzy ACO algorithm calculates the global path between the target subgroups. Last, the fuzzy ACO generates the local paths for a single-target subgroup. A cooperative communication method was used to reduce the number of UAVs performing a task. The objective function minimizes the total distances traveled by the UAVs and the detention time for all UAVs. The evaluation section indicated the effectiveness of the proposed fuzzy ACO when simulated based on two UAVs considering different numbers of ants, targets, and iterations. Table 3 summarizes existing path planning approaches for multi-UAV systems based on ACO and variants.

4.5. PIO and Its Variants

PIO is a relatively new algorithm proposed in 2014 by H. Duan and P. Qiao [109]. The basic PIO algorithm was initially proposed to solve the path planning problem of a single air robot. The homing behavior of pigeons, including their perception of the Earth’s magnetic field by altering the map in their brains through magnetoreception, inspired the algorithm. Pigeons use the altitude of the sun as a compass to modify their direction. When pigeons fly close to their target, they rely on nearby landmarks: they will fly directly to their destination if they recognize the landmarks. Pigeons far from their destination will follow other pigeons familiar with the current location. Specifically, they utilize a map and compass operator model based on the magnetic field and the sun. PIO implements virtual pigeons that adjust their velocity and position vectors in each iteration. The algorithm utilizes randomness and the current global position to update its information [6]. The PIO is known for its superiority in task assignment and path planning over other swarm intelligence optimization methods. However, it suffers from a short population search span and fast prematurity [47].

4.5.1. Original PIO

Figure 11 shows the original PIO algorithm for the multi-UAV path planning problem. However, our review revealed that no previous work has applied the original PIO to approach the multi-UAV path planning problem.

4.5.2. Enhanced PIO

For enhancing PIO, in 2018, Zhang and Duan [6] introduced the social-class pigeon-inspired optimization (SCPIO) as an enhancement to address some of the basic PIO shortcomings, such as a lack of diversity and prematurity. SCPIO was developed to address the multi-UAV path planning problem in an assault mission where UAVs take off from a base and arrive at a designated location simultaneously to collaboratively execute an attack task against a specific target. The objective is to minimize the overall cost which includes the total threats and coordination cost. For evaluation, a time stamp segmentation (TSS) technique was developed to provide references for multi-UAV coordination such as the desired velocity and motion time. The evaluation results against the original PIO and PSO algorithms show the reliability and efficiency of the proposed system when simulated with four UAVs in a 3D complex environment. The results also demonstrated its enhanced convergence capabilities.

In a recent enhancement of PIO, Duan et al. [47], in 2021, proposed a dynamic discrete PIO algorithm (D2PIO) to solve the cooperative path planning problem in a multi-UAV search-attack mission that aimed to find and destroy as many targets as possible with various constraints. The original PIO was improved by adding a response threshold sigmoid model and an information fusion method to construct a probability map to guide UAV movements. The above improvements were combined with an integrated centralized task assignment and a distributed path creation phase which allowed the algorithm to respond to dynamic changes. The extensive evaluation framework of the proposed algorithm experimented through numerical and visual simulations considered various numbers of UAVs, up to fifteen, and four benchmarks, which include basic PSO (BPSO) [58,59], basic PIO (BPIO) [109], dynamic PSO (DPSO) [110], and modified particle swarm optimization (MPSO) [111]. The results proved the improved optimization capability of D2PIO where it showed less time consumption for search-attack mission planning. Both of the above studies on enhanced PIO, [6,47], presented computational complexity analysis of their proposed methods. Table 3 summarizes existing path planning methods using the PIO algorithm and variants.

4.6. FOA and Its Variants

The FOA is a simple global optimization method [112] introduced in 2012 by Wen-Tsao based on the fruit fly’s foraging behavior [59,112]. Among all species, the fruit fly is distinguished by its sensing and perception, especially in apheresis and vision. A fruit fly can easily locate a food source by distinguishing food scents, exploiting its excellent vision, and targeting the flocking location of other fruit flies [113]. Among the main advantages of FOA are the clear principles and simple operation. However, FOA does not work well in high-dimensional nonlinear optimization problems and it can easily relapse into local optima [114]. Additionally, despite its few parameters, these parameters need to be manually set [113].

4.6.1. Original FOA

According to the simple idea presented in the previous section, the original FOA, shown in Figure 12, repeatedly searches for the optima, which represents a food source [91]. The algorithm iterates as long as a new path has a superior fitness value. In the context of multi-UAV path planning, each UAV will have a swarm of fruit flies representing a candidate path. Each algorithm iteration searches for an optimal flight path for the UAVs. The algorithm terminates whenf the results remain mostly unchanged and ultimately, the optimal flight path for each UAV is returned. However, none of the previous work has considered applying the original FOA. Instead, several enhanced versions were proposed as presented in Section 4.6.2.

4.6.2. Enhanced FOA

In 2020, Kun et al. approached the multi-UAV path planning problem with an improved FOA algorithm based on the optimal reference point (ORPFOA) [91]. They considered an oilfield inspection mission with online changing tasks in a 3D environment. The algorithm generates an optimal initial path for each UAV to traverse task points, then reoptimizes this initial path to consider the changing task problem. The cost function comprises the weighted sum of the average height of the UAVs, time consumption, and total power consumption. A convergence analysis was conducted which proved that the algorithm converges to the optimal global solution. To highlight the algorithm’s effectiveness, it was compared with six other swarm intelligence optimization algorithms: FOA, predator–prey PIO [115], PIO, PSO gravitational search algorithm (PSOGSA) [60], PSO, and GWO. The study of the cost function value and running time showed that the proposed algorithm had the best convergence and optimization performance (both the smallest cost function value and shortest running time). Table 3 summarizes existing methods using FOA and variants to approach the multi-UAV path planning problem.

4.7. LSO and Its Variants

The LSO was introduced by Krink and Lovbjerg [116] in 2002 as a novel adaptive search heuristic inspired by the biological lifecycle. In biology, individuals pass through four stages: birth, growth, reproduction, and death. The transition from one stage to the next is often triggered by environmental factors and leads to drastic transformations of the species to give them a stronger ability to adapt to a particular environment, interestingly, the genome remains unchanged within each cell [117]. In a similar approach, individuals (candidate solutions and their fitness) in the LSO begin as PSO particles and evolve into GA individuals, solitary stochastic hill climbers (HC), and eventually back to particles, as shown in Figure 13. The motivation behind the proposal of LSO was that each search approach (GA, PSO, and hill-climbers) has distinct benefits and disadvantages. However, the evaluation studies of LSO show its fast convergence speed although it is a bit slower than the basic PSO and its solution does not match the quality of the original GA [116].

In 2020, Liu et al. [92] proposed an enhanced hybrid LSO to address the problem of task allocation and trajectory planning with obstacle avoidance for a team of heterogeneous UAVs. The algorithm considered a multi-target, multi-base, collaborative combat mission in a complex 3D mountain environment. The algorithm varies the number of individuals in the population to improve the basic LSO, then it combines the basic LSO with the Rapidly exploring random tree algorithm (RRT) to generate an optimized path. The main objective is to find the shortest trajectory and the minimum threat cost which can be achieved by the weighted sum of the UAV track length and the cost of the track threatened by radar. The simulation results of 21 UAVs and two benchmark algorithms, the original PSO and the whale optimization algorithm (WOA) showed that ILSO had a faster convergence speed and better convergence accuracy than the benchmarks. Table 3 summarizes existing methods using the LSO algorithm and variants to approach the multi-UAV path planning problem.

5. Discussion

Our search queries in this literature review retrieved studies, published between 2013 and 2021, related to multi-UAV path planning based on biological inspirations. Figure 14 displays the number of applications of each reviewed algorithm from 2013 to 2021 where GA applications were the earliest but stayed stable over the period while interests in applying algorithms, such as LSO and FAO have just started recently, during 2020. The chart shows that PSO is the most used heuristic for multi-UAV route planning and its applications have risen in recent years which highlights its superior advantages and efficiency over the other bio-inspired methods. This conforms to the findings in [87,118,119] where PSO was identified as the most influential reference algorithm among bio-inspired algorithms followed by GA.

We observed that most of the studies fall within the category of enhanced algorithms, as shown in Figure 15 which suggests that original bio-inspired algorithms require enhancement to tackle the specific challenges associated with the multi-UAV path planning problem, such as collision avoidance and high dynamicity of the environment.

When analyzing the considered environment in previous studies by comparing studies that regarded dynamic environments versus those that regarded static environments, we noticed that the majority of studies worked with a static environment. Specifically, 77% of the environments were static, while only 23% were dynamic, as depicted in Figure 16. This finding is justified by the level of complexity in a dynamic setting, especially with multiple UAVs [59]. Another key factor that we have analyzed concerning the environment is whether it is a 2D or 3D environment. Figure 16 shows that most studies focus on 3D environments, which is predictable as, normally, a UAV navigates through a 3D environment. We have also investigated the correlation between the environment representation and its evolution in Figure 16 which indicates that 3D applications concentrate on static environments. This observation can be attributed to the need to manage the level of complexity in 3D environments, in contrast to the 2D studies which face fewer challenges, and thus equally explored static and dynamic environments.

As CA is a crucial issue that multi-UAV missions should deal with, we have examined how it is affected by the environment model, whether 2D or 3D. We could not find any significant trends when 2D environments are considered. For instance, the number of 2D studies with and without CA is comparable. In contrast, in 3D environments, CA is usually explicitly handled, as Figure 17 indicates that 80% of the studies managed collision avoidance between UAVs. Among these studies, 48% implemented an altitude layering approach, while 41% followed the safe distance method. The remaining 11% of studies applied other approaches to handle CA within the objective function or as a constraint.

Additionally, we have analyzed the CA feature with obstacles, as well as other UAVs. Figure 18 shows that most 3D proposals with CA worked on collisions with both UAVs and obstacles. Therefore, in Figure 19, we examined further how this choice affected the path planning scope, where we found that global path planning is more common than local planning due to the challenges of managing collisions without global knowledge about the environment.

Similarly, we analyzed studies of a dynamic environment to determine the focus on the goal or obstacle dynamicity. Figure 20 shows that most studies on dynamic environments assume dynamic obstacles with static goals. Along with the earlier statement about the challenges in the dynamic environment, only one study assumed dynamic goals and obstacles together [75]. Due to the complexity that comes with uncertainty in the environment, the situation of having unknown goals and obstacles was rare. Only one study worked with unknown goals and obstacles [90]; all other studies assumed either goals or obstacles were unknown, not both.

We were interested in determining how the planning mode is affected by the amount of uncertainty in the world. Figure 21 shows the number of studies using known obstacles/goals versus unknown obstacles/goals in each path planning mode. The figure suggests that most research studying partially known environments used either online or hybrid path planning, as handling unknown aspects of the environment “on the fly” is more efficient than regenerating a path each time new data arrives.

To analyze the specific application where the proposed path planning method was applied, we grouped the literature, as shown in

Table 4. A summary of application areas considered by the reviewed papers.

Mission	Studies
General path planning	[36,65,66,70,78,80,83,85,86,88,91,108]
Search mission	[24,37,46,64,73,75,81,89]
Search and attack mission	[6,47,69,82,87,90,92]
Search and rescue mission	[93]

, into four classes: First, general path planning where the work introduced a path planning approach without considering the context of a specific mission, most of the reviewed work fall into this category. Second, in searching missions, such as surveillance missions, remote sensing, and finding targets within points of interest, fewer approaches come under this group. The third and fourth categories include search and rescue and search and attack missions respectively, with the latter receiving the least attention which suggests that military applications might not always be the main driver for advances in UAV technologies. Additionally, our review found that the above categories show no major differences in the path planning tactics except for certain constraints, such as including radar range as a threat in search and attack missions or a survivor critical lifetime window for search and rescue missions.

Another significant aspect of multi-UAV applications is the number of UAVs; thus, we examined the maximum number of UAVs used to assess each approach. In general, most studies tested their approach with fewer than eight UAVs, and only three approaches considered ten or more UAVs. The Maximum number of UAVs used for evaluation in each approach is shown in

Table 5. Maximum number of UAVs used for evaluation in each approach.

Number of UAVs (Up to)	Studies
2	[64,80,90]
3	[24,46,65,81,89,91]
4	[6,36,66,73,83,87]
5	[78,86]
6	[37,69,88]
8	[82,84,93]
10	[47]
24	[92]
200	[85]

.

When characterizing the studies that handled the communications between UAVs, we found that only a few surveillance applications and search and attack missions, such as [46,64] have considered this aspect which suggests that non-military applications are less concerned about the communication side although it has a massive impact on the mission’s success [120].

Examining the evaluation methodologies used in the reviewed literature reveals several key findings. Firstly, most approaches were evaluated using simulation experiments, with only a few studies (such as [82,83]) involving real experiments. However, this limited the level of complexity that could be considered, as these studies were conducted in known, static environments based on an offline planning mode. Secondly, there is a lack of reference implementations of bio-inspired algorithms, which is consistent with previous related reviews (such as [59]). Furthermore, there are considerable limitations in environmental and mission models, such as the availability of reference maps and mission settings at different levels of complexity that can be used to benchmark new proposals. It is important to note that benchmark maps typically used with mobile robots are insufficient, as UAVs usually operate in 3D environments. Thirdly, while reducing running time is one of the main goals of path planning [7] (particularly in multi-UAV problems [121]), most evaluation frameworks overlook the running time of proposed approaches or merely benchmark them against brute force approaches (such as [78,83]). Only a few applications considered benchmarking against previous proposals (such as [86]).

6. Conclusions

This review examined the literature studies on the multi-UAV path planning problems and focused on bio-inspired algorithms. These algorithms can address challenges such as collision avoidance and high environmental dynamicity. According to the review, PSO is the most popular heuristic for multi-UAV route planning and its applications have grown in recent years, demonstrating its superior advantages and efficiency over other bio-inspired methods. The majority of studies belong to the enhanced algorithm category, which suggests that original bio-inspired algorithms need to be enhanced in order to deal with the specific challenges associated with multi-UAV path planning, including collision avoidance and high environmental dynamicity. There is a greater tendency for global path planning than local planning since it is more difficult to manage collisions without knowledge of the environment at a global level. Similarly, most studies considered dynamic environments with dynamic obstacles and static goals. To handle the challenges of partially known environments researchers apply either online or hybrid path planning, as handling unknown aspects of the environment “on the fly” is more efficient than regenerating a path each time new data arrives.

Among the important findings of this review is that a significant lack of reference implementations of bio-inspired algorithms is alarming, which is consistent with previous reviews, e.g., [59] and considerable limitations exist in environmental and mission models, for example, reference maps and mission settings at various complexity levels are not available for benchmarking new proposals. In view of the fact that UAVs primarily operate in 3D environments, benchmark maps used for mobile robots are insufficient.

Some possible future research directions that are suggested based on this study include:

• Developing new bio-inspired algorithms that can tackle the specific challenges associated with the multi-UAV path planning problem, such as collision avoidance and high dynamicity of the environment.
• Investigating the use of local path planning to manage collisions without global knowledge about the environment.
• Investigating the use of hybrid path planning to handle partially known environments more efficiently.
• Developing reference maps and mission settings at different complexities that can be used to benchmark new proposals.
• Developing benchmark maps that are specifically designed for UAVs operating in 3D environments.