Philippe Averty
email: averty@cena.frguittet@recherche.enac.fr

Kévin Guittet

Pascal Lezaud
email: lezaud@recherche.enac.fr

An Ordered Logit Model of Air Traffic Controllers' Conflict Risk Judgment

Though there is a considerable agreement amongst past studies about the great variability in conflict judgments by Air Traffic Controllers (ATCos), certain behaviors observable in control rooms speak in favor of the existence of a common core they would that controllers share regarding conflict risk perception. The study presented in this paper began with the construction (from real recordings) of traffic scenarios showing two converging aircraft in approach. Three variables characterized these traffic scenarios, quantifying respectively horizontal separation, vertical separation and the momentum of the formation of the judgment (prediction time span). The conditions created by factorial manipulation of three variables led to the design of short scenarios (about 1min) involving two aircraft upon which 161 controllers gave their judgments about possible occurrence of a separation loss. A first descriptive analysis of the data, conducted in Averty (2005), confirmed the large variability of the experts' judgments but also clearly indicated the global consistency of the results. The data thus called for a deeper statistical analysis, the results of which will be presented in the article. In a first step, particular models have been constructed for each value of the prediction time span. The comparison of the model's parameters allows evaluating the influence of the time span on the conflict perception. It appears for example that the horizontal dimension has more "separating power" that the vertical dimension far from the conflict location, but that its relative importance diminishes (along with uncertainty) as the conflict resolves. Individual models are then nonlinearly aggregated into an "integrated model" by maximum likelihood estimation on the whole dataset. Finally, the relevance of this model to individual models is statistically validated, indicating that very few information has been lost in the aggregation process.

Introduction

Air Traffic Control (ATC) is composed of several tasks that generally overlap over time. The conjunction of these, especially in heavy traffic, may result in the controller's processing capacities being exceeded. Global agreement exists for aiding air traffic controllers (ATCos) by providing them with automated tools that would perform some of the most demanding subtasks. Among these, the Conflict Detection and Resolution (CD&R) processes are traditionally singled out. This sharing of tasks in real time between operator and system requires a sufficient knowledge of experts' key processing mechanisms, so as to comply with safety and capacity target levels. In this study, we address the conflict detection process and provide a predictive model of ATCos conflict judgments.

Relevant research in the domain of conflict detection can be categorized into two fields that include automatic detection schemes based on engineering intuition (CD&R systems) as reviewed in Kuchar and Yang (2000), as well as controller centered literature that aims at understanding the cognitive processes involved in the detection task and favors the investigation of factors that affects controllers performance [START_REF] Leroux | Cognitive Aspects and Automation[END_REF] [START_REF] Nunes | Identifying Controller Strategies that Support the Picture[END_REF]. The CREED project (Conflict Risk Evaluation based on Expert Detection) undertaken at the DSNA stems from these two fields as its objective is to provide an expert model of Conflict Detection, that is, a model that will have as output the expected conflict risk perceived by controller rather than a conflict/non conflict diagnosis based on objective threshold metrics as in usual CD&R systems.

To this end, a large experiment was conducted in which experienced controllers, confronted with pairs of converging aircraft in an approach environment, were asked to provide judgments about possible occurrence of a separation loss. In this article we analyze the collected data and present a statistical model that predicts the controllers' judgments for the conflict geometries considered in the experiment.

Our contribution is twofold. First, we show how information gathered from the cognitive literature on conflict detection can be exploited to describe the conflict geometry in a way that remains close to the mental representation of ATCos. Then, we show that this description can be used further to build a statistical model that performs well in predicting ATCo conflict risk judgments for the class of conflicts considered in the CREED experiment.

The paper is organized as follows. The first sections present a brief review of the existing research on conflict detection. We then detail the experimental plan and the assumptions which underpin it. The derivation of the statistical model is then presented and discussed.

Need to complete CD&R schemes

The difficulty in predicting an insufficient separation between aircraft stems from the fact that a significant amount of air traffic cannot be sorted out in advance into the two casesconflict and non conflictas long as the strict separation minima remain the criteria [START_REF] Alliot | A statistical analysis of the influence of vertical and ground speed errors on conflict probe[END_REF]. Indeed, a fundamental feature of ATC is that uncertainty vitiates the data required for making conflict diagnoses. This uncertainty includes a large range of different aspects: variability, ambiguity, incomplete or missing data, etc. These come from various (and varying) flight environment factorswind shift, engine parameters setting by pilots, etc.which result in inaccurate or even inappropriate conflict prediction. Management of this uncertainty is therefore central to the conflict detection process and appears to differ when it is processed by CD&R systems rather than by using ATCo expertise.

Thresholds metrics used in CD&R systems have indeed failed until now to adequately meet results of experts' heuristics, especially as they cannot easily take into account important cost aspects such as controller's workload (Kuchar and Yang, 2000). Consequently, the subset of conflicting aircraft coming from ATCo expertise and that coming from system algorithms are not the same in general, and can not be identified with the subset of factual "losses of separation" that would have resulted from the initial conflict contingencies. There is nothing inherently surprising in this difference as, in most cases, algorithms used in "tactical collision alerting systems" ultimately aim to automate the conflict detection and resolution tasks. As such, they are only marginally interested in complying with controllers' processes. [START_REF] Xu | Conflict detection in air traffic control: a task analysis, a literature review, and a need for further research[END_REF] acknowledge, however, that data on human performance could provide "a guideline for designers to develop and improve automated conflict detection that can off-load the controller's spatial temporal cognition". So, our guess is that a step forward could be made if a conflict detection model that reproduces the judgments of controllers could be proposed. From the workload point of view, this makes perfect sense as conflict-related measures of complexity have persistently been found to predict the controller's workload or assessment of traffic complexity in a number of studies, most of which were reviewed in [START_REF] Hilburn | Cognitive Complexity In Air Traffic Control -A Literature Review[END_REF] (see also [START_REF] Kopardekar | Measurement and prediction of dynamic density, 5 th USA/Europe Air Traffic Management R&D Seminar[END_REF] for a review of these variables and their integration in a "unified dynamic density metric"). If these variables, built on "objective" (as in Kuchar and Yang, 2000) conflict detections models, do well in predicting workload, why shouldn't analogous variables built upon a "subjective" model of conflict detection perform even better 1 ? A more ambitious application of such a model is provided by the ongoing European Community-funded project ERASMUS: the basic idea of ERASMUS (and so-called subliminal control) is that imperceptible alterations of an aircraft's speed or climb rate could be used to provide ATCos with "lucky traffic", where conflict contingencies are uncannily but "naturally" rare.

Accordingly, the objective of the "subliminal control problem" as presented in [START_REF] Crück | Subliminal air traffic control: Human friendly control of a multi-agent system[END_REF] is to "minimize the level of risk that will be perceived by the ATCo, using only imperceptible maneuvers". This requires that the controllers' judgments for any potential conflict situation can be estimated. Resource-consuming conflict situations could therefore be identified and avoided whenever possible.

Human-centered analysis of Conflict Detection

To build a predictive model of controllers' judgments on conflict detection, it seems necessary to understand how this task is performed in real field operations and to focus on the human centered aspect of conflict detection. Various cognitive processing and strategies are in fact likely to be used by ATCos but their connections with traffic configurations to which they are applied are not clearly established [START_REF] Xu | Conflict detection in air traffic control: a task analysis, a literature review, and a need for further research[END_REF] [START_REF] Loft | Modeling and Predicting Mental Workload in En Route Air Traffic Control: Critical Review and Broader Implications[END_REF].The fundamental result on the subject is that experience acquisition by ATCos particularly results in becoming long in heuristics and short in computing within the conflict detection process [START_REF] Bisseret | Application of signal detection theory to decision making in supervisory control: the effect of the operator's experience[END_REF].

This particular feature of ATC practice is responsible for the fact that a large part of conflict detection is automated. Indeed, perceptual processes -underlying detection processes -both involve heuristics and visually available data. As airspace structure and flow distribution in each sector determine specific locations and events from which conflicts are more likely to occur [START_REF] Loft | Modeling and Predicting Mental Workload in En Route Air Traffic Control: Critical Review and Broader Implications[END_REF], these processes are basically interpretation ones, automatic, influenced by context and expectation [START_REF] Willems | Air Traffic Control Specialist Visual Sanning II: Task Load, Visual Noise, and Intrusions into Controlled Airspace[END_REF] [START_REF] Landry | Perceptual grouping in Air Traffic Control[END_REF]. A daily repeated practice and the rule-based environment of ATC (published or usual trajectories) therefore allows controllers to substantially automating the detection process [START_REF] Leroux | Cognitive Aspects and Automation[END_REF]. Also, this prevalent use of heuristics is likely to favor the development of inter-individual differences that may well have existed ab initio: [START_REF] Law | Perceptual and cognitive factors governing performance in comparative arrival-time judgments[END_REF], for example, show that men and women differ in their ability to process velocities and distances concurrently. This explains why, when asked to estimate conflict risk, controllers put forward partly different judgments [START_REF] Averty | Conflict perception by ATCS admits doubt but not inconsistency[END_REF], which could, a priori, appear unexpected from full performance-level experts. For all that, this variability does not systematically prevent consistent judgments from emerging, since judgments also largely depend on objective features of the configuration of aircraft trajectories [START_REF] Averty | Conflict perception by ATCS admits doubt but not inconsistency[END_REF] (Nunes and Kirlik 2006).

Typically, separation assessment on the horizontal plane involves visual heuristics and generally calls for pattern processing [START_REF] Enard | Analyse de la prévision de séparation entre deux avions convergents sur l'écran radar[END_REF] [START_REF] Nunes | Identifying Controller Strategies that Support the Picture[END_REF] [START_REF] Xu | Conflict detection in air traffic control: a task analysis, a literature review, and a need for further research[END_REF].

Since conflict detection requires controllers to foresee future behavior and positions of aircraft, a projection process (extrapolation) is assumed using both the perceptible current flight data and the individual experiences of operators (Endsley, 1995) [START_REF] Xu | Conflict detection in air traffic control: a task analysis, a literature review, and a need for further research[END_REF] [START_REF] Davison | Modeling the Air Traffic Controller's Cognitive Projection Process[END_REF]) [START_REF] Boag | An analysis of relational complexity in air traffic control conflict detection task[END_REF]. Focusing on the former, the separation assessment in the horizontal plane requires the controller to evaluate the "time to conflict". While the time to the closest point of approach (CPA) is the exact information from which a possible miss distance could be inferred, [START_REF] Xu | Relative Importance of Conflict Geometry Variables in Influencing Pilots Conflict Detection Using a Cockpit Display of Traffic Information[END_REF] sensibly put forward that an intermediate step could exist in such a task, leaning on the 2-D trajectory intersection point (IP), easier to perceptually extrapolate than CPA. Although no evidence exists yet to explain the method they use, it is conceivable that ATCos initially grade conflict contingencies with regard to the mere distance of each target to the IP. This point has been reported to be neededi.e. extrapolatedby controllers [START_REF] Enard | Analyse de la prévision de séparation entre deux avions convergents sur l'écran radar[END_REF] [START_REF] Bisseret | Application of signal detection theory to decision making in supervisory control: the effect of the operator's experience[END_REF] [START_REF] Davison | Modeling the Air Traffic Controller's Cognitive Projection Process[END_REF]. The distance of each aircraft to this point is the salient information, biasing judgments [START_REF] Law | Perceptual and cognitive factors governing performance in comparative arrival-time judgments[END_REF]. The closest aircraft is indeed preferentially estimated as arriving first over the IP, even for cases where the velocity ratio actually makes the furthest away come first ("distance-over-speed" bias). In fact, the speed ratio has contradictory effects, according to literature [START_REF] Enard | Le degré de certitude dans l'estimation de la séparation entre deux avions convergents[END_REF] [START_REF] Xu | Conflict detection in air traffic control: a task analysis, a literature review, and a need for further research[END_REF] and it can be used in ATC for reinforcing a judgment that has already begun to emerge [START_REF] Bouju | Analyse de la prévision de la séparation entre deux avions évolutifs convergents[END_REF]. Furthermore, when present, acceleration is a parameter that controllers perceive with difficulty and do not frequently integrate into projected positions [START_REF] Davison | Modeling the Air Traffic Controller's Cognitive Projection Process[END_REF]. Despite being established from numerical values, and therefore needing some computation, altitude is often found to be the privileged parameter to establish conflict diagnosis [START_REF] Rantanen | Hierarchical Conflict Detection in Air Traffic Control[END_REF] [START_REF] Loft | Modeling and Predicting Mental Workload in En Route Air Traffic Control: Critical Review and Broader Implications[END_REF]. This diagnosis is magnified by the fact that numerous studies only involve aircraft flying levels. When vertical separation is not granted, aircraft attitudei.e. the fact they are level, climbing or descendingseems to have strong effects [START_REF] Lafon | Observations en trafic réel de la résolution des conflits entre avions évolutifs[END_REF] [START_REF] Lamoureux | The influence of aircraft proximity data on the subjective mental workload of controllers on the air traffic control task[END_REF]: except for non-radar separated aircraft, i.e. flying either at different altitudes or on clearly distinct routes, conflict judgment needs information on the four dimensions (spatial and temporal). As soon as one of the involved aircraft is climbing or descending (or supposed to get this attitude in the short or medium term), judgment will depend on whether the aircraft will be found to reach the same altitude at the moment of the position overlap on the horizontal plane [START_REF] Boag | An analysis of relational complexity in air traffic control conflict detection task[END_REF]. Rates of climb/descent by themselves are seldom used by controllers, bringing about inaccurate assessment of vertical positions [START_REF] Michard | Analyse de la représentation des trajectoires d'évolution chez les Premiers Contrôleurs[END_REF], except probably for aircraft of identical attitude [START_REF] Bouju | Analyse de la prévision de la séparation entre deux avions évolutifs convergents[END_REF]. [START_REF] Boag | An analysis of relational complexity in air traffic control conflict detection task[END_REF] underlined the link between complexity of conflict detection and the "number of relations" between variables from a pair of aircraft that needed to be processed to perform the diagnosis. They proposed metrics to categorize conflicts according to this relational complexity.

Other geometrical features of trajectories also have an impact on judgment accuracy [START_REF] Remington | Visual Search in Complex Displays: Factors Affecting Conflict Detection by Air Traffic Controllers[END_REF]. An increase in convergence angles generally makes judgments more inaccurate, reaching a maximum effect near 90° [START_REF] Bouju | Analyse de la prévision de la séparation entre deux avions évolutifs convergents[END_REF] [START_REF] Nunes | Interactions between Convergence Angle, Traffic Load, and Altitude Distribution in Air Traffic Control[END_REF]. According to [START_REF] Law | Perceptual and cognitive factors governing performance in comparative arrival-time judgments[END_REF], an interaction between aircraft speed and convergence angle also seems to exist, impacting the perceived complexity and the accuracy of judgment.

Finally, conflict processing and workload have the closest relationship in ATC [START_REF] Lamoureux | The influence of aircraft proximity data on the subjective mental workload of controllers on the air traffic control task[END_REF]) [START_REF] Remington | Visual Search in Complex Displays: Factors Affecting Conflict Detection by Air Traffic Controllers[END_REF] [START_REF] Averty | Mental workload in air traffic control: an index constructed from field tests[END_REF] [START_REF] Loft | Modeling and Predicting Mental Workload in En Route Air Traffic Control: Critical Review and Broader Implications[END_REF]. In particular, conflict classification is radically impacted by contextual workload, since it has been shown that ATCos may sort out a part of the traffic into either conflict or non conflict with the aim of managing their own workloada phenomenon of workload homeostasis by strategy change [START_REF] Sperandio | The regulation of working methods as a function of workload among air traffic controllers[END_REF]. Actually, maximizing the relevance of diagnoses is time/resources consuming [START_REF] Leroux | Cognitive Aspects and Automation[END_REF] and leads to early defusing of the current conflict possibilities in order to regulate workload. This basically means increasing the number of conflict diagnoses. Thus, "diagnosing conflicts" does not uniquely depend on the configuration of the involved aircraft and their intrinsic separation probability.

Integrating doubt management in Conflict Detection

A large part of research on human-centered conflict detection focuses on the performance of the subjects, either through the accuracy of the diagnosis or by the time needed to formulate them. Some authors, however, acknowledge that conflict judgment inherently includes a doubt dimension [START_REF] Enard | Analyse de la prévision de séparation entre deux avions convergents sur l'écran radar[END_REF] [START_REF] Bisseret | Application of signal detection theory to decision making in supervisory control: the effect of the operator's experience[END_REF] [START_REF] Leroux | Cognitive Aspects and Automation[END_REF]. [START_REF] Bisseret | Application of signal detection theory to decision making in supervisory control: the effect of the operator's experience[END_REF] even showed that the precision of the calculations is not of prime importance for the controller. It is indeed far less detrimental for him to accept a certain degree of imprecision if it gives him better guarantees against omissions of conflict diagnosis, than to use calculations in order to reduce uncertainty to a maximum, and be "surprised" from time to time by a diagnostic error. As experience is acquired, computation processes step aside in favor of more holistic but robust processes, capable of preventing the cognitively disruptive effects of certain events.

Consequently, maintaining the doubt in his/her mental representation is very profitable to the ATCo. By deferring the decision to classify a certain traffic configuration into conflict or no conflict for as long as is reasonable, the controller minimizes the costs of an error of appreciation. Furthermore, she can more easily approach the resolution that is necessary and sufficient. This phase of doubt is fundamental in ATC -air traffic control is the "art of doubting" [START_REF] Leroux | Cognitive Aspects and Automation[END_REF]. In other words, it is the management of this doubt, i.e. the decision to prolong it or, on the contrary, to suppress it, which makes up the heart of know-how in ATC. In line with [START_REF] Bisseret | Application of signal detection theory to decision making in supervisory control: the effect of the operator's experience[END_REF] and [START_REF] Leroux | Cognitive Aspects and Automation[END_REF], the acquisition of expertise by controllers leads them to substitute computing and accuracy in conflict detection in favor of doubt, resulting in a more robust diagnosis, which is globally equivalent in accuracy since false responses decrease.

Our purpose was then to draw an accurate picture of the detection capacity of ATCos, in order to model their real conflict judgments. Consequently, we made the following experiment comply with four main features:

-To keep only the number of task components that could be experimentally handled. In practical terms, only realistic uncertain data were kept (from the §b above) and a single fixed geometrical configuration was considered.

-To consider a simple (pair-wise) configuration of aircraft.

-To present traffic scenarios dynamically, using devices (radar screen and maps, flight strips) peculiar to each center and flights coming from real local recordings.

-To integrate doubt expression in responsesdoubt being viewed as self-assessed reliability on each individual judgment e.g. as a part of ATC expertise.

To sum up, our objective may be restated in the taxonomy proposed by Kuchar and Yang (2000):

we want to build a three dimensional Conflict Detection model where state propagation is nominal (aircraft are assumed to follow their "maximum likelihood trajectory") and management of uncertainty is left to the controller. The literature on controller centered issues therefore provides a guideline for modeling in that it indicates which factors are most likely to impact judgments and how they should be modeled.

Experimentation

In keeping with the above, a set of experiments (CREED project: Conflict Risk Evaluation based on Expert Detection) was designed to evaluate the controllers' real detection capacity. It was designed so as to allow them to express their opinions on a wide range of conflicts, in order to identify the values of the variables (or sources of variations) associated with them: when does it "work" and when does it "not work", simply from the controller's point of view? The statistical aspect of the study was taken into consideration when drawing up the experimental plan, allowing the data gathered to be processed appropriately.

Construction of Conflict Scenarios

The first step was the design of scenarios for the tests. We call "scenario" a traffic sequence involving two converging aircraft, dynamically displayed on a radar screen for about one minute and fifteen seconds. Aircraft attitudes and conflict geometry were considered as variables to be controlled for and were consequently set once for all scenarios: one aircraft was stable while the other one was descending (attitudes) and we imposed a 90° crossing (geometry).

In this study we focused on conflict configurations for which the descending aircraft crossed the altitude of the stable one before overflying their IP. Situations that did not comply with this assumption were excluded from our experimental test: even if these cases may perfectly well occur in real operations, ATCos handle them by delivering up to the descending aircraft an initial safety clearance, e.g. a leveling of one thousand feet higher than the altitude of the level aircraft. This clearance is usually imperative until one of the aircraft has overflown the IP. While doing this, controllers show they systematically process them as 'certain' conflicts. By no means would responses from controllers upon these geometrical configurations have represented ATC expertise, and they were not included in our scenarios for this reason.

Once these restrictions on the conflict configurations under examination had been set, three variables (sketched in Figure 1) appeared to be necessary to characterize the scenarios. The first two variables relate to the horizontal and vertical separation, while the third one describes the temporal dimension of the conflict and is considered to be its most significant extrinsic variation.

Figure 1

1. Ed: the horizontal miss distance between the two considered aircraft, irrespective of their altitudes. Accordingly, Ed differs from the horizontal miss distance at the 3-D closest point of approach (CPA), and is generally lower unless aircraft are flying level. Therefore, a valid conflict diagnosis for low values of Ed requires the additional processing of the vertical dimension. We chose five levels for the construction of our traffic scenarios: 0, 3, 6, 9, and 12 nmi.

2. Efl: this variable was set to describe the vertical separation of aircraft. Hypothesizing that this would be closer to the actual mental representation of controllers (built from a radar display), we defined it as the longitudinal distance (in nmi) existing when the altitude difference between the two aircraft regain the separation minimum. Following [START_REF] Bisseret | Application of signal detection theory to decision making in supervisory control: the effect of the operator's experience[END_REF], this variable attempts to reproduce the fact that conflict detection involves visual heuristics more than computing. Regardless of the strategies they actually use [START_REF] Boag | An analysis of relational complexity in air traffic control conflict detection task[END_REF], controllers need to assess and combine vertical and horizontal projections of aircraft, as soon as one of them is climbing or descending. Quantifying what can be understood from visual effects of vertical dimension on conflict, Efl aims to remain close to those elements supposed to be handled mentally by controllers. As a result, it should reduce noise among the responses, therefore giving a better robustness to the mathematical model we aim to infer from them. We also selected five levels for this variable: 0, 5, 10, 15 and 20 nmi.

3. DA: (stands for Degree of Anticipation). This variable aims at characterizing conflict development and was defined as the longer distance to the trajectory intersection. Though both time ('prediction time span') and distance ('visual span') measures could have been selected, the distance choice reflects the authors' own experience that, as main information support (radar) shows plane or spatial information, controllers spontaneously translate times into distances: to the question "when do you think the problem will disappear?", an ATCo will typically respond "when aircraft A arrives here" and show a location on the radar screen. This choice of a distance formulation for the conflict development variable also finds supports in the literature in conflict detection as it relates to the "distance-over-speed bias" phenomenon. Of particular relevance are the experiments on arrival time judgments performed in [START_REF] Law | Perceptual and cognitive factors governing performance in comparative arrival-time judgments[END_REF], where a systematic "over-reliance on relative distance information" was observed. There are six levels for this variable: 6, 10, 15, 21, 28 and 36 nmi. These values were computed at the end of the scenario display.

For each TRACON (Terminal Radar Approach Control) in which we planned to perform the experiment and for each triplet value (DA, Ed, Efl), we built 3 similar basic scenarios, i.e. using a different pair of aircraft each time. This way, we were able to make the callsigns, the aircraft types, the location of the IP, the magnetic orientation of trajectories, the vertical speed and the relative speeds of the involved aircraft vary -all other things being equal. The chosen number of the modalities of the three explanatory variables resulted from a trade-off between the experimental combinatory -keeping it manageable -and the search for accuracy that would benefit the mathematical model. Concrete values were inferred from recorded traffic in past study investigating conflicts from real ATC operations [START_REF] Averty | Mental workload in air traffic control: an index constructed from field tests[END_REF]. Moreover, we had to take account of the fact that relationships between these variables are constrained. Indeed, since DA represents the distance of one of the aircraft to the IP, for low value levels of this variable (say 6 nmi), scenarios with high values of Ed and Efl could not exist.

Consequently, feasible combinations allowed about 75 scenarios to be generated for each of the three pairs of aircraft, in each TRACON [START_REF] Averty | Conflict perception by ATCS admits doubt but not inconsistency[END_REF].

The construction of scenarios specific to each facility was motivated by our desire to reproduce the real expertise of controllers. It was therefore important for us to provide the subjects with conflict situations that could have been extracted from real local traffic and would not be perceived as artificial.

Trajectories of aircraft were actually copied from files of real recorded traffic, so that aircraft did not fly with artificially constant speeds.

Procedure

Every participant in each experimental site was presented with a random set of scenarios built in the following way: for any of the 75 classes of basic scenarios (as characterized by the triplet (Ed, Efl, DA), one of the three basic scenarios was selected. The presentation order was itself random. For each scenario, the subject was asked to give an opinion in terms of the existence of the separation minima (3 nmi or 1000 ft). Overall duration for each participant was less than one hour, as judgments were often formulated before the end of the available 1'15" of each scenario.

During the instructions given before the experiment started, it was stressed that the aim was to express simply "what your eyes would perceive", referring only to the separation minima. The aim, as indicated above, was to minimize the systematic and variable addition of margins linked to setting up a resolution. The effect of the "natural" coupling of the two processes -detection and resolution -is to produce "noise" in the replies, and to produce judgments that dissimulate the detection process model itself. In order to achieve this, it was suggested to the controller, while she was being given the test instructions, that she should not project herself into the role of the "controlling controller", but rather into that of a tester, or a controller in a mirror position. So the controller was invited to be concerned about the existence (or otherwise) of the separation minima, but without being able to act on it, or to resolve it.

Figure 2

Controllers' judgments had to be expressed on an 8-degrees scale on a tactile display (see Figure 2). From the analysis of conflicts in a past study [START_REF] Averty | Mental workload in air traffic control: an index constructed from field tests[END_REF], we postulated that a 8-degrees scale should reflect the highest differentiation an expert could express in a conflict diagnosis. Possible responses were ordered from "non-conflict sure" to "conflict sure" and presented in two groups: the four on the left stood for separation-loss judgments (conflict) whereas the four on the right meant that sufficient separation was the most probable outcome (non-conflict). Thus, each group conveyed four levels of certainty so that subjects could self-assess while selecting each one (the lower the degree of doubt, the darker the key).

The traffic scenarios were submitted to 161 controllers coming from four different TRACONs, each time using the usual local devices and radar maps. The choice of TRACON controllers was only governed by opportunities for experiment deployment at that time. The overall sample was composed of 75.2% male (mean age 44.8) and 24.8% female (mean age 40.6). All of them had to be fully qualified for at least two years, but the mean ages (above) show that most were considerably more experienced (generally more than 10 years).

Statistical Models Introduction

In [START_REF] Averty | Conflict perception by ATCS admits doubt but not inconsistency[END_REF], a descriptive statistical analysis of the collected dataset was presented. Though judgments formulated for given conflict configurations were sometimes found to be very heterogeneous across controllers, the global consistency of responses appeared remarkably high, as increases in the horizontal or vertical separation of aircraft systematically resulted in a safer "median" judgment. Moreover, the graphical analysis of the data also showed that controllers managed uncertainty by expressing doubtful responses and thus confirmed the importance of doubt in the conflict detection process. The data therefore supported [START_REF] Leroux | Cognitive Aspects and Automation[END_REF] in its statement that air traffic control is the "art of doubting". These results suggested that the sources of variations identified at this stage of the study (Ed, Efl and DA) could be used further to develop a predictive model of conflict detection and that the collected data could actually be used to calibrate it.

The following section presents the derivation of the statistical model and discusses the estimated parameters.

The Ordered Logit Model

The air traffic controllers judged the risk of collision on an ordered scale of eight levels, going from "airprox certain" (separation between aircraft will be lost), through "caution", to "no problem". The

Ordered Logit Model provides a common and convenient framework for analyzing such data in which the dependent variable is both discrete and ordered [START_REF] Greene | Econometric Analysis[END_REF]. It is based on a natural way of representing the decision-making process, consisting of defining a continuous "latent variable", U, whose level determines the subject's final reply. If the value of U is less than a certain threshold, noted α 1 , the reply will be "airprox certain"; if the value of U is higher than α 1 , but less than another threshold α 2 , the reply will be the next one up on the scale of possible replies, and so forth.

As the latent variable U is not observable, it must be reconstructed from the observable variables Ed, Efl and DA. In the specific context of the CREED experiment, these variables are supposed to give the best explanation of the controller's reply. However, due to its particular nature, the variable DA will be treated differently from the others and we will build a model for each value of DA. An "integrated" model will be obtained later through the interpolation of these models. Other sources of variations may affect the controller's judgment, but though they cannot be or were not observed in the experiment, they must nevertheless be incorporated into U, which must be broken down into an observed component and a non-observed component:

U=β' x + ε.
Usually, the non-observed component ε is considered as a noise, thus as a random variable, whose law determines the probability of the replies; here we used a logistical law 2 . The observed component is generally modeled by a linear combination of the explanatory variables; for a fixed value of DA, it will therefore be formalized by the linear relation:

'x =  1 Ed +  2 Efl +  3 EdEfl
where the unknown coefficients β 1 , β 2 , and β 3 , are called regressors; note the presence of the term Ed

x Efl which captures the crossed influences between the two variables Ed and Efl.

Ordered Logistic models for each DA

For each given DA, the model is determined by ten coefficients that need to be estimated. The method used for the estimation is based on the maximization of the log-likelihood, which depends on the data observed and the coefficients; an optimization algorithm is then used. The estimated parameters are shown in Table 1. 2 The distribution function of a logistical law is

)) exp( 1 /( ) exp( ) ( ob Pr ) ( t t t t F     
. Therefore, the probability that the reply is the discrete value according to the interval ] α The Ordered Logit Model belongs to the class of Generalized Linear Models: a linear combination of explanatory variables (the latent variable U in our setting) is nonlinearly linked to the dependent variable. Interpretation of the parameters of the model is therefore analogous to the interpretation in linear models, provided the link between the "latent variable" and the dependent variable is well understood. In our model, an increase of U implies that more risk is perceived by the controller.

i, α i+1 ] is . ) ' exp( 1 ) ' exp( ) ' exp( 1 ) ' exp( ) ( ob Pr 1 1 1 x x x x U i i i i i i                        DA=6 DA=10 DA=15 DA=21 DA=28 DA=36
First, one may observe that β 1 and β 2 are always positive and significant. This supports a very natural intuition: the direct effect of an increase in the separation minima translates into a decrease in the perceived risk. However, one needs to consider the impact of the cross-product parameter β 3 : for values of DA greater or equal to 15, β 3 is not significant and its point estimate is very low. It is thus unsurprising that we actually observe a positive direct effect of Ed and Efl on the latent variable for reasonable conflict geometries. Moreover, the fact that the cross influence of Ed and Efl for these conflict geometries is low supports the idea that, when the time pressure is low, controllers have a rough estimate of the conflict geometry: any increase in vertical or horizontal separation directly translates into a decrease in the perceived risk.

When DA equals 10, β 3 is negative and significant but remains small enough for the direct effect of Ed and Efl on the latent variable to stay positive: the perceived risk still decreases when the conflict geometry becomes less dangerous. However, the negative β 3 indicates that actual separation somehow begins to matter. For example, the perceived risk decreases less for a given increase in Ed (resp. Efl) when Efl (resp. Ed) is higher. That is, when the prediction time span is short and separation of aircraft is ensured vertically (resp. horizontally), an increase in horizontal (resp. vertical) separation does not reduce the perceived as much as it would have in the case of non-separated aircraft. This, again, is a very intuitive result.

Finally, when DA equals 6, β 3 is negative and significant but becomes large enough to induce a negative direct effect of Ed and Efl on the perceived risk. This happens for Ed greater than 6.44 or Efl greater than 18, that is once separation, given the very short prediction time span, is obvious: indeed, we observe that for these values of (Ed, Efl), the median response regarding the perceived risk is the safest.

Figure 3

Another interesting fact about estimated parameters is that the relation β 1 /β 2 varies linearly as a function of DA as shown in Figure 3. This relation provides information on the variable that is the "most used" during the "conflict/no conflict" diagnosis: in an extreme case, if it was equal to 0 (respectively infinity), the controller would only base his judgment on Efl (respectively Ed). As these two variables are expressed in the same unit and describe horizontal distances, it can be estimated that when the relation β 1 /β 2 equals 1, Ed and Efl are evenly discriminating in the controller's judgments. This fact tends to prove that, in our setting, ATCos privilege Efl for DA less than 12nmi whereas Ed becomes dominant for DA over 12nmi. This finding is consistent with previous results on conflict detection: according to [START_REF] Loft | Modeling and Predicting Mental Workload in En Route Air Traffic Control: Critical Review and Broader Implications[END_REF] and the studies quoted therein, ATCos indeed "appear to prefer using altitude to heading and speed information when determining the likelihood of aircraft conflict" and seem to use "lateral separation only in circumstances where vertical separation is questionable". The scenarios proposed in this study display conflict situations in which one aircraft is descending and crossing the other's altitude. Since separation is first granted vertically (as explained in the experiment design section, the other types of conflict are avoided as much as possible in real life operations), it is natural to recover the dominance of the vertical dimension for small DA, that is when aircraft have similar altitudes and the rate of descent may actually be used [START_REF] Bouju | Analyse de la prévision de la séparation entre deux avions évolutifs convergents[END_REF]. For high values of DA, the vertical separation is instead questionable since vertical positions of the descending aircraft are inaccurately projected [START_REF] Michard | Analyse de la représentation des trajectoires d'évolution chez les Premiers Contrôleurs[END_REF]. ATCos have therefore to rely primarily on planar separation for these large DA.

Figure 4

Using these coefficients, we can then calculate for each value of Ed and Efl the probability of observing a given reply and compare these predictions with the observations. Such a comparison is provided in Figure 4, where probabilities for each response are presented for the pair Ed = 0 and Efl = 0. Answers are ordered by perceived risk and with black (resp. dark gray) standing for high (resp. low) perceived risk. The agreement between the model and the data is very good for each value of DA.

Integrated model

So far we have constructed logit models for each of the values of explicative variable DA. In order to be able to interpolate, it becomes necessary to integrate this variable into a more general model, which we will call "integrated model". We opted for the approach depicted in Figure 5: first, the variable DA being given, the regressors and thresholds have to be estimated. This will in turn allow the observed part of U to be computed for fixed values of Ed and Efl. The expression of the noise distribution function will then be used to compute the probabilities for each reply.

Figure 5

We therefore need to evaluate the seven thresholds and the three regressors, for DA values that are different from those already considered. An appropriate technique to handle this problem is to use non linear regression: after having established as many ordered logistical models as values of DA (DA=6, 10, 15, 21, 28, 36), we have a sample of six values for each parameter. Non-linear regression would then allow each of the parameters to be expressed as a function of variable DA. These functions have to be chosen a priori in a certain family: the better the family choice, the closer the fit of the parameters. So, the first step needed to build the integrated model consists in determining the form of the 10 parameters as a function of DA. To this end, we used the samples for each parameter we obtained by computing the six ordered logit models, one for each DA. We selected, a priori, a common model for the parameters:

    DA C A B A C B A DA with DA DA B A DA C B A DA DA C B A DA DA C B A DA DA i i i i              ) exp( exp ) ( ) , , , ( ) ( ) ( ), , , , ( ) ( ), , , , ( ) ( ), , , , ( ) ( 2
1 1 1 3 3 3 3 2 2 2 2                    
This choice for the family of non-linear functions was made because they provide a parsimonious way to model monotonous responses that have a finite value in DA=0 and an horizontal asymptote at DA, that is properties that are satisfied by the seven thresholds and two of the three regressors (β 2 , β 3 ). As the last regressor (β 1 ) could be easily parameterized using the linear relationship described in the previous section, this specification of the model was expected to perform well on our data.

Non-linear regressions gave a first numerical estimation for each of the 29 parameters of the model and a graphical inspection of the results confirmed the relevance of these choices. It also gave some further information on the form of the model: in particular, the coefficients  i C were close enough to be constrained to be equal, as could the coefficients  i C . These restrictions imply that thresholds on the one side and β 2 and β 3 on the other side converge at the same speed to their respective asymptotes. Lastly, the coefficient  3 A was nearly equal to zero and we decided to assume it was. This imposes that β 3 is asymptotically null for large values of DA. Given that β 3 was found to be statistically significant for DA greater or equal 15 nmi, this assumption is actually very natural. Under these assumptions, the integrated model depends on 21 parameters. However, though it gives a good insight into the relevance of the family functions, performing independent regressions is best considered as a first step in the modeling process. Indeed, the initial dataset is only used through the estimated parameters. Then if a single parameter is estimated using information has been lost in process. More importantly, the impacts on the latent variable of the departure from point estimations (for the available DA values) are not likely to compensate for one parameter to another and may lead to inconsistent estimate. A way to circumvent these problems could be to perform a global weighted regression of the parameters (using the computed covariance of the parameters as weights), but it might be preferable for simplicity to maximize a global log-likelihood constructed on the whole data sample. Note that the latter method presents the great advantage to work with non-concentrated values of DA (and thus would extend to other variables standing for the prediction time span, one being suggested [Stankovic and al., 2006]).

Surely, even if they are estimated on a large dataset, 21 parameters remains a large number.

However, it should be acknowledged that a large part of these parameters relate to the thresholds, the number of which was "imposed" by the number of response categories that were offered to the controllers during the experiment. The latent variable, which formally describes how the perception of the geometry evolves with the prediction time span, needs only 6 parameters to be described. 3 more parameters would be needed to calibrate the model if we were only interested in the binary choice "conflict/no-conflict". The supplementary parameters describe the data with more richness as they allow the whole set of judgments to be recovered and therefore adequately reproduce doubt.

In this paper, the final model was obtained by expressing the integrated log-likelihood and numerically maximizing it. To facilitate convergence, we used the parameters obtained by non-linear regression as starting values for the optimization algorithm. The resulting curves are displayed in Figure 6.

Figure 6

Finally, it is of interest to investigate the loss of accuracy of the integrated model for the 6 values of DA for which we know the optimal parameters. This can be assessed by testing for each DA the null hypothesis that the local parameters (the parameters obtained by maximizing the log-likelihood for a given DA) are equal to the integrated parameters (the parameters obtained though the integrated model). We therefore ran a series of 6 likelihood ratio tests (see e.g. [START_REF] Greene | Econometric Analysis[END_REF] These p-values3 indicate that the null hypothesis may never be rejected at any usual significance level. This means that the loss of accuracy induced by the interpolation of the parameters is very low.

Hence, there is nothing in the data that would cause rejection of the integrated model. This robustness supports the idea that the model could be used as a building block to design ATC support tools.

Conclusion

In this article, we have presented the results of an experiment conducted on a large number of experienced controllers that would make it possible to derive a "controller-like" model of conflict detection.

With regard to the experimental plan, a particular effort was put into the design of traffic scenarios and the definition of the explanatory variables. As these were supposed to reproduce the perceptual heuristics used by controllers in their actual detection process and therefore often rely on a planar representation of the conflict geometry, they differ from the ones that would typically be used in engineering approaches, such as those reviewed in Kuchar and Yang (2000). However, they are, as explained, relatively well supported by the cognitive literature on conflict detection. As for the statistical model to be constructed, a key requirement was that it should properly account for doubt. Doubt, indeed, is central in the work of ATCos and a better understanding of traffic configurations where it occurs could therefore be of some interest in the design of operational tools. In this aspect, the European project ERASMUS provides a concrete example of potential application.

A graphical analysis of the data, presented in [START_REF] Averty | Conflict perception by ATCS admits doubt but not inconsistency[END_REF], showed that judgments exhibited a high degree of variability but were "globally" consistent, in the sense that any increase in the horizontal or vertical separation of aircraft systematically resulted in a safer "median" judgment. As variability was mainly observed for conflict situations for which judgments were not definite, the author concluded that the data adequately reproduced doubt and could be used to build a controller-centered model of conflict detection. The derivation of such a model is presented in some detail in the present article. In the first part of the statistical analysis presented here, we estimated Ordered Logit Models for given values of DA, our variable describing the temporal dimension of the conflict situation. The use of this type of model is very natural given the discrete and ordered nature of the expressed judgments, but also presents the great advantage of inherently accounting for doubt. Comparison of the model parameters across DA indicated that the relative importance of the horizontal and vertical separations evolved with conflict development, with the horizontal separation dominating away from the conflict location, and the vertical dominating close to it. In the second part of the statistical analysis of the data, an "integrated" Ordered Logit Model was derived using maximum likelihood estimation and a proper family of functions. The integrated model was then statistically validated on the "fixed DA models" and we proved that no significant loss of accuracy had occurred in the derivation process.

As of now, the model presented in this article may be used to predict controllers' judgments, including doubt, for the particular class of conflict geometries considered in the experiment. It is a very supportive result in our research effort to provide a general model of controllers' judgments, but much work remains to be done if one wants to generalize the model to other conflict geometries. Some factors (convergence angle, contextual workload, for example) that impact the conflict/non conflict diagnosis have been kept constant in the experiment and the robustness of our model should be tested against these sources of variations. We can expect, for example, our model to be "conservative" for non-perpendicular crossings, as it is often shown that controllers' judgment is the least precise when the convergence angle is 90° (e.g. in [START_REF] Law | Perceptual and cognitive factors governing performance in comparative arrival-time judgments[END_REF]). However, if drastic changes rather than small variations were to be imposed on the conflict geometry, it is possible that other explanatory variables would need to be considered to describe the conflict. Indeed, the ones defined in this study remain close to the perception of the controller for the range of approach conflict geometries considered and it is unclear whether they generalize well or not. In this direction, the recent findings of Nunes and Kirlik (2006) suggest that good agreement between controllers' judgments and "objective" conflict probabilities may exist. The judgments collected for this study could therefore be used to calibrate more general models of conflict detection, such as the one introduced in Cruck and Lygeros ( 2007). Note that these potential extensions require new data to be gathered and a new experiment, which we are currently designing.

Finally, from a human-factor perspective, it would also be of great interest to evaluate the heterogeneity of controllers. Variability of judgments was broadly discussed in [START_REF] Averty | Conflict perception by ATCS admits doubt but not inconsistency[END_REF] and is partly accounted for in the Ordered Logit Model presented in this paper, but could be further investigated. This is the purpose of ongoing research in the CREED project. The tactical display used to collect the responses. Two groups of four keys were available for the subjects on the interface, ranging from "conflict sure" on the left to "non conflict sure" on the right. For each scenario, ATCos had to select the key that reflected at best their judgment.

Biographies

Figure1:

  Figure1: Illustration of the three explanatory variables as they were used in the traffic scenarios. Two aircraft (here: AFR123, passing through 14700ft and FBAAC flying level at 6000ft) were dynamically shown on radar during 1 minute and 15 seconds. Before the end of this period, i.e. when the value of DA was computed, the subjects had to express their judgments about the conflict risk. These judgments also related to the values of Ed and Efl. The positions of the aircraft, where Ed and Efl are computed, are only displayed here for clarity purpose.

Figure 3 :Figure 4 :Figure 5 :

 345 Figure 3: Variation of the ratio β 1 /β 2 versus DA (nmi): estimated ratios and fitted linear relationship.

Figure 6 :

 6 Figure 6: Integrated model: variation of the estimated thresholds and regressors versus DA

Table 1 : Estimation of the ordered logistic model parameters: (Significance codes: 0 '' 0.001 '' 0.01 '' 0,05 '' 0,1 ' ' 1)

 1

	α 1 α 2 α 3 α 4 α 5 α 6 α 7 β 1 β 2 β 3	1,506 2,399 2,840 3,181 3,733 4,050 4,747 0,232  0,660  -0,036 	0,862 1,898 2,316 2,653 3,185 3,603 4,299 0,405  0,400  -0,026 	-0,040 1,124 1,668 2,155 2,751 3,255 4,143 0,315  0,236  -0,006	-0,704 0,525 1,078 1,564 2,215 2,826 3,595 0,281  0,158  -0,003	-1,376 -0,084 0,589 1,239 1,850 2,346 3,137 0,188  0,097  0,001	-1,793 -0,237 0,413 1,157 1,804 2,376 3,178 0,231  0,077  -0,002

Table 2 : Comparison between the model LVG with the model LV by way of the log-likelihood test.

 2 ). The results are presented in Table2, where LVG (resp. LV) stand for the integrated (resp. local) log-likelihood.

	DA	6	10	15	21	28	36
	LVG	-828.08	-1308.74	-2374.87	-3369.98	-3906.24	-4002.14
	LV	-823.71	-1305.09	-2370.92	-3364.29	-3901.13	-4001.57
	p-value	0.56	0.7	0.64	0.33	0.42	1

  Philippe Averty is Confirmed Expert (PhD in Cognitive Psychology) with the DSNA/DTI/R&D. He first worked as an Air Traffic Controller and Instructor at Lyon TRACON and Paris ACC. He is now involved in different projects including workload assessment and decision modeling and collaborates to the European project ERASMUS. Kévin Guittet is researcher in the DSNA/DTI/R&D. He holds a PhD in Applied Mathematics and a Master Degree in Economics. His research interests include air transport economics and statistical modeling applied to airspace complexity.Pascal Lezaud received his Diploma of Electronics Engineer from l'Ecole Nationale de l'Aviation Civile, Toulouse France, in 1982. He joined the DSNA/DTI/R&D in 1992, in which he was involved in dependability studies for ATM systems. He obtained his PhD in Probability in 1998. Now, his main interests include collision risk models, probability, Markov processes and simulation of rare events. He collaborated to the European Research project "Hybridge" and participates to the new project "iFLY".

Note that, following this idea, conflict detection measures built around a preliminary version of this work have been included in the set complexity indicators used in[START_REF] Gianazza | Evaluation of air traffic complexity metrics using neural networks and sector status[END_REF]

2006b) to model the link between workload and dynamic sectorization in the French airspace.

The null hypothesis is not rejected as soon as the p-value is greater than the significance level α, e.g. α=0.05.

Acknowledgements:

We are deeply indebted to the editor and the anonymous referees for their very helpful comments and suggestions. We are also grateful to Esa Rantanen for having contributed to a greatly improved presentation of this paper. All the statistical computing and graphics have been obtained with the free software R (R Development Core Team, 2006).


Raphael Deau

Jean-Baptiste Gotteland
email: gotteland@tls.cena.fr

Nicolas Durand

Runways sequences and ground traffic optimisation

At the airport level, the new systems involved in the A-SMGCS (Advanced Surface Movement Guidance and Control System) give the possibility to take advantage of some innovative decision support tools bound to the optimisation of the ground traffic management.

In this article, two different tasks assumed by airport controllers are analysed and modeled: the runway sequencing process and the application of runways sequences at the ground level. An existing ground traffic simulator is adapted to measure the potential improvements that could be expected by the use of some optimisation methods applied on these two modeled problems.

I. INTRODUCTION

Airport congestion is still a key point to be studied for the next years: the evolutions that are expected concerning the future management of the ground traffic situations (A-SMGCS: Advanced Surface Movement Guidance and Control System) at the airport control level have obviously several environmental and economical issues.

On major airports, these evolutions can be technically provided by taking advantage of some new developed systems such as the surface radars, the D-GPS (Differential Global Positioning System) associated with the ADS-B (Automatic Dependant Surveillance mode B) and numerous other coordination tools like AMAN (Arrival MANager) and DMAN (Departure MANager).

In this context, this article focuses on the possible optimisation of two major aspects of the airport controllers tasks: the aircraft sequencing at the runway level and the conflict resolution between taxiing aircraft. An airport simulation tool (ATOS: Airport Traffic Optimisation Simulator) is adapted and used to measure the delay reduction that could be expected.

II. RELATED WORK

A. Projects

Two main approaches called AMAN (Arrival MANager) and DMAN (Departure MANager) deal with the aircraft sequencing problem:

• AMAN are decision support tools that provide the controllers with information on arrival flows, including calculated arrival runways sequences. These informations are regularly updated with the actual positions of aircraft in the approach sectors.

• DMAN are planning tools developed to improve the departure flows at airports by optimizing the departure runways throughput. Some projects as PHARE (Program for Harmonised ATM Research in Eurocontrol) [1] have defined some DMAN and/or AMAN systems but do not coordinate both of them at the airport ground traffic level. PHARE was a project instaured by Eurocontrol. It was a collaborative research program that investigates an air traffic management concept.

Gate to Gate [2] is a European project which takes into account aircraft from their departure gates to their arrival gates. It mostly improves an AMAN project by managing the air traffic problem. A DMAN is used for the mixed runways and shares out the main informations about the departures. The AMAN has to set the arrivals with the information provided by the DMAN.

The NLR develops a concept which schedules the aircraft on the airport by using constraint relaxation [START_REF] Van Leeuwen | Houwert Scheduling aircraft using constraint relaxation NLR: Nationaal Lucht & Ruimtevaartlaboratorium[END_REF]. A lot of parameters are considered, as the runway separations, SID routes, exit points, . . . DMAN and AMAN are not explicitly described but implicitly defined.

OPS [START_REF] De Jonge | R Seljée Outbound Punctuality Sequencing by Collaborative Planning NLR: Nationaal Lucht-en Ruimtevaartlaboratorium[END_REF] defines a new DMAN to schedule departures. This project is based on more human interactions (from pilots and controllers for example) but is also more flexible (the users can setup a lot of values). They look forward to define a real-time decision support tool.

Total Airport Management (TAM) [START_REF] Günther | Niederstrasser Total Airport Management (Operational Concept and Logical Architecture)[END_REF] tries to merge together as many concepts as possible defined by Eurocontrol, concerning AMAN, DMAN in the ATC in order to optimise the airport capacity and improve the predictability of airports traffic.

CADM (Coordinated Arrival Departure Management) [START_REF] Bohme | Coordinated Arrival Departure Management[END_REF] is a concept that mixes a DMAN and an AMAN but does not consider precisely the taxiing times. It uses fuzzy inference mechanism to determine rules to use to set the aircraft sequence.

All these projects focus on the definition and/or the prediction of airports runways sequences for arrivals and/or departures, trying to share as efficiently as possible all the available informations given by the approach sectors and the airport systems. However, the taxiing phases of the flights are still the ones that are the most difficult to predict with a good accuracy: the tested DMAN systems are still not so satisfying

B. Background

Previous publications [START_REF] Gotteland | Optimisation du trafic au roulage sur des grands aéroports[END_REF], [START_REF] Gotteland | Genetic Algorithms Applied to Airport Ground Traffic Optimization Proceedings of the Congress on Evolutionnary Computation[END_REF], [START_REF] Gotteland | Handling CFMU slots in busy airports Proceedings of the Air Traffic Management R&D Seminar[END_REF], [START_REF] Pesic | Aircraft Ground Traffic Optimization using a Genetic algorithm[END_REF] studied the ground traffic optimisation on Roissy Charles De Gaulle and Orly airports. The ATOS (Airport Traffic Optimisation Simulator) simulator was developed and used to compare the efficiencies of several optimisation methods applied to different traffic situations.

The simulator uses a detailed description of the airport taxiways, gates, push-backs, runways and the existing constraints (one-way taxiways for example) to calculate a set of possible paths for each aircraft (see figure 1). The whole traffic is simulated using the real airport flight plans demand of a day of traffic. The flight plans contain information such as the aircraft type, the gate position, the landing or take-off time, the runway used . . . Using these informations, and for each traffic situation, the possible paths for each aircraft are calculated on a defined time window T w , taking into account uncertainties on taxiing speeds and a trajectory prediction done: in such a prediction, the future aircraft position is not a point but a set of possible points (a line segment) on the taxiways used (see figure 2).

The problem to solve consists in assigning a path to each aircraft, with holding points if necessary, in order to solve every conflict with other aircraft within the time window T w . Two aircraft are in conflict each time the separation standards defined by the operating rules of the airport are violated.

These rules are modelled as follows: • parked aircraft are supposed to be conflict free;

• a minimum separation distance is required between each taxiing aircraft pair;

• time separations are required between aircraft on runways, depending on the aircraft types and their wake turbulence categories. Among all the possible solutions, the best conflict free trajectory is search according to a global criterion taking into account the delay due to holding points and longer paths chosen.

The problem is very combinatorial because of the number of possible paths and holding points for each aircraft. When the number of aircraft involved increases, the problem can become very difficult to solve using exact methods. Different optimisation methods have been studied by the DSNA/DTI R&D POM team to solve it:

• A sequential deterministic approach consists in first ordering aircraft, give the shortest path to the aircraft with the highest priority, and optimise the n + 1 th trajectory solving conflicts with the n previous already optimised trajectories. Optimising the trajectory of one aircraft, solving conflicts with n other known trajectories is quite simple and can be done with an A * or branch & bound method [START_REF] Horst | Global Optimization: Deterministic Approaches[END_REF], [START_REF] Ahuja | Network Flows, Theory, Algorithms and Applications[END_REF].

• A global approach using stochastic optimisation based on genetic algorithms [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF], [START_REF] Durand | Automatic aircraft conflict resolution using genetic algorithms Proceedings of the Symposium on Applied Computing[END_REF] can be used to find the best paths combination. To increase the efficiency of the algorithm, the partial separability of the problem can be used to define crossover and mutation operators able to optimally recombine current solutions during the convergence process [START_REF] Durand | Genetic crossover operator for partially separable functions[END_REF]. When a traffic situation is solved at time t, the paths obtained are applied to the moving aircraft during a time ∆ (∆ < T w ) called time shift window, to create the updated situation at time t + ∆ (figure 3). A whole day of traffic can thus be simulated using this shifting window modeling, taking into account the uncertainties on aircraft taxiing speeds.

C. Obtained Results

The first simulations results obtained with this modeling have shown some characteristics on the traffic and can help quantifying some parameters of the problem:

• When "realistic" uncertainties on taxiing speeds (from 20% to 50%) are used, the time window must be reduced to 10 minutes to be able to solve the problem. This emphasis the difficulties encountered on the DMAN concept because with a 10 minutes advance notice, the final takeoff time for an aircraft on the runway is to lately known.

• The method using a genetic algorithm consider globally each traffic situation (without classifying aircraft with priority orders) reduces the delays from 1 to 2 minutes per aircraft during peak hours at Roissy Charles De Gaulle Airport, which shows that the possible time saved by optimising the taxiing phase of a flight is quite significant on such airports.

• During peak periods, knowing precisely the paths followed by each aircraft is necessary to manage correctly the CFMU 1 slots: an optimised simulation can help knowing the delay due to congestion and allows to anticipate departures from gates if necessary.

D. Conclusions

These last results show that on large airports such as Roissy Charles De Gaulle, the performance of systems such as AMAN and DMAN depends on an optimised taxiing management. On the one hand, the calculation of runway sequences must take into account the taxiway paths and holding points given to aircraft. On the other hand, it might be better to take into account the full runway sequence to optimise the gate time departures and the aircraft holding points and paths.

As it was shown that the acceptable time window adapted to realistic uncertainties is less than 10 minutes, it is proposed in this article to split the resolution process of each traffic situation in two steps:

• First, the best runways sequences compatible with the current aircraft positions and the known arrival flows should be computed, with a large anticipation time (about 30 minutes if possible). This point is described in part III.

• Then (part IV), the aircraft paths and holding points should be optimised in order to fit as close as possible to these targeted runways sequences, with an adapted anticipation time (less than 10 minutes)

III. RUNWAYS SEQUENCES OPTIMISATION

A. Goals

This part, focuses on finding some optimal runway sequences, respecting a given traffic situation and considering the arrival flows.

A system merging the AMAN and the DMAN informations at the airport level is defined: on runways shared by arrivals and departures, this is the only way to optimise correctly the sequence, and as far as arrivals and departures have to share the same airport infrastructure, they have to be managed together at the ground level.

1 Central Flow Management Unit

B. Problem modeling

To meet these goals, the problem is defined as follows:

• The variables of the problem are the slots that must be assigned to each aircraft;

• The main constraints are the landing times, the minimal remaining taxiing time of each departure, the runway separation rules and the CFMU2 slots allocated to some departing aircraft;

• The criterion to minimise measures the departures delays and the deviations from the CFMU slots;

• The prediction time should be close to 30 minutes. 1) Constraints: At the airport level, the arrival sequence cannot be substantially modified: the ordering of arrivals is fixed by approach sectors and it is reasonable to consider that each arriving aircraft cannot be delayed more than a reduced time λ (λ < 1 minute) if these kind of decisions can be taken in advance enough.

Concerning the departures sequences, the minimum possible taxiing time to the runway becomes a constraint for aircraft leaving parking positions: to obtain a feasible sequence, each aircraft's shortest time to runway is considered as a constraint in the sequence search.

The most important constraints used in the sequence optimisation is the separation due to the wake turbulence. The minimum time between two aircraft depends on their weight category. For example: a "low weighted" aircraft cannot take off less than 180 seconds after a "heavy weighted" aircraft has taken off. Three categories of aircraft (and associated wake turbulence) are defined: "low", "medium" and "heavy".

L = Low, M = Medium, H = Heavy A = Arrival, D = Departure
Other constraints concern aircraft which are assigned some CFMU slots: these aircraft have to be inserted in the sequence between arrivals and classical departures, respecting their fixed CFMU slots. According to the CFMU official acceptance, a CFMU slot is respected if the aircraft takes off from 5 minutes before to 10 minutes after the schedule. However, the actual off-gate times does not always allow to respect all the CFMU slots (as for example when a departure leaves the gate later than its assigned slot). In consequence, the only constraint that is defined as such is the interdiction to take off more than 5 minutes before the slot and the other CFMU requirements will be integrated in the criterion. 2) Criterion: In the estimated sequence, the penalties relative to the deviation from each CFMU slot (see fig. 4) and the delay regarding the minimal runway access time for each other departures are computed. The aim of the optimisation is to minimise the sum of those values: the more the CFMU slots are respected and the shorter is the time spent by aircraft on taxiways, the better the sequence is evaluated.

On the other hand, arrivals sequencing delays are not taken into account in the criterion as these little delays (less then λ seconds for each arrival) are not penalising. Of course, sequences which would cause one landing to be delayed more than λ seconds are considered not valid regarding the constraints that are defined and cannot be accepted.

3) Prediction time: The sequence optimisation takes into account all the aircraft that may appear in the sequence during the next T s minutes. The choice of this prediction time is influenced by several factors: as the sequence optimisation problem is very combinatorial (for n aircraft, the complexity of this scheduling problem is proportional to n!), the prediction time should be short enough to keep the problem size small enough. On the other hand, it seems logical that the larger the prediction is, the better the sequence will be optimised on the whole day.

C. Resolution

The sequence optimisation problem is a classical scheduling problem that can be solved with deterministic Constraint Satisfaction Problem algorithms.

1) Problem modeling: The problem is to find the best sequencing for a given list of aircraft considering the almost fixed arrivals and the separation time between two aircraft. To find the best solution, each permutation of the aircraft list has to be explored.

2) Branch & bound algorithm:

To solve this problem, a classical branch & bound algorithm is used: each branch of the sequences tree (see fig. 5) is potentially explored and at each node of the tree, the delay generated by the already assigned slots is calculated. Once a solution has been found (i.e.: when one of the leafs of the tree is joined), the cumulated delay obtained updates the "best current solution found" for the next steps: when a node generates a higher delay than this "best current solution found", the branch is cut.

This algorithm can be summarised as follows:

Mainloop: For each non yet inserted aircraft 'a':

• Insert 'a' in the current (partial) sequence

• Calculate the new resulting penalty • If this penalty is acceptable then:

-If some aircraft still remain to insert, explore the next node of this branch (call back the Mainloop) -Otherwise, mark the current sequence as the best solution found

• remove 'a' from the sequence To obtain the best cuts in the tree exploration, the initial order plays a major role. It was observed that defining the initial order in accordance to the "ideal" time on the runway (i.e: the minimal runway access time for non-CFMU departures and the CFMU slots for the others) was a good strategy.

Moreover, some other cuts must be implemented to minimise the number of explorated nodes. These cuts are relative to some specific characteristics of the problem:

• There is obviously no need to explore a branch in which some arrivals are not in the right order.

• There is no need to explore a branch which swaps two equivalent aircraft in the sequence. The equivalence between aircraft is defined according to their wake turbulence category, their type (arrival or departure) and their CFMU profile(with or without a CFMU slot).

D. Results

In order to measure the efficiency of the proposed runway sequence optimisation method, ground traffic simulations were carried out with a traffic sample relative to a heavy day at Roissy Charles De Gaulle, when the fourth runway was not yet in operation (this period presents the advantage to provide a mixed runway 09-27 shared by both departures and arrivals).

At each simulation step (every ∆ = 2 minutes), an optimal sequence is computed for each runway, with different anticipation times (from 20 minutes to 50 minutes), and the resulting theoretical delay for departures in these optimal sequences are recorded (this theoretical delay is measured by the difference between the proposed slots in the sequence and the "ideal" slots for aircraft.)

The figures 6 and 7 give the mean delay per aircraft as a function of the number of aircraft involved in the runway sequence, for the two runways used for departures: runway 27 (shared with arrivals) and runway 26R (only used for departures.)

On these figures, the influence of the prediction time window on the quality of the runway sequence can be observed and confirms the expected conclusion: the highest the prediction time is, the best the runways sequences are. Moreover, this relation can be quantified: when the prediction time grows from 20 minutes to 50 minutes, the mean departures delay decreases from 140 seconds to less than 100 seconds in heavy traffic situations.

Of course these delays measures are theoretical and could only be realised if the calculated runway sequences were exactly applied. This is the subject of the next part, in which the retained prediction time window that is considered for the runway sequences is 30 minutes, as it seems to be the best compromise between what can be expected from AMAN and DMAN systems and what can be treated by the optimisation process.

IV. APPLICATION TO THE GROUND TRAFFIC SITUATIONS

A. Goals

In this part, the runway sequences previously optimised are considered as a target for the ground traffic solver: the objective is to fit as close as possible to the predefined sequences while solving aircraft conflicts on taxiways and gates.

Many options can be studied in this framework: it can be interesting, for example, to favor the earliest departures of each runway sequence and to delay in priority aircraft which might arrive on the runway in advance according to their allocated slot. It can also be interesting to strategically sequence departures before they leave their gate position, by assigning them an initial delay.

These different concepts will be studied and compared to the results obtained without the runway sequence optimisation in the last part of this article.

Therefore, the different optimisation methods must be adapted to take into account the new objective (i.e. fit to the optimised runways sequences) and not only minimise the aircraft delay: this part details the modification that were done for each resolution method.

B. Sequential resolution method

The sequential resolution method deals with a simplified problem, in which aircraft are initially sorted and then considered one after an other (first considered aircraft have priority on last considered ones). As a consequence, this resolution method can be easily adapted to fit some given runways sequences, as these sequences will directly provide the aircraft classification to be considered: each aircraft a can be associated with its slot t a in the concerned runway sequence, and the sequential method will be applied in the order given by (t a ).

In most of the cases, this process ensures that on each runway, departures always take off in the order defined by the runway sequence (except in some very particular cases relative to the limited aspect of the prediction time window.) However, on runways shared both by departures and arrivals, the order between arrivals and departures is not ensured: if a departure planned just before an arrival reaches the runway area too late, it will be forced to take off after the arrival (in this case, the resolution method has to modify the aircraft classification to find a conflict free solution).

Another point has to be considered, concerning the departures constrained by CFMU slots: generally, the CFMU slots correspond to some delayed take-off times. When such aircraft are involved in a runway sequence, the classification of departures is not the only factor to assume: the exact takeoff time of concerned aircraft must also precisely correspond to their given CFMU slots, in agreement with the official CFMU acceptance (no more than five minutes before the slot, nor ten minutes after). During low traffic periods, these departures could take off much earlier while respecting the runway sequence order. For these reasons, a minimal departure time (from the gate) has to be assigned to aircraft [START_REF] Gotteland | Handling CFMU slots in busy airports Proceedings of the Air Traffic Management R&D Seminar[END_REF] and the resulting delay must be propagated over the following departures, in order to keep a consistent sequencing of departures.

Therefore, an initial wait w d is calculated for each departure d, as a function of:

• its minimal runway access time t mind ,

• its optional CFMU slot t cd ,

• the official acceptance for CFMU slots (δ c = 5 minutes),

• and the initial required wait w p of the prior aircraft p in the sequence (all aircraft are sorted in the order given by the sequence). For the first aircraft d 0 :

• If d 0 has a CFMU slot t cd 0 :

w d0 = max{0, t cd 0 -δ c -t mind 0 } • Otherwise, w d0 = 0
For the following departures d i (i > 0):

• If d i has a CFMU slot t cd i : w di = max{0, t cd i -δ c -t mind i , w di-1 +t mind i-1 -t mind i } • Otherwise, w di = max{0, w di-1 + t mind i-1 -t mind i }
The best trajectory for a departure d i (looked forward by the sequential branch & bound algorithm) is the one corresponding to the shortest path allowing a delay as near as possible to the requested wait d i .

C. Genetic algorithm solver

The conflict resolution method based on a genetic algorithm consider globally each traffic situation, without assuming any classification between aircraft: thus, the logical way to adapt this method to the new problem (which is the application of some predefined runways sequences) consist in modifying the global criterion to minimise: in this way, the predefined sequences will be considered as a goal but not as a constraint, which is necessary to ensure that some acceptable solutions still exist, even when the traffic situation does not allow to carry out the targeted sequences.

Concerning acceptable (conflict free) solutions, the global criterion is defined as the sum of each specific criterion relative to each aircraft: for a departure, this specific criterion must be refined, in order to estimate the difference between the takeoff time that would result from the proposed solution and the take-off time targeted in the optimal runway sequence.

Different definitions of such a criterion can be considered. The main difficulty is obviously relative to the difference between the anticipation time used for the ground conflicts resolution and the one used to compute the runways sequences: on large airports such as Roissy Charles De Gaulle, departures taxiing times can easily exceed the prediction time window, so that the take-off times that will result from the proposed paths and holding positions are uncertain on the long range.

Moreover, looking forward to hold the departures when their positions seem to be in advance compared to their targeted take-off slots is not appropriate, as such a ground traffic management would clearly risk to propagate every form of ground delay to the whole airport.

As a consequence, the proposed criterion is still proportional to aircraft delay, but a balance is applied, in order to penalise more the delay of an aircraft when its minimal runway access time becomes closer to its targeted slot.

With this kind of criterion (based on delay), the same treatment as before has to be considered concerning the management of the CFMU slots (see IV-B): an initial wait w d has to be computed for each departure d, in order to ensure the correct insertion of these particular departures in the rest of the traffic. Obviously, this initial wait also affects the definition of the criterion.

Finally, the penalty P (a) to be minimised for each aircraft a is estimated as a function of the delay dl a of the aircraft (including assigned wait and/or path lengthening), the minimal runway access time t mina and the targeted slot t a of the aircraft, as follows:

• For an arrival a: P (a) = dl a (unchanged)

• For a departure d with a CFMU slot t cd which is late (t mind > t cd + δ c ):

P (d) = 20 * (dl d + t min d -t cd )
• For a departure d with a CFMU slot t cd which is in advance (t mind < t cdδ c ) and which required wait is w d :

P (d) = 10 * (|dl d -w d | + t cd -t mind )
• For each other departure d which required wait is w d :

P (d) = 5 * (|dl d -w d | + max(0, t mind -t d ))
In these definitions, the balance that is applied to departures delay is defined in order to favor as often as possible departures against arrivals.

V. RESULTS

To measure the efficiency of the proposed optimisation methods, four simulations are carried out (with the same traffic sample as in III-D): the two different ground traffic solvers (i.e. the sequential method and the genetic algorithm solver) are tested on two scenarios: in the first one, there is no runway sequence to target, while in the second one, the optimal runways sequences are computed and targeted as explained before.

These four simulations are compared by the generated delay, the slots deviations for concerned departures, and the differences between the targeted slots and the final ones.

A. Delay comparisons

The following These delays can also be measured as a function of the number of taxiing aircraft on the airport, as shown on figure 8: the mean delay is calculated for each period of 10 minutes As one can see, the runway sequencing optimisation process enhances the departures results of both solvers, and the sequential solver becomes almost as efficient as the genetic algorithm one. Globally, the difference between a "basic" management of taxiing aircraft (i.e. the sequential method without runway sequencing) and the final genetic algorithm solver is really significant: 45 seconds per aircraft are saved on the whole day, and more than 1 minute par aircraft can be saved during traffic peaks.

Of course, the arrivals delay shown on figure 9 follow an opposite progression, especially with the final genetic algorithm solver (for which the defined criterion voluntarily give priority to departures). In an operational point of view, the 20 seconds of delay added per arrival in compensation to departures management enhancement should be profitable.

B. Deviations to CFMU slots

The figures 10 and 11 shows the distribution of the CFMU slots deviations observed for the concerned departures. These results show that the CFMU slots are quite respected (in fact, the only exceptions concern departures that are ready to leave their gate too late to catch their slot, in accordance with the CFMU requirements).

As no penalty was defined from 5 to 0 minutes before the CFMU slot, the major slots deviations observed are globally spread in this time period. As a consequence of the criterion defined for the genetic algorithm solver, the runway sequencing process allows to concentrate the departures take-off times at the beginning of the allowed period.

C. Deviations to targeted slots

The difference between the calculated runway sequences and the final ones is measured: the figure 12 shows the number of aircraft concerned by each value of slot deviation formulated in minutes.

This figure shows that the runway sequences generated with the genetic algorithm solver are closer to the targeted ones, but there are still a lot of aircraft that don't succeed in catching correctly their initial assigned slot. This result shows that the management of the taxiing aircraft is a very critical step and should really take advantage of some appropriate optimisation methods, rather than only be defined with some basic circulation rules.

VI. CONCLUSIONS AND FURTHER WORK

In the first part of this article, a classical (and exact) method has been implemented and tested to compute some optimal runways sequences at Roissy Charles De Gaulle airport, taking into account each traffic situation with precision, adding the expected arrival flow fixed by approach sectors to the actual ground positions of all taxiing aircraft. The simulation results show that the runways sequences can be largely enhanced if they are well organised with a sufficient anticipation time (the largest possible anticipation time greater than 30 minutes). As a consequence, the delay (and then the taxiing times) assigned to departures at the airport level could be significantly reduced if the surface management of the airport allows to perform these targeted optimal runways sequences.

The second part of this article explores and proposes some concepts that should be developed at the airport control level to manage correctly the taxiing aircraft, while targeting the computed runways sequences. This concepts can decrease significantly the departures delay, but the simulations carried out also confirm that this task is very complex during traffic peaks, as far as the speed of the taxiing aircraft is not precisely known and as far as the conflicts that have to be solved between these aircraft affect the feasibility of the runways sequences. The ground management of aircraft becomes again more complex for runways shared by both departures and arrivals, as departure delays can sometimes totally change the optimal sequence to target.

Further work will consists in refining the way to target a runway sequence at the airport level, by considering for example some new methods to enhance the estimation of the appropriate decisions that must be taken concerning the taxiing aircraft, in order to keep the ground traffic situations consistent with the targeted runways sequence.

Another development will concern the generalisation of the constraints defined to perform the runways sequences optimisation, taking into account more operational issues, like the sequencing rules used by the airport controllers relative to aircraft SID (Standard Instrument Departure) and STAR (Standard Terminal Arrival Route).

Fig. 1 .

 1 Fig. 1. Roissy map

  Fig. 3. Shifted windows

Fig. 4 .

 4 Fig. 4. Criterion for CFMU slots

  Fig. 5. Sequences tree

Fig. 6 .Fig. 7 .

 67 Fig. 6. Mixed runway 27 at Roissy

Fig. 8 .Fig. 9 .

 89 Fig. 8. Mean delay per departure (seconds)

Fig. 11 .

 11 Fig. 10. CFMU deviations without sequencing

Fig. 12 .

 12 Fig. 12. Deviations to targeted slots (minutes)

CFMU: Central Flow Management Unit