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/.


extfieldsofstudy:
Computer Science
Engineering

text:
Improving Generalization of Deep Neural Network Acoustic Models with Length Perturbation and N-best Based Label Smoothing

We introduce two techniques, length perturbation and n-best based label smoothing, to improve generalization of deep neural network (DNN) acoustic models for automatic speech recognition (ASR). Length perturbation is a data augmentation algorithm that randomly drops and inserts frames of an utterance to alter the length of the speech feature sequence. N-best based label smoothing randomly injects noise to ground truth labels during training in order to avoid overfitting, where the noisy labels are generated from n-best hypotheses. We evaluate these two techniques extensively on the 300-hour Switchboard (SWB300) dataset and an in-house 500-hour Japanese (JPN500) dataset using recurrent neural network transducer (RNNT) acoustic models for ASR. We show that both techniques improve the generalization of RNNT models individually and they can also be complementary. In particular, they yield good improvements over a strong SWB300 baseline and give state-of-art performance on SWB300 using RNNT models.

Introduction
Generalization is a fundamental problem in machine learning. In ASR, acoustic models with deep neural network (DNN) architectures may suffer from overfitting due to their huge number of parameters. To make DNN models generalize well, techniques such as model regularization (e.g. 1-norm or 2-norm regularization [1] and dropout [2]) and data augmentation [3] [4][5] [6] have been broadly used in training. In this paper we introduce two techniques to improve generalization of DNN acoustic models in ASR. One is data augmentation based on length perturbation which randomly drops and inserts frames of an utterance to alter the length of the speech feature sequence. The other is label smoothing based on n-best hypotheses.
Length perturbation compresses and stretches the feature sequence of an utterance in the training to provide a perturbed variant of it having a different length. This is conducted by both frame skipping and frame insertion. Frame skipping and frame insertion as separate approaches have been used in the speech community for different purposes. In most cases, frames are skipped in ASR systems, in a fixed or dynamic manner, for reduced processing time in training or decoding [7][8] [9] [10]. In [11], SpliceOut is proposed to treat frame skipping as a time masking approach to improve generalization of DNN models in various speech recognition and audio classification tasks. In [10], it is observed that DropFrame, despite being aimed at reducing training time, may also help to improve performance of end-toend models. Analogously, frame insertion or time stretching is a common perturbation technique for speech and audio signals in the other direction [12][13] [14]. From the length perturbation perspective, the current application of either frame skipping or frame insertion tends to perturb the length of an utterance biased towards one direction. The length perturbation approach investigated in this paper consists of perturbation both ways.
Label smoothing, first introduced in [15], aims to improve generalization in machine learning by avoiding overconfidence over labels. Although researchers are still trying to gain insights into the working mechanism of label smoothing [16] [17], it has been shown to be helpful in a broad variety of machine learning tasks [18] [19][20] [21]. In its conventional setting, label smoothing is accomplished by smoothing a one-hot label vector with a uniform distribution across all class labels under the cross-entropy loss function. Since ASR is essentially a sequence to sequence mapping problem and the acoustic model of interest in this work is recurrent neural network transducers (RNNTs) [22][23] estimated under the maximum likelihood loss function, we approach label smoothing from a sequence perspective. We choose n-best hypotheses as competing "classes" and use them as "noisy" labels in the training with probability.
ASR experiments are carried out on the 300-hour Switchboard (SWB300) dataset [24][25] which consists of narrowband speech and an in-house 500-hour Japanese (JPN500) dataset which consists of broadband speech to evaluate the two proposed techniques with various configurations. The acoustic models are RNNTs [8][26] [27]. We show that both techniques can improve word error rates (WERs) separately on the two datasets. Moreover, the two techniques can be complementary. In particular, when combining length perturbation and n-best label smoothing, we obtain state-of-the-art WERs on the SWB300 dataset using RNNTs.
The remainder of the paper is organized as follows. Section 2 and Section 3 are devoted to the length perturbation and n-best label smoothing, respectively. Experimental results on SWB300 and JPN500 are reported in Section 4. Section 5 concludes the paper with a summary.

Length Perturbation
Implementation of the proposed length perturbation is given in Algorithm 1. The length of an utterance is perturbed first by skipping frames and then followed by inserting frames, both with a probability. To skip frames, one randomly samples rs percentage of frames from the utterance to operate on. For each sampled frame x, ts consecutive frames are dropped starting from x where ts is an integer upper bounded by a hyper-parameter Ts. Analogously, to insert frames, one randomly samples rp percentage of frames from the utterance to operate on. is the logMel spectrum after frame skipping followed by frame insertion.
sampled frame y, tp consecutive blank frames (zero vectors) are inserted after y where tp is an integer upper bounded by a hyper-parameter Tp. This is illustrated in Fig.1 where the logMel spectrum of an utterance is demonstrated in Fig.1a. Fig.1b and Fig.1c are its perturbed versions by frame skipping and insertion, respectively. Fig.1d is the overall effect of perturbation after both frame skipping and insertion. All three perturbations are carried out with certain probabilities according to Algorithm 1.
Length perturbation can help in scenarios where there is a mismatch in the length of utterances between training and test conditions. In addition, by randomly dropping frames, it can also perturb the "memory" of a sequence model such as long shortterm memory (LSTM) [28] network to avoid simply memorizing the history of the feature sequence in the training. Therefore it can improve the generalization. Furthermore, the applied frame insertion can be viewed as simulating a SpecAug [6] mechanism for an utterance of longer length (Fig.1c). It encourages the system to fill in those inserted frames during training, which is also similar in spirit to the filling in frames (FIF) idea in voice conversion [29].

Algorithm 1 Length Perturbation of Input Utterances
L ← Total number of utterances ps ← Probability of perturbation by dropping frames; rs ← Percentage of frames to be perturbed in an utterance; Ts ← Maximum frames to drop; pp ← Probability of perturbation by inserting frames; rp ← Percentage of frames to be perturbed in an utterance; Tp ← Maximum frames to insert; for 1 ← 1, · · · , L do Perturb this utterance by dropping frames with prob. ps: DropFrames(rs, Ts) Perturb this utterance by inserting frames with prob. pp: Insert tp consecutive blank frames after y this is one this is one of the most highly taxed areas in the country 01 this is one this is one the most highly taxed areas in the country 02 this is one this is one the most highly tax areas in the country 03 this is one this is one the most highly taxed areas and country 04 this one this is one the most highly taxed areas and the country 05 this is one this is one the most highly tax areas and country Figure 2: An example of a ground truth label (top line in bold) and its 5 best hypotheses.

N-best Based Label Smoothing
Label smoothing introduces a small amount of noise to ground truth labels to avoid training with over-confidence to help generalization. For a classification problem with cross-entropy loss, labels are typically provided as one-hot vectors. Suppose y is a class label for a sample x and there are K classes in total. Label smoothing smoothes the label with a uniform distribution over K classes weighted by as shown in Eq.1 Suppose p is the ground truth (one-hot) distribution, q is the distribution to be learned and u is the uniform distribution. Label smoothing amounts to imposing a regularization term n i=1 Hi(u, q) to the original cross-entropy term n i=1 Hi(p, q) as shown in Eq.2 where i = 1, · · · , n and n is the total number of samples.
Extending the label smoothing setting in Eq.1 to RNNT training under the maximum likelihood loss is not straightforward as the softmax output of RNNT reflects local decisions while the learning is focused on the whole sequence. From a sequence classification perspective, each sequence may represent a class and all sequences over the output space Y form a countably infinite set of classes in that sequence space. In this light, we may smooth out the ground truth label sequence with a small number of competing label sequences, which motivates us to investigate the label smoothing strategy based on n-best hypotheses.
Let γ be a random variable uniformly distributed in [0, 1] and a constant ∈ [0, 1]. Suppose y is a ground truth label sequence and Ω y|x = {ŷ1, · · · ,ŷK } is the n-best set that consists of K nbest hypotheses of y given x. Select uniformly at random from K hypotheses a hypothesisŷi, i ∈ {1, · · · , K}, and replace the ground truth label with it with probability . This is given in Eq.3 where I(·) is the indicator function: Fig.2 shows an example of a ground truth label sequence and its n-best hypotheses that are used to smooth the ground truth label. The n-best hypotheses are generated by the baseline RNNT models.

SWB300
The RNNT acoustic model for SWB300 has 6 bi-directional LSTM layers in the transcription network with 1,280 cells in each layer (640 cells in each direction). The prediction network is a single-layer uni-directional LSTM with 768 cells. The outputs of the transcription network and the prediction network are projected down to a 256-dimensional latent space where they are combined by element-wise multiplication in the joint network. After a hyperbolic tangent nonlinearity followed by a linear transform, it connects to a softmax layer consisting of 46 output units which correspond to 45 characters and the null symbol. The acoustic features are 40-dimensional logMel features extracted every 10ms and their first and second order derivatives. The logMel features are after conversation based mean and variance normalization. Every two adjacent frames are concatenated and appended by a 100-dimensional i-vector [30] as speaker embedding. Therefore the input to the transcription network is 340 in dimensionality.
The training data goes through three steps of data augmentation. First, it is augmented by speed and tempo perturbation [4]. This is conducted offline and produces additional 4 replicas of the original training data, which gives rise to about 1,500 hours of training data in total. After the speed and tempo perturbation, mix-up sequence noise is injected where an utterance is artificially corrupted by adding a randomly selected downscaled training utterance from the training set [5]. After that, SpecAugment is applied where the logMel spectrum of a training utterance is randomly masked in blocks in both the time and frequency domains [6]. Dropout [2] is also used in the LSTM layers with a dropout rate of 0.25 and the embedding layer with a dropout rate of 0.05. In addition, DropConnect [31] is applied with a rate of 0.25, which randomly zeros out elements of the LSTM hidden-to-hidden transition matrices. A Connectionist Temporal Classification (CTC) [32] model is used to initialize the transcription network.
Optimizer AdamW is used for the training. The learning rate starts at 0.0001 in the first epoch and then linearly scales up to 0.001 in the first 10 epochs. It holds for another 6 epochs before being annealed by 1 √ 2 every epoch after the 17 th epoch. The training ends after 30 epochs. The batch size is 64 utterances. An alignment-length synchronous decoder [33] is used for inference. We measure the WERs with and without an external LM. When decoding with an external LM, density ratio LM fusion [34] is used. The external LM is trained on a target domain corpus (Fisher and Switchboard) and the source LM is trained only on the training transcripts. The length perturbation is applied before mix-up and SpecAug, all of which are carried out on the fly in the data loader. We evaluate various hyper-parameter configurations for length perturbation (ps,pp,rs,Ts,rp,Tp) and n-best label smoothing (K and ) on Hub5 2000, Hub5 2001 and RT03 test sets. The data preparation pipeline follows the Kaldi [35] s5c recipe. Table 1 breaks down the performance of length perturbation on frame insertion (2 nd -5 th rows), frame skipping (6 th -9 th rows) and perturbation both ways (10 th -12 th rows), respectively, on the Hub5 2000 test set. The length perturbation is applied in the first 25 epochs and lifted afterwards. From the table, one can observe that both frame insertion and skipping alone can improve WERs. The best WER is obtained when perturbing both ways (avg. 10.7% without using external LM and 9.4% when using external LM.) Table 2 shows the performance of n-best label smoothing under various , which controls the probability to replace the ground truth label with a noisy label, and K, which is the total number of n-best hypotheses considered. Similarly, the label smoothing is applied in the first 25 epochs and lifted afterwards. The best performance (avg. 10.9% without using external LM and 9.5% when using external LM) is achieved when = 0.1 and K = 20.
Experimental results on combining the two techniques are reported in Table 3 where label smoothing is applied up to 15      Table 4 reports the WERs using label smoothing (nbestls), length perturbation (lenpb) and their combination on Hub5 2000, Hub5 2001 and RT03. The external LM is used in the decoding. For comparison, we present the single-model result reported in [8] as one baseline (1 st row) and the baseline used in this work (2 nd row). The difference is the learning rate schedule and the number of epochs. In [8], the maximum learning rate is set to 5e-4 and the OneCycleLR policy [36] is used for 20 epochs. The current baseline gives slightly better performance. The models that give the best performance on Hub5 2000 in Tables 1, 2

JPN500
The RNNT acoustic model for JPN500 has 6 bi-directional LSTM layers in the transcription network with 1,280 cells in each layer (640 cells in each direction). The prediction network is a single-layer uni-directional LSTM with 1,024 cells. The outputs of the transcription network and the prediction network are projected down to a 256-dimensional latent space where they are combined by element-wise multiplication in the joint network. After a hyperbolic tangent nonlinearity followed by a linear transform, it connects to a softmax layer consisting of 3547 output units which correspond to Japanese characters and the null symbol. The acoustic features are 40-dimensional log-Mel features extracted every 10ms and theirs first and second order derivatives. The logMel features are after utterance based mean normalization. Every four adjacent frames are concatenated. This more aggressive frame skipping is to reduce the length mismatch between the feature sequence and character label sequence. The input to the transcription network is 480 in dimensionality.
There is no data augmentation in the training. But dropout is used in the LSTM layers with a dropout rate of 0.25 and the embedding layer with a dropout rate of 0.05. Optimizer AdamW is used for the training. The learning rate starts at 0.0001 in the first epoch and then linearly scales up to 0.001 in the first 10 epochs. It holds for another 6 epochs before being annealed by 1 √ 2 every epoch after the 17 th epoch. The model is obtained after 30 epochs. The batch size is 256 utterances. The same alignment-length synchronous decoder is used for inference. No external LM is used in decoding. Both length perturbation and label smoothing are applied in the first 25 epochs and lifted afterwards, respectively. We evaluate various hyper-parameter configurations for length perturbation (ps,pp,rs,Ts,rp,Tp) and n-best label smoothing (K and ) on 13 real-world test sets from a broad variety of domains and report the average CERs across these test sets. Table 5 and Table 6 show the respective performance of length perturbation and n-best based label smoothing on JPN500 using various hyper-parameter settings. Following a similar trend in SWB300, both techniques help to consistently improve the CERs over the baseline. The length perturbation can reduce the CER from 19.4% in the baseline to 18.5% and the label smoothing can reduce to 18.6%. One interesting observation is that since JPN500 has a more aggressive downsampling strategy (4-frame skipping) in input feature processing compared to that of SWB300 (2-frame skipping) the optimal length perturbation setting for JPN500 tends to favor frame insertion more than frame skipping over SWB300 (Ts = 3, Tp = 5 for JPN500 vs. Ts = 7, Tp = 3 for SWB300). Table 7 shows that the two techniques can also be complementary. In the experiments, the label smoothing is applied up to 15 epochs and length perturbation is applied between 16 to 25 epochs. After 25 epochs both techniques are lifted and the training continues for another 5 epochs. The model used for decoding is after 30 epochs. The combination of the two techniques can achieve a CER of 18.4%, which amounts to 1% absolute improvement over the 19.4% baseline averaging across 13 test sets.   Table 6: N-best label smoothing using various configurations on JPN500.  Table 7: Combination of n-best label smoothing and length perturbation on JPN500.

Discussion
Since the length perturbation perturbs an utterance both ways, it has SpliceOut [11] and DropFrame [10] as a special case of one-way perturbation, which corresponds to the results in Table  1 and Table 5 where only Ts is used (Tp = 0). The length perturbation can be used by itself as shown in the JPN500 case or used together with other data augmentation techniques as shown in the SWB300 case. The implementation of the length perturbation may have numerous variations such as the order of frame skipping and insertion or whether frame skipping and insertion should take place in different utterances. This will be further investigated in the future work.

Summary
In this paper we introduce length perturbation and n-best based label smoothing to improve the generalization of DNN acoustic modeling. We evaluate the two techniques extensively on both SWB300 and JPN500 datasets and show that both techniques can improve accuracy over strong baselines with RNNT acoustic models. The techniques can be complementary. By combining the two techniques, we have obtained state-of-art single-model results on SWB300 using RNNT.