Yana Nehmé
email: yana.nehme@liris.cnrs.fr

Patrick Le Callet
email: patrick.lecallet@univ-nantes.fr

Florent Dupont
email: florent.dupont@liris.cnrs.fr

Jean-Philippe Farrugia
email: jean-philippe.farrugia@univ-lyon1.fr

Guillaume Lavoué
email: glavoue@liris.cnrs.fr

Exploring Crowdsourcing for Subjective Quality Assessment of 3D Graphics

Keywords: crowdsourcing, laboratory, subjective quality assessment, 3D graphics, virtual reality, accuracy

Multimedia subjective quality assessment experiments are the most prominent and reliable way to evaluate the visual quality as perceived by human observers. Along with laboratory (lab) subjective experiments, crowdsourcing (CS) experiments have become very popular in recent years, e.g., during the COVID-19 pandemic these experiments provide an alternative to lab tests. However, conducting subjective quality assessment tests in CS raises many challenges: internet connection quality, lack of control on participants' environment, participants' consistency and reliability, etc. In this work, we evaluate the performance of CS studies for 3D graphics quality assessment. To this end, we conducted a CS experiment based on the double stimulus impairment scale method and using a dataset of 80 meshes with diffuse color information corrupted by various distortions. We compared its results with those previously obtained in a lab study conducted on the same dataset and in a virtual reality environment. Results show that under controlled conditions and with appropriate participant screening strategies, a CS experiment can be as accurate as a lab experiment.

I. INTRODUCTION

Subjective quality assessment experiments are of primary importance for assessing the Quality of user Experience (QoE), understanding human physiological and psychological behavior (perception of multimedia content), benchmarking and tuning objective measures and algorithms. With the growing trend of machine learning, large datasets are needed and are in high demand, which has prompted researchers to invest more in subjective experiments.

Subjective quality assessment experiments have been traditionally conducted in laboratories in a controlled environment and with high-end equipment. In recent years, crowdsourcing (CS) experiments have gained quite a lot of popularity, especially with the development of the internet, and have been an alternative to laboratory (lab) experiments in certain cases, particularly during the COVID-19 pandemic, where participants could not be physically present in the laboratory to carry out tests. CS has been exploited in several fields and for different types of media, such as the evaluation and annotation of images, videos, audio, speeches and documents. CS and lab studies differ considerably in several aspects. (1) A task is performed by an unspecific internet crowd in the former rather than a specific group of people in the latter. Thus, CS enable researchers to access a much larger and more diverse subject pool and build generalized datasets representative of real-life scenarios. [START_REF] Redi | When the crowd challenges the lab: Lessons learnt from subjective studies on image aesthetic appeal[END_REF] Experiments conducted in a lab environment typically last around 20-30 minutes [START_REF]Methodology for the subjective assessment of the quality of television pictures BT Series Broadcasting service[END_REF], while CS experiments should be kept as short as possible. Indeed, previous works [START_REF] Redi | When the crowd challenges the lab: Lessons learnt from subjective studies on image aesthetic appeal[END_REF]- [START_REF] Reimann | Teaching Data-driven Video Processing via Crowdsourced Data Collection[END_REF] pointed out that a CS task should last 5-10 minutes to avoid participants' boredom, frustration and decreased attention, leading to unreliable behavior and results.

(3) Regarding time-effort, CS experiments are dramatically less time-consuming than lab tests, especially when evaluating large datasets. (4) Last but not least, lab experiments allow better control of the study setup, while CS experiments are carried out in uncontrolled test environments (different viewing conditions that affect participants' perception of quality, e.g. lighting, bandwidth constraints, display device, distance between the participant and the viewing screen, etc.).

As a result, CS imposes several challenges to overcome compared to similar lab tests, notably those related to the lack of control over the participants' environment and the trustworthiness of the participants since they are not supervised in these tests. A thorough overview of these concerns can be found in [START_REF] Hoßfeld | Best practices for qoe crowdtesting: Qoe assessment with crowdsourcing[END_REF], [START_REF] Ghadiyaram | Massive online crowdsourced study of subjective and objective picture quality[END_REF]. To detect and deal with malicious/unreliable participants, several mechanisms have been proposed over the years [START_REF] Hoßfeld | Best practices for qoe crowdtesting: Qoe assessment with crowdsourcing[END_REF], [START_REF] Vuurens | How much spam can you take? an analysis of crowdsourcing results to increase accuracy[END_REF], [START_REF] Li | A probabilistic graphical model for analyzing the subjective visual quality assessment data from crowdsourcing[END_REF]. Despite these challenges, CS studies are still capable of producing accurate and reliable results if the experiment framework has been properly designed [START_REF] Chen | A crowdsourceable qoe evaluation framework for multimedia content[END_REF], [START_REF] Ribeiro | Crowdsourcing subjective image quality evaluation[END_REF].

Regarding the experimental methodologies used in crowdsourcing, most CS studies have used the pairwise comparison (PC) method as it is straightforward: the task of choosing one of the two stimuli is simpler than rating them on a discrete or continuous scale [START_REF] Chen | A crowdsourceable qoe evaluation framework for multimedia content[END_REF], [START_REF] Huang | Ranking individuals by group comparisons[END_REF], [START_REF] Søgaard | On subjective quality assessment of adaptive video streaming via crowdsourcing and laboratory based experiments[END_REF]. Other works have adopted the Absolute Category Rating (ACR) method [START_REF] Jiménez | Influence of number of stimuli for subjective speech quality assessment in crowdsourcing[END_REF], [START_REF] Ribeiro | Crowdsourcing subjective image quality evaluation[END_REF].

978-1-6654-3288-7/21$31.00©2021 IEEE Available crowdsourcing frameworks already implement these methods and offer the possibility of modifying them to fit the needs of the study. A detailed overview of the crowdsourcing frameworks and an evaluation of them is provided in [START_REF] Hoßfeld | Survey of web-based crowdsourcing frameworks for subjective quality assessment[END_REF].

In this work, we investigated the accuracy and reliability of CS studies to assess the quality of 3D graphics. Thus, we conducted a CS experiment based on the Double Stimulus Impairment Scale (DSIS) method, which is, to the best of our knowledge, one of its first uses in CS studies. We used a dataset of animated 3D models [START_REF] Nehmé | Comparison of subjective methods for quality assessment of 3d graphics in virtual reality[END_REF]. The results of this experiment were compared to those obtained from a previous lab experiment conducted in a Virtual Reality (VR) environment. The design of the CS experiment is detailed in section 2, while its results are presented in section 3. Note that, the only 3D representation used in this work is meshes, however, we believe that our results remain valid for other 3D representations, such as point clouds, hence the use of the term "3D graphics".

II. CROWDSOURCING EXPERIMENT

A crowdsourcing (CS) experiment has been carried out in which subjects were recruited to assess the quality of an animated 3D graphics dataset. Since our goal is to compare the results of this experiment to previously collected Lab results [START_REF] Nehmé | Comparison of subjective methods for quality assessment of 3d graphics in virtual reality[END_REF], we replicated the lab experiment as much as possible, using the same instructions, dataset and subjective evaluation methodology. This section provides details on the CS experiment.

A. Dataset

The 3D graphic stimuli used in this study were previously used in the laboratory based subjective experiment, reported in [START_REF] Nehmé | Comparison of subjective methods for quality assessment of 3d graphics in virtual reality[END_REF]. This dataset contains 80 animated meshes with diffuse color information. It was generated from 5 source models ("Aix", "Ari", "Chameleon", "Fish", "Samurai"), corrupted by 4 types of geometry and color distortion that represent common simplification and compression operations: Uniform geometric quantization (QGeo), Uniform LAB color quantization (QCol), simplifications that take into account either the geometry only (SGeo) or both geometry and color (SCol). Each distortion was applied with 4 different strengths adjusted manually in order to cover the whole range of visual quality from imperceptible to high levels of impairment. The source models as well as examples of distortions are illustrated in [START_REF] Nehmé | Comparison of subjective methods for quality assessment of 3d graphics in virtual reality[END_REF].

B. Experimental procedure

In order to be able to compare the results of the CS and lab studies, we opted for the same setup as implemented in the lab experiment [START_REF] Nehmé | Comparison of subjective methods for quality assessment of 3d graphics in virtual reality[END_REF]: the stimuli were animated with a slow rotation (of 15 • around the vertical axis in clockwise and then in counterclockwise directions) and displayed in a neutral virtual room (light gray walls) under the same viewpoints as those used in the lab experiment. Their material type complied with the lambertian reflectance model, and they were visualized without shadows and under a directional light.

The subjective testing methodology used in CS is also the same as the lab experiment, namely the Double Stimulus Impairment Scale method (DSIS), in which observers see the reference model and the same model impaired, simultaneously, side by side, for 10 sec and rate the impairment of the second stimulus in relation to the reference using a five-level impairment scale, displayed after the presentation of each pair of stimuli. Thence, we generated videos of the final rendered dynamic stimuli. The videos were all in 650 x 550 resolution (so that the videos of the reference and degraded models fit simultaneously on a screen with a minimum resolution of 1920 x 1080) with a frame rate of 30 fps and encoded using H.264 encoder (mp4 container) at a bitrate of 5 Mbps to ensure imperceptibility of compression artifacts. The duration of the videos is 10 sec, which corresponds to the display time of the models in the lab experiment.

To conduct the crowdsourcing subjective experiment, a web-based platform was developed suitable for presenting videos according to the DSIS method. It does not require the participants to install any software on their device (except a web browser with an H.264/AVC decoder). The platform first checks the screen resolution of the participants (must be equal to or higher than 1920 x 1080) as well as the page zoom level and ask them to keep the full screen mode until the end of the experiment. Otherwise, they are not allowed to proceed in the test. Once the device's compatibility has been verified, the test instructions are displayed to the participants. At the bottom of this page is a progress bar showing the status of the loading process of all the video pairs that will be used in the test. When the loading is completed a start button appears leading to the test. In this way, the videos of the reference and distorted models are ensured to be played simultaneously without any latency or unintended interruptions.

The experiment starts with a training, during which observers familiarize themselves with the task [START_REF]Methodology for the subjective assessment of the quality of television pictures BT Series Broadcasting service[END_REF]. We selected the same training model used in the training of the lab experiment as well as its distorted versions which cover the whole range of distortions. After displaying each pair of training videos for 10 sec, the rating interface is displayed for 5 sec and an example score assigned to this distortion is highlighted. Once the training is completed the actual test starts. The videos of the stimuli are displayed in a random order (3D models, distortion types and levels all mixed) to each participant. Each video/stimulus is presented once; participants are not able to replay the videos. Moreover, participants are not able to provide their score unless the videos have been played completely. There is no time limit for voting and videos of the stimuli are not shown during that time. At the end of the experience, participants will receive unique codes allowing them to get their remuneration. Figure 1 illustrates the graphical interface of our CS experiment.

C. Test sessions and participants

As stated in the introduction, CS experiments should be kept as short as possible to keep participants motivated and to avoid unreliable results. Therefore, we divided our dataset of 80 stimuli into 4 groups, called playlists (i.e. 20 stimuli/playlist), and each participant evaluates one playlist of the dataset. The stimuli were distributed evenly across the playlists so that each playlist contained the 5 source models and the 4 distortion types and strengths. Furthermore, as this database encloses the subjective scores obtained in the lab test, we opted to distribute the stimuli between the playlists so as to have the same Mean Opinion Scores (MOSs) distribution in these playlists.

Since participants in CS cannot be supervised, it is important to ensure the quality of annotations by detecting unreliable and malicious participants. To do so, there are 3 common/popular strategies [START_REF] Sorokin | Utility data annotation with amazon mechanical turk[END_REF]. The first one, known as gold standard, is the insertion of dummy stimuli or stimuli with trusted annotations. The second strategy (a.k.a consistency question) is to collect multiple scores for repeated stimuli, which allows to assess participant's consistency, while the third strategy is a grading task in which a participant looks at several annotated images and scores every annotation. Inspired by the first and second strategies and as in [START_REF] Ghadiyaram | Massive online crowdsourced study of subjective and objective picture quality[END_REF], we injected 3 trapping stimuli, that we called golden units, into the playlists of our test. They consisted of (1) a very poor quality stimulus (high level of impairment), (2) a very high quality stimulus (the reference is compared to itself) and (3) a stimulus displayed twice to assess the participant's consistency (coherence of his/her scores). Participants who fail to answer the golden units correctly are considered outliers and their scores are rejected (more details in section IV-A).

Thus, the test session of our CS experiment is constituted of 23 pairs of videos to rate (1 playlist) and lasts about 10 minutes: informed consent + loading videos + instructions + 6 training stimuli x (10s video length + 5s Rating) + 23 test stimuli x (10s video length + ∼ 4s Rating).

We ran our experiment until each playlist was fully rated by 60 participants, which required approximately 12 hours. A total of 240 participants took part in this study: 148 males and 92 females. They were from 33 different countries and aged between 18 and 68. All participants were naive about the purpose of the experiment. Note that, participants who started the experiment and did not complete it (101 participants) were discarded. The recruiting process of the participants was performed using Prolific 1 , an internet marketplace that provides 1 https://www.prolific.co/ tens of thousands of trusted participants. Only participants having a high reliability score (score based on how well they did in past studies) and an adequate number of duly completed jobs (number that reflects their familiarity with the platform) on Prolific were admitted to the experiment.

III. LAB EXPERIMENT

We have previously conducted a lab experiment using this dataset to assess the perceived quality of 3D graphics in virtual reality (VR) [START_REF] Nehmé | Comparison of subjective methods for quality assessment of 3d graphics in virtual reality[END_REF]. The experiment was based on the DSIS method and conducted in a VR environment, using the HTC Vive Pro headset. Stimuli, animated with the same slow rotation as the CS test, were rendered for 10 seconds in a virtual scene at a fixed distance from the observer and rotated in real time. The study involved 30 participants: students and professionals at the University of Lyon. Each participant evaluated the whole dataset (80 stimuli) in one session that lasted about 23 minutes. The rating scores collected in the lab experiment are compared to those obtained in the CS experiment in the following section.

IV. RESULTS AND COMPARISON OF EXPERIMENTS

This section presents the results of the crowdsourcing experiment described above and compares them to the lab results in terms of accuracy, confidence intervals, and participants' agreement. For the subsequent analyses, subjective scores ranging from very annoying to imperceptible are mapped on a discrete numerical scale from 1 to 5. Note that the scores assigned to the golden units are only taken into account in observers screening and are not considered in the rest of the analyzes.

A. Participants screening

Before starting any analysis, it is necessary to identify and remove outliers which could affect the accuracy of the results. The participants of the lab experiment were filtered according to the ITU-R BT.500-13 recommendation [START_REF]Methodology for the subjective assessment of the quality of television pictures BT Series Broadcasting service[END_REF]. We found 1 outlier (i.e. 29/30 subjects remain).

For the CS study, as recommended in [START_REF] Hoßfeld | Best practices for qoe crowdtesting: Qoe assessment with crowdsourcing[END_REF], participants were screened by combining: (1) the ITU-R BT.500-13 screening procedure, which revealed 7 outliers among the 240 participants and (2) the golden units analysis (trapping stimuli): we found that 4 participants incorrectly rated the very poor quality stimulus (i.e. its distortion is rated as imperceptible or perceptible but not annoying), 2 participants misjudged the very high quality stimulus (i.e. its distortion is considered very annoying or annoying; however, this stimulus is not degraded.), and lastly, 1 participant gave inconsistent scores to the third golden unit, called G (i.e.

s Grep1 i -s Grep2 i ≥ 3,
where s G i denotes the score assigned by participant i to stimulus G, shown twice rep1 and rep2). As a result, a total of 7 participants failed to rate the golden units, 3 of which were detected by the ITU-R BT.500-13 screening procedure. Thus, 11 participants were rejected (ITU-R outliers Golden units outliers), i.e. 229/240 subjects remain. After outliers removal, each stimulus is rated by 29 participants in the lab test and by at least 56 participants in CS test. Only the scores of these screened participants will be used in our subsequent analyzes.

B. Resulting MOSs

In order to analyze the results of the CS experiment, we computed for each stimulus the Mean Opinion Score (MOS), rating scores averaged over all participants. We compared them to those obtained from the lab experiment. Figures 2,3 Figure 2 shows that the MOS results of the CS experiment strongly correlate with those of the lab test. Indeed, the (Pearson, Spearman's rank) correlation coefficients between CS's and lab's MOSs are (0.975, 0.954). Overall, no significant difference was found between the MOS means of the 2 studies (p-values = 0.191).

For both the lab and CS experiments, MOSs decrease as distortions strengths increase. However, we can notice some differences in the distribution of the scores and the use of the rating scale in the 2 experiments (see Figures 2 and3): overall, the stimuli rated in the lab scored lower than those in CS. This effect is more visible for high strength distortions (strengths ≥ 3), meaning that the lab test participants were able to detect some distortions that the CS participants missed. Indeed, the lab test was conducted in a VR environment. Therefore, we believe that detecting visual quality losses of stimuli is easier in VR than on a 2D screen (CS), since VR headsets provide a bigger/wider field of view (FoV) than a desktop setup and so the size in terms of visual angle of objects in VR is considerably larger than on screen (the stimuli size is approximately 37 and 18 degrees of visual angle in VR and on-screen, respectively).

C. Confidence intervals

Since participants in a CS experiment are not supervised, the evaluation of confidence intervals (CIs), i.e. the dispersion of individual scores, is particularly important. We therefore calculated the 95% CIs of the MOSs for the CS study and compared them to those obtained in the lab test. We assessed the evolution of the CIs width according to the number of ratings collected per stimulus (which is indirectly related to the number of participants involved in the test). Thus for each stimulus, we considered all possible combinations (without repetition) of N ratings and averaged the width of the CIs over all these ratings combinations. N ∈ [START_REF]Methodology for the subjective assessment of the quality of television pictures BT Series Broadcasting service[END_REF]29] and [START_REF]Methodology for the subjective assessment of the quality of television pictures BT Series Broadcasting service[END_REF]56] for the lab and CS test, respectively. Results are shown in Figure 5. Overall, for a given number of ratings, the CIs of the lab test are slightly larger than those of the CS test. This difference is not significant, according to the results of the t-tests (at a level of significance of 5%). Thus, both studies showed similar agreement between the participants' scores. Participants' agreement is further explored in section IV-E.

D. Accuracy of subjective scores

We investigate, in this section, the accuracy (discrimination ability) of the CS test and compare it to that of the lab test. A more accurate test should yield in a larger number of pairs of stimuli whose quality can be considered different in a statistical test. As in [START_REF] Nehmé | Comparison of subjective methods for quality assessment of 3d graphics in virtual reality[END_REF], we conducted two-samples Wilcoxon tests between rating scores of each possible pairs of stimuli and computed the percentage of pairs of stimuli rated significantly different (p-value < 0.05) among all the possible pairs (80 × 79/2 = 3160 pairs). Similar to the previous subsection, we evaluated the evolution of accuracy as a function of the number of ratings per stimulus: for a given stimulus and number of ratings N , we averaged the number of pairs of stimuli rated significantly different over the possible combinations of ratings. Figure 6 shows the results. Ratings of the lab test are slightly more accurate than those of the CS test. For instance, at least 17 rating scores per stimulus (equivalent to 17 participants) are needed in the lab experiment to achieve accuracy with an overall level of 70%, whereas this number increases to 19 ratings in the CS experiment (corresponding to at least 76 participants in our actual CS test setup). Although there was no significant difference between the CIs of the 2 experiments (see section IV-C), the lab study produces slightly more accurate results, as the lab participants used the rating scale better (as shown in section IV-B).

Regarding the overall trend of the curves and despite this slight difference in the accuracy, the DSIS method offers consistent performance in the lab and CS experiments.

E. Participants' agreement / consistency

In this section, we evaluate the agreements between the participants. To do this, we evaluated the internal consistency of participants' data, as proposed by [START_REF] Ghadiyaram | Massive online crowdsourced study of subjective and objective picture quality[END_REF]. For each stimulus, we randomly split the participants who rated it into two equal size groups and computed the Spearman's rank correlation between the MOSs of the 2 groups. After 500 splits, the range of correlations was between 0.94 and 0.978 (with a mean of 0.963) in the CS experiment, and between 0.898 and 0.965 (with a mean of 0.934) in the lab experiment. Results show a high degree of inter-subject agreement in both experiments. This agreement is slightly lower in the lab experiment, possibly due to its more complex immersive viewing environment. This is in line with the CIs being slightly larger in the lab test (see section IV-C).

F. Content ambiguity

As stated in [START_REF] Li | Recover subjective quality scores from noisy measurements[END_REF], some contents tend to be more difficult to rate than others. This is known as "Content ambiguity" and can be estimated by the Maximum Likelihood Estimation (MLE) model [START_REF] Li | Recover subjective quality scores from noisy measurements[END_REF]. Therefrom, we computed the ambiguity values of the 5 source models that constitute our dataset. Since the content ambiguity obtained by the MLE model [START_REF] Li | Recover subjective quality scores from noisy measurements[END_REF] depends on the participants, we considered the same number of rating per stimulus (N = 29) for the lab and CS experiments in order to be able to compare their results. Thus, for the CS experiment, we randomly selected 100 combinations of 29 ratings for each stimulus. We averaged the ambiguity values over these combinations of ratings. Figure 7 shows that all the source models are more ambiguous in the lab experiment than in the CS experiment. This may be because in VR, due to the larger FoV (as explained in section IV-B), participants can see more details and low-level features, which makes the task of assessing the differences between the reference and the distorted stimulus more difficult. The Chameleon model is associated with the highest content ambiguity in both experiments.

Content ambiguity is related to the dispersion of subjective scores (CIs). Therefore, we averaged the CIs of the stimuli over the models. For both experiments, we obtained the same shape of curves as in Figure 7, meaning that models with high CIs are also associated with high ambiguity values.

V. DISCUSSION

We designed a subjective experiment for assessing the quality of 3D graphics in crowdsourcing (CS). The experiment was based on the DSIS method. Since in CS experiment, participants are unsupervised, we sought to impose controls on several aspects: (1) we used the Prolific platform which is more selective in recruiting and filtering participants than other similar platforms such as Mturk, Microworkers, etc. (2) We pre-screened participants during the recruiting process based on their reliability score on this platform. (3) We tried to control the viewer's environment as much as possible (e.g. minimum screen resolution required, maintain a full screen mode, limited interactions to rating). Finally, (4) we combined different screening strategies to identify outliers. The results of this experiment were compared to results collected from a previous lab experiment conducted in a VR environment.

Results showed that under controlled conditions and with a precise/proper participant screening/filtering approach, a CS experiment can be as accurate as a lab experiment. Indeed, we obtained a high correlation between the mean opinion scores of the 2 experiments as well as a good agreement between the participants' ratings (CIs). This agreement was slightly lower in the lab test which can be due to the VR environment. Our findings corroborate previous studies, by [START_REF] Ghadiyaram | Massive online crowdsourced study of subjective and objective picture quality[END_REF], [START_REF] Ribeiro | Crowdsourcing subjective image quality evaluation[END_REF], [START_REF] Søgaard | On subjective quality assessment of adaptive video streaming via crowdsourcing and laboratory based experiments[END_REF], which also achieved high correlation with the lab results, and furthermore, they highlight the quality of the Prolific participants involved in our CS study, their reliability and seriousness despite the fact that the participants were not supervised. It is worth mentioning that the golden units approach we implemented seems to work well. In fact, all the outliers detected by the inspection of golden units were found to have a high inconsistency according to MLE model [START_REF] Li | Recover subjective quality scores from noisy measurements[END_REF]. Regarding the experimental methodology, DSIS seems accurate and adapted for evaluating the quality of 3D graphics in crowdsourcing. We believe that this due to the fact that this method presents explicit references which simplifies the task and makes it easier: according to a short questionnaire asked at the end of our CS test, 89% of the participants found the experiment's instructions clear and 94% rated the work as easy.

In term of time-effort, it took us 12 hours to collect all the data in the CS experiment (5520 quality judgments collected), compared to 36 hours in the lab experiment (2400 quality judgments collected). Crowdsourcing is quite faster. It is frequently used to evaluate large datasets, which requires weeks of laboratory evaluations. However, building and designing our CS experiment tool was a time-intensive task and required significant software development effort (both technical and of conceptual challenges). Furthermore, as stated earlier, the CS experiment must be short to keep participants accurate and consistent, making our CS test require additional programming effort to implement a tool that evenly divides the dataset into batches/playlists and assigns a different batch to each participant.

VI. CONCLUSION

In this work, we investigated how crowdsourcing could be used for quality assessment of 3D graphics. CS experiments based on the DSIS method appear to be a promising way not only to quickly collect a large amount of realistic quality judgments, but also to provide (when combined with appropriate participant screening strategies) accurate and reproducible results. We expect our findings to help the scientific community when designing subjective quality assessment studies in CS. Further experiments are still needed to find the best compromise between the number of stimuli, the duration of the test and the accuracy of the results. Also, it would be very interesting to repeat the same experiment in the lab, this time using a desktop setup, to clearly isolate the effects of VR.

Fig. 1 .

 1 Fig. 1. The display interface based on the DSIS method (left) and the rating interface (right) of our CS experiment.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Comparison of the mean opinion scores of the lab and CS experiments, for all the stimuli. Results are grouped by source models and types of distortion.

Fig. 4 .

 4 Fig. 4. Boxplots of MOSs obtained for the lab and CS experiments.

Fig. 5 .

 5 Fig. 5. Variation of CIs according to the number of ratings per stimulus in the CS and lab experiments. ns and (*) refer to not statistically significant (p-value ≥ 0.05) and 0.01 ≤ p-value < 0.05, respectively.

Fig. 6 .

 6 Fig.6. Variation of the accuracy according to the number of ratings per stimulus for the CS and lab experiments. The accuracy (y-axis) is defined as the percentage of pairs of stimuli whose qualities were assessed as statistically different. Curves represent mean values of these percentages and areas around curves represent 2.5th -97.5th percentiles.

Fig. 7 .

 7 Fig.7. Content ambiguity of each source model associated its CI (calculated as described in[START_REF] Li | Recover subjective quality scores from noisy measurements[END_REF]), for the CS and lab experiments.

This work was supported by French National Research Agency as part of ANR-PISCo project (ANR-17-CE33-0005).


Thibault Lehouillier
email: thibault.lehouillier@polymtl.ca

Jérémy Omer
email: jeremy.omer@polymtl.ca

François Soumis
email: francois.soumis@polymtl.ca

Guy Desaulniers
email: guy.desaulniers@polymtl.ca

A New Variant of the Minimum-Weight Maximum-Cardinality Clique Problem to Solve Conflicts between Aircraft

Keywords: Air Traffic Control, Conflict Resolution, Maximum Clique, Mixed Integer Linear Programming

In this article, we formulate a new variant of the problem of finding a maximum clique of minimum weight in a graph applied to the detection and resolution of conflicts between aircraft. The innovation of the model relies on the cost structure: the cost of the vertices cannot be determined a priori, since they depend on the vertices in the clique. We apply this formulation to the resolution of conflicts between aircraft by building a graph whose vertices correpond to a set of maneuvers and whose edges link conflict-free maneuvers. A maximum clique of minimal weight yields a conflict-free situation involving all aircraft and minimizing the costs induced. We solve the problem as a mixed integer linear program. Simulations on a benchmark of complex instances highlight computational times smaller than 20 seconds for situations involving up to 20 aircraft.

Introduction

Developing advanced decision algorithms for the air traffic control (ATC) is of great importance for the overall safety and capacity of the airspace. Resolution algorithms for the air conflict detection and resolution problem are relevant especially in a context of growing traffic, where capacity and safety become an issue. Indeed, a simulation-based study performed by Lehouillier et al. [START_REF] Lehouillier | Interactions between operations and planning in air traffic control[END_REF] shows that the controllers in charge of the traffic in 2035, which will have increased by 50%, would have to solve on average 27 conflicts per hour in a busy sector.

Maintaining separation between aircraft is usually referred to as the air conflict detection and resolution (CDR) problem. A conflict is a predicted loss of separation, i.e., when two aircraft are too close to each other regarding predefined horizontal and vertical separation distances of 5NM and 1000ft respectively. To solve a conflict, the controllers issue maneuvers that can consist of speed, heading or altitude changes. Given the current position, speed, acceleration and the predicted trajectory of a set of aircraft, the CDR problem corresponds to identifying the maneuvers required to avoid all conflicts while minimizing the costs induced.

The CDR problem is one of the most widely studied problems in air traffic management. For a comprehensive coverage of the existing literature, the reader may refer to the review in Martìn-Campo thesis [START_REF] Campo | The collision avoidance problem: methods and algorithms[END_REF]. Exact methods include optimal control, which can be associated with nonlinear programming. However, these methods suffer from the sensitivity to the starting point of the resolution and the high computational time. Mixed integer linear and nonlinear programming (MILPs and MINLPs) techniques are often considered. Omer and Farges [START_REF] Omer | Hybridization of nonlinear and mixed-integer linear programming for aircraft separation with trajectory recovery[END_REF] present a time-discretization of optimal control. Omer [START_REF] Omer | A space-discretized mixed-integer linear model for air-conflict resolution with speed and heading maneuvers[END_REF] also develops a space discretization using the points of interest for the conflict resolution. Pallottino et al. [START_REF] Pallottino | Conflict resolution problems for air traffic management systems solved with mixed integer programming[END_REF] develop MILPS solving the problem with speed changes and constant headings or with heading changes and constant speeds. Alonso-Ayuso et al. [START_REF] Alonso-Ayuso | Collision avoidance in air traffic management: a mixed-integer linear optimization approach[END_REF] develop a MILP that considers speed and altitude changes. However, MINLPs suffer from high computational times and do not give any optimality guarantee in finite time. Besides, the hypotheses made in MILPs to have linear constraints may not work il all situation. Several heuristics were developed to find a solution rapidly. Examples of techniques developed include ant colony algorithms like in Durand and Alliot [START_REF] Durand | Automatic aircraft conflict resolution using genetic algorithms[END_REF], variable neighborhood searches (see Alonso-Ayuso et al. [START_REF] Alonso-Ayuso | A vns metaheuristic for solving the aircraft conflict detection and resolution problem by performing turn changes[END_REF]). Other fast methods include particle swarm optimization, prescribed sets or neural networks. Heuristics find a solution rapidly, but the hypotheses can be restrictive and the convergence is not guaranteed. Graph theory is seldom used in ATC. Generally, conflicts between aircraft are modeled by a graph whose vertices represent the different aircraft and whose edges link pairs of conflicting aircraft, like in Vela [START_REF] Vela | Understanding conflict-resolution taskload: implementing advisory conflict-detection and resolution algorithms in an airspace[END_REF]. Barnier and Brisset [10] assign flight levels to aircraft with intersecting routes by looking for maximum cliques in a graph where a proper coloring of the vertices defines an assignment of all aircraft to a set of flight levels.

The model presented in this article uses the concept of a clique in a graph, which is a subset of the vertices where each pair of elements is linked by an edge. Finding a maximum clique in an arbitrary graph is a well-known optimization problem that is N P-hard. The problem has been thoroughly studied and several methods, both exact and heuristic, have been developed. For a comprehensive coverage on the subject, one can refer to Bomze et al. [START_REF] Bomze | The maximum clique problem[END_REF] and Hao et al. [START_REF] Wu | A review on algorithms for maximum clique problems[END_REF].

We formulate the air conflict detection and resolution problem as a new variant of the problem of finding a maximum clique of minimum weight in a graph. To this end, we build a graph whose vertices represent a set of possible maneuvers and where a clique yields a conflict-free solution involving all the aircraft. On the one hand, our model is innovative due to the cost structure for the vertices. With this model, we can maintain a reasonable size for the graph built, hence reducing the computational time. On the other hand, our model significance relies on its flexibility: a modification of the problem constraintes or objective function do not jeopardize the validity of the mathematical framework developed. Being flexible is critical in ATC: in addition to being able to cover more ground, it will allow meaningful comparisons with existing models in the literature.

Problem Formulation

Modeling aircraft dynamics

To model the flight dynamics, we use the three-dimensional point-mass model presented in the BADA user manual [START_REF]User manual for the Base of Aircraft Data (BADA)[END_REF]. Aircraft follow their planned 4D trajectory, which is a sequence of 4D points requiring time and space accuracy, leaving the remainder of the trajectory almost unconstrained. The non-compliance with this contract costs penalty fees to companies. As a consequence, an aicraft needs to recover its initial 4D trajectory after performing a maneuver. We assume that the planned speed for an aircraft corresponds to its nominal speed, i.e., the speed minimizing the fuel burn rate per distance unit traveled using the model described in [START_REF]User manual for the Base of Aircraft Data (BADA)[END_REF].

Maneuvers are performed dynamically as described in [START_REF] Paielli | Modeling maneuver dynamics in air traffic conflict resolution[END_REF], where the author states that the typical acceleration during a speed adjustment is in the order of 0.4kn/s. Heading changes are approximated by a steady turn of constant rate and radius. The changes of flight level are performed with a vertical speed, whose computation is detailed in [START_REF]User manual for the Base of Aircraft Data (BADA)[END_REF], as a function of the thrust, drag, and true airspeed.

On cliques and stables

Let G = (V, E) be an undirected, simple graph with a vertex set V and an edge set E ⊆ V × V.

A clique in graph G is a vertex set C with the property that each pair of vertices in C is linked by an edge:

C ⊆ V is a clique ⇔ ∀(u, v) ∈ C × C, (u, v) ∈ E (1)
A maximum clique in G is a clique that is not a subset of any other clique in G. The cardinality of a maximum clique of G is called clique number and is denoted by w(G). Let c : V → R be a vertex-weight function associated with G. A maximum clique of minimum-weight in G is a maximum clique C that minimizes v∈C c(v).

A stable set S ⊆ V is a subset of vertices no two of which are adjacent. A bipartite graph is a graph whose vertices can be partitionned into two distinct stable sets V 1 and V 2 . Each edge of the graph connects one vertex of one stable to a vertex in the other stable. This concept is extended to k-partite graphs, where the vertex set is partitionned into k distinct stable sets.

Graph construction

In this subsection, we introduce the graph G = (V, E) used to model the CDR problem.

Defining the vertices Let F = 1; n denote the set of the considered aircraft. We define M = ∪ n f =1 M f as the set of the possible maneuvers, M f being the set of maneuvers for aircraft f ∈ F. We consider both horizontal and vertical maneuvers of the following types:

-NIL refers to the null maneuver, i.e., when no maneuver is performed; -H θ corresponds to a heading change by an angle θ ∈ [-π; π]1 ; -S δ corresponds to a relative speed change of δ%; -V δh denotes a change of δh flight levels.

A maneuver m ∈ M is described as a triplet (δχ m , δV m , δF L m ) corresponding to the heading, speed and flight level changes induced by m. The set of vertices is defined as V = 1; |M| 2 . We note V f the set of vertices corresponding to aircraft f . In emergency scenarios where the feasibility of the problem can be an issue, it is possible to introduce n vertices corresponding to costly emergency maneuvers to ensure the feasibility of the problem. However, since the feasibility was not an issue for the tested instances, those vertices were not considered in this article. The weight of the vertices correspond to the fuel consumption induced by the corresponding maneuvers. We give further detail in Subsection 2.3.

Defining the edges

Let (i, j) ∈ V ×V be a pair of vertices representing maneu- vers (m i , m j ) ∈ M × M of aircraft (f i , f j ) ∈ F × F. For i = j,
we write m i 2m j when no conflict occurs if aircraft f i follows maneuver m i while aircraft f j performs maneuver m j . The set of edges E corresponds to the pairs of maneuvers performed by two different aircraft without creating conflicts:

E = {(i, j) ∈ V × V, i = j : m i 2m j } (2)
It is important to note that there is no edge between two different maneuvers of a given aircraft, which yields Proposition 1.

Proposition 1. For all f ∈ F, V f is a stable set, i.e there is no edge linking two distinct vertices of V f . Hence, the graph G is |F|-partite.

Let (i, j) ∈ V × V be a pair of vertices representing maneuvers (m i , m j ) ∈ M × M of aircraft (f i , f j ) ∈ F × F. The methodology used to compute if the edge (i, j) is added to G is described with the following notations:

-T : time horizon for the conflict resolution; -p fi (t) ∈ R 3 : position vector of aircraft f i at time t. p fi,x (t) p fi,y (t) and p fi,z (t) denote respectively the abscissa, ordinate and altitude components of the position vector; -s fi (t) ∈ R 3 : speed vector of aircraft f i at time t. s fi,x (t) s fi,y (t) and s fi,z (t) denote respectively the abscissa, ordinate and altitude components of the speed vector;

-a fi (t) ∈ R3 : acceleration vector of aircraft f i at time t. a fi,x (t) a fi,y (t) and a fi,z (t) denote respectively the abscissa, ordinate and altitude components of the acceleration vector; -p fj (t), s fj (t) and a fj (t) are also defined following the same notations.

The definition of the maneuvers m i and m j applied to f i and f j is used to project the aircraft trajectory over time. Aircraft f i and f j are said to be separated at time t if and only if at least one of constraints ( 3) and (4) holds:

d h fifj (t) 2 = (p fi,x (t) -p fj ,x (t)) 2 + (p fi,y (t) -p fj ,y (t)) 2 ≥ D 2 h,min (3)
d v fifj (t) 2 = (p fi,z (t) -p fj ,z (t)) 2 ≥ D 2 v,min (4)
3

At any time t ∈ T , either none, one or both aircraft are maneuvering. T can thus be divided into intervals where both f i and f j have a constant acceleration. For each interval, we compute the time at which the aircraft are the closest to verify if the separation constraints hold. Let T k be one of these intervals. Consider f i and t 0 ∈ T be the starting time of maneuver m i . If we assume that maneuver m i is applied with a constant acceleration, we obtain the position and the speed vector of f i at time t 0 + t with t such that t -t 0 ≤ |T k |:

p fi (t 0 + t) = p fi (t 0 ) + (t -t 0 )s fi (t 0 ) + (t -t 0 ) 2 2 a fi (t 0 ) (5)
s fi (t 0 + t) = s fi (t 0 ) + (t -t 0 )a fi (t 0 ) (6)
Let p h fifj (respectively s h fifj , a h fifj ) denote respectively the horizontal position, the speed and the acceleration of aircraft f j relatively to aircraft f i . We define We have:

d h fifj (t + τ ) =
t h fifj =      0 if τ fifj = 0 |T | if τ fifj ≥ |T k | τ fifj otherwise
Aircraft f i and f j are horizontally separated during interval T if and only if [START_REF] Durand | Automatic aircraft conflict resolution using genetic algorithms[END_REF] holds:

d h fifj (t h fifj ) 2 ≥ D 2 h,min (7)
By a similar reasoning, aircraft f i and f j are vertically separated during interval T if and only if (8) holds:

d v fifj (t v fifj ) 2 ≥ D 2 v,min (8)
If either [START_REF] Durand | Automatic aircraft conflict resolution using genetic algorithms[END_REF] or (8) holds when aircraft f i and f j apply maneuvers m i and m j , then an edge is created between i and j. As explained in 2.1, it is important that every aircraft initiates a safe return towards its initial trajectory once the conflict is avoided. For each edge, we compute the minimum time necessary before one or both aircraft can recover their initial trajectories. The cost of the recovery of a trajectory is detailed in Subsection 2.3.

Application to the CDR problem As mentioned in Section 1, given the current position, speed, acceleration and the planned trajectories of a set of aircraft, solving the CDR problem consists in finding a conflict-free set of maneuvers that minimizes the costs. Proposition 2 links the cliques in G to the CDR problem: Proposition 2. Let C be a clique in graph G. Then C represents a set of conflictfree maneuvers for a subset of F of cardinality |C|.

Proposition 2 shows that finding a set of conflict-free maneuvers for F is equivalent to finding a clique of G of cardinality |F|. We derive the following theorem:

Theorem 1. If a conflict-free solution exists, then ω(G) = |F|. Otherwise, ω (G)
is the maximum number of flights involved in a conflict-free situation.

We define the problem CDR M as the restriction of the CDR problem to the set of maneuvers M. Using both Proposition 2 and Theorem 1, we can state anew the CDR M problem as follows: solving the CDR M problem consists in finding a clique of maximum cardinality and minimal cost in graph G. In fact, we consider a new variant of a clique problem where the weight associated with a vertex is not known a priori and rather depends on the edges induced by the clique. Indeed, the cost associated with a maneuver depends on the duration that this maneuver will be performed before returning towards the planned trajectory. Because this duration depends on the maneuvers selected for the other aircraft, it cannot be determined a priori and must be computed as the maximum duration needed to avoid a loss of separation with all other aircraft given their chosen maneuvers. To handle such vertex costs, we first define edge costs.

Computing the cost of the edges The cost measure chosen for this article corresponds to the extra fuel consumption induced by the maneuvers, i.e., the additional fuel required to return to the 4D trajectory after the maneuver is performed. We use the model given in [START_REF]User manual for the Base of Aircraft Data (BADA)[END_REF]. For a jet commercial aircraft f , the fuel consumption by time and distance unit is given by ( 9) and ( 10):

C t,f (t) = c 1,f 1 + V f (t) c 2,f F T,f (t) (9)
C d,f (t) = C t,f (t) V f (t) (10)
where c 1,f and c 2,f are numerical constants depending on the type of aircraft f .

We compute the cost of an edge e = (i, j) linking two vertices representing two maneuvers of aircraft f i and f j , denoted m i and m j , as a pair constituted of the extra fuel costs for both f i and f j , denoted C (i,j) i and C (i,j) j . The additional consumed fuel corresponds to the performed maneuver along with the fuel required to recover the inital 4D trajectory. After a change of speed of δ% during a period δt, the aircraft recovers its 4D trajectory by making the opposite change of speed during δt. After a change of direction δχ during a period δt, the aircraft performs a turn with an angle θ r in order to recover its physical trajectory along with a change of speed to retrieve the 4D trajectory. The cost induced is the extra fuel burnt when the aircraft flies at the recovery speed and the fuel burnt on the extra distance induced by the maneuver. For a flight level change, we compute the extra cost as the difference of consumption between the different flight levels, along with the cost of changing twice of flight level. The distance flown is also longer, and this extra distance is also accounted for.

Computing the cost of the vertices Several techniques can be followed in order to determine the vertices cost. The basic one would be to discretize the duration of the maneuver, and to create the vertices accordingly. In this situation, computing the costs would be straight-forward. However, the drawback of this method is that the graph built is huge, which could result in a difficult resolution. We choose to follow another structure of cost because it is more compact in terms of graph size.

Let us consider a vertex i which corresponds to a maneuver m i for an aicraft f i . The cost of each edge linking i to one of its neighbors j, associated to a maneuver m j for aircraft f j , corresponds to f i applying m i during a time t j i , which depends on m j . Time t j i is the minimum time during which f i must apply m i in order to avoid any conflict if one or both aircraft return to their initial trajectory. Following maneuver m i for a duration t j i induces a cost C (i,j) i

. If i is part of the maximum clique C to be determined, we need to establish the time t i during which maneuver m i is actually applied in order to determine its cost c i . t i is obtained by:

t i = max j∈V∩C t j i ( 11
)
As a consequence, we have that c i is the cost of aircraft f i applying m i during t i . If i is not part of the maximum clique C, then no constraint is imposed on the cost c i . As detailed in Section 3, the optimization model will automatically force the value of c i to 0. To conclude, we have that for any i ∈ V:

c i =    max j∈V∩C C (i,j) i if i ∈ C 0 otherwise

Illustrative example

For the sake of clarity, an illustrative example with three aircraft is given in Figure 1. If each aircraft follows its planned trajectory, conflicts will happen between the blue aircraft and the two others. For this example, we assume that, in addition to the null maneuver, only two heading changes (±30 • ) are allowed. We build the CDR graph shown in Figure 1(b). The graph is 3-partite, as the vertex set is partitionned into 3 stable sets of 3 vertices each. Solving the CDR is then equivalent to searching for a minimum-weight clique of 3 vertices, i.e., a triangle. Determining the cost of a vertex i is very specific, since it is correlated to whether or not i belongs to a maximum clique C. As a consequence, the algorithms usually used in existing librairies dedicated to graph theory cannot be used for our model. We formulate the problem as a mixed-integer linear program using the following variables:

-x i = 1 if vertex i is part of the maximum clique 0 otherwise -c i ∈ R + is the cost of vertex i.
We describe the clique search by the following linear integer program:

minimize i∈V c i (12)
subject to

x i + x j ≤ 1, ∀(i, j) ∈ E (13)
i∈V

x i = |F| (14)
c i ≥ C (i,j) i (x i + x j -1), ∀(i, j) ∈ E (15)
x i ∈ {0; 1}, ∀i ∈ V (16)
c i ∈ R + , ∀i ∈ V (17)
The objective function [START_REF] Wu | A review on algorithms for maximum clique problems[END_REF] minimizes the cost of the maneuvers. ( 13) are clique constraints, and constraint ( 14) exploits Theorem 1 defining the cardinality of the maximum clique. Constraints (15) are used to compute the cost of the vertices: if a vertex is in the maximum clique, then its cost must be greater than its cost on all edges connecting it to other vertices in the clique.

Results

All tests were performed on a computer equipped with an Intel Core i7-3770 processor, 3.4 GHz, 8-GB RAM. The algorithms were implemented in C++ and using CPLEX 12.5.1.04 . The headings of the tables presented in these section are given as follows:

case: case configuration; n: number of variables; m: number of constraints; z ip : optimal value for the problem; nodes: number of branch-and-bound nodes; t lp : time (in seconds) to continuous relaxation of the MILP; t ip : time (in seconds) to obtain the z ip value;

Benchmark description

The benchmark used for this study gathers three types of instances. The first set is roundabout instances R n , where n aircraft are distributed on the circumference of a 100NM radius and fly towards the center at the same speed and altitude. The second set is crossing flow instances F n,θ,d , where two trails of n aircraft separated by d nautical miles intersect each other with an angle θ. The last type of instance is a grid G n,d constituted of two crossing flow instances F n, π 2 ,d with a 90 • angle, one instance being translated 15NM North-East from the other. An example of these instances is given on Figure 2.

Computational results

The first set of simulations considers only horizontal maneuvers, with relative speed changes of ±3% and ±6% and heading changes of ±5 • , ±10 • , ±15 • . The graph remains small when one considers this set of maneuvers, and their small magnitude makes them less costly. Nevertheless, if these values were to be inefficient to solve all the conflicts, we could introduce maneuvers of larger magnitude. Table 1 gathers information about the graph G, the MILP and the main computational results. The solution time for the continuous relaxation is very small, but the quality of the relaxation is mediocre. Indeed, the fractional solution of the linear relaxation chooses two maneuvers for each aircraft with a value of 0.5. Constraints (15) force the cost of each vertex to be 0, yielding an optimal value of 0 and a gap of 100%. Results also display short solution times: problems known to be complex with 20 aircraft are solved to optimality in less than 15 seconds. This result is very satisfying since the density of the graph is high. In the second simulation set, we introduce altitude maneuvers: aircraft are allowed to move to an adjacent flight level. Table 2 reports the main results. The values of the optimal solutions for the roundabout instances remain the same, highlighting that it is optimal to make simple turns instead of changing flight levels. For the crossing flows and the grid instances, it is more efficient for some aircraft to change their flight level instead of turning or changing their speed. As a consequence, the solutions are less expensive. Solution times tend to slightly increase, but the solution can still be computed in a short time. These results are promising since the instances tested are denser than real-life instances. Table 2: Dimensions of the instances and computational results

Conclusions

A new variant of the problem of finding a maximum clique of minimum weight in a graph and its application to aircraft conflict resolution have been presented.

The innovation of the model comes from the cost structure: the costs of the vertices cannot be determined a priori since they depend on the vertices in the clique. As a consequence, we model the problem as a MILP. The model performs well, since complex instances involving up to 20 aircraft are solved to optimality in near real-time. The design of the model is flexible, meaning that tuning some parameters of the model will allow meaningful comparisons with existing models. These conclusions validate the model as a basis for further research. For instance, techniques reducing the size of the graph are of interest. Adding uncertainties is also a meaningful extension of the model. Additional benchmarks including real-life instance and random scenarios will be necessary in order to challenge the model.

Fig. 1 :

 1 Fig. 1: Illustrative example with three aircraft

  -|F|: number of aircraft; -|V|: number of vertices; -|E|: number of edges; d = 2|E| |V|(|V|-1) : graph density;

  Fig. 2: Examples

Table 1 :

 1 Dimensions of the instances and computational results

			Graph G		MILP	Resolution
	Instance type Case	|F | |V|	|E|	d	m	n	zip nodes t lp tip
		R2	2 22	90 0.39	44	225	3.71	6	0 0.02
		R4	4 44	492 0.52	88 1073	14.98	73	0 0.02
		R6	6 66 1194 0.56 132 2521	22.7	0 0.01 0.15
		R8	8 88 2184 0.57 176 4545	31.05	47 0.01 0.53
	Roundabout	R10 R12	10 110 3430 0.57 220 7081 12 132 4944 0.57 264 10153 189.27 112.7	208 0.05 1.56 581 0.09 3.41
		R14	14 154 6720 0.57 308 13749 224.75	183 0.1 6.98
		R16	16 176 8896 0.57 352 18145 261.44	162 0.15 9.5
		R18	18 198 11358 0.58 396 23113	636.7	257 0.21 12.1
		R20	20 220 1402 0.58 440 28461	740.6	210 0.27 3.2
		F5,30,10	10 110 4522 0.75 220 9265	49.08	405 0.02 1.5
		F5,45,10	10 110 4518 0.75 220 9257	41.29	535 0.02 1.52
	Flows	F5,60,10	10 110 4478 0.75 220 9177	34.49	238 0.02 1.39
		F5,75,10	10 110 4492 0.75 220 9205	30.66	496 0.02 1.34
		F5,90,10	10 110 4528 0.76 220 9277	28.28	269 0.02 1.41
	Grids	G2,3,10 G2,5,10	12 132 6645 0.78 264 13555 20 220 19724 0.82 440 39889 121.92 2740 0.2 12.7 57.65 564 0.01 3.64

positive angles correspond to counter-clockwise rotations

In this paper we choose D h,min = 5NM and Dv,min = 1000ft.

see the IBM-ILOG CPLEX v12.5. User's manual for CPLEX