Air Trajectory Optimization for Noise Reduction Marco Gullo
ID 900465
Supervisor Federico Malucelli Co-supervisor Matteo Crippa
A thesis presented for the degree of Computer Science and Engineering
Ingegneria Industriale e dell’Informazione Politecnico di Milano
Italy
Academic Year 2019/2020 April, 28, 2021
Abstract
Many people who live near an airport are aware of the noise caused by the aviation industry. Over the years, authorities have taken several steps to reduce the perceived aircraft’s noise. This thesis aims to con-tribute to these efforts by proposing a new mathematical model and optimization algorithms to optimize and generate air routes producing the least amount of noise pollution. The mathematical model is based on nonlinear programming. The model will rely on A*, a graph-search algorithm. The proposed local search algorithm will exploit the air routes’ features to enhance the solutions. Next, flight and noise simu-lations will provide the data to evaluate the results and compare them with existing routes. Special attention will be devoted to the actual case of the Malpensa Airport. We will provide a functional implemen-tation of the algorithms proposed, which gave us promising results during the testing phase, leaving the door open for future research and improvements.
Sommario
Molte persone che risiedono nei pressi di un aeroporto conoscono bene l’inquinamento acustico prodotto dall’industria aeronautica.
Negli anni le autorità hanno preso diversi provvedimenti al fine di ridurre il rumore prodotto dagli aerei e percepito dalla popolazione. Questa tesi ha lo scopo di contribuire a questi sforzi proponendo un innovativo modello matematico e degli algoritmi di ottimizzazione per ottimizzare e generare rotte aeree minimizzandone il rumore emesso. Il modello matematico è basato sulla programmazione non lineare, la cui soluzione è demandata a un algoritmo che trae ispirazione da A*, un algoritmo di ricerca-grafo.
L’algoritmo di ricerca locale proposto sfrutterà le caratteristiche delle rotte aeree per migliorare le soluzioni ottenute. In seguito, una simulazione di volo e una del suono forniranno i dati necessari a valu-tare i risultati ottenuti e a confrontarli con le rotte esistenti. Sarà pre-stata particolare attenzione all’aeroporto di Malpensa, proposto come caso di studio.
Verrà descritta un’implementazione funzionante degli algoritmi trat-tati, che in fase di valutazione ha fornito risultati promettenti, aprendo le porte a futuri studi e sviluppi.
Contents
List of Figures 5
List of Tables 7
1 Introduction 8
2 The problem 10
3 State of the art 11
3.1 Aviation noise . . . 11
3.2 Similar works . . . 12
3.3 Other useful works . . . 14
3.3.1 Path planning . . . 14
3.3.2 Search algorithms for path planning . . . 15
3.3.3 Comparison . . . 16 4 Our approach 18 4.1 Approach overview . . . 18 4.2 Environment modeling . . . 18 4.2.1 Modeling overview . . . 18 4.2.2 Aircraft’s state . . . 19
4.2.3 Sensitive receptors and noise . . . 19
4.2.4 Air routes . . . 19
4.2.5 No-flight zones . . . 20
4.3 Route generation . . . 20
4.3.1 The algorithm: A* . . . 20
4.3.2 Dynamic graph generation . . . 22
4.3.3 A* complexity and performance improving . . . 23
4.3.4 Search algorithm pseudocode . . . 24
4.3.5 Bidirectional search . . . 24
4.3.6 Bidirectional search pseudocode . . . 26
4.4 Route optimization . . . 27
4.4.1 The algorithm: nonlinear programming . . . 27
4.4.2 Optimization’s problem formalization . . . 28
4.4.3 The local minima trap . . . 28
5 The implementation 31
5.1 Implementation overview . . . 31
5.2 Hardware used . . . 31
5.3 Inputs and outputs . . . 32
5.4 Geographic approximation . . . 32
5.4.1 Geoidal model and Vincenty’s formulae . . . 33
5.4.2 Spheric model and Haversine’s formula . . . 33
5.4.3 Flat model . . . 34
5.5 Algorithms implementation . . . 37
5.5.1 Trajectory generation using A* . . . 37
5.5.2 A* performance improvements strategies . . . 38
5.5.3 Trajectory optimization using nonlinear programming . 42 5.6 Performance analysis . . . 43
5.6.1 Trajectory generation algorithm’s performance . . . 43
5.6.2 Route optimization algorithm’s performance . . . 58
6 Further implementation enhancements 66 6.1 Implementing dynamic precision for trajectory generation . . . 66
6.2 Reducing complexity with Voronoi diagrams . . . 66
7 Testing and results 69 7.1 Malpensa airport . . . 69 7.2 Sensitive receptors . . . 70 7.3 Flight simulation . . . 70 7.4 Noise simulation . . . 72 7.5 Study cases . . . 72 7.5.1 Departure DOGUB5L . . . 72 7.5.2 Departure SRN5W . . . 83 8 Conclusions 94 8.1 Results analysis . . . 94 8.2 Future works . . . 94 8.2.1 Solution improvements . . . 94 8.2.2 Implementation improvements . . . 96 8.2.3 Testing improvements . . . 97 8.3 Possibilities of application . . . 98 Appendices 99
A Brief software usage instructions 99
A.1 Installation . . . 99
A.2 Directory structure . . . 99
A.3 Execution . . . 100
A.4 Configuration . . . 100
A.4.1 Scenario . . . 100
A.4.2 Geometry . . . 101
A.4.3 Route . . . 102
A.5 Optional configuration . . . 103
A.5.1 Settings . . . 103
A.5.2 Population data . . . 104
A.6 Usage . . . 105
A.7 Generating and optimizing routes . . . 106
A.8 Searching altitude data . . . 107
A.9 Visualizing and exporting information . . . 107
List of Figures
1 Visual representation of the noise perceived by a sensitive
re-ceptor. . . 29
2 Visual representation of the noise value with three sensitive receptors. . . 30
3 Geographical precision test shape. . . 36
4 Error in our flat model test at various latitudes. . . 37
5 Reference image for the search area. . . 38
6 Performance improvement discretizing locations. . . 40
7 Unidirectional and bidirectional A* search comparison. . . 41
8 The scenario and the generated trajectory for the sensitive receptors test. . . 44
9 The average time for the generation algorithm test with dif-ferent numbers of receptors. . . 45
10 The program’s output with central and side receptors. . . 47
11 The program’s output with different distance bias coefficients. 49 12 The program’s output with different distance bias exponents. . 50
13 Program outputs with different Earth models. . . 52
14 The necessary iterations for the generation algorithm test with different step sizes. . . 54
15 The necessary iterations for the generation algorithm test with different numbers of angles. . . 55
16 The program’s output using a step size of 3 kilometers and considering 7 angles at each iteration. . . 56
17 Performance comparison using different cost step sizes. . . 57
18 Performance comparison using different numbers of waypoints. 60 19 Program outputs using 8 and 20 waypoints. . . 60
20 Optimization test changing the number of sensitive receptors. 61 21 Performance comparison in the optimization test using differ-ent numbers of receptors. . . 62
22 Program outputs using different delta values. . . 64
23 Performance comparison in the optimization test using differ-ent delta values. . . 65
24 Program outputs using different maximum delta differences. . 65
25 A Voronoi diagram for six points on the plane generated using SciPy. . . 67
26 A discrete weighted Voronoi Diagram. . . 68
27 Aeronautical chart where the SID DOGUB5L is visible. . . 73
28 Test 1: the projection of the generated trajectory and the original one. . . 77
29 Test 1: noise intensity comparison. . . 78 30 Test 1: noise intensity comparison in Sesto Calende, Arsago
Seprio and Vergiate. . . 79 31 Test 1: noise intensity comparison in Varallo Pombia, Pombia
and Borgo Ticino. . . 80 32 Test 1: heat maps of the noise intensities. . . 81 33 Test 1: the projection of the generated trajectory and the
optimized one. . . 83 34 Aeronautical chart where the SID SRN5W is visible. . . 84 35 Test 2: the projection of the original trajectory and the
gen-erated one. . . 86 36 Test 2: the projection of the original trajectory and the
gen-erated one using the new boundaries. . . 87 37 Test 2: noise intensity comparison. . . 89 38 Test 2: noise intensity comparison in Nosate and Turbigo. . . 90 39 Test 2: noise intensity in Castano Primo. . . 91 40 Test 2: heat maps of the noise intensities. . . 91 41 Test 2: the projection of the long generated trajectory
opti-mized using nonlinear programming with 20 waypoints. . . 93 42 Noice main menu after loading a configuration containing an
List of Tables
1 Works comparison. . . 17 2 WGS 84 reference values . . . 33 3 Performance improvement discretizing locations . . . 39 4 Performance improvement using bidirectional A* search . . . . 40 5 Performance comparison in the generation test using different
numbers of sensitive receptors. . . 45 6 Performance comparison using different distance bias coefficients 48 7 Performance comparison using different distance bias exponents 50 8 Performance comparison using different Earth models . . . 51 9 Performance comparison using different step sizes. . . 54 10 Performance comparison using different branching factors. . . 55 11 Performance comparison using different cost step sizes. . . 57 12 Performance comparison using different numbers of waypoints. 59 13 Performance comparison in the optimization test using
differ-ent numbers of receptors. . . 62 14 Performance comparison in the optimization test using
differ-ent delta values. . . 63 15 Test 1: comparison of noise emission and absorption for
dif-ferent receptors between the original and generated trajectories. 76 16 Test 1: comparison of noise emission and absorption for
differ-ent receptors between the generated and optimized trajectories. 82 17 Test 2: comparison of noise emission and absorption for
dif-ferent receptors among the original, the long generated, and the short generated routes. . . 88 18 Test 2: comparison of noise emission and absorption for
1
Introduction
One of the most severe problems of the aviation industry is the environmental impact. Noise pollution is the most annoying and immediately perceivable consequence of an airport’s presence.
Prolonged exposure to noise, especially at night, can cause damage to health. In addition to the hearing system’s impact, noise can cause sleep dis-turbances, impaired cognitive performance, and severe cardiovascular effects, such as hypertension, myocardial infarction, and stroke.
In everyday life, it can cause stress, which contributes to the deterioration of health conditions.
A study published in 2014, conducted by the European Society of Cardi-ology [1], analyzed the impact of different types of recurrent noise of artificial origin. The correlation between aircraft noise and several diseases stands out among them. Arterial hypertension and coronary heart disease are the most common.
Nocturnal noise causes alterations in blood pressure, which risks damag-ing cardiovascular health in the long term.
Due to the possible health risks and the continued nuisance caused by airport noise, local administrations took various measures to reduce noise pollution. Among them are restrictions on aircraft types, operating hours, and air traffic balancing on the different take-off and landing routes, evenly distributing noise and reducing the maximum exposure detected.
The purpose of this thesis is to contribute to these efforts by proposing an optimization algorithm capable of generating air trajectories that reduce noise exposure in the most sensitive areas. The main objective is to re-duce the amount of noise on the so-called sensitive receptors, i.e., the most noise-sensitive areas. The algorithm generates from scratch or improves air trajectories for the aircraft to stay as far as possible from the sensitive re-ceptors.
This approach allows focusing on realistic scenarios in which the aim is to reduce noise in certain areas, such as densely populated areas, hospitals, and schools. It also offers an easy way to quantify the algorithm’s improvement, specifying where we need to measure noise.
We will focus on take-off and landing procedures since they produce the harshest noise for the people. Regulations often set vertical profiles to fixed levels near airports. Thus, the algorithm focuses on the horizontal profile optimization of trajectories, reducing the problem’s complexity.
The aim is to conceive an algorithm that suits different airports in geo-logically different environments.
This approach will meet both aviation companies and the local popula-tion’s needs, improving the emitted noise levels without impacting airport operations.
2
The problem
This paragraph aims to define the inputs and outputs of the algorithm we will describe in the following chapters.
Our objective is to generate optimized trajectories or optimize existing trajectories using some initial parameters. We will treat generation and optimization as separate problems. Nonetheless, they share many input pa-rameters.
The algorithm’s main inputs are the initial and final positions’ geograph-ical coordinates, the aircraft’s initial and final headings, and the sensitive receptors’ geographical coordinates and associated weights. The algorithm computes an approximation for the aircraft’s noise emission in the sensitive receptors proportional to their weights.
The algorithm requires inputting an existing trajectory in the form of a set of waypoints to perform direct optimization. A waypoint is the tuple of the aircraft’s geographical coordinates and heading.
The secondary inputs are the performance constraints that impact the trajectory’s shape and the delimitation of the area where the trajectory must lie. Optionally, the algorithm can consider no-flight zones.
The algorithm uses three mutually exclusive approximation models: the geoidal, spheric, and flat models. Different models provide different precision levels and execution times.
The output trajectory is a set of waypoints. Trajectory generation uses a fixed step size to generate new waypoints, meaning that they will be all equispaced. Optimization instead relies on the input waypoints.
The waypoints approximate the final air route. The output trajectory does not respect technical formality and requires an additional step before being compared to official routes. In principle, the aircraft must follow the waypoint’s coordinates and direction.
Currently, the algorithm does not take into consideration aircraft’s alti-tude and speed.
Therefore, the results require filling those values to obtain a realistic trajectory. In our case, we will be using a flight simulator that uses fixed vertical profiles and dynamically imputes the aircraft’s speed. The simulator also implements rules that we exploited to make the virtual aircraft follow the route’s waypoints.
When generating or optimizing an air trajectory, the algorithm aims to minimize the aircraft’s total noise emission.
3
State of the art
3.1
Aviation noise
Sound is a physical phenomenon that consists of a sinusoidal wave caused by oscillations in atmospheric pressure. The human ear can perceive sound waves on average between the frequencies of 20 Hz and 20,000 Hz.
A sound source emits power (N), measured in energy per unit of time (Joules per seconds - or Watts). The power travels in space together with the sound propagating through a medium.
Sound intensity (I) is the sound power transmission through a surface (Watts per squared meter).
We can express sound intensity relative to a reference intensity, being the hearing threshold 10−12W/m2 (I
ref), in a logarithmic scale called Decibel
(dB). When expressing the sound intensity in decibels, we refer to the sound intensity level (LI). The sound intensity level formula is:
LI = 10log10(I/Iref) = 10log10(I) + 120
The ear is sensitive to intensities between 0 and 130 dB.
We compute the sound density at a specific distance from the source as: I = N
4πr2
For instance, a sound source of 100 W from 1 meter emits 100/(4π12) =
7.9577W/m2, which corresponds to 10log10(7.9577) = 129dB.
Our algorithm considers 1/r2 a measure for noise intensity. Despite this
value not being correct, comparisons among different intensities are coherent. They are fundamental for the optimization process.
A turbojet plane engine’s sound power is around 100,000 W. We will assume that an aircraft is a punctiform omnidirectional sound source with that constant power in our testing.
Our project aims at reducing noise intensity in specific areas. Regula-tions also consider other aspects relevant, such as the duration of exposure. Therefore, time-weighted average values of sound intensity levels help mea-sure aviation noise.
The Italian law on airport noise is articulated and complex and covers all aspects of noise analysis and management, such as measurement, monitoring, simulation models, and mitigation actions.
The noise emitted by aircraft appears to have a short duration and high intensity. The noisiest events (take-offs and landings) affect the Airport Noise
Rating Level (LVA). Isolevel curves, which delimit areas with the same LVA, represent the acoustic impact.
The airport noise level is determined based on the logarithmic mean of the daily LVAJ values (the noise index calculated over 24 hours). The LVA results from the average of the three most congested weeks of the year, according to the Ministerial Decree of October 31, 1997.
The daily level of LVAJ, on the other hand, is divided into daytime level LVAD (6.00 a.m. - 11.00 p.m.) and night level LVAN (11.00 p.m. - 6.00 a.m.). The noise produced at night is ten times more penalizing than that produced during the day.
Sources: [2][3]
3.2
Similar works
In the literature, it is rare to find researches aiming at optimizing air routes to reduce noise emissions. H.G. Visser produced the most significant work in this area.
His work focuses on take-off and landing procedures [4][5][6], the most delicate ones for sound emission, and the same ones analyzed in our testing. The case study is the Amsterdam Airport Schiphol (AAS), where aircraft use the so-called Continuous Descent Approach (CDA) for arrivals as a noise abatement procedure. However, the application of this procedure is limited to the least congested hours for logistical reasons. As for departures, the ICAO1 "noise abatement departure" is used, designed to reduce the
high-intensity area at the expense of enlarging the low-noise area.
Visser relied on the Integrated Noise Model (INM)2, the Federal
Avia-tion AdministraAvia-tion’s standard methodology from 1978 to 2015, to analyze the noise emission improvements during his optimization work. He inte-grated into a single software tool called NOISHHH the INM, a Geographic Information System (GIS), and a dynamic trajectory optimization algorithm. Unfortunately, the software tool is not available to the public.
He applied an acoustic model based on the methodology used by the INM, which selects it from a specific noise-thrust-distance (NTD) table to determine the Sound Exposure Level (SEL). Finite-length segments, with a particular SEL value, divide the air path. The determining factor is the geometry of the segment from the observer’s point of view. Visser adds to the calculation a speed correction to the fixed 160 knots value and a
1International Civil Aviation Organization.
2Integrated Noise Model. It was a computer model to evaluate aircraft noise impact in
airports’ vicinity licensed by the Federal Aviation Administration from 1978 and replaced in 2015 by the Aviation Environmental Design Tool (AEDT.)
lateral attenuation that considers different effects of noise propagation on the ground, including ground reflection effects, refraction effects, and airplane shielding effects.
Our efforts are to provide a mathematical method to expand with such precise noise modeling.
EZopt takes care of NOISHHH’s optimization process. It is a software produced by ISCFDC (ISraeli Computational Fluid Dynamics Center), which implements a variant of the so-called collocation method, capable of dealing with multi-phase trajectory optimization problems. This method transforms the control problem into a nonlinear programming formulation, discretizing the dynamics of the trajectory. This discretization must consider the tradeoff between the desired level of accuracy and the computational cost.
What emerges from Visser’s analysis is that one of the leading causes of noise reduction is the thrust cutback during certain parts of the path, applicable to specific arrival and take-off maneuvers. [4]
Visser also demonstrates that it is possible to adapt the optimization process to area-navigation (RNAV). [7] This combination is interesting be-cause it allows at the same time the discretization of the trajectory and the production of a flyable route, composed of only two types of legs3:
track-to-fix (TF), i.e., a straight segment, and radius-to-track-to-fix (RF), i.e., an arc of the circumference that connects two points. There are some rules to follow by adopting this approach. For example, it is not possible to adjacently place two RF legs with different radii.
For our implementation, each pair of adjacent waypoints defines a TF leg. A flight simulator correctly joins the legs. The Testing chapter provides further detail.
Visser’s optimization takes place considering the following variables: [8] • The position in two-dimensional horizontal space;
• The direction; • The altitude profile; • The speed profile; • The bank angle; • The required thrust.
Instead, Visser considers the following values constant by approximation:
• The coefficient of aerodynamic drag; • The gross weight of the aircraft.
The primary metric used is sound exposure, which combines with a secondary metric that penalizes routes that are too long and affect fuel consumption excessively. Our implementation allows applying a similar bias towards short trajectories.
One of Visser’s students proposed a variant of his method in a 2015 the-sis. [9] This variant is based on the recently developed Snake Algorithms and focuses on on-line optimization. The presented approach allows obtaining a solution to the optimization problem in a shorter time, albeit more approx-imate, since it will enable to bring the scenario back to a relatively simple physical system in which elastic and tension forces act.
On-line optimization, however, is not one of the objectives of our project.
3.3
Other useful works
3.3.1 Path planning
Path planning, or motion planning, is the computational problem of finding a sequence of valid configurations that describe a system’s evolution from an initial to a final state. Some constraints often subject this problem, such as avoiding colliding with obstacles.
This algorithms’ class mainly applies to computational geometry, digital animation, video games, and robotics. In the latter field, there was a partic-ular growth of interest in recent years due to the advent of Unmanned Aerial Vehicles (UAVs), a category of aircraft that ranges from commercial drones to military vehicles.
Many researchers proposed innovative methodologies to solve path plan-ning problems.
One example is the approach proposed by Rymsha Siddiqui based on the Artificial Potential Field (APF) algorithm. [10]
This approach treats the environment as a potential force field. The obstacles are repulsive force sources, and the goal location is an attractive force source. The traveling object moves pushed or pulled by force sources.
The approach is iterative and discretizes the environment organizing the space in grid cells. At each iteration, it moves the object from a cell to an adjacent cell with lower potential. No near cell might have a lower potential than the current one; in this case, a local minimum trap occurred. To solve this issue, Rymsha adds an imaginary obstacle in the local minimum’s region.
We evaluated adopting the Artificial Potential Field algorithm for smoothing, but the testing phase revealed no strict necessity.
Another proposed approach is the Rapidly-exploring Random Trees (RRT) algorithm. It is a stochastic iterative approach that supported path planning for several years and is very efficient in finding a path in a non-convex space, even with large sizes. [11]
Rapidly-exploring Random Trees algorithms build a search tree generat-ing random samples in the search space. They divide the search space into areas and assign them an evaluation value, which influences the probability to generate a sample in that area.
Rapidly-exploring Random Trees algorithms can help to generate paths also in the tridimensional space. In this case, it is crucial to smooth the results to obtain feasible trajectories in the analyzed environment. [12]
Even though RRT algorithms are very promising, we wanted to adopt a deterministic approach for our problem, which is, by its nature, subject to many parameters and whose results can change depending on how it is tuned. We avoided adding aleatory factors.
We can make a similar point about genetic algorithms, which X. Hu et al. proposed for on-line path planning problem solving due to their stochastic nature and high-resolution speed. [13] Genetic algorithms are metaheuristics, i.e., a partial search algorithm that can find an almost optimal solution, inspired by natural selection processes and part of the so-called evolutionary algorithms. In the path planning problem, each chromosome represents an optional path, and the genes are waypoints. In the algorithm’s evolutionary process, chromosomes combine and mutate to find the optimal or a sub-optimal path.
The researchers model trajectories introducing the concepts of time-slice and discrete heading. They divide the problem into partial optimization prob-lems for each time-slice. The found sub-trajectory depends on the previous run of optimization and the set of discrete headings.
We brought similar concepts to our trajectory model. Since we do not directly address aircraft speed, we treat the aircraft as flying at a constant velocity, and the distance between the waypoints represents a time-slice. Moreover, in the generation process, the algorithm chooses for each waypoint a turning angle from a discrete set of angles.
3.3.2 Search algorithms for path planning
Path planning is not an optimization algorithm. For instance, when solv-ing obstacle-avoidance problems, we are not considersolv-ing path length or fuel consumption; we are just generating a feasible path not passing through
obstacles.
If we want to optimize specific path parameters, we should complement path planning with some optimization criteria.
R. A. Morris et al. proposed a path planning approach to minimize rotorcraft landing trajectories’ noise. [14] They based the approach on using physical simulations combined with a search algorithm.
They employed a two-phase architecture, consisting of a search step phase and an evaluation phase. The search step phase outputs a trajectory, while the evaluation phase outputs a score for the trajectory. They exploited the simulations for the evaluation phase. Then, they compared the A* search algorithm and Stochastic Local Search (SLS) performances for the search step phase. The advantage of one search strategy over the other depends significantly on the scenario and the required accuracy. Generally, their results show that SLS can perform similarly to A* in less time, especially when setting a high precision level.
Nonetheless, we decided to adopt A* for our path generation algorithm. The main reason is that we wanted to use a deterministic method. Moreover, our approach does not involve physical simulations during the generation phase, severely impacting the performance. The following chapter explains how we integrated the A* search algorithm with our air trajectory model. 3.3.3 Comparison
Table 1 summarizes the principal aspects of the algorithms proposed in the papers we discussed above. The last row denotes how this thesis will treat them.
Our method can perform both path planning and trajectory optimization together. It aims to generate air trajectories minimizing noise emission. It is a deterministic method, meaning that identical initial conditions correspond to identical results. Moreover, our method is guaranteed to find the optimal solution in the adopted model’s context4.
4The Implementation chapter will describe some techniques to improve the algorithm’s
Work or author Objective Algorithm Method Sol.
opt. Model Testing Rymsha Siddiqui,
2018
Propose a path planning algorithm for Unmanned
Aerial Vehicles (UAVs) APF Determ. No 2D N/A
S. M. LaValle, 1998 Presentmethod for path planningan innovative RRT Stochastic No 2D N/A
A. Abbati et al., 2012
Extend an existing path planning technique to the
3d case RRT Stochastic No 3D
Four imaginary scenarios
X. Hu et al., 2004 Proposemethod for on-line flightan innovative
path optimization GA Stochastic No 2D
Simulation system (Boeing-707 model)
R. A. Morris et al., 2013
Couple a search technique with simulations to design low-noise flight profiles for rotorcraft
A*, SLS Det./Stoch. Yes/no 3D Imaginary sce-nario
This thesis
Propose an innovative method for air trajectory optimization and noise reduction
A*, NP Determ. Yes 2D Two scenariosin Malpensa airport
4
Our approach
4.1
Approach overview
The solution we propose consists of two distinct approaches.
The first uses a graph search algorithm to generate an air trajectory from some initial parameters.
The second uses a nonlinear programming local search technique to en-hance existing routes. They can be routes from an official database or gen-erated by our algorithm.
Combining the two approaches allows obtaining better results in terms of noise reduction.
The following paragraphs will describe how to model the environment and the two approaches in detail.
4.2
Environment modeling
4.2.1 Modeling overview
Firstly, we need to define how to represent a point on the Earth’s surface. A point is a pair of coordinates: latitude and longitude. Latitude specifies the north-south position on the Earth’s surface and ranges from -90° (south) to +90° (north). Longitude specifies the west-east position on the Earth’s sur-face. Conventionally, the prime meridian, which passes through Greenwich, England, is 0° longitude. Positive longitudes are east of the prime meridian, and negative ones are west. Longitude ranges from -180° to +180°.
Our algorithm works on a rectangular area defined on the Earth’s surface, enclosing the system under consideration. We compute distances within the rectangle using three model types: flat Earth, spherical Earth, and geoidal Earth. The latter is the most precise. Depending on the chosen approxima-tion, the rectangle must be sufficiently small to obtain the desired level of precision, and the algorithm should not operate at too high latitudes.
We tested the algorithm with the three Earth models around 45° latitude and 8° longitude.
The rectangle’s definition consists of its center’s geographical coordinates and the vertical and horizontal spans in meters. The model used may require a transformation of the rectangle.
The Implementation chapter will provide further information about the Earth models.
4.2.2 Aircraft’s state
An aircraft’s state defines a unique physical state of the aircraft. States can have a sequence relation, meaning that the aircraft can reach one state from the other directly without needing to define intermediate states.
In our model, an aircraft’s state consists of the aircraft’s bidimensional position (i.e., the geographical coordinates) and heading.
The aircraft state is expandable, meaning that it can integrate other parameters for future works, such as the aircraft’s altitude and speed. 4.2.3 Sensitive receptors and noise
Sensitive receptors are a tuple of latitude, longitude, and weight. The weight is a scalar number that represents the severity of emitting noise in that sensitive receptor.
We measure noise emission as if the aircraft were an omnidirectional punc-tiform noise source. We obtain a value for noise dividing the sensitive recep-tor’s weight by the square Euclidean distance between the receprecep-tor’s and the aircraft’s positions.
The total punctual noise emission is the sum of noise emitted in every sensitive receptor.
We model the aircraft’s noise while flying over a segment dividing it into points and computing the sum of punctual noise emission values. We define the distance between those points a priori. This discretization decreases computational complexity.
We will often refer to noise emission as cost (e.g., a segment’s cost is the aircraft’s noise while flying over that segment).
4.2.4 Air routes
We model an air route as a broken line. The route’s cost is the sum of its segments’ costs.
An aircraft cannot strictly follow a broken line while flying. Two adjacent segments with different directions are thus approximating a curve. This approximation is to consider when processing the generated route to obtain a realistic one.
The Testing chapter will provide further information about how segments transform into curves.
4.2.5 No-flight zones
We model no-flight zones using two different shapes: a circle or a polygon. To define a circle, we need its center’s coordinates and its radius. For the polygon, we need the coordinates of its vertices.
4.3
Route generation
4.3.1 The algorithm: A*
To generate air routes, we used A*, a graph traversal and path search algo-rithm.
The graph G is a structure amounting to a set of nodes N and a set of arcs A. A pair of ordered nodes define an oriented arc. Every arc features a weight value.
A node in N represents an aircraft’s state, consisting of the aircraft’s coordinates and heading angle. An arc in A represents the transition from an aircraft’s state to another. Its weight represents the aircraft’s noise emission during the transition.
The whole graph G represents the system in which the aircraft moves. G is a weighted directed graph. A* searches for a path (i.e., a sequence of arcs) connecting two nodes in the graph and having the least total cost, computed as the sum of the arcs’ weights. The initial one is the start node, the final one is the goal node.
A* is an iterative algorithm. It maintains a search tree5 of paths
originat-ing at the start node and extends them one edge at a time until a termination criterion is satisfied.
At each iteration, A* decides which path to extend. It computes the path’s cost to the currently extended node and estimates the cost to reach the goal node. This latter estimation is called a heuristic.
Let us call g(n) the cost of reaching the node n and h(n) its heuristic. A* chooses the node to expand selecting that minimizing:
f (n) = g(n) + h(n)
The heuristic’s usage allows A* to speed up computation. Neverthe-less, to guarantee the solution’s optimality, the heuristic must be admissible, meaning that it never overestimates the actual cost to get to the goal.
We chose A* to implement the following heuristic. Let us imagine that the aircraft could fly towards the goal on a straight line, regardless of its
5A data structure used for locating specific nodes within a set. In our case, the search
current heading and the final heading constraint. Let us assume that all the sensitive receptors lay behind the aircraft considering this imaginary trajectory, keeping the same distance from the aircraft in its current position. Now let the aircraft fly towards the goal and measure the cost of the traveled segment. This cost is the heuristic value. This heuristic advantages aircraft states close to the goal state and far from sensitive receptors.
To check for the heuristic’s admissibility , let us consider the following. The cost of a path depends on two factors: its length and the relative position of the sensitive receptors. A straight line is the shortest path connecting two points. Thus, we minimized length. While computing the heuristic, the receptors’ positions make their distances from the aircraft linearly decrease with the aircraft’s imaginary movement during the heuristic computation. Having fixed the receptors’ initial distances, this is the best situation possible since their distances could not decrease faster with time. Thus, the heuristic value is at most equal to the actual cost of reaching the goal.
A* keeps a priority queue called fringe to select the node to expand with the minimum cost.
When expanding the least expensive node, A* checks for cycles in the search tree and excludes new nodes that cause them, allowing to reduce the number of nodes in the fringe. A cycle occurs when the new aircraft’s state is equal or very similar to another state in the current path, meaning the aircraft turned around. For the solution to still be optimal while checking for cycles, the heuristic must also be consistent: for each edge in the graph connecting two nodes x and y with a weight w:
h(x) <= w(x, y) + h(y)
The previous condition means that if the heuristic decreases from one node to the next, the decrement must be inferior to the cost of the arc connecting the two nodes.
The most significant decrement in the heuristic value would occur if the aircraft moved towards the goal location, leaving the receptors behind, such as in the heuristic computation scenario. In this case, the previous state’s heuristic would equate to the sum of the current state’s heuristic and the transition’s cost. Thus, the condition holds and the heuristic is consistent.
Eventually, the algorithm stops if a termination condition holds for the current expanded node. In our case, it is enough to verify whether the aircraft is sufficiently close to the goal position and has a sufficiently similar heading to the goal heading. How close the aircraft should be is a parameter to tune according to the analyzed scenario.
The termination condition is necessary because it is statistically difficult for the algorithm to find the actual goal state. Loosening the termination
condition allows the algorithm to perform faster in exchange for a less accu-rate solution.
The algorithm also stops if the fringe is empty after the first iteration. That would mean that the algorithm explored every reachable node from the start, and none of those nodes was close to the goal node. In that case, we should modify the performance constraints or the scenario.
It is possible to fix some parts of the trajectory a priori. For instance, if the algorithm generates a landing procedure, the aircraft can be forced to fly in a straight line for the last part.
4.3.2 Dynamic graph generation
The graph of all the possible aircraft states in the system is virtually infinite. Thus, the algorithm discretizes the graph and generates it iteratively.
Every time A* expands a node, it dynamically generates its successors, using a fixed step size and a set of turn angles. The algorithm generates the turn angles in advance from the minimum turning radius and a given cardinality value.
The maximum turning angle a is measured as: a = asin
s
2r
where s is the step size, and r is the minimum turning radius.
If the maximum angle is greater than a right angle, we trim it to 90°. Doing so avoids using steps bringing the aircraft backward with respect to its heading, which can lead to unexpected results.
The turning angles are equispaced, range from −max angle to +max angle, and are in quantity equal to the chosen cardinality. Every angle represents a possible step with a fixed size.
When the algorithm expands a node, it computes a new state for each step.
Depending on the model used, the algorithm applies different formulas to compute new states’ position and heading. The Implementation chapter provides further details.
The algorithm discards the states that lie outside the system’s rectangular area or inside a no-flight zone. Then, It adds the remaining ones to the fringe. We can also introduce an arbitrary shift of the start and goal locations. This shift is beneficial when we want the airplane to maintain a specific direction when starting or ending the trajectory. In real cases, this option would be helpful, for instance, when landing or taking off.
4.3.3 A* complexity and performance improving
The A* computational complexity depends on the branching factor and the solution’s depth.
In our problem, the branching factor is the steps’ cardinality (i.e., how many possible steps the algorithm considers when expanding a node). The solution’s depth is the needed number of steps to reach the goal along the lowest cost path.
Thus, reducing the steps’ cardinality and size will reduce the algorithm’s complexity at the expense of a physical environment’s sparser model.
The heuristic has a significant effect on the A* performance since it allows the algorithm to prune away many nodes that do not lead to the optimal solution.
In the worst case of an unbounded search space, the number of expanded node is exponential in the depth of the solution d, and the time and space complexity of A* is O(bd), where b is the branching factor.
If the heuristic is close to the optimal heuristic (i.e., the exact cost to get to the goal), the effective branching factor (the average number of expanded children of each node) is close to 1.
In our problem, the heuristic gets more precise if the optimal path is similar to a direct segment joining the start and the goal positions. The heuristic will never be optimal since we move the sensitive receptors behind the aircraft to measure it. If the algorithm kept the receptors in their original position, we could not guarantee the solution’s optimality. Moreover, the heuristic would not necessarily improve in terms of closeness to the optimal heuristic.
To increase the algorithm’s performance, we introduce a bias towards shorter paths. The bias varies according to a coefficient b1 and an
expo-nent b2. When computing a path’s cost or a node’s heuristic, the algorithm
changes them in the following way.
path cost = path cost + b1× path length × b2
heuristic = heuristic + b1∗ goal distance × b2
The bias represents a tradeoff between the solution’s optimality and the path length while decreasing time and space complexity. The algorithm will tend to exclude nodes that bring further from the goal when deciding which node to expand, and it is likely to come close to the goal in a shorter time.
The values for cost and heuristic depend on the number and the position of the sensitive receptor. Thus, the user should tune the bias coefficient for each scenario.
4.3.4 Search algorithm pseudocode Algorithm 1: Path search using A*
generate steps using step size, minimum turning radius, and steps cardinality;
initialize tree and fringe; current node = start node; goal node = goal node;
while not termination condition do
get the current path from the start node to the current node going up the tree;
add the current node to the tree;
generate successors for the current node using the steps; for successor in successors do
if boundaries broken then go to next successor
path cost =sum the cost of the segment from the current node to the successor to the path cost of the current node;
compute the heuristic for the successor;
add the successor with its path cost and its heuristic to the f ringe;
current node = extract the best node from the fringe (i.e., the one having the lowest cost + heuristic);
if termination condition then return current path;
else
if f ringe is empty then raise error;
4.3.5 Bidirectional search
We can apply a bidirectional search to solve the A* algorithm. The bidi-rectional search runs two simultaneous searches: one forward from the start node and one backward from the goal node, stopping when the two searches meet.
The two searches proceed as the unidirectional, or direct, one. The only difference is that a junction detection is performed at every iteration, checking if the two searches met. The junction detection checks the current node against every node in the tree of the other search. If it finds a pair of close
enough nodes, the algorithm stops.
On average, bidirectional search strongly increases the performance. If the two searches meet exactly halfway, they both have a complexity of O(bd
2).
The sum of the two complexities is much less than O(bd).
In our problem, bidirectional search provides another advantage. The algorithm’s complexity increases if the sensitive receptors are close to the goal. The intention to stay away from the receptors and the attempt to get close to the goal contradict themselves.
This problem does not occur if the sensitive receptors are close to the start node because the aircraft must stray from the start position.
Starting both from the start and the goal nodes mitigates this issue. If one of the two searches reaches its goal before meeting with the other, the opposite search continues until it reaches the goal or meets the first search. The algorithm outputs the best-found solution, which can be the result of a direct search.
4.3.6 Bidirectional search pseudocode
Algorithm 2: Path search using bidirectional A*
initialize tree(toward), fringe(toward), tree(backward), f ringe(backward);
current node(toward) = start node; start node(toward) = start node; goal node(toward) = goal node;
current node(backward) = goal node inverted (with opposite heading);
start node(backward) = goal node inverted;
goal node(backward) = start node invertedappend current node(toward)to tree(toward) and
current node(backward)to tree(backward); d = toward;
while not termination condition do
current path = path from start node(d) to current node(d) for successor in successors do
if boundaries broken or cycle detected then go to next successor;
path cost =cost of the segment from the current node to the successor + path cost of the current node;
compute the heuristic for the successor;
append the successor with its path cost and heuristic to f ringe(d);
if the other search did not stop then invert d;
else
if only one search can keep going then set d to the only available direction; else
return the best solution found;
if no search can continue and no solution was found then raise error;
4.4
Route optimization
4.4.1 The algorithm: nonlinear programming
In mathematics, an optimization problem is a problem of finding the best solution from all feasible solutions. An optimization problem can be discrete or continuous. In the first case, the optimization must find some objects from a countable set. In the latter, the optimization must find a value from a con-tinuous function. Optimization problems aim at minimizing or maximizing a function called objective function over a set of unknown real variables. They include constrained problems, where some constraints restrict the allowed values for the variables.
The algorithm to optimize already formed trajectories relies on nonlinear programming. That is the process of solving an optimization where the constraints or the objective function are nonlinear.
Firstly, we need to define the problem variables which will model the physical problem.
We start by dividing the trajectory into segments. If we generated the trajectory using our route generation algorithm, it will probably already be in an acceptable shape.
Each end of the segments is a waypoint of the trajectory. Each waypoint except the first and the last (representing the start and the goal positions) can shift on a shift axis.
Shift axes are lines passing through the waypoints and perpendicular to the trajectories. Their direction is the mathematical mean of the direction from the current waypoint to the previous one and the direction from the current waypoint to the next one.
The shift of a waypoint on its shift axis is called delta. We define a fixed maximum value for deltas such that the optimized trajectory is close to the original one. To further limit the optimized trajectory deviation, we impose constraints on the maximum difference between adjacent waypoints’ deltas.
The last set of constraints imposes a maximum value for the turning angles, measured as the differences between adjacent segments’ orientations in the trajectory.
We measure the maximum value for turning angles in the same way we did for the search problem in the previous paragraph, using the average length of the initial trajectory’s segments instead of the step size.
The optimization’s objective is to minimize the trajectory’s cost, i.e., the sum of its segments’ costs.
4.4.2 Optimization’s problem formalization Variables d[n], where n is the number of shift axes
Constraints d[i] ∈ [−delta limit, +delta limit], for every i ∈ 1..m, where m is the number of waypoints
|d[i] − d[i + 1]| <= max(delta diff ), for every i ∈ 1..n − 1 gap(dir(i − 1, i), dir(i, i + 1)) <= max angle, for every i ∈ 1..m, where m is the number of waypoints
Objective minimize P
cost(i, i + 1), for every i ∈ 1..m − 1
gap is a function computing the acute angle formed by two di-rections.
dir is a function computing the direction of the vector joining two waypoints; for the start waypoint, the previous direction is the initial angle; for the goal waypoint, the next direction is the final angle.
cost is a function computing the cost of a segment; check the Environment modeling section for further details.
4.4.3 The local minima trap
In mathematics, a function existing on an n-dimensional interval is convex if the line segment between any two points on the function’s graph lies above the graph between the two points.
A strictly convex function on an open set has no more than one minimum, and the optimization is bound to find the global minimum. Our objective function is a sum of punctual noise emissions:
X
i,j
wi
((xj − xi)2+ (yj− yi)2)
where i ∈ sensitive receptors, j ∈ points
The function’s shape, visible in figure 1, is centered around the sensitive receptor.
If we constrain the function inside a rectangle, there are four local minima in the rectangle’s corners.
When considering the emission of a single point against multiple recep-tors, local minima appear inside the rectangle where the functions’ valleys intersect (figure 2).
Thus, punctual noise emission is not a convex function, and neither is the sum of multiple noise emissions.
The optimization can result in a local minimum, not the optimum value in the considered scenario.
Figure 1: Visual representation of the noise perceived by a sensitive receptor. X and Y axes (horizontal coordinates) correspond to the aircraft coordinates. The Z axis (vertical coordinate) corresponds to the noise value. Getting close to the receptor quadratically increases the noise emission.
Computer solvers often use iterative approaches to solve optimization problems, starting from an initial configuration. Depending on the configu-ration, the solver will find the closest local minimum.
The proposed solution consists of running the optimization with multiple initial configurations to find more local minima, then choosing the best one. This approach does not guarantee to find the optimal solution. Nonethe-less, the chances to find a solution close to the global minimum or the global minimum itself significantly increase.
We generate the initial configurations following a specific pattern. We identify n pivots on the trajectory. Then, we define m delta values for each pivot. Every combination of pivot values corresponds to an initial configura-tion.
In our implementation, we combined two pivots with five delta values, resulting in 25 different configurations. The Implementation chapter provides further details.
Figure 2: Visual representation of the noise value with three sensitive recep-tors. When the three colored areas meet, a local minimum lies.
4.4.4 Considerations
The route generation algorithm and route optimization are two very differ-ent approaches. The first can generate routes just considering the sensitive receptors. Therefore, the result can severely differ from an official route.
The latter instead relies on the definition of an existing route and re-mains in its vicinity. We empirically noticed that official routes often lie in deep local minima, and optimization is sometimes ineffective. In those cases, route generation can output a very different trajectory from the official one, minimizing noise in the environment model.
We can also combine route generation with optimization, improving the result, especially when we need to increase the approximation during the generation phase to reduce the A* complexity.
5
The implementation
5.1
Implementation overview
We developed a computer program to implement the solution previously de-scribed. We wrote the program using Python, an open-source programming language released under the Python Software Foundation Licence. The pro-gram comes with many configuration files and functionalities.
The main functionalities are:
• generation of air routes using the A* algorithm;
• optimization of existing routes using nonlinear programming. Other functionalities are:
• parsing user’s configuration files;
• managing geographical coordinates and converting them from and to Cartesian coordinates;
• graphically showing routes to the user;
• exporting routes in several formats, among which KML, XML, and CSV.
A brief user guide in the appendices describes how to use the configuration files.
5.2
Hardware used
We developed and tested the program on a Lenovo Thinkpad T470p with the following specifications:
• Intel i7-7820HQ at 2.90 GHz base clock; • Intel HD Graphics 630;
• NVIDIA GeForce 940MX;
• 16.0 GB, 2400 MHz, single-channel RAM; • Windows 10 Enterprise, version 2004.
Every performance benchmark will refer to this hardware and software con-figuration.
5.3
Inputs and outputs
The program needs the following inputs:
• a scenario, consisting of the coordinates of the search area’s center and the sensitive receptors’ configuration, i.e., their geographical locations and weights;
• a geometry, being the horizontal and vertical spans of the search area; the geometry also specifies the grid’s size for the flat model’s conversion; • a route, which can be a mere indication of the start and goal locations
or the complete data about an existing trajectory.
The program checks the compatibility among the receptors, the trajectory, and the geometry. If the route lies outside the search area, the program asks the user to change the inputs. Instead, if a receptor lies outside the search area, it simply discards it, informing the user.
The program generates new trajectories, which are sets of waypoints. It can present those data to the user in several ways, the most immediate being graphically showing the trajectory’s flat projection.
It can also export the trajectory information in several formats, for in-stance, in KML, a format compatible with Google Earth6.
5.4
Geographic approximation
Our program implements three Earth’s models in ascending order of accu-racy: the flat, spheric, and geoidal models. The user can choose one of these models during the program execution.
The flat model projects the Earth’s surface on a Cartesian plane. Then, it applies the Euclidean geometry formulae to compute positions and distances. The flat model requires a conversion between geographical and Cartesian coordinates before and after working with it.
Spheric and geoidal models instead work directly on geographical coor-dinates. The first model approximates the Earth with a sphere and uses Haversine’s formulae to compute positions and distances. The latter uses Vincenty’s formulae, which work on an oblate spheroid, i.e., the shape of an approximate rotating planet, like the Earth.
6Google Earth is a computer program that renders a 3D representation of Earth based
5.4.1 Geoidal model and Vincenty’s formulae
The geoid is the shape that the ocean surface would take under Earth’s gravity and rotation alone.
The World Geodetic System (WGS) is a standard for cartography, geodesy, and satellite navigation and describes the geoid that better approximates the Earth’s shape. Its last version is WGS 84, maintained by the NGA (National Geospatial-Intelligence Agency) since 1984. [15]
WGS 84 provides the measurements shown in Table 2. Semi-major axis (a) 6378137.0m
Semi-minor axis (b) ≈ 6356752.314245m Inverse flattening (1/f ) 298.257223563 Mean radius ((2a + b)/3) 6371008.771415m
Table 2: WGS 84 reference values WGS 84 claims to have an accuracy of ±1m. [16]
Vincenty’s formulae are two, the direct and the inverse ones. The first allows computing a new position on the geoid’s surface, given an initial posi-tion, a distance, and an azimuth. The second allows computing the distance and azimuth between two positions. [17]
WGS 84 provides the semi-major axis, the semi-minor axis, and the in-verse flattening values used in the formulae.
Vincenty’s formulae are iterative methods requiring a threshold indicating the level of precision. When the difference between two subsequent iterations falls under the threshold, the algorithm has reached the required precision level and stops.
Our program uses a dynamic threshold for the direct formula based on the step distance and observing the following expression:
10−(9−distance0s order of magnitude)
with the maximum threshold being 10−3. The inverse formula works with
a fixed threshold of 10−12. We chose the thresholds empirically, searching
for the minor thresholds requiring a reasonable amount of iterations, not becoming a computational burden.
5.4.2 Spheric model and Haversine’s formula
Haversine’s formula allows computing the distance and azimuth between two points on a sphere’s surface. [18] To approximate the Earth’s shape, we set
the sphere’s radius to the mean Earth’s radius provided by the WGS 84 and reported in the previous paragraph.
To compute a step on the sphere’s surface, we inverted the Haversine formula. The inverse formula takes as input some coordinates, a direction, and a distance and outputs the new point’s coordinates and the final azimuth, just like Vincenty’s inverse formula.
The Performance analysis section provides a comparison between Vin-centy and Haversine’s performance.
5.4.3 Flat model
The flat model requires coordinate conversion from geographical to Cartesian coordinates and vice versa. We perform the conversion using Vincenty’s formulae. Below we provide a numeric example to explain how the conversion works.
Example
Let us suppose we are working on a scenario with the following parameters: • the center of the search area is 45° latitude and 9° longitude;
• the area is a square spanning 100 km horizontally and vertically; • the area projects itself on a 100 × 100 grid on the Cartesian plane. The grid extends from the lower-left corner (0, 0) to the upper-right corner (100, 100). Every Cartesian unit corresponds to a geographical distance of 100km/100units = 1km (the ratio between the vertical span and grid’s height, or the horizontal span and grid’s width; the program checks that the two ratios are equal and raise an error if not). We assign to the area’s center the Cartesian coordinates (50, 50).
Let us suppose we want to obtain the Cartesian coordinates of another location: 44.7° latitude and 8.7° longitude. The program uses Vincenty’s inverse formula to compute the distance and azimuth between the area’s center and the other location.
We divide the distance between the two locations by the length of a Cartesian unit to obtain the Cartesian plane’s corresponding distance.
The azimuth is 0° in the north direction and increases going clockwise. Euclidean angles used in trigonometry start from the east direction and in-crease going anti-clockwise. To perform the conversion, we apply the formula:
angle = 90◦− azimuth
Having the Cartesian distance and the Euclidean angle, we perform a move-ment on the Cartesian plane applying the following formulae:
• x = x0+ cos(angle) × distance
• y = y0+ sin(angle) × distance
where x0 and y0 are the starting point’s Cartesian coordinates, in our case,
the area’s center.
We obtain the following values: • x = 25.985013684782366 • y = 16.37233868492173
By contrast, let us suppose that we want to convert the Cartesian coordinates (60, 70) into geographical coordinates.
We start by finding the distance and the angle between the center of the area (50, 50) and the other point. Then, we convert the Cartesian distance into the geographical distance by multiplying for a Cartesian unit’s length. To obtain the geographical azimuth, we apply the formula used earlier. We use Vincenty’s direct formula to compute the other point’s geographical coordinates from the area’s center, obtaining the following values:
• latitude = 45.17811256422445 • longitude = 9.125964776351518
We conducted a test to verify the flat model’s precision, consisting of drawing a shape on the Earth’s surface using the geoidal and flat models. The shape’s appearance is visible in figure 3.
We drew the shape at several latitudes and compared the results of the two models. We measured the distances from the positions computed on the geoidal model and the flat model, and we used them as an error measurement. Figure 4 summarizes the results.
Figure 3: Geographical precision test shape. The most inner segment is one kilometer long. Adjacent segments are equal in length or differ by one kilometer.
• The error often increases with latitude. Latitudes higher than 80° may produce an unacceptable error, even for short trajectories. The error for negative latitudes is symmetric.
• The error appears to be cumulative: longer trajectories may generate a more significant error. At 45° latitude, a trajectory 60 kilometers long may produce an error of about 30 meters, which is acceptable, approximately being an airliner’s length.
Figure 4: Error in our flat model test at various latitudes.
5.5
Algorithms implementation
5.5.1 Trajectory generation using A*
We produced an original Python implementation of the A* algorithm for our problem. This choice’s main reason was the necessity for dynamic graph generation and the main functions’ interchangeability. For instance, the user can change the Earth model without modifying the A* algorithm.
The pseudocode of the algorithm is in the Approach chapter. For clarity, we report a summary of the principal algorithm’s functions:
• it maintains the following data structures: a graph, a fringe, and a search tree;
• it uses a node generation function that generates one node’s successors, considering boundaries, no-flight zones, and performance constraints; • it uses a cycle detection function that checks for cycles on a specific
path and deletes them;
• it uses a termination function to check whether it should terminate. 5.5.2 A* performance improvements strategies
A* bounds It is possible to narrow the search area without excluding the sensitive receptors inside the original rectangular area. The algorithm uses the minimal reference rectangle formed by the start and goal positions, describing its diagonal. Any smaller rectangle would not be sufficient to contain the trajectory. The user can extend the minimal rectangle by some length in every direction (north, south, west, and east), depending on the scenario.
Using a narrower rectangle than the entire search rectangle provides a performance improvement that varies considerably depending on the config-uration and the sensitive receptors’ location.
When the sensitive receptors are between the initial and goal locations, our heuristic struggles. We can push the search towards the goal by narrow-ing the search space or applynarrow-ing a distance bias, described in the Approach chapter.
Figure 5: Reference image for the search area. To the left, the minimal reference rectangle. To the right, a custom search rectangle.
Discretization of locations Discretization is optional and requires using the flat model. When discretization is active, every point on the Cartesian plane, which results from a computation, is rounded to its closest integer point.
The discretization allows the algorithm to perform certain computations efficiently. When comparing positions, different positions rounded to the same point become equal. When the algorithm generates a new node, it checks for its existence in the search tree. If it had already generated the same node, it keeps only the one with the lower evaluation value. With dis-cretization, the algorithm excludes many close nodes, reducing the necessary iterations to reach the solution.
Here is an example of performance improvement thanks to discretization. Scenario:
• start position: 45.39° latitude, 8.81° longitude; start azimuth: 316.58°; • goal position: 45.61° latitude, 8.74° longitude; goal azimuth: 352.18°; • flat model;
• 70 sensitive receptors;
• center: 45.63° latitude, 8.723056° longitude; • span: 60 km horizontal, 60 km vertical. Performance:
• minimum turning radius: 3704 m (3 N.M.); • step size: 1852 m (1 N.M.).
The resulting route has 14 waypoints. We performed a bidirectional search on the minimal rectangle with horizontal coefficient 3 and vertical coefficient 1. At each iteration, the algorithm considers 7 different steps. The algorithm did not apply any distance bias.
Continuous 240 × 240 grid 120 × 120 grid Execution time 800.13sec 69.18sec 27.04sec
Iterations 10050 1063 449
Figure 6: Performance improvement discretizing locations. To the left, the continuous search on a 240x240 grid; in the center, the 240 x 240 grid discrete search; to the right, the 120 x 120 grid discrete search.
Bidirectional search Bidirectional search provides significant performance improvements over direct search. In the Approach chapter, we discussed how it reduces the worst A* complexity from O(bd) to O(bd2) and helps resolve
the receptors near the goal node problem. The following example shows the beneficial effect of using the bidirectional search.
Considering the previous paragraph’s scenario, we applied direct and bidi-rectional search to a 120 × 120 grid. We ran the program three times and averaged the execution times.
Iterations Exec. time Direct search 4116 152.99sec Bidir. search 449 27.04sec
Table 4: Performance improvement using bidirectional A* search Figure 7 shows that the two searches output slightly different results. This difference exists because direct and bidirectional searches use different termination functions: the first checks for proximity with the goal node, the latter with the opposite search tree. Imposing stricter termination conditions allows the two results to be closer at the expense of performance.
The performance gap between direct and bidirectional search can vary considerably depending on the scenario and the configuration. In this case, the sensitive receptors’ closeness to the goal position strongly disadvantages the direct search.
Ordered data structures The algorithm needs to process some data structures at each iteration.
Figure 7: Unidirectional and bidirectional A* search comparison. To the left, the direct search. To the right, the bidirectional search.
Specifically:
1. it checks if a just generated node exists in the graph;
2. if yes, it removes the worst one from the graph and repeats the check on the fringe;
3. it extracts the node with the lowest evaluation value from the fringe to expand during the next iteration.
Using nonordered data structures gives the search operation a complexity of O(n), where n is the number of the list’s elements, increasing with each operation. The three operations’ complexities are:
1. O(g) 2. O(f) 3. O(f)
where g is the number of nodes in the graph and f is the number of nodes in the fringe.
Keeping the graph and fringe ordered reduces these operations’ complex-ity since it allows using binary search, having a complexcomplex-ity of O(log n). [19] The program orders the fringe nodes by their evaluation value and the graph nodes using an aircraft’s state sorting criterion. The program compares
two nodes’ abscissa, ordinate, and then heading. If a comparison results in one value being smaller than the other, then the node with that value comes firsts. If all the values are the same, the nodes are equal.
With this sorting, the complexities become: 1. O(log g)
2. O(log f) 3. O(1)
The graph remains ordered since, checking for identical nodes, we also obtain the position to insert a new node. The fringe requires performing an additional binary search operation to keep it ordered, costing O(log f). 5.5.3 Trajectory optimization using nonlinear programming We implemented the nonlinear programming algorithm using the Python library SciPy.
SciPy allows choosing among many programming solvers. We chose Se-quential Least Square Programming (SLSQP), based on the Han-Powell quasi-Newton method. [20] It allows us to apply boundaries and nonlin-ear constraints, and to optimize a nonlinnonlin-ear objective function. Being an iterative approach, it features good performance.
The algorithm searches for the optimized values for different deltas that vary the route’s waypoints’ positions. Please refer to the Approach chapter for further details.
To perform the optimization, SLSQP needs an initial condition, i.e., an array of initial delta values.
The algorithm runs 25 times with different initial conditions and out-puts the best solution among the ones found. As discussed in the Approach chapter, this configuration allows us to mitigate the local minima problem.
We define two trajectory’s waypoints that we will call pivots. The dis-tances between the initial waypoint and the pivots are approximately 1/3 and 2/3 of the trajectory.
Then, we define five delta values to apply to the pivots. The values are all equidistant and span between the minimum and the maximum allowed values for delta.
We apply every possible pair of delta values to the pivots, generating all the initial conditions. The combinations are in total 25.
