Fixed-Wing UAV Energy Efficient 3D Path Planning in Cluttered Environments

UAV path planning in 3D cluttered and uncertain environments centers on finding an optimal / sub-optimal collision-free path, considering in parallel geometric, physical and temporal constraints, fox example, obstacles, infrastructure, physical or artificial landmarks, etc. This paper introduces a novel node-based algorithm, called Energy Efficient A* (EEA*), which is based on the A* search algorithm, but overcomes some of its key limitations. The EEA* deals with 3D environments, it is robust converging fast to the solution, it is energy efficient and it is real-time implementable and executable. In addition to the EEA*, a local path planner is also derived to cope with unknown dynamic threats within the working environment. The EEA* and the local path planner are first implemented and evaluated via simulated experiments using a fixed-wing UAV operating in mountain-like 3D environments, and in the presence of unknown dynamic obstacles. This is followed by evaluating a set up where three UAVs are commanded to follow their respective paths in a safe way. The energy efficiency of EEA* is also tested and compared with the conventional A* algorithm.


Introduction
Without loss of generality, simple 2D path planning algorithms are not implementable in complex 3D uncertain environments. On the other hand, challenges in 3D path planning are basically due to their computational complexity, underlying vehicle physical, kinematic and dynamic constraints, vehicle maneuverability, to say the least. Derivation and implementation of a collision free 3D path planning algorithm in cluttered environments constitutes an NP-hard problem. There is no universally acceptable solution, and most of existing solutions are not optimal but heuristic ones. This paper proposes a novel EEA* algorithm and a local path planner that are real-time implementable in 3D cluttered environments; they account for dynamic collision avoidance and they consider physical constraints and limitations of the fixed-wing UAV. The EEA* computes the energy consumed by the vehicle (in this case, the UAV) while following its path, and it minimizes this value by adapting the path, accordingly. The local path planner copes in real-time with unknown dynamic threats present in the operational space, after an off-line computation of the nominal path that is to be followed. It is shown that the energy efficiency of the proposed EEA* algorithm is superior to the conventional A* algorithm; the EEA* reduces on average the energy needed to follow the route by 3.43% in 86.7% of the tested case studies.
The rest of the paper is organized as follows. Section II presents a well-focused literature review, with emphasis on listing advantages, disadvantages, implementation challenges, and limits of existing path planning techniques. Section III states the problem and derives the proposed EEA* algorithm, while Section IV discusses implementation details. Section V presents a comprehensive simulation campaign that supports the effectiveness of the approach. Section VI concludes the paper.

Literature Review
The UAV path planning problem is cast as an optimization problem that returns an optimal solution subject to constraints. Regardless, the specific challenges that have motivated this research, and have dictated the literature review are: 1. 3D: Any proposed algorithm should be used in a 3D real world environment. Much research considers a 2.5D environment, and several existing algorithms do not account for a dynamic 3D environment. 2. Real-Time: Since the environment in which the vehicle (UAV) moves is/may be dynamically changing, the flight path may also change during flight. As such, any proposed algorithm must be real-time and on-board implementable. Many existing algorithms are not implementable online due to high computational burden. 3. Energy Efficiency: Energy limitations (fuel, battery consumption) must be considered. When it comes to aggressive maneuvers with high accelerations, this challenge becomes even more important. Managing energy is one of the least treated issues although as important as the other ones. 4. Robustness: A candidate path planning algorithm must be robust, must overcome the trap in local minima problem, must converge to at least a near optimal solution. Moreover, the algorithm must demonstrate ability to account for position sensitive device errors, rotation driving errors, linear driving errors during path planning, etc.
When looking at published literature, according to [1], path planning algorithms may be divided in the following five categories that are reviewed next.

Sampling Based Algorithms
In [3] and [14], two versions of the same algorithm have been used: RRT and RRT*. In the former, the RRT has been combined with biased sampling and greedy extension of nodes with an added continuous curvature path smoothing satisfying non-holonomic constraints. The algorithm is very simple and fast enough to be executed online. In the latter, the RRT* has been used along with nadir-and obliquecamera views for close proximity as well as large-scale 3D mapping applications. With the support of state-ofthe-art 3D reconstruction software, the recorded inspection data have been post-processed and dense, high-quality point clouds and triangular meshes have been derived. In [15], a hybrid approach has been employed for near-optimal solution in a 2D environment. A third dimension is managed in an online fashion through a fuzzy controller working simultaneously with a Lazy Theta* algorithm [40]. The best path may be found to avoid obstacles by changing the UAV's altitude online using data from the sensors and topographical database.

Node Based Optimal Algorithms
Node based optimal algorithms model and explore routes between nodes of a graph, representing the navigable space, starting at one node and traversing nodes until the destination has been reached. These algorithms have been successfully used to identify optimal routes through a graph for uses such as logistics planning, least cost call or IP routing, and gaming simulation.
In [4], a Fuzzy Virtual Forces (FVF) algorithm is used. To solve the issue of local minima encountered in VF algorithms, the combination of threats has been integrated in the algorithm through a suitable adjacency matrix. An adaptive proportion coefficient based on Bayesian belief network and fuzzy logic reasoning has been added, which can be adapted to environment changes. In [22], a modified A* algorithm is proposed, combined with the Global Navigation Satellite System (GNSS) error distribution obtained by implementing the GNSS, whereas in [25], the authors have proposed an Evolutionary Optimization Algorithm based on an improved t-distribution to deal with high computational complexity.

Mathematical Model Based Algorithms
In [7], mixed-integer programming for control (MILP) is used to successfully show the ability to plan paths that achieve a desired communication topology, while minimizing fuel consumption and avoiding collision and no-fly zones, also satisfying altitude constraints with respect to the terrain. In [8], a trajectory planning/replanning flatness technique is proposed that can be implemented in real-time applications deploying a simplified model. However, using such a simplified models in trajectory planning increased uncertainties and mismatch with the real system. In [9], a Bi-Level Programming based approach is proposed that includes a BLP model and a solution algorithm embedded with heuristic strategies, while in [37] a BLP-based real-time path planner is introduced to generate reference way-points and control inputs at variable planning time intervals. Performance variations are addressed and smooth flight paths are adapted only when necessary. In [16], a given bounded volume is explored through a receding horizon technique. In [17], the UAV path planning problem has been modeled as a single objective optimization problem that utilizes a receding horizon approach and quadratic Bézier curves. The method is gradient-based, allowing for quick and robust convergence to a near optimal solution. Differently, in [38], it is proposed to integrate active perception in a receding horizon setting for a goal reaching task. In particular, a perception-aware receding horizon navigation system is designed using a single forward looking camera for MAVs. In addition to avoiding obstacles, the perception-aware receding horizon navigation system is able to select motion to favor the state estimation accuracy, which is especially advantageous in environments with visually degraded regions. In [23], belief uncertainty-aware planning is followed to achieve consistent exploration. An architecture is presented to achieve this goal. It has been experimentally verified that the proposed receding horizon, two-step, planning paradigm manages to explore different unknown environments with consistency, by following uncertainty optimizing trajectories that are derived through a belief-space propagation process operating on-board a Micro Aerial Vehicle robot.

Bio-Inspired Algorithms
In [2], an evolutionary algorithm-based path planner for UAVs has been presented, called Vibrational Genetic Algorithm (VGA), which is able to construct feasible path lines under prescribed constraints such as path length, turn angle, and clearance between the path and the boundary (terrain) within an acceptable time period, for the online planner as well, where the execution time is important. In [10], two non-deterministic algorithms are used, a Genetic Algorithm (GA) and a Particle Swarm Optimization (PSO), while in [12] a novel algorithm denoted by Harmony Search has been applied to the optimization of agricultural management tasks. In [19], a Hybrid Genetic Algorithm (HGA) is introduced to solve the path planning problem in nonconvex environments. Nevertheless, HGA have provided ineffective results in terms of fuel consumption due to the high accelerations required to follow the path. In [26], a complete UAV surveillance system is designed. An Artificial Neural Network (ANN) is used to make the control structure easier to be used, to reject the disturbances and to reduce the control parameters to be controlled. Furthermore, with a combination of K-agglomerative clustering, a Set-based Particle Swarm Optimization (S-PSO) and an A* algorithm, a path can be efficiently planned predicting and reducing the energy consumption, as well. In [27], three different path planning algorithms have been implemented for biological control. The implemented algorithms are Ant Colony Optimization (ACO), Guided Local Search (GLS) and Lin-Kernighan (LKH). LKH gave better results in terms of RAM consumption, execution time, number of memory used and distance travelled.

Multi-Fusion Based Algorithms
In [5], a hybrid meta-heuristic Ant Colony Optimization (ACO) and Differential Evolution (DE) algorithm approach is followed for Uninhabited Combat Aerial Vehicles (UCAV), allowing for 3D path planning in combat field environments, whilst in [6] a hybrid algorithm is proposed that combines a Virtual Force (VF) algorithm for its simplicity and the A* algorithm for its robustness and efficiency. In [11], the authors have improved the PRM by random sampling in bounding boxes to ensure a more reasonable distribution in the 3D space. Based on the voxel connectivity, the selected nodes composed a roadmap, which has been applied for path searching by the A* algorithm for a feasible path. In [13] a hybrid metaheuristic approach is implemented combining GA and PSO. The disadvantage is that this approach modifies the convergence properties of the single algorithm, and the convergence of the new algorithm remains unproven. In [18], a novel approach is proposed that utilizes the formulation of dynamic Bayesian, Distance Based Value Function (DBVF) and Grey Wolf Optimization (GWO) Algorithm, while in [20] a GA has been implemented along with a Multi-Objective Path Planning (MOPP) Algorithm for area coverage and target detection. The GA aims to minimize completion time, which includes the time to find the target and the time to set up a communication path. In [21] a hybrid approach is implemented in a quadrotor. With the use of the mathematical model enriched by a Q-learning method, the goal is reached after a reinforcement learning phase. In [28] a Grey Wolf Optimization algorithm has been enriched with a Reinforcement Learning method. A cubic B-spline curve has been used to smooth the generated flight path. The authors compared the developed algorithm with another GWO algorithm, showing its statistical superiority. In [24] the chosen algorithms have been the A* and Dijkstra algorithms. Real time tests have been performed on a UAV and the two path length algorithms show the same path length. With respect to time savings, the A* algorithm showed better performance. In [39] the authors have realized a Lazy Theta* implementation for autonomous exploration in a large environment. To achieve this goal, two optimizations have been introduced taking into account the sparse grid that represents the world and the obstacle layout, while calculations are reduced by restricting the space discretization of the flight corridor to two dimensions. Table 1 summarizes key characteristics of each reviewed work. It is important to emphasize that limitations refer to the implementation presented in the reviewed paper. The reviewed algorithms may not have been used in the cited references to overcome these limitations; however,

Problem Statement
The problem statement is detailed in this Section.

3D Path Planning
An acurate mathematical definition of the 3D path planning problem is presented in [29][30][31][32]. Here, fixed-wing UAVs are assumed to fly in a 3D space (R 3 ), called the workspace w. The workspace includes obstacles, so let wo i be the ith obstacle. The free workspace without obstacles is the region represented by The initial point x init and the goal point x goal belong to the free workspace w free . Thus, a path planning problem is defined by a triplet (x init , x goal , w free ).
Definition 2 Given is a path planning problem (x init , x goal , w free ) and a cost function c : Σ → R ≥ 0, where Σ denotes the set of all possible paths. If a process Φ fulfills Definition 1 to find a δ , and c(δ ) = min{c(δ), δ being the set of all feasible path}, then δ is the optimal path and Φ is optimal path planning.

Energy Computation for a Fixed-Wing Aircraft
The energy efficiency problem is accommodated as part of a node-based path planning algorithm, still being consistent with the physics of the model. The total energy for traveling from a specified start node to a destination node is the sum of the total energy spent when traveling through the required edges. Hence, in order to calculate the energy of a path that consists of multiple straight flight paths, we compute the energy consumption ΔE i,j flying through each straight line of length Δd from node i to node j . As explained in details in [33], the difference in the total energy consumption is the sum of differences in potential energy and difference in kinetic energy, plus the energy used to turn the fixed-wing UAV Assuming there is no energy consumption when the UAV altitude is decreasing, the difference of potential energy is given as where h i and h j are the altitudes of node i and j, respectively.
To calculate the kinetic energy we focus on optimizing the velocity that depends on the drag-to-lift ratio of the UAV. In [34] the drag-to-lift ratio is computed as where V is the flight speed and A and B are UAV parameters, also depending on the air density. The UAV parameters are given as Most of the parameters depend on the structure of the UAV; W = mg is the aircraft's weight, b is the wing span, f is the parasite area of the aircraft, and e is Oswald's efficiency. In addition, ρ(h) is the air density at altitude h, computed as [35]: where P 0 = 101, 325N/m 2 is the sea level atmospheric pressure, T 0 = 288.15K is the sea level standard temperature, and R = 287.04m 2 /Ks 2 is the universal gas constant. We assume that the fixed-wing UAV flies with a constant optimum Carson's speed V opt = (B/A) 1/4 , occurring when the D/L ratio is optimum (D/L opt = 2 √ (AB)). Assuming that the consumption efficiency of the UAV is 100%, then this ratio is proportional to the energy consumption, regardless the effect of any wind force.
For a zero-wind scenario, the kinetic energy ΔE k consumed is used to overcome the drag force D on a straight flight Since the lift force L is equal to the UAV weight, if the UAV flies with the constant optimum Carson's speed, then Following the calculation in [36], the consumed energy for turning between two arcs is approximately where σ is the steepest rolling angle that the drone needs to take for turning. Parameters are computed at each time instant within the computation of the cost, assuming that the altitude h i at which the UAV is flying in that specific instant is known, and assuming: -g = 9.81m/s 2 , gravitational acceleration -P 0 = 101.325N/m 2 , sea level atmospheric pressure -T 0 = 288.15K, sea level temperature -R = 287.04m 2 /Ks 2 , universal gas constant -L = 0.0065K/m, lapse rate Hence, the following parameters can also be computed: -T , the temperature at the altitude h i computed as T 0 − Lh i , as long as we are in the troposphere, condition respected since the RQ-170 Sentinel is not apparently intended to flight above 15.000m; -P , the atmospheric pressure at the altitude h i , computed as P = P 0 ( T T 0 ) g LR ρ(h), the air density at the altitude h i , computed using Eq. 7; -A and B, using Eq. 5, computed at the specific altitude h i ; -D/L, the drag-to-lift ratio, computed as the optimal one that is D/L opt = 2 √ AB; -V , the velocity of the UAV, kept at its optimal value and computed as v = (B/A) 1 4 ; -σ , the steepest rolling angle to be taken to turn, set to a maximum of 0.78 rad in case of turning.
Given that the proposed algorithm does not have an implemented path smoothing feature but it deals with kinematic and dynamic constraints setting the maximum turning angle at 0.78 rad, the dissipated energy for a turn may not be reliable, sometimes misleading. Such a sharp angle for a fixed-wing UAV at high velocities implies a huge amount of energy dissipated. Turning angles in real life will be much smaller, resulting in smaller values in consumed energy for a turn. Therefore, the energy dissipated during turning maneuvers is neglected, while we explicitly consider the variation of potential energy ΔE p and the variation of the kinetic energy ΔE k .

Implementation Details
The choice is to center on node-based optimal algorithms due to their reliability and speed to find an optimal path. These characteristics make them appropriate for a 3D path planning problem.
Among them, A* is one of the best choices. Indeed, thanks to its heuristic nature, the A* search algorithm is noticeably faster than other Node-based ones. Choosing the A* algorithm two challenges are intrinsically solved: it deals with 3D environments and it is robust. The third challenge is the energy consumption problem. This is why an energy efficient version of the A* is proposed, called EEA* search algorithm. Finally, to fulfill the real-time requirement, a local path planner is added to deal with unknown dynamic obstacles. The logic is to generate intermediate way-points along the path when an obstacle is sensed by the fixed-wing UAV. The assumption that are considered are: -Part of the map and the static obstacles of the environment are known a-priori. -No wind or disturbances are considered during flight.
After an offline phase, which can be performed while the aircraft is on ground in order to not largely harm the performance, where the global path planner evaluate the apriori known part of the map, the online part is suitable for online implementation. During the online stage the local path planner evaluates dynamically the unknown part of the maps, the dynamically changing obstacles and the other fixed-wing UAVs flying in the map, computing the path accordingly.

A* Search Algorithm
The A* search algorithm is a node-based algorithm, an extension of Dijkstra's algorithm. As explained in https://en. wikipedia.org/wiki/A* search algorithm, A* was created as part of the Shakey project that focused on building a mobile robot that could plan its own actions. Nils Nilsson originally proposed using the Graph Traverser algorithm for Shakey's path planning. Graph Traverser is guided by a heuristic function h(x), the estimated distance from node x to the goal node: it entirely ignores g(x) the distance from the start node to x. Bertram Raphael suggested using the sum, g(x) + h(x). Peter Hart invented the concepts we now call admissibility and consistency of heuristic functions. A* was originally designed for finding least-cost paths when the cost of a path is the sum of its edge costs, but it has been shown that A* can be used to find optimal paths for any problem satisfying the conditions of a cost algebra.
Ultimately, Node based optimal algorithms are classified because they deal with node and arc weight information; they calculate the cost by exploring the nodes to find the optimal path. Unlike Dijkstra's algorithm, A* reduces the number of states by introducing the heuristic estimation of the cost from the current state to the goal state. A* can converge very quickly and to an optimal solution.
An evaluation function is introduced, which consists of post-calculation toward the initial state and heuristic estimation toward the goal where g(x) is the cost from the initial state x init to the current state x, h(x) is the heuristic estimation of the cost of an optimal path from the current state x to the goal state x goal . On finite graphs with non-negative edge weights, A* is guaranteed to terminate and it is complete, i.e. it will always find a solution (a path from start to goal) if one exists. On infinite graphs with a finite branching factor and edge costs that are bounded away from zero d(x, y) > ε > 0 for some fixed ε, A* is guaranteed to terminate only if there exists a solution.

The Proposed EEA* Search Algorithm
Starting from the implementation of the A* search algorithm, a way to reduce as much as possible the usage of the energy is considered. This new algorithm still has all the advantages of an A* search algorithm and concurrently returns a path that is more cost-effective in terms of energy consumption.
A constant velocity along the route V is assumed. The aircraft's weight W , its mass m, the wing span b, the parasite area of the UAV f , the drag-to-lift ratio D/L and the Oswald's efficiency factor of the UAV e are given. The distance from the node i to the node j Δd is kept constant. Therefore, the parameters that affect the total energy computation are the difference of altitude Δh in the potential energy ΔE p , the air density at a certain altitude ρ(h), the kinetic energy ΔE k , and the steepest rolling angle for turning σ that affects the energy consumed for turning, called ΔE turn .
Here, the specific parameter research has focused on because it seemed more logical to work with, is the difference of altitude Δh between one node and its successor. In particular, limiting as much as possible the ascending movement of the fixed-wing UAV so that the total potential energy ΔE p is as low as possible to fly from the starting node to the goal node.
Working on the kinetic energy is less relevant since the air density is strictly related to the altitude to which the UAV flies in that particular moment. Working on this parameter is harder due to some constraints in the flight. Firstly, a safety constraint on the minimum altitude to avoid collisions with the ground. Secondly, constraints inherent in laws that give certain ranges of altitudes for certain type of aircraft.
Going into details, at each computational step of the algorithm, performed in the same way as the A*, the EEA* looks for the node with the lowest f (x) in the OPEN list. Then, it confronts z j , the z component of the node j , with z i , the z component of the node i (the parent node of j ), obtaining two possible branches: -ifz j is equal or lower than z i then the next node has been found (the UAV is keeping is altitude or is descending). -if z j is greater than z i then update the jth node with a new greater f (x) value which takes into account of the energy spent to ascend to a new altitude and repeat the process looking back in the OPEN list.
If a chosen node has been already picked up before and its f (x) has already been updated, that is going to be the next node since every node can be rejected only once.
Once the next node is selected, every nodes whose f (x) has been changed during this phase has brought back to its original value. This operation is needed to take into account the fact that the value of f (x) changes according to the parent node where the algorithm comes from and does not depend only on the node itself. Hence, the operation has to be done again every time the algorithm has to compute a new node.

Local Path Planner
When the distance of the fixed-wing goes below a certain distance with respect to an obstacle a detection happens. When this condition is verified, two different situation can be triggered: -the UAV detects a generic dynamic obstacle: the local path planner generates an intermediate waypoint above the obstacle in order to guarantee the safety of the flight. In the simulations a blue line is drawn to show the optimal path planned by the EEA* search algorithm, whereas a red line represents the actual trajectory performed by the fixed-wing UAV. The drone avoids in a fairly smooth Fig. 1 Fleet of UAVs performing their path altogether. When the path intersect the object is not actual a collision but it means the object or the UAV are passed in a different moment in time so they did not collide at all manner the dynamic obstacle after sensed it, generating intermediate waypoints above the actual path computed by the global path planner. The sensing of the dynamic unknown obstacles and the computation of new waypoints is carried out in real-time.

Multi-Agent Implementation
The implementation of the fleet of UAVs has been made to show that the constellation of algorithms and functions employed by each fixed-wing make them able to work properly together in a multi-agent situation. Each drone, receiving the coordinates of the starting point and of the goal point, is able to compute its own nominal path deploying the EEA* Search Algorithm; then, when the UAVs start following their route, they use their local path planning algorithm to avoid each other treating the other agents as dynamically changing obstacles. Hence an UAV does not know during the flight where the other UAVs are in a specific moment unless they are near enough to be sensed. Fig. 2 Simulations in different mountain environments. In every map there is a no-fly area in red and a dangerous weather area in white. The blue line is the one computed by the global path planner, the red line is the actual trajectory performed by the fixed-wing UAV. The black and yellow objects are the dynamic threats. The objects are spheres whose the head is the actual threat; the tail is not a threat, but it is represented to show the trajectory followed by the dynamically changing obstacles. The small circle is the starting node, the small cross is the goal node Furthermore, the local path planner applies different actions on the computation of the intermediate waypoint depending on if the obstacle is an unrecognized object or another agent. To do that, the agents are able to recognize the other agents once they sense each other. In Fig. 1 some examples are depicted.
The workflow of the simulation is the following one: -The number of agents requested are spawned in the map in their respective starting node. -The agents receive their goal node. -The agents employ the global path planner, in the specific the EEA* Search Algorithm developed in this Thesis work. -The simulation starts and time by time the agents monitor the area around them to look at possible threats. -If a threat is sensed, depending on if it is an unknown obstacle or another agent, a control action is taken to make it able to avoid the collision. -Every agent reach its goal node and the simulation ends.

Simulation Results
To test the energy efficiency of the EEA* Search Algorithm 30 simulations have been carried out for the EEA* and for the A*. In order to compare the performances, the same start goals and node goals have been given as input.
The tests have been made on a HP Pavillion dv6 laptop with a second generation Intel Core i7, an 8GB RAM and 500GB Hard Disk.
The parameters that have been collected are the variation of potential energy ΔE p , the variation of the kinetic energy ΔE k , the variation of the total energy ΔE which is the sum of the first two. Then, they have been compared to assess the performance of the EEA* in terms of energy efficiency. Specifically, the variation of the total energy has been compared and the difference between the two has been computed for every simulation done. In this way, the amount of work saved to perform the route with the novel algorithm has been obtained. After that, the same result has been computed in terms of percentage value; hence it has been gotten the percentage of variation of energy saved with the novel algorithm. In Figs. 1 and 2 the simulations are showed. Simulations have been performed Fig. 3 Comparison between A* and EEA* in terms of variation of total energy consumption. The first picture shows the results plotted on a diagram. The second picture shows the results plotted on a histogram in different mountain-wise environments and both in normal and multi-agent implentations.
In the Table 2, those computed datas have been collected and organized as follows: in the first column we have the number of the simulation which the other datas on the raw refers to, in the second column we have the total variation of energy saved.
Looking at the Table 2, some conclusions can be drawn. The algorithm performs better in terms of energy consumption 86.7% of the time, performs worse 10% of the time and the two algorithm did the same once, equal to the 3.3% of the simulation run. In Figs. 3 and 4 the results are depicted via diagrams and histograms.
When the EEA* does better, the work saved by the UAV spans between 0.13% and 13.46% of the one done with the A*, with an average reduction of 41.5MJ per flight corresponding to an average 3.43% of variation of energy saved. The standard deviations are equal to 4.67MJ and 4.04%.
During the 30 simulations using the A* and the 30 simulations of the EEA*, for a total of 60 simulations, no collision has been registered. Both the static obstacles and the dynamic obstacles has been avoided correctly by the algorithms reporting good performances. In the Table 3, the performances are showed in terms of mean value of the variation of the total energy saved, its standard deviation and those values expressed in percentage.
In the Fig. 5 is depicted an example of the control action applied by the local path planner. The diagram depicted shows on the vertical axis the distance expressed in meters between an UAV and one of the dynamic threats present in the map.
As it can be seen, the UAV approaches the object quickly and dangerously in the first part of the plot. Nonetheless, at a certain point, when the distance is more or less near to 500m, the sensors of the drone detect the moving obstacle approaching and invading the area right in front of the fixedwing UAV. At that point, the local path planner comes into action. Moving the UAV upwards, the local path planner allows the aircraft to be kept far from the threats avoiding a collision. This behaviour is depicted in the diagram with the sharp turning of the function, with the distance kept for a while at a reasonable distance of half a kilometer. In that area of the plot the UAV and the object are flying in the same region, but thanks to the local path planner, they do that in a safe way. After that, it can be seen an almost linear increase of the distance between the two, signifying a departure since both the UAV and the object keep flying on their own path. Fig. 4 The plot shows the percentage of variation of the total energy saved by means of using the EEA* algorithm instead of the A* Fig. 5 The diagram shows the action of the local path planner with respect to the distance from the UAV and the object. The vertical axis represents the distance in meters between a certain UAV and a dynamic threats in the map

Conclusions and Future Work
In this work, we have firstly carried out a literature review concerning the last-decade researches on path planning for UAVs. After a classification of the algorithms employed, limitations have been identified and common challenges have been recognized. These challenges have been overcome in different ways by researchers, nonetheless, as far as we know, none of them have solved the four problems altogether, at least for UAV applications.
Later, a novel node-based 3D real-time energy-efficient path planning algorithm has been developed using MAT-LAB in order to overcome these four challenges altogether. Specifically, the algorithm, called EEA* Search Algorithm, is based on the A* Search Algorithm and deploys a global path planner and a local path planner finding the most energy-efficient route and avoiding dynamic unknown obstacles in the map.
The algorithms have been deployed in different and gradually more complicated environments. Then, three fixedwings UAVs have been employed to work together without interfere with each other.
The energy efficiency has been tested. To do that, 30 simulations have been carried out for both the EEA* and the A* feeding them with the same inputs and looking for the results. From the data collected, we observe that the EEA* reduces the work needed to follow the route in 86.7% of the time and of the 3.43% on average.
Even if the algorithm provides encouraging preliminary results, some improvements are required. In future works, we will aim at increasing the uncertainty sources, contemplating wind disturbance toward working in an environment similar to the real world. Another important aspect to be considered, to better validate the algorithm developed, is to include a path smoothing algorithm in order to have more realistic and feasible paths to be performed by a fixed-wing UAV. This feature not only have this advantage, but it would permit us to better study the performance of the energy efficiency, taking into account of the work needed for turning maneuvers. Indeed, with more realistic paths, the estimation of the variation of energy would be much more accurate, further reducing the approximation of the results.
Funding Open access funding provided by Politecnico di Torino within the CRUI-CARE Agreement. A.R. acknowledges partial funding by Compagnia di San Paolo and the 2019 Amazon Research Award.
Author Contributions K.V. and A.R. conceived and supervised the research. G.A. designed and implemented the simulation studies and drafted a preliminary version of the paper. All the authors concurred to the analysis of data, revised, and approved the final version of the manuscript.

Conflict of Interests
The authors declare that they have no conflict of interest.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons. org/licenses/by/4.0/.