C Morlaas

A Chabory

B Souny

G Hattenberger

Compact Helical Ring Antenna for Iridium Communication on UAV

Keywords: UAV antenna, small circular polarization antenna, Iridium antenna, helical ring antenna

The ENAC UAV team participates to a challenge named Fly2Corsica. The aim of this project is to link the French Riviera to the Corsica Island with a small electric UAV. To achieve a radio link between the French Riviera and Corsica (Fly2Corsica project), the ENAC UAV team plans to use the Iridium satellite service. To render this possible, a small antenna with good efficiency and pure circular polarization is required to optimize the link budget. We present an antenna that fulfils this requirements.

Introduction

The ENAC UAV team participates to a challenge named Fly2Corsica. The aim of this project is to link the French Riviera to the Corsica Island with a small electric UAV. The distance between both points is about 185 km. The endurance of the UAV is limited to about 4 hours : a compromise has been found between the speed and the consumption to fly near the maximal range point. A telemetry from the UAV is necessary all along the flight to get the flight information on the Ground Control Station. This is mandatory by the French Regulator to have the UAV position. The radio range of a GSM base transceiver station is too limited to maintain a transmission with the UAV. A solution is to use a satellite communication service like Iridium. To render possible the transmission between the UAV and the satellite with an optimal link budget, we need a small and light antenna with a good efficiency and circular polarization. The well-known commercial Iridium antennas are based on helix technology (SARENTEL SL3101) or on patch design (PN# 500644). In this article, we propose as an alternative solution an antenna that we have patented [START_REF] Souny | Antenne autodirectrice en polarisation circulaire -Self-directing antenna with circular polarisation[END_REF]. This antenna fulfils the requirements of the Iridium service. This antenna is constituted by a ring made of 8 metallic turns. With an appropriate feeding, the radiation can be oriented towards only the upper half-space with a pure circular polarization regardless of the nature of the support. Besides, its size can be reduced without using high dielectric materials which would increase the weight. This article is organized as follows. Firstly, the history of the Fly2Corsica project is described. Secondly, we explain the antenna principle with his design and his feeding. Then we present simulation results from which we deduce the performances in terms of radiation pattern, bandwidth, efficiency and size.

Project description and history

History of the project

Aircraft design

The design of this aircraft has been done using a homemade tool [START_REF] Bronz | Towards a Long Endurance MAV[END_REF][START_REF] Bronz | Flying Autonomously to Corsica: A Long Endurance Mini-UAV System[END_REF] that sweep over a wide range of settings such as wing span and wing area. One of the main constrain for the final wing span is the size of the battery pack. With tree cells of 275x55mm each, the only suitable location is inside the wing. This configuration almost forbids to have some dihedral on the wing, that would increase the natural stability of the plane. The directional and longitudinal stability is provided by a pretty large tail with a long arm from the centre of gravity, which makes it difficult to balance.

Autopilot system

The autonomous navigation and stabilisation system used for this mission is the Paparazzi System [START_REF] Brisset | The Paparazzi Solution[END_REF]5] developed at ENAC (Fig. 2). An autopilot board Tiny2.1 provides the attitude stabilisation, the navigation by means of a small GPS receiver, and a bidirectional link with the ground station. The ground station itself is a regular laptop that runs a set of programs including a graphical interface that allows to monitor and control the flight plan of the UAV. The modem we use for normal data link is a Xbee Pro 2.4GHz. Due to the French regulation, the emitting power is limited and for the first flight to Corsica, this link was lost after 3.6km despite of the use of a directional antenna on the ground.

GSM communications

For the first attempt, a GSM module was planned to be used as a secondary telemetry link to keep track of the plane after loosing the radio-modem connection. The choice of the GSM module (TELIT 864 GSM/GPRS) was made because of its small size and affordable cost. An other reason was that the planned track for the crossing is close to the commercial ferry line between Nice and Calvi, and that high gain GSM antennas are supposed to be oriented on this axis. This let us hope for a better range with the GSM module than the radio-modem. Two main drawbacks arise from this solution. First the GSM network is not covering the whole trajectory. It means that we would have lost the communication during the first attempt even without the other technical issues that led to the lost of the plane. The second issue is the size and weight of the commercial antenna we have used. It is a flap antenna of 110x20mm for 8 grams that needs to be hold vertically. Thus, the only possible location is inside the tail of the aircraft in order to avoid an increases of the drag. Despite of its small weight, the long arm between the tail and the centre of gravity increase the aft centring of the plane. The new design of the tail for the second attempt, with a bigger surface and a further position, without modifying the main body, makes it almost impossible to use such antenna.

For this reasons, the opportunity to use a Iridium modem has been studied. This solution would allow to maintain the communication during all the flight. An other reason to consider this option is that Iridium modules are getting smaller every year and they are now fitting inside the main fuselage of the plane. The remaining issue is the antenna that still need to be as small as possible, with a good efficiency and the possibility to place them close to the centre of gravity. The design of this antenna has been done by the LETA team from ENAC.

Antenna Principle

Half-directivity

To obtain directivity we combine two radiating modes, both with a torus radiation pattern and a circular polarization. We assume that the first torus is oriented along the x-axis, whereas the second is oriented along the y-axis. If there is a phase shift of ±90 degrees between them, one can prove that the total radiation will be null, (resp. maximal) in the +z-direction, maximal (resp. null) in the -z-direction (Fig. 3).

direction of the null and maxima depends on the sign of the phase shift while the direction of the circular polarisation depends on the direction of the winding turns.

3: Half-directional radiation pattern

To obtain the first torus radiation pattern (along the xaxis) with a circular polarization, , a solution consists in a magnetic dipole and an electric dipole, both collocated and aligned with the x-axis [START_REF] Wheeler | A helical antenna for circular polarization[END_REF][START_REF] Kraus | The helical antenna[END_REF] (Fig. 4). Both dipoles present a natural phase quadrature and their magnitude can be equalized by tuning the length S of the electric element and the diameter D of the loop. For an axial ratio equal to unity, this yields the simple relation πD= 2S λ The second torus radiation pattern (along the y-axis) with a circular polarization can be obtained in the same way. Thus, the two radiating modes can be obtained via two helical antennas oriented along the x and y axis.

We can collocate the two helical antennas by using a helical antenna, which shape is either a ring, a square, or a cross.

In order to prevent unwanted mode coupling, we choose to employ the ring shape. When the number of turns is a multiple of four, we have an invariance of the structure under rotation of 90°.

In Fig. 5 an example of an 8-turns design is given.

Figure 5: Antenna structure

Antenna feeding

For the antenna feeding, a solution is to use two feed probes placed on the x-and y-axis to excite the two orthogonal modes [START_REF] Souny | Compact selfdirectional antenna based on a helical ring[END_REF]. The phase shift between both probes allows to control the direction of the radiation. This can be realized by means of an 3dB hybrid splitter. The sense the circular polarization corresponds to the left-hand or right-hand orientation of the helix. Alternatively, only one feed probe can be used by adding an internal metal piece to realize a controlled mode coupling. This coupling element is inserted so as to obtain the quadrature excitation. To do so, the element is placed at ±45° from the position of the feed probe, with a ± sign chosen to orient the radiation towards the direction ±z.

In this article, we use only one feed probe that is electrically coupled to the antenna by means of a metallic disk placed below the ring. A magnetic coupling would also be possible using classical loops. Electric coupling with one probe is chosen here because it yields a simpler design without extra components.

Antenna design.

For a fixed number of turns, the frequency is matched by adjusting the diameter of the ring, the height of the turns and the distance between the ring and the metallic disc.

The circular polarization is matched by adjusting the height of the turns to the diameter of the ring, and from the coupling piece between both modes. Note that the antenna efficiency depends on its final size: the smaller the size is, the smaller the bandwidth and efficiency are. Nevertheless, As explained in [START_REF] Pigeon | Highly Compact Composite Antenna[END_REF], this size can be strongly reduced compared to a half-wavelength antenna without high dielectric materials inclusion.

In [START_REF] Pigeon | Highly Compact Composite Antenna[END_REF], we have also shown that, in such structures, the field remains mainly confined inside the helical part.

Hence the sensitivity of this antenna to its surrounding is low.

Finally, the proposed antenna is of height 11.5mm and diameter 20mm.

Simulation results

The simulations are performed with Ansoft HFSS.

display in Fig. 6 the 3D radiation pattern. As expected, the antenna is half-directional, i.e. it only radiates towards the half space z > 0.

The maximal right-hand circular polarized (RHCP) gain is of 3.5dBi. The antenna is designed to have a beamwidth wide enough so as to maintain good performances of the antenna even at low elevation angles. This is due to the configuration of the Iridium constellation. In Fig. 7, the radiation pattern in the x0z plane is represented for both RHCP and the LHCP gain.

In the 0z direction, the front-to-back ratio is 9.4dB and can be improved by optimizing the design of the antenna. In Fig. 9, the axial ratio is plotted in the x0y plane at the minimal, central and maximal values of the frequency band, i.e. at 1.6, 1.613, and 1.626Ghz, respectively. We observe that the radiation is almost purely RHCP regardless of the direction of observation. At zenith (+z), the axial ratio remains smaller than 1.5 in all the bandwidth. For low elevation angles, where some Iridium satellites may be located, the performances in terms of circular polarization remains very good. Weight: to be estimated according to the technology used This antenna has not been realized yet. Nevertheless, a four turn prototype has already been constructed to confirm the presented properties, ie, the self-directivity in an half space with good circular polarization radiation.

The great interest of this compact helical ring antenna technology is its immunity to de-tuning in the presence of surrounding materials, like metallic or dielectric support when it will be mounted on the UAV.

The performances in terms of efficiency and polarization will remain satisfying regardless of the constellation configuration, allowing the antenna to maintain a connection during all the flight.

Conclusion

A new structure of antenna has been proposed to achieve a half-directional pattern without any reflector and with a very good right-hand circular polarization. Besides, since the electromagnetic fields are highly confined inside the helical part without extra materials like ceramic dielectric, this antenna presents a low sensitivity to its environment for a light weight. These properties render this antenna highly adapted to be integrated on an UAV to perform a long range connection using the Iridium satellite services.

Fly2Corsica

  project has started as a collaborative student project between ISAE and ENAC in 2009. The objective is to fly from the French Riviera to Corsica with the smallest possible electrically-powered UAV. The chosen trajectory is to go from Menton to Calvi, which represent a distance of approximately 185km, at an altitude of 100m above the sea. A first attempt has been made in June 2010 without success. An other attempt is planned for June 2011, with noticeable improvements for the protection of the flight envelope of the aircraft. The latest version of the plane, called Spirit Of Corsica, is shown in Figure 1. It is a 1.5m wing span aircraft. The weight is around 2kg and more than half of it is coming from a 3-cells Lithium-Polymer battery of 210Wh.

Figure 1 :

 1 Figure 1: Spirit Of Corsica

Figure 2 :

 2 Figure 2: Paparazzi System overview

Figure 4 :

 4 Figure 4: Co-located magnetic (M) and electric (J) dipoles

Figure 6 :

 6 Figure 6: Antenna RHCP gain pattern (dBi)

Figure 7 :

 7 Figure 7: Antenna RHCP and LHCP gain pattern (dBi)

Figure 8 :

 8 Figure 8: Smith chart of the antenna reflection coefficient (S11)

Figure 9 :

 9 Figure 9: Antenna axial ratio at the minimal (blue dashed curve), central (continue red curve), and maximal (magenta dashed curve) frequencies of the bandwidth


DSNA Nicolas Durand

Cyril Allignol

Nicolas Barnier

A GROUND HOLDING MODEL FOR AIRCRAFT DECONFLICTION

In the SESAR traffic growth predictions, traffic complexity will become an issue that the current Air Traffic Management organization is not able to handle. The 4D trajectory concept offers new perspectives for deconflicting the traffic by groundholding aircraft before they take-off. This paper studies the possible complexity reduction achievable by optimizing the aircraft take-off times. Therefore a simple model is introduced to detect pairwise 3D possible conflicts and define conflicting takeoff time differences. Two resolution algorithms are tested on a real traffic data sample collected in the French airspace. The first one is based on a Constraint Programming model of the problem and ensures the optimality of the maximum delay required to solve every conflict. The second one uses an evolutionary computation algorithm to minimize the mean delay among the aircraft population. A sliding window model is introduced to reduce the size of the problem and to regularly update the current situation. Experimental results performed in the French airspace with fast time simulation show that with perfect 4D trajectory, every conflict over flight level 290 can be solved by delaying less than a quarter of the traffic within a range of delays varying from 1 to 90 minutes and a mean delay of 4 minutes. The Constraint Programming approach gives better results than the evolutionary computation approach. Adding uncertainty around 4D trajectories dramatically degrades the results.

Experimental results

J. Evolution of the problem size

Simulations were performed using real flight plan data on the Complete Air Traffic Simulator (CATS) developed by the French DSNA. Simulations were

Introduction

The SESAR program is anticipating the future growth of air traffic in Europe. In this context, the Episode 3 [START_REF] Graham | Preparing an initial assessment of the SESAR concept of operations "EP3: Single european sky implementation support through validation[END_REF] project has aimed at assessing the performance of new ATM concepts, such as 4D trajectory planning and strategic deconfliction. ATC performances in Europe are limited by the hourly capacity constraints defined on each en-route ATC sector to limit the rate of entering aircraft. The current ground holding slot allocation process ensured by the CFMU (Central Flow Management Unit) allocates departure slots (that must be respected within a -5/+10 minutes margin) in order to respect these limits. Much research has been conducted to optimize the CFMU algorithm [START_REF] Dalichampt | Innovative slot allocation (ISA)[END_REF], [START_REF] Barnier | Slot allocation with constraint programming: Models and results[END_REF]. However these approaches did not address the conflict pair resolution problem, but only try to respect sector capacity limits not necessarily related to the traffic complexity [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF].

In the context of 4D trajectories, solving conflicts far in advance might become possible and prevents from defining complexity indicators that are hard to validate. Current equipment does not allow aircraft to fly perfect 4D trajectories and the results obtained in this arcticle can only give a theoretical cost of complexity reduction. The Air Traffic Management System will probably always need to be structured with different levels of granularity and time horizons in order to be able to handle uncertainties, unpredictable events and emergencies.

In the following sections, we briefly introduce the related work and the context of the research project. Then we give a description of the model chosen. Next we introduce the Evolutionary Computation approach and the Constraint Programming model that are compared using real data in the following section. The last section deals with sensitivity of the results to uncertainties. We conclude by outlining the further work that needs to be adressed to enhance the approach.

Related Work and Context of the Study

Many results were obtained using Constraint Programming (CP) approaches in the air traffic management domain. [START_REF] Barnier | Slot allocation with constraint programming: Models and results[END_REF] has for example introduced a new approach to address the sector capacity constraint that prevents the peak effect due to the usual definition of sector capacities (number of aircraft entering a sector per time period). CP approaches have also been successfully used to optimize the number of flight levels necessary to separate the routes having the biggest traffic flows [START_REF] Barnier | Graph coloring for air traffic flow management[END_REF]. Evolutionary algorithms have been successful in many different applications, such as short term conflict detection and resolution ( [START_REF] Durand | Optimal resolution of en route conflicts[END_REF], [START_REF] Mondoloni | An airborne conflict resolution approach using a genetic algorithm[END_REF]), 3D conflict free network definition ( [START_REF] Gianazza | Separating air traffic flows by allocating 3d-trajectories[END_REF], [START_REF] Riviere | Redesign of the european route network for sector-less[END_REF]) or taxiing optimization on big airports [START_REF] Gotteland | Genetic algorithms applied to airport ground traffic optimization[END_REF]. All these problems involve large data sets, are combinatorial, and deal with a large number of constraints that are difficult to handle with classical optimization methods.

In Europe, en-route sector capacities are limited below bounds defined over given time periods (usually one hour) by local experts, the Flow Management Position (FMP) Controllers in each Air Traffic Control Center (ATCC). The CFMU first identifies the overloaded sectors with the CFMU pre-tactical tool for network optimization PREDICT. The Computer Assisted Slot Allocation (CASA) tool [START_REF]Basic CFMU Handbook -General & CFMU Systems[END_REF] computes a slot allocation for some aircraft involved in the most constrained areas. CASA is able to deal with many operational constraints and updates, but is based on a greedy algorithm that cannot guarantee a solution that satisfies all the constraints or that is optimal.

The traffic complexity is difficult to measure and the sector capacities, expressed as a number of aircraft entering the sectors over a time period do not necessarly reflect the controller's workload. Gianazza [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF] compared this measure to the moments when subsets of sectors are split or merged and showed very different complexity profiles. Recent work such as [START_REF] Flener | Air-traffic complexity resolution in multi-sector planning[END_REF] uses a more precise and complex CP model to balance the traffic over the sectors in a control center of the upper airspace. Barnier [START_REF] Barnier | Application de la programmation par contraintes à des problèmes de gestion du trafic aérien[END_REF] used CP to optimize the sectors opening schedules to match more closely the predicted traffic. Baptiste and Tan Dac [START_REF] Dac | Airspace sectorization by constraint programming[END_REF] also used CP to redesign airspace sectorization with a better balancing.

In this paper, we propose to estimate the cost of directly solving all conflicts in the upper airspace with ground holding, provided that aircraft are able to follow their trajectories accurately. Therefore we introduce a model of this large scale combinatorial optimization problem based on a sliding window principle.

Modeling the problem

In the model, aircraft estimate their 4D trajectories a few minutes before departure and send them to a centralized unit that first detects 3D pairwise potential conflicts and check if the aircraft takeoff times are compatible. In many situations, no 3D conflicts occur, or the current take-off times of the pair of aircraft are not conflicting. When a 3Dconflict occurs, the difference of take-off times creates a constraint between the aircraft pair concerned. Clusters of conflicts are the transitive closure of the potential 3D-conflict pairs.

A. Conflict Detection

Real traffic data are provided by the CATS1 simulator [START_REF] Alliot | CATS: A Complete Air Traffic Simulator[END_REF], which takes as input all of the flight plans in a given airspace for a given day of traffic, and outputs the corresponding 4D trajectories.

To detect all "significant" conflicts, CATS discretizes trajectories with a δt = 15 s time step, which is small enough to detect every conflict.

Trajectories are then probed pairwise2 for potential conflicts, ignoring those that could only occur for greater delays than the given maximal one ∆ max . The separation norm is thus tested for each pair of points of the two probed trajectories (up to p = 1300 points per trajectory for up to n = 9500 flights in O(n 2 p 2 ), as observed in the largest instances simulated by CATS) as illustrated on figure 1 in the horizontal plane. Note that trajectory enclosing bounding boxes or sweep line techniques [START_REF] Berg | Computational Geometry -Algorithms and Applications[END_REF] could be used to lower the detection complexity, but it is here considered as a static data production phase and its efficiency is not a primary concern of the present study.

Though the maximal allowed delay ∆ max can be seen as a parameter of the search algorithm only, it also affects conflict detection. Indeed, when the maximal allowed delay is increased, the size of the problem grows as well, as more and more flights tend to be in potential conflict. Ultimately, if a 24 h-delay would be allowed, the conflict detection could be done regardless of time, as any two spaceconflicting trajectories would generate a constraint. So, whenever a particular instance has been proved inconsistent, it has to be generated again with higher values of the maximal delay, which will capture later potential conflicts on the trajectory pairs and increase the size of the instance. Operationally, flights originating outside the Eurocontrol countries cannot be delayed, so their delay variable will be fixed to 0 in our constraint model, reducing the number of variables but tightening the constraints as well and offering less opportunities for optimization. Constraints corresponding to conflicts occurring between two such flights will of course be discarded as we cannot delay the flights to solve them. Such remaining conflicting cases would have to be taken care of by other ATC or ATFM techniques that will not be addressed in this study.

B. Conflicts Constraints

To compute the constraints of our model, the trajectories (up to 9500 flights for one day of traffic in the French airspace) are pairwise probed for couples of conflicting points.

We define a set D of decision variables:

D = {δ i , ∀i ∈ [1, n]}
of finite domain [0, max_delay] that represents the delay associated with each of the n flights (between 6000 and 8000 after processing for our experiments). The value of max_delay is typically chosen as 90 min and increased as needed when no solution is found (up to 300 min in our experiments). As explained in the previous section, the size of the instance grows with max_delay.

It was shown in [START_REF] Barnier | 4d-trajectory deconfliction through departure time adjustment[END_REF] that pairwise conflict constraint could be expressed in the following way: if δ i and δ j are respectively the delays of aircraft i and j then aircraft i and j are not in conflict if

d ij = δ i -δ j ∈ [lb 1 , ub 1 ] ∪ . . . ∪ [lb q , ub q ]
where [lb k , ub k ] are time intervals representing different possible conflict zones between the two aircraft. Most of the time, q = 0, which means that the two trajectories are not conflicting or q = 1 which means that they have one conflicting zone. When a pair of flights are conflicting on several disjoint times over their entire trajectories (as illustrated on figure 2), q > 1. 1) Further Instance Processing: The takeoff and landing part of trajectories are truncated around airports within a given radius (usually 10 NM) as the traffic is considered to be handled with specific procedures by the TMA control services in these zones.

After the computation of the conflict constraints, the whole instance is scaled down to a more reasonable time step than the 15 s used during conflict detection. We ensure that the original forbidden intervals are strictly included in the scaled ones, with appropriate interval arithmetic operations which can possibly merge conflicting disjoint intervals. A 1 min time step was chosen for the resolution: a smaller time step would not have been realistic for a departure time, whereas a greater one would have reduced the set of feasible solutions. Furthermore, a 1 min time step seems compliant with the SESAR objectives of ±3 min precision for takeoff time.

In addition, the flight level of the detected conflicts were filtered, for example to only take into account conflicts occurring within the upper airspace (from FL290 and above). The minimal and maximal altitude of each conflict is recorded during the detection stage and a conflict is discarded if it entirely occurs below or above the specified airspace slice.

It is also possible to filter the time interval during which the conflicts may occur, taking the time bounds of the allowable delay into account. Any conflict strictly occurring outside the given time interval is then discarded.

Eventually, all the flights that do not have any conflict with any other flight are withdrawn from the instance.

2) Conflict Extension: To improve the robustness of our solutions towards uncertainty on the departure times of the flights, we add an extra parameter ext that extends conflicting intervals by a fix amount of time. Such an extension of ext minutes the start and the end of a conflict will be able to manage uncertainties of ± ext 2 minutes on the departure slot (see the last section), at the price of an increase in the cost of the solutions.

We expect that this extension scheme may as well be able to diminish the effects of other sources of uncertainty (e.g. vertical and ground speed) regarding the number of remaining conflicts during simulation.

C. A Sliding Forecast Time Window model

In order to limit the size of the problem and to be reactive to uncertainties, the whole day is not treated at once, but only aircraft scheduled for takeoff during the next T w minutes are considered. T w represents the lookahead time also called forecast time window. The situtation is reconsidered every σ minutes with σ << T w . σ is the time step used in the model to make the T w time window slide. This approach ensures that the problem can be updated every σ minutes : if an aircaft needs to cancel or delay its departure for external reasons, it will be able to free its slot and be reconsidered later on. Aircraft that are already airborne at the current time are taken into account as constraints. This is also the case for aircraft scheduled in the next A n minutes (see figure 3) because an advance notice time is required to assign any delay to an aircraft. In practice, this advance notice time A n can be longer or shorter than σ. In the numerical results, this value was set to 0 because it does not affect the quality of the solution. Figure 3 gives an example of the evolution of an aircraft take-off slot when the forecast time window slides. At the first step (current time=0) the aircraft is delayed to take-off at T 1 . Because T 1 is far enough from the current time (more than A n + σ minutes ahead, in the dotted zone), the slot will still be modifiable when the current time is σ (second line). When the time window slides (current time=σ), the delay might be reduced and a slot chosen at T 2 which is still modifiable. At current time 2 σ the delay can be reduced again and a slot chosen at T 3 which belongs to the notification zone. After this current time (2σ) no modification is possible because at the next step (current time=3σ), the take-off slot will be too close to the current time (less than the advance notice required). The size of the forecast time window is an important parameter. If it is too big, the size of the problem will include a very large number of variables and the resolution might be more difficult. If it is too small, the solutions found might be worse and the total delay induced over the day much higher. This will be debated in the results section.

Evolutionary Computation Approach

Classical Evolutionary Computation principles such as described in the literature [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF], [START_REF] Michalewicz | Genetic algorithms + Data Structures = Evolution Programs[END_REF] were used for this approach.

D. Fitness function

The cost function used in this part is simply the sum of the delays over the aircraft population.

Solutions respecting the separation constraints cannot be built easily. Consequently, we need to include the separation criteria in the fitness function.

The fitness function chosen is:

F = n -n i=1 ( δi δmax ) 1 + nrc
where n is the number of aircraft and nrc is the number of remaining conflicts.

The fitness function increases when the number of remaining conflicts and delays decrease. It takes its values in [0, n].

E. Crossover operator

The conflict resolution problem is partially separable as defined in [START_REF] Durand | Genetic crossover operator for partially separable functions[END_REF], [START_REF] Durand | Automatic aircraft conflict resolution using genetic algorithms[END_REF]. In order to increase the probability of producing children with a better fitness than their parents, principles applied in [START_REF] Durand | Genetic crossover operator for partially separable functions[END_REF] were used. For each aircraft i of a population element, a local fitness F i value is defined as follows:

F i = 1 -( δi δmax ) 1 + nrc i
where nrc i is the number of remaining conflicts involving aircraft i.

Figure 4 presents the crossover operator. First two population elements are randomly chosen. For each parent A and B, fitness A i and B i of aircraft i are compared. If A i < B i , the children will take aircraft i of parent A. If B i < A i , the children will take aircraft i of parent B. If A i = B i children randomly choose aircraft A i or B i or even a combination of A i and B i .

F. Mutation operator

For each candidate to mutation, the delay of an aircraft having one of the worst local fitnesses is modified. If every conflict is solved, an aircraft is randomly chosen and its parameters changed. In practice, a number m is randomly chosen in the interval [1, n 2 ] and we pick up m times an aircraft to find the most constrained aircraft among these m trials. The delay of this aircraft is then either locally optimized or randomly modified with a probability of 50%. We could be tempted to always locally optimize the delay of the worst aircraft, but this would make the algorithm become very deterministic and lead to a premature convergence of the algorithm.

The crossover and mutation operators are more deterministic during the first generations because there are many conflicts to solve. They focus on making feasible solutions. When the solutions without conflicts appear in the population, they become less deterministic.

Sharing:

The problem is highly combinatorial and may have many local optima. In order to prevent the algorithm from a premature convergence, the sharing process introduced by Yin and Germay [START_REF] Yin | A fast genetic algorithm with sharing scheme using cluster analysis methods in multimodal function optimization[END_REF] is used. The complexity of this sharing process has the great advantage to be in n log(n) (instead of n 2 for classical sharing) if n is the size of the population. The distance used to compare two population elements p and q is:

D = n i=1 |δ p i -δ q i | n

G. Parameters

In the experiments, the following parameters were empirically chosen: the size of the population was set to 100, 20% of the population is crossed, 60% is muted, the selection uses the stochastic remainder without replacement. A sharing process is used. As time to solve a problem is limited, the number of generations is limited to 500.

Constraint Programming strategy

H. Cost Function

For this approach, the cost is simply defined as the maximal allocated delay, to ensure equity among the various postponed flights:

cost = max{δ i , ∀i ∈ [1, n]}
However, the overall sum of the delays is of utmost importance as well for the quality of a solution and we will take it into account within the search strategy to provide realistic max-optimal solutions during the resolution of the problem.

I. Search Strategy

The constraints of the problem are reminiscent of the disjunctive mutual exclusion constraints often used to model scheduling problems [START_REF] Baptiste | Constraint-Based Scheduling, Applying Constraint Programming to Scheduling Problems[END_REF]. At a coarse grain, we could consider each conflicting area as a machine on which to process two tasks of different lengths (depending on the speed of the aircraft). Several conflicts along a trajectory could even be seen as the ordered tasks of a given job, as in the Job-shop Scheduling Problem (JSP).

However, the comparison does not hold much further. First, the time intervals between any two conflict-tasks of the same trajectory are fixed, as only one delay variable is associated with each flight (unlike the JSP where all tasks are only related with precedence constraints). Second, to consider a potential conflict in three dimensions only, as the transitive closure of the overlapping conflicting segments, with task lengths proportional to the time spent by the aircraft within the area, is misleading. In this setting, the conflict associated with two catching-up flights on the same route would be the entire trajectory, preventing them from being airborne at the same time! Obviously, our model is much more precise and allows two aircraft on the same route to be separated by 5 NM only. Third, the number of "conflict machines", if not quadratic in the number of "flight jobs" as it could ultimately grow for arbitrary instances, is quite large and cannot be easily related with any known standard scheduling problem.

Nevertheless, the branching scheme of our search strategy to solve this essentially disjunctive problem is inspired by standard scheduling techniques.

For instance, trying to start the search by directly labelling the delay variables δ i may impede the search because of thrashing (i.e. repeatedly fail over the same constraint), as the constraints are expressed over the differences d ij . In this case, a more efficient filtering can be obtained by feeding the propagation of the arithmetic constraints with new domain bounds for the d ij auxiliary variables.

In this respect, our search strategy first tries to order pairs of conflicting flights by adding the constraint d ij < lb or d ij > ub in the case of a single conflicting interval. If there are several holes in the domain of d ij , branching is repeated with the bounds of the remaining holes. The variable d ij with the highest sparsity, i.e. the smallest ratio between the domain size and the difference of the domain bounds, is chosen first for branching.

To compensate for the cost being defined as the maximal delay only, disregarding the total amount of time, we choose to branch first within the d ij interval corresponding to the minimum potential increase for its delay variables δ i and δ j . Such an interval would be the closest to 0, while if d ij were far from 0, then at least one delay would be large. Whenever the search backtracks over such a decision, this interval is discarded and we branch on the next one recursively.

When all conflicts are ordered and there are no more holes in the domain of the d ij , we start labelling the decision variables δ i with a standard dom/deg selection heuristic: the variable with the smallest domain, and the highest number of constraints in case of tie, is dynamically selected. Then, the values closest to 0 are probed first to attempt to keep the total amount of delay as low as possible.

After the first solution is found, the branch and bound algorithm proceeds by dichotomy on the cost domain to find the optimal solution with respect to minimization of the maximal allocated delay, while keeping low the overall amount of delay thanks to the search strategy.

run on the French airspace on a heavy day of traffic (October 10, 2008). Figure 5 shows the evolution of the number of aircraft that can be delayed during the day, with different forecast time windows. The problem sizes increase until 5 a.m. and reach a peak at 8 am. They decrease at the end of the day when the traffic starts decreasing. 8 different time windows were tested from 15 to 360 minutes and also considering the whole day at once (1440 minutes). Figure 6 shows that the number of aircraft that can be delayed (dotted line) and the total number of aircraft (solid line) at the peak hour (8 am) grow linearly with the forecast time window width (in minutes). Simulation results also show that it is not possible to separate the traffic into smaller problems that can be solved independently because the 3D-traffic clusters generally involve most of the current traffic, especially during peak hours.

K. Comparison of results with no uncertainty

Table I gives the number of aircraft delayed, the maximum delay, the total sum of the delays, the mean delay over the delayed aircraft, and the computation time (on an Intel Xeon 2.66GHz processor) for different time windows. In the simulation, only conflicts over F L290 were considered, and σ = 15 min. The problem had 6184 variables over the day for 8693 flights.

With the CP approach, all the conflicts can be solved by delaying less than a quarter of the aircraft. The mean delay is smaller than 4 minutes and the maximum delay smaller than 88 minutes. When increasing the Forecast Time Window T w the mean delay decreases but the computation time increases.

With the EC approach, all the conflicts can be solved by delaying less than a fifth of the aircraft. The mean delay is close to 7 minutes for T w = 30 min but it increases with T w . An explanation could be that when the size of the problem increases the EC algorithm does not converge as easily to a good solution and returns a solution that is worse than when the size of the problem is smaller. The computation times are much higher than those obtained with the CP approach.

Results show that the CP approach is much more efficient in time resolution, total and mean delay, but tends to delay more aircraft than the Evolutionary Computation approach. The maximum delay is slightly higher in the EC approach. The resolution time increases with T w in both approaches but the growth is higher for the EC approach.

L. Influence of uncertainty

Uncertainties on take-off times are very frequent and can be caused by many different factors. In order to make the previous approach robust to uncertainties, we need to prevent aircraft from being in conflict even if their take-off times are not precise. Therefore the value of the ext parameter (described in the modeling section) in the model should be increased.

Table II compares results for different values of ext with a 90 minutes sliding time window or for the whole day (1440 minutes) of traffic.

An uncertainty of ±1 minute (ext = 2) requires to delay more than twice as many aircraft as with no uncertainties, with the CP approach. With the Evolutionary Computation approach, the number of aircraft delayed is almost twice the number found with no uncertainties. The delay increase is huge (9 times for the CP, and 8 times for the EC). For ext = 4 (uncertainty of ±2 minutes on the take-off time), delays obtained with the CP approach are far too big to be acceptable in a real context. The EC algorithm cannot even solve every conflict within a reasonable computation time.

The target figures for efficiency within SESAR are:

• at least 98% of flights departing on time (ontime departure being defined as actual departure less than 3 min before or after scheduled departure),

• the average departure delay of delayed flights must not exceed 10 min. The first target would correspond to ext = 6 minutes. Our results show the limits of the concept. In order to meet this target, we probably need to combine our strategy to others such as, for example, an efficient flight level allocation in order to separate the main flows of aircraft.

Conclusion

This article introduces an original ground holding approach to solve all potential conflicts occurring above a given flight level a few hours or minutes in advance with a sliding window model. Rather than trying to respect sectors capacities constraints, we model each possibly conflicting situation between any two aircraft and impose adjustements of departure times to keep them separated, with the hypothesis that aircraft could precisely follow their planned 4D trajectories. The resulting problem size can be reduced by only looking at the next T w minutes and reconsidering the situation every σ minutes.

Two different algorithms were compared to allocate the delays to aircraft. The first one is an evolutionary algorithm that uses the partial separability of the problem to define efficient crossover and mutation operators. The other one is based on a Constraint Programming (CP) approach and uses the FaCiLe constraint library developed at ENAC. It is based on a branch and bound algorithm that minimizes the maximum delay on every aircraft.

Simulations were performed using real flight plan data on the Complete Air Traffic Simulator (CATS) developed by French DSNA. Simulations were run on the French airspace on a heavy day of traffic (October 10, 2008) focusing on conflicts over Flight Level 290. The sample dealt with 8693 flights that generated 1418 conflicts above FL 290. Results using the Constraint Programming approach are better than those obtained with the Evolutionary Algorithm. They show that every conflict could be solved by delaying 22% of the flights with a mean delay of 4 minutes and a maximum delay of 84 minutes.

We have also presented a first step toward taking uncertainties into account by extending the forbidden intervals of conflicting flights. However, an extension as small as 4 min, which is able to cope only with a 2 min uncertainty on the departure time generates tremendous amounts of delays, far above SESAR performance objectives. We plan to overcome these issues and further assess the possible outcomes of 4D trajectory planning in the context of Episode 3 WP4 and address larger (European) instances with various techniques like combining our delay algorithm with a prior flight level allocation, repeatedly solving the problem on a sliding time window or solving the remaining conflicts with a CATS resolution module.

This research is a primary approach to reduce the traffic complexity by solving conflicts with ground holding. Simulations on real data showed that most conflicts could be solved by ground holding aircraft in a 4D trajectory context. However the model remains very unrealistic since it does not take into account many uncertainty parameters. For example winds can largely modify the trajectory predictions. Further work is currently being done on the robustness of such solutions, that can be achieved by reducing the update frequency of the model and increasing the size of forbidden take-off time intervals.

Figure 1 .

 1 Figure 1. Detection of conflicting points.

Figure 2 .

 2 Figure 2. Three potential conflicts between two flights: one near Paris airport at low altitude and two other en-route at the cruising altitude of the lower flight. The gray scale corresponds to time (in minutes) along the trajectory, the lighter the later.

Figure 3 .

 3 Figure 3. Sliding forecast time window.

Figure 4 .

 4 Figure 4. Crossover operator

Figure 5 .

 5 Figure 5. Evolution of the problem size for different forecast time windows.

Figure 6 .

 6 Figure 6. Total number of aircraft (solid) and problem size (dotted) at 8 am as a function of the forecast time window size.

The Complete Air Traffic Simulator developed at DSNA/DTI.

Note that the conflict detection for two given flights is symmetrical, so that only ordered pairs are considered.


Nicolas Barnier
email: barnier@recherche.enac.fr

Cyril Allignol
email: allignol@tls.cena.fr

Traffic Management Research and Development Seminar (ATM2011)

Keywords: Flight Level Allocation, Ground Holding, Deconfliction, Constraint Programming

As acknowledged by the SESAR program, current ATC systems must be drastically improved to accommodate the predicted traffic growth in Europe. In this context, the Episode 3 project aims at assessing the performance of new ATM concepts, like 4D-trajectory planning and strategic deconfliction.

Building on a preliminary ground holding algorithm aimed at directly solving all conflicts (instead of satisfying sector capacity constraints), a prior flight level allocation program is used to reduce the complexity of the traffic input, dramatically improving the quality of the solutions.

We present Constraint Programming (CP) models of these large scale combinatorial optimization problems and the encouraging results obtained with the FaCiLe constraint library. However, our approach does not yet address uncertainties and we plan to overcome this issue by improving the robustness of our conflict model and iteratively solving the problem over a sliding time window.

I. INTRODUCTION

In an already saturated European sky, the predicted growth of air traffic volume urges to improve Air Traffic Management (ATM) efficiency, as attested by the ACARE Strategic Agenda 2 [START_REF]Strategic research agenda 2[END_REF] and the European Single Sky program SESAR. Current ATM optimization strategies, like reducing the size of control sectors or the distance of separation (RVSM, P-RNAV), seem to have reached the structural limits of the system, while the automation of Air Traffic Control (ATC) has known few significant improvements over the last decades [START_REF] Garot | Failures in the automation of air traffic control[END_REF].

In this context, the European Commission has launched the Episode 3 [START_REF] Graham | Preparing an initial assessment of the SESAR concept of operations "EP3: Single european sky implementation support through validation[END_REF] research project to assess the concepts studied within SESAR definition phase. Among the key concepts identified to meet SESAR performance objectives, the planning of 4D-trajectories would allow to increase en-route capacity, while preserving the current level of safety. One of the goals of the WP4 of Episode 3 is to estimate how such regulations could benefit strategic deconfliction schemes over the current Air Traffic Flow Management (ATFM) process.

Currently, the Central Flow Management Unit (CFMU) in Brussels is in charge of optimizing the traffic by, among other strategic or tactical measures, delaying departure slots for the flights involved in overloaded enroute sectors. The purpose of this ground holding scheme is to respect the en-route capacity constraints provided by each ATC Centre (ATCC) as a number of aircraft per hour, according to their daily schedule. Former studies like [START_REF] Dalichampt | Innovative slot allocation (ISA)[END_REF], [START_REF] Barnier | Slot allocation with constraint programming: Models and results[END_REF] aimed at improving this slot allocation over the greedy algorithm used at the CFMU. However, one of the limitations of this regulation model is that the definition of sectors capacities (hourly rate of aircraft entering the sector) is poorly related to the complexity of the traffic with respect to the controllers workload, as assessed by [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF].

Therefore, in [START_REF] Barnier | 4D-Trajectory deconfliction through departure time adjustment[END_REF] we proposed to directly solve by ground holding the potential conflicts occurring between any two intersecting trajectories instead of trying to satisfy en-route capacity constraints. A single delay would be associated with each flight such that all potential conflicts occurring above a given flight level would be avoided. This very fine grain model generates much larger constraint sets than the macroscopic (at the sector level) capacitated ones, but guarantees conflict-free trajectories all along the flight path. This scheme proved to generate acceptable delays (w.r.t. CFMU figures) if no uncertainty on the takeoff times is taken into account, but they dramatically increase otherwise.

Regulation with ground holding benefits from only one degree of liberty (time), but 4D-trajectories could be deconflicted along the spatial dimensions as well. If we leave to airlines the choice of the flight paths of their flights, there still is the cruise altitude, or flight level (FL), on which allocation schemes could attempt to deconflict the traffic. Previous works like [START_REF] Letrouit | Optimisation du réseau de routes aériennes en Europe[END_REF], [START_REF] Barnier | Graph coloring for air traffic flow management[END_REF] present approaches to optimize the flight level allocation within a direct route network to avoid conflicting flows, but without trying to optimize on delays as well. Trying to solve the deconfliction problem simultaneously on both dimensions, with such large instances as the French or European traffic, is still out of reach for current combinatorial optimization technology, but it is possible to combine the two kind of deconfliction schemes successively to obtain better solutions than one of the two techniques taken alone, even if the resulting regulations are suboptimal w.r.t. the huge 2-dimensional problem. So to further optimize our solution or be able to handle takeoff uncertainties, we propose to combine our ground holding scheme with a prior flight level allocation, which aims at vertically separating intersecting flows of aircraft and therefore reduces the number of temporal constraints of the slot allocation. However, the Requested Flight Level (RFL) of a flight plan usually corresponds to an optimal cruise altitude (w.r.t. fuel consumption / CO 2 emission) and thus the distance between the allocated flight level and the RFL should be kept as low as possible, should such a scheme be accepted by airlines. Of course, this first FL allocation step, which approximates trajectories in the horizontal plane without taking the climbing or descent phases into account, only prevent conflicts occurring between levelled flows in their cruise phase. So conflicts involving at least one vertically evolving trajectory, or catch up flights belonging to the same flow, will still have to be resolved by the ground holding algorithm.

Several optimization paradigms are being evaluated for this purpose, namely meta-heuristics, local search and Constraint Programming (CP). We will focus here on the CP approach as it offers to obtain proved bounds on the maximal deviation from RFLs to vertically separate the flows and the maximal delay to solve the conflicts, which can be used to draw conclusions on the feasibility of this kind of regulation. Moreover, CP is a technology of choice for implementing such preliminary work, as it allows to easily refine the problem by adding new constraints (e.g. connection constraints between flights using the same aircraft) and to experiment with various search strategies without changing the rest of the model.

In the following sections, we first briefly introduce ATC and ATFM in Europe, focusing on ground holding and flight level allocation policies and related research projects. Then we describe our models of an intersectionfree flight level allocation for flows of aircraft and of a conflict-free delay allocation. Next, our results on instances of the French Traffic are presented. We end with planned further works to enhance the approach before concluding.

II. CONTEXT AND RELATED WORKS

A. ATC and ATFM

Air Traffic Control (ATC) is a ground-based service provided to ensure the safety and efficiency of the flow of aircraft. The first goal of ATC is to maintain aircraft separated: outside Terminal Areas (TMA) around airports, two aircraft should remain distant from each other at least by 5 NM horizontally and 1000 ft vertically, as illustrated by the safety volume of figure 1.

NM 1000 ft

Fig. 1. Vertical and horizontal separation. Another aircraft cannot be inside the cylinder at the same time.

The overall system currently implemented in Europe to achieve this goal can be conceptually divided in several layers or filters with decreasing time horizon with respect to the flight date of the traffic concerned: Altitude Warning) and airborne (Traffic Alert and Collision Avoidance System, Ground Proximity Warning System). We will focus in the following section on the kind of regulations performed by the CFMU by postponing the takeoff of aircraft.

B. Ground Holding

As aircraft obviously cannot be paused while airborne whenever the traffic complexity becomes too high to be safely handled by a controller, one of the simplest way to leverage ATC workload is to postpone the takeoff of aircraft 1 . This kind of measure is however quite unpopular among airlines, as it can be very costly and may propagate in terms of missed correspondences and aircraft rotation (see [START_REF]Evaluating the true cost to airlines of one minute of airborne or ground delay[END_REF]), so the delays should be minimized as much as possible.

1) Satisfying En-Route Sectors Capacity Constraints: The aim of CFMU regulations is to maintain the number of en-route aircraft entering a given subset of sectors below some bound over given time periods (usually one hour), according to the constraints declared by experts (FMP) in each ATCC for the day of traffic. The CFMU experts first identify the overloaded sectors and responsible flows with the PREDICT tool, then compute a slot allocation as ground delays for the involved flights with the CASA tool (cf. [START_REF]Basic CFMU Handbook -General & CFMU Systems[END_REF]).

CASA is able to take into account many operational constraints and updates to optimize its allocation process, but the algorithm used has greedy properties and thus cannot guarantee to find a correct solution (which satisfies all the constraints) or an optimal one. CP technology has been applied with good results to prove and optimize the allocation process with a relaxed model [START_REF] Dalichampt | Innovative slot allocation (ISA)[END_REF] or to smooth the resulting load profiles [START_REF] Barnier | Slot allocation with constraint programming: Models and results[END_REF] with a tighter model.

However, traffic complexity is very hard to define precisely, and sector capacities, expressed as a maximum number of aircraft entering the sector over a given time period, do not take into account many parameters relevant to accurately represent the performance of ATC. Observed actual capacities, as well as merging and splitting subset of sectors, symptomatically present very different profiles than the predicted ones.

To overcome this issue, recent works such as [START_REF] Flener | Air-traffic complexity resolution in multi-sector planning using constraint programming[END_REF] use a much more precise and complex workload CP model to dynamically balance the traffic over the sectors of an ATCC in the upper airspace. Other works, like [START_REF] Barnier | Application de la programmation par contraintes à des problèmes de gestion du trafic aérien[END_REF] uses CP technology as well to optimize the ATCC opening schedules to match the predicted traffic more closely, or even attempt to redesign airspace sectorisation with better balancing like [START_REF] Huy | Airspace sectorization by constraint programming[END_REF].

2) Solving the Conflicts: One of the key ATM operational concept of the SESAR program that Episode 3 should validate is the design of conflict-free 4D-tubes within crowded airspace (whereas separation could be delegated to aircraft in less dense areas). So instead of only respecting sectors capacities macroscopically, we propose to evaluate the cost of precisely solving all potential conflicts by ground holding, while minimizing the worst allocated delay to maintain equity among airlines.

Optimality proofs for the overall sum of the delays can be exponentially harder than our max criterion, and therefore out of reach for such large problems. However, our search strategy will focus on maintaining the overall amount of delay as low as possible, while the use of CP technology will provide proved maximal delay bounds that other optimization techniques (e.g. local search or meta-heuristics) cannot produce.

Other approaches have been presented to solve conflicts in real-time, automating the task of controllers. Some of the most promising ones are centralized techniques that compute simple horizontal or vertical manoeuvres [START_REF] Granger | Détection et résolution de conflits aériens : modélisations et analyse[END_REF] and small speed adjustments as proposed by the ERASMUS project [START_REF] Archambault | Speed uncertainty and speed regulation in conflict detection and resolution in air traffic control[END_REF]. These solvers, based around a meta-heuristic (Genetic Algorithm), can take uncertainties on ground and vertical speed into account and repeatedly compute solutions for a sliding time window.

C. Flight Level Allocation

Even if CFMU experts can balance traffic load by separating flights of the same flows over alternative routes, no real optimization of the flight level allocation is currently performed at the strategic/pre-tactical level in Europe, except for a few static rules attributing the parity of FL according to the heading of flights to prevent face-to-face conflicts. At the real time level, Air Traffic controllers can issue temporary FL changes to separate aircraft, and this kind of vertical manoeuvres has been integrated in the ERCOS conflict solver [START_REF] Granger | Optimal resolution of en route conflicts[END_REF].

Our work is more similar to the approaches presented in [START_REF] Letrouit | Optimisation du réseau de routes aériennes en Europe[END_REF], [START_REF] Barnier | Graph coloring for air traffic flow management[END_REF] where graph coloring techniques are applied to optimize the FL allocation of French and European networks of direct routes, or in [START_REF] Gianazza | Assessment of the 3dseparation of air traffic flows[END_REF] where a Genetic Algorithm and an A ⋆ algorithm are used to optimize traffic flows with possible changes of FL along the route (as well as lateral deviations for direct routes).

However, contrary to these studies, our model does not fit well within standard graph coloring problems as the choice of FL is very much restricted for operational reasons and each flow will only have a couple of possible FL available above or below its RFL. Moreover, the FL allocation phase should handle over-constrained instances as well to obtain the best possible solution to feed the ground holding phase, even if some conflicts remain, so classic coloring techniques like the use of cliques as lower bounds or "all-different" constraints (cf. [START_REF] Barnier | Graph coloring for air traffic flow management[END_REF]) cannot be used to speed up the search. Furthermore, the cost of solutions is measured w.r.t. the number of still conflicting flows and the sum of distances to RFLs (weighted by the number of flights in the flow), which are uncommon criteria for graph coloring problems.

III. DECONFLICTION WITH GROUND HOLDING

The ground holding CP model uses as input a set of temporal conflict constraints computed for each pair of flights that intersect in the three spatial dimensions. This conflict detection will be used as well as input of the FL allocation phase, but without taking the vertical dimension into account during intersection computation.

The following section describes the processing of flight plans to compute the conflict constraints and the modelling of deconfliction by ground holding as a constraint program.

A. Conflict Detection

Our data are provided by the CATS 2 simulator [START_REF] Alliot | CATS: A complete air traffic simulator[END_REF], which takes as input all filed flight plans concerning the French airspace for a given day of traffic and the relevant airspace configuration (sectors, waypoints...), and outputs the corresponding 4D-trajectories. Trajectories are sampled with a 15 s time step, which is the largest interval to guarantee that at least two points of the trajectories of facing aircraft at the highest possible speed will be closer than one separation norm, i.e. even the shortest conflicts will be detected.

Trajectories are then probed pairwise for potential conflicts, taking the maximal allowed delay into account. The separation norm is thus tested for each pair of points of the two probed trajectories (up to p = 900 points per trajectory for up to n = 8600 flights in O(n 2 p 2 )) as illustrated on figure 2 in the horizontal plane.

To reduce the complexity of this detection phase, trajectories are encapsulated into bounding boxes: each 2 The Complete Air Traffic Simulator developed at DSNA/DTI. trajectory is split into segments (a segment being here defined as a constant heading portion of the trajectory); then each of these segments is encapsulated into a bounding box, such that every point of the segment is farther than half the separation norm from each side of the box, as illustrated in figure 3 in the horizontal plane. Consider two flights i and j with trajectories encapsulated in bounding boxes (b 1 i , ..., b n i ) and (b 1 j , ..., b m j ) respectively. If there is an intersection between boxes b k i and b l j , then the pairwise tests for conflicting points is only performed for points contained in b k i and b l j , thus saving a lot of useless tests for the rest of the trajectories. This filtering proved to reduce computing time for conflict detection dramatically.

Operationally, flights originating outside the Eurocontrol countries cannot be delayed, so their delay variable will be fixed to 0 in our constraint model, reducing the number of variables but tightening the constraints as well and offering less opportunities for optimization. Constraints corresponding to conflicts occurring between two such flights will of course be discarded as we cannot delay the flights to solve them. Such remaining conflicting cases would have to be taken care of by other ATC techniques beyond the scope of this study.

B. CP Model

To compute the constraints of our model, the trajectories are pairwise probed for couples of conflicting points. Given a flight i, we note the input data:

• {p k i } the chronologically ordered sequence of the 3D-points of its trajectory;

• t k i the time at which the flight will be at point p k i , should it not be delayed. We define a set of decision variables {δ i , ∀i ∈ [1, n]} of finite domain [0, δ max ] that represent the delay associated with each of the n flights, and we will describe our model using the following auxiliary variables:

• θ k i = t k i + δ i the date at which flight i will be at point p k i if it is delayed by δ i ; • d ij = δ j -δ i .
For any geometrically conflicting points p k i and p l j such that the separation norm is violated (d h being the distance in the horizontal plane and d v in the horizontal plane):

d h (p k i , p l j ) < 5 NM and d v (p k i , p l j ) < 1000 ft
we must temporally ensure that θ k i = θ l j which can be rewritten with the difference variables d ij = t k it l j . Starting at the first such point p k i that conflicts with a point of flight j, we take into account the whole continuous segment of trajectory j conflicting with p k i :

{p l j , ∀l ∈ [l k , l k+r ]}
for some r, and we impose that:

d ij ∈ {t k i -t l j , ∀l ∈ [l k , l k+r ]} d ij ∈ [lb k , ub k ]
with lb k and ub k being respectively the lower and upper bound of the set of t k it l j . If the next point p k+1 i of the trajectory of flight i conflicts with a further segment of flight j, we will obtain another forbidden segment d ij ∈ [lb k+1 , ub k+1 ] taking part in the same potential conflict. To ensure separation we must then impose:

d ij ∈ [min(lb k , lb k+1 ), max(lb k , lb k+1 )]
as the conflicting segments of flight j overlap.

So if we take into account all the successive points of flight i, starting at p k i , that conflict with overlapping segments of flight j, up to some last point p k+s i , with lb 1 = min{lb k+u , u ∈ [0, s]} and ub 1 = max{ub k+u , u ∈ [0, s]} being the overall lower and upper bounds of the corresponding forbidden intervals for d ij , we can define the first conflict between flights i and j:

d ij ∈ [lb 1 , ub 1 ].
Note that we take as parameters of the problem instance the maximal allowable delay δ i ∈ [0, δ max ], therefore the domain of

d ij = δ j -δ i is the interval [-δ max , δ max ].
We simply discard the conflict whenever ub < -δ max or lb > δ max .

A pair of flights may conflict several disjoint times over their entire trajectories, so several such disjoint intervals may be forbidden for the difference of their delays. For two flights i and j conflicting σ times over their entire trajectories:

d ij ∈ lb 1 , ub 1 ∪ • • • ∪ lb σ , ub σ (1)
or, rewritten as a disjunctive constraint over the decision variables (-

δ max ≤ d ij < lb 1 )∨(ub 1 < d ij < lb 2 )∨• • •∨ (ub σ-1 < d ij < lb σ ) ∨ (ub σ < d ij ≤ δ max )
, provided that lb 1 > -δ max and ub σ < δ max , otherwise the first or last part of the disjunction is removed. We note:

C ij = lb 1 , ub 1 ∪ • • • ∪ lb σ , ub σ (2)
the union of forbidden intervals that represents the conflict between flights i and j.

The cost of a solution is then defined as:

cost = max{δ i , ∀i ∈ [1, n]}

IV. DECONFLICTION WITH FLIGHT LEVEL ALLOCATION

The flight level allocation is aimed at vertically separating intersecting flows of aircraft, in order to reduce the complexity of the traffic, prior to the takeoff time allocation. This FL allocation is performed according to the following steps:

• aggregation of flights into flows;

• computation of intersections in the horizontal plane between flows;

• allocation of a FL to each flow in such a way that two intersecting flows are given a different FL (if possible).

Of course, this phase cannot solve catch up conflicts within the same flow and doesn't take the climbing or descending parts of trajectories into account, so conflicts will still be detected after the allocation. These remaining conflicts will be solved by the following ground holding stage, which is expected to compute much better solutions once the FL allocation is optimized.

A. Flows and Intersections

Flights that share the same route (i.e. the same sequence of beacons in their flight plans) and RFL are gathered into one flow. We note F the set of all flights, and we define for each flow F k ⊆ F:

• r k its route;

• RF L k its requested flight level;

• size k its number of flights. Note that the set of all flows F k forms a partition of the set of flights F.

Without taking time into account, we could define a (potential) conflict between two flows of aircraft F k and F l if their routes r k and r l intersects in the horizontal plane. However, this first approximation dramatically overestimates the number of conflicts and yields so overconstrained problems that only a very small subset of the constraints may be satisfied with limited flight level resources (i.e. if the distance between the allocated flight level and the RFL is bounded by a small constant, noted dev max in the following section).

In order to reduce the tightness of the corresponding conflicts graph, the temporal dimension of the flights must be considered. Indeed, an aircraft does not occupy its entire route all day long, but intersects other trajectories during short time periods, as explained in the previous section. So two flows are in conflict if at least two flights (one from each flow) are in conflict w.r.t. definition 1 given in section III-B, but with a conflict detection performed in the horizontal plane only. Resulting conflicting intervals between flights i and j will be noted C H ij (by analogy with the C ij in definition 2). Such a conflict will occur if d ij (i.e. the difference between the delays of flight i and j) belongs to the union of forbidden intervals C H ij . So if no delay is considered, i.e. δ i = 0, δ j = 0 and therefore d ij = 0, flights i and j will be in conflict iff 0 ∈ C H ij . Given two flows F k and F l , we will note conf lict(F k , F l ) the relation associated to the former definition. Of course, with this definition of conflicting flights and flows, potential delays allocated during the ground holding phase are not taken into account, and two flows which are not in conflict for the FL allocation model could be potentially conflicting during the slot allocation.

However, it is easy to generalize the conflict definition in order to take delays into account. If we note δ max the maximal delay of the slot allocation phase as in section III-B, a conflict between two flights will be detected iff [-δ max , δ max ] ∩ C H ij = ∅. Then the conf lict relation can be more formally defined:

conf lict(F k , F l ) ⇔ ∃i ∈ F k , ∃j ∈ F l , s.t. [-δ max , δ max ] ∩ C H ij = ∅ (3)
However, taking even very small delays (e.g. 5-15min) into account tends to generate very dense conflict graphs which are over-constrained for reasonable values of the maximal discrepancy dev max allowed between allocated FLs and RFLs. Many conflicts will then remain for the ground holding phase and the purpose of FL allocation compromised. Furthermore, only a fraction of the flights will be delayed during the second phase, and many postponed flights are allocated very small delays, so it would be a too rough approximation to constrain each pair of intersecting flows as if the maximal delay were allocated to their conflicting flights. Eventually, the detection used to produce the results presented in section V is performed with d ij = 0 (i.e. as if the flights were not delayed in the following phase), which allows to obtain solutions without conflicting flows for very low discrepancy bounds between allocated FL and RFL.

B. Constraint Model

The decision variables of the CP model are the flight levels allocated to flow k:

F L k , ∀k ∈ [1, m]
where m is the number of flows. As an aircraft which does not fly at its optimal FL will burn more fuel during the flight, we limit the possible discrepancy between the RFL of a flow and its allocated flight level by a maximal deviation dev max . So each

F L k has finite domain [RF L k -dev max , RF L k + dev max ].
The constraints of the model are straightforwardly derived from equivalence 3 of the previous section that defines conflicting flows:

∀k, l ∈ [1, m] 2 , k < l, conf lict(F k , F l ) ⇒ F L k = F L l (4)
As this model still may produce over-constrained instances, the constraint program uses soft constraints instead of hard ones to be able to compute partial solutions which do not satisfy all the disequality constraints appearing in 4. To obtain a solution which will ease as much as possible the task of the delay allocation, i.e. a traffic with as few 4D-intersections as possible between flows, the cost of a solution is defined as the number of remaining conflicting flows, i.e. flows which have a common FL with at least one of their intersecting flows.

cost F L = |{F k , k ∈ [1, m] s.t. ∃l ∈ [1, m], l = k, conf lict (F k , F l ) ∧ F L k = F L l }| (5)
The soft constraint program allows then to produce the best possible solution w.r.t. the number of conflicting flows, and even if there is no solution with cost F L = 0 for low values of dev max , the resulting traffic will be much easier to deconflict during the following slot allocation phase than the raw traffic with its original RFLs. However, a rough estimation of airlines operational cost of such a flight level allocation scheme should take the number and range of all the discrepancies from RFLs of the set of flights, so we define:

op cost F L = m k=1 |RF L k -F L k | × size k (6)
Even if the optimization criterion of our model only takes the former cost F L into account, the search strategy attempts to minimize op cost F L by allocating flight levels as close as possible to their RFLs. Note that the induced cost of a discrepancy to the RFL would probably raise more rapidly than a linear growth as proposed in equation 6, were more technical considerations taken into account to estimate a real fuel cost function. But as dev max will be chosen very low during the experiments reported in section V to be acceptable for airlines (a deviation of 3, i.e. an FL of 10, 20 or 30 above or below the RFL, seems to be enough to solve all conflicts of most instances), the ordering of the solutions w.r.t. op cost F L should be quite similar to the one induced by a realistic operational cost function, the design of which is beyond the scope of this work.

V. RESULTS

These two CP models have been implemented with the FaCiLe library [START_REF] Barnier | FaCiLe: a Functional Constraint Library[END_REF] and have produced the following results on various days of traffic within the French airspace in 2008, with up to 8600 flights. After the conflict detection in the horizontal plane, flights are divided in flows and fed to the FL allocation program with a FL30 maximal discrepancy from the RFL and no delay taken into account; then the conflict detection in 3D is performed on the modified traffic and its result is taken as an instance of the ground holding program. About 10% of the flights are non-European flights, so their delays will be fixed to 0 during the ground holding phase as aforementioned.

A. FL Allocation Phase

Table I sums up a few dimensions of the instances like the number of flights, of flows (flights sharing the same route and RFL) and of conflict constraints between flows intersecting in the horizontal plane and temporally (with no delay taken into account). The instances typically comprises 3000 to 3500 flows with 160 000 to 200 000 constraints.

The maximal discrepancy dev max is fixed to 3, which allows the FL of a flow to be allocated to FL10, FL20 or FL30 above or below its RFL. Such a low value is enough to obtain solutions without conflicts on all the days of traffic of our data set and should be acceptable for airlines. The typical distribution of discrepancies to RFL after allocation for the various days of traffic is presented in figure 4: 60% of the flights remain untouched, and among deviated flights, 70-80% have a discrepancy of FL10 and 1-5% only the maximal discrepancy of FL30. The operational cost op cost F L defined in equation 6 is not directly optimized by the CP branch & bound algorithm, as mentioned in section IV-B, but the search strategy first assigns flight levels closest to the RFL of each flow to obtain allocations with reasonable discrepancies. The last line of table I shows the operational cost obtained for the days of our data set.

To assess the allocation phase and to produce the new trajectories data for the ground holding phase, the CATS simulator is fed with the flight plans and the new FLs with its conflict detection activated. Figure 5 shows the evolution on the number of actual conflicts detected by CATS, on the 12/08/2008 traffic, with increasing values of dev max : 0 corresponds to the original RFLs, i.e. without FL allocation, and 30 to the maximal discrepancy value used for the solutions given to the ground holding phase. The conflicts are divided in two main types:

• "Evol" for conflicts where at least one of the two flights is climbing or descending;

• "Cruise" for conflicts where the two flights are in the cruise phase; then each of the previous categories are further divided in two subtypes:

• "Crossing" for conflicts where flights are on distinct crossing segments;

• "Catch up" for conflicts where aircraft are on the same flight segment between two beacons. As the total number of conflicts decreases as the maximal discrepancy dev max grows, essentially among conflicts occurring during the cruise phase of the flights. Indeed, the FL allocation model approximates trajectories without taking climb or descent phases into account, so almost all conflicts occurring with one vertically evolving aircraft will not be solved. Nevertheless, the total number of conflicts is reduced by 20% for a FL10 maximal discrepancy, and a discrepancy of FL30 was necessary to solve all conflicting flows of the FL allocation model, inducing a 27% reduction of the conflicts.

Of course, the effect is much more sensible if only conflicts occurring during the cruise phase are taken into account, as 60% of them are solved by a FL10 discrepancy, and up to 75% for FL30 (81% if only crossing conflicts are counted). But the ratio of conflicts with evolving aircraft is around 65% for a typical day of traffic like the one of figure 5, and as our FL allocation scheme is unable to solve this heavy share of the conflicts, they will have to be taken care of by the ground holding phase. After FL allocation, the share becomes close to 90%.

B. Ground Holding Phase

The CP ground holding algorithm takes as input the trajectories of one day of traffic modified by the previous FL allocation with a FL30 maximal discrepancy. Figure 6 shows the variation of the cost, i.e. the maximal delay needed to solve all conflicts, before and after the FL allocation phase. The decrease of the cost can reach more than 50% for the first instance, or as bad as 0% for the second -and could possibly raise, even if we did not observe it on our data set. However, it was already mentioned in [START_REF] Barnier | 4D-Trajectory deconfliction through departure time adjustment[END_REF] that the maximal cost was rather aimed at proving the feasibility of the delay allocation but was a poor indicator alone of the quality of a solution, and that the sum of the delays and the ratio of delayed flights give much more information. Moreover, it was observed as well that the maximal cost exhibits very steep variations when the algorithm is parameterized to select flights and conflicts above a given flight level only (which allows to tune the size), unrelated to the smooth decrease observed for the sum of delays. Nevertheless, the decrease in terms of the sum of delays or ratio of delayed flights is much more sensible: 11% to 28% is gained on the sum, with a 20% mean, and a reduction of 12% to 16% of the percentage of delayed flights (i.e. an average improvement of 5% of the total amount of flights).

VI. FURTHER WORK

The results of this combination of FL allocation and ground holding are encouraging. However, we have only addressed so far the resolution of conflicts within the French airspace. In a unified European ATC context, all conflicting traffic throughout the Eurocontrol countries should be taken into account. Such instances would comprise up to 30 000 flights per day. We plan to experiment with various refinements of our algorithm to be able to address such large scale problems, as well as to handle uncertainties on takeoff times and trajectory management.

A. Handling Uncertainties

To improve the robustness of our solutions towards uncertainty on takeoff times, the conflicting intervals described in section III-B can be extended by a fixed amount of time ext, thus allowing the allocation process to handle a ± ext 2 uncertainty. The resulting constraints would be tightened compared to the original model, so that the cost of our solutions would increase significantly.

This method was tested in [START_REF] Barnier | 4D-Trajectory deconfliction through departure time adjustment[END_REF] without the prior FL allocation, showing a costly increase of the cost with the ext parameter. We plan to experiment this feature with FL allocation taken into account to test whether the cost increase scheme is improved through this combination.

It also possible, as seen in section IV-A, to take some delay into account for the flight level allocation. Handling large delays seems to yield over-constrained instances. However, since most flights are allocated a small delay (typical figures for the problems we considered are: 85% flights with a delay less than 3 min, 90% with a delay less than 5 min), we plan to study the effect on our solutions of taking such small delays into account for the FL allocation.

In order to handle takeoff time uncertainties and other operational hazards such as flight cancellations or bad weather, we also plan to adapt our algorithm to proceed on a sliding time window. Slices of the problem would be iteratively solved on a limited time window T w , then only the earliest part of the solution would be kept over a small interval λ and then the resolution window would slide by λ. Each time the window is shifted, takeoff times can be updated, cancelled flights can be discarded and other constraints can be taken into account. Parameters T w and λ must be carefully chosen according to the computation time of the resolution. A similar approach is used for dynamic conflict resolution in the CATS solver as described in [START_REF] Granger | Optimal resolution of en route conflicts[END_REF].

B. European Instances

Our algorithm was not able to address European instances with ground holding only. However, we expect that the combination of ground holding with FL allocation as described in this paper will allow such large instances to be solved with a reasonable amount of delay.

Also, the use of a sliding time window method as described above would help handling such instances by slicing it into smaller ones.

VII. CONCLUSION

We have presented a novel combination of flight level allocation and ground holding to solve all potential conflicts for a day of traffic in the French airspace which improves the results published in [START_REF] Barnier | 4D-Trajectory deconfliction through departure time adjustment[END_REF]. Rather than trying to respect sector capacity constraints, we model each possibly conflicting situations between any two aircraft and impose adjustments of FL and departure times to keep them separated, with the hypothesis that aircraft could precisely follow their planned 4D-trajectories.

The size of the corresponding combinatorial problem is huge, but our CP algorithm is able to reach optimal solutions for the two phases. The maximal delay, overall delay sum and ratio of delayed flights are comparable to delays allocated by the CFMU, while discrepancies from the RFL are tightly bounded.

However, this preliminary work does not yet take into account uncertainties on the 4D-trajectories accuracy. We plan to add robustness towards uncertainties on the takeoff times to our approach by tightening the conflict graph of the FL allocation with small delays taken into account during conflict detection, adding the so-called "conflict extension" presented in [START_REF] Barnier | 4D-Trajectory deconfliction through departure time adjustment[END_REF] for the ground holding phase and iteratively solving temporal slices of the problem.

1 ) 3 )

 13 Strategic (several months), ASM (Air Space Management): design of routes, sectors and procedures (e.g. reduced separation RVSM since 2002, Area Navigation (RNAV) with fictive beacons...). 2) (Pre-)Tactical (a few days to a few hours), ATFM: ATC Centres opening schedules define hourly capacities of each open sectors (or groups of sectors). To respect these capacity constraints, the CFMU computes and updates flow regulations and reroutings according to the posted flight plans and resulting workload excess. Real time (5/15 min), ATC: surveillance, coordination with adjacent centres, conflict resolution by various simple manoeuvres (heading, flight level, speed) transmitted to the pilots. 4) Emergency (less than 5 min), safety nets: groundbased (Short Term Conflict Alert, Minimum Safety

Fig. 2 .

 2 Fig. 2. Conflicting points detection.

Fig. 3 .

 3 Fig. 3. Two intersecting trajectories and their associated bounding boxes. Conflicting point detection is only performed for points in the intersecting boxes.

Fig. 4 .

 4 Fig. 4. Distribution of discrepancies from RFL after allocation.

Fig. 5 .

 5 Fig. 5. Maximal discrepancy from RFL devmax vs number of remaining conflicts on 12/08/2008.

Fig. 6 .

 6 Fig. 6. Optimal cost before and after FL allocation.

Fig. 7 .Fig. 8 .

 78 Fig. 7. Sum of delays before and after FL allocation.

Note that flights might be delayed for other reasons than en-route capacity violation, like bad weather or equipment failures.

AUTHORS