Bhargav Teja Nallapu

Nicolas P Rougier

Bapi Raju Surampudi

The art of scaling up : a computational account on action selection in basal ganglia

Keywords: neural dynamics, basal ganglia, large scale, nengo, decision making

, besides operating with a larger neuronal populations. The power of converting algorithms to efficiently weighed neural networks in Nengo [10, 1] is exploited in this work. Crucial aspects in a computational model, like parameter tuning and detailed neural implementations, while moving from a simplistic to large-scale model, are studied.

Introduction

Action selection is one of the most vital processes for the survival of an organism. The very importance of the process of action selection (and learning from it) in the survival of an organism, pushes for a need of understanding the process from an evolutionary, biological and physiological point of view.

Brain works by running complex dynamics forming complex connections within itself, specific to each behavioral repertoire. It is at the level of few (or many) neurons that the information transfer takes place, which drives all the processes like perception, memory, decision making, language or any other brain process. Ideally, it is that level of detail one wants to model any sub-system of brain or the whole model of brain itself. We start with considering one of our previous works on a computational study of decision making and its dynamics using a thalamo-cortical BG network [START_REF] Nallapu | Dynamics of reward based decision making a computational study[END_REF] inspired by [START_REF] Guthrie | Interaction between cognitive and motor cortico-basal ganglia loops during decision making: a computational study[END_REF] and replicated in [START_REF] Topalidou | re] interaction between cognitive and motor corticobasal ganglia loops during decision making: a computational study[END_REF].

The emphasis is on modeling these functional networks at a large scale, both in terms of neuron populations as well as multiple brain structures. To achieve this, we use a neural engineering framework(NEF) based graphical and scripting tool called Nengo [START_REF] Stewart | Python scripting in the nengo simulator[END_REF].

Methods

Task

The task is a probabilistic learning task that is described in [START_REF] Pasquereau | Shaping of Motor Responses by Incentive Values through the Basal Ganglia[END_REF] and used in [START_REF] Guthrie | Interaction between cognitive and motor cortico-basal ganglia loops during decision making: a computational study[END_REF][START_REF] Topalidou | re] interaction between cognitive and motor corticobasal ganglia loops during decision making: a computational study[END_REF][START_REF] Nallapu | Dynamics of reward based decision making a computational study[END_REF]. Four target shapes are associated with different reward probabilities (see figure 1). Every time any two of the four possible shapes are presented at two random positions (out of the four cardinal positions -up, right, down and left). By the end of trial period, a choice is made and the reward is given according to the reward probability associated with the chosen shape. In a single independent

Reward probabilities

Fig. 1. The two armed bandit task as described in [START_REF] Pasquereau | Shaping of Motor Responses by Incentive Values through the Basal Ganglia[END_REF][START_REF] Guthrie | Interaction between cognitive and motor cortico-basal ganglia loops during decision making: a computational study[END_REF].

trial, the cognitive decision (shape of the cue) and motor decision (direction of position) are independent of each other. However, ideally, the motor decision is expected to be in the direction of the cue shape that is chosen. On subsequent reward association of the cue decision, one should eventually select the direction in which the most rewarding cue is present.

Model

In [START_REF] Leblois | Competition between feedback loops underlies normal and pathological dynamics in the basal ganglia[END_REF], authors demonstrated an action selection mechanism in the cortico-basal ganglia loops based on a competition between the positive feedback, direct pathway through the striatum and the negative feedback, hyper-direct pathway through the sub-thalamic nucleus. This model allows a bidirectional information flow between loops such that during early trials, a direction can be selected randomly, irrespective of the cue positions. However, after repeated trials, the model is able to consistently make the motor decision, only after cognitive decision, towards the position of the more rewarding cue shape.

The NEF and Nengo

The underlying principles of NEF are: representation, transformation and dynamics. The activity of a group of neurons is considered to be best represented by encoding of some underlying variable, for e.g, any vector generally of smaller dimensionality. The transformation of information from one neural group to the other neural group. i.e., the neural group representing x can be connected to other group of neurons representing a variable y, such that y = f (x). Any desired function can be approximated with improved accuracy by increasing the number of neurons. The dynamics of NEF allows us to build recurrent neural networks. These networks can compute the time evolution of a given variable x of the form dx dt = f (x, u).

Results

The following simulations assume cue shapes are represented by [0, 1, 2, 3] in the cognitive channel of the cortex and the cardinal directions, where the shapes could be presented, are also represented by [0, 1, 2, 3] in the motor channel of the cortex. The cue shapes have a rewarding probability in the order 1>0>2>3. The synaptic weights that were learned in the previous model were applied. These weights ensure that the highest rewarding cue is always selected. It is also implicit in the model dynamics that the position corresponding to the chosen shape only will be selected. Figure 3 displays the correct cognitive decision (shape) and corresponding motor decision (position).

Model

Cortical level Total Simplistic model [START_REF] Guthrie | Interaction between cognitive and motor cortico-basal ganglia loops during decision making: a computational study[END_REF] 24 72 Model implemented 24000 387,200 Full-scale rat model [START_REF] Moren | A full rat-scale model of the basal ganglia and thalamocortical network to reproduce parkinsonian tremor[END_REF] 180K 3 million Table 1. No. of neurons across models Fig. 3. For the combinations of cue shape and position, the best rewarding cue shape is selected (see CTX COG) and the corresponding position (as per stim cog and stim mot represent shape 0 is shown at position 3 and shape 1 is shown at position 2). It can be seen that, at a point later than choosing shape, corresponding position is chosen (see CTX MOT). Inset The decision in the original simplistic model

Discussion

For the models claiming to have network-induced dynamics, the choice of the neuronal dynamics should not make a significant difference. This has been demonstrated clearly in this work. The model developed is tested under similar conditions of action selection task, switching between direct computations and neural implementations like Sigmoidal and Integrate & Fire (IF). To start with, we used simple neurons that directly compute a function. Then the neurons are changed to detailed implementations, but to a lower scale. However, the switch between neuron implementations involved minimal tuning of parameters of the network as well as optimization of few framework parameters, provided there is computational power to handle the large scale of spiking or IF neurons.

Although the population numbers in this work are comparable to that of experimental numbers of a rat's BG and some recent modeling work by Moren et al. 2015 [START_REF] Moren | A full rat-scale model of the basal ganglia and thalamocortical network to reproduce parkinsonian tremor[END_REF] (see table 1), we are still far away from the scale of that of humans' (150K in rats where as 2.2 million neurons, only the globus pallidus and subthalamic nucleus combined [START_REF] Halliday | Comparison of the basal ganglia in rats, marmosets, macaques, baboons, and humans: Volume and neuronal number for the output, internal relay, and striatal modulating nuclei[END_REF]). As for results, the neural activity corresponding to synaptic weight-driven decision making and the ideal choice as per high reward, were consistent. We also believe, at a full range simulations on the model, performance would match that from the previous simplistic model. In future, such a functional large scale network could become readily usable in other functional processes involving motor reaching or motor learning [START_REF] Magdoom | Modeling basal ganglia for understanding parkinsonian reaching movements[END_REF], modeling deficits in neuro-degenerative disorders such as Parkinsonianism [START_REF] Muralidharan | A computational model of altered gait patterns in parkinsons disease patients negotiating narrow doorways[END_REF] etc.

The authors would like to acknowledge the following grants which have been a major support to this research.

Fig. 2 .

 2 Fig. 2. Architecture of BG model (left) from [2]. A model nengo network (right)

-

  Indo-French CEFIPRA Grant for the project Basal Ganglia at Large (No. DST-INRIA 2013-02/Basal Ganglia dated 13-09-2014) -Internships programme at INRIA, 6 month Internship with Team Mnemosyne at INRIA Bordeaux -Sud-Ouest -Travel Support by Nengo 3 rd annual Summer School on large-scale brain modeling, University of Waterloo, ON, Canada, 5 th June, 2016 -17 th June, 2016


Ingrid Falk

Fabienne Martin

Automatic Identification of Aspectual Classes across Verbal Readings

The automatic prediction of aspectual classes is very challenging for verbs whose aspectual value varies across readings, which are the rule rather than the exception. This paper sheds a new perspective on this problem by using a machine learning approach and a rich morpho-syntactic and semantic valency lexicon. In contrast to previous work, where the aspectual value of corpus clauses is determined on the basis of features retrieved from the corpus, we use features extracted from the lexicon, and aim to predict the aspectual value of verbal readings rather than verbs. Studying the performance of the classifiers on a set of manually annotated verbal readings, we found that our lexicon provided enough information to reliably predict the aspectual value of verbs across their readings. We additionally tested our predictions for unseen predicates through a task based evaluation, by using them in the automatic detection of temporal relation types in TempEval 2007 tasks for French. These experiments also confirmed the reliability of our aspectual predictions, even for unseen verbs.

Introduction

It is well known that the aspectual value of a sentence plays an important role in various NLP tasks, like for instance the assessment of event factuality [START_REF] Saurí | Are you sure that this happened? Assessing the factuality degree of events in text[END_REF], automatic summarisation [START_REF] Kazantseva | Summarizing short stories[END_REF], the detection of temporal relations [START_REF] Costa | Aspectual type and temporal relation classification[END_REF] or machine translation [START_REF] Meyer | Detecting narrativity to improve English to French translation of simple past verbs[END_REF]. Since, however, the aspectual value of a sentence results from a complex interplay between lexical features of the predicate and its linguistic context, the automatic detection of this aspectual value is quite challenging.

Studies on the computational modelling of aspectual classes emerged about two decades ago with the work of [START_REF] Passonneau | A computational model of the semantics of tense and aspect[END_REF] and [START_REF] Klavans | Degrees of stativity: The lexical representation of verb aspect[END_REF], among others. In probably the most extensive study on the field, [START_REF] Siegel | Learning methods to combine linguistic indicators: Improving aspectual classification and revealing linguistic insights[END_REF] extract clauses from a corpus and classify them into states and events, sorting the latter into culminated and non-culminated events in a subsequent step. The classification is based on features inspired by classic Vendlerian aspectual diagnostics, themselves collected from the corpus. Since, however, these features are collected on a type level, this method does not give satisfying results for verbs whose aspectual value varies across readings (henceforth 'aspectually polysemous verbs'), which are far from exceptional (see section 3) 1 .

This problem is directly addressed by [START_REF] Zarcone | Computational models for event type classification in context[END_REF]. These authors classify corpus clauses into the four Vendlerian aspectual categories (states, activities, accomplishments and achievements), and like Siegel and McKeown, base their classification on (classic aspectual) features collected from the corpus. However, they additionally employ some syntactic properties of the predicate, a move that enables them to better account for the influence of the linguistic context on the aspectual value of the verb across readings. [START_REF] Friedrich | Automatic prediction of aspectual class of verbs in context[END_REF], who extend [START_REF] Siegel | Learning methods to combine linguistic indicators: Improving aspectual classification and revealing linguistic insights[END_REF] model to distributional features, also address the problem of aspectually polysemous verbs, by making use of instancebased syntactic and semantic features, obtained from an automatic syntactic analysis of the clause.

The approach we present here is designed to tackle the issue of aspectual variability and is complementary to the methods just described. As we know from detailed work on verbal syntax and semantics in the tradition of [START_REF] Dowty | Word Meaning and Montague Grammar : The semantics of Verbs and Times in Generative Semantics and in Montague's PTQ[END_REF], [START_REF] Levin | English Verb Classes and Alternations: A Preliminary Investigation[END_REF], [START_REF] Rappaport | Building verb meanings[END_REF] and subsequent work, many morpho-syntactic and semantic properties of the verb exert a strong influence on its aspectual value in context. As far as we know, no study on the computational modelling of aspectual classes has tried to systematically take advantage of these correlations between lexical properties and lexical aspect. We aim to capitalise on these correlations with the help of a rich French lexical resource, "Les Verbes Français" [START_REF] Dubois | Les Verbes français[END_REF][START_REF] François | Présentation de la classification des Verbes Français de Jean Dubois et Françoise Dubois-Charlier[END_REF], henceforth LVF). The LVF is a valency lexicon of French verbs providing a detailed morpho-syntactic and semantic description for each reading (use) of a verb.

Differently from previous work, the instances we classify aspectually are verbal readings as delineated in the LVF (rather than corpus phrases). We therefore study lexical aspect on an intermediate level between the coarse-grained type (verb) level and the fine-grained corpus utterance level. Also, while in previous approaches, the features are collected from corpora, those we make use of are retrieved from the lexicon entries. The substantial advantage of this approach, that heavily makes use of the colossal amount of information manually coded in the LVF, is that it enables us to fully investigate the aspectual flexibility of verbs across readings and the factors that determine it.

For our automatic aspectual classification, we firstly extracted verbal readings from the LVF for a set of 167 frequent verbs chosen in such a way that each of the four Vendlerian aspectual classes are roughly equally represented. A semanticist manually annotated each of the corresponding 1199 readings based on a refinement of the classic Vendlerian 4-way aspectual categorisation. This refinement is motivated by recent studies in theoretical linguistics converging in the view that the traditional quadripartite aspectual typology has to be further refined (see [START_REF] Hay | Scalar structure underlies telicity in 'degree achievements[END_REF][START_REF] Piñón | Weak and strong accomplishments[END_REF][START_REF] Mittwoch | On the criteria for distinguishing accomplishments from activities, and two types of aspectual misfits[END_REF] among many others). Such a refinement enables one to better account for the variable degree of aspectual flexibility among predicates, so as to e.g. delineate between 'strictly stative' predicates (e.g. know), and those stative predicates that also naturally display an activity reading (e.g. think). This annotation provides the gold standard for our classification experiments. For each annotated reading, we then collected morpho-syntactic and semantic features from the LVF, chosen for their relevance for the aspectual value of the verb in context. Based on these features, we trained classifiers to automatically predict the aspectual class of the LVF readings.

We assessed the accuracy of our automatic aspectual classification in a task based evaluation as follows. [START_REF] Costa | Aspectual type and temporal relation classification[END_REF] showed that (type-based/verb-level) aspectual indicators improve temporal relation classification in Tem-pEval challenges [START_REF] Verhagen | Semeval-2007 task 15: Tempeval temporal relation identification[END_REF], which emerged in conjunction with TimeML and Time-Banks [START_REF] Pustejovsky | Annotation of temporal and event expressions[END_REF]. The tasks involved in these challenges require temporal reasoning. Following Branco and Costa's example, we performed TempEval tasks on the French TempEval data, using aspectual indicators derived from the predictions generated by our classifier. This way, we could show that our aspectual classification based on lexical features is reliable.

The paper is structured as follows. Section 2 presents the resource used. Section 3 explains on which criteria verbal readings were manually annotated. Section 4 describes the features collected from the LVF. Section 5 presents the automatic aspectual classification based on these features. Section 6 presents the aspectual indicators derived from the classification. Section 7 describes how our automatic classification was evaluated through TempEval tasks.

The Resource -LVF

The LVF, which roughly covers 12 300 verbs (lemmas) for a total of 25 610 readings, is a detailed and extensive lexical resource providing a systematic description of the morpho-syntactic and syntactico-semantic properties of French verbs 2 . The basic lexical units are readings of the verbs, determined by their defining syntactic environment (argument structure, adjuncts) and a semiformal semantic decomposition (with a finite repertoire of 'opérateurs'). Once the idiosyn-crasies are put aside, this decomposition very roughly uses the same inventory of labels and features as in the lexical templates found in e.g. [START_REF] Pinker | Learnability and Cognition: The Acquisition of Argument Structure[END_REF] or [START_REF] Jackendoff | Semantics and Cognition[END_REF]. In Table 1, we give the sample entries for the verb élargir 'widen' to illustrate LVF's basic layout.

Syntactic description (Table 1a). Each reading of a verb is coupled with a representation of its syntactic frames. In principle, a verbal reading can be coupled with a transitive frame (labelled 'T'), a reflexively marked frame ('P') and an intransitive frame ('A', 'N') unmarked by the reflexive. The syntactic description additionally specifies some semantic features of the main arguments (e.g. whether the subject and direct object are animate and/or inanimate, whether the indirect object refers to a location, etc). This information is often crucial for the aspectual value of the reading (e.g. a 'human-only' intransitive frame strongly indicates unergativity and henceforth atelicity).

Semantic description (Table 1b). Each entry in the LVF is also characterised by a semi-formal semantic decomposition providing a rough approximation of the meaning of each verbal reading. Each entry is therefore paired with a finite set of primitive semantic features and labels on the basis of which verbal readings are sorted into 14 semantic classes (eg. psych-verbs, verbs of physical state and behaviour, etc.). The semantic features and labels used in the semantic decomposition provide other cues about the type of verbs (unergative/ unaccusative verbs, manner/ result verbs, etc.) which is instantiated by each reading. For instance, for the reading 01 of élargir 'widen' ('élargir01' for short) in Table 1b, 'r/d +qt [p]' roughly corresponds to BECOME(more(p)) ('r/d' stands for '(make) become'; '+qt' stands for an increase along a scale). From this, one can safely infer that élargir01 is a 'degree achievement' verb.

Derivational properties. The LVF also indicates when a verb is formed through a derivational process, and in the positive case, provides information about the category of the verbal root, thus enabling one to identify deadjectival or denominal verbs. Finally, for each entry is specified which suffix is used for the available reading-preserving deverbal nominalisations and adjectives (-ment,age, -ion, -eur, -oir, -ure or zero-derived nominalisations, and -able, -ant, -é adjectives).

The annotation

We retrieved 1199 entries (verbal readings) for the selected 167 frequent verbs mentioned earlier. On average, each verb has roughly 15 readings, while 50% have more than 133 . These readings were manually annotated according to a fine-grained aspectual classification on a 'telicity scale' of eight values.

At the bottom of the scale are readings that are unambiguously ('strictly') stative (i.e. for which any other aspectual value is excluded), rated with 1 (S-STA). For instance, élargir02 (see Table 1a) is rated with 1, given (a.o.) its incompatibility with the progressive. Those are distinguished from stative verbs that also display a dynamic reading (e.g. penser 'think'), rated with 2 (STA-ACT). Readings that are unambiguously dynamic and atelic ('strict activity' readings) are rated with 3 (S-ACT).

At the top are found achievement readings for which any other aspectual value is excluded, rated with 8 (S-ACH). At the middle of the scale are found 'variable telicity' readings, that have no preference for the telic use in a neutral context and are compatible both with forand inadverbials, rated with 4 (ACT-ACC). For instance, élargir01 is rated with 4, because (a.o.) it is compatible both with forand inadverbials and has no preference for the telic reading in a neutral context. These variable telicity readings are distinguished from 'weak accomplishment' readings, rated with 5 (W-ACC). Out of context, weak accomplishment readings trigger an inference of completion and have a preference for the telic use; however, they are nevertheless acceptable with a for-adverbial (on the relevant interpretation of this adverbial). For instance, remplir01 'fill' (Pierre a rempli le seau d'eau 'Peter filled the bucket with water') is rated with 5, because it by default triggers an inference of completion, but is nevertheless still acceptable with a for-adverbial under the 'partitive' reinterpretation of this adverbial. Under this reinterpretation, described e.g. by [START_REF] Smollett | Quantized direct object don't delimit after all[END_REF] or [START_REF] Champollion | The scope and processing of for-adverbials: A reply to Deo and Piñango[END_REF], the sentence triggers an inference of non-completion [START_REF] Bott | The Processing of Events[END_REF] joie 'This news filled Peter with joy') -are incompatible with the partitive reinterpretation of for-adverbials. 4 Those are rated with 6 (S-ACC). Finally, accomplishments that share a proper subset of properties with achievements are rated with 7 (ACC-ACH).

The annotator evaluated each entry with a definite or singular indefinite internal argument, in order to abstract away from the role of the determiner in the aspectual value of the VP (see e.g. [START_REF] Verkuyl | A Theory of Aspectuality : The Interaction between Temporal and Atemporal Structure[END_REF]).

We also used a coarser grained aspectual scale and group the verbal readings into the following classes: ATElic (rating 1-3), with VARiable telicity (rating 4), and TELic (5 or more). Table 2 gives an overview of the distribution of the aspectual ratings.

The first finding is that verbs display a considerable aspectual variability across readings, which confirms the need to go beyond the type level for the computational modelling of aspectual classes. The aspectual value of 2/3 of the 151 verbs with more than one reading varies with the instantiated reading (on the 8 value scale). With respect to the coarser grained scale, roughly half of the verbs (82, for a total of 793 readings) have readings in more than one of the three overarching aspectual classes.

The features

The LVF connects each verbal reading with specific morphological, syntactic and semantic features. Among such features, those that influence the lexical aspect of the verb in context are known to be pervasive: Verbs encoding the BECOME operator in their event structure generally have a telic use; intransitive manner verbs are mostly activity verbs (see e.g. Rappaport Hovav and Levin (1998) and subsequent work); ditransitive verbs like give are mostly result verbs (see e.g. [START_REF] Pylkkänen | Introducing Arguments[END_REF]) and thus accomplishments. 5 . We took advantage of many of these features for our classification. Also, some semantic classes give very clear hints to the lexical aspect of its members. For instance, readings instantiating the class of 'enter/exit verbs' are telic, those instantiating the 'transformation' class are never atelic only, etc. 6We also made use of features conveyed by the semantic decomposition, in particular its main component (BECOME, DO, ITER, STATE, etc.).

We also took advantage of the encoded information on the suffixes used in reading-preserving nominalisations. For instance, readings with an intransitive but no transitive frame can in prin- ciple characterise unaccusative (telic) or unergative (atelic) verbs. But only the latter undergoeur nominalisation, as in English (see [START_REF] Keyser | On the middle and ergative construction in English[END_REF]). The availability of the -eur nominalisation is therefore a reliable aspectual feature too.

Tables 3 and4 compare features used in some previous aspectual classifications and their equivalents in the LVF. As one can check, the LVF features cover most of the features used in [START_REF] Siegel | Learning methods to combine linguistic indicators: Improving aspectual classification and revealing linguistic insights[END_REF] and [START_REF] Zarcone | Computational models for event type classification in context[END_REF] 7 . For obvious reasons, features related to grammatical aspect conveyed by tenses are not covered in our valency lexicon. But overall, our set of features roughly corresponds to those used in previous work, for a total of 38 features.

Classifying LVF entries

The items we classified are the 1199 readings for the 167 verbs selected. Our classification task consisted in predicting the right (coarse-grained) aspectual class for these readings (ATE, VAR or TEL). In this supervised learning setting, we ap- plied the classifiers shown in Table 5 with the implementation provided by Weka [START_REF] Hall | The WEKA data mining Software: An update[END_REF], mostly with their default settings 8 . We measured the performance of the classifiers by assessing the accuracy in 10-fold cross-validation, and compared it to the accuracy of a baseline classifier which always assigns the majority class (TEL, rules.ZeroR). We also performed a linear forward feature selection using the Naïve Bayes algorithm 9 . This way, nine features were selected, coding, among others:

• the presence of a temporal or manner argument/adjunct in the semantic decomposition;

• the main primitive in the semantic decomposition;

• the use of the suffixes -ment and -ure in the reading-preserving nominalisation;

• the relative polysemy of the lemma (indicated by the number of its readings);

• a subject that must be inanimate;

• the presence of a reflexive reading.

8 For libsvm (the SVM implementation), we used a linear kernel and normalisation. We selected roughly one classifier from each class. 9 An exhaustive search with the 38 features in this group was computationally too time-consuming. The results in Table 5 show that the features retrieved from the LVF enable one to predict the aspectual class considerably better than the baseline:

The accuracy ranges from 12 points to almost 20 above the baseline accuracy of 48.37. The best configuration, achieving an accuracy of 67.48%, is the lazy.kstar classifier based on the feature set reduced by feature selection. A comparison with the results reported in previous work is difficult, due to the great discrepancies in the experimental settings (see the introduction). However, our results clearly show that the aspectual class characterising verbal readings can be predicted with a reasonable precision on the basis of lexical-related information only. They once again empirically confirm the well-documented correlations between lexical aspect and the morphosyntactic/semantic properties of the verb.

Aspectual indicators

In this section, we take a more qualitative look at the results obtained in section 5. We assessed the quality of the predictions of our model (henceforth LVF-model) in two ways. Firstly, we derived aspectual indicators for the type level, describing the general 'aspectual profile' of a verb across all its readings. These are later used in the task based evaluation described in section 710 . Secondly, we looked at the aspectual values assigned to the readings of particular verbs (see indicators for the verbal readings below).

Indicators for the type-level. The aspectual indicators for the type-level are computed on the basis of the aspectual values predicted for each reading of the verb. As shown in Table 6, they are designed to reflect how aspectual values vary across the readings of the verb. For example, the indica- 6a shows whether there is any variation at all, 't' assesses the presence of at least one telic reading, etc. Whereas the indicators in Table 6a provide qualitative cues, those in Table 6b convey quantitative information. The first three give the proportion of readings of a particular aspectual class. The last three are computed from the probability estimates generated by the libsvm classifier.

In order to get an idea of the quality of our predictions, we computed from automatic predictions the aspectual indicators for all annotated verbs. We provide some of them in Table 7 for verbs judged aspectually polysemous by the annotator. These 'automatic' aspectual indicators are given in normal font. For the same verbs, we also computed the 'manual' aspectual indicators, i.e. those computed on the basis of the manual annotations (when possible)11 . These are set in bold face. The verbs in Table 7a are dominantly telic, those in 7b dominantly atelic and those in 7c dominantly variable. As one can check, the dominant aspectual value is correctly assigned in most cases. Also, in most cases, the proportion of uses of the nonpreferred readings closely matches the proportion obtained manually. Unsurprisingly, the sample of verbs predicted to be 'mostly telic' are mostly (quasi-)achievement verbs or strong accomplishments describing 'non-gradual' changes (verbs lexicalising changes involving a two-point scale, e.g. dead or not dead for kill, see e.g. [START_REF] Beavers | Scalar complexity and the structure of events[END_REF]). Unsurprisingly again, many verbs predicted to be 'mostly variable' are degree achievement verbs. More remarkably, remplir 'fill' is rightly predicted to be 'mostly telic', although it is a verb of gradual change. The model therefore preserves here the crucial distinction between degree achievements associated with a close scale like remplir, tolerating atelic readings under some uses although they conventionally encode a maximal point (see [START_REF] Kennedy | Measure of change: The adjectival core of verbs of variable telicity[END_REF]), and achievement verbs associated with an open scale like élargir 'widen', that also accept both forand inadverbials, but do not show a preference for the telic reading in absence of any adverbial. These observations suggest that even if predictions for some readings are wrong, the aspectual indicators might still rightly capture the general 'aspectual profile' of verbs at the type level.

Indicators for the verbal readings. We also inspected the predicted values for some predicates and compared them to the values assigned manually. For predicates showing a high degree of aspectual variability like élargir 'widen' (see Table 7c), the results are very good: élargir01 ('They are widening the road') is correctly analysed as VAR and élargir04 ('They are extending the majority') as TEL. Interestingly, élargir02 ('This jacket widens Pierre's shoulders') is correctly analysed as ATE, despite of the fact that it is wrongly analysed by the LVF as instantiating the class of change of state verbs (see footnote 6). This suggests that the computational model could leverage the information provided by the syntactic frames associated to élargir02 (see Table 1b) to outweigh the wrongly assigned semantic class and produce the correct aspectual prediction.

Task based evaluation

Reliable automatic aspectual classifications are expected to enhance existing solutions to temporal relation classification. Thus, if our LVF-model improves such a solution, we can conclude that our learned aspectual values are reliable. We therefore evaluated the predictive power of the LVFmodel on unseen verbs through such tasks, following the method proposed in [START_REF] Costa | Aspectual type and temporal relation classification[END_REF]. While [START_REF] Costa | Aspectual type and temporal relation classification[END_REF] collected their aspectual indicators from the web and improved the temporal relation detection in the Portuguese TimeBank (PTiB), we derive ours from the predictions generated using the LVF-model, as described in section 6 and use them in TempEval tasks for the French TimeBank. TempEval data, a corpus for French annotated in ISO-TimeML (FTiB in the following) described in [START_REF] Bittar | French TimeBank: An ISO-TimeML annotated reference corpus[END_REF]. This data contains about 15 000 tokens12 annotated with temporal relations. Of these, roughly 2/3 are marked between 2 event arguments and 1/3 between an event and a temporal expression. The classification tasks we are concerned with deal with the automatic detection of the type of these temporal relations, namely the tasks A, B and C in the TempEval 2007 challenge 13 . Table 8 gives an overview of the data for each of the three classification tasks. We build our experiments on top of a base system addressing these challenges and show that the performance of this base system can be improved using our aspec- tual indicators. Like [START_REF] Costa | Aspectual type and temporal relation classification[END_REF], we implemented as base system the classifiers proposed for English by [START_REF] Hepple | USFD: Preliminary exploration of features and classifiers for the TempEval-2007 Task[END_REF], which only rely on relatively simple annotation attributes. Table 9 lists the features used in the context of our FTiB data, basically the same as in [START_REF] Hepple | USFD: Preliminary exploration of features and classifiers for the TempEval-2007 Task[END_REF] and [START_REF] Costa | Aspectual type and temporal relation classification[END_REF]. As in their work, we also determined the final set of features by performing an exhaustive search on all possible feature combinations for each task, using again the Naïve Bayes algorithm. The features marked ' ' are those finally selected this way. Using this set of features, we trained the same classifiers and under the same conditions described in section 5 on the FTiB data. The accuracy of the resulting models in 10-fold cross-validation on the three TempEval tasks are shown in italics in Table 10.

Following again [START_REF] Costa | Aspectual type and temporal relation classification[END_REF], we then enhanced this basic set of features with each of the aspectual indicators computed from the predictions generated by the LVF-model. The aspectual indicators are listed in Table 6; we described their computation in section 6. This way, we obtained 10 enhanced feature sets, one for each as-pectual indicator. Using these feature sets and the same classifiers as before, we learned models on the FTiB data and computed their accuracy in 10 fold cross-validation.

The improvements achieved this way are shown in Table 10. Whenever an aspectual indicator improves the results of the base system, we give its accuracy (in bold face) below the accuracy of the base system. The superscripts refer to the lines in Table 6 and show which of the aspectual indicators was used to enhance the base feature set to obtain the reported improved accuracy14 .

The results given in Table 10 show that the accuracy of 8 out of the 15 tested classifiers could be improved by 1-3 points by adding the aspectual indicators. The indicator which produced the most and largest improvements was the average over the probability estimates, suggesting that this value best reflects the dominant aspectual value of the verb. Overall, the improvement obtained through our classification is quantitatively comparable to the enhancement realised by [START_REF] Costa | Aspectual type and temporal relation classification[END_REF]: Their results show an improvement similar in size to ours for 9 out of the same 15 classifiers. They evaluate on a test set, whereas we compare accuracy in 10-fold cross-validation. This was necessary since the French TimeBank is considerably smaller (roughly 1/4 of Costa and Branco's data set for Portuguese, see PTiB column in Table 8). As mentioned earlier, a qualitative comparison is nevertheless difficult, given the substantial differences between the data and the methodology used here and there.

The results clearly show however that the LVFmodel trained on our annotated lexical entries performs well on unseen predicates.

Conclusion and future work

This paper focuses on the issue of aspectual variability for the computational modelling of aspectual classes, by using a machine learning approach and a rich morpho-syntactic and semantic valency lexicon. In contrast to previous work, where the aspectual value of corpus clauses is determined at the type (verb) level on the basis of features retrieved from the corpus, we make use of features retrieved from the lexicon in order to predict an aspectual value for each reading of a same verb (as they are delineated in this lexicon). We firstly studied the performance of the classifier on a set of manually annotated verb readings. Our results experimentally confirm the theoretical assumption that a sufficiently detailed lexicon provides enough information to reliably predict the aspectual value of verbs across their readings. Secondly, we tested the predictions for unseen predicates through a task based evaluation: We used the aspectual values predicted by the LVF-model to improve the detection of temporal relation classes in TempEval 2007 tasks for French. Our predictions resulted in improvements quantitatively similar to those achieved by [START_REF] Costa | Aspectual type and temporal relation classification[END_REF] for Portuguese and thus confirm the reliability of our aspectual predictions for unseen verbs.

The investigation reported here can be further pursued in many interesting ways. One possible line of work consists in exploring the aspectual realisation and distribution of the LVF readings in corpus data. This would also provide means to relate our findings for verbal readings to corpus instances.

Our study strongly relies on the LVF lexical database, a very extensive source of morphosyntactic and semantic information. For other languages, this kind of information, when it is available, is generally not contained in a single lexicon. Therefore, a further interesting research direction would be to evaluate the applicability of our technique to suitable information from distributed resources. On this respect, recent efforts made for linking linguistic and lexical data and making these data accessible and interoperable would certainly be very helpful. For English in particular, available suitable resources are already abundant.

One of these is the Pattern Dictionary of English Verbs, see [START_REF] Hanks | Mapping Meaning onto Use: A Pattern Dictionary of English Verbs[END_REF]. Other interesting data bases are FrameNet [START_REF] Baker | The Berkeley FrameNet project[END_REF], VerbNet [START_REF] Levin | English Verb Classes and Alternations: A Preliminary Investigation[END_REF][START_REF] Schuler | VerbNet: A Broad-Coverage, Comprehensive Verb Lexicon[END_REF] and Prop-Bank [START_REF] Palmer | The proposition bank: An annotated corpus of semantic roles[END_REF], especially since these different resources have been mapped together by [START_REF] Loper | Combining lexical resources: Mapping between propbank and verbnet[END_REF], thus giving access to both the lexical and distributional properties defining each entry.

Increasing the reliability of automatic identification of aspectual classes also represents interesting opportunities for several NLP applications. A finer-grained and more reliable automatic assessment of aspectual classes can among others be quite useful for increasing the accuracy of textual entailment recognition, and, particularly, the sensitivity of systems to event factuality [START_REF] Saurí | Fact-Bank: A corpus annotated with event factuality[END_REF]. For instance, for telic perfective sentences, while the inference of event completion amounts to an entailment with strong accomplishments and (quasi-)achievements (at least in absence of an adverb signalling incompletion like partly), the same inference is to some extent defeasible with weak accomplishments. Integrating finer-grained distinctions among predicates could also enable one to better disambiguate verbal modifiers like durative adverbials. A foradverbial typically signals that the event is incomplete when it modifies a weak accomplishment; e.g., Peter filled the truck for one hour suggests that the filling event is not finished, see [START_REF] Bott | The Processing of Events[END_REF] a.o. However, the same adverbial does not trigger this inference when it applies to a strong accomplishment or a (quasi)-achievement. For instance, They broke the law for five days does not suggest that the breaking event is not finished. A system that performs better in the identification of fine grained aspectual classes would therefore evaluate with more precision the probability that the reported event is completed in the actual world.

Table 1 :

 1 , see e.g. Peter filled the bucket with water for 10 minutes). 'Strong' accomplishment readingslike remplir09 (Cette nouvelle a rempli Pierre de id frame encoded information 01 T1308 transitive, human subject, inanimate direct object, instrumental adjunct P3008 reflexive, inanimate subject, instrumental adjunct A30 intransitive with adjunct, inanimate subject 02 N1i intransitive, animate subject, prep. phrase headed by de (of ) A90intransitive with adjunct, subject human or thing T3900 transitive, inanimate subject, object human or thing The four readings illustrated by sample sentences and their semantic description a Literal translations -01: One widens a road/the road is REFL widened/the road widens. 02: This jacket widens Paul 'at the' shoulders/ The dress widens the waist. 03: One widens one's knowledge. 04: One extends the debate to foreign policy. LVF entries for élargir

	(a) Syntactic descriptions

Table 2 :

 2 Aspectual distribution of the 1199 manually annotated verbal readings

	1	2	3	4	5	6	7	8	1-3	4	5-8
	S-STA ACT-STA S-ACT ACT-ACC W-ACC S-ACC ACC-ACH S-ACH	ATE VAR TEL
	182	67	175	195	172	227	29	152	424	195	580
			(a) 8 value scale					(b) 3 value scale
	Features collected from corpus	Related features
	Example Clause		in LVF
	frequency		-
	not or never		-
	She can not explain why.
	temporal adverb	durative adverbial
	I saw to it then.	in semantic decomposition
	implicit or no external argument canonical passive, refl.
	He was admitted to the hospital. constr. w. instrumental adj.
	past/pres participle	-
	. . . blood pressure going up.
	in adverbial		-
	She built it in an hour.
	4 tense related features	-
	manner adverb		manner argument or adjunct
	She studied diligently.
	evaluative adverb	+ql
	They performed horribly.	in semantic decomposition
	for adverbial		durative adverbial
	I sang for ten minutes.	in semantic decomposition
	continuous adverb	+re (iterative operator)
	She will live indefinitely.	in semantic decomposition

Table 3 :

 3 [START_REF] Siegel | Learning methods to combine linguistic indicators: Improving aspectual classification and revealing linguistic insights[END_REF] and LVF features.

Table 4 :

 4 [START_REF] Zarcone | Computational models for event type classification in context[END_REF] and LVF features.

	Features collected	Related features
	from corpus	in LVF
	temporal adverbs	temporal arg. or adj.
	intentional adverbs	-
	frequency adverbs	+qt in sem. decomp.
	iterative adverbs	+re in sem. decomp.
	tense	-
	only subject	A* or N* frame
	presence of direct obj	T* frame
	presence of indirect obj N* frame
	presence of locative arg	encoded in frame sem class = L
	presence of sent. compl. encoded in frame
	canonical passive	T* and A* schema
	subj & dobj,	plural subj or obj
	number, animacy,	human/animal subj or obj
	definiteness	thing subj or obj

Table 5 :

 5 Classification accuracy for LVF readings, with complete feature set and selected in feature selection process.

	Algorithm	complete selected
	trees.j48	61.80	63.00
	rules.jrip	63.89	61.56
	lazy.kstar	62.89	67.47
	functions.libsvm	62.72	61.13
	bayes.naivebayes	60.22	65.80
	baseline	48.37	48.37

Table 6 :

 6 Aspectual indicators tor 'v' in Table

	v. var > 1 telicity value for same lemma?
	m. maj Telicity value of majority
	t.	tel	Any telic reading?
	a. ate Any atelic reading?
		(a) Nominal and binary aspectual indicators
	1. %tel	Proportion of telic readings
	2. %ate	Proportion of atelic readings
	3. %var	Proportion of flexible readings
	4. probest.max Max of probability estimates
	5. probest.min Min of probability estimates
	6. probest.avg Average of probability estimates
			(b) Numeric aspectual indicators.

Table 7 :

 7 The data used in these experiments are the French Aspectual indicators computed from predictions and from manual annotations. Indicators in bold face are computed based on manual annotations. The names of the indicators refer to the labels used in Table6.

	lemma	m t a	%tel %ate %var
	casser	TEL 1 0 95.00	0 0.05
	'break'	TEL 1 1 95.65	4.35	0
	mourir	TEL 1 1 75.00 25.00	0
	'die'	TEL 1 1 75.00 25.00	0
	remplir	TEL 1 1 70.00 30.00	0
	'fill'	TEL 1 1 80.00 20.00	0
		(a) Mostly telic
	lemma	m t a	%tel %ate %var
	regarder ATE 0 1	0 91.67	8.33
	'look at' ATE 1 1 16.67 83.33	0
	chanter	ATE 0 1	0 66.67 33.33
	'sing'	ATE 0 1	0 66.67 33.33
	étudier	ATE 1 1 30.00 60.00 10.00
	'study'	ATE 1 1 20.00 80.00	0
		(b) Mostly atelic
	lemma	m t a	%tel %ate %var
	vieillir	VAR 0 1	0 11.11 88.89
	'get older'	VAR 0 1	0 22.22 77.78
	embellir VAR 0 1	0 33.33 66.67
	'beautify' VAR 1 0 33.33	0 66.67
	élargir	VAR 1 1 25.00 25.00 50.00
	'widen'	VAR 1 1 25.00 25.00 50.00
		(c) Mostly variable

Table 8 :

 8 Event instances for TempEval tasks A, B and C for French and Portuguese (left) and corresponding verbs and readings in LVF (right).

		FTiB	PTiB			LVF
		tlinks rel. types tlinks lemmas(seen) readings
	A	302	10 1659		164(16)	1597
	B	264	5 2887		149(14)	1329
	C 1172	15 1993		427(40)	3827
		Attribute		A	B	C
		event-aspect		×
		event-polarity	×
		event-pos		×
		event-class
		event-tense		×	×	×
		event-mood *	×
		event-vform *	×
		order-adjacent	× N/A N/A
		order-event-first	× N/A N/A
		order-event-between		N/A N/A
		order-timex-between × N/A N/A
		timex-mod		×	×	N/A
		timex-type			×	N/A
		tlink-relType		class

Table 9 :

 9 Features used in the base system for TempEval tasks A, B and C. Features checked ( ) were selected in the feature selection process.

Table 10 :

 10 Accuracy of classifiers obtained on FTiB with base and enhanced feature sets. Values for the base classifiers are in italics. In bold face improvements of an enhanced classifier, no values represent no improvement. Superscripts give the aspectual indicator used to enhance the base feature set and obtain the improved result. They refer to rows in Table6.

	Classifier	A	B	C
	trees.j48	0.71	0.81	0.40
		0.73 1 0.82 3 0.41 a
	rules.jrip	0.71	0.83	0.36
		0.73 6 0.84 6 0.37 m
	lazy.kstar	0.72	0.82	0.42
			0.85 5
	functions.libsvm 0.74	0.83	0.40
			0.85 6
	bayes.naivebayes 0.73	0.84	0.40
	baseline	0.72	0.62	0.29

Type-based classification selects a dominant sense for any given verb and then always assigns it for each reading of this verb.

The paper version is available online at http: //talep.lif.univ-mrs.fr/FondamenTAL/. Online access and electronic versions in XML are available at http://rali.iro.umontreal.ca/rali/ ?q=fr/lvf.

Interestingly, the average number of 15 readings per verb very closely matches the number of event categories per verb obtained in the experiment reported by[START_REF] Marvel | Event categorization beyond verb senses[END_REF], who propose a new method of automatically categorising event descriptions.

The for-adverbial is nevertheless compatible with rem-plir09, but only under its (non-partitive) 'result state-related interpretation', under which it scopes on the result state, cf.[START_REF] Piñón | Durative adverbials for result states[END_REF]; see e.g. This news filled Peter with joy for ten minutes.

Relevant features are sometimes coded in an indirect way. For instance, the difference between verbs like donner x à y 'give x to y', that subcategorise the indirect object, and verbs like dire x à y 'say x to y', that do not, is retrievable through the difference in the associated syntactic frames.

On this respect, note that the semantic decomposition of élargir02, which involves BECOME, shows the limits of the analysis provided by the LVF: Under the 'spatial' use of which élargir02 is an instance, degree achievements do not describe events in which an individual undergoes change over time (see[START_REF] Deo | From change to value difference[END_REF]).

The features used by[START_REF] Friedrich | Automatic prediction of aspectual class of verbs in context[END_REF] are mainly derived from those of[START_REF] Siegel | Learning methods to combine linguistic indicators: Improving aspectual classification and revealing linguistic insights[END_REF].

Assigning a value to the type level was necessary to test our predictions on the TempEval corpus, since aligning each utterance of this corpus with a specific LVF-reading is not feasible.

Indicators derived from the probability estimates are not computable from the manual annotations.

This corresponds to 1/4 of the English TimeBank.

Task A is about temporal relations between an event and a time, task B focuses on relations between events and the document's creation time, and task C is concerned with relations between two events.

We only show improvements of at least 1%, and only show the largest gains in performance.

Acknowledgments

This research was funded by the German Science Foundation, SFB 732 Incremental specification in context, Project B5 Polysemy in a Conceptual System. For feedback and discussions, we thank Achim Stein and the reviewers of *Sem 2016.


Romaric Breil
email: breil@recherche.enac.fr

Daniel Delahaye

Laurent Lapasset

Éric Féron

Multi-agent Systems for Air Traffic Conflicts Resolution by Local Speed Regulation and Departure Delay

Keywords: Air traffic management, multi-agent system, conflict resolution, speed regulation, departure delay

Air Traffic Flow Management (ATFM) aims at structuring traffic in order to reduce congestion in airspace. Congestion being linked to aircraft located at the same position at the same time, ATFM organizes traffic in the spatial dimension (e.g. route network) and/or in the time dimension (sequencing and merging in TMA, Miles-in-Trail for en-route airspace).

The objective of this paper is to develop a methodology that allows the traffic to self-organize in the time dimension when demand is high. This structure disappears when the demand diminishes.

In order to reach this goal, a multi-agent system has been developed. In this system, aircraft agents regulate speed and delay departure time in order to reduce the number of conflicts, thus decreases overall traffic complexity, which becomes easier to manage by air traffic controllers. This algorithm was applied on realistic examples.

I. Introduction

Air traffic volume has been constantly increasing during the past decades, and ICAO [START_REF]to 2030 and Trends to 2040[END_REF] predicts that the annual number of flights will double in 2030 in comparison to 2013. Air traffic controllers are in charge of ensuring traffic safety and fluidity by temporarily diverting flights from their original trajectory when necessary. In doing so, a minimum separation distance is maintained between all aircraft. This task is known as conflict detection and resolution. It is increasingly perceived that the present centralized way of managing traffic cannot scale up anymore. In order to deal with traffic growth, major research programs around the world, such as SESAR (Single European Sky ATM Research) and NextGen (US Next Generation Air Transportation System) consider automating some tasks previously done by controllers, allowing them to manage more flights simultaneously. In a more daring effort, decentralized flow management, whereby traffic flow management is delegated to individual aircraft, is also an option.

A. Air Traffic Management

The current air traffic system is structured [START_REF] Isaacson | Tactical scheduling for precision air traffic operations: Past research and current problems[END_REF] on a route network whose vertices are geographical positions called waypoints, through which an aircraft shall go. Each waypoint is identified by a name. Edges of the route network define the set of routes that can be followed by aircraft. Before departure, the pilot or the airline dispatcher is to submit a flight plan to the civil aviation authority, containing information related to the flight (route, departure and arrival airports, etc.). This flight route is defined by a set of waypoints identified by their names. Once airborne, however, modifications to the flight plan may be initiated by the flight crew or air traffic control, depending on local traffic and weather conditions.

The airspace of every country is usually divided into several sectors. Each sector is managed by a team of air traffic controllers in charge of planning trajectories, managing collision avoidance, and communicating with aircraft. Controllers can only take charge of a limited number of flights simultaneously. Sectors and route networks are designed in such a way that controllers' workload is reduced; they have only a limited number of flights to manage simultaneously in their sectors, each of them following a predefined route. They have to keep separation distances between each pair of aircraft above given threshold values: during cruise, a conflict occurs when two aircraft are separated by less than 5 nautical miles horizontally (5 NM = 9.26 km) and 1,000 feet vertically (1,000 ft = 304.8 m). When a conflict between two aircraft is foreseen, the controller requests that one or both pilots execute a maneuver, usually temporarily changing the heading or altitude to increase separation, before returning to initial flight path.

The air traffic is constantly increasing and the current air traffic structure is reaching its maximum capacity. To cope with this situation, parts of the control process could be delegated to automatic algorithms, like conflict detection and resolution or other traffic management tasks.

Aircraft are increasingly capable of communicating full estimated 4D trajectories over the next minutes by means of messages. These data can be transmitted by using Automatic Dependent Surveillance -Contract (ADS-C) [3, 2.2.6]. These messages are exchanged following a request-answer protocol. Usually, a ground station sends a request to a specific aircraft, which sends back a data frame containing aircraft identifier, position, speed and the predicted route composed of a set of 4D positions (3D + time). Information carried by ADS-C is more accurate than radar positioning since an aircraft uses GPS to get its position. Ground stations receiving these messages are able to provide controllers with accurate representation of air traffic. This is well adapted to airspace where radar coverage is not available (e.g. oceanic airspace).

Free flight is an air traffic management concept developed in the U.S. that enables aircraft to choose their path in low traffic zones with more freedom, by ignoring route networks. The implementation is currently studied by the NextGen research program. In Europe a similar concept was developed by the SESAR project; the Free Route Airspace is already deployed in some areas. These zones are managed or not by air traffic controllers. In the second alternative, automatic separation assurance systems would benefit from aircraft information exchange systems.

B. Conflicts Detection and Resolution Algorithms

Many studies have already been performed to design automatic conflicts resolution methods. Some are referenced in [START_REF] Kuchar | A review of conflict detection and resolution modeling methods[END_REF]. Most of those methods try to reproduce the way controllers regulate traffic by changing aircraft heading for a short period. According to air traffic controllers, those algorithms can interfere with their own decisions since the controllers and the algorithms take the same kind of decision in the same controlled areas and within the same time horizon [START_REF] Villiers | Automatisation du contrôle de la circulation aérienne: "ERASMUS", une voie conviviale pour franchir le mur de la capacité[END_REF].

In 2004, a new way to solve this problem was proposed as a part of the project ERASMUS (En Route Air traffic Soft Management Ultimate System). According to Villiers [START_REF] Villiers | Automatisation du contrôle de la circulation aérienne: "ERASMUS", une voie conviviale pour franchir le mur de la capacité[END_REF], instead of trying to reproduce what controllers are doing, those algorithms should help them by removing a part of the conflicts before they appear by slightly changing aircraft speed, for instance. This type of automated system organizes traffic in order to create a favorable traffic situation, more easily managed by controllers. Moreover, this algorithm does not interfere with controllers' decision process, since controllers mainly manage traffic in space dimensions by modifying aircraft heading, and the algorithm manage traffic in time dimension by regulating aircraft speed. This concept was validated with experiments [START_REF] Bonini | How ERASMUS can support an increase in capacity in 2020[END_REF] and human factors studies [START_REF] Chaloulos | A simulation based study of subliminal control for air traffic management[END_REF]. The speed regulation method was implemented as a genetic algorithm [START_REF] Bonini | How ERASMUS can support an increase in capacity in 2020[END_REF].

Since problems encountered in Air Traffic Management (ATM) are highly combinatorial, deterministic optimization methods tend to become inefficient when dealing with real traffic scenarios (involving hundreds or even thousands of aircraft). To overcome this situation, heuristics have been used in several research works, giving satisfactory results over a time horizon compatible with operational constraints [START_REF] Delahaye | Genetic algorithms for Air Traffic Control systems[END_REF].

Multi-agent systems can be used to develop heuristic algorithms, and have already been applied to air traffic management problems. Some studies focus on traffic regulation in free flight (or Free Route) zones. Aircraft flying in free flight areas must automatically be able to find conflict-free trajectories, respecting the required distance separation between aircraft. This problem can be solved using multi-agent systems, such as the one developed by Wollkind, Valasek and Ioerger [START_REF] Wollkind | Automated conflict resolution for air traffic management using cooperative multiagent negotiation[END_REF], or the one developed by Sislak, Volf and Pechoucek [START_REF] Sislak | Agent-based cooperative decentralized airplane-collision avoidance[END_REF]. Those algorithms solve conflicts using maneuvers such as heading and flight level changes. However, and as shown by Villiers, this regulation method can interfere with controllers' decision process.

The algorithm described in this paper aims at implementing the traffic regulation method of the project ERASMUS as a multi-agent system. As detailed in Section I-C, this type of algorithm has several advantages compared to global optimization methods used in ERASMUS.

C. Multi-Agent Systems

Multi-agent systems have been used to solve many problems in operations research, like regulation of urban transportation networks [START_REF] Balbo | An agent oriented approach to transportation regulation support systems[END_REF], design of mechanical systems [START_REF] Capera | Self-organizing agents for mechanical design[END_REF], or pathfinding problems [START_REF] Dorigo | Ant colony optimization[END_REF]. This paradigm is often regarded as a kind of distributed artificial intelligence. Multi-agent systems are made of autonomous agents interacting among themselves and with their environment [START_REF] Ferber | Multi-agent systems: an introduction to distributed artificial intelligence[END_REF]. Usually, agents have a limited perception of environment and they partially know the internal state of their neighbors, via message exchanges. Their behavior can either be simple (whereby reactive agents are only influenced by environmental changes) or complex (whereby cognitive agents try to fulfill an objective).

Self-organization is a key aspect of multi-agent systems. Self-organization means that the system organization is not predefined, but emerges from interactions between agents, and gives a complex behavior to the overall system. If the rules that direct agents are carefully chosen, such a complex behavior can emerge at the system level from local interactions and behavior of agents. When multi-agent systems are used to solve operations research problems, a carefully chosen set of agent behaviors can help to find an overall solution to the problem (system level) by only using local rules (agents level).

Multi-agent systems can be implemented either within a computer simulation, or as a physical system that is composed of robots that are able to communicate and to interact among each other and with their environment. When agents are implemented within a computer simulation, computations of agents can be done in parallel, exploiting modern hardware architectures (multi-core processors, computations on graphic card). A multi-agent system can also run on a cluster of computers.

Those systems have several advantages compared to centralized decision algorithms. When correctly designed, they exhibit a good resilience when facing disruptive events [START_REF] Rieger | Resilient control systems: A multi-agent dynamic systems perspective[END_REF].

Agents try to fulfill a goal and act in order to become closer to this objective. When they are confronted to local perturbations in their environment, they adapt their actions to take those changes into account, enabling the system to return to a new stable state. Since decisions are decentralized at agents level, the failure of an agent will not impact the whole system. Computer experiments indicate that, in general, when decisions are decentralized, a central regulation entity failure may prevent the system to work. In the field of information technologies, such a central point would be defined as a Single Point of Failure (SPOF).

D. Implementation of a Conflict Resolution Multi-agent System

Applied to air traffic management, the implementation of new onboard collaborative decision processes can be done progressively, whereby equipped aircraft cooperate among themselves and are given more freedom in their decisions than non-equipped aircraft (for example by constraining the latter to follow rigid corridors).

Even if current technology like ADS-C does not allow aircraft to really exchange data about trajectories directly from aircraft to aircraft, these data can be collected by ground stations. Traffic regulation algorithms like the one described in this article can then compute speed changes, which can then be sent back to aircraft. The distributed aspect of a multiagent approach to the management of traffic is somewhat diminished since aircraft do not take decisions themselves. Yet, other advantages are preserved, like resilience and general performances.

This article describes a conflict resolution algorithm based on aircraft speed self-regulation. This implementation of the ERASMUS concept benefits from the use of multi-agent systems. Expected benefits include resilience to disruptive events like non-cooperative aircraft, and the ability to delegate the decision process onboard, supposing that aircraft will be able to exchange trajectory data among themselves. Section II details the algorithm. Section III describes a scenario based on actual traffic aiming at validating expected assets of this algorithm.

II. Aircraft Speed and Delay Self-Regulation for Conflict Resolution

A. Hypotheses

The algorithm described in this section regulates aircraft in cruise phase. Their altitude is supposed to be constant. Aircraft flying at different altitudes do not interact; they are never in conflict, and they ignore each other during the decision process.

Each flight has a preferred cruise speed depending on general aircraft performances and airlines preferences. Airlines can give priority to reducing fuel cost by reducing aircraft speed, or to the reduction of crew costs by increasing speed, which also increases fuel consumption. This setting is adjusted by using a value called Cost Index (CI), which is the ratio of Figure 1. In the algorithm described in Section II, a trajectory is a curve composed of segments (constant speed in gray, acceleration in green) and of arcs of circles (in dark yellow). Aircraft flies from a waypoint to another (triangles).

the cost of flight time (including crew costs) to the cost of fuel.

Let v be the current speed of an aircraft and v opt its optimal speed. In order to be inserted into a route network, aircraft may have to choose a speed v different from v opt within a given interval. A lower bound v min = v opt -6% allows a human or an algorithm to insert this aircraft into a flow without dramatically increasing fuel consumption [START_REF] Delgado | Fuel consumption assessment for speed variation concepts during the cruise phase[END_REF]. A speed interval of [v opt -6%, v opt + 3%] is a common choice for speed regulation in en route airspace [START_REF] Averty | Could ERASMUS speed adjustments be identifiable by air traffic controllers?[END_REF].

Aircraft acceleration and deceleration are fixed to ±4,000 NM/h 2 (±0.572 m/s 2 ) for all aircraft. The standard turn rate [18, PCG S-6] of 3°/s is used so that a complete 360°t urn is completed in 2 minutes.

In a general traffic situation or in free route scenarios, some conflicts cannot be solved by using speed control only, as in head-on encounters, for instance. The aim of this algorithm is to simplify the traffic by doing subliminal speed changes in order to help controllers. The speed regulation algorithm reduces the number of conflicts and delegates the remaining ones to air traffic controllers.

Thus, these conflicts need additional maneuvers to be solved. In this algorithm, aircraft are also able to delay departure time up to 10 minutes, in order to remove the remaining conflicts.

B. Algorithm

In this multi-agent system, aircraft are agents exchanging ADS-C messages containing estimated 4D trajectories. A trajectory is stored and exchanged as a sequence of arcs that can be straight segments (aircraft flying at a constant speed, accelerating, or decelerating) or arcs of circles (aircraft turning), as shown in Fig. 1. This curve is differentiable at least once everywhere.

This curve is built from a flight plan defined by a set of waypoints. Flight plan execution is as follows: an aircraft has to fly above each waypoint (Fig. 1). After an aircraft reaches a waypoint, it turns in order to head towards the next one. Speed changes are planed at given times (Section II-B2), and can occur only during the execution of straight trajectory segments.

In our model an aircraft cannot accelerate and turn at the same time. Thus, all turns can be represented by arcs of circles, enabling the computation of conflicts (Section II-B1a) with a simpler analytic method than if aircraft could accelerate during turns. Furthermore, flight plans are designed to minimize flown distance. Heading changes are usually small, and turns rarely last more than on the order of tens of seconds. Thus, postponing speed changes after turns has little or no influence on the decision process.

The multi-agent system (Fig. 2) is timed by a global clock. Each tick corresponds to one second in the simulation. All agents are synchronized: at the end of an iteration, agents drop off messages into the mailbox. When the next iteration begins, those messages are delivered to addressee agents. Therefore, even if agents processes are run asynchronously, agents work logically in parallel. This choice helps the overall system to avoid problems related to sequence order. For performance reasons, agents are run in parallel, using multiple threads.

During the lifecycle of an agent, a sequence of three steps is repeated at every iteration of the multi-agent system until the agent is removed. The perception step allows agents to receive ADS-C messages and refresh their internal representation of the airspace. During the decision step, aircraft plan speed changes on the basis of this internal representation. In the action step, agents update their position using updated speed, and broadcast an ADS-C message. Aircraft lifecycle steps are detailed below.

1) Perception: Each aircraft agent first receives messages from its neighbors, from which it extracts 4D trajectories. In order to detect conflicts, the aircraft then samples other aircraft trajectories to get their predicted position every 10 seconds during 20 minutes (Fig. 3).

a) Conflict Detection: This algorithm aims only to regulate aircraft trajectories in time dimension. The space and time dimension are handled separately by the algorithm. The spatial dimensions of a trajectory are the dimensions of the geometric space spanned by the trajectory in 3D. Altitude of a trajectory is supposed to be constant, and aircraft vertically separated will not be considered in conflict. The temporal dimension is defined by aircraft speeds at each instant. The algorithm regulates only the time dimension. The internal representation of an aircraft trajectory is the distance flown by the aircraft as a function of the time, and can be represented as a curve in a 2D space, as in Fig. 4.

In order to compute speed changes, conflicts have to be represented in a form understandable by the decision process. Conflicts are also projected into the 2D space where the aircraft trajectory is already projected (Fig. 4).

A conflict occurs when the distance between two aircraft flying at the same altitude becomes smaller than 5 NM on a horizontal level. When an aircraft follows a path, its future positions are defined by its own current position and by its speed changes. Since speed is to be chosen during the decision phase, all potential conflicts with the aircraft's neighbors need to be detected, regardless of its own speed. Then, for each intruder predicted position, the algorithm searches for possible intersections between its own path and a circle of 5 NM centered on the intruder predicted position (Fig. 3). Thus, whatever speed changes the aircraft will choose, it will always manage to detect conflicts.

b) Internal Representation of Own Trajectory: Since an aircraft strictly follows a fixed geometrical path, the decision process only modifies speed. As previously mentioned, to manipulate a trajectory defined by a 4D curve is not necessary: this 4D trajectory can be simplified by using the traveled distance over the route as a function of time, by integrating the instantaneous speed over time. In other words, the aircraft trajectory can be represented as a 2D curve defined by the arc length as a function of time. This curve is then projected into a 2D space (Fig. 4).

Conflicts detected during the conflict detection step (Section II-B1a) are also projected in this space. Each potential intrusion extracted from the sampled neighbor's trajectory is projected according to its position along the path (Fig. 3). The portion of the path intersecting with the circle of 5 NM cen- For each time step, 3 choices are tested: to accelerate (green), to cruise (gray), to decelerate (blue). The choice leading to the longest conflict-free trajectory is applied. In this case, it accelerates two times at the beginning, then it cruises.

tered on the intruder's position gives an interval of positions forbidden to the agent (Fig. 4). An example of this process is shown in Fig. 3 and4. In Fig. 3, conflicts are symbolized by red segments representing intersection of 5 NM-radius circles centered on intruder aircraft and of the spatial components of aircraft's own trajectory. In Fig. 4, these red segments are projected in the 2D internal representation of the trajectory.

2) Decision: Decisions are updated every 8 seconds. The instant of the first decision is randomly chosen within the first 8 seconds of agent's lifetime. It means that between two executions of the same traffic scenario, aircraft will take decisions in a different order, and decisions of the first aircraft has an influence over decision of the next ones.

Using conflicts projected in the 2D representation (displayed in Fig. 4), aircraft can plan speed changes. The goal is to avoid conflicts by way of speed changes. This goal is achieved by exploring a decision tree where for each time sample, the aircraft can maintain its speed, accelerate or decelerate.

A time step of 5 seconds was chosen. Aircraft acceleration rate is ±4,000 NM/h, or ±1.11 NM/s (Section II-A). An aircraft whose optimal speed v opt is 447 kt has an admissible d (NM) t (s) 0 10 0 40 Figure 6. The conflict is unsolvable because of the objective function that tries to maximize the delay before the first conflict; in the first time sample, all the possible choices (to accelerate, to cruise or to decelerate) lead to a conflict at t = 20 s. In this case, the aircraft chooses to cruise, which leads to a severe conflict lasting 40 seconds. An alternative objective function that minimizes the duration of a conflict can choose to decelerate three times in order to cause a less severe conflict lasting only 10 s (dashed segments).

speed range of [420 kt, 460 kt], so it takes 36 seconds to accelerate from its minimum to its maximum speed. Aircraft accelerate constantly between two time steps. Thus, a time step of 5 seconds means that aircraft can choose 7 different speeds. Experiments (Section III) shown that it is sufficient to solve all the conflicts. For each time sample, three choices are tested: cruise, acceleration or deceleration at the maximum rate (Fig. 5). Then at each time step and for each possible decision, the time of the first conflict is computed. The problem is solved using a greedy algorithm that locally maximizes the time of the first conflict.

A pseudo-code describing the decision-making process of each aircraft is presented in Appendix A. In this process, the set of decisions D is iteratively constructed. For each time step, acceleration (acc), deceleration (dec) and cruise (cr) choices are tested: the time when the first conflict occurs is stored in the variable cflTime. Then, the algorithm looks for the decision leading to the latest conflict date. If speed constraints are respected (checked by the function isValid()), this decision is accepted.

Using a greedy algorithm makes possible to get good results (Section III) after a short period of computation. Yet, since a greedy algorithm is only a local optimization process, it may find a local optimum and be unable to find a conflict-free solution, even if one exists as shown in Fig. 6. Therefore, some conflicts cannot be solved. The choice of this method is a compromise between the computation time and the quality of the results.

Results given by the greedy algorithm can nonetheless be refined by the addition of intermediate decisions at each time step (e.g. accelerations and decelerations of ±2,000 NM/h 2 and ±4,000 NM/h 2 ), but at the cost of longer computation times.

3) Action: In the action step, the set of decisions D computed by the algorithm of Section II-B2 is used to generate the new 4D trajectory, which is communicated to neighbors using an ADS-C message. 4) Delay of departure time: Aircraft are generated 10 minutes before departure. They immediately start to send ADS-C messages containing their 4D trajectory. This behavior allows aircraft to plan speed changes before actually appearing in the simulation. It also enables aircraft already in flight to anticipate their presence enroute.

An additional action is possible by delaying departure times. Aircraft can delay their departure time up to 10 minutes. As in the pseudo-code in Appendix B, agents call iteratively the speed regulation method described in Section II-B2 and in Appendix A with increasing delay values. The aim of this function is to maximize the date of the first conflict that cannot be solved by the speed regulation algorithm. Aircraft can adjust departure delay during the decision step (Section II-B2) until the departure time. The latest allowed departure time is 10 minutes after the departure time initially set in the flight plan.

Delay values start from 0 to 10 min. In order to reduce the number of iterations, the time step ∆t is set to 1 s when delay is lower than 15 s, ∆t is set to 5 s when delay is lower than 3 min, otherwise ∆t is set to 10 s. The tested delays are then {0, 1, 2, . . . , 14, 15, 20, . . . , 175, 180, 190, . . . , 600}. Then, the algorithm iterates 90 times instead of 600 times if the time step was fixed to 1 s from 0 to 10 min. The process stops if a conflict-free solution is found.

Since all agents apply the same decision process iteratively, numerical experiments indicate that the system converges to a stable state in which conflicts are solved. When aircraft follow the same route, they fly at similar speeds in order to avoid conflicts. When they follow intersecting routes, the separation distance between aircraft of each route becomes similar in order to allow them to cross alternatively the intersection point. The Figure 7 shows an example of two perpendicular flows of aircraft. In order to maintain a minimum distance of 5 NM, aircraft of each flow have to be separated by:

2 • 5 √ 2 = 14.14 NM (1)
and cross the intersection alternately.

In order to validate the algorithm, various traffic scenarios were tested. A description of the scenarios and some results can be found in Section III.

III. Test Scenarios Based on Actual Flight Plans

In order to validate the algorithm, different scenarios based on actual traffic were tested. Scenarios are based on flight plans of aircraft flying over France during 10 hours (from 4 AM to 2 PM), as shown in Fig. 8. Only the flights at 37,000 ft, one of the most densely occupied altitude, have been analyzed. 283 aircraft fly at this altitude in this scenario.

Three sets of scenarios were tested (Section III-A). In the first set, aircraft regulate speed but do not change departure time. In the second set of scenarios, aircraft can delay departure time up to ten minutes, but do not regulate speed and fly at their optimal speed. In the third set, aircraft regulate departure delay and speed.

In order to test resilience of the algorithm to disruptive events, for each set of scenarios, the decision process was disabled for a given subset of aircraft (Section III-B). Percentages of non-cooperative aircraft were chosen to be 10 %, 20 %, 50 % and 80 %.

During simulations, the distances between all pairs of aircraft were monitored. Each time aircraft were separated by less than 5 NM, a conflict was registered (a single record for the duration of the conflict).

Each scenario was run 10 times. The number of conflicts was recorded (Fig. 9 and 11), as well as the number of accelerations (Fig. 12) and the delay (Fig. 13) chosen by every cooperative aircraft.

Results vary between runs of the same scenario. In Fig. 9, the minimum and maximum measured number of conflicts are indicated alongside the average number. These variations have two origins. Firstly, aircraft update their decisions every 8 seconds, but the instant of the first decision is randomly chosen within the first seconds of agents' lifetime. It means that from one run to the other, aircraft will take decisions in a different order, and decisions of the first aircraft has an influence over decision of the next ones. Secondly, in scenarios with non-cooperative aircraft, these aircraft are randomly cho- Each scenario was run 10 times; the minimum, average and maximum number of conflicts was measured.

Figure 10. When aircraft cannot delay their departure time, they are sometimes starting at too close positions and speed regulation is not sufficient to solve these conflicts.

sen within the set of agents for each simulation run. An aircraft can cooperate in a run and be non-cooperative in another one.

The influence of an aircraft on the overall traffic can vary, depending for instance if its trajectory crosses congested areas or not.

In order to provide a baseline, a first simulation was run in which decision process was disabled for all aircraft. This scenario generated 47 conflicts. In Section III-A we will discuss the algorithm's ability to reduce conflicts when aircraft cooperate against the baseline. In Section III-B we will discuss the algorithm resilience when confronted to disrupted events.

A. 100 % of Cooperative Aircraft

In this section, we discuss the algorithm's ability to reduce conflicts when all aircraft cooperate. In the first set of scenarios, aircraft only regulate speed. As shown in Fig. 9, when all aircraft cooperate, 24.9 of the 47 initial conflicts are solved on average (-53 %). Solving conflicts requires that each aircraft accelerate 7.2 times on average, for an accumulated acceleration duration of 35.9 seconds (Fig. 12).

22.1 conflicts are not solvable by the speed regulation algorithm alone. As shown in Fig. 10, some aircraft start from positions that lead to an unsolvable conflict. Furthermore, speed regulation alone cannot solve face-to-face conflicts.

In the second set of scenarios, aircraft do not regulate speed, but they are able to delay departure time up to 10 minutes. This strategy allows the system to remove conflicts that cannot be solved by speed regulation only, such as the conflict depicted in Fig. 10. The number of conflicts is then much lower than for the previous set of scenarios, with only 4 unsolved conflicts on average (-91.5 %). Aircraft delay their departure by 13.3 seconds on average, as displayed in Fig. 13.

In the last set of scenarios, aircraft can regulate speed and departure time. This is the most favorable situation, since the degree of decision freedom is the greatest. Aircraft can solve conflicts such as the one shown in Fig. 10. When all aircraft cooperate, between 0 and 2 conflict remain, with an average of 0.6 unsolved conflicts.

Aircraft are able to solve conflicts with 5.8 speed changes on average, for an accumulated acceleration duration of 28.9 seconds. Comparing with the first set of scenarios (aircraft regulate speed only), allowing aircraft to delay departure helps them to slightly reduce the number of speed changes needed to solve conflicts. The average delay is also reduced by 56.6 % compared to the second set of scenarios (aircraft only delay departure time); when all aircraft are cooperative, the average delays decreases from 13.3 seconds to 5.8 seconds.

B. Resilience

In order to validate the algorithm's resilience, for each of the three sets of scenarios (speed regulation only, departure delay only, speed and delay regulation enabled), 4 additional scenarios were tested with different percentages of non-cooperative aircraft. In these scenarios, the ability to make decisions was removed for 10, 20, 50 and 80 % of agents. The cooperative aircraft consider the non-cooperative ones as constraints on their decision process, and solve conflicts if admissible delay and speed interval allow them to do so. In these simulations, resilience was analyzed at three different levels. At the level of all agents, resilience is related to air traffic controllers' workload. At the level of cooperative agents, resilience is related to overall performances of the algorithm. And at the level of a single agent, resilience is related to the quality of aircraft decisions.

1) Resilience at the Level of All Agents: Air traffic controllers' workload is partially related to the complexity of a traffic situation. A part of this complexity comes from the number of conflicts controllers have to solve. Fig. 9 displays the total number of conflicts that could not be solved by the algorithm as a function of the number of non-cooperative aircraft. These residual conflicts must be solved by controllers, and have an influence over traffic complexity. Then, values displayed in Fig. 9 gives a trend of the perceived complexity as a function of the ratio of non-cooperative aircraft. When 20 % of aircraft do not cooperate, the number of conflicts increases by about 10 % with respect to when all aircraft cooperate. In the first set of scenarios (only speed regulation), the number of conflicts increases by 8.5 %, from 22.1 to 26.1 conflicts over the 47 initial ones. In the second set (only departure delays allowed), the number of conflicts increases by 12.6 %, from 4 to 9.9 conflicts compared with the initial number of conflicts. In the last set (delay and speed regulation), the number of conflicts increases by 8.9 %, from 0.6 to 4.8 conflicts compared to the 47 initial ones. Disabling the decision-making ability for 20 % of aircraft increases the number of conflicts only by 10 % on average in comparison to when all aircraft cooperate. This value indicates that the increase of controllers' workload caused by the number of conflicts will be limited if some aircraft do not cooperate.

2) Resilience at the Level of Cooperative Agents: The number of conflicts increases with the number of non-cooperative aircraft. These additional conflicts can be categorized in two groups: conflicts between two non-cooperative aircraft, and conflicts involving at least one cooperative aircraft. The first group has to be taken into account in order to monitor overall performances of the system, but does not provide much information about performances of the decision process. These conflicts cannot be solved, and their number tends to 47 as the ratio of cooperative aircraft tends to 0.

The number of conflicts involving at least one cooperative aircraft provides more information about the algorithm performances, because these conflicts can be solved by the decision process. As shown in Fig. 11, the number of conflicts belonging to this category slightly increases with the number of non-cooperative aircraft, by 5.4 % on average while 20 % of aircraft do not cooperate. In the scenario where only speed is regulated, the number of conflicts increases by 3.6 %, from 22.1 to 23.8 conflicts over the 47 initial ones. In the scenario where only delay is applied, conflicts increase by 7.4 %, from 4 to 7.5 conflicts. When speed regulation and delay are applied, the number of conflicts increase by 5.1 %, from 0.6 to 3 conflicts.

In other words, half of the conflicts appearing while 20 % of aircraft do not cooperate are caused only by non-cooperative aircraft. When one fifth of aircraft do not contribute to conflicts resolution, the number of conflicts remains stable with an increase of 5.4 % of conflicts compared to when all aircraft cooperate. This value indicates that the algorithm is resilient to disruptive events such as one aircraft being, or becoming, non cooperative.

3) Resilience at the Level of a Single Agent: At the level of individual agents, the number of speed changes and average delay chosen by each aircraft was also monitored for each scenario. The average values in function of the ratio of noncooperative aircraft are shown in Fig. 12 and Fig. 13. The average number of accelerations is stable as the number of non-cooperative aircraft increases, and is bounded between 5.8 and 8.8 speed changes for all scenarios.

Delay slightly increases with the number of non-cooperative aircraft. The maximum delay increase is 3.8 seconds while the number of non-cooperative aircraft increases from 0 to 80 %, increasing from 5.7 s to 9.6 s when delay and speed regulation are applied by aircraft.

The average number of speed changes and delay before departure are stable while the number of non-cooperative aircraft increases. This indicates that the aircraft decision process is resilient against an important number of non-cooperative aircraft.

In conclusion, the multi-agent system is resilient at three different scales. At system level, the limited increase of the number of conflicts means a limited increase of air traffic controllers' workload if some aircraft do not cooperate to solve conflicts. If conflicts involving only non-cooperative aircraft are ignored, increase of the number of conflicts is limited, indicating resilience of the algorithm. Finally, the number of accelerations and the average delay remain stable, indicating resilience at the level of individual agents.

IV. Conclusion

The algorithm described in this article has several advantages related to the usage of multi-agent systems. It is able to solve up to 100 % of the conflicts in the tested scenario, is resilient to perturbations like non-cooperative agents, and could eventually be implemented on board, removing the need to rely on ground equipment. Speed regulation alone is not able to solve all conflicts, and is not meant to do so. The algorithm described in this article is designed to assist air traffic controllers, and not to replace them. To successfully solve all conflicts, aircraft have to execute other types of maneuvers in addition to speed regulation, like delay of the departure time, flight level changes or heading changes. Allowing aircraft to delay departure time helps the algorithm to remove all the remaining conflicts. Nowadays, these decisions are taken by air traffic controllers and are not planned to be delegated to algorithms in humancontrolled airspace.

Our next research will aim at implementing a global optimization method to solve the problem described in this article. It will allow to measure the difference in terms of computation time and result optimality between results returned by this multi-agent system and by a global optimization method, often used to solve similar problems.

Thanks to the ability of multi-agent systems to integrate non-cooperative agents and to recover from disruptive events, they offer a good framework to mix human-controlled traffic with an automated one. Eventually, these algorithms could then collaborate with humans in air traffic management applications, because they work over different scales, time-wise for the algorithm and space-wise for humans.

Figure 2 .

 2 Figure 2. Multi-agent system lifecycle.

Figure 3 .

 3 Figure3. The black aircraft detects potential conflict with the gray aircraft for each time sample in the next minutes. A potential conflict is the intersection between a circle of 5 NM centered on the gray aircraft and path of the black aircraft (red segments).

Figure 4 .Figure 5 .

 45 Figure 4. Representation of the 2D trajectory of the black aircraft (distance as a function of time) and intrusions of the gray neighbor in the black aircraft's path at each time sample (vertical red segments) of the Fig.3. A conflict will occur if the black aircraft maintains its initial speed: the curve representing the black aircraft's trajectory intersects with the vertical segments that represents potential conflicts.

Figure 7 .

 7 Figure 7. Intersecting flows of aircraft regulated by the multi-agent system. At a perpendicular intersection, if aircraft flying at the same speed are separated by 14.14 NM on each route, and if they alternately cross the intersection, they can keep a minimum distance of 5 NM.

Figure 8 .

 8 Figure 8. Traffic scenario using actual flight plans, described in Section II. This picture displays flight plans of aircraft flying at 12:00.

Figure 9 .

 9 Figure 9. Number of conflicts as a function of the percentage of noncooperative aircraft. Results are given for each set of scenarios: with speed regulation only, with delay regulation only, and with both methods enabled. Each scenario was run 10 times; the minimum, average and maximum number of conflicts was measured.

Figure 11 .

 11 Figure 11. Number of conflicts involving cooperative aircraft as a function of the percentage of non-cooperative aircraft. The number of conflicts is lower than in Fig. 9; conflicts between non-cooperative aircraft are not counted in this plot because they are not significant to study the algorithm performances. Conflicts counted in this Figure imply at least one cooperative aircraft. Results are given for each set of scenarios: with speed regulation only, with delay regulation only, and with both methods enabled.

Figure 12 .Figure 13 .

 1213 Figure 12. Average number of accelerations decided by cooperative aircraft in function of the percentage of non-cooperative aircraft. Results are given with delay regulation enabled and disabled.