Christophe Hurter
email: christophe.hurter@aviation-civile.gouv.fr

Mathieu Serrurier
email: serrurie@irit.fr

Roland Alonso
email: alonso@cena.fr

Gilles Tabart
email: tabart@cena.frvinot@cena.fr

Jean-Luc Vinot

An automatic generation of metro-like maps to display flight routes for air traffic controllers: structure and color optimization

Keywords: Visualization, schematic maps, colors assignment, Air Traffic Controller. ACM Classification H5.m. Information interfaces and presentation (e.g., HCI): Miscellaneous

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Fundamental research in visualization is concerned with the impact of presentation on visual perception and understanding [START_REF] Tufte | Visual Explanation[END_REF] [START_REF] Ware | Information Visualization, perception for design[END_REF]. Current Air Traffic Control (ATC) environments employ complex visualization systems. These visualizations display large quantities of information that must be understandable with the minimum cognitive workload. As traffic increases together with safety levels, The ATC environment requires new kinds of visualizations.

The activity of Air Traffic Controllers (ATCos) consists in maintaining safe distances between aircraft by giving clearance to pilots (heading, speed, or altitude orders). The traffic is planned in advance: companies must request a flight plan from the regulatory authorities, which is translated into a mandatory Flight Route (FR) i.e. a sequence of beacons ( named locations on the ground), with an associated time and altitude. A first task associated with the FRs is the a posteriori analysis of the traffic in order to determine the most conflicting FRs. Moreover, future ATC systems promote the use of FR as their main component. For instance, ATC regulators envisage a system where airline companies have to book time-slots along FRs. A natural visualization for this kind of task is the geographical view. However FRs are numerous and run into each other. A direct representation of the FRs is too complex and unusable. An efficient visualization of FRs would simplify their utilization.

In this context, metro map visualization appears to be a suitable solution. Metro maps are schematic drawings of the underlying geographical network that represents the different stations and lines of a metro system [START_REF] Garland | Mr Beck's Underground Map[END_REF]. Automatic generation of metro maps is an active, ongoing research area [START_REF] Avelar | Schematic maps on demand: design, modeling and visualization[END_REF] [START_REF] Nöllenburg | A mixed-integer program for drawing high-quality metro maps[END_REF] [START_REF] Stott | Metro Map Layout Using Multicriteria Optimization[END_REF] [START_REF] Stott | Metro Map Layout Using Multicriteria Optimization[END_REF]. Most existing methods consist in optimizing the shape of the networks by considering the mathematical criteria the authors want to minimize (network density, straight lines...).

Our approach is divided into two parts: The geographical optimization and the color assignment of FRs.

In the first part of this paper, we study how to adapt existing metro map generation to the ATC context. Most existing metro maps are produced manually: while metro-map design is time-consuming, it is also limited by the number of metro lines, and by the fact that the metro network does not often change. On the contrary, a schematic maps view of FRs must be generated automatically, as FRs are too numerous (more than 600 FRs in the French airspace) and change regularly (their life-time can be as low as 40 days, and adding a new flight route is cheaper and physically less challenging than creating a new metro line). In order to adapt the metro map generation, we compare differences between metro and FRs layouts. Then we define specific mathematical cost functions that measure the quality of a schematic maps view of the FRs.

These functions are finally used in an optimization algorithm to generate optimal configurations. The second part of our paper concerns the color assignment of the lines of a metro map. The schematic views for metro maps are used to maximize the transmission of relevant information (lines, metro stops) of network visualizations. Automatic generation of metro maps focuses principally on the physical structure of the network, but less on the color choice which is, nevertheless, an accurate visual discrimination variable. The FR discrimination will increase if close FRs have distant perceptual colors. A random color assignment is not optimal for two reasons: all the colors do not have the same differenciation power and distant FRs are already visually separated and do not need the color differenciation. Hence, we use an algorithm of color generation and color assignment. Our goal is to produce a set of N discriminating colors to assign for N FRs. In order to facilitate the communication between users, we favor colors that can be named in the common color language. The color assignment is an NP complete problem; therefore we use simulated annealing to find an optimal solution [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF].

The remainder of this paper is organized as follows. We first recall the state of the art of metro-like automatic generation. We present a description of a specific activity (Air Traffic Controllers with Flight Route management), and highlight differences with public transportation. We show how we adapted the algorithm of automatic metro map generation by introducing new mathematical cost functions in an optimization process. Then we explain how we create a color set and how we assign it to FRs. Finally, we perform experimentation to assess the views produced.

ATC/metro map comparison

Metro maps are schematic drawings of the underlying geographical network that represents the different stations and metro lines of a metro system [START_REF] Garland | Mr Beck's Underground Map[END_REF]. Ever since the first one was created in 1934 by Beck, the drawing rules have not changed: transport lines are straightened and restricted to horizontals, verticals and diagonals are depicted at 45 degrees (coined as octilinear in [START_REF] Nöllenburg | A mixed-integer program for drawing high-quality metro maps[END_REF]). The scale in crowded downtown areas is larger than in the less dense suburbs in order to create more uniform distances between adjacent stations. In spite of all this distortion, the network topology and the relative position between metro stations must be retained. Metro maps have been tentatively applied to other classes of problems than metro traveling, such as understanding the structure of a thesis, or the sequence of teaching courses [START_REF] Nesbitt | Getting to more abstract places using the metro map metaphor[END_REF].

Automatic generation of metro maps is an active, ongoing research area, with no complete and general solution. The most frequently used methods are to optimize the shape of the networks by considering the mathematical criteria the authors want to maximize [17] [21]. The best results are performed by using metaheuristic techniques such as simulated annealing. The criteria used are essentially based on the direction and bending of the line in order to generate metro maps where lines are as straight as possible and follow octilinear directions. Some methods are focused on specific criteria such as line crossing minimization [START_REF] Bekos | Line Crossing Minimization on Metro Maps[END_REF], or path simplification [START_REF] Merrick | Path Simplification for Metro Map Layout[END_REF]. A related problem is the automatic generation of directions [START_REF] Agrawala | Rendering effective route maps: improving usability through generalization[END_REF]. Though not strictly a metro map, the authors have designed an activity-driven visualization, with multiple kinds of graphics and textual information.

ATCos manage air traffic in an area called a sector, (white area in Figure 1). Airways are the straight segments that planes have to follow (solid and dashed blue lines in Figure 1). Two beacons delimit an airway. A Flight Route is a sequence of airways (example: the route displayed as a thick red line is made up of three segments, and passes over 2 beacons). FRs span multiple sectors, but ATCos only need to know the section of FRs that cross their sector. Each flight has an associated FR. FR are often re-used by companies, either for regular flights (5 per day between Paris and Toulouse for example), or by companies that compete on the same route. With the increase of the traffic some new tasks arise. The first one is the a posteriori analysis of traffic in order to determine the most conflicting Flight Routes and the densest sections (e.g. Flight per hour). The second is a future task for companies. It has been envisaged to ask the companies to book time slots along flight routes in order to optimize the traffic. For these two tasks a geographical representation of the sectors is the most appropriate solution However, direct representation of FRs is note suitable due to their number and to their density in some areas. The exact location of beacons is not compulsory since this task does not require real-time traffic management. Users need an easy-to-read view of flight routes (with a low cognitive workload). In this way, the view produced can be used to understand the structure of the FRs, and to display the traffic density (e.g. by adding a size proportional to the traffic of each section of the FR). By comparing problems and questions in public transportation and ATC, we can see how related they are. A common theory in the field of cognitive psychology is that people think of a path as a sequence of steps [1] [6]. For ATCo, these steps are the beacons [START_REF] Mackay | Reinventing the Familiar: Exploring an Augmented Reality Design Space for Air Traffic Control[END_REF]. We think that schematic map visualization is a promising visualization for ATC. However, the metro map drawing rules used for public transportation cannot directly be applied to the ATC field. The specificity of ATC lies in the following aspects:  Subway stations vs. beacons: stations are spread out to maximize the servicing of an area by public transportation, whereas beacons are very close together. Furthermore, beacon layout is much more heterogeneous than station layout.



The regularity of station spacing: for effective service purposes, metro stations are inherently spaced regularly along a line. Thus, the constraint that equalizes distances between stations modifies only slightly the topology of the network. On the contrary beacons are not spaced regularly along the FR. A constraint that equalizes distances between beacons is not desirable, as it would alter the topology of the network to an excessive extent.  There are more "interchange" beacons than "intermediate" beacons, as a lot of FRs intersect at the same beacon. Metro stations seldom connect more than five lines.  Flight Routes have a lot of crossings compared to subway lines. This is due to the general orientation of airways (East-West and South-North flows).  Flight Routes are numerous and they often share the same sections. When FRs share the same altitude, it is as if metro lines shared the same rails.

These differences lead us to define new specific mathematical rules (cost functions) to produce a schematic maps view of Flight Routes.

Graph optimization

Currently, the visualization of a sector and its FRs is produced manually. There is no significant previous work in the ATC field that tries to automatically produce visualizations of schematic FRs.

The graph of the representation of a sector is constructed from a set of beacons and FRs. A beacon has a name, a center position and a span value that describes the distance between each FR that connects with it. We also need the input and output location of the FR at each given beacon. The W sector (Figure 1) is composed of 19 beacons and 24 FRs. Figure 5 and Figure 7 are representations of FRs before the geographical optimization. As we can see, numerous beacons overlap, and FRs cross so much that it is difficult to follow a specific FR.

Each of the above design constraints can be transposed into mathematical cost functions. Cost functions can be integrated into an optimization algorithm to obtain an optimal schematic maps view with respect to these visual constraints. For ATC metro maps, we consider three major constraints:

Topological closeness: Cost dist

The visual location of each beacon has to be as close as possible to the real beacon location. If the view produced significantly alters the topology, this may create a gap between the mental and physical representation of the ATC sector. In metro maps, metro stations are often inherently evenly spaced, and topological closeness is usually respected even if not constrained. Here, Cost dist exponentially increases with the distance between the real beacon location and its representation. Cost dist is defined as follows:

Where Roughly speaking C dist corresponds to the displacement that is accepted without a penalty and MAX dist is the ratio of the penalty increase when the accepted displacement is reached.

Density: Cost den

As pointed out in the introduction, one major ATC specificity is the high density of beacons in some areas. This density is incompatible with a clear representation. With a given beacon, Cost den increases with the proximity of its neighbors.

Where C den and MAX den are constants respectively fixed to 80 and 6. Roughly speaking MAX den is the minimum distance needed between the beacons. b i , b j B,i ≠ j is the set of all the different beacon couples.

Crossing: Cost cross

Once again, a clear view requires a minimum of overlapping FRs.

Cost cross is the rate of crossing segments. This issue has already been addressed in classical metro map drawing, but in our context this criteria need a stronger optimization.

Algorithm

According to the above considerations, an efficient view must minimize all the previously listed costs. This cost minimization is a complex problem since all these costs are interdependent. Thus this optimization problem is intractable using a deterministic algorithm. Nowadays, the best automatic metro maps are produced with meta-heuristic methods. In this paper, we use a method that is deeply rooted in optimization technique. Simulated Annealing (SA) is a powerful, general, optimization technique [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF]. SA is computationally costly, but this remains acceptable since the time span to produce a schematic maps view is considerably shorter than the lifetime of the visualized FR.

Cooling parameters of Simulated Annealing is tuned to 0.9997.

The algorithm stops when it converges, i.e. 100 steps without increasing the function. The optimization of the sector W took approximately 3 hours on a Mac pro under Linux. This time is acceptable since the maps do not need to be produced interactively.

We minimize the following costs:

Cost phase1 = C*(Cost den +Cost dist )+ Cost cross
Where C is a constant fixed empirically at 5. This minimization is performed by the SA. The SA is based on the notion of neighbor which corresponds, roughly speaking, to a small variation of the current state. In our case, a neighbor of a current visualization is obtained by moving the location of a beacon, changing the span of a beacon or switching the FR order of a beacon. The visualization obtained is the best trade-off between Cost dist and Cost den which are antagonist. Parameters used in Cost dist and Cost den create an area where these costs do not change (e.g. when beacons are not close and not too far from their initial location). In this area, the configuration with the smaller number of crossings is computed.

The initial view of the W sector is presented in Figure 5 and in Figure 7. The geographically optimized view of the W sector is presented in Figure 6 and in Figure 8. We can see that the view is well spaced out. The number of crossings has been lowered. The remaining crossing segments would require too much modification of the topology. Having optimized the geometry of the metro maps, we will now choose and assign the colors associated to each FR.

Placement and map generation assessment

Most metro maps are created by a graphic designer who chooses the appropriate design and color of each metro line. The designer creates a harmonious color set with graphic techniques [START_REF] Ishizaki | Color adaptive graphics: what you see in your color palette isn't what you get![END_REF] [19]

[20] [START_REF] Ware | Color Sequences for Univariate Maps: Theory, Experiments and Principles[END_REF].

In this section we propose a generic method to create color sets based on designers" techniques and previous works [START_REF] Harrower | org: an online tool for selecting colour schemes for maps[END_REF] [11] [START_REF] Moretti | Controlling the complexity of grouped items in colour interfaces[END_REF].

Colors must be as distinguishable as possible. The generation of distinguishable colors in the RGB space is not suitable since Euclidean distance in this space cannot be considered as a perceptual distance. Indeed, color differences in RGB space are not homogenous with the color difference perception of human beings. The only way to set up colors and assess their perceptive distances is to use the findings of the CIE (International Commission of Illumination) [START_REF]A Color Appearance Model for Colour Manage-ment Systems: CIE CAM[END_REF]. The CIE built, with empirical methods, models that describe the chromatic colors, taking into account human visual perception. The CIE L*a*b* model (CIELAB) is a color space that is homogeneous with human perception. The Euclidean distance between two colors, in the L*a*b* space, can be computed with de Delta e 2000 formula. The LCHab color space is the result of the transformation of Lab space in a cylindrical coordinate system. This color space uses three intuitive dimensions: Luminosity, Chroma (i.e., saturation) and Hue. L, C, H dimensions are orthogonal and perceptually uniform. However, the use of the CIELAB model is limited to the RGB gamut (actual displayable colors) of the output device.

With the CIE LCHab, we can easily compute any color set regularly spaced on the circular Hue axis. The division of the hue axis is the cornerstone of the generation of perceptually separated color classes. It is also possible to compute color distance with the Delta e 2000 method, but this is not sufficient. We also want colors with everyday language semantics (this constraint will help users to designate colors and then the routes orally). Constant value of luminosity and hue do not automatically produce colors with a correspondence in the language. To address this issue, we based the extraction of color with the "named colors" experimentations [4] [START_REF] Párraga | Modelling inter-colour regions of Colour Naming Space[END_REF]. Finally, we use the Munsell tables [START_REF] Munsell | A Pigment color System and Notation[END_REF] to extract, with a given luminosity, the available Hue in the « named color » space. The pseudo code presents the extraction of an RGB color set with the number of colors to produce, the color model to use (by default LCHab), the ICC profile of the output device (by default sRGB), the starting angle of the Hue, and the available range. The function namedColorLum returns the best luminosity value for a given hue. The function maxChromaInRGBgamut computes the maximum Chroma (i.e., saturation) in the gamut. Finally, the function LCHcolor2RGB converts the RGB value of an LCH color with the ICC profile. This algorithm could produce a sufficient number of colors, since in practice, a sector contains of maximum of 30 FRs and their corresponding color.

Colors assignments

With a metro map composed of N routes, we can generate, with our color generation algorithm, N visually separable colors. But N! available choices do exist to assign them to the N routes. We need to se up a numerical value that corresponds to a quality level of this color assignment. We want to assign to close routes the most distinguishable color. To compute the color distance we use the Delta e 2000 formula.

In order to compute the distance between lines, we consider lines as discreet points regularly spaced: i.e. l 1 = { Pt 11 ,… Pt 1m }.

The standard distance between two lines is the minimum distance that separates two points of each line. This distance is not suitable regarding the visual perception of distance. For instance, two crossing lines have, with this distance computation, a distance equal to zero, whereas perceptually they are very distinct. Therefore, we define a new distance computation which is close to the perceptual distance between lines:

l 1 = { Pt 11 ,… Pt 1m } et l 2 = { Pt 21 ,… Pt 2q } with m< q 1 , 2 = min ( ( 1 , =1 2 ), = 1 →
In this formula, d is the Euclidean distance between two points. Thus, the distance between the line l1 and l2 is the sum of the minimum distances between each point of l2 and each point of l1.

Finally, we normalize this distance by dividing it by the biggest distance between the lines.

A color assignment is a couple of a line and color couple (l i , C i ). We define the quality of a color assignment as following:

= , × 2 × (1 - 1 1 + -( , )
, , < )

This value corresponds to a weighting mean of Delta e 2000.

The weight of each Delta e 2000 depends of the distance between lines. We apply a sigmoid curve to this distance in such a way that its weight tends towards 1 when the distance tends toward 0 (the case of two close lines), and towards 0 when the distance tends towards 1 (case of distant lines). Thus, the weight of the Delta e 2000 increases when the distance between lines decreases.

Finding the optimal assignment between the N! assignments is an NP complete problem. No deterministic methods can solve it in a reasonable time span. We will therefore use the simulated annealing method which is very efficient for this kind of problem.

In our case, we try to optimize the color assignment. Colors are computed beforehand. The current state is a group a couples [color, line], a neighbor is computed by switching the color of two couples. Cooling parameters of simulated annealing are tuned to 0.9997. The algorithm stops when it converges, i.e. 100 steps without increasing the function.

Optimal or worst color assignment

The optimal view is the Figure 8: it corresponds to optimized geographical positions and an optimized crossing with an optimized color assignment.

We also produced maps with the worst color assignment. Therefore we use the above optimization algorithm with the opposite of the quality function. Thus, the view produced displays close lines with close perceptual colors.

We observe, especially in Figure 8, that the opposite of the cost function produces assignments where close FRs have perceptually close colors. This creates a rainbow effect through FRs. On the contrary, with the original cost function, close FRs are discriminated by colors as expected.

In the next section we assess the views produced.

Experiments

Firstly, we performed a qualitative evaluation by showing the produced schematic maps produced to Air Traffic Controllers. We assessed the extent to which the corresponding sector was easier to recognize and if the view produced was clearer than the original one. As a first result, the optimized geographical views are clearer than the original view and are easier to recognize.

Secondly, we performed a quantitative evaluation to assess the quality of the metro maps produced.

In this experiment, we selected nineteen participants without sight problems (color blind). They were seated facing an 18" video monitor located at a distance of 0.80 m from their head.

The protocol simulates a real use case with a FR schematic maps map: users have to accurately select a specific section of a Flight Route as fast as possible.

Two different color assignments have been tested:

 Optimal color assignment: close FR have distant color,  Worst color assignment: close FR have close color.

We justify our worst color choice (i.e. non discriminating color assignment) as compared to a random color placement, because random can, with serendipity, create a good color assignment (strong discriminating power).

Two different geographical topologies have been tested:  No geographical optimization, which corresponds to the initial view without beacon spacing and with tangled FR,  Geographical optimization, which corresponds to the optimized view, with beacon spacing, and FR crossing optimization (few crossing FR).

We created metro maps of five ATC sectors. Each sector produces four different metro maps:  No geographical optimization with the worst color assignment.

 No geographical optimization with the best color assignment.

 Geographical optimization with the worst color assignment.

 Geographical optimization with the best color assignment.

We also defined three difficulties levels for each section of FR:  Level 1 (easy): the section is located in a non dense area without crossing lines,  Level 2 (medium): the section is located in a dense area with less than 2 crossing sections,  Level 3 (hard): the section is located in a dense area with more than 2 crossing lines.

Then, for each map with extracted 3 sections of each difficulties level (easy, medium, and hard) which represents 9 sections per map.

Each participant had to select 45 sections (5 maps, 9 sections per map) with two kinds of metro map:  The worst color assignment with, and without, geographical optimization, Or  The best color assignment with, and without, geographical optimization.

Each participant performed 90 randomized tries (45 sections with two conditions). The number of maps and the kinds of map (worst colors or optimized color assignment) reduced the learning effect. We recorded the time needed to select a section of a FR (this time record starts when the requested color and the blinking beacons appear) and the correctness of the answer (we counted the number of right or wrong answers).

Procedure

In the view produced, a horizontal straight line (at the top left corner of the view) indicates the requested color (Figure 2). Two blinking beacons indicate the requested section (Figure 2). When the user flies over a section of a FR with the mouse pointer, the fly-over section oscillates indicating that this section can be selected by pressing the mouse (Figure 2).

For each try, the mouse pointer is located over the requested color position (the horizontal straight line); hence the user can memorize the color. The two blinking beacons use the pre-attentive effect [START_REF] Treisman | Preattentive Processing in Vision[END_REF], so the user immediately sees which area must be investigated. Finally, the user has to select the correct section by choosing the requested color between the blinking beacons. The fly-over section is animated; other visual designs were envisaged but they created color distortions: wider line sections, blinking colors.

Figure 2 :

The User"s task is to select the section of a Flight Route between two blinking beacons with a requested color.

Results

All dependent measures were separately analyzed by performing an analysis of variance (ANOVA) with two groups of participants (no geographical optimization, and geographical optimization) and with repeated measurements for two factors: levels of difficulty (easy, medium, and hard) and color assignments (best and worst color).

Concerning the selection time, there was a significant effect regarding the level of difficulty F (2,28)= 45.77 p <.05; the greater the level of difficulty , the longer the selection time is (Figure 3).

In addition, there is an interaction between the level of difficulty and the geographical condition (with or without geographical optimization), F (2,28)= 4.33, p <.05 (Figure 3). The time movement increase, due to the level of difficulty, is less important with the geographical optimized view than with the non geographical optimized one (Fig. 4). Therefore, the geographical optimized view is more efficient (smaller selection time) than the non geographical optimized one.

Initial view

Geographical optimization

1 2 3
Level of difficulty The analysis of the error number yielded a main effect with the level of difficulty F (2,28)= 8.79 p<.05: The number of errors increases when the level of difficulty increases.

In addition, there is an interaction between the level of difficulty and the color assignment conditions (best or worst), F (2,28)= 40.79 p<.05 (Figure 4). The error number increase, due to the level of difficulty, is less with the best color assignment than with the worst one (Figure 4). Therefore, the good color assigned view is more efficient (smaller errors number) than the worst color assigned one.

As expected, the two proposed enhancements (geographical optimization and best color assignments) improve performance in the select a section of a FR.

Conclusion

In this paper, we address a new issue of metro map layout. We present a complete method to produce an efficient layout of aircraft Flight Routes in the ATC context. We turn ATC specific visual constraints into mathematical formulations. The simulated annealing algorithm, with these adapted cost functions, and optimizations, produces visualizations which fulfil the defined constraints. As we use an automatic process, the method allows the generation of schematic maps views for any ATC sector. The automatic generation process is a great asset when sectors or FRs are updated. We also studied the generation and the placement of colors on metro maps in order to enhance the readability of the view. This issue hasn't been extensively studied until now. We proposed a method to generate colors that takes into account their semantics and their perceptual distance with respect to other colors. We defined a cost function that measures the quality of a placement of color on a metro map. This cost function is integrated into an optimization process in order to obtain an optimal view. We validated the produced views with qualitative and quantitative assessments. The geographical optimizations with optimized color views are clearer than the original view, and easier to recognize. The views produced improve the accuracy and speed up the selection of a specific section of a FR.

The proposed method is not specific to the ATC context and can be used for any metro-like visualization.

We plan to use the produced views with Air Traffic Controllers. Two main applications are envisaged. Firstly, we plan to add the traffic density of each FR the view. As a design choice, we plan to use the width of the line or its luminosity. Secondly, we will conduct a design study to use these maps to help companies to reserve time-slots on FR.

Figure 1 :

 1 Figure 1 : a sector (white zone), and a route (red line)

1 /

 1 Topological closeness: it indicates the relative closeness of represented beacons to their original position, 2/ Density: it indicates the number of neighboring beacons, 3/ Crossing: it indicates the number of crossing FRs. Topological closeness is inherited from the classical metro maps. Density and crossing are more specific to the ATC field. Linearity (straight line) and octolinearity (rounded up angle values) are not very pertinent in the ATC context since the direction of a FR changes at each beacon.

  B is the set of beacons, b and b' are respectively the initial and the modified position of the beacon. d(b,b") is the Euclidean distance between b and b". |B| is the cardinal of B. The erf term is the Gauss error function. C dist and MAX dist are constants respectively fixed at 200 and 30 (empirical assignments).

Figure 3 :

 3 Figure 3 : Movement time as a function of the level of difficulty and geographical conditions.

Figure 4 :

 4 Figure 4 : Number of errors in terms of the level of difficulty and color conditions.

Figure 5 :

 5 Figure 5 : View with no geographical optimization and with the best color assignment.

Figure 6 :

 6 Figure 6 : View with geographical optimization and with the best color assignment. This view is the most efficient one.

Figure 7 :

 7 Figure 7 : View with no geographical optimization and with the worst color assignment. This view is the less efficient one.

Figure 8 :

 8 Figure 8 : View with geographical optimization and with the worst color assignment.


Christophe Hurter
email: christophe.hurter@aviation-civile.gouv.fr.

Dsna

Benjamin Tissoires
email: tissoire@cena.fr.

Stéphane Conversy
email: stephane.conversy@enac.fr.

Abstract-In this paper, we describe a set of visualization methods with an accumulation tool to perform interactive data exploration. Accumulation maps or Kernel Density Estimation (KDE) maps, count the amount of data accumulated at a certain location. The accumulation tool addresses the cluttering issues when displaying large amounts of data. But the accumulation tool can also be used to unveil patterns, to detect outliers and flaws in datasets. Through these applied examples, we show how the accumulation tool and its real time applications take advantage of human vision and are therefore assets for data exploration and validation. As the accumulation tool uses GPU techniques, it can be used in real-time with large datasets. Index Terms-Accumulation, Kernel Density Estimation, Information Visualisation, Data exploration, data validation.

INTRODUCTION

Thanks to recent progress in computer power, data storage, and recording technologies, data of various kinds are collected in growing amounts. Analysis of such data is an issue due to their quantity. Users need efficient visualizations to optimize the use of human perception skills, before subsequently speeding up the analysis process. When transforming data into graphical marks, a regular visualization system draws each graphical mark independently of the others: if the last mark to be drawn happens to be at the same position as a previously drawn mark, the system replaces (or merges, when using translucent colors) the pixels in the resulting image. As a result, a lot of cluttering occurs and hinders the data analysis process. Accumulation maps (or their generalization, Kernel Density Estimation (KDE) maps) address the cluttering issue by retaining the number of marks that fill a particular pixel. A typical use of an accumulation map is the so-called "illuminated height map" where users perceive and interpret mountains and valleys as data accumulation values.

In this paper, we explore a geographical and temporal dataset: a oneday record of aircraft positions over France. With the accumulation tool, the produced KDE maps can be used for different purposes:

 pattern detection,  outlier detection,  dataset flaw detection. The remainder of this paper is organized as follows. Firstly, we list relevant previous works referring to accumulation maps. Secondly, we present some applications of the accumulation tool to perform the analysis of a geographical and temporal dataset. Finally, we discuss the product design efficiency and future applications.

RELATED WO RK

The Semiology of Graphics was introduced by J. Bertin [START_REF] Bertin | Graphics and Graphic Information Processing[END_REF]. Visualizations use seven visual variables that form the most basic elements of graphic composition. These are position (the spatial variables), size, value (luminosity), texture, orientation, shape, and hue. Each of these visual variables has a perceptible length which corresponds to the number of distinguishable variations that a visual variable possesses. For instance, size has a theoretical infinite length whereas luminosity has a smaller length than size. Each of these visual variables also has a combination property. A visual variable is associative when its use doesn't alter the perception of other visual variables. For instance position is associative with size, because the user will perceive the same size whatever the position. Large numbers of items with numerous attributes are difficult to display. The use of the popular method of the scatterplot [START_REF] Cleveland | The Elements of Graphing Data[END_REF] is not sufficient to display all the information because of lots of overlapping occurs. Kernel Density Estimation (KDE) maps address the overlapping issue [START_REF] Silverman | Density Estimation for Statistics and Data Analysis[END_REF] of scatterplots. Data distribution is represented by apparent density. KDE is a mathematical method that computes density by smoothing data points to reduce sampling artefacts. Three standard data visualization techniques can be used to visualize KDE maps:

• Color coding. The KDE value is mapped to a colors scale used in turn to fill shapes. These views are also called heat maps • Illuminated height maps, on which users perceive mountains and valleys and interpret them as data accumulation values • Isovalue contours. Contours can be used to show the boundary of specific clusters [START_REF] Van Wijk | Enridged contour maps[END_REF]. Landscape visualizations with hills and valleys have been shown to be "easy" to interpret [START_REF] Van Wijk | Cushion Treemaps: Visualization of Hierarchical Information[END_REF]. The visualization of illuminated height maps is an efficient technique for the scientific visualisation of the scalar functions of two variables [START_REF] Van Wijk | Enridged contour maps[END_REF] : for information visualization [START_REF] Van Wijk | Cushion Treemaps: Visualization of Hierarchical Information[END_REF], and for movement visualization [START_REF] Willems | Visualization of Vessel Movements[END_REF]. KDE map generation is computationally costly; we therefore implemented a GPU KDE map generation with the extension of the data exploration software FromDaDy [START_REF] Hurter | FromDaDy: Spreading Aircraft Trajectories Across Views to Support Iterative Queries[END_REF]. We designed FromDaDy, a trajectory visualization tool that tackles the difficulties of exploring the visualization of multiple trails. This multidimensional data exploration is based on scatterplots, brushing, pick and drop, juxtaposed views and rapid visual design. Users can organize the workspace composed of multiple juxtaposed views. They can define the visual configuration of the views by connecting data dimensions from the dataset to Bertin's visual variables. They can then brush trajectories or KDE maps, and with a pick and drop operation they can spread the brushed information across views. They can then repeat these interactions, until they extract a set of relevant data, thus formulating complex queries

ACCUMULATION TO O LS APP LIC ATIO NS

Our GPU implementation allows direct manipulation and real time animation of KDE maps which extend the accumulation tool features regarding data exploration. In this paper, we present three examples where the accumulation helps to unveil relevant information with the detection of noticeable patterns. In the first example, accumulation helps to detect stationary trails. In the second example, the accumulation reveals a flaw in the dataset. Finally, the last example shows an animated accumulation map which helps to discover outliers.

3.1

Pattern detection This example illustrates how the accumulation tool can be used to detect relevant aircraft trajectories.

With the recording of one day's flights over France, each datum represents the position of an aircraft at a certain time. Such a datum is called a "radar plot". If many aircraft have a similar location (on the screen axes) during the day, shapes representing a plot accumulate. The KDE map (Figure 1) is the result of the accumulation of plots with a triangular kernel. Here, the Latitude and Longitude position of each plot is mapped on the X and Y dimensions of the KDE map and on the X and Y dimensions of the resulting image. KDE values are used as an index in a color map to yield pixel colors. As such, this visualization is a standard colorscale KDE visualization. The image produced shows very dense areas over the main airports in France (Roissy, Orly, Lyon...) which was expected. However, the dense areas exhibit few details. When using accumulation value as "heights" maps and with illumination, circular shapes emerge (Figure 2) that were not noticeable in the first accumulation view (Figure 1): low accumulation values appear as valleys and high accumulation values appear as hills. It is well known that shading works as a gradient detector: it emphasises strong accumulation value variations between adjacent points. This is the reason why these circular hills pop out. To push forward the investigation in order to identify the source of these circular shapes, the user can take advantage of tools provided by FromDaDy [START_REF] Hurter | FromDaDy: Spreading Aircraft Trajectories Across Views to Support Iterative Queries[END_REF].Thus the user brushes the circular patterns, isolates and edits them with "pick and drop". Finally, the user finds out that these circles correspond to stationary trails which are emitted by the radar station which monitors them.

3.2

Data stream failure detection In this example, we use the accumulation as a tool to highlight flaws in the one-day record of aircraft positions dataset. Our main concern is to check the validity of the radar recorded data: radars send data over networks with a constant stream rate (one radar position of each aircraft every 4 to 8 minutes in our dataset) and we want to check that the data stream is not interrupted. Due to the large number of records, a lot of cluttering occurs (Figure 3) when displaying the time series of the aircraft's identifier. The cluttering hides the areas where, during a small time period, no data are recorded. Hence the user is unable to discover this flaw in the database, unless he or she zooms over the specific areas to reduce the cluttering of points, which is unlikely. Here, because during a specific time-span, no data are recorded, the produced accumulation view displays many furrows (Figure 4). Each of these furrows indicates that during the time corresponding to the thickness of furrows no data where recorded. Thus, the accumulation unveils continuous and discontinuous data stream.

Data discontinuities

Figure 4: time series of the incremental number of aircraft (Y axis) over time (X axis) with the accumulation tool

This design is very efficient: since the data stream rate remains roughly constant over time, flaws in the data rate will produce furrows that pop out from the design. Again, the shading magnifies valleys because it acts as an edge detector (like a Sobel or high pass filter). This design helped to identify a flaw in the aggregation algorithm that produced our dataset from eight different sources.

3.3

Outlier detection with an animated histogram In image processing, histograms are a sequence of bars which corresponds to the count of pixels of the same color in the image. If we consider the histogram of the red color of a picture, it is ordered from the lower red intensity to the higher red intensity (Figure 5). Histograms can be considered as an accumulation tool which counts accumulated values over one dimension (in this example, the red color dimension). Until now, we only considered the geographical nature of the dataset. But one-day records of aircraft are geographical and temporal datasets. To explore a geographical and temporal dataset with the accumulation tool, users employed the 2-dimensional (latitude, longitude) accumulation tool with a dynamic filter on the time parameter. The visualization produced is a movie-like animation of traffic density over time.

The sequence of the evolution of the traffic remains roughly the same with records of different days (Figure 7 The result of the animated histogram is not surprising, but it is nonetheless very efficient and "intuitive" to explain the traffic density evolution when shown to users. It gives a basis for further investigation and it is a very good overview of the traffic density and perfectly illustrates Shneiderman's mantra "Overview first..." [START_REF] Shneiderman | The Eyes Have It: A Task by Data Type Taxonomy for Information Visualizations[END_REF].

Nevertheless, when playing the traffic density animation in February 2008, the user noticed an abnormal accumulation. At 2 AM only few aircraft usually fly, but the animation shows that for 2 hours, a heap appears at the French and Belgium border, which is unusual. This heap indicated that many aircraft were flying at the same location for a long period. After a deeper investigation with the standard tools provided by FromDaDy [START_REF] Hurter | FromDaDy: Spreading Aircraft Trajectories Across Views to Support Iterative Queries[END_REF], the user deduced that for 2 hours, 12 aircraft were unable to land due to very bad weather conditions in Belgium. Some of these aircraft waited by performing ellipsis cycle trails (called "stacking" in Air Traffic Controller vocabulary) at various altitudes for two hours until being able to land. In this example, the animation helps practitioners to compare dynamically the evolution of the histogram, thus detecting unexpected information, and producing data analysis.

CONCLUSION AN D DISCUSSION

In this paper, we used accumulation as a new tool to enhance data analysis. The different applications illustrated are:  To detect patterns with the accumulation of stationary points,  To detect flaws in the data base, with the detection of a break in the data rate of aircraft positions,  To illustrate the traffic density evolution over time with a dynamic histogram and to detect outliers (i.e. stacking in Belgium at 2 AM).

We think that the visualizations produced with the accumulation tool are ecological. Ecological design was introduced by Gibson [START_REF] Gibson | The Ecological Approach to Visual Perception[END_REF]. He based his work on human perception regarding the living environment. Gibson thinks that direct (or pre-attentive) perception concerns not only basic visual clues like color or luminosity. High level characteristics, such as invariants and affordances, can also be perceived. Invariants, like grass field texture or atmospheric light filters, help the user to evaluate his distance from perceived objects. Affordances [START_REF] Gibson | The theory of affordances[END_REF] are the relations between a human and his environment and give clues to indicate how an action can be performed.

The accumulation tool and its associated lighting produce furrows and ridges. As a result, the design is ecological since heaps mean more accumulated data and a higher data stream rate, whereas furrows imply less accumulated data and a lower data stream rate.

Hence the interpretation of accumulated data is facilitated because the user is used to managing them. The human perceptual system is attuned to these high-level features: it perceives them directly. We call this kind of representation that improves these features "ecological", or "natural".

Furthermore, the shading can be considered as a new visual variable with associative [START_REF] Bertin | Graphics and Graphic Information Processing[END_REF] properties since the bump mapping will not alter other visual variables. The color is still perceivable even if shading is applied. The shading also enhances the color length because it acts as an edge detector. The shading magnifies the color variation and helps to perceive greater detail.

The accumulation tool and its visualization take advantage of human vision. Therefore, this design is easy to understand and reduces the cognitive workload involved in the analysis and are assets for data exploration and validation.

  Fig. 1. One-day accumulation of aircraft Radar positions over Paris, France

Figure 1 :Figure 2 :

 12 Figure 1: Design configuration and accumulation maps without shading

Figure 3 :

 3 Figure 3: time series of the incremental number of aircraft (Y axis) over time (X axis) To notice this flaw without serendipity, the user can use the accumulation tool with the same design configuration (the visualization of the time series of aircraft identifiers). Continuous data stream over time produces flat accumulation (the same amount of data are accumulated over time), whereas discontinuous data stream produces ridges (increase of the data stream rate) or furrows (decrease of the data stream rate).Here, because during a specific time-span, no data are recorded, the produced accumulation view displays many furrows (Figure4). Each of these furrows indicates that during the time corresponding to the thickness of furrows no data where recorded. Thus, the accumulation unveils continuous and discontinuous data stream.

Figure 5 : 1

 51 Figure 5: 1 Dimension histogram (Red color histogram) A "2-dimensional histogram" represents the accumulation of pairs of values. For instance, a visualisation of semi-transparent aircraft trails (with the latitude and longitude respectively on the screen X and Y axis) is a 2D histogram since color blending creates a color accumulation when trails use the same screen pixel. In Figure 6, dark points represent an area of high accumulation, whereas white areas represent areas with very few trails. A 3-dimensional visualization shows the accumulation value for each latitude/longitude pair (Figure 6, right): instead of mapping the accumulation count on intensity, one can map the accumulation count on height in a 3D visualization of a histogram.

Figure 6 :

 6 Figure 6: a 2 dimensional (latitude, longitude) histogram of aircraft trails with a gray color scale (left) and its visualization in 3D (right).

  ):  from midnight to 5 AM, only a few areas show accumulation (few aircraft,)  from 5 AM to 8 AM only the Paris areas (the main French airport) show accumulation,  from 8AM to 12 noon, various Flight Routes are recurrently salient,  from 12 noon to 1 PM we observe a slowdown in the accumulation value,  from 1 PM to 10 PM, various Flight Routes are recurrently salient,  from 10PM to midnight, only a few trajectories are accumulated.

Figure 7 :

 7 Figure 7: 2D histogram over time


Christophe Hurter
email: christophe.hurter@aviation-civile.gouv.fr

Christian Colongo
email: christian.colongo@isae.fr

Dominique Bernard
email: dominique.bernard@isae.fr

Benjamin Tissoires
email: tissoire@cena.fr

Visual analysis to support exploration of recorded UAV data

Keywords: dataset exploration, information visualization, unmanned vehicle data

Introduction

Thanks to the recent progress in computer power, data storage, and in recording technologies, data of various kinds are collected in growing amounts. This is especially true when dealing with real-time recording of Unmanned Aerial Vehicle (UAV). The analysis of such data is an issue due to their size. The cognitive workload while performing information retrieval, exploration and analysis is usually high. Users need efficient visualization 5 to optimize the use of human perception skills, and then, to speed up the analysis process. The ability of the human being to acquire insight into multivariate data can be immensely enhanced by the opportunity to view data in graphic form. This process is called an externalization because it extracts a mental image into a physical device (often a drawing) 1. The simplest externalization of a multivariate database is a scatterplot. A scatterplot is a two dimensions graph (e.g. speeds of an aircraft on the Y axis and time on the Y axis). It helps to understand the data structure and the relation between data dimensions. The design choices widely influence the externalization quality while, for instance, monitoring UAV parameters 8. This quality is the amount of relevant information that a human can perceive with a graph. The design of a graph is a set of two data dimensions for the two graph axis and a set of visual variable 1 (size, color, texture, shape, orientation). The human acquisition of insight into multivariable data can also be enhanced if user can graphically interact with data. The most efficient manipulation is the direct manipulation since the user interprets visual entities as tangible objects 4. In order to perform an efficient exploration of a dataset, users need tools that support data exploration with easy construction of queries and rapid feedback (response time < 100ms) 11. Dynamic queries 1 have proven its usefulness in meeting these goals. Another important paradigm for the data exploration is the data selection. It allows selecting a sub-set of relevant data. The main problem is to effectively explicit the queries. One powerful technique is the brushing 2. Brushing is an available feature in many data visualization systems. It is a mechanism to interactively select subsets of the dataset so that they become highlighted. Traditionally, brushes have been defined in screen space via methods such as painting and range selection rectangles.

Based on these previous considerations, we have developed FromDaDy 7 (which stands for "FROM DAta to DisplaY"), a visualization tool that tackles the challenge of representing, and interacting with numerous data. FromDaDy employs a simple paradigm to explore multidimensional data based on scatterplots, brushing, pick and drop, juxtaposed views and rapid visual configurations. The fundamental new aspect of FromDaDy compared to existing visualization systems, is to enable users to spread data across views. Together with a finely tuned mix between design customization and simple interactions, users can filter, remove and add data in an iterative manner until they extract a set of relevant information, thus formulating complex queries. Fig. 1. One day's record of traffic over France. The color gradient from green to blue represents the ascending altitude of aircraft (green being the lowest and blue the highest altitude). Thus, the French coastline is revealed here as a consequence of sightseeing in light aircraft and the straight blue lines represent high altitude flight routes.

How does FromDaDy work ?

First, the user select displayed dimension in the database description. Second, the user setup the visual properties based on Bertin's visual variables (position, size, color, shape). Third, the user can interact with the displayed data with the brush, pick and drop paradigm. These simple interactions techniques allow the iterative exploration of a database; hence allow answering complex queries in a multivariate database.

Fig. 2. Link creation and removal.

FromDaDy uses the data flow model, through a tool that enables a user to draw connections between data dimensions and visual variables 4 , thus specifying a visual configuration. For instance, in the left hand image of Erreur ! Source du renvoi introuvable., the user connected the longitude with the X axis of the view and the latitude with the Y axis of the view. The user also connected the altitude field of the database to the color of the lines. The resulting connections produce a vertical representation of a one-day traffic record over France (Fig. 1). The user can also remove a connection by drawing a line that cut an existing connection (Fig. 2). Finally, the user can double-click on axis X or Y of a view to make the field selection menu appear, and change the mapping for that axis (Fig. 3).

Fig. 3: Setup of the axis.

To select a subset, the user uses the brushing technique. Brushing is an interaction that allows the user to "brush" graphical entities, using a size-configurable or shapeconfigurable area which is stuck to the mouse. Each entity touched by the area during the mouse movement is selected (Fig. 4).

Erase Brush Original

Enable Brush Size Change Brush Fig. 4: The brushing interaction allows the user to select trajectories by brushing them with a size configurable tool.

Thanks to the brushing technique, the user can select and highlight part of the displayed data. By hitting the space bar, the user can extract previously selected data and attach them to the mouse cursor (beginning of following figure). By default, the selected data are picked: they are removed from the view, and appear in a "fly-over" view. When the user hits the space bar a second time, a drop occurs in the cell under the cursor. If there is an empty cell under the cursor, the software creates a new view with the selected data. If the user presses the space bar while moving over a cell with an existing view, FromDaDy adds the selected data to this view (Fig. 5).

Impementation

FromDaDy is written in C# with the .net framework 3.0 for the interface implementation and uses DirectX 10 for the GP-GPU usage. The GPU usage is widely inspired from the well-known GPU techniques 6. These techniques mainly consist in the use of the render-to-texture techniques combined with an appropriate fragment and geometry shaders to achieve the collision of the points of the tracks and the brushed area. Thus, FromDaDy can display up to 5 million points in real time (framerates of over 20 FPS) with current generation of computer and a modern graphic card (8800GTX).

analysis of Unmanned Aerial Vehicle recording

Development and improvement of UAV features is an awkward and difficult challenge. This activity requires precise tools and evaluation methods to analyze the UAV parameters. Therefore a huge quantity of data must be monitored and analyzed: servo-controlled loops, speed, altitude, orders, batteries' power, GPS positions.

FromDaDy has already been used to analyze days of recorded aircraft trails.

FromDaDy unveiled unexpected information: radar errors areas, transponders' errors (onboard transmission system that sends the altitude and identification of the aircraft), Radar test points, local hubs (dense areas). In this section, we present results of the produced visualization with FromDaDy when exploring recorded data of an UAV. This will give a good insight of available information and then assess the performance of the flight.

The UAV data

The recorded data are composed of manifold attributes (32 monitored fields). The following table details the most important ones.

Visual analysis

In order to explore the recorded data, we applied the Keim 9 and Shneiderman 12 mantra:"overview first, details on demand". These data contains the recorded UAV positions organized within a sequence of Way Points (WP). The Fig. 6 shows a top view (latitude and longitude) of the recorded positions, with a different color for each WP's segment. This first step in the data exploration is very important since it validates the dataset's integrity: the UAV recorded trail is conform to the actual UAV positions, the location of each waypoints is also visually checked. This overview highlights some trails erroneous behaviors. The UAV performed two positions' overshooting at the second and third WP. Deeper analysis will explain this phenomenon.

In the following images, no scales are displayed, but the user can interactively explore the displayed value since an information box is attached to the mouse pointer and gives the pointed value.

2D graph

With a top view of the UAV trail, the user can use the color to visually code relevant fields of the dataset. For instance, Fig. 7 shows the number of satellites synchronized with the NavSat system. And then the user discovers that during each steering, the number of satellite decreases. When hoovering over the most interesting points of the graph, the user can read the exact values which indicate a minimum of 4 satellites to a maximum of 7 synchronized satellites. This visualization is relevant since it indicates that the UAV can face geographical positioning issues when it changes direction. Further investigation must be done to figure out exactly the reason of this satellite loss.

Less satellites

Time series

The user wanted to investigate the evolution of the altitude during the recording. Therefore the time series of the altitude values over time displays some artifacts. Fig. 9 shows the time series of the recorded altitudes and exhibits strong variation at every WP. The colors scale is the same as in Fig. 6. This time series indicates a quick altitude loss when the UAV passes each WP. This phenomenon is related to the UAV change in direction and the decreasing of its lift. This graph also shows the strong altitude correction which produces oscillations. Fig. 10 and Fig. 9 show that the altitude loss when turning should be anticipated in order to optimize the UAV trail. In the Fig. 6 (the top view), the second WP was overshot. To help understand this behavior, Fig. 11 shows a time series of the distance evolution to each WP. When the UAV reaches each a WP (distance is null), its distance is reset to the distance to the next WP. This distance evolution within the same WP section should be monotone (only decreasing values), but it is not the case.

In the two first WP segments, the distance to the next WP decreases, but in the 2 nd and the 3 rd segment, this distance kept on increasing after the UAV reached the WP. The UAV did not anticipate enough the required steering. The steering actions should have been initiated before the UAV reached a 5 meters distance to the WP. Generally speaking, each recorded dimension must be validated in order to remove outliers and errors. Fig. 12 shows the time series of the evolution of the autopilot orders. It shows numerous errors since the recorded flight was fully automatic. This analysis software allows the user to select them (with the brushing paradigm) and remove them.

Parallel exploration

The graph analysis allows visualizing the threshold detection efficiency. For instance, Fig. 13 shows the real measures of the pitches values and their threshold filtering. This visualization helps to setup correct threshold value.

Mesured UAV pitch Filtered UAV pitch

Correlation

One of the main activities when performing data exploration is seeking fields correlation. To do so, we usually use the matrix scatter plot 2 visualization that displays all the available 2D graph regarding the fields in the Data Base. Since the visual configuration is easy to setup with FromDaDy, the user can very quickly swap from one visual configuration to another. Fig. 14 shows an actual correlation between tet (UAV pitch) and sortie_PWM_camera (the camera pitch). The feedback loop system tries to maintain the embedded camera horizontal; therefore the motor actions (sortie_PWM_camera) must be correlated to the actual UAV pitch, which is the case in Fig. 14.

Fig. 14 : correlation between the UAV pitches and the camera pitches.

Conclusion

FromDady is an accurate, quick and easy to use visualization software. From it, the user can extract a set of relevant information that answers complex queries. This software stems from innovative research and development in the HCI (Human Computer Interaction) and the InfoVis (Information Visualization) fields. It aims at improving the bandwidth between the visualized data and the perceived information.

To do so, it uses a minimalist interface: a desktop with a matrix of cells (views navigation), and a dimension-to-visual variables connection tool (to setup the design of the views). Its interactions are also minimalist: brushing, picking, and dropping. Nevertheless the combination of these interactions enables numerous functions and helps users to quickly setup the visualization and thus speed-up the exploration process.

In this paper, we used FromDaDy as a design configuration tool to produce relevant visualizations. It helps to get insight of the dataset, to find out correlation, outliers, and erroneous data. It also helps to find some tuning in the UAV behavior: anticipation of steering orders. FromDaDy also helps to unveil the wind direction and its alterations on the UAV trail. As a future work, we plan to explore records of multiple trails. This will give a good overview of available information and will help to compare trails, to sort them, thus unveiling unexpected information. Finally we also plan to explore merged data from UAV flight records and human operator with physiological recorded parameters.

Fig. 5 :

 5 Fig. 5: Pick and Drop interaction.

Fig. 6 :

 6 Fig. 6: Single UAV trail with Way Points and optimal trails.

Fig. 7 :Fig. 8 :

 78 Fig. 7 :Top view with a color scale of synchronized satellites. Another interesting visualization is a top view with colors indicating the UAV speed. Since the UAV have a constant pitch, its speed should remain constant. Variations should only occur when steering or adjusting the altitude of the UAV. But Fig. 8 clearly indicates that the UAV had high speed values when going from North to South and low speed values when flying from South to North. This graph clearly indicates that during the recording the wind blew from the North and then altered the UAV trail.

Fig. 9 :

 9 Fig. 9 :Time series of the altitude evolution over time. Color codes the WP numbers.

Fig. 10 Fig. 10 :

 1010 Fig.10shows the same altitude time series, color visually coding motor actions on the elevator. This visualization confirms that too strong actions were performed on the elevator which produces altitude oscillations.

Fig. 11 :

 11 Fig. 11: Time series of the distances evolution to the next WP. Color codes the WP number.

Fig. 12 :

 12 Fig. 12 : Outliers in the autopilot time series. Color codes the WP number.

Fig. 13 :

 13 Fig. 13: Time series of the UAV pitches evolution. Left figure shows the actual pitches values, right figures shows the filtered values (threshold usage).


Stéphane Conversy

Hélène Gaspard- Boulinc

Stéphane Chatty

Stéphane Valès

Carole Dupré

Claire Ollagnon

Supporting Air Traffic Control collaboration with a TableTop System

Keywords: CSCW, tabletop, system design, collaboration, Air Traffic Control ACM Classification H.5.3 Information Interfaces and Presentation: Group and Organization Interfaces;

Collaboration is key to safety and efficiency in Air Traffic Control. Legacy paper-based systems enable seamless and non-verbal collaboration, but trends in new software and hardware for ATC tend to separate controllers more and more, which hinders collaboration. This paper presents a new interactive system designed to support collaboration in ATC. We ran a series of interviews and workshops to identify collaborative situations in ATC. From this analysis, we derived a set of requirements to support collaboration: support mutual awareness, communication and coordination, dynamic task allocation and simultaneous use with more than two people. We designed a set of new interactive tools to fulfill the requirements, by using a multi-user tabletop surface, appropriate feedthrough, and reified and partially-accomplishable actions. Preliminary evaluation shows that feedthrough is important, users benefit from a number of tools to communicate and coordinate their actions, and the tabletop is actually usable by three people both in tightly coupled tasks and parallel, individual activities. At a higher level, we also found that co-location is not enough to generate mutual awareness if users are not engaged in realistic tasks.

INTRODUCTION

The goal of Air Traffic Control is t o maximize t w o properties: safety (avoiding accidents) and capacity (raising the number of manageable flights). ATC is a highly collaborative activity [START_REF] Rognin | Cooperation, reliability of socio-technical systems and allocation of function[END_REF]. Collaboration makes controllers more efficient a n d i s essential for safety. The trustworthiness of the system comes not only from its individual parts (hardware, software, or people), but emerges from the process of checking and crosschecking the activity of teammates [START_REF] Hughes | Faltering from ethnography to design[END_REF]. As with many other activities, various computer systems have been introduced to support ATC. However, most systems introduced have been largely based on single-person paradigms: hence, computerization has been done at the expense of collaboration. Recent hardware advances in multi-touch multi-user tabletop systems enable us to imagine new potential solutions for collaboration support. We designed a set of new interactive tools relying on a multi-user tabletop surface, appropriate feedthrough, and reified and partially-accomplishable actions.

SYSTEM REQUIREMENTS

Based on an analysis of collaborative situations in ATC, we devised a set of requirements for our system. Our primary design goal was to foster s e a m l ess collaboration by requiring less explicit communication and fewer coordination acts. Our main assumption is that better collaboration will yield benefits in terms of capacity and safety. More precisely, the system should… • … enable users to inform the systems with their clearances, which is not possible with current, paperbased systems [START_REF] Mackay | Is paper safer? The role of paper flight strips in air traffic control[END_REF].

• … allow more than two users to interact simultaneously with it. This should allow capacity increases since multiple users will be able to handle tasks concurrently (parallelization)

• … foster mutual awareness. Safety should increase because users will have more means to be aware of teammates' activity and more means to detect problems (more eyeballs). • … foster dynamic task allocation. Capacity should increase because users will be able to pick up new tasks to be done as soon as they have completed existing tasks (workload balancing).

SYSTEM DESIGN

The requirements can be fulfilled if users are aware of tasks to be done, or are able to evaluate workload of their colleague. In addition, it can only be done if any user is allowed to interact with any representation or tools while the other user is engaged in another task. We used a shared, multi-touch, multi-users surface as the basis of our system. Shared surface are supposed to exhibit these properties: users are close to each other, and they enable interacting simultaneously if designed appropriately. We devised the following guidelines to design interactive tools so that they support collaboration:

• Reify actions into objects. Since objects lie on the table, their manipulation may enable accountability [START_REF] Hughes | Faltering from ethnography to design[END_REF]; furthermore, they can be passed around and allow for task reallocation.

• Enable partial accomplishment of actions. An action can be separately prepared, checked and accomplished, possibly by different users, thus offering seamless workload allocation.

• Provide as much as feedback as possible. Since activities must be accountable, it is important that appropriate feedback provide an opportunity for teammates to observe one another's actions.

We also used several guidelines from tabletop and CSCW literature (orientation [START_REF] Kruger | Fluid integration of rotation and translation[END_REF], t e r r i t o r i a l i t y [START_REF] Scott | System guidelines for co-located, collaborative work on a tabletop display[END_REF], t a b l e t o p [START_REF] Hughes | Faltering from ethnography to design[END_REF], direct collaboration [START_REF] Hughes | Faltering from ethnography to design[END_REF] and coupling [START_REF] Hughes | Faltering from ethnography to design[END_REF]). In the following, we mention the guidelines that we applied. We chose not to prevent inter-controller conflicts using technical features; instead, we relied on social norms. We designed several software tools, such as layout-free, orientable strips, editors, Post-it, an extrapolation tool, a timeline, several feedthrough, delayed audio annotation etc.

PRELIMINARY EVALUATION

We have conducted four experiments to evaluate our design choices. The experiments were qualitative and involved a limited number of subjects and trials. As such, they yielded preliminary results only; however, we did make several useful observations. The experiments were not meant to test whether our system is better than current systems in terms of capacity or safety. Rather, they test to what extent the first three requirements we listed above (more than two users, mutual awareness, communication, c o o r d i n a t i o n , dynamic task allocation) are fulfilled. P r e l i m i n a r y evaluation shows that feedthrough is important, users benefit from a number of tools to communicate and coordinate their actions, and the tabletop is actually usable by three people both in tightly coupled tasks and parallel, individual activities. At a higher level, we also found that co-location is not enough to generate mutual awareness if users are not engaged in realistic tasks.

Figure 1 :

 1 Figure 1: hardware and visualization settings

ACKNOWLEDGMENT

The project was funded by Eurocontrol Experimental Center under grant EEC A06/12013BE.