Path Planning for Autonomous Drones: Challenges and Future Directions

Abstract

Unmanned aerial vehicles (UAV), or drones, have gained a lot of popularity over the last decade. The use of autonomous drones appears to be a viable and low-cost solution to problems in many applications. Path planning capabilities are essential for autonomous control systems. An autonomous drone must be able to rapidly compute feasible and energy-efficient paths to avoid collisions. In this study, we review two key aspects of path planning: environmental representation and path generation techniques. Common path planning techniques are analyzed, and their key limitations are highlighted. Finally, we review thirty-five highly cited publications to identify current trends in drone path planning research. We then use these results to identify factors that need to be addressed in future studies in order to develop a practical path planner for autonomous drones.

1. Introduction

Unmanned aerial vehicles (UAV), commonly referred to as drones, are defined as aerial vehicles that operate without the need for an onboard human pilot. According to the Federal Aviation Administration, there will be 835,000 commercial drones registered in the United States of America by 2025, about twice the number of commercial drones registered in 2020 [1]. Moreover, Morgan Stanley’s base case forecasts indicate that the autonomous urban aircraft industry (including drone delivery, flying taxis, military drones, and industrial worker drones) will be worth USD 1.5 trillion by 2040. Drones are particularly beneficial since they can perform high-risk missions without endangering human lives. Since drones are a safer alternative to manned military aircraft, they have been widely used for defence. However, due to advancements in technology and decreases in drones’ production costs, there has been a lot of interest in developing drones for commercial applications. The versatility of drones makes them ideal for surveillance, precision agriculture, search and rescue missions, inspections, and goods delivery. There have been extensive reviews into the advancements of the use of drones for agricultural [2] and logistical applications [3].

Over the last decade, many logistics companies, such as Amazon, United Parcel Service, and DHL, have been looking for alternative approaches to reduce the costs of last-mile deliveries. The use of autonomous drones can be very beneficial, especially since companies are consistently looking to deliver packages faster. Amazon [4] has announced that it is developing a hybrid drone with the ability to travel 15 miles to deliver packages under five pounds. However, there are many challenges with the use of drones for commercial applications. Generating energy-efficient paths has been a major area of research for such applications. For example, in some studies such as [5], the authors suggest generating a path along a public transportation network for drone delivery.

Although drones can be controlled by an operator at a ground control station, developing drones with high levels of autonomy makes them very useful for completing tasks that must be performed beyond the visual line of sight. There are many challenges involved in the development of a control system for autonomous drones. Several factors, including decision-making capabilities, path planning, trajectory generation, and fault-tolerant redundant management (in the instance of disturbances and failures), are required for drones to navigate autonomously [6]. To achieve this, drones must have the ability to sense and perceive its environment and compute a path using onboard computers and sensors. Additionally, flight navigation controlled by an onboard computer reduces the frequency with which an operator needs to interact with a drone, thus limiting the opportunity for human errors.

Many path planning algorithms have been suggested in the literature. The objective of this review is to summarize common methods suggested for drones to navigate an environment and path planning algorithms suggested for drones to compute an optimal or near-optimal path. We highlight key limitations with existing algorithms and some of the work being performed to overcome these limitations. Although much progress has been made in the field of path planning for drones, further work is required to develop a robust path planner. From a review of recent studies, we identify key factors that need to be considered in a study in order to develop a practical path planner for commercial applications.

The paper is organized as follows: In Section 2, we review the different types of drones that are available. Section 3 describes the current limitations of drones. Section 4 describes the drone path planning problem. Section 5 outlines some of the current drone path planning solutions in the literature, and in Section 6, an analysis is performed to determine future directions. Finally, we draw conclusions in Section 7.

2. Drone Classification

Generally, there are three major categories in which drones can be classified under: rotary-wing, fixed-wing, and flapping-wing drones. Each drone design has their own benefits and disadvantages [7]. For the purposes of this review, we are interested in looking at how these drone types affect drone path planning and navigation; therefore, we focus primarily on drone maneuverability and endurance.

Many studies model multi-rotor drones, such as quadcopters, for path planning applications due to their vertical takeoff and landing capabilities, high maneuverability, and hovering capabilities [8,9,10]. The maneuverability of drones makes multi-rotor drones suitable for tasks such as surveillance and search and rescue [11]. However, the main issue with rotary-wing drones is their limited flight time. Compared to flapping-wing and fixed-wing drones, rotary-wing drones rank the worst in flight endurance but best in maneuverability [12].

Even though fixed-wing drones have better battery performance than multi-rotor drones, they have many kinematic and dynamic constraints that need to be considered for practical applications. Moreover, it has been shown that rotary-wing drones are less susceptible to air turbulence than fixed-wing drones of similar dimensions [13]. However, in rural areas, fixed-wing drones have proven to be reliable for delivery applications. The drone delivery company Zipline has been using fixed-wing drones to deliver blood in Rwanda and Ghana. Takeoff and landing are a challenge with fixed-wing drones, but they can be valuable for rapid long-distance deliveries. Moreover, compared to rotary-wing drones, fixed-wing drones have been shown to cause less vibration during drone flight in real-world delivery applications [14].

Flapping-wing systems, which are inspired by birds, have potential benefits over rotary-wing and fixed-wing drones. The flapping process generates less friction drag, which increases a drone’s speed and ability to maintain speed in harsh wind conditions [15]. Therefore, flapping-wing drones can navigate longer distances than rotary-wing drones and do not have as many dynamic constraints as fixed-wing drones [12]. However, there are many design challenges which affect the stability of this type of drones [7]. To benefit from the endurance of fixed-wing drones and the maneuverability of rotary-wing drones, hybrid models, such as tilt-rotor drones, have been more recently proposed for drone delivery applications [4]. Tilt-rotor drones have vertical takeoff and landing capabilities and can cruise at high speeds. However, there are design challenges related to transitioning between vertical and horizontal configurations [4]. Moreover, in real-world experiments, these hybrid drones have also been shown to have stability issues [16].

A detailed review of the different types of drones and design challenges can be found in [7]. More recently, reconfigurable drones have been gaining attention [17]. These drones adapt configurations during their flight to minimize the energy consumed by them. Such designs can be beneficial when trying to navigate in crowded and narrow spaces and can greatly improve the trajectory planning of drones.

3. Current Challenges

Apart from current regulations that prohibit drones’ operation beyond the visual line of sight, safety concerns in instances of mechanical failure, and drone navigation in a GPS-denied environment [18], there are other limitations that need to be considered when developing a practical path planning algorithm. In this section, we go over four major limitations: the limited battery capacity of drones, onboard computational capabilities of drones, extreme weather conditions, and dynamic environments.

3.1. Energy Constraints

Although rotary-wing drones are highly maneuverable and versatile, they are still limited in terms of endurance. Thus, a single rotary-wing drone cannot be used for missions requiring long flight distances. Many factors can affect the battery performance of drones. Many maneuvers, such as hovering, horizontal and vertical movements, payload, speed, and flying in the wind direction, can impact drones’ battery performance at varying levels [19]. In many studies, it is often assumed that drones can navigate through a computed path on a single charge. However, in practical settings, drones may often need to stop and recharge in order to navigate to their destination.

Improvements have been made to reduce the energy consumption of drones. The overall weight of rotary-wing drones has been reduced by using carbon-fiber airframes. There have also been improvements in brushless direct-current motors’ power-to-weight ratios, which contributes significantly to energy consumption [20]. Since there are weight constraints to drones, additional batteries or batteries with larger capacities cannot be placed on a drone to improve its endurance. In [21], it has been shown that there is an optimal value of mass on a rotorcraft. Increasing a drone’s weight after such a point begins to reduce the drone’s endurance and causes the drone to become unstable.

3.2. Onboard Computational Capabilities

For many tasks, such as autonomous navigation, vision processing, localization of a drone, and mapping of the environment, the onboard computer requires high processing power and battery capacity. However, due to weight restrictions, onboard computers placed on drones have limited resources and onboard computational power. There have been many studies dedicated toward developing a lightweight fault-tolerable computing platform for drones [22]. Many complex three-dimensional (3D) path planning algorithms and image processing algorithms cannot be processed directly onboard since they require high computational power. For example, in [11], the authors performing a pilot drone search and rescue operation with thermal cameras noted that they could not use a simple machine learning algorithm onboard due to computational limitations. Moreover, since the environment is continually changing, drones must rapidly compute a path to avoid a collision. Although an optimal solution in terms of path length is desirable to improve battery performance, such approaches often require heavy computations and a lot of time, which is not feasible for drones. Although technological advances are being made and drones are now able to handle more complex tasks through the use of onboard graphical processing units [23], the limited computational power should still be considered when developing path planning algorithms for drones.

3.3. Weather Conditions

An important factor to consider for drone path planning is the potential for navigating under extreme weather conditions. Although there are many improvements being made in the design of drones to make them more durable for such conditions [17], environments with precipitation, fog, and severe wind can have an adverse effect on a drone’s endurance, visibility, and sensors for navigation and collision avoidance [24]. Recently, there have been a few studies that have proposed solutions for such weather conditions. Some studies have proposed solutions where drones can evaluate risk and avoid regions that may have severe weather conditions when generating a path [25]. Others, such as in [26], suggest using the Euler method to perform a numerical analysis to predict the trajectory of drones under different kinds of wind conditions. In [27], the authors suggest tilting a drone based on different wind directions can significantly help reduce the deviation of the camera on the drone when tracking the movement of a ground object. Finally, for vision-based path planning algorithms which rely on cameras to avoid obstacles, fog can severely reduce visibility [28].

3.4. Dynamic Environments

Collision avoidance in environments that are consistently changing has been a challenge for path planning for ground, underwater, and aerial vehicles [29]. It is nearly impossible to obtain information about the entire environment prior to the takeoff of a drone. There can be stationary or moving objects that are placed after takeoff, which hinders the drone’s flight path. One area of research has been on developing better hardware to detect obstacles. There has been research focused on adding different types of sensors, such as LiDAR and ultrasonic sensors [30], to better detect obstacles during flight. Other studies have focused on how to incorporate such sensor data to avoid obstacles in real time. For example, in [8], the authors proposed using a Gaussian process occupancy map to predict the probability of there being a collision along the path using the sensor data that have been collected. Based on that information, the algorithm decides potential waypoints to include during its path generation. More recently, there have been more learning-based algorithms that have been suggested for navigation in dynamic environments [31,32,33,34]. These techniques generally do not need prior information about the environment to generate a path. They learn from prior actions taken by a drone to determine how to navigate in an unknown environment. Another recent challenge is coordinating multiple drones that are navigating in an unknown environment and ensuring that the drones do not collide with one another [35].

4. Drone Path Planning Problem

Although path planning has been extensively studied, there has yet to be a practical solution that addresses the energy constraints and onboard computational limitations of drones. To successfully deploy drones for commercial applications, drones must be able to avoid collisions and navigate to their destination efficiently. Therefore, we focus on analyzing various path planning techniques and provide insights into areas that need to be addressed when developing a path planning algorithm. Research into the path planning problem for drones has been growing since 2000. The number of published proceeding papers and articles related to path planning in the Web of Science database has been growing exponentially since 2000 (Figure 1). The majority of all published drone studies in the Web of Science Core Collection between 2000 and 2022 are related to the path planning problem. Computing the shortest path between two points in a 3D environment with polyhedral objects is NP-hard [36]. Thus, most drone path planning algorithms use heuristics and metaheuristics to generate a near-optimal path.

In this paper, the drone path planning problem refers to generating a minimum-cost and collision-free path between the start and the destination point. In many studies, the objective is to minimize total path length. However, some studies also minimize flight time [20], flight altitude [37], and drone speed [38].

Path planning algorithms can be categorized as either offline path planners or online (real-time) path planners. Offline path planners compute a path for a drone prior to takeoff. Thus, these path planners require information about the environment in advance. Information regarding obstacles and no-fly zones are made available to these path planners to generate an accurate path. An advantage of offline path planners is that they are able to employ models of drone dynamics to ensure that the path is feasible. However, these types of algorithms are not able to respond to changes in the environment dynamically. The environment is continually changing. Moving obstacles, such as birds, wind, and other aircraft, may hinder the original path, and a robust path planner must be able to re-compute a new path to avoid such obstacles.

Online path planners utilize sensor data to detect obstacles and, therefore, react to changes in the environment. However, online path planners are often not able to ensure that near-optimal paths are generated. Some online path planners function by generating an initial feasible path and modifying their path as dynamic obstacles are detected [8]. Other online path planners utilize probability functions to generate a path as new information regarding the environment becomes available [9]. Depending on the specific use case, one of these approaches may be beneficial over the other. For example, in drone delivery applications, the first approach would allow a drone to travel a relatively shorter overall distance than the second approach. However, in target tracking applications, pre-defined paths cannot be utilized. Therefore, a path planner must incrementally generate a path.

5. Path Planning Algorithms

In this section, we review algorithms that have been proposed in the literature for path planning. Path planning generally involves three main tasks: mapping the environment, applying an algorithm to generate an optimal path, and smoothing the path to make it feasible.

5.1. Environmental Representation

Before searching for a path, the search space must be mapped for an algorithm to understand the location of obstacles. Figure 2 summarizes some of the most commonly used techniques to represent an environment. Cell decomposition techniques have been extensively used in many studies [39,40,41]. An environment can be divided into a uniform grid (Figure 2a) with fixed-size cells or voxels to simplify the task of computing paths. Any cell containing a portion of an obstacle is marked as occluded, and any cell without an obstacle is marked as free. However, even if a small part of a particular cell contains an obstacle, the entire cell is marked as being occluded with these approaches. Although such approaches can determine whether there is a solution for any given input, in a finite amount of time, these approaches require a large amount of memory. They cannot function in real time to solve problems.

To mitigate the computationally intensive process of cell decomposition techniques, some studies have designed solutions using adaptive cell decomposition techniques [43], which limit the number of voxels used to generate a path. Adaptive cell decomposition techniques, such as quadtrees (Figure 2b), have been proposed to represent obstacle information accurately. There are more voxels (smaller in size) when close to an obstacle and fewer (larger in size) voxels when away from an obstacle. A modified adaptive cell decomposition method for 3D environments is suggested in [44], which reduces the amount of memory required to compute a path by continuously dividing a cell until the voxel size has reached a predefined fixed value. However, this approach may require a large amount of time in cluttered environments. More recently, in [45], the authors use a layered graph to effectively store the coordinates of obstacles. Since the number of layers created to store environmental information can be controlled, the amount of memory required to represent an environment can be bounded.

Voronoi diagrams (Figure 2d) have also been used to model an environment. This method involves partitioning a plane with a set of objects into convex polygons, where each polygon contains a single object. Any point in each polygon is closer to the object in its polygon than any other objects. Moreover, each point on the edge of the Voronoi diagram is equidistant from its two nearest neighbors. However, using the edges of a Voronoi diagram to generate a path may lead to sub-optimal solutions. Voronoi diagrams are often used to compute a path away from a threat or radar [46]. In recent studies, Voronoi diagrams have been constructed to improve the quality of path generated by other algorithms. For example, in [47], Voronoi diagrams were constructed to increase the convergence rate of a genetic algorithm by selecting members on the Voronoi vertices to be part of the initial population.

Visibility graphs can also be used to represent a search space. Visibility graphs function by adding nodes corresponding to the vertices of obstacles into a graph. Nodes in the graph are connected by an edge if the edge connecting the two nodes lie in an obstacle-free region (Figure 2c). Visibility graphs have been used extensively in 2D path planning because of their simplicity and because they can be used to compute global shortest paths for a point [48]. However, a large amount of time and memory is needed to generate visibility graphs in 3D, and only near-optimal solutions can be generated when only considering obstacle vertices. To address this issue, some studies have constructed reduced visibility graphs by using only a subset of obstacles in the environment [49,50,51,52]. Algorithms based on bounded energy space [50] and approximation with visibility line [51] reduce the number of obstacles by only considering obstacles in the straight path from the start to the destination point. However, such approaches can generate poor solutions (roughly 8% larger than the optimal path) and cannot guarantee that a solution will be found in complex environments with many obstacles [51]. Moreover, these algorithms have a high time complexity [52]. Other studies have transformed a 3D space into a 2D space to reduce the complexity of the problem [53,54]. Although there are limitations with using this approach for cluttered environments, in use cases where there are only a few obstacles, visibility graphs have been proven to be beneficial [55].

5.2. Path Generation

Many studies attempt to reduce the three-dimensional path planning problem to two dimensions [41,56]. By limiting the maneuvers of a drone to a horizontal plane (at a fixed altitude), the complexity of the problem can be significantly reduced, and algorithms proposed for other ground vehicles can be directly applied to drones. However, there are many benefits in utilizing the vertical translational movement of drones. One particular benefit is obstacle avoidance and navigation.

Many shortest-path algorithms have been suggested for drone path planning. After modeling the environment, Dijkstra’s algorithm [54,56] has been suggested to generate the shortest path for drones. Dijkstra’s algorithm determines the shortest paths from the start point to all vertices in a graph by iteratively traversing through all nodes and updating the distances to adjacent nodes. Although the implementation of Dijkstra’s algorithm can be optimized to perform quickly, in large environments where there are a lot of vertices in the graph, the A* algorithm is often desired. Since the A* algorithm focuses on searching for the shortest path toward the destination point, as opposed to the shortest path to every vertex in the graph, it has often been used for drone path planning [57,58]. As opposed to Dijkstra’s algorithm, the A* algorithm uses a heuristic h(u) when calculating the cost of a particular vertex in the graph. As long as the value of h(u) is lower than or equal to the actual distance of u to the destination point, the heuristic is considered admissible and can compute an optimal path. However, if the distance from u to the destination point is overestimated, then the A* algorithm cannot guarantee that an optimal solution will be computed. The value of h(u) can have an impact on the time complexity of the algorithm. Variations of the A* algorithm, such as the D* algorithm [40] and Theta* [57], have also been proposed for online path planning; however, such approaches may be slower than the A* algorithm due to the increase in the number of calculations.

Sampling-based path planning algorithms have been extensively studied due to their low computational complexity and ability to solve complex high-dimensional problems. Probabilistic road maps (PRMs) and rapidly exploring random trees (RRTs) [59] are common sampling-based path planning algorithms that compute a path using a set of randomly chosen points from the configuration space. PRMs can be inefficient when obstacle geometry is not known beforehand [60]. The original RRT algorithm generates solutions very rapidly in dynamic environments; however, its solutions are not optimal. The RRT* algorithm [61] was later proposed to improve the RRT algorithm by using nearest neighbors to refine the overall path. The RRT* algorithm has been proven to be asymptotically optimal. Thus, the cost of the path will almost surely converge to the optimum. However, the convergence rate at which the algorithm reaches the optimal solution is very slow. Although the RRT* algorithm can compute optimal paths, the slow convergence rate makes it unsuitable for real-time applications, such as drone path planning. Many variants of the RRT and RRT* algorithms have been proposed to improve the rate at which these algorithms converge to an optimal solution [60,61]. RRT- and RRT*-based solutions have been commonly proposed for drone path planning [8,9,10,62,63,64]. Many studies use RRTs for online path planning where sensors are used to detect either stationary or moving obstacles, and RRTs are used since they are effective at re-planning paths [8,9,10]. Other studies have attempted to integrate RRTs with other path planning techniques, such as potential fields [62] and particle swarm optimization [63]. Some studies target fixed-wing drones and only sample points that satisfy a minimum turning radius [64]. A limitation with attempting to generate an optimal path with RRT-based approaches is that if a path does not exist (there is no solution), the algorithm may run infinitely.

Artificial potential fields have also been proposed for path planning in 3D environments [38,62,65]. A gravitational field of attraction is placed around the destination, and repulsive forces are placed around the obstacles. The combination of potentials creates a force field, which is then used to guide the drone toward the destination while avoiding the obstacles. A major issue with potential fields is that they can easily converge to a local minimum due to location, geometry of obstacles, and large environments. Once a drone is trapped at a local minimum, it can no longer reach its destination point. Moreover, artificial potential fields cannot guarantee that the resulting path is optimal [38]. Several approaches have been proposed to solve these issues. In [38], the problem is converted into an optimization problem and solved using an optimal control method to successfully move a vehicle out of traps. In [66], a pre-determined or randomly selected guided point is introduced to allow a UAV to continue searching for the destination when it reaches a local minimum. Artificial potential fields have been demonstrated on a network of micro-drones to successfully avoid obstacles while maintaining formation [62].

Many metaheuristic algorithms based on biological models have also been proposed as solutions to the path planning problem. Genetic algorithms [67,68,69], ant colony optimization (ACO) [70,71,72], particle swarm optimization (PSO) [63,73], fruit fly optimization [74,75], wolf pack search [76], and differential evolution [37] are all examples of such evolutionary algorithms, which use bio-inspired properties for optimization. Figure 3 depicts the general structure of an evolutionary algorithm. Generally, in evolutionary algorithms, the initial population is randomly generated. In the case of genetic algorithms, solutions are altered (mutated) such that the fittest solution, based on an objective function, is chosen for the next generation. In other algorithms such as PSO, the particles’ positions in the environment are updated based on their individual best known position and the population’s best known position.

A limitation with genetic algorithms is that they can be computationally expensive. However, implementing a genetic algorithm on field-programmable gate arrays (FPGA) and GPUs has been shown to quickly generate feasible solutions in small environments [67,68]. Another major limitation with evolutionary algorithms in general is premature convergence. To overcome this issue, increasing the diversity of the population through periodic mutation applications has resulted in fast convergence for genetic algorithms [69]. Moreover, combining PSO with an adaptive decision operator has helped overcome premature convergence [73]. This improved PSO is able to generate solutions that are superior to the original genetic algorithm, PSO, and firefly algorithms. To resolve the local minimum and premature convergence in ACO algorithms, adding a disturbance by applying a particular chaos factor has shown to work [72]. The use of multiple colonies that communicate with each other [47] has also been shown to improve the quality of the solution generated by an ACO algorithm.

More recently, learning-based methods have been suggested for drone path planning [31,32]. Reinforcement learning can be used to make sequential decisions. Thus, information about the environment does not necessarily need to be made available [32]. When discussing reinforcement learning, an agent makes a decision based on current and past experiences. The objective is to maximize the reward value and learn an optimal policy quickly. A policy refers to the agent’s actions. In other words, it determines how the agent reacts in different situations and which actions to take. An adaptive and random exploration approach based on Q-learning has been proposed for drones to navigate and avoid obstacles in real time [31]. During path planning, there is a learning module that derives a strategy for action by looking at historical data and action of a drone. In [32], the classical Q-learning algorithm is improved by adding an artificial potential field to avoid local minima, improve convergence rate, and navigate in dynamic environments. However, these approaches may be computationally expensive in large environments since environments are represented as grids.

The use of deep learning with reinforcement learning (DRL) has been gaining interest after much success in other applications, such as video games. DRL uses deep learning concepts with reinforcement learning to give an optimal solution based on its experiences [78]. A detailed description of deep learning, reinforcement learning, DRL, and various classifications of deep learning reinforcement can be found in [78]. There have been more map-less online solutions proposed using DRL for autonomous navigation. For example, in [34], the authors suggest fusing multiple sensory data using an end-to-end convolutional neural network to control the motion and direction of a drone. Although the drone is only navigating on a 2D plane, the simulation and implementation on a physical drone successfully show that the drone would be able to avoid obstacles in a dynamic environment. Deep deterministic policy gradient (DDPG) is another approach based on the actor–critic method. The actor in this scenario chooses an action to perform in a continuous space, and the critic evaluates the advantages and disadvantages of the current strategy. In [79], the authors use a DDPG-based approach where a UAV determines a trajectory to reach a dynamic destination within a continuous space. However, the drone only reaches its destination without colliding into an obstacle in 82% to 84% of the time.

Other approaches using control theory have also been suggested [71,80,81,82]. In [71], the authors suggest that a Markov decision process can be used to plan an energy-efficient path based on the uncertainty of a Gaussian distribution, which is used to determine the uncertainty in wind fields. Model predictive control (MPC) is another model used to control a drone’s path planning while satisfying a set of constraints. In [83], the authors use MPC for controlling the trajectory of a drone with respect to a reference trajectory. MPC has been shown to generate trajectories for drones using limited computational resources. However, it does not scale well when there is a central MPC for an increasing number of drones [80]. In [82], the authors used a distributed MPC as part of an online planner to generate paths for a swarm of drones. The authors suggest offloading the path planning computation to computational units on the ground and using the distributed MPC to select a subset of the most relevant drone trajectories to be replanned.

6. Analysis

6.1. Analysis of Recent Studies

For this review, path planning papers were retrieved from the Web of Science database. Highly cited studies between 2010 and 2022 were investigated. Preference was given to more recent studies. Since we were mainly interested in path planning algorithms for commercial applications, we did not investigate coverage path planning algorithms or target tracking path planning algorithms. Coverage path planning algorithms are necessary for applications such as search and rescue and surveillance, which require a drone to compute the best path to traverse the entire environment. We analyzed 35 different studies and summarized the results in

Table 1. Analysis of 35 published drone path planning papers.

Ref	3D	Energy Constraints	Path Optimization	Drone Type (F/R/N)	Path Planner (ON/OFF)	Obstacle Type (MV/ST)	Environment Type (S/M/L)	Computer Simulations	Practical Implementation (I/O)	Algorithm Category
[37]	✓	✗	✓	F	OFF	ST	S	✓	✗	BA
[47]	✗	✗	✗	R	OFF	ST	S	✓	✗	BA
[71]	✗	✗	✗	N	OFF	ST	S	✓	✗	BA
[69]	✓	✗	✓	F	OFF	ST	S	✓	✗	BA
[73]	✗	✗	✓	N	OFF	ST	S	✓	✗	BA
[74]	✓	✗	✗	N	OFF	ST	S	✓	✗	BA
[70]	✓	✗	✓	N	OFF	ST	M	✓	✗	BA
[75]	✓	✗	✓	N	OFF	ST	S	✓	✗	BA
[77]	✓	✗	✓	R + F	OFF	ST	S	✓	✗	BA
[76]	✓	✗	✓	N	OFF	ST	S	✓	✗	BA
[84]	✓	✗	✓	N	OFF	ST	M	✓	✗	BA
[85]	✓	✗	✓	N	OFF	ST	S	✓	✗	BA
[40]	✓	✗	✗	R	ON	ST/MV	M	✓	✗	GS
[57]	✓	✗	✗	N	OFF	ST	S	✓	✗	GS
[58]	✗	✗	✓	R	ON	ST/MV	S	✓	✗	GS
[86]	✓	✗	✓	N	OFF	ST	S	✓	✗	GS
[31]	✗	✗	✗	F	ON	ST	S	✓	✗	LA
[32]	✗	✗	✗	N	ON	ST	S	✓	✗	LA
[33]	✗	✗	✗	N	ON	ST/MV	S	✓	✗	LA
[34]	✓	✗	✗	R	ON	ST	S	✓	O	LA
[87]	✓	✗	✗	R	ON	ST	S	✓	✗	LA
[79]	✓	✗	✗	R	ON	ST	S	✓	✗	LA
[72]	✗	✓	✓	F	ON	ST	S	✓	✗	OT
[88]	✓	✗	✓	R	OFF	ST	S	✓	✗	OT
[89]	✗	✗	✗	F	OFF	ST	S	✓	✗	OT
[38]	✓	✓	✗	R	OFF	ST	S	✓	✗	PF
[66]	✓	✗	✗	R	OFF	ST	S	✓	O	PF
[8]	✓	✗	✓	R	ON	ST/MV	S	✓	I	SBA
[9]	✓	✗	✓	R	ON	ST	M	✓	✗	SBA
[10]	✓	✗	✓	R	ON	MV	S	✓	I	SBA
[64]	✓	✗	✓	F	OFF	ST	S	✓	✗	SBA
[63]	✓	✗	✓	N	ON	ST	M	✓	✗	SBA
[62]	✗	✗	✗	N	OFF	ST	M	✓	✗	SBA
[35]	✓	✗	✓	N	ON	ST/MV	M	✓	✗	SBA
[90]	✓	✗	✓	R	OFF	ST	M	✓	I	SBA

.

The critical review of drone path planning papers was based on the following criteria:

• Dimension: Studies included the spatial dimension for which the path planning algorithm was proposed. The algorithm was either suggested for 2D or 3D environments.
• Energy Constraints: Studies analyzed factors other than path length in their cost function. Various factors, such as payload, weight, wind, motor thrust, drone maneuvers, can affect the battery performance of drones [19].
• Path Optimization: Flight trajectory is important, particularly for fixed-wing drones. Since fixed-wing drones have limited turning angles, often Dubins curves or Bezier curves are used to ensure the path is feasible. Path smoothening techniques have also been applied to rotary-wing drones to allow for continuous motion and prevent the drone from having to come to a complete stop.
• Drone Type: Fixed-wing drones (F), rotary-wing drones (R), or the paper did not specify which type of drone the algorithm was intended for (N).
• Path Planner: The algorithm was developed as an online path planner to compute paths in real time (ON) or as an offline path planner (OFF).
• Obstacle Type: The algorithm can generate a path in an environment with stationary obstacles (ST) or moving obstacles (MV).
• Environment Type: Type of environment used for testing. We defined a small-sized environment as having 0–50 obstacles (S), a medium-sized environment as having 51–500 obstacles (M), and a large-sized environment as having more than 500 obstacles (L).
• Computer Simulations: Studies indicated whether computer simulations were used to validate the algorithm.
• Drone Implementation: Studies indicated whether the algorithm was tested on physical drones in an indoor (I) or outdoor (O) setting.
• Algorithm Category: We categorized the approach taken as either bio-inspired algorithm (BA), graph search (GS), learning algorithm (LA), other (OT), potential fields (PF), or sampling-based algorithm (SBA).

6.2. Future Directions

Although some of the proposed algorithms have great potential to be used as path planners for autonomous drones, limitations exist in terms of the quality of the solutions that they produce and the required computational resources. Many different factors need to be considered before an autonomous drone can use a path planner. In this section, we review current research trends and improvements that can be performed in the future to develop a robust path planner for drones.

Many path planning algorithms for ground vehicles have been applied to drones [29]. Initially, these algorithms were applied to drones by modeling the environment in two dimensions. However, as shown in Table 1, the majority of the studies (especially more recent studies) have developed 3D drone path planning solutions. Unlike ground vehicles, drones have the ability to navigate over objects. Consequently, path planners may be able to generate more optimal solutions. Moreover, not all 2D path planning algorithms can be easily applied in three dimensions. Three-dimensional path planning can be much more complex and requires more time to generate a solution [91].

The majority of the studies we reviewed optimized their path based on time or distance. Although the goal of a path planner should be to navigate a drone to its destination point as quickly as possible, as discussed earlier, different drone maneuvers, a drone’s payload, and its wind speed can all impact the drone’s battery performance at varying levels. Therefore, a drone may not have the battery capacity to navigate the generated paths based solely on optimizing distance and speed. To address this issue, some studies have developed a power consumption estimation model [92] to detect battery levels and re-route drones to a charging station when necessary. Some studies that we reviewed considered motor thrust [38] and wind energy [72] to improve the energy consumption of drones. In the future, it would be beneficial if studies consider the limited battery capacity of drones when developing algorithms. Different factors, such as changes in altitude or number of times a drone needs to alter its flight direction, can also be considered when developing a potential solution.

Previously, since path planning algorithms were developed for combat operations, many studies focused on developing solutions for fixed-wing drones. However, in recent years, many studies have been developing solutions for rotary-wing drones due to their maneuverability and ability to hover. Although the design of flapping-wing drones has been well studied, there have not been a lot of studies that use such drones for path planning experiments. The limited availability of flapping-wing drones and reconfigurable drones may also potentially be a reason for the limited number of studies using such designed drones. In the future, studies may benefit by using hybrid vertical take off and landing drones [17] for path planning. Such drones have the ability to hover when necessary and navigate longer distances than rotary-wing drones.

From the reviewed studies, the most commonly applied algorithms for the drone path planning problem are bio-inspired algorithms and sampling-based algorithms (particularly RRT-based approaches), as shown in Figure 4. Although many studies have previously used graph-search-based approaches, only limited studies have used such approaches for online path planning. This may be due to the high computational power requirements for such algorithms. More recently, especially for the online path planning problem, learning-based algorithms have shown moderate experimental success in dynamic environments. However, in the future, studies should focus on testing in environments with stationary and moving dynamic objects to simulate real-world conditions. From the reviewed studies, less than 20% of the studies considered moving objects when testing their algorithm, and the majority of the studies did not implement their solution on a physical drone and did not test in real-world conditions.

In cluttered urban environments where drones would navigate autonomously for commercial applications, there can be thousands of obstacles of varying sizes. In the majority of the studies that we reviewed, the proposed approach was only tested in small environments with fewer than 50 obstacles in their simulations. When testing the robustness of a path planner, obstacles should be placed randomly. Similar to the approach taken in [45], obstacles of varying widths and heights should be used to determine how long it takes for a path planner to generate a path and the overall quality of the path generated.

Trajectory generation is another area of research that has been gaining a lot of interest. Although we have reviewed multiple methods to generate a path, there are challenges in having a drone follow a computed flight path smoothly. For instance, Figure 5 shows the trajectories generated by four different flight control systems (FCS) for a quadrotor drone. As shown in the figure, different FCS can track the reference trajectory; however, when there is a disturbance (such as wind gusts), it can affect the controller’s ability maintain the drone’s position. The control problem involves generating a controller which can maintain the position and altitude of the drone, which is essential for deploying autonomous drones. Convergence time, ability to adapt to disturbances, and control precision are all required for a robust flight controller [93]. Proportional–integral–derivative (PID) controllers have been suggested for drone trajectory tracking [94]; however, they are sensitive to disturbances and nonlinear systems. Other studies have suggested using variable structure control to develop more robust controllers [93]. Computer simulations of the trajectory of a drone along the generated path can provide an idea of the effectiveness of a path planner; however, there may be challenges when trying to test it in the real world. In many of the studies, the details regarding the platform on which the simulation was run is not provided. Therefore, an algorithm may perform as expected when it has the available computational resources and power, but it may not be a feasible solution when applying it to a drone with fewer resources available. Although there are mathematical models that can be used to simulate the dynamics of drones, more studies in the future need to implement their algorithm on physical drones in real-world environments for validation. In some of the studies we reviewed, the algorithms were validated in indoor environments with a few obstacles [8] and in outdoor environments [34,66]. However, a drone does not generate smooth trajectories or is prone to disturbances. There has been some progress in developing a flight controller that can effectively reject disturbances [93]. However, further studies are required to determine flight controllers’ efficacy in navigating in complex, cluttered environments.

Lastly, from the reviewed studies, about half of the studies did not compare the effectiveness of their algorithm to another path planning algorithm. A detailed comparative study that compares multiple types of algorithms based on memory consumption, running time, and path cost is necessary. Moreover, a comparative analysis should include algorithms from multiple categories. In [96], the authors performed a comparative analysis of RRT-based path planning algorithms. In another recent comparative study, the authors compared a graph-search-based algorithm with a sampling-based algorithm [97]. However, a more comprehensive comparison with many more algorithms in a real-world setting is crucial to determine how viable a solution can be for practical purposes.

Recently, there have been a lot of studies focusing on utilizing groups of drones [35,83,98], especially for optimal coverage path planning algorithms. However, this also introduces other challenges, such as communication, task allocation, and control. In [81], the authors suggested having a network of drones complete portions of a task. The objective was to minimize the total distance travelled by the drones to address the energy limitation of these drones. However, this study did not focus on the simultaneous deployment of drones for tasks. The use of multiple drones can be beneficial for applications where a drone needs to navigate large areas. Examples include disaster recovery, traffic monitoring, and search and rescue operations. In the future, studies optimizing coverage path planning algorithms can focus on approaches to improve the simultaneous deployment of drones for tasks.

There are many other interconnected areas of research where improvements are required to use autonomous drones for commercial operations. In this review, we focus on path planning. However, privacy and security are a major concern during the autonomous navigation of drones [99]. As described in [99], many studies have focused on vulnerabilities in drone communication. Some studies have suggested a blockchain framework to secure data collection and communication within a drone network [98]. Moreover, communications between drones and between a drone and a ground station are also critical during missions. As shown in [100], cellularly connected drones can work together using a RL-based framework to generate an energy-efficient path and minimize the interference they cause on ground networks, as well as on their wireless transmission latency.

7. Conclusions

Developing a computationally inexpensive, efficient, and robust path planner for drones can be challenging. In this review, we explore various drone path planning algorithms in recent literature. We highlight the limitations of these commonly used path planning algorithms and explore some of the suggestions in the literature to overcome these issues. Moreover, we provide insight into various factors that should be considered when developing a path planner for autonomous drones in the future. For example, factors affecting the battery performance of drones, including payload, communication, and motor thrust, need to be considered when computing a path for an autonomous drone. Moreover, to make algorithms more practical for commercial applications, future studies should develop path planners that are able to dynamically respond to changes in 3D environments. Finally, although the majority of the reviewed studies validated their algorithm using computer simulations, future studies should implement and test their algorithm in realistic environments.