Verena Lyding

Lionel Nicolas

Branislav Bédi

Karën Fort

Introducing the European NETwork for Combining Language

Keywords: crowdsourcing, computer assisted language learning, language resources, COST Action. 1

Introduction

EnetCollect was founded as a large European network project through COST Association for four years starting from March 2017. The project tackles the major European challenge to foster the language learning of all citizens with diversified cultural, educational, linguistic and socio-demographic backgrounds by combining the well-established domain of language learning (Godwin-Jones, 2011) with recent crowdsourcing approaches [START_REF] Brabham | Crowdsourcing as a model for problem solving. An introduction and cases[END_REF]. The demand for language learning is continuously increasing due to ongoing globalisation and political happenings, i.e. migration. Also, learner profiles are getting more diversified in terms of the learners' language backgrounds, daily realities and communicative needs. This calls for more adapted learning content to optimally serve the individual learner, and to increase the ecology of learning (Blewitt, 2006). At the same time, the Internet has opened new possibilities for a collaborative development; sharing and reusing content for language learning has never been easier.

Objectives and approach

EnetCollect aims to research and promote the possibilities that crowdsourcing offers for language learning. It can provide a long-term solution to the complex and ever-changing demands on language learning by involving the "crowd" in creating and improving language learning materials.

In CALL, Duolingo (von Ahn, 2013) is an example of a language-learning platform which follows a similar logic as enetCollect, in offering free learning services for numerous languages while crowdsourcing lessons and translations through exercises. EnetCollect distinguishes two forms of crowdsourcing approaches, as follows. Explicit crowdsourcing involves a crowd that intentionally participates in data creation, i.e. by providing language content for teaching and curricula design for specific languages. It is based on the "wisdom-of-the-crowd" approach that enables stakeholders to collaboratively create resources of common interest, as implemented in the language learning platform Memrise, the online dictionaries Dict.cc, Wiktionary and Lingobee (Procter-Legg et al., 2012), and the well-known Wikipedia. Implicit crowdsourcing involves a crowd that is not necessarily aware of its participation. It includes generating exercises and content based on learner's achievements, e.g. Games-with-a-Purpose (GWAPs) [START_REF] Chamberlain | Using games to create language resources: Successes and limitations of the approach[END_REF][START_REF] Lafourcade | Games with a Purpose (GWAPS)[END_REF].

The learners' activities are monitored in terms of difficulties and errors, the efficiency in completing different exercises, and learning analytics. This involves features from intelligent CALL (iCALL) [START_REF] Gamper | A review of intelligent CALL systems[END_REF]. Based on this, enetCollect will explore new opportunities for autonomous and life-long learning, and concentrate on the practical implementation of theories with regard to learning materials that respond not only to the learner's individual pace but also to the content and, as opposed to Duolingo, to the overall curricula design for each language individually.

Structure of the network and implementation strategies

The network is structured into five specialised working groups (WGs) and three coordination groups (Outreach, Exploitation and Dissemination). It is steered by the Core Group and the Management Committee (MC) (see Figure 1). About 200 researchers from more than 40 countries representing different domains, e.g. CALL, crowdsourcing, NLP, e-lexicography, computer science, ethics, law, and business, have joined forces. WG1 deals with approaches for the collaborative creation of teaching content (explicit crowdsourcing). WG2 is concerned with the integration of implicit crowdsourcing techniques into interactive learning content (e.g. gap filling exercises), which allows to harvest information and data on learners. WG3 researches the usability and user experience of learning platforms in order to assure to attract and retain enough learners and tutors. WG4 addresses technical challenges related to an online learning environment for numerous distributed clients, such as scalability and robustness. Finally, WG5 deals with ethical, legal and commercial perspectives. The coordination groups, i.e. Outreach, Exploitation and Dissemination, support the WGs with transversal tasks enabling optimal communication and knowledge exchange within and outside of enetCollect.

Figure 1. Organisational structure of enetCollect

The objective is to carry out the groundwork for setting into motion a new research and innovation trend for the creation of online language learning solutions. The WGs will explore innovative approaches for the production and enhancement of online teaching materials, the opportunities posing the integration of crowdsourcing techniques into learning environments, and the blending of learning content with gamification and data harvesting. This effort can particularly be beneficial for less widely taught languages with smaller speaker communities that have limited language resources [START_REF] Mariani | Technologies de la langue : Etat des lieux[END_REF], because it will enable them to gather data for teaching and provide these to learners, who would otherwise have a very limited access to such materials. While for lesser spoken languages it can be particularly challenging to involve a sufficient number of participants, the extent of the network, together with the gamification layer, comprehensiveness and online nature of its approach foster participation and support to a maximum. Depending on the type of language resources dealt with, the completion of material gathering can be achieved with semi-automatic methods [START_REF] Sagot | The Lefff, a freely available and large-coverage morphological and syntactic lexicon for French[END_REF] related to explicit and implicit crowdsourcing, which will collaboratively devise lesson content (explicit crowdsourcing) and generate exercise content for individual learners based on their progress and feedback (implicit crowdsourcing).

Having a manpower producing language resource materials can result in high costs [START_REF] Böhmová | The Prague dependency treebank : Three level annotation scenario[END_REF], but crowdsourcing offers a cost-effective solution. For instance, both Wikipedia, which redefined the domain of encyclopedias, and reCAPTCHA, have made the highly laborious task of manual writing and annotation possible by obtaining a workforce from the crowd. The content providers will upload and share content via telecollaboration across the boundaries of local territories, thus making it available as free, partially free, or paid, all depending on the business scheme, maintenance, and overall support of official authorities. The assurance of quality can also be part of a crowd feedback. Different types of users will evaluate the usefulness and trustworthiness of content via different reward and feedback mechanisms. The problem of ethics is also a very important in this context and will be addressed in connection with data collection and usage, and personal data protection using an ethics by design approach [START_REF] Spiekermann | Ethical IT Innovation: A Value-Based System Design Approach[END_REF].

Conclusion and future work

EnetCollect aims both at reviewing the state-of-the-art in order to gather and compile an overview of relevant approaches and techniques, and at achieving a shared understanding of the subject by creating an interdisciplinary framework for defining its terminology, key concepts, objectives and opportunities. It aims at carrying out prototypical experiments, evaluating and disseminating their results. It possesses communication means allowing to easily exchange information and reach relevant stakeholders for targeting new research stays, organized workshops, training schools, and funded initiatives. The involvement of new and current members will be pursued through promotion of the Action through relevant channels of the research domains concerned.

5.

Eurac Research, Bolzano, Italy; e-mail verena.lyding@eurac.edu

Eurac Research, Bolzano, Italy; e-mail lionel.nicolas@eurac.edu

University of Iceland, Reykjavík, Iceland; e-mail brb19@hi.is

Sorbonne Université, Paris, France; e-mail karen.fort@sorbonne-universite.fr

Acknowledgements

This article is based upon work from COST Action enetCollect (CA16105) supported by COST (European Cooperation in Science and Technology).


Matthieu Mastio

Gérard Scemama

Omer Rana

Two Distribution Methods for Multiagent Traffic Simulations

Keywords: Multiagent Systems, Traffic, Simulation, High Performance Computing

Modeling and simulation play an important role in transportation networks analysis. With the widespread use of personalized real-time information sources, the behavior of the simulation depends heavily on individual travelers reactions to the received information. As a consequence, it is relevant for the simulation model to be individual-centered, and multiagent simulation is the most promising paradigm in this context. However, representing the movements of realistic numbers of travelers within reasonable execution times requires significant computational resources. It also requires relevant methods, architectures and algorithms that respect the characteristics of transportation networks. In this paper, we define two multiagent simulation models representing the existing sequential multiagent traffic simulations. The first model is fundamental diagram-based model, in which travelers do not interact directly and use a fundamental diagram of traffic flow to continuously compute their speeds. The second model is car-following based, in which travelers interact with their neighbors to adapt their speeds to their surrounding environment. Then we define patterns to distribute these simulations in a high-performance environment. The first is agent-based and distributes agents equally between available computation units. The second pattern is environment-based and partitions the environment over the different units. The results show that agent-based distribution is more efficient with fundamental diagram-based model simulations while environment-based distribution is more efficient with car following-based simulations.

Introduction

Mobility policies makers need decision support systems to decide which transportation policies they should implement. In this context, simulation is one of the important tools that allow to test strategies and multiple scenarios without impacting the real traffic [START_REF] Abadi | Traffic flow prediction for road transportation networks with limited traffic data[END_REF]. However, transport systems are becoming progressively more complex since they are increasingly composed of connected entities (mobile devices, connected vehicles, etc). It becomes critical that simulation tools take into account this fact. Indeed, with the generalization of real-time traveler information, the behavior of modern transport networks becomes harder to analyze and to predict.

For these reasons, multiagent simulation, which adopts an individualcentered approach, is one of the most relevant paradigms to design and implement such applications. The design and development of multiagent traffic simulations are relevant in several contexts and in pursuit of various objectives. The simulation can be used to validate the impact of the use of cooperative systems [START_REF] Guériau | Vips: A simulator for platoon system evaluation[END_REF], to test changes in behavior after the introduction of new mobility services, such as carpooling. A multiagent traffic simulation platform simulates the behavior of travelers interacting in a complex, dynamic and open environment, on which they have a partial perception [START_REF] Badeig | Agent-based coordination model for designing transportation applications[END_REF]. Each agent tries to find the most efficient route to reach its destination in a network evolving dynamically. In some applications (e.g. [START_REF] Zargayouna | Agent-based simulator for travelers multimodal mobility[END_REF]), an agent can potentially be informed of the status of the network and use this information to modify its route. In this kind of simulations, it is important to model and simulate a realistic number of travelers to correctly observe the effects of individual decisions. In the European project Instant Mobility1 for instance, the objective was to supply a multimodal platform with individual and multimodal travel queries and dynamic positions of travelers and vehicles. To allow the platform to demonstrate its efficiency in an operational context, we implemented a simulator (called SM4T [START_REF] Zargayouna | Multiagent simulation of real-time passenger information on transit networks[END_REF]), which had to be executed with an actual volume of travelers. Other examples where simulations must be scalable concern the testing of new mobility services such as carpooling, car sharing, dial a ride, evacuation modeling, the exchange of information between connected vehicles, etc.

However, the simulation of an actual number of passengers in a big city (several millions of travelers) comes with a high cost. If the same computing infrastructure is maintained, the cost is a loss in accuracy. Otherwise, the cost is a considerable computing power and an architecture allowing the distribution of computations on many computation units. We desire to keep the same simulation quality and choose the latter approach. However, the majority of current multiagent traffic simulators do not allow such distribution. This induces limitations on the number of simulated travelers, means of transport and the size of the considered networks. Our main objective in this paper is to provide reproducible distribution patterns that could be used by existing and future implementations of multiagent traffic simulations.

In this paper, we propose to study distribution methods for multiagent traffic simulations. We define two multiagent simulation models, representing the main types of multiagent simulations of the literature. The first model is called fundamental diagram-based model, in the sense that travelers do not interact directly but use a fundamental diagram of traffic flow to continuously compute their speeds. This is the choice performed for instance by [START_REF] Zargayouna | Simulating the impact of future internet on multimodal mobility[END_REF]; [START_REF] Meignan | Simulation and evaluation of urban bus-networks using a multiagent approach[END_REF]; [START_REF] Mahmassani | Dynamic network traffic assignment and simulation methodology for advanced system management applications[END_REF] and [START_REF] Cajias | A multi-agent traffic simulation framework for evaluating the impact of traffic lights[END_REF]. The second model is called car following-based, in which travelers interact with their neighbors to adapt their speeds to their surrounding environment. This is the most common choice performed in the literature for multiagent simulations (e.g. [START_REF] Zhang | Virtual traffic simulation with neural network learned mobility model[END_REF]; [START_REF] Kühnela | Implementing an adaptive traffic signal control algorithm in an agent-based transport simulation[END_REF]). These two models correspond partially to microscopic and mesoscopic traffic simulations. Microscopic models simulate the interactions between individual vehicles, while mesoscopic models simulate small groups of traffic entities, whose interactions are described in a medium level of detail. This paper studies two distribution patterns (agent-based and environmentbased) applied to these two simulation models. The objective is to discover the most suitable distribution pattern, provided a chosen multiagent traffic model. The results show that agent-based distribution is more efficient with fundamental diagram-based simulations while environment-based distribution is more efficient with car following-based simulations.

The remainder of this paper is structured as follows. In section 2, we present the previous proposals for multiagent traffic simulation and the existing distributed multiagent platforms. Section 3 presents a simulator for the execution of both fundamental diagram-based and car following-based multiagent traffic simulations. Section 4 presents the two distribution patterns (agent-based and environment-based) and their application to the two simulation models. Section 5 explains our experimental setup and the results of our simulations. Section 6 concludes this paper.

Related work

The problem

The problem tackled in this paper is to distribute n agents on k connected computation units. The interactions between agents on the same units are less costly then inter-units interactions, which generates messages using the communication network. Let w i the workload of agent a i . Let p(a i , a j ) the interaction costs between agents a i and a j . If they are on the same unit, this cost is zero. The workload of a unit U i is:

W (U i ) = a j ∈U i w j (1)
The communication cost between two units U i and U j is:

P (U i , U j ) = a k ∈U i a l ∈U j p(a k , a l ) (2)
An ideal distribution of the n agents on the k units is a multi-objective optimization which has to:

• distribute best the workload between units,

• limit to the maximum the communications between units.

Formally, find the distribution minimizing:

1≤i≤j≤k P (U i , U j ) with W (U i ) = 1≤h≤k W (U h ) k + (3)
Miyata and Ishida (2007) perform an integer programming optimization of the problem. Even if this approach allows to find an optimal solution to the distribution problem, the computational complexity increases exponentially with the number of agents, which makes it unusable for large-scale traffic simulations.

Two approaches exist for distributing simulations [START_REF] Vigueras | A comparative study of partitioning methods for crowd simulations[END_REF][START_REF] Rihawi | Effective distribution of large scale situated agent-based simulations[END_REF]. The first ignores communication costs and focuses on workload, distributing the agents the most equitably possible between units. The second approach is environment-based: il assumes that agents that are physically close would probably interact more. The environment is then split and each unit is responsible of a subpart of the environment and the agents in it.

State of the art

In this section, we position our work with the previous works in the literature. In the next paragraph, we present the existent multiagent traffic simulators. Then we focus on the existing proposals for distributing these platfoms. We finally describe the parallel multiagent platforms.

Multiagent traffic simulation

There exist several multiagent traffic simulations in the literature. Most of them are car following-based models, in the sense that they rely on local interactions between traveler agents to define agents speeds. For instance, Transims [START_REF] Nagel | Parallel implementation of the transims microsimulation[END_REF], MATSim [START_REF] Kühnela | Implementing an adaptive traffic signal control algorithm in an agent-based transport simulation[END_REF], Sumo [START_REF] Zhang | Virtual traffic simulation with neural network learned mobility model[END_REF] and Vissim [START_REF] Ehlert | Junction parameter calibration for mesoscopic simulation in vissim[END_REF] are widely used car following-based simulators of this type. AgentPolis ( Čertickỳ et al., 2014), Polaris [START_REF] Auld | Polaris: Agent-based modeling framework development and implementation for integrated travel demand and network and operations simulations[END_REF] and Archisim [START_REF] Doniec | A behavioral multiagent model for road traffic simulation[END_REF] are also multiagent traffic simulation platforms describing precisely the behaviors of each traveler at a microscopic scale. Some existing multiagent simulations are fundamental diagram-based model, in the sense that they compute the agents speeds based on a function mapping the number of agents traveling on an edge with their speeds. This model is generally used when an individual representation of travelers is needed but there are no reliable data about their local behavior. [START_REF] Zargayouna | Simulating the impact of future internet on multimodal mobility[END_REF]; [START_REF] Meignan | Simulation and evaluation of urban bus-networks using a multiagent approach[END_REF]; [START_REF] Cajias | A multi-agent traffic simulation framework for evaluating the impact of traffic lights[END_REF]; [START_REF] Mahmassani | Dynamic network traffic assignment and simulation methodology for advanced system management applications[END_REF] have made this choice.

Distributing traffic simulation

The problem of distributing multiagent traffic simulations has attracted many studies recently. Some previous works have addressed the specific problem of distributing multiagent traffic simulations. [START_REF] Bragard | Self-balancing decentralized distributed platform for urban traffic simulation[END_REF] propose dSumo, a distribution platform applied to the Sumo microscopic simulation platform. [START_REF] Lee | A framework for parallel traffic simulation using multiple instancing of a simulation program[END_REF] propose a parallel version of Paramics [START_REF] Chen | Evaluation of performance of bus lanes on urban expressway using paramics micro-simulation model[END_REF]. However, they present small clusters and networks (grid-like).

Some proposals in the literature propose parallel but non-distributed solutions. These simulations are potentially faster but can only work with multi-threaded environment but not with distributed environments. [START_REF] Nagel | Parallel implementation of the transims microsimulation[END_REF] present a parallelization of the Transims platform. They use a master-slave model for synchronizing the different units. [START_REF] Qu | Large-scale dynamic transportation network simulation: A space-time-event parallel computing approach[END_REF] present parallel-computing framework for mesoscopic transportation simulation. Aimsun [START_REF] Barcelo | Parallelization of microscopic traffic simulation for att systems analysis[END_REF]) also proposes such a parallel but not distributed simulation setup.

All these interesting proposals focus on distributing specific simulation platforms. In the present work, our objective is to propose distributed mechanisms that are independent from specific traffic platforms. In addition, to the best of our knowledge, our work is the only one dealing with the distribution of simulations using the two different interaction models (viz. car following-based model and fundamental diagram-based model).

Some general-purpose multiagent platforms have been specifically developed for large scale simulation in the last years. Mace3j [START_REF] Gasser | Mace3j: fast flexible distributed simulation of large, large-grain multi-agent systems[END_REF], James [START_REF] Himmelspach | Plug'n simulate[END_REF] and Swages [START_REF] Scheutz | Swagesan extendable distributed experimentation system for large-scale agentbased alife simulations[END_REF] are distributed multiagent platforms, but that have no available source or executable code. Jade [START_REF] Bellifemine | Developing Multi-Agent Systems with JADE[END_REF] simplifies the implementation of distributed multiagent models across a FIPA compliant middleware. The platform can be distributed across multiple units and its configuration can be controlled from a remote GUI. Agents are implemented in Java while the communications relay on the RMI library. D-Mason2 (Cordasco et al.) is the distributed version of the Mason multiagent platform. It does not require users to rewrite their already developed simulations while overcoming the limitations on maximum number of agents. RepastHPC [START_REF] Collier | Repast HPC: A platform for large-scale agentbased modeling[END_REF], a distributed version of Repast Simphony, uses the Repast's concepts of projections and contexts and adapts them for distributed environments. Pandora [START_REF] Angelotti | PANDORA: a multi-agent system using paraconsistent logic[END_REF] is close to RepastHPC and automatically generates the code required for inter-server communications. GridABM [START_REF] Gulyas | A modeler-friendly API for ABM partitioning[END_REF] is based on Repast Simphony but takes another approach and proposes to the programmer general templates to be adapted to the communication topology of her simulation. Flame [START_REF] Coakley | Exploitation of high performance computing in the FLAME agent-based simulation framework[END_REF] allows the programmer to generate HPC simulations from finite state machines. It has also been suggested to use graphical units (GPGPU) to scale up the multiagent simulations. The TurtleKit 3 platform has been used in GPGPU [START_REF] Michel | Délégation GPU des perceptions agents : intégration itérative et modulaire du GPGPU dans les simulations multi-agents. application sur la plate-forme turtlekit 3[END_REF] and [START_REF] Strippgen | Multi-agent traffic simulation with cuda[END_REF] propose to use it in parallelizing multiagent traffic simulations. However, these distributed platforms do not offer fine controls on how the communications between units are performed. Indeed, the communication layer is transparent for the programmer, which makes it easier for him to implement distributed simulations, but prevents him from optimizing the distribution. The best way to manage the communications depends on the application and using such general platforms for a traffic simulator would not produce optimal results. [START_REF] Rihawi | Effective distribution of large scale situated agent-based simulations[END_REF] discuss the issues related to multiagent simulation in a distributed virtual environment. The authors describe methods to split the virtual environment in several zones to parallelize the simulation execution. This work proposes an efficient splitting of a continuous space in two dimensions. In the present paper, we use among others an adaptation of this work for a graph structure, adapted to distribute traffic-based simulations.

Multiagent traffic simulations

In the following, we present two multiagent traffic simulations. They are designed with the objective of representing the existing multiagent traffic simulations. They contain the main features of these types of simulation, namely the network and agents individual representation and the agents movements on this network. This section presents the common components of these simulations. The following sections present the differences between the two simulations, mainly concerning the travelers speed computation.

The multiagent system

The multiagent system, which is common to both simulations, is composed of a dynamic set of agents representing travelers, interacting with a transportation network environment. We model the transportation network in which the travelers use a graph G(V, E), where E = {e 1 , ..., e n } is a set of edges representing the roads and V = {v 1 , ..., v n } is a set of vertices representing the intersections. The agents, representing the travelers, move on this network from their origins to their destinations, trying to minimize their travel costs. A traffic simulation usually adheres to the following steps. First, the simulation platform loads the parameters (simulation duration, number of generated agents, etc.) and the description of the network. Then, it creates the logical graph from the network representation, to enable shortest paths calculation and agents movements. The agents then execute one step of simulation. During a step of simulation, each agent either computes a shortest path or moves from one position to another. When an agent reaches its destination, it leaves the simulation. When the simulation duration is reached, the simulation stops and the results are collected.

When created, an agent has an origin node o and a destination node d. The first action that it executes when created and activated is to compute an A shortest path algorithm between o and d. The shortest path is performed on the graph G, which edges costs are dynamic, depending on the current traffic. When it has a current path, the agent moves according to it. At each activation, it moves the allowed distance following its current speed. The speed of the agent is computed following the simulation model (car following-based or fundamental diagram-based model), described in the following sections. Each time it reaches a node, the agent recomputes a shortest path, to check if the current traffic conditions have evolved and if a new shortest path has become available3 .

These are the main components of the model that are common to both types of simulations. In the following sections, we present the specific methods for the two simulations, namely fundamental diagram-based and car following-based.

Fundamental diagram-based simulation model

In the fundamental diagram-based simulation model, the speed of an agent on an edge is computed following the number of other agents traveling on the same edge. To this end, a fundamental diagram of traffic flow is used [START_REF] Daganzo | The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory[END_REF]. The diagram defines a relation between the flow (vehicles/hour) and the density (vehicles/km) (cf. Figure 1) on an edge or a part of an edge to calculate the speed of the agents at each time. The fundamental diagram suggests that if we exceed a critical density of vehicles k c , the more vehicles are on a road, the slower they move (Figure 2).

With the distribution objective that we have, the locations of the agents and their interaction patterns are the most important. In the fundamental

Car following-based simulation model

In the car following-based simulation model, the speed of an agent on an edge is computed following the position and speed of the vehicles surrounding him. In this model, the information available to each agent is only local. The agents perceive a part of their environment and calculate their next move given the perceived information. This implies many local communications between the agents, because their actions are conditioned by the actions of the other agents present in their surroundings. This model is generally based on a car-following model described in the following.

At each activation, each agent i computes its speed based on the speed and position of the agent i -1 before him:

speed i (t + T ) = αspeed i (t) + βs i,i-1 (t)
with T the reaction time and s i,i-1 (t) the relative speed of i. If there is no vehicle preceding the agent, it accelerates until it reaches the speed limit of its edge.

In this model, we cannot rely on the fundamental diagram of traffic to continuously have the current travel times on the edges. Instead, each agent registers its experienced travel time when it reaches the end of the edge (as proposed by [START_REF] Wahle | The impact of real-time information in a two-route scenario using agent-based simulation[END_REF]). The shortest path calculation is based on the graph where the travel times costs are fed by the agents following this procedure.

In contrast with the fundamental diagram-based model, the agents in the car-following model do interact directly. The speed of the agent is computed with a direct interaction between the considered agent and the agents before him. This difference between the two models conditions the choice of the relevant distribution pattern for the considered simulation type. The distribution patterns are described in the following section. [START_REF] Behrisch | SUMO -simulation of urban MObility -an overview[END_REF]; [START_REF] Maciejewski | Towards multi-agent simulation of the dynamic vehicle routing problem in matsim[END_REF]; [START_REF] Doniec | A behavioral multiagent model for road traffic simulation[END_REF]; [START_REF] Cameron | Paramics -parallel microscopic simulation of road traffic[END_REF] for instance adhere to this car following-based model.

The Distribution Methods

We define two patterns to distribute traffic simulations. The patterns are the same than those identified by [START_REF] Rihawi | Effective distribution of large scale situated agent-based simulations[END_REF] for general-purpose situated multiagent simulations, and we believe that they present two representative distribution patterns for this kind of simulations. The first pattern (called agent-based distribution) is the distribution model used by [START_REF] Barceló | Microscopic traffic simulation for ATT systems analysis. a parallel computing version[END_REF]. It consists in the duplication of the transport environment on all processing units, and the equal dispatching of the agents on each one. As a consequence, agents stay on the same unit during all the simulation. The second pattern is the mostly used pattern in the literature. It consists in partitioning the transportation environment and the dispatching of each subpart of the environment -and all the agents in it -on each processing unit. In this pattern, agents might have to move from one unit to another if their itinerary crosses several subparts of the transport environment.

Agent-based distribution

The first distribution pattern is agent-based, since it clusters the set of agents in k equal parts (with k the number of available processing units), and distributes each subset on a unit and executes the simulation (cf. Figure 4). The transportation network is duplicated on each unit. This method ensures that each unit has the same amount of work at any time of the simulation. In the following, we describe the use of this pattern for both simulation models that we have defined.

Fundamental diagram-based simulation with agent-based distribution

In a fundamental diagram-based simulation, when it is distributed following the agent-based distribution pattern, every unit continuously informs the other units of its network state. Indeed, every unit does not have a complete view of the network state, since only a part of the agents evolve in the unit. Thus, every unit sends the list of edges together with the number of agents currently on them. Each unit is then capable of computing the relevant speed for each agent (using the fundamental diagram of traffic) and to compute the shortest paths for the agents.

Car following-based simulation with agent-based distribution

When distributed following the agent-based distribution pattern, the agents in a car following-based simulation do not use a fundamental diagram of traffic to compute their speeds. Instead, they need to know the state of the agents preceding them. To do so, they interrogate the edges in the other units to know if there are agents preceding them, and if it is the case, to know their states. Moreover, the units exchange the current travel times (provided by the agents as explained in the car following-based model), in order to compute the shortest paths for the agents.

Environment-based distribution

The second approach to distribute traffic simulations is environmentbased. Its main idea is that it tries to keep on the same unit the agents who are geographically close in the transport network (cf. Figure 5). To this end, the network is partitioned in k parts (with k the number of available processing units), and distribute it between the different units. Each unit is only aware of what is happening on the part of the graph that it is managing, and the agents that are in the same area are now likely to be on the same unit. If an agent reaches a part of the network that is not managed by its current unit, it moves to the proper unit. In order for the environment distribution method to be effective, each unit has to manage approximately the same number of agents and the number of edges connecting the partitions has also to be minimized (to reduce the number of agents being transferred between units).

The problem of graph partitioning has been widely studied in the scientific literature. We propose a method derived from the Differential Greedy algorithm by [START_REF] Fiduccia | A linear-time heuristic for improving network partitions[END_REF] that allows us to use the algorithm with weighted vertices while producing more connected partitions (Algorithm 1). For edges partitioning, we make the same choice as [START_REF] Cetin | A large-scale agent-based traffic microsimulation based on queue model[END_REF] by not cutting edges in the middle. We associate each edge with the partition of its origin node.

The algorithm starts by creating a minimal partition with only one node each (instructions (1) to ( 5)). Then, while there are nodes to be associated to partitions, the algorithm:

• chooses the lightest partition P p , in terms of agents present in it (instruction ( 6))

• finds the nodes that are the most connected with the nodes already in P p and that are the least connected with the nodes that are not in P p . The parameter gives more or less importance to the nodes that are close to the partition (instruction 7).

• chooses one of these nodes, adds it to the partition and removes it from the nodes to process (instructions 8 to 10).

Our modification of the original differential greedy algorithm concerns the choice of the current partition to treat. The "lightest" partition in the Algorithm 1 Differential Greedy algorithm Require:Graph G = (V, E), number k of partition Ensure:Partition P (1) original algorithm concerns the number of nodes in the partition, while in our algorithm, it concerns the number of agents in the partition. The second difference concerns the use of , which encourages the connectivity of the sub-partitions. Indeed, having sub-partitions that are not connected could lead to agents going back and forth to the same unit while staying in the same neighborhood. 4.2.1. Fundamental diagram-based simulation with environment-based distribution When used with an environment-based distribution, the computation units in the fundamental diagram-based simulation exchange the current travel times on the transport edges, to be able to compute the shortest paths for the agents. However, since all the agents on an edge are present on the same unit, they do not need to exchange the number of agents per edge. The fundamental diagram of traffic and the speeds of the agents can indeed be defined locally.

P ← P 0 , ..., P k-1 (2) V ← V for p ∈ [0, k -1] do (3) v ← random vertex of V (4) P p ← {v} (5) V ← V \ {v} end for while |V | > 0 do (6) p ← index of the lightest partition (7) m = min v∈V (1 + )(number of v's neighbors ∈ P p ) -(number of v's neighbors / ∈ P p ) (8) mv = random vertex of v ∈ V |(1 + )(number v's neighbors ∈ P p ) -(number of v's neighbors / ∈ P p ) = m (9) P p ← P p ∪ {mv} (10) V ← V \ {mv} end while (11) Return P

Car following-based simulation with environment-based distribution

When distributed following the environment-based distribution pattern, the agents in a car following-based simulation need to know the state of the agents preceding them. In contrast with the agent-based distribution model, the agents preceding them are by definition present on the same computation unit. The interrogation of the edges is then local to the concerned computation unit. The units keep on exchanging the current travel times (provided by the agents) to compute the shortest paths for the agents.

Experiments and Results

Implementation

A way to execute a distributed simulation is to define a distributed program where each computation unit, while executing the same program, owns only a part of the program data in its private memory, and all the processors are connected by a network. The advantage of this approach is its high scalability. Indeed, it can be implemented on most parallel architectures and we can deploy the same simulation on larger systems if we need more computing power and memory. We use Python to develop our simulator for its efficiency in quick prototyping. Python is a mature portable language with many well tested scientific libraries and is along with C and Fortran one of the most used languages for high performance computing [START_REF] Shivashankar | Efficient software for programmable visual analysis using morse-smale complexes[END_REF]. Here, we do not seek absolute performance, but we aim to study the relative efficiency of different distribution methods. Thus we believe that Python is a relevant choice. The inter-process communications are managed by MPI, which is the standard language for parallel computing with a huge community of users. MPI offers a simple communication model between the different processes in a program and has many efficient implementations that run on a variety of machines4 .

We use the igraph tools for the modeling of the traffic network in the form of a directed graph. Three python classes are defined. The Simulation class loads the parameters, the graphs and creates the agents. The Context class manage the agents, while the Agent class manages the agents behaviors, including their movements and shortest paths calculations.

We have executed the distributed simulations on an experimental cluster that we have set up. For our tests, we used two units under Linux Mint 17.2 Rafaela (kernel version 3.16.0-38-generic) each with an Intel Xeon processor CPU E7-4820 (32 cores at 2Ghz) with 250GB of memory. A ssh server is installed on each machine. The ssh protocol is used by MPICH 3.0.4, to encapsulate the MPI messages. We ran the simulations on six configurations: the first is a sequential version of the program on a single core and the five others are distributed versions with 4, 8, 16, 32 and 64 cores. The behaviors in terms of traffic of the sequential and all the distributed versions are rigorously the same.

We have considered two networks. The first is a real network concerning the Paris-Saclay region, France, with 1895 nodes and 3831 edges. The number of daily travelers using this network is around 110,000. The originsdestinations of the travelers are based on real data travel patterns. We consider from 10,000 travelers to 500,000 travelers in our simulations. That means that we represent from around 10% to around 500% of the real volumes of travelers in our simulations. The second is a virtual network of 200 nodes power-law graph generated with the [START_REF] Barabasi | Emergence of scaling in random networks[END_REF] model with random origins and destinations. We have executed each simulation 10 times and provide the average results5 We consider no lane-changing behaviors in the implemented car-following model.

Results

Distribution Method × Simulation Model

In this section, we compare the two methods of distribution (agent-based and environment-based distributions) with the different simulation models (car following-based model and fundamental diagram-based model) with increasing the number of agents (from 10,000 to 500,000). The speedup measures how many times the distributed simulation is faster compared to the corresponding sequential execution. The speedups for the two distributions methods applied on the different paradigms are plotted in Figure 6 and Figure 7. As we can see, the agent distribution is efficient for a fundamental diagram-based model (more than 5 times faster with 500,000 agents). There is no local interactions in this type of simulations and therefore this method allows to get a perfectly balanced load all along the simulation, while keeping the amount of inter-servers communications at the minimum.

However, this method is particularly ineffective in the case of a car followingbased simulation. Indeed, the agents interact continuously with the other agents that are not situated in the same unit. This generates many communications between the servers, and the gain of the parallelization is annihilated by the time required by these communications. This method is even less efficient than the sequential execution for the car following-based model For a fundamental diagram-based simulation, the environment-based distribution is less efficient than agent-based distribution. It is well adapted for a car following-based model simulation though. This method is up to 14 times faster than a sequential execution applied in a car following-based simulation. The explanation of the poor results of the fundamental diagram-based sim-ulations with environment-based distribution is that the communication of edges costs between units, necessary for the computation of vehicles speeds, takes too much time and penalizes these simulations.

Figure 8 shows the preferred pairs (fundamental diagram with agentbased distribution and car-following with environment-based distribution). The curves show that the pair environment-based distribution with carfollowing model is more effective than the pair agent-based distribution with fundamental diagram based.

Impact of Network type

To assess the impact of network type and size on the distribution, we have executed the same methods on a virtual network of 200 nodes power-law graph generated with the Barabasi-Albert model [START_REF] Barabasi | Emergence of scaling in random networks[END_REF]. Origins and destinations are this time generated randomly. The Figure 9 provides the results for the agent-based distribution and Figure 10 provides the results for the environment-based distribution. For agent-based distribution, the findings are the same: the fundamental diagram-based simulations behave way better than car following-based simulations. However, for environmentbased distribution, the findings are different: the two simulations types profit of the distribution at the same level (fundamental diagram-based simulations perform even slightly better). We explain this difference by the network size. Indeed, Paris-Saclay network is ten times bigger than the considered virtual network. The communication of edges costs between units, necessary for the computation of vehicles speeds, is a lot less costly with the virtual network and does not penalize the fundamental diagram-based simulations anymore.

Increasing units Numbers

To better assess the scalability of the different distribution methods, we execute the different simulations on the Paris-Saclay network with increasing number of available units: 4, 8, 16, 32 and 64. We consider 100,000 travelers in these simulations, which correspond to the real number of daily travelers. The results are reported in Figure 11

Conclusions and perspectives

The work presented in this paper is motivated by the scalability limitations of existing simulation platforms, and specifically of our simulation platform SM4T [START_REF] Zargayouna | Simulating the impact of future internet on multimodal mobility[END_REF]. We applied two distribution methods on two types of multiagent traffic simulators. The results show that agentbased distribution is well suited for fundamental diagram-based simulators while environment-based distribution is well suited for car following-based simulations. To use the distribution methods presented in this paper, we have to first classify the simulation platform at hand. For SM4T, the simulation is fundamental diagram-based because agent's speeds are computed with a function associated with the edges that they are using. As a consequence, distributing SM4T should be performed following an agent-based distribution model. Of course, the actual implementation of the distributed version of the simulation platform has to be done. But now we know which distribution pattern would me more relevant. This process could be applied with other simulation platforms to be distributed. In the near future, we will propose a load balancing algorithm that is able to dynamically balance the loads of a traffic simulation. We will also test this method on a cloud-like environment (single core units, linked by a network). We also plan to consider multimodal multiagent traffic simulators. The presence of different transport modes and networks could encourage to mix the patterns presented in this paper with a distribution per transport mode. We are also working on the integration of information networks (such as social networks or intervehicular interaction [START_REF] Zargayouna | Generic model for resource allocation in transportation. application to urban parking management[END_REF]) and their impact on the distribution performance. Indeed, if travelers interact often, they should be preferably executed on the same units, or else they would generate too many communication and deteriorate the performance of the system. Finally, other aspects than simulation models might impact the distribution, such as the presence of a multi-threading or message-passing environments, and we will consider investigating them. The experiments in this paper were performed on a research simulator, and we look forward to confirming them with other models from the literature.

Figure 1 :

 1 Figure 1: Fundamental diagram

Figure 3 :

 3 Figure 3: The car-following model

Figure 4 :

 4 Figure 4: Agents distribution

Figure 5 :

 5 Figure 5: Environment distribution

Figure 6 :

 6 Figure 6: Speedup for the agent-based distribution (Paris-Saclay Network)

Figure 7 :

 7 Figure 7: Speedup for the environment-based distribution (Paris-Saclay Network)

  for agent-based distribution and Figure 12 for environment-based distribution. The results show that the speedup is increasing fast for environment-based distribution with car following-based simulation and for agent-based distribution with fundamental diagram-based simulation. The speedup is stable or increasing slowly for agent-based distribution with car following-based simulation and for environment-based distribution with fundamental diagram-based simulation. These results confirm

Figure 9 :

 9 Figure 9: Speedup for the agent-based distribution (Barabasi network)

Figure 11 :

 11 Figure 11: Impact of the number of units (agent-based distribution)

Figure 12 :

 12 Figure 12: Impact of the number of units (environment-based distribution)

http://www.instant-mobility.com/

Distributed Mason

The graph being directed, turnarounds are only possible at nodes and there is no need for the agent to execute a shortest path while traveling on an edge.

MPI4PY is an efficient interface that allows to use MPI with Python.

The standard deviation is less than 5% in all the simulations.


Angélique Villière

Sarah Le Roy

Catherine Fillonneau

Carole Prost

HAL is

Validation of the olfactometric method for wine aroma analysis

An original approach for wine aroma recombination 33 odorant zones were significantly detected by GC-MS-O analysis. Evaluation of extracts designed with the InnOscent device demonstrates that the mixture of odorants detected significantly by GC-O can mimic the aroma of the wine studied. Moreover, the mixture those perceived by 75% of the judges is demonstrated to be sufficient to mimic the aroma of the wine whereas these compounds represent only around 40% of the odorants detected. Gas chromatography coupled to mass spectrometry and olfactometry (GC-MS-O) is a method commonly used to study wine aroma. Analysis of experiments involving several judges results in a profile in which the more detected odorants are supposed to contribute most to the aroma product. While valuable, this method does not provide information on the actual impact of these compounds when they occur together in the product.

Under the InnOscent device -a laboratory-designed chromatographic system -an innovative reconstitution method was developed to evaluate the contribution to wine aroma of odorants detected by GC-O and assess the relevance of the olfactometric approach.

SPME extraction and olfactometric analysis

Compounds perceived by at least 6 judges N ≥ 6

Mass Spectrometer

  of recombination which does not require standards, enables to reinforce the relevance of GC-O to explore complexity of wine aroma.