Keywords: Neural network, tree search, Branch & Bound, airspace configuration, air traffic complexity

Introduction

Air traffic is currently controlled by human operators (air traffic controllers) who monitor aircraft trajectories and give instructions to pilots so as to avoid mid-air collisions and dangerous situations. The airspace is partitioned into managerial units, air traffic control centres (ATCC), which are themselves partitioned into elementary airspace modules 2 . These basic airspace modules may be combined together so as to form air traffic control (ATC) sectors each operated by a small team of 2-3 controllers 3 .

In many centres, the airspace configuration, i.e. the partitioning of the ATCC airspace into ATC sectors, may change during the day, depending on the incoming traffic and controller workload. Sectors may be split 4 when the workload increases, or merged (or collapsed) when the workload decreases. More complex recombinations may sometimes be decided by the control room manager, so as to balance the workload across all the control sectors.

The ultimate objective of the research presented in this article is to forecast airspace configurations with a good degree of realism, using a reliable workload forecast grounded on relevant air traffic complexity metrics. The basic idea is to learn from the current control sector operations in order to propose efficient forecasting models and algorithms.

Assessing the controller workload and predicting when this workload will exceed safe limits are difficult problems involving human factors, which have 2 The usual term to denote these elementary airspace modules is sector, which may be confusing as it can either denote a single airspace module, or a control sector made up of several modules. So, in the rest of this paper, the elementary geographic sectors will be referred to as modules, in order to avoid confusion with ATC (Air Traffic Control) sectors. 3 A team operating a control sector is composed of a radar controller who gives instructions to the pilots (direction or flight level changes), and a planning controller. The planning controller monitors the incoming traffic a few minutes before it enters the sector and is in charge of pre-detecting any potential conflicts, as well as coordination with the adjacent sectors. In some countries, an additional controller may assist these two controllers when the traffic is heavy. 4 Splitting an ATC sector requires that it is composed of at least two modules.

2 been the subject of many studies (see [START_REF] Loft | Mooij Modeling and Predicting Mental Workload in En Route Air Traffic Control: Critical Review and Broader Implications[END_REF] for an overview). Some studies focus on the relationship between air traffic complexity metrics and controller workload. A general statement is that workload depends largely on the number of flights, but also on the traffic complexity: aircraft flying parallel tracks at constant flight levels are less difficult to handle than climbing/descending flights on various converging trajectories, for example. However, no universal workload metric has been agreed on so far, and one can only hope to select a set of relevant air traffic complexity metrics that fits the chosen context and application. Our main contribution on this subject ( [START_REF] Gianazza | Evaluation of air traffic complexity metrics using neural networks and sector status[END_REF] and [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF]) was to use the sector status (merged, normal, or split) as a dependant variable, trying to find the subset of metrics that was best correlated to this sector status. The basic assumption is that the decision to reconfigure the ATC sectors is somewhat related to the controller's actual workload.

Airspace design and management have also been the subjects of many studies, using several methods: mixed integer programming techniques ( [START_REF] Verlhac | Optimization of opening schemes[END_REF]), evolutionary algorithms ( [START_REF] Delahaye | Genetic algorithms for partitioning airspace[END_REF], [START_REF] Delahaye | Genetic algorithms for automatic regroupement of Air Traffic Control sectors[END_REF], [START_REF] Delahaye | Airspace Sectoring by Evolutionary Computation IEEE International Congress on Evolutionary Computation[END_REF]), seed growth methods inspired by crystal growth ( [START_REF] Klein | An efficient method for airspace analysis and partitioning based on equalized traffic mass[END_REF]), constraint programming ( [START_REF] Trandac | Optimized Sectorization Of Airspace With Constraints[END_REF], [START_REF] Trandac | Airspace sectorization by constraint programming[END_REF], [START_REF] Flener | Air-traffic complexity resolution in multi-sector planning using constraint programming[END_REF]), computational geometry ( [START_REF] Basu | Geometric Algorithms for Optimal Airspace Design and Air Traffic Controller Workload Balancing[END_REF]), graph partitioning methods or a new meta-heuristic inspired by nuclear fusion and fission ( [START_REF] Bichot | A tool to design functional airspace blocks[END_REF], [START_REF] Bichot | A New Meta-method for Graph Partitioning[END_REF]). These studies address a variety of operational contexts: strategic airspace design, pre-tactical planning, and tactical airspace management. Some background on air traffic management and more details on related works on airspace design and management are provided in section 2. Let us just say that many of these studies ( [START_REF] Delahaye | Airspace Sectoring by Evolutionary Computation IEEE International Congress on Evolutionary Computation[END_REF], [START_REF] Trandac | Optimized Sectorization Of Airspace With Constraints[END_REF], [START_REF] Trandac | Airspace sectorization by constraint programming[END_REF], [START_REF] Bichot | A tool to design functional airspace blocks[END_REF], [START_REF] Bichot | A New Meta-method for Graph Partitioning[END_REF], [START_REF] Klein | An efficient method for airspace analysis and partitioning based on equalized traffic mass[END_REF]) addressed a highly difficult airspace partitioning problem, only slightly reduced by the introduction of connectivity 5 and convexity6 constraints on sectorisation. Among these studies, most of them used only mock-up sectors, whereas very few used real sectors and real traffic. Some other studies ( [START_REF] Verlhac | Optimization of opening schemes[END_REF]) were made in a highly realistic context but used metrics that are not sufficient to model the actual workload (see subsection 2.2), and a fairly reduced subset of pre-defined airspace configurations. Others ( [START_REF] Flener | Air-traffic complexity resolution in multi-sector planning using constraint programming[END_REF]) used more relevant air traffic complexity metrics to assess the controller workload, but did not propose airspace reconfigurations.

Our contribution aims at improving the predictability and flexibility of today's airspace management in Europe, in a pre-tactical or tactical context 7 . The initial difficulty of the airspace partitioning problem is highly reduced by considering only sector recombinations within each managerial unit, using only operationally valid ATC sectors listed in the en-route 8 air traffic centre's database. A realistic workload prediction model is proposed, relying on relevant air traffic complexity metrics and using a neural network trained on historical data. Our previous works dealt with the selection of the relevant metrics (see section 3). An initial version of our airspace configuration algorithm was given in [START_REF] Gianazza | Airspace configuration using air traffic complexity metrics[END_REF], using a simple exhaustive tree search method for local sector recombinations. In this article, a branch & bound algorithm was used to reconfigure the whole airspace when necessary. Some preliminary results were presented in [START_REF] Gianazza | An efficient airspace configuration forecast[END_REF]. The current article gives full details of the model and algorithm hybridizing the neural network for workload prediction and the branch & bound that computes airspace partitions of minimum cost, balancing the workload as well as possible across the ATC sectors. In addition, we have introduced the possibility of posting constraints on the maximum number of ATC sectors in an airspace partition. The rest of the paper is organized as follows: section 2 describes the air traffic management context and related works. Section 3 gives a short description of the methods we used to select the most relevant complexity metrics. Section 4 details the neural network used for workload prediction. The tree search algorithms that build optimal combinations of airspace modules are introduced in section 5, and the iterative algorithm that builds the full opening schedule for a whole day of traffic is presented in section 6. The experimental setup is described in section 7. Some results are shown in section 8, and section 9 concludes and gives the perspectives of future research and potential applications in the operational field. A glossary of terms can be found in the appendix. 7 In the European air traffic flow management process, pre-tactical operations usually take place the previous day (sector opening schedules, preliminary flow regulations plan, etc.), and tactical operations take place in real time, or up to a few hours before flights actually enter the airspace. 8 En-route air traffic management deals with traffic that follows routes between its origin and its destination, as opposed to terminal air traffic management, which deals with traffic near airports.

Background and related works

The air traffic management and airspace configuration context

Let us start with a short description of the current air traffic management system in Europe. We have seen in the introduction how elementary airspace modules can be combined so as to form control sectors. The airspace configuration may change during the day, depending on the controller workload. However, it is not always possible to split an ATC sector into several smaller sectors when the workload increases, either because the initial sector is composed of a single module or because there are not enough air traffic controllers on duty. This may lead to potentially dangerous situations when the traffic within a control sector is too heavy and too complex to be safely handled by the human operators.

Such situations are avoided by re-routing or assigning departure delays to aircraft that plan to enter the sector in the overloaded time interval. In Europe, the departure slots are allocated by the Central Flow Management Unit (CFMU). The Flow Management Position (FMP) operators of each air traffic control centre try to anticipate future overloads in their airspace. When necessary, flow regulations, which are used as input to the CFMU slot allocation algorithms assigning ground delays to aircraft, are enforced.

In some air traffic control centres, like the five French en-route centres, pre-tactical sector opening schedules are built by the FMP operators one or two days ahead. In France, the current method to build such schedules is fairly simple. A set of the usual airspace configurations is filed in a database. The FMP operator chooses among them the ones he (or she) thinks are the most adequate for each time period. The day is divided into fixed periods of usually one hour and no sliding time window is used. Candidate configurations are empirically assessed by counting the flights entering each ATC sector and comparing that count to pre-defined threshold values (sector capacities).

These pre-tactical schedules are unrealistic, partly because they rely on an estimated traffic demand, but also for other reasons: first, counting entering flights is not sufficient to model the controllers' actual workload, and second only a small subset of pre-defined configurations is considered. The current method directly results from former procedures, when flights were counted by hand.

As a consequence, the FMP schedules are not actually used to forecast future overloads. Instead, the FMP and CFMU operators rely on their past experience of similar traffic situations to enforce flow regulations on specific airspace boundaries, entry points, or airspace volumes 9 . The causal relationship between the slot allocation based on these regulations and the actual workload experienced by the controllers in real time is not clearly established. A more accurate assessment of future workload and a better forecast of future airspace configurations could certainly improve the predictability of the European air traffic management system.

So far, we have only described the French and European air traffic management, which is the context of our study. In the United States, the context is largely similar, although air traffic management is more concerned with convective weather problems. Many studies focus on the dynamic adjustment of the airspace structure to traffic flow reroutings caused by severe weather conditions. It is expected that more flexible boundaries would allow a more efficient use of airspace and increase overall capacity. In [START_REF] Klein | Airspace playbook: Dynamic airspace reallocation coordinated with the national severe weather playbook[END_REF], pre-defined scenarios of airspace sectorisations associated with traffic rerouting scenarios are proposed as a short-term improvement to the current practices. A more dynamic re-sectorisation with flexible boundaries is envisioned in future operational concepts ( [START_REF]Global air traffic management operational concept[END_REF], [START_REF] Swenson | Next Generation Air Transportation System (NGATS) Air Traffic Management (ATM)-Airspace Project[END_REF], and some SESAR10 Operational Improvement steps). It is expected that moving the sector boundaries in real-time to adapt to the traffic demand would increase the capacity and efficiency of the ATM (Air Traffic Management) system. The actual capabilities and potential benefits of this new operational paradigm are still largely unknown at this early stage, however. There is also some concern that unlimited flexibility in the sectors boundaries would lead to a loss of situational awareness by air traffic controllers (see discussion and literature review in [START_REF] Stein | Dynamic resectorization in air traffic control: A human factors perspective[END_REF]).

In the rest of this paper, we stick to the current context where the airspace is divided into pre-defined elementary modules.

Related works on airspace design and management

Current research on airspace configuration is manifold and may deal with strategic airspace partitioning, pre-tactical sector opening schedules, or tactical airspace management. Several methods have been tried out, with fairly different definitions for "workload". In [START_REF] Basu | Geometric Algorithms for Optimal Airspace Design and Air Traffic Controller Workload Balancing[END_REF], Basu et al. used geometric algorithms to design sector boundaries so as to balance a macroscopic workload (i.e. cumulated traffic over a whole day) across the sectors. The sectorisation problem was addressed by Delahaye et al. as a graph partitioning problem ( [START_REF] Delahaye | Airspace Sectoring by Evolutionary Computation IEEE International Congress on Evolutionary Computation[END_REF]), and solved with evolutionary algorithms. Workload was an aggregation of conflict workload, coordination workload, and monitoring workload. A graph representing the air routes was partitionned so as to minimize coordinations between sectors, under various constraints (connectivity, convexity). Klein ([8]) designed airspace boundaries for the American air route traffic control centres by growing hexagonal cells from initial seed locations, using an equalized traffic mass metric. Bichot et al. ([13]) worked on today's actual sectors and tried to partition the European airspace into optimally balanced airspace blocks (air traffic control centres), considering inter-sector traffic flows and using graph partitioning methods (standard methods or a new fusion-fission meta-heuristic). These studies are focused on strategic airspace design.

In [START_REF] Delahaye | Genetic algorithms for automatic regroupement of Air Traffic Control sectors[END_REF], Delahaye et al. addressed the dynamic airspace sectorisation problem for tactical operation, although only with mock-up sectors. The graph model and workload definition are the same as in their other works described above. This same problem was addressed by Tran Dac, Baptiste, and Duong ( [START_REF] Trandac | Airspace sectorization by constraint programming[END_REF], [START_REF] Trandac | Optimized Sectorization Of Airspace With Constraints[END_REF]) using a Kernighan-Lin heuristic combined with Constraint Programming techniques. Note that the airspace partitioning problem is highly combinatorial in its initial formulation: the number of partitions of a set of n elements into k subsets is the Stirling number of the second kind. The introduction of connectivity constraints (an ATC sector should be a single geographic area, not composed of several connected components), convexity constraints (a flight following a route should not enter the same sector twice), or operational constraints (choose from only identified operational sectors) reduces this difficulty.

A more realistic operational context was considered by Verlhac and Manchon ( [START_REF] Verlhac | Optimization of opening schemes[END_REF]) of Eurocontrol, who applied mix integer programming techniques to improve the pre-tactical planning of sector configurations in Europe, using actual sectors. Only a small subset of pre-defined usual configurations was considered. The traffic load was assessed by counting the flights entering the sector in a one-hour time window, like in the current FMP schedule. This is clearly not sufficient to model the actual controller workload: for example, a flow of 40 flights per hour may well be below the sector capacity (maximum value allowed for this flow), but may not be acceptable in terms of actual workload if all the flights entered the sector in the first 15 minutes of the hour.

In [START_REF] Gianazza | Optimal combinations of air traffic control sectors using classical and stochastic methods[END_REF], we proposed several algorithms exploring all combinations of airspace modules in a realistic context, using the same variables (number of flights entering the sector in a given time window) and thresholds (sector capacities), as well as the same constraints (number of controllers on the duty schedule) as the French Flow Management Positions (also used in [START_REF] Verlhac | Optimization of opening schemes[END_REF]). Standard tree search methods proved efficient when considering only operationally valid ATC sectors, i.e. those defined in the air traffic control centre database. An evolutionary algorithm was also proposed as an alternative, in case a wider range of airspace modules and ATC sectors was to be considered, and possibly larger geographic areas. The results were not realistic enough (see [START_REF] Gianazza | Optimization of air traffic control sector configurations using tree search methods and genetic algorithms[END_REF]), however, as the flow variables do not model the workload with enough accuracy. The conclusion was that a better assessment of the controller workload was needed.

Much research has been undertaken on traffic complexity metrics (see next section) with the aim of capturing the main features explaining the air traffic controller workload. Such metrics were used by Flener et al. to model controller workload in [START_REF] Flener | Air-traffic complexity resolution in multi-sector planning using constraint programming[END_REF]. Tactical reroutings and flight profile modifications were used to balance traffic complexity across several sectors, for tactical multi-sector planning purposes. However, no airspace reconfiguration was proposed.

We propose to forecast the controller workload in each ATC sector, as well as the airspace configuration of the whole centre airspace, with the aim of improving the current pre-tactical or tactical air traffic management operations. Currently, each controller is qualified only for operations in a given geographic area (qualification zone 11 ). As a consequence, the ATC sectors of a qualification zone cannot be combined with sectors from another qualification zone. In addition, we only consider operationally valid ATC sectors, listed in the en-route air traffic centre's database. With these restrictions and in the current context, the airspace partitioning problem is much less combinatorial and standard tree search methods can be used to find optimal combinations of elementary airspace modules, balancing the controller workload as well as possible across the ATC sectors.

The next section details how the relevant air traffic complexity metrics that model the controller's actual workload were selected.

Selection of the relevant complexity metrics

The selection process that allowed identification of the most relevant complexity metrics has already been described in previous publications ( [START_REF] Gianazza | Evaluation of air traffic complexity metrics using neural networks and sector status[END_REF], [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF]). Let us just recall the main steps of this process.

A set of relevant variables is usually selected by maximizing the correlation of the chosen metrics with a quantifiable dependant variable assumed to represent the actual controller workload. Many proposals have been made in past studies on the choice of dependent variables: physical activity ( [START_REF] Laudeman | Dynamic density: An air traffic management metric[END_REF]), physiological indicators ( [START_REF] Crump | Review of stress in air traffic control: Its measurement and effects[END_REF], [START_REF] Averty | Evaluating a new index of mental workload in real ATC situation using psychological measures[END_REF]), simulation models of the controller's tasks ( [START_REF] Yousefi | Investigation of en route metrics for model validation and airspace design using the total airport and airspace modeler (TAAM)[END_REF], [START_REF]An evaluation of dynamic density metrics using RAMS[END_REF], [START_REF] Majumdar | The factors affecting airspace capacity in Europe: A framework methodology based on cross sectional time-series analysis using simulated controller workload data[END_REF]), or subjective ratings ( [START_REF] Kopardekar | Measurement and prediction of dynamic density[END_REF], [START_REF] Chatterji | Measures for air traffic controller workload prediction[END_REF], [START_REF] Masalonis | Dynamic density and complexity metrics for realtime traffic flow management[END_REF]).

For our problem, we made the basic assumption that past decisions to reconfigure the airspace by splitting or merging the ATC sectors were statistically related to the controllers' actual workload 12 : ATC sectors can be split into smaller sectors when the workload is too heavy, or merged with other sectors when the workload is too light. They can be operated normally otherwise. Other, more complex, recombinations are also possible. The sector status (split, normal 13 , or merged) was chosen as the dependent variable quantifying the actual workload, when the sector was observed to be in one of these three states 14 . This variable has the advantage of being directly related to our problem. In addition, it does not require a heavy experimental setup to collect the data: it is already available in large quantities from the air traffic control centres archives.

The candidate explanatory variables were complexity metrics chosen from the literature (see [START_REF]Cognitive complexity in air traffic control, a literature review[END_REF], [START_REF] Mogford | The complexity construct in air traffic control: A review and synthesis of the literature[END_REF] and [START_REF] Kopardekar | Dynamic density: A review of proposed variables[END_REF] for a review), and included aircraft count, proximity-related and conflict-related15 metrics, flow metrics, track or speed disorder metrics, etc. Several methods have been used in past studies to correlate such metrics to chosen dependent variables: linear ( [START_REF] Kopardekar | Measurement and prediction of dynamic density[END_REF]) or logistic ( [START_REF] Masalonis | Dynamic density and complexity metrics for realtime traffic flow management[END_REF]) regression, cross-sectional time series analysis ( [START_REF] Majumdar | The factors affecting airspace capacity in Europe: A framework methodology based on cross sectional time-series analysis using simulated controller workload data[END_REF]), and neural networks ( [START_REF] Chatterji | Measures for air traffic controller workload prediction[END_REF]). We used a neural network, although not as a regression method but as a classification method (see details in the next section).

For workload modelling purposes, the metrics were computed from recorded aircraft trajectories ("radar tracks") and from the sector geometry. Later on in this paper, when trying to forecast the workload, we use trajectories simulated from flight plans 16 . Flight planning errors (cancellations, missing flight plans, short-notice departures, etc.), as well as navigation errors, and controllers' actions -for example vectoring instructions to avoid conflicts with other trajectories -may introduce forecasting errors and biases on the metrics values. These issues are further discussed in section 7 and in the conclusion. Let us just say that we can expect that the biases due to the controllers' actions on the traffic should remain relatively small. The influence of the differences between planned traffic and actual traffic on the quality of the airspace configuration forecast is covered in subsection 8.2.

The metrics selection process started with a principal component analysis that reduced the dimensionality of the initial set of candidate metrics. The most relevant components were selected using Akaike's AIC 17 ([2]). Schwartz's Bayesian Information Criterion (BIC) was also used as an alternative in [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF] when selecting the best individual metrics in each relevant principal component. The use of such information criteria avoids the bias due to the increasing number of model parameters (the neural network weights) when considering subsets of input metrics of increasing sizes.

Among the initial 28 explanatory variables chosen from [START_REF] Kopardekar | Measurement and prediction of dynamic density[END_REF], [START_REF] Chatterji | Measures for air traffic controller workload prediction[END_REF], [START_REF] Delahaye | Air traffic complexity: towards intrinsic metrics[END_REF], [START_REF] Averty | Conflit perception by ATCS admits doubt but not inconsistency[END_REF] and other sources, the 6 most relevant variables were the sector volume V , the number of aircraft within the sector Nb, the average vertical speed avg vs, the incoming flows with time horizons of 15 minutes and 60 minutes (F 15 , F 60 ), and the number of potential trajectory crossings with an angle greater than 20 degrees (inter hori 18 ).

Let us note that these metrics are fairly basic, compared to others that can be found in the initial set of candidate metrics. This does not mean that all these other metrics were not relevant. Many of them were redundant with the basic metrics that were found to be most correlated to the sector status. This is probably due to the fact that our observation of the actual workload is relatively macroscopic, as we only have three levels of workload: "too low" when the sector is merged, "normal" when it is operated, or "too high" when it is split into smaller sectors operated separately. This does not allow very small variations of the actual workload, within the normal domain of operation, to be captured with more sophisticated metrics. This is enough, however, for our purpose of predicting airspace configurations.

In [START_REF] Gianazza | Smooth traffic complexity metrics for airspace configuration schedules[END_REF], we improved this workload prediction model by smoothing the input metrics: the raw metrics showed high variations in time, causing too frequent airspace reconfigurations (see [START_REF] Gianazza | Airspace configuration using air traffic complexity metrics[END_REF]). Another promising approach, which is left for further work, would be to consider the input metrics as time series.

To conclude on the metrics selection, let us say that our final model with its 6 variables could probably be improved by considering the sector volume that is actually available at every moment of the day to air traffic controllers, taking account of convective weather or military activity, instead of the overall volume. Other metrics related to the sector complexity (see [START_REF] Welch | Macroscopic workload model for estimating en route sector capacity[END_REF]) could also be tried, as well as other traffic complexity metrics that have not yet been implemented in our libraries.

A neural network for workload prediction

Let us now detail the model that is used for workload prediction, based on the assumption that previous decisions to split or merge ATC sectors in the past were statistically related to the controllers' actual workload.

Considering the nature of the observed data, we chose a "1 of 3" encoding for the desired target representing the actual sector status:

• d = (1, 0, 0) T when the sector is merged with other sectors into a larger ATC sector (low workload),

• d = (0, 1, 0) T when the sector is in its normal domain of operation (acceptable workload),

• d = (0, 0, 1) T when the sector is split into several smaller control sectors (excessive workload).

Observed patterns where the sector is in a state other than one of the above 19 were discarded.

The explanatory variables are the relevant complexity metrics {V ,N b, avg vs, F 15 , F 60 , inter hori} (see section 3), normalized by subtracting the mean value and dividing by the standard deviation. Let us denote x = (x 1 , ..., x i , ..., x 6 ) T this vector of input variables, where T denotes the transpose operator.

Our aim is to determine from any given measure of x if the workload in the considered ATC sector is low, normal, or too high. This is typically a classification problem, that we chose to address with a simple feed-forward network with one hidden layer, as a first approach. The reader can refer to [START_REF] Bishop | Neural networks for pattern recognition[END_REF] and [START_REF] Ripley | Pattern recognition and neural networks[END_REF] for an extensive presentation of neural networks for pattern recognition, or [START_REF] Jordan | Neural Networks[END_REF] for a shorter review. The results presented in this paper were produced with a network having 6 units on the input layer, 15 units on the single hidden layer, and 3 units in the output layer. Let us denote y = (y 0 , y 1 , y 2 ) T the output vector of the neural network. The neural network equation is written as follows:

(y 0 , y 1 , y 2 ) T = Ψ( 15 j=1 w jk Φ( 6 i=1 w ij x i + w 0j ) + w 0k ) ( 1
)
where Ψ is the softmax function:

Ψ k (z k ) = e z k 3 m=1 e zm (2)
Φ is the sigmoid logistic function:

Φ(z) = 1 1 + e -z (3)
The error function we are trying to minimize when training the network is the cross-entropy function:

E(w) = - N n=1 C k=1 d (n) k ln( y (n) k d (n) k ) ( 4
)
with C = 3 classes, and considering N patterns for training, and where

d = (d 0 , d 1 , d 2 )
T is the desired target vector. The cross-entropy function is simply the log-likelihood

L(w) = - N n=1 C k=1 d (n) k ln(y (n) k )
from which was subtracted the minimum log-likelihood

L min = - N n=1 C k=1 d (n) k ln(d (n) k )
reached when y k = d k (see [START_REF] Bishop | Neural networks for pattern recognition[END_REF], pp. 237-238). See also [START_REF] Dunne | On the pairing of the softmax activation and cross-entropy penalty functions and the derivation of the softmax activation function[END_REF] for justifications on the choice of the cross-entropy penalty function for classification problems, and on the natural pairing of the softmax activation and cross-entropy penalty functions. A standard back-propagation method ( [START_REF] Rumelhart | Learning internal representations by error propagation[END_REF]) was used to compute the gradient of the error function, and a quasi-Newton method (BFGS, namely) was used to minimize the error. These methods were implemented in a library written in Objective Caml.

The output vector can be interpreted as a vector of posterior probabilities of class-membership: y 0 can be seen as the probability p(C low /x) that the ATC sector falls in the "merged" class (low workload) when the measured air traffic complexity vector is x, and similarly for y 1 and y 2 , with classes C normal and C high respectively. Using an abbreviated notation, we shall denote y = (p low , p normal , p high ) T the output vector in the rest of this paper, so as to clarify the nature of the neural network output.

As we are necessarily in one of the above three cases (low, normal, or excessive workload), the sum of the three probabilities p low , p normal , and p high is always 1, which is ensured by the use of the softmax function Ψ.

If interpreting the network output in terms of probabilities related to the controller workload is rather straightforward, this is not so easy concerning the function Φ and the cross-entropy 20 . As stated by Jordan and Bishop ([44]), neural networks may best be viewed as a class of algorithms for statistical modelling and prediction. A neural network is simply a statistical model made of a mixture of adaptive functions. The functions Φ map each a portion of the multi-dimensional space of input variables (the air traffic complexity metrics). The model is adaptive in the sense that the function's weights w are tuned during the training phase so as to fit the observed data as well as possible, minimizing the error between the computed output and the observed sector status (using the cross-entropy in our case, which is just an expression of the log-likelihood).

This combination of functions, when using a network with at least one hidden layer of sigmoidal units, has the interesting property of approximating any decision boundary to arbitrary accuracy (see [START_REF] Bishop | Neural networks for pattern recognition[END_REF], p. 130 for bibliographic references on this property). This provides universal non-linear discriminant functions, and allows modelisation of posterior probabilities of class-membership for classification problems. This is why this class of algorithms was preferred to linear or logistic discrimination techniques 21 .

This does not mean that those methods or other statistical models would not perform well. For example, an ordered logit model like the one used in [START_REF] Averty | An Ordered Logit Model of Air Traffic Controllers Conflict Risk Judgment[END_REF] could be well adapted to our classification problem. However, although it would be interesting, it is not in the scope of this paper to make such a comparative study on various methods. This could be addressed in future works

Tree search algorithms for airspace partitioning

Let us now see how to partition the airspace, using the workload indications given by the neural network to assess the optimality of candidate configurations. In order to find an optimal airspace configuration, one needs to explore all possible partitions of elementary airspace modules, while restricting them to operationally valid configurations. Finding an optimal partition requires two things: first a mechanism to build valid configurations and, second, some cost functions to evaluate and compare the candidate configurations. The next subsections detail the cost of a configuration and the tree search algorithms.

Cost of a configuration

To evaluate an airspace configuration, we consider the number of ATC sectors and the values of probabilities p low (s i , t), p normal (s i , t), and p high (s i , t) issued by the neural network for each sector s i in the configuration c = {s i /i ∈ [1, m]}, where t is the time. As illustrated in our previous example, a sector s i is a group of airspace modules labelled by a sector name.

Considering configuration [({1}, s); ({2, 3}, a); ({4, 5}, c)] of this example, it would be perfectly balanced in terms of workload if we had (p low , p normal , p high ) equal to (0, 1, 0) for all ATC sectors a, b, and s = {1}. Such ideal situations rarely occur in reality, however, where p normal may be less than 1 in several sectors, and where overloads and under-loads22 may occur, sometimes in the same configuration.

Before defining the cost of a configuration, let us state the objectives we are trying to reach, in decreasing order of priority. The first objective is to satisfy the constraint on the maximum number of ATC sectors, when such a constraint is posted. This constraint is useful when, for some reason, some controller working positions are not available, or when there are not enough controllers to operate more than a maximum number of sectors. The second objective is to avoid overloads, which are potentially dangerous situations.

The third objective, supposing there are no overloads, is to open as few sectors as possible. Finally, we would like to balance the workload as well as possible across the ATC sectors, by minimizing under-loads and selecting configurations where the p normal probabilities are as close as possible to 1.

In some previous papers, the cost was expressed as a number where the leftmost digits were assigned to sub-costs with the highest priorities. Note however that there is no need to express the cost as a real number, as long as we are able to compare two configurations. In the current paper, the cost is defined as a record structure, whose attributes contain sub-costs. This removes some numerical problems that were encountered when restricting sub-cost values to a chosen number of digits.

The sub-costs assigned to a configuration c = {s i /i ∈ [1, m]} are the following, in decreasing order of priority:

• the number of ATC sectors above the maximum allowed number, when such a constraint is defined.

• the maximum value of probability p high (s i , t) across overloaded sectors, except when this value is 1 23 for the two configurations we are comparing. In this case, this criterion alone does not allow highly overloaded configurations to be compared, and we will simply use the number of aircraft in the sector instead 24 ,

• the total number of ATC sectors in the configuration,

• the maximum value of probability p low (s i , t) across under-loaded sectors,

• the maximum value of (1-p normal (s i , t)) across normally loaded sectors.

When comparing two candidate configurations, we simply compare these sub-costs in decreasing order of priority. Now let us describe the algorithms that build valid airspace configurations and select the optimal one, using the above cost comparison.

Exhaustive tree search

Figure 1 illustrates a tree search that builds all valid combinations of airspace modules, on the same example as before. Here, each tree node is a list of couples where the first element is a group of modules, and the second is the list of valid ATC sectors that contain these modules, but no modules from the other groups of the node. Let us illustrate how this tree is built. The root is a node containing a single group {1}, made of only one module. The possible ATC sectors for {1} are s = {1}, d = {1, 5}, and e = {1, 2, 3, 4, 5}. From this point, we may add a second module, say 2, either in the same group already containing 1 (left branch), or in a new group (right branch). For the left branch ({1, 2}), the only ATC sector containing both 1 and 2 is e. For the right branch ({1} and {2} as separate groups), the list of possible ATC sectors for {1} now contains only s = {1} and d. The ATC sector e is no longer a valid possibility: it contains 1, but also 2 which is already in a separate group. For this group {2}, the valid ATC sectors are s = {2} and a = {2, 3}.

While exploring this tree, it may happen that the list of possible ATC sectors becomes empty. This is the case for example with the node made of groups {1, 2} and {3} (when developing the left branch). There is no valid ATC sector containing both 1 and 2 which does not also contain 3. There is no need to develop further this node, as it will never lead to an operationally valid airspace partition.

The selection of the best airspace partition is made according to the cost criteria defined in section 5.1, which depend on the number of ATC sectors and the values of the probabilities p low , p normal , and p high issued by the neural network for each control sector of the considered airspace configuration.

The exhaustive tree search may be computationally intensive, or even not feasible in a reasonable amount of time, when the number of elementary airspace modules and possible ATC sectors is too high.

Branch & Bound

Let us describe the Branch & Bound algorithm used to build airspace configurations. The main difference with the exhaustive tree search is that, for each node being explored, a lower bound of the costs of all leaves (full configurations) that can be reached from that node is computed. If this lower bound is higher than the cost of the best configuration found so far, then there is no need to continue the search from this node.

Figure 2 shows how the tree is explored, on the same example as in the previous subsection. In the beginning (steps 1 to 4 in the figure), the search is performed like in the exhaustive search, until a first valid configuration is reached (step 5). Afterwards, the best configuration is memorized, together with its cost, and the following nodes are evaluated and compared to this best configuration.

The cost of a node is similar to the cost of a configuration (see subsection 5.1), except that we consider the best possible choice from among all the control sectors associated with each group in the node, so as to provide a lower bound of all full configurations that can be obtained from that node.

In the example shown in Figure 2, the cost function for configurations is denoted cost, whereas the cost function for a node is denoted cost . When evaluating the cost of node [({1}, {s, d}); ({2}, {s, a})] in step 6, we shall take the best possible choice for group {1}, from among singleton s = {1} and valid group d = {1, 5}, and for group {2}, we will choose among singleton s = {2} and valid group a = {2, 3}. Let us say that the best possible choices are d for group {1} and a for group {2}. The node cost cost ([({1}, {s, d}); ({2}, {s, a})]) is then equal to cost([d; a]), the cost of a virtual, and incomplete, configuration containing only these two ATC sectors.

Note that choosing the best ATC sector for each group in the node may lead to virtual configurations that are not airspace partitions. In step 8 for example, a virtual configuration with d = {1, 5}, a = {2, 3} and c = {4, 5} is not a valid airspace partition as module 5 is in both sectors d and c. However, this heuristic ensures that the cost of a node is always lower than the cost of any valid configuration that can be reached from that node.

Predicting airspace configurations throughout the day

Description of the algorithm

So far, we have seen how a neural network could be used to assess the controller workload for any given ATC sector, and how to partition the airspace so as to balance this workload as well as possible among all sectors, at any given time t. Now, let us see how to build an airspace configuration schedule for a whole day of traffic.

Finding an optimal airspace partition of the whole airspace at every moment of the day seems the most straightforward solution, but it would lead to a succession of drastically different configurations in short periods of time. In reality, the airspace is reconfigured around 30 times a day (for French airspace), and usually with relatively minor changes from one configuration to another. The reason is that transferring one or more airspace modules from one controller to another must be done safely, ensuring that the receiving controller does not miss any potentially dangerous situations in the new traffic and the new airspace sector he will have to handle.

Initial configuration (t=0):

1 ATC sector ←all elementary airspace modules 2. At each time step (1 minute):

• Decide if airspace must be reconfigured -→ check workload in each ATC sector

• If so, reconfigure airspace:

select modules to recombine, explore all combinations, select configuration with minimum cost. So it was decided to mimic the actual behaviour of control room managers as well as possible, keeping the current airspace configuration as long as it remained acceptable. Figure 3 describes the main loop of the chosen algorithm. The current airspace configuration is checked at every time step. If the workload in some sectors of the current configuration is really too low (p low close enough to 1) or too high (p high close enough to 1), then a reconfiguration is triggered. Depending on a user-preferred option, either only a few sectors are recombined, or the whole airspace is reconfigured.

Let us recall that the network was trained on observed sector statuses (merged, normally operated, or split). So, when a configuration change is triggered, one might interpret the network output as a recommendation to split or merge the triggering sector. This output is just a workload indication, though, and the tree search algorithm does not restrict itself to splitting or merging sectors: it recomputes a new optimal partition of the set of modules chosen for recombination.

As a result, the transition from one configuration to the next may show split sectors, merged sectors, or modified boundaries between two ATC sectors due to the transfer of one or several modules from one sector to the other.

There may be even more complex recombinations such as A, BC, D, E -→ AB, CDE (where A,B,C,D, and E are airspace modules). Some of these complex recombinations may actually not be feasible in operation. In future work, we plan to optimize sequences of configurations while satisfying constraints on the transitions, allowing for example only one simple change per sector: split, merge, shift boundaries, or open a new sector made up of modules transferred from other sectors.

Decision criterion

In order to describe more formally the decision criterion triggering the configuration changes, let us consider our three probabilities (p low , p normal , p high ) sorted by decreasing values p 1 , p 2 , p 3 . The decision criterion is expressed as follows, depending on which probability is the highest:

• if p 1 is the probability p low that the workload in the sector is too low: the decision to reconfigure is taken only if 1 -p 1 < α

• if p 1 is the probability p high that the workload is too high: we decide to reconfigure only if 1 -p 1 < β, where β is a chosen parameter.

In the other cases, the sector does not trigger a reconfiguration. We choose different criteria for probabilities p low and p high , because we may need to be more reactive when the workload is increasing than when it is decreasing.

Choosing the sectors to recombine

When a reconfiguration is triggered, we can adopt different strategies when building the set of sectors to recombine. We can select either:

• only the triggered sectors (p high or p low close enough to 1),

• or the sectors for which p high (or p low ) is higher than the other two probabilities. This usually gives us a slightly larger set than with the previous criterion,

• or the previous set to which we add the neighbouring air traffic control sectors. This increases the chances of a better local recombination, especially for under-loaded sectors. These sectors cannot be recombined alone, whereas overloaded sectors can always be split as long as they are made up of several modules,

• or all the sectors. This allows an optimal partition for the whole airspace to be found.

The user can choose one of the above options, or a mix of local and full recombinations. In the latter case, the default behaviour is to make a local recombination (for example only sectors for which the probability p high or p low is the highest), except when there are more than 2 connected components (or a chosen number) in the set of ATC sectors to recombine. In this case, a full airspace reconfiguration is triggered. The rationale underlying this logic is that there are some cases when the limited recombination is not sufficient, for example when there are two under-loaded sectors that are not geographically adjacent.

Sectors can be recombined using either the exhaustive tree search for local recombinations only, or the branch & bound for both local and full reconfigurations. The results presented in this article are obtained with full reconfigurations with the branch & bound. Before presenting these results, let us detail the experimental setup.

Experimental setup

Discussion on the choice of input trajectories

The neural network was trained on actual aircraft trajectories (see details in the next subsection). When trying to forecast airspace configurations, the input trajectories were simulated from flight plans.

Choosing radar tracks to tune the workload model and flight planned trajectories to predict future workload may introduce a bias between modelling and forecasting, as the actual trajectories may have changed from the planned trajectories, due the controllers' actions. With radar tracks, trajectory conflicts are solved by the controllers before separation losses 25 actually occur, whereas this is not the case when using flight plans. So the proximity-related metrics relying on the distance between aircraft, as well as the conflict-related metrics, may be under-estimated when using radar tracks instead of flight planned trajectories. This may have slightly biased the selection of relevant metrics (see section 3), although the conflict-related metrics that were implemented in our initial set of metrics use relative directions and velocities, so potential conflicts should be correctly detected with enough anticipation, before trajectories are deviated by the controller. In any case, these biases should remain small, considering the relative influence of conflict-related metrics when compared to the aircraft count, the sector volume, and other metrics (see [START_REF] Gianazza | Evaluation of air traffic complexity metrics using neural networks and sector status[END_REF] and [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF]).

So we use radar tracks for workload modelling, and flight planned trajectories for forecasting purposes, as we have no better guess on where the aircraft will be in the future. In future works, a mix of radar tracks and intended 26 trajectories may provide greater accuracy. After this discussion on the possible biases due to the chosen input traffic, let us return to the details of our experimental setup.

Training the neural network on historical data

For the results shown below, the neural network was trained on data samples from 2nd June, 2003, using recorded traffic ("radar" tracks) and sector opening archives from the five French air traffic control centres (ATCCs).

The data set used to train the neural network was built by measuring the relevant complexity metrics every minute of the day, in all ATC sectors of the five centres. The complexity metrics were computed from the aircraft trajectories and sector geometry. The training and test patterns were made from the input complexity metrics and from the observed state of each sector, merged, normal (i.e. actually operated), or split, coded as a state vector (see section 4). Data samples corresponding to a state where the sector is neither operated, nor split into several smaller sectors, nor collapsed within a larger sector were discarded, as we cannot deduce anything on the actual workload from such states.

In our training set, about 46% of the observed patterns fell in the merge class, 27% in the normal class, and 27% in the split class. Detailed results on the neural network outputs can be found in previous publications ( [START_REF] Gianazza | Evaluation of air traffic complexity metrics using neural networks and sector status[END_REF], [START_REF] Gianazza | Selection and evaluation of air traffic complexity metrics[END_REF], [START_REF] Gianazza | Smooth traffic complexity metrics for airspace configuration schedules[END_REF]). Let us just say that the correct classification rates across all classes were around 85% with a feed-forward neural network with 15 hidden units, when using smoothed input metrics (see [START_REF] Gianazza | Smooth traffic complexity metrics for airspace configuration schedules[END_REF]). Considering each class individually, we obtained 90% of correct classifications for the merge class, 68% for the normal class, and 93% for the split class. The results on the test set were quite consistent with those obtained on the training set. We have a feeling that these results could still be improved by considering the input metrics as time series and by using recurrent neural networks, but this remains to be done.

Choice of parameters

Our initial results with a straightforward decision criterion based on the highest probability, and with raw complexity metrics as input showed too frequent configuration changes during the day, although the evolution in the number of ATC sectors stayed fairly close to the actual airspace configurations.

The choice of parameters α and β27 for the decision criterion was discussed in [START_REF] Gianazza | Airspace configuration using air traffic complexity metrics[END_REF]. The best compromise that was found was α = 0.1 and β = 0.3. These values mean that our algorithms are more reactive when the workload increases than when it decreases. This seems to reflect the controllers' actual behaviour.

Smoothing the input metrics over 30 minutes with a "moving average" method also improved the results for an air traffic control centre with large sectors such as Brest ATC centre 28 . We use these parameters in the results presented in this paper.

Assessing the airspace configuration on recorded trajectories

In addition to the neural network evaluation, we also need to assess the airspace configurations produced by our algorithms. A first step to validate our approach was to compute the complexity metrics from real recorded traffic ("radar tracks"), and compare the resulting configurations to the actual sector openings.

Ideally, the computed schedules should reproduce the actual configurations recorded that day. However, there is a high variability in the decisions made by control room managers on how to reconfigure the airspace, which comes in addition to the variability of decisions on when to reconfigure. We may hope that our workload model could give an indication on when to trigger a reconfiguration and allow the tree search method to build realistic configurations, but our algorithms may not compute exactly the same configuration as in reality.

So we will mainly assess the realism of the computed schedule by comparing the number of ATC sectors in our computed configurations with the actual number of sectors open on the same day. Pearson's correlation coefficient may give an indication of the linear correlation between the computed and the real number of sectors. However, this may not always be reliable29 so we will also compute an ad-hoc "dissimilarity measure", which is the surface delimited by the two curves (computed and real number of ATC sectors operated during the day), divided by the surface between the x-axis and the curve of the real number of ATC sectors. With this measure, two identical curves have a dissimilarity 0 if they are exactly superposed. In addition, we will also consider the number of reconfigurations throughout the day, which should be close enough to the real one.

Assessment of the airspace configuration forecasted from planned traffic

Radar tracks are available only after the aircraft have flown through the airspace. The proposed algorithms may be useful only if we are actually able to forecast airspace configurations before the aircraft enter the airspace.

For this purpose, predicted aircraft trajectories are simulated from the anticipated traffic demand (i.e. flight plans filed by the airline operators), using a fast-time simulator (see [START_REF] Durand | CATS, a complete air traffic simulator[END_REF], [START_REF] Durand | Optimal resolution of en route conflicts[END_REF]). The resulting airspace configuration schedule is then compared both to the prediction that was made the day before by flow management, and to the actual sector openings. Let us now see a few results, starting with the validation on historical data.

Results

Comparison to real configurations, using recorded traffic

The model tuned on 2nd June was tested on two other days of traffic, using recorded radar tracks as input. Figure 4 shows the number of air traffic control sectors in the computed configurations, and the real number of ATC sectors that were open on 6th June 2003, in Brest air traffic control centre. The upper curve shows the number of aircraft within the centre boundaries, as an indication of the total traffic that day. Note that this curve is related to the y axis on the right, and that it has been shifted upward so as to make the figure more readable. The left y axis shows the number of sectors, and the x axis is the time, expressed in minutes after 0h00.

As shown on this figure, the computed number of sectors is fairly close to the actual number of sectors that were operated that day. The dissimilarity measure is 0.191 and Pearson's correlation coefficient is 0.91. Our algorithms found 46 configuration changes, whereas there were 33 in reality.

The total number of aircraft within the centre (upper curve) is given as a very crude indication of the overall workload. We can observe that the number of ATC sectors follows this curve more or less, although not always strictly. One should bear in mind that the traffic may be dispatched differently across the sectors throughout the day, and also that the number of aircraft is not the only factor of air traffic complexity and workload. Still, this traffic curve gives a good hint of the traffic variations throughout the day, and allows finer interpretations of the other curves. Figure 5 shows the same information, but for 7th June 2003. For that day, the algorithms show slightly better results, with a dissimilarity measure of 0.115 and a correlation coefficient of 0.94. There were 37 computed configurations, against 33 in reality.

The two figures, 4 and 5, illustrate the fact that the model only reflects the average behaviour of air traffic controllers and control room managers when they decide to split or merge sectors, or reconfigure otherwise. There are variations in this behaviour among the population. Some controllers are more experienced or more efficient than others and may consequently manage higher workloads, or there may be younger controllers completing the final period of their training under the supervision of fully qualified instructors. Figure 6 shows the traffic in Brest airspace on 6th June 2003, and the number of ATC sectors in the configurations computed with either the real traffic or the simulated traffic as input. In the latter case, a fast-time 30 air traffic simulator was used to compute the aircraft trajectories from the flight plans of the initial traffic demand. This is typically what might be done in a pre-tactical context, well before flights take off, when no radar tracks are available.

We can observe the differences between the planned traffic and real traffic by considering the two upper curves in Figure 6. Although it may be described as a statistical phenomenon ( [START_REF] Gwiggner | Uncertainties and Interpretation in Flow Planning[END_REF]), this difference between planned and real traffic is rather difficult to anticipate with great accuracy in a given sector at a given time. This leads to uncertainties when forecasting the complexity metrics used as input to the neural network.

Missing flight plans or short-notice departures may indeed lead to drastically under-estimated aircraft counts and other complexity metrics (see [START_REF] Sridhar | Airspace Complexity and its Application in Air Traffic Management[END_REF]), especially for departure sectors. Considering the results in Figure 6, this does not seem to be the case with our flight plan data and with the considered en-route ATCC. However, we still observe some differences that may stem from navigation uncertainties, re-routings, flight cancellations, etc. These uncertainties on planned traffic do have an influence on the quality of the forecast, although this influence is certainly somewhat lessened by the use of a moving average method to smooth the input metrics.

Flight planning uncertainties may be reduced by using a mix of radar tracks and flight intentions, if the proposed algorithms are to be used in a tactical context where complexity metrics are forecast 20-30 minutes ahead. In any case, the difference between planned traffic and actual traffic may be an important source of error. The quality of the prediction depends on the reliability of the 4D-trajectory forecast.

Comparison with the current forecast

Let us now compare our forecast, using planned traffic, with the actual prediction made on the same data by the flow management operators. We can see in Figure 7 that the schedule computed with planned traffic as input is much closer to the number of control sectors that were actually open that day than what was predicted by the FMP operators from the same flight plans that we used.

The dissimilarity metric measuring the difference between prediction and reality is 0.568 for the FMP schedule, whereas it is only 0.137 for our fore- Finally, let us illustrate what may be the most useful application of the proposed algorithms. So far we have not introduced constraints on the maximum number of ATC sectors in each configuration. Running the algorithms without such constraints allows the operator to check if the duty roster is sufficient to handle the planned traffic.

Now, what happens if for some reason, there are not enough controllers, or not enough working positions available to handle the traffic? In such cases, the cost comparison described in section 5.1 allows the branch & bound algorithm to find configurations that satisfy such constraints while balancing the workload as well as possible. In Figure 8, we have constrained the maximum number of control sectors to 4 between 00h00 and 06h00, 8 between 06h00 and 08h30, 10 between 8h30 and 20h00, and finally 4 after 20h00. The figure shows the number of sectors for both solutions, with or without constraints. An experimental human-machine interface is currently under development, with the aim of demonstrating and refining the proposed algorithms. Figure 9 shows the general view of the sector opening schedule for Brest centre, without constraints, over one day of traffic. Each column represents a partition of the airspace into ATC sectors. A pop-up window (not shown) may give more details on each configuration when browsing over the coloured boxes. The colour code is the following: blue when the sector is under-loaded, green when it is normally loaded, red when it is overloaded (although there are none here, without constraints). Coloured dots on the right of each box give an indication of which workload threshold (low or high) triggered the configuration change.

When posting no constraints on the maximum number of sectors, this display shows how many sectors would be necessary to handle a given traffic demand. This could allow the staff manager to adapt the duty roster to the input traffic. Note that without constraints, only ATC sectors made up of a single airspace module can be overloaded: otherwise a sector composed of several modules would have been split into two smaller sectors when becoming overloaded. Figure 10 shows the same situation, with constraints on the maximum number of sectors. We can observe the overloaded control sectors shown in red. Such a display could help flow managers to take preventive measures (departure delays, reroutings) so as to prevent such dangerously overloaded situations from actually occurring.

The user can switch to a more detailed view, as shown in Figure 11 where the workload evolution across time is displayed for each selected sector. For this purpose, each selected sector box shows the three probabilities issued by the neural network, stacked one above the other, using the same colour code: blue for p low , green for p normal , and red for p high . The transitions between airspace configurations are also shown.

Conclusion and perspectives

Summary remarks

Forecasting airspace configurations requires at least two things: first a model assessing the controller workload for any given ATC sector in traffic conditions of variable complexity, and second an algorithm providing an optimal partition of the airspace into ATC sectors. The proposed workload model assumes that the observed sector operations reflect the controllers' actual workload: ATC sectors made of several modules may be recombined when the workload is either too high or too low. The model relies on a neural network to issue workload probabilities, using the sector volume and a selection of air traffic complexity metrics as input. Among several others found in the literature, these metrics appeared to be the most correlated to the observed sector status in past operations. Some others also proved relevant but were redundant with the selected variables and slightly less relevant. As the literature is fairly extensive on this subject, we have not implemented all existing metrics, and other complexity factors may be tried in the future that might improve the model.

The partitioning problem, which is highly combinatorial when considering all the possible combinations of airspace modules, has been addressed using standard tree search methods. This was made possible by restricting the tree search to partitions made up only of ATC sectors described in the ATCC databases. The neural network output probabilities were used to assess the cost of candidate configurations while exploring the tree.

This hybrid method was first tried on recorded traffic, and assessed by comparing the results to the archived sector openings. The neural network was trained on data collected in the five French ATC centres on 2nd June 2003 and assessed on two other days (6th and 7th June 2003). Two measures were used to quantify the differences between the computed output and reality: a dissimilarity measure accounting for the differences in the number of ATC sectors, and the number of configuration changes.

The proposed method showed that the number of ATC sectors was fairly close to the actual one. The dissimilarity measure was 0.191 on 6th June and 0.115 on 7th June. However, the number of configuration changes was still above what actually occurred in reality: 46 against 33 in reality on 6th June, and 37 against 33 on 7th June.

After outlining the possible sources of bias and forecasting errors that may occur due to the difference between the planned traffic demand and actual flights, we tried our algorithms on simulated trajectories computed from flight plans. The comparison to the actual forecast made by the flow management operators shows that our prediction is far more realistic than those done currently in operations: the dissimilarity measure is 0.137 for the computed configurations, and 0.568 for the FMP forecast on 7th June.

Limitations of the proposed method

In our results, the influence of flight planning and navigation uncertainties was certainly somewhat lessened by two factors. First by the use of a moving average method to smooth the input metrics (including the aircraft count), and second by the fact that the neural network trained on historical data reflects the average behaviour of controllers and control room managers over the observed past airspace operations.

Concerning the first factor, one must be aware that there is a trade-off between smoothing the metrics and the forecast accuracy. In fact, averaging the metrics over too long a period delays the times when airspace configuration changes are predicted. This might motivate further research, using time series, instead of smoothing the input metrics with a moving average method.

Dealing with flight planning uncertainties may have an influence over the context in which the proposed algorithms could be used. A certain level of uncertainty and the use of smoothed metrics may be acceptable in a pretactical context, when roughly assessing how many ATC sectors are necessary to handle the planned traffic. But this same level of uncertainty may not be acceptable for a tactical tool, when overloads need to be anticipated with greater accuracy. However, we can expect to reduce these uncertainties by using a mix of radar tracks and flight intentions.

These issues need to be further explored, through scientific studies eventually involving ATC experts in real-time experiments. In any case, it must be underlined that one cannot expect a highly realistic airspace configuration forecast without an accurate 4D trajectory forecast.

Let us finally highlight a restriction in the use of the proposed algorithms: the workload prediction model is tuned on historical data and reproduces the average past behaviour of control room managers and air traffic controllers. So it should not be used by control room managers actually to decide how to split or merge sectors. This would freeze the whole system and always reproduce the same behaviour. The proposed hybrid method should in fact be seen as a forecasting tool for flow managers or multi-sector planners.

Potential gains in operational perspective

Considering the difference (see Figure 7) between the sector opening schedule made by the FMP operator and the actual sector operations, the potential benefits in staff costs that could be expected from a more accurate forecast are obvious.

However, several arguments mitigate this statement. One cannot expect to adjust the staff variable perfectly to the traffic demand on an everyday basis, even with a perfect airspace configuration forecast. The staff variable is adjusted to peak traffic demand, estimated well in advance, as it takes several years to train a controller: air traffic controllers are a highly trained and highly qualified work force. The total number of controllers in operation cannot be fine-tuned over the year: this would mean employing fewer controllers in the winter than during the summer for example, which is not easily feasible. Also, air traffic management is a world of uncertainties (take-off times, unexpected delays, sector entry times, weather disturbances, etc): some researchers refer to the "stochastic" nature of air traffic planning. Consequently the overall system also needs to deal with these uncertainties. The fact that the FMP schedule requires more staffing than what is actually necessary is also a safety margin that can be useful when unexpected peaks of traffic occur. It also reflects the flexibility of the current system: merging sectors or reconfiguring the airspace in real-time when the workload is low also allows air traffic controllers to maintain their proficiency by handling a large enough amount of traffic at all times of the day. So, in fact, it is not cost efficiency or flexibility (the system is already highly flexible in real time) that we could improve the most with the proposed algorithms, it is the predictability of the system.

It is expected that our algorithms could be used, possibly by flow management operators or multi-sector planners, to forecast airspace configurations and controller workload with greater accuracy than today's empirical method. This would allow better anticipation of potentially dangerous situations, and preventive measures to be taken well in advance when some sectors are predicted to be overloaded.

When using our algorithms without constraining the maximum number of ATC sectors, they could be used to assess how many sectors would be necessary to handle a given traffic demand. Posting constraints on the number of ATC sectors could help flow managers to forecast potential overloads in the circumstances of the day (duty roster, or limited number of controller working positions).

The potential gain in operations remains to be assessed through real-time experiments, and the HMI currently under development may be used for this purpose in the future.

Further work

This work was a first approach to the problem. Time-dependencies were not explicitly taken into consideration, except through the use of complexity metrics that are related to traffic flows over a period of time. A simple feedforward neural network was used, and its output only depends on a snapshot of the metrics values at every time t.

In future work, we plan to improve the workload prediction model by considering each input metric as a time series, and by using recurrent neural networks like the Jordan network ( [START_REF] Jordan | Serial order: a parallel distributed approach[END_REF]), trained with backpropagation through time ( [START_REF] Rumelhart | Learning internal representations by error propagation[END_REF], [START_REF] Werbos | Proceedings of the IEEE[END_REF], [START_REF] Williams | Gradient-based learning algorithms for recurrent networks and their computational complexity[END_REF]).

The opening schedule algorithm also needs improvements, such as checking if there is a feasible path from one configuration to another. At the beginning of this conclusion, we stated two issues when forecasting airspace configurations: predict the workload, and find an optimal airspace partition. In fact, we can add a third one, which is to find an optimal sequence of airspace configurations throughout the day, satisfying some constraints on the transitions between airspace configurations.

We have partially addressed this third issue by allowing local recombinations of sectors from one configuration to the next. However, we still need to explore this issue further by applying tree search methods through a whole sequence of successive candidate configurations, instead of successively applying the tree search at each time step. Constraint programming techniques could be useful for this purpose.

The work presented in this paper will be included in the contribution of the French Air Navigation Services Provider to SESAR, the major European R&D programme.

A. Glossary of terms

Elementary airspace module: a volume of airspace to which a radio frequency is assigned that may be used for communications between the aircraft flying in this volume and the air traffic controller in charge of aircraft separation. Modules can be combined (i.e. grouped onto one working position) to form larger ATC sectors, depending on the controller workload. Note that the usual term to denote these airspace modules is sector, which might be confusing as sector can either denote a single airspace module, or an air traffic control sector made up of one or more modules. So in this paper these elementary geographic sectors are referred to as modules, in order to avoid confusion with ATC (Air Traffic Control) sectors.

ATC sector: volume of airspace made up of one or more elementary airspace modules, operated as a single unit by a team of usually two controllers ("radar" and "planning").

Controller working position: a piece of furniture with radar screens, radiocommunications equipment, telephones, systems interfaces, etc, operated by two controllers in charge of a control sector.

Airspace configuration: mapping of the set of elementary airspace modules onto a smaller number of controller working positions. It can also be seen as a partition of the ATC centre's airspace into control sectors.

Sector opening schedule: (or opening scheme) the successive airspace configurations that are predicted over a period of time in the future.

  As an example, let us imagine an ATCC airspace divided into 5 modules {1, 2, 3, 4, 5}. Let us say that the possible combinations of modules into ATC sectors are a = {2, 3}, b = {3, 4}, c = {4, 5}, d = {1, 5}, and e = {1, 2, 3, 4, 5}, to which we may add each module operated as a single sector. A valid configuration shall be a partition of the set of airspace modules into ATC sectors: for example [({1}, s); ({2, 3}, a); ({4, 5}, c)], or [({1, 5}, d); ({2}, s); ({3, 4}, b)], where s is the generic notation for a singleton.

3 ,Figure 1 :

 31 Figure 1: Exhaustive tree search algorithm for airspace partitioning.

Figure 2 :

 2 Figure 2: Branch & Bound algorithm for airspace partitioning.

Figure 3 :

 3 Figure 3: Iterative algorithm for airspace sectors opening schedule.

Figure 4 :

 4 Figure 4: Computed vs. real configurations (Brest ACC, 6th June 2003), using real traffic as input.

Figure 5 :

 5 Figure 5: Computed vs. real configurations (Brest ACC, 7nd June 2003) using real traffic as input.

  traffic (initial traffic demand) Configurations with planned traffic Real traffic (radar tracks) Configurations with real traffic

Figure 6 :

 6 Figure 6: Initial traffic demand (flight plans) vs. real traffic (radar tracks), in Brest ACC on 7th June 2003.

  planned traffic) Computed configurations (planned traffic)Real configurations

Figure 7 :

 7 Figure 7: Airspace configuration forecast using flight plans as input: computed prediction vs. current FMP prediction (Brest ACC, 7th June 2003).

cast 31 . 8 . 4 .

 84 Results with or without constraints on the number of sectors

Figure 8 :

 8 Figure 8: Airspace configuration forecast with or without constraints on the maximum number of ATC sectors (Brest ACC, 7th June 2003).

Figure 9 :

 9 Figure 9: HMI display of the airspace configuration forecast, without constraints (Brest ACC, 7th June 2003).

Figure 10 :

 10 Figure 10: HMI display of the airspace configuration forecast, with constraints (Brest ACC, 7th June 2003).

Figure 11 :

 11 Figure 11: Details of some overloaded control sectors when enforcing constraints on the number of available working positions (Brest ACC, 7th June 2003).

  ATC: Air Traffic Control.ATCC: Air Traffic Control Centre. A managerial unit in charge of a volume of airspace divided into a number of sectors.

	ATM: Air Traffic Management.
	ATFM: Air Traffic Flow Management
	CFMU: European Central Flow Management Unit
	FMP: Flow Management Position

SESAR: Single European Sky ATM Research Programme.

An air traffic control sector should not be made up of several disconnected volumes of airspace.

Flights following standard routes should not exit and re-enter the same control sector.

For example: no more than N flights per hour over point P for flights originating from geographic area Z

SESAR: Single European Sky ATM Research Programme, where ATM stands for Air Traffic Management.

A qualification zone is usually the whole airspace of an air traffic centre, or half of it.

Note that this may not always be the case for all Air Navigation Service Providers. Some control centres are far less flexible in the way they merge or split sectors, and strictly follow a pre-defined duty roster. However, in the chosen context (France) and in many countries, the airspace configuration is highly flexible and is adapted in real-time.

Some other terms (such as operational, manned, or "armed") may be found in previous papers for this status which denotes that the sector is, or could be, operated in its normal workload domain.

At a given time of the day an ATC sector, defined as a group of airspace modules, may be split, merged, normally operated, or be in a nondescript state where, for example, some of its modules are part of a larger sector, and the rest are operated normally, or split, or merged into another sector. In such cases, the observed state cannot be interpreted as an indication of the actual controller workload.

In the French upper airspace, and in many other European countries, the horizontal separation between two aircraft should be at least 5 nautical miles, unless their vertical separation is at least 1000 feet. A "conflict" occurs when it is expected that the future relative positions will not achieve this separation.

A flight plan is sent by the airline operator before take-off, describing the planned route, requested flight levels, and other basic flight intentions.

AIC: "An Information Criterion"

This inter hori metric with its 20-degree threshold comes from a metric defined by the Eurocontrol Performance Review Unit with the aim of comparing the performance of ATC centres. It accounts for the fact that traffic following parallel routes is less complex to handle than traffic with crossing trajectories.

For example when, for sector AB, A is merged within a sector AC and B within another sector BD.

Note that this kind of domain-related interpretation would not be easy for other classes of algorithms either, such as polynomial regression.

Note that linear techniques can be seen as networks with linear units, and logistic discrimination as a network with sigmoidal units but with no hidden layer

In our context, a sector will be said to be overloaded (resp. under-loaded) when the probability p high (resp. p low ) is higher than the two others.

or close enough to 1, in practice

Note that such situations mainly occur when the number of ATC sectors is highly constrained.

In the french upper airspace, and in many other European countries, the horizontal separation between two aircraft should be at least 5 nautical miles, unless their vertical separation is at least 1000 feet. A "conflict" occurs when it is expected that the future relative positions will not achieve this separation.

"Intended trajectory" can be understood here as the baseline trajectory entered by the pilot in his flight management system (FMS), and from which he might deviate if instructed to do so by the controller so as to avoid other traffic. It may be different from the flight plan available in ground-based systems, or simply more accurate.

An additional parameter η expressing a threshold on the difference between the two highest probabilities was also used in[START_REF] Gianazza | Airspace configuration using air traffic complexity metrics[END_REF]. As this parameter was useless, considering the current values used for α and β, it was abandoned.

The smoothing strategy may vary from one centre to another: trials with centres where ATC sectors are smaller seem to show better results with a shorter time window, but no exhaustive results on this subject have been published yet.

The correlation coefficient between two equal variables x and y = x will be 1. Let us note however that this coefficient is not sufficient actually to measure how close we are to equality: the correlation coefficient between a variable x and another variable y = x + d, where d is a constant offset, will also be 1.

The simulation of a whole day of traffic over France takes about one minute of com-

The correlation coefficient is 0.91 for the FMP prediction and 0.93 for our prediction, which confirms that this coefficient is not usable to assess the quality of the prediction


Laureline Guys
email: laureline.guys@capgemini.com

Stéphane Puechmorel
email: puechmorel@cena.fr

Laurent Lapasset
email: laurent.lapasset@capgemini.com

Luca Amodei
email: luca.amodei@math.univ-toulouse.fr

Pierre Maréchal
email: pierre.marechal@math.univ-toulouse.fr

Génération automatique de trajectoires aériennes sans conflit à l'aide de fonctions biharmoniques

Keywords: fonctions de navigation, fonctions biharmoniques, trajectoires sans conflit

Introduction

Le projet SESAR1 a été mis en place afin de renouveler et d'uniformiser les systèmes de contrôle aérien sur toute l'Europe. Le système actuel de sectorisation de l'espace aérien ayant atteint ses limites, de nouvelles techniques de planification de trajectoires et d'aide à la décision doivent être mises en place afin d'aider les contrôleurs dans leur travail. Une des pistes envisagées consiste à contraindre un avion en position et en temps, ce qui permettrait de garantir l'évitement de conflit ainsi que l'heure d'arrivée de l'avion, réduisant ainsi de manière significative le nombre d'interventions nécessaires de la part des contrôleurs et permettant l'augmentation du trafic.

Les problèmes de génération et planification de trajectoires sont apparus pour la première fois en robotique et de nombreuses techniques ont été développées pour y répondre. Parmi elles, les fonctions de navigation (partie 2) sont une méthode prometteuse, permettant de générer des trajectoires garantissant l'arrivée à destination, ainsi que l'évitement d'obstacles. Les fonctions harmoniques sont un type particulier de fonctions de navigation qui présentent l'avantage d'être simples à calculer, mais l'inconvénient de donner des vitesses de vol très variables. Or dans le cadre de la navigation aérienne, la vitesse d'un avion doit respecter des bornes strictes, l'idéal étant d'obtenir une vitesse constante.

Plutôt que d'essayer de borner la vitesse obtenue avec une fonction harmonique à l'aide de lois de commandes, nous avons choisi de travailler ici avec une fonction biharmonique (partie 3) qui permet d'obtenir un champ de navigation à vitesse constante. Les fonctions biharmoniques présentent ce net avantage sur les fonctions harmoniques, mais sont également plus compliquées à calculer et demandent notamment un traitement particulier avant de pouvoir être utilisées pour la planification de trajectoires. Nous montrons de plus que les fonctions biharmoniques peuvent être ramenées au cadre des fonctions de navigation et qu'elles garantissent ainsi l'arrivée à destination et l'évitement d'obstacles. Enfin, nous expliquons comment utiliser une méthode de résolution sans grille afin de réduire le temps de calcul de notre méthode.

Définition et propriétés

Une fonction de navigation est une fonction de potentiel φ : E → [0, 1], E = R 2 \{obstacles} étant l'espace libre dans lequel les avions peuvent naviguer. Lorsque plusieurs avions volent dans le même espace, chacun considère les autres avions comme des obstacles, réduisant ainsi l'espace dans lequel il peut évoluer. À chaque avion correspondra donc un espace libre et une fonction de navigation. φ est alors construite de manière à être uniformément maximale à la frontière des obstacles et à n'accepter qu'un unique minimum : le point de destination. Sur le reste de l'espace libre, elle évolue de manière continue entre sa valeur maximale et sa minimale. Pour déterminer une trajectoire menant à la destination, il suffit alors de suivre les valeurs décroissantes de la fonction de navigation : -∇φ.

Pour garantir l'arrivée à destination et l'évitement des obstacles, une fonction de navigation doit vérifier une propriété supplémentaire : elle doit être Morse, c'est-à-dire que ses points critiques doivent être non-dégénérés. Un point critique est non-dégénéré si le déterminant de la hessienne de φ en ce point est non nul. Le caractère Morse de la fonction de navigation garantit que toute trajectoire obtenue en suivant -∇φ tendra vers l'unique minimum de la fonction de navigation (notre destination), sans passer par les obstacles.

État de l'art

Une fonction de navigation pour l'aérien : Rimon et Koditschek, les créateurs de la fonction de navigation, ont créé une fonction de navigation particulière pour la robotique [START_REF] Koditschek | Robot navigation functions on manifolds with boundary[END_REF]. Kyriakopoulos et Roussos ont par la suite repris et amélioré cette fonction de navigation afin de l'adapter à la génération de trajectoires aériennes [START_REF] Roussos | Decentralised navigation and collision avoidance for aircraft in 3D space[END_REF]. Cette fonction de navigation a néanmoins atteint ses limites. En effet l'imposition d'une vitesse constante le long de la trajectoire ne passe pas par la fonction de navigation elle-même, mais par des lois de contrôle sur l'avion. De même, le rayon de courbure des virages est limité par des lois de contrôle, mais sans prendre en compte la régularité de la trajectoire, donnant parfois des trajectoires chaotiques, certes réalisables, mais très peu appréciées par les pilotes et les passagers.

Une fonction harmonique comme fonction de navigation : Connolly et al. ont été les premiers à utiliser une fonction harmonique L, définie par △L = 0, △ l'opérateur laplacien, comme fonction de navigation [START_REF] Connolly | Path planning using Laplace's equation[END_REF]. Il est en effet relativement simple de construire une fonction harmonique afin qu'elle vérifie les propriétés des fonctions de navigation : on peut lui imposer un point minimum unique et la rendre uniformément maximale sur ses frontières. Il est également facilement démontrable qu'une fonction harmonique est Morse (voir annexe de [START_REF] Masoud | A discrete harmonic potential field for optimum point-to-point routing on a weighted graph[END_REF]). Les fonctions harmoniques ont été largement étudiées, que ce soit avec des conditions aux limites variées [START_REF] Masoud | Evolutionary action maps for navigating a robot in an unknown, multidimensional, stationary environment. II. Implementation and results[END_REF] ou pour la recherche de chemins sur des graphes [START_REF] Masoud | A discrete harmonic potential field for optimum point-to-point routing on a weighted graph[END_REF]. Elles présentent néanmoins l'inconvénient de donner un champ d'amplitude non constante, ce qui implique une vitesse de vol non constante pour les avions. Certaines conditions aux limites, comme la condition de Dirichlet, impliquent même que le champ de navigation est évanescent, c'est-à-dire qu'il tend exponentiellement vite vers zéro loin de la destination, rendant impossible l'atteinte de la destination en temps fini.

Ces deux types de fonctions de navigation présentant des défauts majeurs, nous cherchons à en créer un troisième, en utilisant des fonctions biharmoniques.

Les fonctions biharmoniques, c'est-à-dire les fonctions u qui vérifient △ 2 u = 0, sont très présentes en mécanique du solide et en mécanique des fluides. Masoud et Masoud furent les seuls à les utiliser pour la navigation de robots [START_REF] Masoud | Robot navigation using a pressure generated mechanical stress field : "the biharmonic potential approach[END_REF]. Les auteurs ont utilisé une analogie avec la mécanique du solide afin de générer leur champ de navigation. Ils ont considéré une plaque d'un matériau représentant l'espace libre de leur robot. A la destination du robot, ils ont imaginé un trou, dans lequel un ballon est placé. En gonflant le ballon, celui-ci exerce une contrainte P sur le matériau, contrainte qui se propage dans toute la plaque. De n'importe quel endroit de la plaque, il suffit de remonter ce champ de contraintes pour atteindre la destination. Les obstacles sont alors représentés par d'autres trous laissés vides, dans lesquels les contraintes ne pourront pas se propager et que le robot évitera donc naturellement. Les résultats obtenus par les auteurs montrent un champ de navigation d'amplitude constante, une caractéristique très intéressante pour la navigation aérienne. Ce sont donc ces fonctions biharmoniques que nous avons décidé d'étudier afin de générer nos trajectoires d'avion.

Obtention du champ de navigation à partir de l'équation △ 2 u = 0

En travaillant avec un logiciel adapté à la mécanique des structures, Masoud et Masoud ont choisi de travailler avec l'équation telle qu'elle est présentée dans la théorie de l'élasticité. Cette formulation rend cependant l'imposition des conditions aux limites relativement compliquée. Nous avons donc fait le choix de la simplifier et d'utiliser le système suivant en 2D :

     △ 2 u = 0 △ u = P à la destination, P > 0 △ u = 0 sur les frontières des obstacles. (1)
La résolution de ce système, puis le calcul de la hesienne de u, nous permet d'obtenir un champ de tenseurs, c'est à dire une matrice de dimension (2 × 2) en chaque point de l'espace, inutilisable tel quel pour la navigation. Pour obtenir un champ de vecteurs, nous calculons alors en chaque point le vecteur propre associé à la valeur propre minimale du tenseur, la seule utilisable pour générer le champ de navigation. C'est ce calcul de vecteur propre qui permet d'obtenir un champ de navigation d'amplitude constante. Un vecteur propre étant défini à une constante près et donc au signe près, le champ obtenu peut pointer vers la destination de l'avion ou à l'opposé de celle-ci. D'autres domaines de recherche, comme celui de l'imagerie médicale et de l'IRM de diffusion rencontrent les mêmes difficultés dans la récupération d'un champ de vecteurs à partir d'un champ de tenseurs. Pour résoudre ce problème, nous avons créé un algorithme de redressement de champ qui permet de retrouver, en chaque point, le sens dans lequel la direction donnée par le vecteur propre doit être suivie. Cet algorithme est fondé sur le fait que le champ de vecteurs obtenu doit être continu. Il oblige les vecteurs directement autour de la destination à pointer vers cette dernière, puis ces vecteurs, appelés «redressés», sont utilisés comme référence afin de redresser les vecteurs dans leur voisinage direct. Le processus est répété jusqu'à ce que tous les vecteurs aient été redressés. Ce n'est qu'après cette opération que le champ peut être utilisé pour faire naviguer notre avion.

Garantie d'évitement d'obstacles

Si les fonctions biharmoniques permettent d'obtenir un champ de navigation d'amplitude constante, elles sortent néanmoins du cadre des fonctions de navigation, ce qui implique la perte de la garantie d'évitement des obstacles. La solution de l'équation biharmonique étant un champ de tenseurs, on ne peut pas parler de caractère Morse pour cette solution. Notre but est donc, en utilisant la théorie de la singularité des applications différentielles, de nous ramener au cadre des fonctions de navigation en montrant que la solution de l'équation biharmonique est non-dégénérée en ses points critiques. Cela permettrait de garantir l'évitement d'obstacles pour le champ de navigation obtenu à partir de l'équation biharmonique.

Implémentation de la technique

Nous avons dans un premier temps implémenté cette technique pour un avion à l'aide de différences finies et d'éléments finis afin de vérifier le comportement de la solution de l'équation biharmonique. Les résultats s'avérant concluants et afin de préparer une étude sur le mouvement coordonné de plusieurs avions, nous avons ensuite implémenté cette technique à l'aide d'une méthode sans grille. En effet, chaque avion considérant les autres comme des obstacles, il nous faudra calculer un grand nombre de fois la solution de l'équation biharmonique, avec des frontières à chaque fois différentes. L'utilisation de la méthode des éléments finis impliquerait alors un remaillage de l'espace pour chaque calcul de la solution, ce qui est un processus très coûteux en ressources et en temps. L'utilisation d'une méthode sans grille permet de contourner ce problème. Dans le cadre de futurs travaux, cet algorithme servira de base à la construction d'une méthode permettant de planifier le mouvement coordonné de plusieurs avions.

Synthèse et perspectives

L

  'algorithme permettant la navigation d'un avion devant éviter un ou plusieurs obstacles statiques peut être présenté sous la forme suivante : • Choix de la destination • Construction d'un système de la forme (1) • Résolution du système à l'aide : } -→ Champ de tenseurs -d'une méthode avec grille (plus simple) -d'une méthode sans grille (plus rapide) • Calcul de vecteur propre associé à la valeur propre } -→ Champ de vecteurs minimale en chaque point • Redressement du champ de vecteurs par continuité -→ Champ de navigation • Calcul de trajectoire à partir de n'importe quel point de l'espace -→ Trajectoire garantissant l'évitement d'obstacles, l'arrivée à destination, avec une vitesse constante. TAB. 1 -Algorithme de génération de trajectoires

Single European Sky ATM Research