Research on Unmanned Aerial Vehicle Path Planning

Abstract

As the technology of unmanned aerial vehicles (UAVs) advances, these vehicles are increasingly being used in various industries. However, the navigation of UAVs often faces restrictions and obstacles, necessitating the implementation of path-planning algorithms to ensure safe and efficient flight. This paper presents innovative path-planning algorithms designed explicitly for UAVs and categorizes them based on algorithmic and functional levels. Moreover, it comprehensively discusses the advantages, disadvantages, application challenges, and notable outcomes of each path-planning algorithm, aiming to examine their performance thoroughly. Additionally, this paper provides insights into future research directions for UAVs, intending to assist researchers in future explorations.

1. Introduction

An unmanned aerial vehicle (UAV) is a pilotless aircraft that combines program operating devices with radio remote control apparatus. UAVs can be divided into fixed-wing UAVs, rotary-wing UAVs, and fixed/rotary-wing hybrid UAVs according to different flight mechanisms. These aerial platforms are amenable to remote control by human operators or can be pre-programmed to execute predetermined flight plans autonomously. The spectrum of UAVs is marked by substantial diversity concerning size, configuration, and functional capabilities, representing various applications across various domains. This aircraft category encompasses fixed-wing, rotary-wing, and hybrid UAVs, each characterized by specific flight mechanisms. The proliferation of UAVs can be ascribed to advancements in Internet and UAV-related technologies, rendering them indispensable in contemporary society due to their flexibility, high mobility, simplicity, concealment, cost-effectiveness, and security attributes. Projections indicate a noteworthy expansion in the UAV market, with an estimated value reaching USD 38.3 billion by 2027 [1]. UAVs play pivotal roles across diverse civil applications, encompassing express transportation [2], traffic control [3], data acquisition [4], disaster rescue [5], and intelligent agriculture generation [6,7].

Additionally, their deployment in the military domain for surveillance, reconnaissance, and tracking tasks highlights their versatility [8,9]. Some applications, such as rescue operations, disaster management, and data acquisition, rely heavily on UAV communication networks (UAVCNs) [10]. The dynamic nature of UAVs, enabled by their high mobility, allows for the real-time adjustment of trajectories to adapt to different environmental conditions. Consequently, a systematic classification and summarization of UAV path-planning algorithms become necessary. Path planning is critical to UAV operations as it considers physical flight capabilities, path security, tactical feasibility, real-time planning, and mission reliability. It involves determining a feasible flight path from the origin to the destination tailored to the specific mission. A review of relevant scholarly articles highlights the significance of UAV path planning, acknowledging the inherent challenges of determining a continuous trajectory involving multiple variables.

The complexity of path planning is further compounded by real-world constraints such as connectivity, fuel limitations, and collisions, which are time-varying and difficult to model accurately. These challenges span various disciplines, including artificial intelligence (AI) optimization, flight mechanics, automatic control, operations research, and combat effectiveness evaluation. Despite advancements in AI, cloud computing, and big data technologies, UAV path planning remains a formidable cross-disciplinary challenge [11]. Note the accurate descriptions for trajectory accuracy, path-planning accuracy, flight step size in the meter unit, and computational effort in the second unit of this paper.

Existing research efforts have aimed to categorize UAV path-planning techniques into representative, collaborative, and non-collaborative approaches [12,13,14,15,16]. Discussions revolve around coverage and connectivity issues in UAV network communication; the classification of path-planning algorithms based on models, conventions, learning, and units; and the exploration of UAVCN applications and challenges in disaster management. Specific studies delved into three-dimensional (3D) path planning, spatial modeling problems, and performance standards. Additionally, the literature has explored energy-saving-based path-planning algorithms for UAVs.

Table 1. Comparison of Path-Planning Survey Papers.

Reference	Year	Main Features	Traditional Algorithms	Intelligent Algorithms	Hybrid Algorithms	Multi-UAV Path Planning	Regional Coverage
[12]	2019	Comprehensive algorithms Performance comparison	√	√			√
[13]	2021	Disaster Management Algorithm Statistics 5G communication	√	√
[14]	2019	Workspace modeling Path smoothing 3D UAV path planning	√	√
[15]	2018	Detailed analysis		√
[16]	2019	Energy efficient	√	√
Ours/This proposed paper	2023	3D UAV path planning Coverage Novelty classification Detailed summary	√	√	√	√	√

concisely compares survey papers on path planning, highlighting key features and content.

This paper’s main contributions are as follows:

• UAV path-planning algorithms are analyzed in detail. We innovatively study the generic path-planning algorithm at the algorithmic and functional levels. Path-planning algorithms are classified into three categories at the algorithmic level: traditional, intelligent, and hybrid. Path-planning algorithms are classified at the functional level into space-based, time-based, and task-based planning. The shortest path problem, traveling salesman problem (TSP), and area coverage problem are introduced. The specific classification is shown in Figure 1.
• Performance metrics, advantages, disadvantages, and challenges in applying path-planning algorithms are systematically tabulated, thereby serving as a comprehensive reference for researchers. Additionally, algorithm selection recommendations are proffered at each respective subsection’s conclusion. This structured presentation facilitates a nuanced understanding of the algorithmic landscape and offers valuable insights for researchers in navigating the complexities associated with choosing and implementing path planning.
• By meticulously examining historical evolution and current paradigms in UAV path-planning methodologies, algorithms, and applications, this study aims to discern prevailing trends, identify research gaps, address challenges, and delineate prospective opportunities. The envisaged outcome is the provision of strategic insights conducive to formulating well-grounded and forward-looking research directions in the specialized domain of UAV path planning.

The rest of this paper is organized as follows. Section 2 introduces the execution process and path-planning model. The algorithm-level UAV path panning classification is given in Section 3. Section 4 classifies and analyses path planning at the functional level. The challenges and solutions of multi-UAV path planning are proposed in Section 5. Next, future research trends and directions related to path planning are given in Section 5. Finally, Section 6 concludes the whole article.

2. Fundamental Knowledge

2.1. Path-Planning Objectives

The investigation into UAV path planning represents a dynamic and highly scrutinized research area within the academic realm. Exploiting UAV mobility offers dynamic state optimization opportunities, aligning with the communication environment through strategic trajectory planning. The imperative of ensuring feasibility, safety, and optimality underscores the necessity for thoroughly integrating environmental information. Concurrently, attention to constraints such as navigation accuracy, fuel power platform maneuverability, and arrival time becomes pivotal, mitigating potential threats and obstacles.

Within the UAV path-planning research context, the central focus is on constructing mathematical models that effectively articulate specific tasks, outline pertinent constraints, and prescribe optimization methodologies. This procedural approach entails the comprehensive definition of the planning space, incorporating considerations such as the starting point, environmental terrain conditions, mission area, and potential airborne threats. The formulation of constraint conditions and the corresponding mathematical path-planning model are intricately aligned with task specifications and performance constraints. Sequential stages involve the judicious selection or development of an appropriate search algorithm to systematically identify the optimal feasible path within the planning space, ensuring compliance with all prescribed conditions. Then, the identified path undergoes a rigorous process of refinement and assessment, culminating in a definitive output.

2.2. Path-Planning Model

The primary objective is the swift identification of the optimal trajectory within the designated planning space, which consists of multiple line segments or path points. The representation of the path is delineated through two distinct modalities: one involving a time series featuring speed and course parameters (dynamics-based) and the other characterized by a time series embodying spatial position coordinates (geometry-based). The subsequent elucidation systematically details the three foundational components comprising the UAV path-planning model—specifically, space model planning algorithms, optimization objective functions, and constraints.

2.2.1. Space Model Planning Method

The initial step in path planning involves modeling the environment, which entails constructing the planning space, also called the search space. The planning space serves as an abstraction of the physical environment. Ideally, if circumstances allow, the information about the physical space should be meticulously and accurately mapped into the planning space. In practical applications, the planning space is typically 3D [17,18]. Of course, to simplify the problem, some studies also simplify the space into two dimensions (2D) [19,20,21]. The commonly used expression algorithms of planning space include cell, landmark, and potential field.

• Cell method

The cell method, encompassing the grid and cell tree methods, divides space into independent cells with corresponding generation values. The grid method uses uniform-sized grids in two or three dimensions, where black geometry denotes obstacles. In contrast, the cell tree method exhibits greater environmental adaptability by employing varying space lattice sizes. References [22,23] applied the grid method in 3D space, while [24] proposed a technique reducing height and size, achieving 3D to 2D conversion. The grid method is simpler but yields a larger search space, posing challenges in cell size selection.

2.

Roadmap method

The roadmap method, exemplified by techniques such as rapidly exploring random trees (RRT) [25], the Voronoi diagram [26], visibility graphs [27,28], and probabilistic roadmaps, represents space as a network diagram following specific rules. The Voronoi diagram divides the planning space into areas along obstacle edges, efficiently reducing the search space and enabling swift pathfinding. However, it may not yield the shortest path. The visibility graph method requires unobstructed lines between points and obstacle vertices, reducing search space but compromising accuracy. Yet, updating the model in response to environmental changes proves challenging. Roadmap methods offer diverse approaches, each with unique advantages and limitations regarding efficiency and adaptability.

3.

Potential field method

The potential field method is a space-planning method independent of graphic representation. It regards the endpoint as the source of attraction to generate attraction. It regards obstacle threats, etc., as the source of repulsion to generate repulsion force and then integrates the force direction of the UAV to obtain the relevant path. The path planning based on the potential field method is easy to solve and can be applied to 2D and 3D spaces. Nonetheless, there is a problem in that the path cannot be found [13,15,29].

The above three space-modeling algorithms are summarized in

Table 2. Comparison of Space-Modeling Algorithms.

Space Modeling Algorithms	Typical Algorithms	Advantages	Disadvantages	Reference
Cell method (discrete)	Cell method Cell tree method	Simple and intuitive Easy to model	Difficulty in the set of low granularity efficiency The conflict between space–time cost and accuracy	[22,23,24]
Roadmap method (discrete)	RRT Voronoi diagram Visibility graph probabilistic roadmaps method	High safety coefficient	Difficulty in update Difficulty in roadmap set Low accuracy	[25,26,27,28]
Potential field method (continuous)	Navigation function method Deep first potential field method Wave propagation method	Easy to solve	Difficulty in finding the path	[13,15,29]

.

The traditional cell and potential field algorithms need to model space obstacles accurately. When the obstacles in the environment are complex and irregular, it significantly increases the difficulty of space planning. The roadmap method reduces the space planning work and is often used in the path planning problem to maximize the safety index. Nonetheless, the accuracy of path planning is worse than the traditional cell and potential field algorithms. In UAV path planning, because obstacle threat avoidance does not limit the cell method and has high precision, this method is usually used to divide the space. A path is represented by coordinate points containing starting and ending points.

2.2.2. Optimization Objective Function

The path planning of UAVs usually needs to build corresponding objective functions according to different task requirements or decision-maker preferences. Generally, flight time, flight distance, and threat cost are used as objective functions. The planning model can be a single target or multiple targets. References [23,24] used the minimum path length satisfying the reconnaissance coverage as the optimization objective function. A two-objective optimization model was constructed based on the maximum number of reconnaissance targets and the minimum sum of all UAV flight distances [25]. Reference [26] took the shortest residence time exposed to enemy radar monitoring range as the objective optimization function. The authors used minimizing path length and threat cost as objective optimization functions [29].

The specific optimization objective function can be expressed as follows:

$$min F={\sum }_i {\omega }_i{J}_i,$$

(1)

where $F$ is the optimization objective function; $J_i$ is the ith cost; and ${\omega }_i$ is the according weight, $\sum _i {\omega }_i=1$. When every cost is constructed into the individual target and not weighted, the problem can be converted into a multi-target optimization problem.

By considering the path length cost, threat cost, and height cost, the total cost function can be expressed as follows:

$$J={\omega }_{1}L+{\omega }_{2}T+{\omega }_{3}H,{ \omega }_1+{\omega }_2+{\omega }_3=1$$

(2)

where J is the total cost; L is the distance cost, which is also called the fuel cost in the literature [30]; T is the threat cost; H is the height cost; ω_1, ω_2, and ω_3 are the weights corresponding to different objective functions. Of course, other cost functions can also be introduced as needed. For example, the literature [31] also presents the yaw angle in the cost function. It takes the comprehensive weighting of the yaw angle, path length, and threat cost as the objective function.

3. Algorithm-Level UAV Path-Planning Classification

In our investigation, we systematically classify and synthesize contemporary UAV path-planning algorithms, specifically at the algorithmic level. This rigorous categorization process comprehensively examines the algorithms’ inherent properties, mathematical formulations, and conceptual designs, identifying three distinct classes: traditional/classical, hybrid, and intelligent algorithms. The designation “traditional/classical” is reserved for approaches firmly grounded in well-established methodologies that consistently demonstrate efficacy across diverse domains. In contrast, hybrid algorithms amalgamate two or more algorithmic types, strategically leveraging the strengths inherent in each. Lastly, the classification of intelligent algorithms encompasses methodologies employing digitized 3D pivot point measurements, simulating natural processes, or drawing inspiration from observed principles in the natural world.

Considering the vast array of UAV path-planning algorithms and space limitations, a strategic decision has been made to identify relevant references selectively. The goal is to provide a concise overview encompassing the fundamental features, advantages, and disadvantages of widely adopted path-planning algorithms, avoiding an exhaustive examination of every algorithmic detail. In-depth discussions are reserved for works considered unique, popular, and distinguished within the literature. Concurrently, a presentation of typical path-planning algorithms across diverse categories is envisioned. This approach aims to enable a more reasonable and clear understanding for readers, with the specific classification outlined in Figure 2.

3.1. Traditional Algorithm

The conventional algorithm relies on environmental information within the mathematical model of the workspace. Considering the design and intrinsic properties governing path-planning algorithms, traditional algorithms are further delineated into four classifications: cell-based, mathematical model-based, node-based, and sampling-based.

3.1.1. Cell-Based Path Planning

A cell-based algorithm is characterized by its self-contained nature, employing a synthesis of graphical and mathematical methodologies for path planning. Noteworthy examples of such algorithms include A-stars (A*) and their improved or extended variants. In a pertinent study documented by the authors in reference [25], the integration of UAV attitude-angle information, predictive control, and real-time heuristic learning is realized within the A* algorithm. The enhanced A* algorithm achieves real-time path planning for stealth UAVs navigating 3D complex dynamic environments [32]. Addressing the inherent inefficiency in node scaling associated with the A* algorithm, the work presented in reference [33] introduces a novel orientation search strategy founded on attitude angle, direction search strategy, adaptive step size strategy, adaptive weight strategy, bidirectional search strategy, and a rewiring process within the A* framework.

3.1.2. Model-Based Path Planning

Path planning for UAVs inherently presents a complex and constrained optimization challenge. This intricate process relies upon a diverse set of mathematical models, spanning planning and probabilistic models, as well as mathematical equations and functions, such as Lyapunov functions, Bessel curves, and Durbin’s algorithm. Collectively, these components contribute to a comprehensive path analysis. The algorithms within this domain can be systematically categorized based on the underlying mathematical models into programming, control theory, and multi-objective optimization. Each classification specifically addresses unique mathematical models and functions, effectively managing the intricate optimization challenges inherent in UAV path planning.

The mathematical planning methodology starts by considering UAV-specific dynamic constraints. Subsequently, indicators such as flight time, path length, energy consumption, threat level, etc., are formulated as objective functions. The final step involves determining optimal values through optimization calculations. Noteworthy mathematical programming algorithms include dynamic programming (DP) [34], nonlinear programming (NP) [35], mixed-integer programming (MIP) [36] and the Markov decision process [37]. Dynamic programming, in particular, demonstrates superior performance compared with genetic algorithms (GAs) in specific scenarios. For example, a study used DP to derive the shortest collision-free path [38], resulting in an 11.6% reduction in path travel time compared with GAs and a 50% reduction in calculation time. Mixed-integer linear programming addresses multi-task and multi-constraint problems, with numerous studies representing path planning as a MIP model [38,39]. A specific paper [40] formulated a MIP model to maximize coverage and monitor time. The conflict objective function ensured UAVs could continuously monitor at any given time. These approaches underscore the adaptability of mathematical models and optimization algorithms in effectively tackling the intricacies of UAV path planning [41].

Control theory, a pivotal aspect of UAV path planning, incorporates algorithms such as optimal control, model predictive control (MPC) [42], and Lyapunov function [43]. While optimal control reduces problem complexity, it necessitates an initial solution and lacks optimization capabilities [41], often prompting a combination with other algorithms [44]. MPC, governing UAV path planning under constraints, was employed to develop a 3D model [45] using adaptive differential evolution for real-time planning. Lyapunov function ensures UAV stability in dynamic environments, analyzing algorithmic stability and reaching specified target trajectories [46,47]. In one instance, authors employed Lyapunov functions and time target points to calculate short-sighted distance trajectories based on the robot’s current state [48].

3.1.3. Graph-Based Path Planning

A graph search control strategy is implemented for pathfinding, classifying into deterministic and stochastic searches within graph-based path-planning algorithms. Deterministic search algorithms, such as depth-first search [49], breadth-first search [50], and Dijkstra’s algorithm [51], are pivotal in the realm of path planning. An enhancement to Dijkstra’s algorithm was proposed to incorporate diagonal and linear searches at any angle for more effective 3D path planning [52]. A performance study comparing Dijkstra’s algorithm, Floyd’s algorithm, the A* algorithm, and ant colony optimization (ACO) underscored the superiority of Dijkstra’s algorithm in terms of running time, complexity, and path length [53]. On the other hand, stochastic search widens the array of feasible paths through random sampling in the state space. Representative algorithms encompass rapidly exploring random trees (RRT) and probabilistic roadmap methods [54]. Various improvements and extensions to RRT, such as RRT-Connect [55], RRT* [56], and Hybrid RRT [57], contribute to this domain. A two-stage path-planning method based on RRT was developed for solar UAVs aiming to evade collisions, maximize solar energy absorption, and minimize energy consumption [58]. The progressive near-optimal lower bound tree RRT (LBT-RRT) algorithm was proposed using single-query sampling [59].

Deterministic algorithms ensure optimality in small-scale path planning yet struggle with complex objectives and constraints. Stochastic search algorithms, such as RRT, adeptly handle UAV dynamics and kinematic constraints. However, their random sampling poses challenges for guaranteeing route optimality, limiting their applicability to complex terrains and dynamic environments due to uncertainties in determining node belonging during sampling.

3.1.4. Potential Field Path Planning

The artificial potential field (APF) method is a representative approach within the possible field method [60]. Initially developed for robot path planning in obstacle avoidance, APF gained popularity due to its straightforward principles. Although the flight paths generated by APF may not always be the shortest, they are often considered the smoothest and safest. However, inherent shortcomings persist, such as high computational complexity and susceptibility to local minimums. The dynamic artificial potential field (Dynamic APF) was introduced in response to these challenges. This variant aims to improve overall performance, reduce hardware dependence, and address the high computational requirements of tracking ground-moving targets using multi-rotor UAVs [61].

Table 3. Summary of the Traditional Path-Planning Algorithms.

Algorithms	Advantage	Disadvantage	Environment	Applicable Issues	Reference
A*	Low path cost Optimal solution	Low processing speed Calculation complexity Insufficient global optimization ability	Static	Shortest path Avoid collision	[25,33,53]
NP	More intuitive Easy to implement in engineering;	Difficult solution Real-time performance	Static	Small-scale problem	[35,44]
DP	Simple operation Global optimal solution	Large storage space Prone to combinatorial explosion	Static and Dynamic	Small-scale problem	[36,38]
MIP	Refined route planning	A large amount of calculation Complex modelingprocess	Static and Dynamic	Establishes target optimization model	[34,38,39]
MPC	Good control effect Strong robustness	Difficult implementation	Dynamic	Constraint control	[42,44,45]
Lyapunov	Control the stability of the UAV in a dynamic environment.	Function Construction	Dynamic	Judgment stability	[43,46,47,48,53]
Depth-first search	Specific knowledge is not required Less memory;	Weak environmental adaptability Lack of flexibility Poor local path-planning ability	Static	Small scale	[44,49]
Breadth-first search	Specific knowledge is not required Easy	A lot of memory The solution is not necessarily	Static	Small-scale path planning	[50]
Dijkstra	Short running time Easy	Less efficient	Static and Dynamic	Shortest path	[51,52,53]
RRT	Probabilistic completeness Fast calculation Low computational cost	Random sampling process Difficult to ensure optimality Not suitable for complex terrain	Static	Simple terrain High/Low-dimensional space	[55,56,57,58,59]
PRM	Effectively avoids local minima	Poor real-time performance Needs pre-known information about the environment The optimal path is random	Static	Simple terrain	[54]
APF	Low computational effort High real-time performance Smooth path	Local minima Difficult to adjust force field parameters	Static and Dynamic	Low-dimensional space Avoids collision	[60,61]

summarizes the advantages, disadvantages, applicable environments, and common challenges associated with the algorithms above to provide a comprehensive overview. Furthermore,

Table 4. Comparison of Traditional Path-Planning Algorithms.

Classification	Algorithms	Reference	Complexity	Fault Tolerance	Robustness	Computational Complexity/Speed	Reliability
Cell-based	A*	[16,17]	Medium	Low	Medium	Medium	Medium
Model-based	NP	[19]	Medium		—		High
	DP	[20,21]	Uncertain	—	—	Fast	High
	MIP	[18,22,23,24]	Uncertain	Low	Medium	Relies on a polynomial equation	Medium
	MPC	[26,29]	Low	High	High	—	—
	Lyapunov	[28,30,31,32]	Low	—	—	—	—
Graphics-based	Depth-first search	[33]	Uncertain	low	—	Low	Low
	Breadth-first search	[34]	Uncertain	Low	—	Medium	Low
	Dijkstra	[35,36,37]	Medium	Low	Medium	Medium	Medium
	RRT	[39,40,41,42,43]	Low	Medium	Medium	Fast	Medium
	PRM	[38]	Uncertain	Low	Low	Medium	Low
Potential field	APF	[60,61]	Low	Low	Medium	Fast	Medium

offers a comparative analysis of the performance of each traditional algorithm.

3.2. Intelligent Algorithm

AI algorithms represented by reinforcement learning, artificial neural networks (ANN), game theory, and deep learning are booming. In recent years, those algorithms have played an increasingly important role in autonomous flight control and decision-making of UAVs (especially in UAV path planning). Figure 3 shows the classification of the intelligent algorithm.

3.2.1. Swarm Intelligence Path Planning

Various intelligent algorithms have been proposed and applied to path-planning problems in recent years. Swarm intelligence algorithms can obtain better solutions when solving large-scale optimization problems. Based on the characteristics of the swarm intelligence algorithm, it can be further divided into evolutionary, biologically inspired, and meta-inspired algorithms according to different populations.

• Evolutionary Algorithm

The evolutionary algorithm, rooted in Darwin’s evolutionary theory, encompasses selection, recombination, and mutation. Notable algorithms in UAV path planning include GA [62], differential evolution (DE) [63], and non-dominated sorting genetic algorithm-II (NSGA-II) [64]. GA, renowned for its versatility and efficacy in large-scale and nonlinear problems, is frequently employed across path-planning studies.

For fixed-wing UAV-assisted systems, a study [65] used DP and convex programming for the optimal path, followed by GA, to derive a suboptimal path, reducing computational complexity. Recognizing GA’s reduced solution diversity due to its random walk nature, improvements included an adaptive threshold [66] and applying Bessel curves for path smoothing, enhancing exploration capabilities. Other studies explored DE and NSGA-II for path planning. DE, known for speed, was used as the fastest evolutionary algorithm. NSGA-II underwent improvements with ranking-based wheel selection and a local search method [67], validated in a 3D real environment dataset of Berlin, albeit without considering dynamic obstacles. For ground-UAV bistatic systems, path planning is modeled as a multi-objective optimization problem [68], employing a constraint-adaptive multi-objective DE method.

2.

Biologically Inspired Algorithms

Biologically inspired algorithms, which emulate biological activities such as foraging, play a significant role in UAV path planning. Several commonly used algorithms in this domain include ACO [69], particle swarm optimization (PSO) [70], wolf swarm [71], grey wolf optimizer (GWO) [72], and artificial bee colony (ABC) [73].

ACO is characterized by its focus on pheromone update state transfer and heuristic function construction. In UAVs’ global optimal trajectory planning, ACO with a multi-agent structure is employed for modeling and path search [74]. Inspired by the foraging behavior of birds, PSO is frequently used for UAV path planning. For example, a spherical vector-based PSO is proposed to address path-planning challenges in complex environments with multiple threats [75]. Comparative studies have been conducted between real-time GA and PSO for fixed-wing UAVs in dynamic 3D environments, revealing that GA statistically produces better trajectories [76]. GWO, a swarm intelligent algorithm inspired by grey wolves’ social organization and hunting-behavior patterns, is efficiently applied to UAV path planning [77]. In a study formulating path planning as a complex optimization problem with constraints, GWO successfully addresses UAV path-planning challenges in 3D environments [78]. ABC, a long-used algorithm for UAV path planning, has seen improvements over time, including introducing a penalty factor to modify the fitness values and enhance individual use within the colony [79].

While biologically inspired algorithms are computationally simple, robust, and scalable, they face challenges such as quick convergence to local optima and slow iteration as problem complexity increases. Modifications to the path-selection strategy and pheromone-allocation mechanism improved the convergence speed and optimality of the original ACO [80]. Another approach involves improving PSO’s global search capability and local search accuracy by introducing nonlinear inertia-weighting coefficients [81]. Additionally, combining bio-inspired algorithms with other widely used path-planning algorithms tailored to enhance different intelligent algorithms has proven to be effective. Further details on such integrated approaches are discussed later.

3.

Other Meta-Inspiration Algorithm

Various meta-heuristic algorithms in UAV path planning draw inspiration from diverse natural phenomena. Bio-inspired and evolutionary algorithms, as branches of meta-inspired algorithms, find application in this domain by mimicking biological activities. Notable algorithms such as Tabu search (TS) [82], simulated degradation (SD) [83], clustering algorithms [84], and multi-verse optimization (MVO) algorithms [85] are among the bio-inspired algorithms gaining popularity in UAV path planning.

TS, a widely used meta-heuristic algorithm, leverages memory structures to avoid revisiting previously explored solutions [86]. Natural phenomena inspire the SD algorithm and contribute to UAV path planning [87]. Clustering algorithms, which emulate the organizational principles observed in nature, have effectively addressed complex constraints and enhanced coverage in multi-mission UAV scenarios [88]. MVO, a relatively recent algorithm inspired by the universe, has found applications in fault diagnosis, power transmission, and numerical optimization [89,90,91]. In the context of UAV path planning, MVO treats the potential path of the UAV network as analogous to the universe, employing concepts such as black holes, white holes, and wormholes for path selection, interference mapping, and threat assessment [92].

Hybrid-optimization algorithms combining simulated annealing (SA) with other algorithms have demonstrated enhanced performance in UAV path planning. For instance, uniting SA with PSO improved global optimization abilities, convergence speed, and calculation accuracy in path-planning applications [86]. Another study applied SA to the execution process of ACO, incorporating an entropy-increase strategy [87]. Combining SA with clustering algorithms addressed the challenges of path planning for multiple multi-mission UAVs under complex constraints, leading to an enlarged UAV cruising coverage [88].

The application of clustering algorithms in UAV-assisted wireless sensor networks is noteworthy. K-means clustering, for instance, has been employed to minimize the cost of multiple UAV paths for information transmission, thereby enhancing the efficiency of subsequent path planning [93]. Inspired by natural and random phenomena, these diverse algorithms contribute to the rich approaches for tackling UAV path-planning challenges.

For better understanding, we compare the performance of the abovementioned swarm intelligence algorithms in

Table 5. Comparison of Swarm Intelligence Path-Planning Algorithms.

Classification	Algorithms	Reference	Complexity	Fault Tolerance	Computational Complexity/Speed	Robustness	Reliability
Evolutionary method	GA	[62,66]	High	High	Slow	High	High
	DE	[63,68]	Medium	High	Medium	High	Medium
	NSGA-II	[64,67]	Medium	High	Medium	High	High
Biological inspiration	ACO	[69,74,80]	Medium	High	Fast	High	High
	PSO	[70,75,76,81]	Medium	Medium	Fast	Medium	Medium
	GWO	[72,78]	Medium	Medium	Medium	Medium	Medium
	ABC	[73,79]	Medium	High	Medium	High	High
Other Meta-inspiration	TS	[82]	Low	High	Fast	Medium	Medium
	SA	[83,86,87,88]	Low	High	Medium	High	Medium
	MVO	[85,92]	Medium	High	Medium	High	High
	Clustering	[84,93]	Low	Low	Fast	Low	—

and then summarize the advantages, disadvantages, applicable environments, and most practical problems of these algorithms in

Table 6. Summary of Swarm Intelligence Path-Planning Algorithms.

Algorithms	Advantages	Disadvantages	Environment	Applicable Issues	Reference
GA	Mature development and wide application	Poor local search ability Difficult to determine genetic factors	Static and Dynamic	Dynamic path planning Terrain coverage	[62,66]
DE	Simple structure and easy to implement Fast convergence It avoids local optimal solutions	Premature convergence Reduces diversity in later stages	Static and Dynamic	Global optimization problem Dynamic path planning	[63,68]
NSGA-II	Multi-objective optimization Easy to select parameters	Poor local search ability Low population diversity Uneven convergence distribution	Static and Dynamic	Multi-objective optimization	[64,67]
ACO	Fast convergence at the later stage Memorability	Long search time in the first phase Many parameters and difficult to set	Static and Dynamic	Global optimization problem	[69,74,80]
PSO	Few parameters Fast convergence speed in the early stage	Slow convergence speed in the later stage Low accuracy	Static and Dynamic	——	[70,75,76,81]
GWO	Fast convergence speed High solution accuracy Strong search ability	Easy to fall into local optima	Static and Dynamic	——	[72,78]
ABC	Multi-role division of labor There is no need to specify derivative or gradient information	Easy to fall into local optima	Static and Dynamic	Function optimization problem	[73,79]
TS	Step-by-step global optimization Strong local optimization ability	Not suitable for large-scale optimization	Static and Dynamic	Combinatorial optimization Function global optimization	[82]
SA	Simple calculation process Strong versatility and robustness	Slow convergence speed and long execution time	Static and Dynamic	Combines with other algorithms A large-scale combinatorial optimization problem	[83,86,87,88]
MVO	Few parameters High search efficiency Avoids local optima	Slow convergence The solution accuracy is not high	Static and Dynamic	A large-scale combinatorial optimization problem	[85,92]
Cluster	No training set required Simple and fast	Susceptible to outliers	Static	Reduces the complexity of the problem	[84,93]

.

3.2.2. AI Path Planning

• Reinforcement-Learning Algorithm

Reinforcement learning learns by interacting with the environment and using evaluative feedback signals to optimize decisions. Reinforcement learning can be divided into value function-based RL and strategy-based RL. The most used algorithm for value function-based reinforcement learning is Q learning, and many studies have applied it to UAV path planning [94,95]. However, since the Q-learning algorithm’s state and action space are discrete, the planned path is poorly flyable and challenging to navigate in the presence of dynamic threats. Researchers proposed a deep-reinforcement-learning (DRL) algorithm combining deep learning and reinforcement learning to meet continuous-state or action-space needs. Unlike traditional algorithms that need to model UAVs, DRL directly maps the motion state of UAVs to their flight control parameters and realizes the autonomous flight planning of UAVs through repeated training. Papers [96,97] introduced two different improved DRLs in UAV path planning, and both achieved good results. However, since the DRL action space is still discrete, the quality of the planned path can be improved. The researchers combine strategy-based reinforcement learning with deep learning to achieve continuous state and action space. The strategy-based DRL algorithm includes deep deterministic policy gradient (DDPG) [98] and distributed proximal policy optimization (DPPO) [99]. Some scholars have tried to apply it to UAV path planning [100,101]. In [102], a phased training scheme based on DDPG was used to plan the UAV path. The method has three stages: in the first stage, a UAV ignores the no-fly zone reaching the target point; in the second stage, a UAV can sense and bypass the no-fly zone to reach the target point; in the third stage, the speed of the UAV is improved based on the second stage to improve the flight efficiency. This research is mainly focused on single UAV path planning.

2.

Game-Theory Algorithm

Game theory seeks optimal strategies that maximize the interests of all parties in interconnected competitive scenarios. Within game theory, a model is crucial to balance the interests of both parties and propose an optimal solution that satisfies everyone’s needs. Nash equilibrium is then used to illustrate the stable state, making it suitable for multi-objective optimization problems with multiple constraints, particularly those involving relative contradictions. Game theory excels in finding mutually satisfying solutions in conflicting interest scenarios, and it has been applied to path planning in various studies. The paper [103] integrated game theory into the path planning of two robots, demonstrating superior performance compared with the widely used A* algorithm. The authors in [104,105] applied game theory to UAV path planning. It introduced a joint game-based solution where the data collected by the UAV is conceptualized as a hedonic cooperative game.

3.

ANN Algorithm

ANNs are algorithmic mathematical models that emulate the behavioral characteristics of animal neural networks, primarily employed for distributed parallel information processing. In contrast to swarm intelligence algorithms, ANNs exhibit a rapid adaptation capability, enabling quicker problem-solving. Numerous studies have harnessed the power of ANNs for UAV path planning. GA outputs were used to train ANN path planning for UAV obstacle avoidance. The method emphasized the crucial link between flight step size and path quality in the meter unit, where a smaller step length enhances path planning accuracy in the meter unit at the expense of increased computational effort [106].

4.

Deep-Learning Algorithm

Deep neural networks (DNNs) exhibit excellent feature learning capabilities, extracting concise and compelling information from complex high-dimensional states. However, few studies exclusively employ DNNs for UAV path planning due to the significant data requirements for deep-learning (DL) algorithm training. Current research often combines DL algorithms with other path-planning approaches, such as GA, PSO, and A*, to generate diverse datasets for DL algorithm training. The neural RRT* algorithm addresses the limitations of RRT by combining a convolutional neural network (CNN) with RRT* [107]. GA mentors impart path-planning experience to DNNs [108]. DNNs were trained using these pre-generated trajectory sets [109]. The combination of DL and reinforcement learning (RL) in deep RL (DRL) enabled the learning of optimal path-planning strategies through interaction with the environment. A recurrent neural network (RNN) extracted critical information. A behavior selection strategy combining the current reward and national behavior values was developed for dynamic 3D UAV path planning [110]. To facilitate understanding,

Table 7. Comparison of AI Path-Planning Algorithms.

Algorithms	Ref.	Complexity	Fault Tolerance	Computational Complexity/Speed	Robustness	Reliability
ANN	[105,106]	Medium	Medium	Medium	Medium	Medium
Q learning	[94,95]	Medium	High	Medium	High	Medium
DRL	[96,97,98,99,100,101,102]	High	High	Related to the learning rate	High	High
Game theory	[103,104]	Medium	High	Medium	High	High
DNN	[107,108,109,110]	High	High	Low	High	High

provides a performance comparison of each AI algorithm, while

Table 8. Summary of AI Path-Planning Algorithms.

Algorithms	Advantages	Disadvantages	Environment	Applicable Issues	Reference
ANN	Strong fault tolerance Certain generalization abilities and adaptive ability	Several path-planning data sets It is easy to fall into local Difficult to determine network structure	Static	Low-dimensional space	[105,106]
Reinforcement learning	Good real-time performance Avoid local minima Simple and efficient	Discrete state and action space Difficult to deal with dynamic threats Random strategy problem	Static and Dynamic	Discrete problem Low-dimensional space	[94,95]
DRL	Model-free self-learning ability Strong self-learning ability No global information is required High-dimensional information perception	Not easy to converge High sensitivity for super parameters	Static and Dynamic	Large-scale and complex path planning	[96,97,98,99,100,101,102]
Game theory	Avoid conflict Cooperation and competition Intelligent decision	Too many Nash equilibrium solutions Weak applicability	Static and Dynamic	Confrontation game Distributed decision Resource management	[103,104]
DNN	Large-scale parallel processing Distributed storage Strong adaptability and fault tolerance	A large number of data sets High redundancy and computational cost Generalization ability to be verified Long training time	Static and Dynamic	Classification and regression High-dimensional space	[107,108,109,110]

summarizes the advantages, disadvantages, applicable environments, and common challenges of these algorithms.

3.3. Hybrid Algorithm

Given the diverse strengths and weaknesses of various path-planning algorithms, researchers often explore integrating multiple algorithms to leverage their respective advantages and compensate for their shortcomings, creating hybrid algorithms. Hybrid algorithms encompass algorithm integration and sorting, combining techniques to enhance overall performance. While many works have delved into the study of hybrid algorithms, this space constrains the detailed elaboration of their principles. It is important to note that these hybrid approaches aim to harness the complementary strengths of different algorithms, providing a more robust and effective solution for UAV path-planning challenges.

3.3.1. Algorithm Integration

Algorithm integration involves the combination of two or more algorithms, where one algorithm serves as the primary component, and others are integrated into specific stages of the algorithmic process. This approach offers flexibility and feasibility in solving complex problems, and it has been applied in various contexts within UAV path planning.

One integration avenue combines traditional and intelligent algorithms, as demonstrated in [111]. Examples include integrating RRT with APF [112], GA with local roll optimization (LRO) [113], and GA with particle filters (PF) [114]. In the case of LRO and GA [113], LRO is introduced into the global planning process, continuously optimizing paths generated by GA.

Moreover, the integration of multiple intelligent algorithms is another viable strategy. Examples include combining the wolf pack algorithm with reinforcement learning [115] and integrating Q-learning with DE [116]. In a specific instance [117], an artificial swarm algorithm was applied to modify the bat algorithm (BA) to generate collision-free, safer, shorter paths in a 3D battlefield environment. This algorithm used BA to generate point trajectories and introduced a mutation factor that selected the top 50% of small bats as employed bees and the remaining as spectator bees. A scout bee was incorporated into the algorithm to overcome local optimal solutions. The computational cost of this integrated algorithm was approximately 50% lower than BA while achieving a path generation quality about 14% higher than ABC.

3.3.2. Algorithm Sorting

In algorithm sorting for UAV path planning, a strategy involves obtaining a path planning result using one algorithm and optimizing it using another. This approach aligns with the concept of algorithm integration. In a specific study [118] focused on the multi-UAV path planning problem in wireless sensor networks, the authors employed the K-means clustering algorithm to simplify the problem’s complexity. They then enhanced the ant colony algorithm by modifying node search rules and introducing optimal solution detection rules for subsequent multi-UAV path planning.

In another instance [119], a novel approach named hybrid DE based on quantum PSO (DEQPSO) was introduced for UAV path planning. The hybrid algorithm updates the overall configuration using quantum PSO in each generation of DEQPSO and then executes the DE algorithm.

Introducing these hybrid algorithms demonstrates their capacity to mitigate some of the shortcomings of both intelligent and traditional algorithms. Consequently, the efficiency of UAV path planning experiences substantial improvement.

Table 9. Summary of Hybrid Algorithms.

Reference	Classification	Algorithms	Description
[112]	Algorithm integration	RRT and APF	RRT makes the overall planning decision for the path and builds the objective function based on the APF and path length
[113]		GA and LRO	GA is used for global path planning LRO is used to optimize the results of the GA continuously
[114]		GA and APF	APF with modified gravitational function is used to obtain the globally optimal path GA is used to optimize the robot’s step length and motion direction.
[116]		DE and Q-Learning	DE for global search, Q-learning for local optimization
[117]		ABC and BA	Uses ABC to modify BA
[118]	Algorithm sorting	K-means and ASO	The k-means clustering algorithm is used for the search efficiency of path planning. ASO with modified node search rules is used to search for paths
[119]		QPSO and DE	QPSO algorithm updates overall. Then, the DE algorithm is executed

provides a detailed analysis of proposals for hybrid algorithms in UAV path planning, showcasing the versatility and advantages of integrating different algorithmic approaches.

The UAV path-planning field has witnessed significant advancements, with swarm intelligence algorithms, AI algorithms, and mathematical model-based algorithms demonstrating fruitful results. The prevailing trend indicates a movement towards integrating AI and a harmonious combination of multiple planning algorithms. This evolution enables algorithms to converge rapidly to optimal solutions in global planning processes while responding promptly to sudden disturbances and uncertainties in local planning.

Swarm intelligence algorithms, AI algorithms, and mathematical model-based algorithms emerge as the front-runners, providing efficient and safe paths. The development trend emphasizes the organic fusion of AI and the use of various planning algorithms, showcasing the algorithms’ ability to adapt quickly to different scenarios.

While traditional and artificial algorithms have matured in path planning, their generalization capabilities for diverse scenarios remain limited. Machine learning, though in its exploratory stage, holds promising applications. Its advantages include excellent real-time capabilities, resistance to local minima, and independence from prior environmental information. However, challenges arise when dealing with continuous state and action spaces, leading to potential convergence issues during model training. Future work could explore incorporating AI to enhance model effectiveness and integrate label-less learning technologies for path planning.

Given the NP-hard nature of path planning, the quest for an optimal path demands substantial computation and memory resources, consuming valuable time. Practical applications necessitate swift responses from path-planning systems, making it essential to balance feasibility with theoretical optimality within specified time constraints. Modern intelligent algorithms, such as genetic and ant colony algorithms, have proven effective in achieving this balance. Scholars are encouraged to refine the algorithms and improve search efficiency and accuracy. It involves tailoring path-planning algorithms to their specific characteristics, refining initialization algorithms, optimizing coding algorithms, and addressing angle constraints. These enhancements aim to create more suitable algorithms for path planning, producing superior trajectories at faster speeds and achieving genuinely effective paths.

4. Function-Level UAV Path-Planning Classification

A comprehensive overview of generic algorithms for the subproblem of UAV path planning focusing on path and trajectory planning is provided. The subsequent discussion aims to classify existing path-planning algorithms at the functional level to build upon this foundation. This classification is based on three distinct perspectives: time-based planning, space-based planning, and mission-based planning. By examining UAV path planning from these alternative viewpoints, researchers can gain a nuanced understanding and make informed choices when selecting path-planning algorithms. Figure 4 shows the classification of function-level path planning.

Planning time-based algorithms are analyzed and classified based on their temporal characteristics. This perspective considers how algorithms perform in terms of planning time, responsiveness, and adaptability to dynamic and time-sensitive environments. The goal is to understand how well algorithms address the temporal constraints inherent in UAV missions.

Space-based algorithms focus on the spatial aspects of path-planning algorithms. They delve into how algorithms handle the spatial intricacies of the environment, considering factors such as obstacles, terrain, and 3D space. Researchers can evaluate their efficacy in diverse operational backgrounds by categorizing algorithms based on spatial characteristics. Missions-based algorithms are classified here based on their alignment with specific mission requirements. Different UAV missions may necessitate distinct path-planning approaches. This perspective evaluates how well algorithms cater to mission-specific objectives, whether they be area coverage, target visitation order, or optimization of mission parameters.

By adopting these functional classifications, researchers can gain insights into the strengths and limitations of path-planning algorithms from various angles. This multifaceted analysis enables a more nuanced understanding of how algorithms perform in different contexts and aids in selecting or developing algorithms that align with specific mission requirements.

4.1. Space-Based Algorithm

From a spatial perspective, existing studies in UAV path planning can be categorized into 2D and 3D scenarios, and we delve into the details of both algorithms.

In the 2D scenario, a UAV is assumed to fly by maintaining a constant flight altitude or through manual adjustments. Early path-planning research primarily focused on 2D scenarios due to the simplicity of path-planning operations and lower computational intensity. Much of previous path-planning research has been devoted to 2D studies.

However, technological advancements and increased environmental complexity have shifted the focus toward 3D path planning in recent years. In a 2D scenario, the UAV operates in a flat plane, while in a 3D scenario, the UAV navigates a 3D space. 3D path planning introduces a more complex environment with additional constraints and kinematic considerations. Challenges include intricate environment modeling, multiple threats, and heightened computational requirements.

With the progress of computing technology, there is now an ability to meet high-performance demands for machine learning and deep learning. Machine-learning and deep-learning algorithms are increasingly applied in 3D UAV path planning, offering more accurate solutions to NP-hard problems within a broader search space. These advanced techniques are particularly beneficial in addressing the challenges posed by the complex nature of 3D environments.

Moreover, breakthroughs have been made in swarm intelligence algorithms, which also apply to 3D path planning. These algorithms leverage collective behaviors inspired by natural systems, such as ant colonies or bird flocks, to find optimal solutions in complex spatial environments.

While 2D path planning has historically dominated research due to its simplicity, recent technological advancements and the growing complexity of real-world scenarios have elevated the importance of 3D path planning. This shift has prompted the integration of advanced computing technologies, machine learning, deep learning, and swarm intelligence algorithms to tackle the challenges posed by intricate 3D UAV operating environments.

4.2. Time-Based Algorithm

The existing research on UAV path planning can be classified into static and dynamic paths based on time characteristics. Static path planning involves modeling a known environment, assuming that the surroundings and mission parameters remain constant. While this approach yields high accuracy, its real-time performance is suboptimal. Traditional path-planning algorithms, well-suited for static scenarios, are not explored in detail here.

In dynamic environments, where real-world situations change rapidly, static paths become obsolete. Dynamic path planning addresses this challenge by re-planning paths based on UAV flight status, fuel consumption, threat level, and time minimization. This dynamic path planning falls into dynamic multi-objective optimization, a recognized NP-hard problem. GA is famous for dynamic path planning, providing optimal real-time solutions. A hierarchical recursive multi-subject GA is proposed, effectively managing computational complexity and generating collision-free paths in real time by considering the dynamic characteristics of the environment [120]. Another approach, presented in [121], uses security indicator diagrams (SID) to capture static and unexpected obstacles. An offline search for static security indicator diagrams yields a Pareto optimal path, while an online search method optimizes paths based on dynamic security indicator diagrams.

Efforts have also been made to enhance dynamic path planning efficiency through big data platforms. Hadoop and Spark platforms are employed for data storage and computation, respectively [122]. This infrastructure supports the development of time-varying path-planning algorithms. Paper [123] also introduces a three-tier online data processing network based on mobile edge computing technology. Sensors generate original data at the bottom layer, a UAV base station (acting as a mobile edge computing server) processes data in the middle layer, and a central cloud system in the upper layer accepts and analyzes results. This network aims to enhance the effectiveness of online route planning for multi-UAV systems.

These dynamic path-planning approaches showcase the evolving landscape of UAV research, focusing on real-time adaptability and efficiency in the face of changing environmental and mission conditions.

4.3. Missions-Based Algorithm

Indeed, it has been strongly suggested that we should analyze the three fundamental categories of UAV path planning: shortest path planning, TSP, and area coverage path planning.

In the domain of shortest path planning, the primary objective is to find the most efficient route from the current location of the UAV to a target location. It minimizes flight time, achieves the shortest distance, or reduces energy consumption. Shortest path planning is foundational to various UAV missions, ensuring optimized navigation between waypoints. Terrain effects, mission-specific requirements, and the physical limitations of the UAV are critical considerations in this context. Algorithms such as recurrent neural networks have addressed the shortest path problem [124].

TSP in UAV path planning involves visiting a set of mission targets in the most efficient order to minimize overall travel costs. The UAV serves as a “traveling salesman”, and each mission target acts as a “city” that needs to be visited exactly once [125]. This problem is relevant to logistics, information gathering, and scenarios where the sequence of target visits impacts mission success. Various optimization algorithms, including GA, PSO, and mixed-integer linear programming, have been applied to solve TSP-related UAV path-planning problems [126,127,128].

Regional coverage path planning focuses on designing paths for UAVs to cover a target region effectively [129]. The goal is to achieve maximum coverage within specified constraints, such as energy limits or path length. It is crucial in communication coverage, photogrammetry, disaster management, search and rescue, and precision agriculture [130]. The optimization problem involves resolving conflicts between objectives, such as minimizing energy consumption, mission time, or maximizing coverage. Various approaches, including weight assignment and mixed-integer linear programming, have addressed challenges in area coverage path planning [131,132]. Each UAV path-planning category addresses specific mission requirements and operational constraints, contributing to UAVs’ diverse applications and capabilities across various industries.

4.3.1. Shortest Path Planning

Determining the shortest path is fundamental in nearly all UAV missions and can be leveraged as a subproblem for the other two types. However, in the context of 3D path planning, the optimal path does not always align with the concept of the shortest path. Considerations such as terrain effects, mission-specific requirements, and the physical limitations of the aircraft must also be factored into the path-planning process. In addressing the shortest path problem, a recurrent neural network approach has been proposed as an effective solution to underscore the significance of deploying advanced techniques to navigate the complexities inherent in UAV path planning scenarios, where considerations extend beyond simple distance or time optimization to encompass a range of dynamic factors and mission-specific constraints [124].

4.3.2. TSP

The TSP in UAV path planning entails optimizing travel time or distance to selected waypoints, resembling a scenario where the UAV serves as a traveling salesman visiting each mission target once. In logistics transportation [125] and information gathering, UAV path planning aligns with the TSP framework. An improved GA (IGA) and a PSO-based ACO (PSO-ACO) algorithm were proposed as solutions to the TSP problem within UAV path planning [126].

Moreover, the authors identify two distinct TSP-based UAV path planning problems: the flying side stands TSP (FSTSP) and the parallel drone scheduling TSP (PDSTSP) [127]. MIP formulation addressed the former problem, bifurcating path planning into two decision phases [128]. The authors devised a Benders-type algorithm to solve this two-stage model effectively. Addressing the limitations of PDSTSP, particularly safety and efficiency, [129] introduced a variant named TSP with unmanned stations (TSP-US).

In UAVCN, solving the TSP problem becomes even more intricate, as each neighborhood’s size can be a design variable contingent upon communication requirements. This particular challenge will be further elucidated in the subsequent section. The integration of TSP formulations within UAV path planning attests to the versatility of this classic optimization problem in addressing diverse requirements in UAV mission scenarios.

4.3.3. Regional Coverage Path Planning

Existing UAV-coverage path-planning methodologies typically address optimization problems grounded in one or more objective conditions, such as minimizing energy consumption, mission time, or maximizing coverage. Given the potential conflicts inherent in these conditions, a pivotal aspect of path planning involves the resolution of such conflicts. One approach consists of formulating a new objective function through weight assignment. The authors addressed the challenge of maximizing coverage within minimum mission time [131]. A weight allocation method was employed to amalgamate these indices into a unified objective function to confront conflicting objectives. It is noteworthy, however, that this algorithm is explicitly tailored for static path planning scenarios.

An alternative methodology entails framing the problem as a mixed-integer linear programming problem. The authors tackled a path planning problem incorporating terrain constraints, obstacle avoidance, and coverage for subsequent flights [132]. The proposed approach involved generating a zigzag path using the DE algorithm for path optimization, with the fast advanced square planner determining the absolute path. Simulation results underscored the method’s ability to ensure a specific flying height at a lower cost, covering the designated area. They demonstrated its applicability in static and dynamic environments to highlight the versatility and efficacy of diverse approaches in addressing the nuanced challenges of regional coverage path planning in UAV systems within the academic discourse.

5. Future Research Directions and Challenges

5.1. UAV Path Planning in 3D Environment

Due to structural constraints and uncertainties, path planning is deemed more feasible than its 2D counterpart in 3D environments. Path planning algorithms aim to determine conflict-free trajectories while minimizing travel distance or energy consumption. Despite the advancements, existing algorithms are underexplored for intricate environments, such as those with U-shaped obstacles or densely populated dynamic scenarios. It highlights the need for more integrated representations of spatial context in 3D path planning in complex settings.

Given the widespread integration of UAVs in military and civil applications, the limitations of a single UAV in payload and flight capabilities become apparent. Collaborative efforts involving multiple UAVs are crucial for executing complex tasks, showcasing enhanced viability and expanded task execution capabilities. Adherence to spatially defined target points and strict temporal constraints in scenarios with multiple UAVs necessitates four-dimensional path planning technology. The ascendancy of four-dimensional path planning, offering superior real-time performance, is inevitable in the evolution of UAV path planning. Therefore, future research should focus on developing and enhancing four-dimensional path-planning algorithms tailored to the challenges of cooperative task execution by multiple UAVs.

The path-planning algorithm holds paramount importance at the core of this technological landscape. Future research must prioritize selecting and refining algorithms to address intricacies in four-dimensional multi-UAV cooperative path planning. This urgency is emphasized by the growing prevalence of cooperative UAV missions, demanding precision in spatial and temporal coordination, thus requiring advancements in path-planning algorithms tailored to these complex operational requirements.

5.2. Dynamic UAV Path Planning

The increasing use of UAVs in both military and civilian applications is driven by the necessity imposed by the uncertain and adversarial nature of operational environments and the potential for encountering unforeseen circumstances during flight. In future research, real-time planning will become a focal point, requiring attention to two critical concerns: the computational speed prerequisites and the fidelity of environmental information. Pioneering works, exemplified by the papers [64,65,68], have used reinforcement learning and deep learning in dynamic path planning, resulting in commendable outcomes. Therefore, an essential trajectory for future investigations involves pursuing UAV dynamic path planning based on deep learning or reinforcement learning principles. Simultaneously, challenges associated with applying existing AI methodologies in path planning need proactive resolution, addressing issues such as relatively low convergence and the scarcity of suitable datasets.

5.3. Game Theory Applied to UAV Decentralized and Cooperative Control

Game theory has emerged as a potent tool for optimizing energy consumption, augmentation of network coverage, resource management, coordinated control of multiple, and enhanced connectivity in UAVCNs [32]. Notably, decentralized cooperative control for UAVs involving multiple UAVs is deemed more consequential than centralized control. Delineating an individual aircraft’s action scope and cooperative path planning is pivotal in designing a decentralized cooperative control structure. Game theory is a foundational framework for facilitating distributed decision-making and cooperative behavior within UAVs. Simultaneously, the intrinsic coupling of UAV target functions and multiple game scenarios, influenced by factors such as interference or collision, markedly advance the applicability of the game theory in the realm of UAVCNs.

5.4. UAV Cluster Path Planning

In extant research about the coordinated planning of multiple paths, a notable lacuna exists in formulating inter-cluster collaboration. A conspicuous divergence is observed, wherein certain studies neglect to consider collaborative aspects and focus solely on the individual planning of multiple paths. Conversely, others incorporate collaboration constraints limited to temporal and spatial considerations. In the broader context, a lack of investigations into the intricacies of deep-level synergy exists. It is imperative to recognize that future agent clusters are envisioned to resemble living systems characterized by integration, hierarchy, and interrelatedness. Consequently, further scholarly inquiry is warranted to delineate the interrelationship between the entire cluster and its constituent components, emphasizing enhancing synergy to optimize the collective benefits accrued by the clusters.

5.5. Hybrid Path-Planning Algorithm

Significant strides have been achieved in UAV path-planning algorithms; nonetheless, each algorithm exhibits inherent limitations. Consequently, the current focal point within the field of path planning is the exploration of novel, efficient path-planning algorithms and fusion algorithms. The synergistic integration of diverse algorithms, leveraging their respective strengths and mitigating weaknesses, has catalyzed the evolution of a spectrum of improved algorithms.

One illustrative instance involves amalgamating machine learning, swarm intelligence, and traditional algorithms in UAV path planning. This integrated approach effectively addresses challenges associated with swarm intelligence algorithms, such as susceptibility to locally optimal solutions, leading to convergence speed and robustness enhancements. Future research endeavors are advised to develop hybrid path-planning algorithms, particularly emphasizing the amalgamation of AI with other algorithmic paradigms. This pursuit aims to refine the UAV path-planning algorithm system, rendering it more comprehensive and creating a more promising landscape for UAV applications.

5.6. UAV Path Planning in 4D Environment

4D path planning is usually referred to as incorporating time as the 4th dimension, including multi-UAV cooperation path planning as the 4th dimension. Effective collaboration and information exchange among UAVs and between UAVs and users relies on a pivotal communication network during task execution. The complexities of path planning surpass those in single UAV networks. These challenges span various factors, including the quantity of UAVs, inter-vehicle distances, functional structures, flight durations, path configurations, device-to-device channel parameters, coordination methodologies, kinematic characteristics, safety considerations, and connectivity requirements.

Within UAV clusters, communication dynamics among UAVs and between UAVs and ground stations impose stringent latency demands, particularly critical in scenarios requiring frequent data interactions for large-scale crowd area detection. Communication channel instability may introduce delays or packet losses, jeopardizing real-time environmental data perception within the cluster system and posing potential security risks. Multi-UAV path planning constitutes a complex, large-scale, and constrained multi-objective optimization problem. The intricate interplay of numerous variables and considerations necessitates sophisticated algorithms and methodologies to navigate the challenges posed by cooperative communication, control, and safety. Optimizing collective performance in UAV clusters demands an integrated approach that addresses the diverse and interconnected aspects of multi-UAV path planning within the context of communication network constraints. This comprehensive perspective is vital for effectively deploying UAV clusters in real-world scenarios, ensuring the optimization problem’s multifaceted nature is appropriately addressed.

5.6.1. Technology Level

Modeling multi-UAV cooperative path planning introduces complexities surpassing those associated with single-UAV path planning, leading to a greater diversity of available solution algorithms. Prevailing research typically divides the process into path-generation and collaborative planning, with initial studies concentrating on constructing path-generation models. Enhancing path planning accuracy necessitates comprehensively considering cluster tasks, temporal coordination constraints, and track smoothing, presenting a multifaceted challenge warranting further investigation.

The prevalent reliance on swarm intelligence algorithms or hybrid methodologies, such as ACO, PSO, and GA, in existing research, signals a need for a more nuanced approach. Recent advancements in AI, particularly in deep learning and reinforcement learning, have demonstrated remarkable efficacy in addressing sequential decision optimization problems. Thus, employing deep learning and reinforcement learning for UAV cluster path planning emerges as a crucial future research direction, promising accelerated and dynamic path planning capabilities. Existing studies exhibit limitations in elucidating collaboration dynamics between clusters, with some overlooking collaboration considerations and others confining synergy within temporal and spatial bounds. A noticeable gap in research on deep-level synergy is apparent. Envisioning intelligent clusters akin to living systems requires renewed attention to global and local relationship planning. Therefore, future research should strive for a more holistic understanding of intelligent clusters and their collaborative dynamics, focusing on optimizing synergy for enhanced collective performance.

5.6.2. Representative Result

A thorough evaluation of multi-UAV dynamics, encompassing radar threat, missile threat, terrain threat, connectivity, fuel consumption, and mission time considerations, was conducted [133]. The authors improved the individual fitness within the GWO framework by initializing the population within predefined constraints. A coefficient was introduced to balance global and local search capabilities, and the PSO concept was incorporated for optimal particle solutions, enhancing the GWO algorithm’s convergence and solution quality.

A distribution method addressed a multi-UAV task assignment problem [134]. Path planning used neighbor search and PSO, ensuring a secure approach applicable in dynamic environments. This methodology provides a robust solution for coordination challenges in multi-UAV scenarios. In another study [135], the focus was on determining the number of UAVs and their task assignments based on priority. Path planning followed the assigned tasks, enhancing the fruit fly optimization algorithm with optimal reference points, a reference point mechanism, and a judgment matrix for improved stability and precision. The established cost function derived an optimal path, highlighting the method’s efficacy in optimizing path-planning processes for UAVs in dynamic environments.

6. Conclusions

As a foundational technology enabling UAVs to execute diverse tasks, path planning assumes a critical role across numerous applications within the UAV domain. This paper offers a comprehensive survey of path-planning methodologies tailored for UAVs. The focus of this survey is an analytical review of UAV path-planning research at both algorithmic and functional levels, combined with a comparative analysis of various algorithms. UAV path-planning algorithms are systematically categorized into three classes—traditional, intelligent, and hybrid—with subsequent sub-classifications. Each algorithmic category’s associated advantages and disadvantages are delineated for comprehensive insight.

Furthermore, this survey addresses specific considerations such as 3D path planning, dynamic path planning, the TSP, determining the shortest path, and coverage issues. A parallel exploration encompasses the challenges and technological levels inherent in multi-UAV path planning. In conclusion, an examination of the future research directions for UAV path planning is conducted, providing a forward-looking perspective on the evolving landscape of this critical field.