Novel Energy-Aware 3D UAV Path Planning and Collision Avoidance Using Receding Horizon and Optimization-Based Control

Abstract

Unmanned Aerial Vehicles (UAVs) have gained significant popularity in recent years thanks to their agility, mobility, and cost-effectiveness. However, UAV navigation presents several challenges, particularly in path planning, which requires determining an optimal route while avoiding obstacles and adhering to various constraints. Another critical challenge is the limited flight time imposed by the onboard battery. This paper introduces a novel approach for energy-efficient three-dimensional online path planning for UAV formations operating in complex environments. We formulate the path planning problem as a minimization optimization problem, and employ Mixed-Integer Linear Programming (MILP) to achieve optimal solutions. The cost function is designed to minimize energy consumption while considering the inter-collision and intra-collision avoidance constraints within a limited detection range. To achieve this, an optimization approach incorporating Receding Horizon Control (RHC) is applied. The entire path is divided into segments or sub-paths, with constraints used to avoid collisions with obstacles and other members of the fleet. The proposed optimization approach enables fast navigation through dense environments and ensures a collision-free path for all UAVs. A path-smoothing strategy is proposed to further reduce energy consumption caused by sharp turns. The results demonstrate the effectiveness and accuracy of the proposed approach in dense environments with high risk of collision. We compared our proposed approach against recent works, and the results illustrate that the proposed approach outperforms others in terms of UAV formation, number of collisions, and partial path generation time.

1. Introduction

Thanks to technological advancements, Unmanned Aerial Vehicles (UAVs) have acquired considerable attention. UAVs provide many notable features, including additional degrees of freedom and flexible deployment [1]. Consequently, they have been utilized in various applications in military and commercial applications, including traffic policing and control, area coverage, aerial surveillance, disaster management, precision agriculture, and search-and-rescue operations [2,3,4,5]. However, many of these applications exceed the capabilities of single UAVs due to limited sensing range, communication bandwidth, and energy constraints [6].

The use of multiple UAVs offers significant advantages such as reducing operational time and improving the robustness of path planning. However, this benefit comes with increased complexity due to the need to consider numerous constraints in path planning [7].

In this case, the demands of more sophisticated tasks often require a sophisticated path planning approach in order for UAVs to accomplish their tasks efficiently and safely. To meet the growing complexity of such applications, the development of strong robustness and high parallelism algorithms and technologies in multiple UAVs is necessary in order to enable real-time decision-making, obstacle avoidance, and path optimization, ensuring that UAVs can navigate dynamic environments effectively [8,9].

Path planning is a critical component of UAV operations and is essential for the successful execution of missions [10]. It involves identifying the optimal route for navigating towards a destination and efficiently achieving the specified objectives [11]. Path planning offers several advantages, including reduced need for human intervention, improved time and cost efficiency, optimized resource usage, and enhanced data collection and analysis capabilities. As a result, it is a valuable tool across a wide range of applications, from environmental monitoring and search and rescue to industrial automation and agriculture. However, solving the multiple-UAV path planning problem is computationally challenging, as it is classified as NP-hard [12,13]. For this reason, developing an effective strategy for multi-UAV path planning becomes particularly challenging in large-scale environments [14,15].

Currently, providing UAVs with the ability to plan collision-free paths in real time while navigating through unknown environments remains a difficult task. These environments pose difficulties because the UAVs lack information about their surroundings and because conditions are subject to constant change. Therefore, UAVs must possess the capability to perceive their environment, make decisions, and take appropriate actions while also being able to explore and acquire knowledge. Consequently, it is important to develop a methodology that can autonomously navigate and plan paths in unknown environments [16,17].

The commonly used mathematical formulation for UAV path planning problem is typically expressed as an optimization problem in which the objective functions include energy consumption, minimum delivery cost and maximum overall customer satisfaction [18], path length, and any required constraints. The next step involves using optimization calculations to determine the optimal values of these functions. Various mathematical programming algorithms, including Nonlinear Programming (NP) [19], Mixed-Integer Programming (MIP) [20], Markov decision processes [21], and Dynamic Programming (DP) [22], are commonly used in this context. These approaches have been shown to outperform approximate solution strategies based on Particle Swarm Optimization (PSO), Genetic Algorithms (GAs), and Ant Colony (AC) algorithms.

MILP can be used to address problems with multiple tasks and constraints, including UAV path planning problem. Such problems can be represented as an MILP model, highlighting the flexibility of MILP optimization in effectively addressing the complexities of UAV path planning. Various constraints have been effectively addressed using MILP in diverse applications [23,24,25,26,27]. For instance, exact optimization methods such as branch and bound and dynamic programming represent effective techniques for handling the path planning problem by developing MILP formulations and solving the problem in a short interval and within the UAV’s Field of View (FoV).

For online path planning, Receding Horizon Control (RHC) offers significant advantages in incorporating mobility and environmental constraints such as obstacles as well as constraints arising from formation relationships such as changing formation shapes. Furthermore, RHC enables a suitable level of cognitive ability through frequent replanning and adaptation to dynamic environments [28].

Despite advancements in UAV path planning, several critical challenges remain unresolved, particularly in dynamic and obstacle-dense environments. While some approaches offer solutions for path planning, they often fail to sufficiently address energy consumption, which is a vital factor for UAVs with limited battery capacity during long missions. Additionally, real-time path adjustments in highly dynamic environments remain a significant hurdle, as many existing algorithms either lack the ability to adapt in real-time or require excessive computational resources. Moreover, although various methods provide basic collision avoidance, they frequently fall short in ensuring safety, especially in environments with unpredictable moving obstacles. This is particularly problematic in densely populated areas, where collisions are difficult to avoid without precise real-time adjustment.

This research paper focuses on the development of a novel approach for guiding a fleet of UAVs through an obstacle-filled environment. The proposed approach tackles the problem of path planning by utilizing MILP, which determines the energy-efficient waypoints for UAVs. Then, the CPLEX solver is applied to obtain the exact solution for the MILP formulation. The concept of a dynamic finite horizon is implemented to solve the MILP formulation within a local spatial region that continuously updates as the UAVs progress along their paths. To minimize energy consumption, a cost function is proposed that incorporates problem constraints. The UAVs aim to reach the desired destinations while minimizing their energy consumption. The constraints of maintaining collision avoidance are imposed on UAVs throughout the entire flight duration to ensure navigation from the initial point to the final points while minimizing the cost function. Notably, we apply the energy model from [29], which was derived from real experiments that considered different maneuvering activities such as horizontal flight, vertical flight, hovering in place, turning.

The contributions of this paper are listed below:

• We present an energy-aware path planning algorithm for multiple UAVs that incorporates collision avoidance for obstacles and between UAVs. The concept of a dynamic finite horizon is implemented to solve the MILP formulation within a local spatial region, continuously updating the UAVs’ locations as they progress along their respective paths.
• The constraints for the path planning problem are derived and thoroughly analyzed with the aim of minimizing overall energy consumption. An MILP-based formulation is then developed to determine the optimal trajectories for all UAVs, guiding them from their starting locations to their destinations while adhering to all specified constraints.
• We propose a safety strategy to guarantee collision avoidance in dense and highly dynamic environments.
• A smoothing strategy is applied to the generated paths to enable smoother turns, thereby reducing energy consumption.

The rest of this paper is structured as follows: Section 2 provides a literature review; in Section 3, we introduce our proposed energy-efficient UAV path planning approach addressing collision avoidance, present the MILP-based problem formulation, and include a detailed discussion and analysis of the optimization problem alongside our proposed path smoothing strategy; Section 4 presents the results and corresponding analysis; finally, our conclusions are provided in Section 5.

2. Literature Review

Currently, real-time online UAV path planning in unknown environments with collision avoidance is a challenging task. These environments pose a challenge because the UAVs lack information about their surroundings and the conditions are prone to constant changes. Therefore, the UAVs need to be able to perceive their environment, make decisions, and take appropriate actions while also being able to explore and acquire knowledge. Consequently, it is important to develop a methodology that allows UAVs autonomously navigate and plan paths in unknown environments. A number of previous works have addressed UAV path planning. This section reviews some of the literature on UAV path planning.

The work in [30] presented an algorithm that combines model predictive control and a genetic algorithm to enable cooperative searching of unknown areas by multiple UAVs. By incorporating the strengths of both genetic algorithms and MPC, this algorithm aims to overcome the issue of local optima. The genetic algorithm provides flexibility and exploration capabilities, while MPC contributes predictive abilities that enhance the overall search performance in unknown environments. However, employing a genetic algorithm for online path planning is often impractical, as the time-intensive nature of GAs can hinder real-time decision-making and responsiveness in dynamic environments.

In [31], the authors proposed a trajectory planner for cooperative UAVs using B-spline curves, potential fields, and differential evolution to avoid collisions with obstacles and generate smooth trajectories in both known and unknown static environments. However, as this approach is restricted to static environment, it cannot be applied in dynamic contexts.

The work introduced in [32] proposed formation control of mobile robots combining model predictive control and particle swarm optimization. The aim was to achieve stable and collision-free formation control while reducing computational complexity. However, it was only applied in a 2D environment. Moreover, employing particle swarm optimization for online path planning is often impractical due its time-intensive operation, which can hinder real-time decision-making and responsiveness in dynamic environments.

The work described in [33] allows for the maintenance of formations with varying shapes over time. However, it is restricted to flat environments with no obstacles, and its testing was limited to simple circular trajectories.

In [34], the authors proposed a planning and control framework for UAV formation using the A* algorithm. In [35], the A* algorithm was replaced with PSO and spline-path planning, resulting in better paths. However, this approach is primarily adapted to 2D scenarios, and offers limited guidance for extension to 3D environments. Moreover, employing particle swarm optimization for online path planning is often time-intensive, which can hinder real-time decision-making and responsiveness in dynamic environments. In [36], A* was replaced by the Fast Marching Method (FMM) in a practical maritime environment. However, as this method is primarily adapted to 2D scenarios, it offers limited guidance for extension to 3D environments.

The work in [37] proposed the Multi-Strategy Improved Sand Cat Swarm Optimization Algorithm as an improved approach to Sand Cat Swarm Optimization for UAV trajectory planning, addressing the limitations of existing algorithms and demonstrating its effectiveness through experimental results.

The work in [38] proposed utilizing turn angles for safe navigation and avoiding collisions among multiple collaborating robots. The paths were optimized to minimize energy consumption and mission duration while avoiding collisions. However, this approach is primarily adapted to 2D scenarios, and offers limited guidance for extension to 3D environments.

In [39], the UAV path optimization problem was formulated via MILP and solved using the CPLEX solver. In [40], the UAV path planning problem was formulated as a maximization optimization problem based on MILP, with target tracking performance as the goal to be maximized. In [27], an MILP formulation was used to address the maximization of coverage and monitoring time to ensure continuous monitoring by UAVs at any given time.

The work in [41] proposed a lightweight real-time path planning method for UAVs based on reinforcement learning. The goal of was to solve UAV path planning in complex urban environments while addressing constraints such as limited computational resources and real-time responsiveness.

In [42], the use of reinforcement learning in path planning for autonomous UAVs operating Beyond Visual Line-of-Sight (BVLOS) in dynamic environments was explored. This study aimed to develop a navigation system allowing UAVs to autonomously navigate through unknown environments while avoiding obstacles. The authors utilized the Advantage Actor–Critic (A2C) algorithm, which is a model-free RL method, to guide the UAV from a starting point to a target using input from limited sensors while avoiding collisions.

The authors of [43] introduced a dynamically constructed graph that limits agents to local planning actions. Although this can enhance path exploration, the approach cannot be applied to real robots due to challenges related to localization and perception uncertainties.

The study in [44] combined a traditional collision avoidance technique with a Deep Reinforcement Learning (DRL) approach to enable effective long-term trajectory planning in the presence of unknown obstacles.

Although there have been many notable works in the literature regarding collision avoidance and path planning for UAVs, some of these studies focus only on single UAVs, while others primarily focus on avoiding static obstacles in 2D environments and neglect 3D environments. Furthermore, many works that consider both static and dynamic obstacles deal with only simple scenarios involving very light obstruction in large environments where the probability of a collision is very low. Such approaches cannot be apply in complex and highly dense environments. Although reinforcement learning approaches have introduced online path navigation in real time, they demand significant training time and face scalability challenges in resource-constrained environments. Moreover, most existing works do not consider energy consumption in the context of formation flight, which is crucial for long-duration UAV operations. In contrast, our method is explicitly designed to minimize energy consumption through the proposed MILP formulation, allowing us to simultaneously optimize not just for collision avoidance but also for energy-efficient UAV operation.

Thus, to address the aforementioned limitations of existing research, we propose an online energy-aware path planning strategy for formation flight that allows UAVs to operate effectively even in highly dense and dynamic environments while ensuring collision-free paths for the UAV formation and simultaneously minimizing energy consumption.

3. Description of Energy-Aware Trajectory Planning for UAVs

The objective of our proposed path planning technique is to reduce energy consumption while ensuring collision avoidance. The approach proposed in this study offers a promising solution for achieving energy-efficient operation and extending the flight duration of UAVs. The concept behind the RHC method is to create a moving time window at each sampling interval, solve the the path planning problem to obtain the optimal solution within that window, and then shift the window forward based on a predefined time step. Its real-time capabilities and optimization provide significant advantages in an online path planning. Moreover, a finite horizon can be employed to restrict the area around the UAV. This finite horizon is designed to be sufficiently large to allow the UAV to maneuver and avoid collisions while keeping the computation time manageable. The duration required for collision avoidance depends on the UAV’s velocity and the predicted collision position. Figure 1 shows a schematic diagram of a UAV path through an environment filled by obstacles. In the figure, the horizon is defined by the UAV’s FoV (the square area).

The specific procedure for each UAV is described in Algorithm 1, which has the following steps:

• Step 1: At sampling time $t_0$, initialize the UAVs and environment information and construct the rolling time window $T_w$. The environment information involves the size of segment for which paths and obstacles are to be planned.
• Step 2: Decompose the segment area represented by each UAV’s FoV into cells. Then, formulate the path planning within the segment as a minimization optimization problem based on an MILP and apply the optimization objective function for minimum energy consumption.
• Step 3: Solve the problem using an optimization solver (CPLEX solver) and find the optimal path that minimizes energy consumption while meeting all constraints.
• Step 4: Smooth the generated path and update the UAV locations and information on the environment.
• Step 5: In the next sampling, repeat Steps 2–4 until the destination is reached.

Algorithm 1: Energy-Aware UAV Path Planning Algorithm

Figure 2 illustrates the the proposed approach with a block diagram. The following subsections explain the different parts of the proposed approach in detail.

The different symbols used in this study are defined in

Table 1. Symbol definitions.

Symbol	Description
$N_p$	Number of possible locations in the segment defined by the UAV’s FoV
$x_{s_{\min }},x_{s_{\max }}$	Represent the x-boundary of the segment within the UAV’s FoV
$y_{s_{\min }},y_{s_{\max }}$	Represent the y-boundary of the segment within the UAV’s FoV
$S{D}_{\min }$	Minimum safety distance from obstacles
$N_d$	Number of UAVs
$N_{\mathrm{obs}}$	Number of obstacles
$E_u$	Available energy for UAV u
$E_{ij}$	Energy used to travel from position i to position j
$MDTO$	Minimum distance to dynamic obstacles
$DT$	Duration time to generate a partial path within the UAV’s FoV
$NoCs$	Number of collisions during the mission

.

3.1. Collision Avoidance Module

To avoid obstacles, we consider a safety margin around the obstacle, as in [45,46]. The obstacle constraints can be represented by penalizing the path by a high value if it passes through obstacles. This module is responsible for formulating the constraints related to collisions with obstacles as well as with other members of the UAV fleet. The module is integrated into the MILP formulation while enforcing constraints to guarantee safe navigation. A safety margin around each obstacle ensures that the UAVs maintain minimum safe distance from obstacles while navigating. This module penalizes any path that collides with obstacles, effectively steering the UAVs away from obstacles. The constraint for obstacle avoidance is mathematically expressed by the problem constraints in Equation (1)e.

This module also handles collisions between UAVs operating in the same space. To prevent UAVs from approaching each other too closely, the module enforces a minimum separation distance $S{D}_{min}$ between any two UAVs. This ensures that the UAV fleet operates safely in a coordinated manner without risking inter-UAV collisions. The constraint for UAV-to-UAV collision avoidance is mathematically expressed by the problem constraints in Equation (1)d.

3.2. MILP Solution Module

This module receives the objective and constraints, then formulates the problem through the following parts.

3.2.1. Segment Area Decomposition

The given segment area is decomposed to generate all possible waypoints using the region decomposition technique. The required waypoints are incorporated into the MILP formulation as constraints. The path planning problem is then formulated as a minimization problem with the aim of reducing energy consumption as much as possible. It has to be stressed that the endpoint within a segment is the closest point to the actual destination. Finally, the problem is solved using the CPLEX solver and the collision-free path is generated. For more information about the segmentation process, we refer the reader to [46].

3.2.2. MILP-Based Formulation

The objective is to navigate through a dense environment in order to deliver the UAVs to the destination safely and with high energy efficiency.

Let $N_p$ be the number of possible locations in the segment defined by the UAV’s FoV; in addition, $N_{obs}$ indicates the number of obstacles, $N_d$ refers to the number of UAVs, Eu represents the available energy for UAV u, and $E_{ij}$ denotes the energy used to travel from position i to position j.

The decision variables of the target path planning problem are inspired by the classical MILP formulation. The collision decision variable $O{C}_{ij}$ is the cost of collision with obstacles, and can be written as follows:

$$O{C}_{ij}=\left\{\begin{array}{cc}inf\hfill & \mathrm{if}\mathrm{the}\mathrm{path}\mathrm{from}positio{n}_i\mathrm{and}positio{n}_j\mathrm{collides}\mathrm{with}\mathrm{obstacle},\hfill \\ 0\hfill & Otherwise.\hfill \end{array}\right.$$

The decision variable $x_{ij}$ can be written as follows:

$$x_{ij}=\left\{\begin{array}{cc}1\hfill & \mathrm{if}\mathrm{a}\mathrm{UAV}\mathrm{moves}\mathrm{from}positio{n}_i\mathrm{to}positio{n}_j,\hfill \\ 0\hfill & Otherwise.\hfill \end{array}\right.$$

For the intermediate decision variable, $y_i$ is an additional variable indicating whether position i is visited or not, and can be written as follows:

$$y_i=\left\{\begin{array}{cc}1\hfill & \mathrm{if}locatio{n}_i\mathrm{is}\mathrm{visited},\hfill \\ 0\hfill & Otherwise.\hfill \end{array}\right.$$

The aim of these constraints is to provide a collision-free path that safely delivers the UAVs to the destination. The objective function considers both path planning and collision avoidance.

In light of this definition, we formulate the following optimization problem for minimizing flight energy consumption by optimizing the path of the UAVs while considering the given constraints:

$$\begin{array}{c}\underset{\mathbf{Energy}}{min}\mathrm{ObjFun}=\sum _{i=1}^{N_p}\sum _{j=2,i\ne j}^{N_p}(E_{\mathrm{ij}}{x}_{\mathit{ij}}+{\mathit{OC}}_{\mathit{ij}}{x}_{\mathit{ij}})\hfill \\ s.t.\left(\mathrm{a}\right):x{s}_{min}\le x_n\le x{s}_{max},\forall n\in N_p,\hfill \\ \left(\mathrm{b}\right):y{s}_{min}\le y_n\le y{s}_{max},\forall n\in N_p,\hfill \\ \left(\mathrm{c}\right):z_{min}\le z_n\le z_{max},\forall n\in N_p,\hfill \\ \left(\mathrm{d}\right):{∥{\mathrm{U}}_i-{\mathrm{U}}_j∥}_2\ge S{D}_{min},\forall i,j\in N_d.\hfill \\ \left(\mathrm{e}\right):{∥{\mathrm{U}}_i-{Obs}_j∥}_2\ge Margin,\forall i\in N_d,\forall j\in N_{obs}.\hfill \\ \left(\mathrm{f}\right):\sum _{j=1}^{N_p}{x}_{ij}\le 1,\forall i\in N_p,\hfill \\ \left(\mathrm{g}\right):\sum _{j=1}^{N_p}{x}_{1j}=\sum _{j=1}^{N_p}{x}_{jg}=1\hfill \\ \left(\mathrm{h}\right):\sum _{j=1}^{N_p}{E}_{ij}-\sum _{j=1}^{N_p}{E}_{ji}=0,\forall i\in \left[2N_p\right].\hfill \\ \left(\mathrm{i}\right):\sum _{i=1}^{N_p}\sum _{j=1}^{N_p}{E}_{ij}{x}_{ij}\le E_u.\hfill \\ \left(\mathrm{j}\right):\sum _{i=1}^{N_p}\sum _{j=1}^{N_p}\{x_{ji}-x_{ik}\le y_i\},\forall k\in \left[2N_p\right],\hfill \\ \left(\mathrm{k}\right):x_{ij},y_i\in [0,1],\forall i,j\in N_p.\hfill \end{array}$$

(1)

The constraints in Equation (1)a, Equation (1)b, and Equation (1)c represent the allowed range for the UAV in its FoV, where $x{s}_{min}$ and $x{s}_{max}$, $y{s}_{min}$ and $y{s}_{max}$, and $z_{min}$ and $z_{max}$ are the minimum and maximum values of $x_n$, $y_n$, and $z_n$, respectively. The constraint in Equation (1)d ensures collision avoidance, where $S{D}_{min}$ is the minimum allowed distance among UAVs. The constraint in Equation (1)e ensures collision avoidance with obstacles, where Margin is the margin around obstacles. The constraint in Equation (1)f ensures that a maximum of only one link exists from location i to location j. The constraint in Equation (1)g ensures that there is only one start and one end location for each UAV. The constraint in Equation (1)h ensures that the flying energy from location i to location j is the same as the flying energy from location j to location i. The constraint in Equation (1)i seeks to ensure that the flying energy from location i to location j is sufficient. This constraint enables the UAV to return to a base station for recharging when its energy consumption is not sufficient to complete the mission. The constraint in Equation (1)j is the intermediate location constraint indicating whether a location i is in the waypoints of the path. Finally, the constraint in Equation (1)k ensures that x and y are binary variables.

To summarize the above steps, the path planning problem is formulated via MILP and solved using the CPLEX solver.

• Problem Formulation: The UAV path planning problem is formulated as a Mixed-Integer Linear Programming (MILP) problem with the aim of minimizing energy consumption while ensuring collision avoidance. The objective function and constraints are defined to ensure that the UAVs remain within their operational boundaries and avoid obstacles.
• Segment Decomposition: The entire path is broken into smaller segments based on the FoV of the UAVs. To reduce computational complexity, each segment is optimized separately.
• Optimization Solution: The MILP problem is solved for each segment using the CPLEX solver. The solver computes the optimal path that minimizes energy consumption while satisfying all constraints.
• Receding Horizon Control (RHC): This process is repeated iteratively for each new segment as the UAV progresses, enabling real-time path planning adjustments in response to changes in the environment.

3.3. Safety Ensurance Approach

In some cases, certain constraints may not be achievable due to complex environmental conditions. For instance, there may be no available waypoints to follow within the UAV’s FoV, making horizontal flight impossible and collision avoidance challenging. In such scenarios, the proposed Safety Ensurance Approach (SEA) allows the UAV to fly vertically and bypass incoming obstacles, ensuring safe and collision-free UAV operation.

3.4. Smoothing Strategy

The path generated by the proposed algorithm consists of waypoints; however, the path segments connecting these waypoints are composed of linear segments, making it challenging for a specific UAV to track them smoothly. Furthermore, making turns consumes a significant amount of energy for a UAV. Therefore, it is necessary to enhance the path by making it smoother in order to ensure suitability for the UAV. The primary objective is to generate an energy efficient path that adheres to the maximum curvature constraint of the UAV. To achieve this objective, we apply a quadratic Bezer curves to the generated segments, smoothing them out and reducing the impact of turns on energy consumption. Figure 3 shows the control points and provides a schematic representation of the path-smoothing strategy.

4. Results and Simulations

To assess the effectiveness of our proposed strategy in efficiently avoiding obstacles while minimizing energy consumption, we conducted a simulation using the Matlab tool (https://www.mathworks.com/products/matlab.html, accessed on 14 November 2024). The optimization feature of the proposed formulation allows for fast convergence, which makes it suitable for handling dense environments characterized by large number of static and dynamic obstacles. In this scenario, the UAVs need to navigate quickly and safely around multiple obstacles. To account for such high-density environments, we used the following parameter settings:

• Environment: We considered two scenarios; in the first, the environment involved nine static obstacles distributed across a 100 m by 100 m area, while in the second fifteen static obstacles were distributed across a 100 m by 300 m area.
• Dynamic obstacles: Fifteen dynamic obstacles moving at random speeds and in random direction were considered.
• UAV fleet: The formation involved five UAVs flying from starting points to destination points.
• Maximum elevation: The UAVs flew at an altitude of 50 m, and the maximum altitude was restricted 120 m, which was the maximum height of the obstacles.
• Safety distance: A safe distance of 5 m was maintained among the UAVs.
• UAV speed: The maximum allowed UAV speed was 10 m/s.

To demonstrate the effectiveness of the proposed approach, the simulation considered different scenarios involving various obstacles. In addition, we examined the influence of the obstacles on energy consumption by simulations involving only static obstacles and simulations including both static and dynamic obstacles. The simulations were executed on a PC with an Intel Core i7 CPU and 16 GB of memory.

4.1. UAV Path Planning Performance

This subsection describes the results of our tests on the ability of proposed approach to safely deliver UAVs to the destination.

4.1.1. Static Environment Scenario

We considered both 2D and 3D scenarios. The 2D scenario focused on static obstacles with different 2D views of the UAV paths. The UAVs flew from the starting position to the destination following the generated energy-efficient and collision-free path. The results are illustrated in Figure 4. The figure shows narrow passages, especially in scenarios 3, 4, 5, and 6. The aim of these scenarios was to test the ability of the UAVs to navigate through such narrow passages using our proposed approach. It can be easily observed that our approach successfully generates collision-free paths in all scenarios.

In the 3D scenario, the obstacles were randomly generated throughout the environment, creating narrow passages for the UAVs to navigate. We considered a 3D environment with static obstacles. First, we tested the ability of the SEA to avoid obstacles in an environment in which there was no passage for the UAV to navigate; the results are illustrated in Figure 5. The UAVs flew vertically to efficiently avoid collision with obstacles and arrived safely at the destination. Next, we considered two scenarios with a swarm of five UAVs flying from starting points to destinations in a dense environment involving obstacles with narrow passages. These two scenarios were considered to show the effect of obstacles on energy consumption, which is discussed further in Section 4.2. The results of the paths for the 2D and 3D scenarios are shown in Figure 6 and Figure 7. In each scenario, UAVs faced different obstacles in their paths. Figure 6a,b (for scenario 1) and Figure 7a,b (for scenario 2) demonstrate the significant advantages of the proposed approach in generating efficient paths for all UAVs. Our proposed approach efficiently avoids obstacles by maneuvering around them or enabling vertical flight when no horizontal path is available. As an example, UAV3 tries to avoid obstacles in its path; however, there is no horizontal path available. The SEA enables UAV3 to fly vertically and avoid the obstacles, while the other UAVs have a chance to avoid the obstacles by flying horizontally around them.

4.1.2. Dynamic Environment Scenario

To further test the proposed approach, we considered a highly dense environment with both static and dynamic obstacles, including fifteen static obstacles and fifteen dynamic obstacles. The dynamic obstacles moved at random directions and with random speeds. To show the effectiveness of the proposed approach in avoiding dynamic obstacles, we recorded the minimum distance between the UAVs and the obstacles. The results are exhibited in Figure 8, where the X-axes represent the margins around the obstacles and the Y-axes represent the minimum distance from UAVs to dynamic obstacles. It can be observed that the minimum distance is always greater than the margin, proving that no collisions occurred with dynamic obstacles.

4.2. Energy Consumption Performance

One of the most important metrics for assessing the algorithm’s performance is energy consumption. It illustrates how the algorithm can produce a collision-free path while consuming the least amount of energy. Without loss of generality, we divide the energy over the required optimal energy when a UAV travels the shortest path from its starting point to its destination at its maximum speed. We simulated a variety of environmental conditions, including both static and dynamic environments. Figure 6c shows the normalized average energy consumed for the mission in the static situation. Notably, different levels of energy consumption are depicted with the variations in the obstacles along the path from the starting point to the destination.

Figure 7c presents an additional static environment scenario that demonstrates variations in UAV energy consumption influenced by diverse environmental constraints. Notably, UAVs 1 and 5 exhibit minimal energy consumption due to fewer obstacles in their direct path from start to end. The UAVs can efficiently navigate, bypassing obstacles easily without the need to fly vertically or make a longer turn around obstacles. Conversely, the presence of numerous barriers between the starting and ending points of UAVs 2, 3, and 4 requires them to enable SEA in order to avoid flying through the obstacles, which consumes additional energy.

To study the effectiveness of the proposed smoothing approach on energy consumption, we applied a smoothing strategy to the generated paths and compared the results with those of the non-smoothed paths. The normalized energy consumption was recorded with and without the smoothing approach. The results depicted in Figure 6c and Figure 7c clearly show that the paths with smoothing exhibit lower energy consumption and improved the performance. A notable improvement in energy consumption is evident. The reason behind this improvement is that sharp turns require the UAV to decelerate and accelerate, which consumes additional energy. The smoothing approach mitigates the effect of these sharp turns, leading to reduced energy consumption.

4.3. Effect of Obstacles on Energy Performance

Obstacles can obstruct the flight path of the UAV. To navigate around these obstacles, UAVs may need to change their flight trajectory, which often requires increased power consumption as the system must works harder to maneuver, leading to higher energy consumption. In this subsection, we study the effect of obstacles on energy consumption. We considered a static environment with fifteen static obstacles as well as a dynamic environment with fifteen static obstacles and fifteen dynamic obstacles. For each scenario, we recorded the average normalized energy for 30 runs. Figure 9 depicts the results for the static and dynamic environments. As Figure 9 illustrates, less energy is consumed in the static environment than in the dynamic one. This is because the UAVs rarely fly in the z-direction in a static environment. In the dynamic environment, more energy is required to avoid moving obstacles that can suddenly appear in front of the UAVs and force them to make decisions such as flying vertically to avoid collisions. As a result, there is an increase in overall energy consumption.

4.4. Comparison with Other Approaches

To validate our proposed approach, we compared it against the strategies presented in [45,47]. The comparison involved three significant parameter metrics: UAV formation, total collisions with obstacles (NoCs), and time needed to generate a partial path, i.e., duration time (DT). The comparison was conducted over 30 iterations and had a maximum speed of 10 mps.

It must be stressed that the proposed algorithm generated collision-free paths and provided the shortest duration time (DT). In this particular scenario, we consider a densely static and dynamic obstacles environment.

Table 2. Comparison of the time required to generate partial paths, number of collisions, and UAV formation results between our proposed approach and the approaches in [45,47].

Approach	Static Environment			Dense Environment
	NoC	DT (ms)	UAVs Formation	NoC	DT (ms)	UAVs Formation
Proposed	00	255.8	YES	00	301.88	YES
[45]	00	288.16	YES	00	447.4	YES
[47]	00	261.9	NO	10	362.68	NO

summarizes the UAV formations, NoCs, and DT. The table also shows the number of collisions in static and dynamic environments in the second and fifth columns, respectively.

The results reveal that every method effectively generates safe paths with zero collisions in the static environment. However, the approach from [47] produces ten collisions in the dense environment, while the proposed approach and the approach from [45] both achieve zero collisions. Notably, the proposed algorithm outperforms the approach presented in [47] in terms of UAV formation and scenario duration time (DT). The proposed approach effectively handles drone-to-drone collision avoidance, ensuring the safety of the entire UAV fleet. Furthermore, it also outperforms the work from [45] in terms of the time required for path generation within the UAV FoV. The reason for this is the simplicity of our linear optimization based on an MILP formulation and solved by CPLEX compared to the nonlinear optimization solved by SQP in [45].

5. Conclusions

In this study, a three-dimensional energy-efficient online path planning approach for UAVs is proposed based on Mixed-Integer Linear Programming (MILP) and path smoothing. The proposed approach aims to reduce energy consumption by smoothing paths and minimizing the impact of sharp turns. The proposed approach effectively addresses the path planning problem by formulating it as an MILP problem and incorporating a cost function that minimizes energy consumption while considering terrain obstacle avoidance. By utilizing a receding horizon control and optimization strategy, the path is divided into segments with collision avoidance constraints. The proposed safety ensurance approach allows UAVs to fly vertically in order to guarantee safe delivery to the destination. We evaluated the impact of obstacles on path generation and energy consumption, finding that the proposed approach enables fast and accurate navigation in dense environments while ensuring collision-free paths. The results obtained from implementation of our approach demonstrate its effectiveness and accuracy in complex environments with high risk of collisions. We compared our proposed approach against recent works, with the results illustrating that it outperforms other approaches in terms of number of collisions, time required for partial path generation, and UAV formation.

In future work, we aim to allow UAVs to learn from the environment using a reinforcement learning approach and to optimize the tradeoff between energy efficiency and computational requirements in real time.