Dinh-Van Nguyen
email: dinh-van.nguyen@inria.fr

Myriam Elizabeth

Vaca Recalde
email: myriam.vaca-recalde@inria.fr

Fawzi Nashashibi
email: fawzi.nashashibi@inria.fr

Low Speed Vehicle Localization using WiFi FingerPrinting

Keywords: WiFi fingerprinting, low speed vehicle, indoor localization, autonomous vehicle, ensemble classification I

Recently, the problem of fully autonomous navigation of vehicle has gained major interest from research institutes and private companies. In general, these researches rely on GPS in fusion with other sensors to track vehicle in outdoor environment. However, as indoor environment such as car park is also an important scenario for vehicle navigation, the lack of GPS poses a serious problem. This study presents an approach to use WiFi Fingerprinting as a replacement for GPS information in order to allow seamlessly transition of localization architecture from outdoor to indoor environment. Often, movement speed of vehicle in indoor environment is low (10-12km/h) in comparison to outdoor scene but still surpasses human walking speed (3-5km/h, which is usually maximum movement speed for effective WiFi localization). This paper proposes an ensemble classification method together with a motion model in order to deal with the above issue. Experiments show that proposed method is capable of imitating GPS behavior on vehicle tracking.

INTRODUCTION

Indoor environment navigation is an important scenario for autonomous vehicle. A report in [START_REF] Barter | Cars are parked 95% of the time[END_REF] estimates that 95% of time cars are in parking lot. In addition, studies in [START_REF] Belloche | On-street Parking Search Time Modelling and Validation with Survey-based Data[END_REF], [START_REF] Gantelet | The time looking for a parking space: Strategies, associated nuisances and stakes of parking management in France[END_REF] suggests that the average searching time for a free slot in car park in Paris and Lyon is 20 minutes and can be as high as 40 minutes for some districts. This leads to around 70 million hours of searching each year for France and represents a 700 million euro loss. In addition, several issues are identified as: noise pollution, insecurity, air pollution and 10% to 60% of congestion. These negative effects also cost France 70 million euro per annum. Thus, by pushing toward a completely autonomous navigation for indoor environment (particularly car park), it is possible that billions of euro will not be wasted every year.

In the last decade, there are a many researches in indoor positioning system with wide ranges of sensory approaches. Most of these researches focus on tracking human or indoor robots. Researches using vision techniques can be found in [START_REF] Cai | Tracking Human Motion Using Multiple Cameras[END_REF]- [START_REF] Mirowski | Depth Camera SLAM on a Low-cost WiFi Mapping Robot[END_REF] which utilize camera (standard camera, depth-sensing camera, Kinect, etc.) to track target movement. These approaches achieve significant accuracy (~ 40 cm) but lack of coverage range as well as costly implementation. Radio Frequency based approach is another method which is being adopted widely. Studies in [START_REF] Lemic | Increasing Interference Robustness of WiFi Fingerprinting by Leveraging Spectrum Information[END_REF]- [START_REF] Huang | Efficient, generalized indoor WiFi GraphSLAM[END_REF] use WiFi signal to determine location of user in known environment. Companies like Google, Apple, Polestar, etc. are using the concept of iBeacon, a low energy Bluetooth (BLE) beacon, as a low cost, easy to implement indoor localization solution. However this approach has low sampling rate as well as accuracy is in range of 1-3m [11][12]. A summary of indoor localization system can be found in Table I below.

Majority of these studies do not specify movement speed of tracking target. It is partly because movement speed of indoor objects can be assumed to be within 3-5 km/h range (which is normal walking speed). However, this is an important factor when it comes to vehicle localization. Study in [START_REF] Belloche | On-street Parking Search Time Modelling and Validation with Survey-based Data[END_REF] shows that average speed of cars in car park is around 10 -12km/h which doubles human walking speed. Together with sampling rate of sensors, localization accuracy may change dramatically when it come to vehicle tracking. This paper proposes a solution that uses WiFi localization to replicate GPS behavior for indoor envrionment. An ensemble classification method of neural network is implemented together with motion model to overcome moving speed constraint. This is a first step in a fusion system consists of multiple localization technologies that aimed to have centimeter accuracy for indoor vehicle localization.

Section II gives a brief introduction to WiFi fingerprinting localization and a proposed improvement for noise filtering in data collection. Section III presents ensemble neural network structure. A constant speed motion model is adopted in section IV in order to improve localization result. Experiment setup and results are explained in section V. Section VI concludes the paper with future work.

II. WIFI FINGERPRINTING METHOD

Wifi Fingerprinting is a WiFi positioning solution which relies on an assumption: each location in environment has a unique set of signal strengths from all reachable Access Points (AP). Hence, by mapping that unique set of signal strengths and its corresponding coordinate in local map, the location can be derived later with only WiFi signal scan. Due to the availability of WiFi infrastructure, this method is a cost-effective solution and widely adopted for indoor positioning system.

There are two phases of WiFi fingerprinting: training phase and prediction phase. A training phase should be done by recording WiFi signal strengths of multiple reference positions in environment and labeling them with an ID. Each ID is then mapped to corresponding coordinate in local map. Set of all reference positions is considered to be classes of classification problem and noted as P. In prediction phase, tracking target will run in the same environment of training phase while continuously scanning and recording WiFi signal. Each scanned data will be a vector of signal strengths without label. Trained classification method such as Random Forest, Neural Network, etc. will take this vector as input and return the most likely reference position which matches signal vector.

However, there are certain limitations of WiFi fingerprinting localization method. The major two are noisy data and low sampling rate. WiFi signal appears to be unstable under influence of environment factors. Problem such as multi-path propagation for which receiver receives multiple signals of same source, each travels in different path is a well-known issue. In addition for a normal 2.4Ghz WiFi receiver, it takes in average 0.9 second to complete a scan of signals. This low sampling rate is capable of responding to average human walking speed (~ 1.4m/s or 3-5km/h). However, as we target vehicles such as cars, wheel chairs, etc. with speed of 10 -12km/h (2.7 -3.3 m/s), this low sampling rate introduces much higher error in localization. Thus, it is necessary to introduce a noise filtering method as well as a movement model to deal with these problems.

In training phase, One sampling vector of a reference position is described as in [START_REF] Barter | Cars are parked 95% of the time[END_REF] where 𝑥 𝑖,𝑗 is WiFi signal strength from jth WiFi APs recorded in ith scan, 𝜌 𝑙 is a label which has corresponding coordinate at position of sampling and n is fixed constant (for learning algorithm purpose) which should be greater total number of APs in learning environment.

{𝑥 𝑖,1 , 𝑥 𝑖,2 , 𝑥 𝑖,3 , … , 𝑥 𝑖,𝑛 , 𝜌 𝑙 }  Collected data will be normalized in range of [-1, 1) where in particular scan, detected AP signals (so called RSSI -Received Signal Strength Indicator) will be normalized (2) in range [0, 1) with 0 as weakest possible signal strength and 1 as strongest possible signal strength. Other signals will be scored as undetected APs at 𝜌 𝑙 and take value -1.

𝑥 𝑖 = { -1, 𝐴𝑃 𝑖 𝑢𝑛𝑑𝑒𝑡𝑒𝑐𝑡𝑒𝑑 1 - (-1)×𝑅𝑆𝑆𝐼 100 , 𝐴𝑃 𝑖 𝑑𝑒𝑡𝑒𝑐𝑡𝑒𝑑    
During the training phase, a fingerprinting database is formed as in [START_REF] Gantelet | The time looking for a parking space: Strategies, associated nuisances and stakes of parking management in France[END_REF] where m is number of sampling vectors in training phase, n is number of total APs and 𝑙 is number of labels (or reference position in training phase).

𝐷 = { 𝑥 1,1 , 𝑥 1,2 , 𝑥 1,3 , … , 𝑥 1,𝑛 , 𝜌 1 𝑥 2,1 , 𝑥 2,2 , 𝑥 2,3 , … , 𝑥 2,𝑛 , 𝜌 1 𝑥 3,1 , 𝑥 3,2 , 𝑥 3,3 , … , 𝑥 3,𝑛 , 𝜌 2 ⋮ 𝑥 𝑚,1 , 𝑥 𝑚,2 , 𝑥 𝑚,3 , … , 𝑥 𝑚,𝑛 , 𝜌 𝑙 }  
In order to reduce noise in collected training set, a spatial normalization process is applied. For each training vector, a global spatial mean value is computed in [START_REF] Cai | Tracking Human Motion Using Multiple Cameras[END_REF]. The spatial normalization relies on assumption that varying signal strength of a small subset APs does not affect variance of all recorded APs. Thus by taking difference of each recorded signal with mean value, local noise by small set of AP signals will be removed [START_REF] Bouchrika | Towards automated visual surveillance using gait for identity recognition and tracking across multiple non-intersecting cameras[END_REF]. A new 𝑚 × (𝑛 + 1) matrix 𝐷 ̅ is formed by substitute 𝑥 𝑖 ̂ for each 𝑥 𝑖 .

𝑥 𝑖 ̅ = 1 𝑁 ∑ 𝑥 𝑖 𝑁 𝑖=1    𝑥 𝑖 ̂= 𝑥 𝑖 -𝑥 𝑖 ̅     III. ENSEMBLE CLASSIFICATION METHOD
Ensemble learning is a well-known method of combining multiple learning models to derive better results of prediction [START_REF] Dietterich | Ensemble Methods in Mac hine Learning[END_REF]. In WiFi fingerprinting, especially for vehicle moving speed, the signal strength collected from WiFi Access Point is highly noisy. Often, noisy data with high variance lead to overfitting problem of classification method. One solution for this problem is applying Bagging (Bootstrap Aggregating) ensemble method [START_REF] Breiman | Bagging Predictors[END_REF].

Consider a classification method with a pair {𝑋 𝑖 , 𝑌 𝑗 } where 𝑋 𝑖 is a vector of predictor variable and 𝑌 𝑗 denotes a response, 𝑌 𝑗 ∈ {1, 2, . . 𝑚} . The target function is 𝑃(𝑌 = 𝑗 |𝑋 = 𝑥) for classification. A function estimator which results from set of training samples and a classification model is formed [START_REF] Clark | Robust Vision-based Indoor Localization[END_REF].

𝑔(•) = ℎ((𝑋 1 , 𝑌 1 ), (𝑋 2 , 𝑌 2 ), … , (𝑋 𝑛 , 𝑌 𝑚 ) ) 
Bagging algorithm consists following steps:

Step 1: Construct a bootstrap sample (7) by randomly sampling with replacement n times from original data:

(𝑋 ^1, 𝑌 ^1), (𝑋 ^2, 𝑌 ^2), … , (𝑋 ^n, 𝑌 ^m) 

Step 2: Compute bootstrapped estimator 𝑔 ^(•) (8) by applying same classification model to newly formed bootstrap sample.

𝑔 ^(•) = ℎ((𝑋 ^1, 𝑌 ^1), (𝑋 ^2, 𝑌 ^2), … , (𝑋 ^n, 𝑌 ^m)) 

Step 3: Repeat two steps above for K times with K is large. The bagging estimator is [START_REF] Biswas | WiFi localization and navigation for autonomous indoor mobile robots[END_REF].

𝑔 ^𝑏𝑎𝑔𝑔 (•) = 1 𝐾 (∑ 𝑔 ^𝑖(•) 𝐾 𝑖=1 ) 
Theoretically, the bagging estimator is [START_REF] Huang | Efficient, generalized indoor WiFi GraphSLAM[END_REF] as K goes to infinity:

𝑔 ^𝑏𝑎𝑔𝑔 (•) = 𝐄 ^[𝑔 ^(•)]
 Thus, a finite large K in practice is expected to improve accuracy of Monte Carlo approximation.

In this study, a neural network is constructed and loosely tuned (weak learner). Bagging method is implemented as following:

-Step 1: Construct a Bootstrap sample by repeatedly random sampling with replacement a row from original training matrix. m random rows will be sampled to form a new 𝑚 × (𝑛 + 1) training data matrix.

-Step 2: Repeat process above for Ktimes. In total, K training data matrices are formed (includes original data).

-Step 3: Train K neural networks on K matrices.

-Step 4: All K models make independent prediction on an input vector X.

-Step 5: Each model returns a vector V = { 𝒫(𝜌 = 𝜌i) | 𝜌i ∈ P} where P is set of all reference positions in training phase and 𝒫(𝜌) is posterior probability that the vehicle is in a particular reference position. Take average of K resulting vectors then select one that has maximum probability. If that value surpasses threshold htakes this as a valid prediction of input X.

Choosing threshold h is critical since it has huge impact on performance of localization. The lower value of h, the more predictions are accepted but also expected error is increased. With too high threshold, very few predictions are accepted so localization performance may not be satisfied.

IV. MOTION MODEL

Due low frequency of WiFi scanning, it takes in average 0.9 second for 1 scan and prediction to be completed. Hence, a valid predicted location will have delayed result. Consider 𝑆 𝑡1 as predicted location result from neural networks, actual location at time of receiving result will be 𝑆 𝑡2 with 𝑡2 -𝑡1 = 0.9 second. Since ∆𝑡 = 0.9 is small enough, a simple constant speed model ( 11) is adopted:

𝑆 𝑡2 = [𝑉 𝑆 𝑡1 ] • [ ∆𝑡 1 ] 
Where 𝑆 𝑡 = (𝑥, 𝑦) 𝑡 with x, y is coordinate. V is constant speed of vehicle obtained at time t.

In addition, the motion model will also help filtering out prediction. Since vehicle is moving with much higher speed in compare to sampling rate, one typical error is jumping prediction where predicted locations are jumping between adjacency reference points. Given prediction and correction from above step, a scoring operator will be applied on all possible reference points (classes) of WiFi localization in order to minimize jumping by a utilizing Euclidean distance cost function.

Every valid predictions (as define in section above) will increase the corresponding reference point score. A valid prediction is accepted when its score goes above a threshold and will be called valid location. In between a valid location and its successor valid prediction there are certain number of invalid predictions. A distance traveled between these two is computed by sum of all distance for each pair of scan in between [START_REF] Senionlab | [END_REF]. The result will then be compared to Euclidean distance of 2 reference points (13) corresponding to the valid location and valid prediction above and the difference must be under a tolerance 𝜀 [START_REF] Dietterich | Ensemble Methods in Mac hine Learning[END_REF].

𝑑 𝑡𝑟𝑎𝑣𝑒𝑙 = ∑ ∆𝑋 𝑖    𝑑 𝑟𝑒𝑓 = 𝑋 𝑣𝑎𝑙𝑖𝑑_𝑝𝑟𝑒𝑑𝑖𝑐𝑡𝑖𝑜𝑛 -𝑋 𝑣𝑎𝑙𝑖𝑑_𝑙𝑜𝑐𝑎𝑡𝑖𝑜𝑛    |𝑑 𝑡𝑟𝑎𝑣𝑒𝑙 -𝑑 𝑟𝑒𝑓 | ≤ 𝜀 
If the condition is not satisfied, the second prediction will not be accepted and its score will be lowered.

V. EXPERIMENT & RESULT

A. Experiment Setup

The experiment is carried out in campus area of INRIA-Rocquencourt with a cybercar (Fig. 1) from RITS team. The cybercar is an electrical vehicle equipped with multiple sensors and a computer. For this study, following sensors are used: IMU (Inertial Measurement Unit), RTK GPS (Real Time Kinematic GPS) and a standard 2.4Ghz WiFi USB dongle. The experiment is conducted in campus site, outdoor scene to make use of highly accurate RTK GPS for ground truth. 13 reference points are picked as illustrated in Fig. 2. A survey for average WiFi signal map and number of detected access points at each reference points are shown in Fig. 3, Fig. 4 respectively. Scale of WiFi signal strength will be in range [0, 1). Theoretically, highest possible WiFi signal strength will be -30dbm which equals to 0.7 in this scale. Training phase consists of taking 30 sample data for each reference position. A database of 390 vectors are formed for 13 different classes. In prediction phase, the vehicle will make 3 round-trips starting from reference point 13, visit all reference points with maximum speed of 2.5 m/s. Localization results with threshold h = 0.65 will be compared with RTK GPS result as ground truth. Details are shown in Table II. For 1264m covered in the experiment, root mean square error is 6.85m and maximum error is 16.48m. However, Fig. 5 shows an interesting observation that most of errors over 8m are from reference points 11, 12, 13. These high errors are expected due to low average signal recorded at these locations demonstrated in Fig. 3 even though numbers of detected WiFi APs in reference points 11 and 13 are significant. Without these reference points, the maximum error is 7.88m while root mean square error is 4.99m. In that case, error distribution is illustrated in Fig. 6. It shows that 90% of errors are achieved under 7.5m.

A further investigation shows in Table III indicates that there is a correlation between quality of signal strength to localization error. With better signal strength, localization performance appears to be enhanced significantly. Since experiment environment is an outdoor scene, it is worth to point out that quality of WiFi signal in this scene is much lower than indoor scene. Thus, a much better performance could be achieved in indoor environment.

VI. CONCLUSION AND FUTURE WORK

This paper shows an early result of using WiFi localization for low speed vehicles to replicate GPS behavior. Although accuracy level is under expectation, it shows promising of using WiFi in combination with other technologies such as SLAM in order to have a seamless transition from outdoor localization system to indoor localization system.

The experiment result shows that with sufficient WiFi signal strength as well as number of visible APs, the result of localization can be improved significantly. In more than 1.2km of testing environment with RTK GPS as ground truth, 8m error is achieved for reference position with average signal strength in range of [0.15, 0.3] or [-85dbm, -70dbm]. This result is expected to be improved in indoor condition with better WiFi signal.

In the future, environment map as well as a particle filter will be integrated into the solution to improve prediction result. Also, output from WiFi localization will be fused with other technologies in order to deliver reliable localization result.

Figure 1 .

 1 Figure 1. The cybercar

Figure 2 .

 2 Figure 2. Experiment area with labeled position

Figure 3 .Figure 4 .

 34 Figure 3. Average WiFi signal map

Figure 5 .Figure 6 .

 56 Figure 5. Distribution of error in each reference point

TABLE I .

 I SUMMARY OF INDOOR LOCALIZATION SYSTEM[START_REF] Mainetti | A survey on indoor positioning systems[END_REF]

TABLE II

 II

		.	LOCALIZATION RESULT
	Total Distance	Mean Error	RMS Error	Maximum
					Error
	1264 m	5.77 m		6.85 m	16.48 m

TABLE III

 III

	.	CORRELATION BETWEEN SIGNAL STRENGTH AND
		LOCALIZATION ERROR
	Average Signal	Average Error	Maximum error (m)
	Strength Range	(m)
	(dbm)
	[-100, -70]	6.85	16.48
	[-80, -70]	4.76	13.02
	[-75, -70]	3.89	7.05


Lucia Larise Stavarache
email: larise.stavarache@ro.ibm.com

Mihai Dascalu
email: mihai.dascalu@cs.pub.ro

Stefan Trausan-Matu
email: stefan.trausan@cs.pub.ro

Philippe Dessus
email: philippe.dessus@upmf-grenoble.fr

PAPER VS. SLIDES: DO THEY HAVE SIMILAR TEXTUAL TRAITS?

Keywords: textual complexity model, MOOC, comparative traits, discourse analysis. I

As different learning methods and educational scenarios highly influence the corresponding outcomes, our aim is to highlight quantifiable discrepancies in terms of the complexity gap between presentations and hand-outs versus full documents (i.e. academic papers), expressed as concrete factors that directly influence the perceived difficulty. Although there are multiple dependant variables that affect the interpretation of a given topic (e.g., order of presented materials, difference in personal styles if materials originate from multiple authors), we limit the scope of our analysis to solely identifying textual traits that can be automatically extracted from conference papers and their corresponding slide presentations. Our approach represents the starting point for adapting MOOC (Massive Open Online Courses) materials to their target audience in terms of: textual complexity, learner comprehension and content reusability. Therefore, this study performs a detailed comparison using a wide variety of textual complexity metrics as background, ranging from surface, syntactic, morphological and semantic factors in order to grasp the specificities of each material. In other words, our goal consists of providing a set of required metrics for adapting learning materials in order to best suit the underlying educational activities. Preliminary results reflect a strong correlation between the two alternative presentation forms of the same material (papers and corresponding slides) and a similar degree of perceived textual complexity, emphasizing the strong and unitary writing characteristics of the author.

INTRODUCTION

A central dimension in the development of Intelligent Tutoring Systems is focused on personalization. One way of doing it is improving the way materials are presented to learners in order to maximize comprehension and the learning outcomes. There are many alternate forms of presenting information to the audience, but a central issue for each author/presenter should consist of finding the best-suited method and form for presenting and adapting his or her materials to the public. Coming from an academic environment, we often pose the question: "What is the best way of presenting information to students and how can we predict likely gaps of understanding?" Therefore, we conducted a preliminary study to find in automatic manner possible objective answers for this question and key differences between the two most frequently used forms (textual materials from academic articles and their corresponding slides). In other words, we focused on the analysis of conference papers versus presentation slides, emphasising on the consistency of the textual complexity level among the analysed sets as we expect that both forms converge towards the same complexity level, without losing too much information. Moreover, the confirmation of the feasibility of our approach represents a fundament for our future studies regarding the textual complexity analysis of MOOCs, since they contain papers and slides as the most frequent learning materials.

As a general overview, our study targets to find boundaries of how different forms of presenting information can be linked, analysed, used and rated. The examples given above represent just the main threads of focus for this article; in terms of a detailed analysis, the goals are much more daring and wider, ranging up to an automated system able to measure the correlations between slides and their source materials from a qualitative point of view. From an academic perspective, the possibility to have such comparisons would add value to tutor-student communication and would facilitate the development of slides best aligned to the audience and designed to enhance comprehension. Moreover, this research path could improve the future development of quality MOOC platforms in terms of content personalization. In addition, this study considers that building a consistent, coherent and cohesive environment should be the actual target for developing viable eLearning platforms and, in order to achieve this, it is compulsory to define and assess qualitative boundaries while encouraging the use of automatic assessment tools based on natural language techniques.

As structure, the study performs a textual complexity comparison based on a multitude of surface, syntactic, morphological and semantic factors later described in detail. Of particular interest is that textual materials and the corresponding slides are strongly connected and all together address similar topics within the same domain. The following section presents the structure and the validation for the textual complexity model used in this study. The third section is an overview of the analysed corpus, describing the selection criteria for the materials and the results of the performed comparison. Moreover, it also details key factors that emerged from our experiments and their underlying interpretations. The final section is dedicated to conclusions and future work, aiming to highlight the key traits observed for the conducted paper vs. slides comparison and presents some key opportunities in terms of future research directions.

II. THE TEXTUAL COMPLEXITY MODEL

Overview of the integrated model

Textual complexity analysis can be considered among the most subjective and difficult tasks for tutors, researchers or automated scoring tools. In order to address the usual problem of aligning materials and information to their target audience, we strive to identify relevant metrics and rules for assessing textual complexity. Let us take the example of a tutor -his role consists of finding the best alternative for presenting information to students in order to maximize the understanding of the materials. Moreover, multiple approaches concur in terms of the assessment of textual complexity, each employing different metrics and scoring methods [START_REF] Nelson | Measures of text difficulty: Testing their predictive value for grade levels and student performance[END_REF]. Additionally there are many factors that influence the perception on the complexity degree like: user experience, user knowhow on the topic, the language used for the materials (native speakers vs non-native speakers), motivation or information structure [START_REF]Common Core State Standards[END_REF].

Starting from these presumptions, the purpose of this study is to analyze from an objective perspective pairs of conference papers and their corresponding slides. The computational metrics used to measure textual complexity are distributed in the following categories: surface, morphology, syntax and aggregated. The aggregation is performed using Support Vector Machines (SVM) [3; 4]. Each category is further described in this paper, while precision results expressed in terms of exact and adjacent agreement [5; 6] between the manual classification and the automatic prediction for each dimension of computed factors are presented in Table 2.

Firstly, the surface category orbits around individual analysis elements (words, phrases, paragraphs) and employs simple statistics. The textual analysis factors from this category are based on Page's grading technique for automated scoring [START_REF] Page | The imminence of grading essays by computer[END_REF], simple readability formulas [8; 9], fluency (e.g. number of words, number of commas), structure complexity (e.g., number of sentences and of paragraphs), diction (e.g., word length, average number of syllables per word, or of words per sentence) and word/character entropy [START_REF] Dascalu | Towards an integrated approach for evaluating textual complexity for learning purposes[END_REF].

Afterwards, the syntactic and morphological category, in opposition to surface analysis, changes the focus from a single component of analysis to the full parsing tree by finding the maximum depth and the size of the parsing structure [START_REF] Gervasi | Quantitative assessment of textual complexity[END_REF]. Additionally, at this level we analyze the corpora from the perspective of each relevant part of speech: prepositions, adjectives, nous or verbs.

The most promising category is focused on semantics, in which lexical chains, entity-density features and co-reference inferences are used for identifying the referential relationships between terms, lexicon variety and cohesion [11; 12]. The evaluation of semantic similarity through cohesion plays an important role, mainly due to the fact that our study is centered on measuring the connectivity for each component of the set (paper vs. slides) and on the identification of key differences.

From a different perspective, word complexity analysis has been approached through the combination of several different factors: syllable count, distance between the inflected form, lemma and stem, specificity of a concept reflected in its inverse document frequency from the training corpora, the distance in the hypernym tree or the word polysemy count from WordNet [START_REF] Miller | WordNet: A Lexical Database for English[END_REF].

Validation of our textual complexity model

In order to train our complexity model, we have opted to automatically extract English texts from Touchstone Applied Science Associates, Inc. (http://lsa.colorado.edu/spaces.html), using its Degree of Reading Power (DRP) score [START_REF] Carver | Measuring Readability using DRP Units[END_REF], considering six classes of complexity [START_REF] Mcnamara | Sources of text difficulty: Across the ages and genres[END_REF] of equal frequency (see Table 1). Based on the initial corpus, 3,000 documents (500 per complexity class) were extracted and later on processed by ReaderBench, our integrated analysis system [12; 16]. The large number of documents was needed in order to ensure a reliable and complete model and to reflect key points that could be useful for scoring purposes. Performance was measured through k-fold cross validation [START_REF] Geisser | Predictive inference: an introduction[END_REF] and is reflected through exact agreement -EA and adjacent agreement -AA [5; 6] for presenting the correctness of the SVM's prediction. The measurements presented in Table 2 are taken as reference for this study and later on used within the comparison experiments. As it can be easily observed, most dimensions are good estimators of textual complexity, whereas the complete model has an extremely high precision score which arguments its relevance and adequacy.

COMPARISON BETWEEN PAPERS AND CORRESPONDING PRESENTATION SLIDES

Overview of the analysed corpus

The selected corpus for our study focused on respecting a validity model that would ensure the processing of a proper content with regards to the purpose of this study. The key requirements for selecting the corpus have been: consistency, integrity, cohesion and coherence. Finding full text coherent materials is not hard, but finding adequate corresponding slides proved to be a difficult task due to different presentation styles. In most cases, we found slides consisting only of pictures that are irrelevant for this analysis or slides with little information, elliptical formulations within bullet items and impossible to use in order to achieve an accurate comparison. The purpose of our paper is not to compare all kinds of slides with their underlying materials, but to define a particular pattern of slides that would help students retain key focus points and understand the purpose of the documents.

In addition, one of the main problems with slides is that sometimes they tend to present a multitude of key features in rather few words, without focusing on the auditorium background and capability of understanding. It happens often that students, who do not attend the courses and do not self-study the full materials, do not perform well at the exam due to their focus on learning solely key information from slides without having solid connections among the central concepts.

In this context, we opted to analyze a preliminary corpus containing four pairs of full papers and their corresponding slides. The sets have been selected from various technical areas, in order to offer variety and a wider analysis (computer science with emphasis on natural language processing and distributed computing, merged with educational sciences). Starting from the previous constraints for selecting the corpus, these sets have been validated against a set of pre-imposed rules in order to reduce unwanted noise, which consisted in: 1) human validations for each set focused on the tight correlation between the paper and corresponding slides in terms of consistency, content and style; 2) manual re-editing of the materials in order to eliminate non-descriptive sections or specific irrelevant elements for our textual analysis (e.g., images, quotes, special characters, formulas, tables and videos), and 3) slides had to cover at least 80% of the topics presented in the papers. All the materials have been afterwards pre-processed into ReaderBench's XML format.

In addition, in trying to have a consistent and coherent corpus, the difficulty of finding valid materials for the analysis significantly increased. Therefore, because the main content available in MOOCs failed in some extent to pass our restrictions, we decided not to include this kind of materials as an initial validation of our approach.

Comparison Results

Starting from the dimensions defined in section 2.1, different textual characteristics can be underlined using individual factors or through a combination of various metrics. For current experiments, the analysis was divided into two main layers. The focus of the first layer consisted in a macrolevel analysis in order to find common properties and trends for both slides and papers. In contrast, the second layer focused on a microanalysis of each individual set, mainly comparing paper versus corresponding slides to find traits and common characteristics.

The main traits noticed at a global level, after computing the textual complexity factors for the previously trained model, have been: 1) a consistent maximum complexity level [START_REF] Dascalu | Towards an integrated approach for evaluating textual complexity for learning purposes[END_REF] for all papers and slides, which reflects also the specificity of the domain, and 2) a high correlation factor (r = .92) between the average textual complexity measures per papers and per slides, but also among each pair (r average = .91). In this context, we can clearly observe a consistency in terms of presentation between the two alternative forms, marking also that the correlation is constant throughout the sets and individual pair of paper-slides materials. At a microscopic level, of particular interest was to highlight specific factors with a very low, insignificant average normalized difference (see Table 3) between the presentation forms, but also factors with a high discrepancy (see Table 4), marking in some extent the key similarities and differentiators between slides and their corresponding papers. Upon closer inspection, factors with similar results reflect the usage of a very similar vocabulary, whereas the differentiators highlight major changes in the underlying discourse structure and representation. Based on the two analysis dimensions, we can state that 1) the writing and presentation styles are consistent between slides and their corresponding papers and 2) there are specific factors that significantly reflect the major differences in structure between papers and slides.

IV. CONCLUSIONS AND FUTURE WORK

Our goal was to observe how the same information can be transposed to different presentation forms and how these are interconnected. Moreover, we focused on identifying specific style markers and how the underlying factors impact the textual analysis. The obtained results confirm that the slides preserve a high connectivity with the sources from which they originated, conserving nevertheless the same complexity class and a high correlation with the textual material's complexity factors. Additionally, we observed that surface factors are consistent throughout papers and their corresponding slides, whereas the major differences are also completely justifiable by considering the differences between the length of a paper and its corresponding slides (a normal proportion would approximate that slides' content represents 10% of the corresponding paper).

Another conclusion that can be extracted shifts the perspective towards authors' writing styles, the structure of information and the evolution of ideas in providing tutors a comprehensive manner of measuring cohesion, coherence and the quality of their materials. From the tutor's perspective, the aim consists of presenting the information as clean, concise and coherent as possible.

As mentioned before, we aim to extend our study to a wider corpus extracted from MOOCs. Additionally, we want to explore beyond finding specific traits between papers and slides: the discovery of author's writing patterns and the identification of specific domain material characteristics from the presented information.

Table 1 .

 1 Ranges of the DRP scores used to define the six textual complexity classes [after 15].

	Complexity Class Grade Range	DRP Minimum	DRP Maximum
	1	K-1	35.38	45.99
	2	2-3	46.02	51.00
	3	4-5	51.00	56.00
	4	6-8	56.00	61.00
	5	9-10	61.00	64.00
	6	11-CCR	64.00	85.80

Table 2 .

 2 Textual complexity dimensions for N =3.000 documents.

	Depth of metrics	Factors for evaluation	Avg. EA	Avg. AA
	Surface Analysis	Readability Factors	.80	.97
		Fluency Factors	.36	.55
		Structure Complexity Factors	.81	.97
		Diction Factors	.86	.94
		Entropy Factors	.36	.64
	Morphology & Syntax Balanced CAF Factors	.86	1
		Part of Speech Complexity Factors	.78	.94
		Parsing Tree Complexity Factors	.50	.81
	Semantics	Named Entity Complexity Factors	.64	.89
		Co-reference Complexity Factors	.56	.86
		Lexical Chains Factors	.59	.78
		Discourse Factors	.69	.92
		Connectives Factors	.39	.53
		Word Information Factors	.47	.72
		Word Complexity Factors	.75	.83
	All Factors Combined		.94	1

Table 3 .

 3 Factors with similar results for slides and corresponding papers

	Depth of Metrics	Complexity factor	Average normalized difference
	Surface Analysis	Readability FOG	8%
		Readability Kincaid	7%
		Average number of syllables per word	3%
		Normalized number of sentences	8%
		Normalized number of blocks	2%
		Standard Deviation for words (letters)	3%
		Standard Deviation for words (syllables)	5%
		Word entropy	3%
		Character entropy	1%
	Balanced CAF Factors	Lexical Sophistication	5%
		Syntactic Diversity	4%
	Named Entity Complexity	Average number of unique entities per
	Factors	sentences	6%
		Percentage of nouns in total entities	2%
	Word Complexity Factors	Mean distance between words and
		corresponding stems	6%
		Mean word polysemy count	7%
		Mean word syllable count	1%

Table 4 .

 4 Differentiators between slides and corresponding papers

	Depth of Metrics	Complexity factor	Average normalized difference
	Surface Analysis	Average block size	69%
	Morphology	Average number of pronouns	75%
		Average number of verbs	67%
		Average number of adverbs	87%
		Average number of prepositions	69%
	Named Entity Complexity	Percentage of overlapping nouns per document	67%
	Factors
	Co-reference Complexity	Total number of co-reference chains per
	Factors	document	80%
		Average co-reference chain span	78%
		Number of co-reference chains with a big span	83%
	Lexical Chains Factors	Maximum span of lexical chains	67%
		Number of lexical chains with more than 5
		concepts	77%
	Discourse Factors	Average block score	72%
		Overall document score	67%
	Connectives Factors	Causal relation	95%
		Temporal relation	97%
		Additive relation	77%
		Logical relation	74%
		Adversative and contrastive relations	88%
		All connectives	79%
	Word Information Factors	First Person Plural Pronouns Count	94%
		Second Person Pronouns Count	100%
		Third Person Plural Pronouns Count	78%


David Sierra González

Steeve Jilles

Christian Dibangoye

Laugier

High-Speed Highway Scene Prediction Based on Driver Models Learned From Demonstrations

One of the key factors to ensure the safe operation of autonomous and semi-autonomous vehicles in dynamic environments is the ability to accurately predict the motion of the dynamic obstacles in the scene. In this work, we show how to use a realistic driver model learned from demonstrations via Inverse Reinforcement Learning to predict the long-term evolution of highway traffic scenes. We model each traffic participant as a Markov Decision Process in which the cost function is a linear combination of static and dynamic features. In particular, the static features capture the preferences of the driver while the dynamic features, which change over time depending on the actions of the other traffic participants, capture the driver's risk-aversive behavior. Using such a model for prediction enables us to explicitly consider the interactions between traffic participants while keeping the computational complexity quadratic in the number of vehicles in the scene. Preliminary experiments in simulated and real scenarios show the capability of our approach to produce reliable, human-like scene predictions.

I. INTRODUCTION

Recent years have seen a significant increase in research on Advanced Driver Assistance Systems (ADAS). Especially, autonomous driving has become a critical concern around the world. Whether it is to increase safety and security of drivers, passengers or pedestrians; enhance mobility for people and freights; or protect the environment. However, techniques to predict accurately the trajectories and intents of the involved traffic participants are time and memory demanding, preventing us from safe and secure autonomous driving systems [START_REF] Fletcher | The MIT-Cornell collision and why it happened[END_REF].

Instead of exhaustively estimating the intent of all road users [START_REF] Lawitzky | Interactive scene prediction for automotive applications[END_REF], one can rely on planning based prediction approaches to overcome the computational complexity [START_REF] Ziebart | Planning-based prediction for pedestrians[END_REF], [START_REF] Kitani | Activity Forecasting[END_REF], [START_REF] Vasquez | Novel Planning-based Algorithms for Human Motion Prediction[END_REF]. Planning-based approaches assume that people, when they move, they do so by minimizing a cost function which depends on their preferences and the context. Thus, given the cost function and the context, their future actions can be predicted. Unfortunately, most of the work in this area is limited to motion prediction for pedestrians in which the cost function is time-invariant and models the behavior of an agent in a static environment (i.e. an environment in which the obstacles do not move).

In contrast, the highway is a dynamic environment in which the actions of a driver are strongly conditioned by the states of the surrounding vehicles. Predicting the future becomes then a difficult task, as it involves predicting the This work has been supported by Toyota Motor Europe. The authors are with INRIA Grenoble Rhone-Alpes, 38330 Montbonnot-Saint-Martin, France -{david.sierra-gonzalez, jilles.dibangoye, christian.laugier}@inria.fr actions of all agents in the scene while taking into account the interactions between them.

Despite the complexity of the task, humans are extremely good at predicting the future intents of other traffic participants. Moreover, we do this instinctively, without thinking too much about it. We know that their actions are constrained by the road network, by the traffic rules, and by a riskaversive common sense. As an example of this, we can consider the situations shown in Fig. 1. When a driver approaches the vehicle in front at a high relative speed, and there is no obstacle preventing him from switching lanes, we can predict with high probability that he will be indeed switching lanes (Fig. 1a). However, if this maneuver carries a high risk of collision due to the presence of an obstacle (Fig. 1b), the most likely response of the driver will be a braking maneuver. In this work, we model this "not so complex" behavior of drivers with a cost function that is a linear combination of (a) static features, which model the preferences of the driver (e.g. how fast to drive); and (b) dynamic features, which model the risk-aversive behavior of the driver and take into account the dynamic environment (e.g. the time to reach the closest vehicle in front at the current speed).

The problem of learning a cost function that encodes the behavior of an agent is not new in robotics. Often, this cost shaping is done manually, balancing the multiple tradeoffs by trial and error. However, such a technique gets in trouble as the complexity of the model increases. Inverse Reinforcement Learning (IRL) algorithms enable us to obtain the cost function that encodes the behavior of an agent from a set of demonstrations in a systematic and mathematically consistent way [START_REF] Ng | Algorithms for inverse reinforcement learning[END_REF].

In this paper, we use IRL to learn the cost function of a regular highway driver from a set of demonstrated highway driving scenes. We use such cost function to predict the behavior of each traffic participant and thus, the long-term evolution of highway traffic scenes. The main contributions of the paper are: (1) A novel highway scene prediction framework that takes into account the interactions between traffic participants through the use of a cost function with static and dynamic features; (2) A procedure that exploits the constraints of the highway environment to sequentially predict the cost induced by the dynamic features for each traffic participant in future timesteps; and (3) Preliminary results in simulated and real-world scenarios that validate our approach and show the potential of driver models learned from demonstrated driving tasks to capture and predict the interactions between traffic participants.

The rest of the document is organized as follows: Section II presents the current state of research in the fields of motion and scene prediction for intelligent vehicles; Section III explains the theoretical background of the work; Section IV describes the proposed approach; Section V presents the different test scenarios and shows the experimental results. Lastly, Section VI concludes.

II. RELATED WORK

In this work, we focus on long-term highway scene prediction. Such a task requires necessarily to take into consideration the interactions between vehicles. An interactionaware approach to predict the development of traffic scenes is presented by Lawitzky et al. [START_REF] Lawitzky | Interactive scene prediction for automotive applications[END_REF]. They assume a set of discrete maneuvers for each vehicle and calculate the collision probabilities associated to each maneuver by explicitly considering all possible interactions between vehicles. This leads to exponential complexity in the number of vehicles in the scene.

A more refined approach is presented by Schwarting and Pascheka [START_REF] Schwarting | Recursive conflict resolution for cooperative motion planning in dynamic highway traffic[END_REF]; they assume that not all dependencies between the vehicles in the scene are equally strong, and consider that a vehicle's decision is dominated by its predecessors'. Initially, egoistic decisions are predicted for all vehicles in the scene. If this results in a conflict, they examine all possible maneuver combinations for each pair of vehicles involved in order to find the best cooperative behavior according to a hand-tuned cost function. In contrast to this work, we do not assume any cooperative behavior but rather a risk-averse behavior for all traffic participants. Dynamic Bayesian Networks (DBNs) have also been used to address the problem of prediction in traffic situations. They are a convenient approach to avoid the exhaustive enumeration of other approaches by exploiting dependencies among vehicles. In the work of Gindele et al. [START_REF] Gindele | Learning driver behavior models from traffic observations for decision making and planning[END_REF], each vehicle is represented within a DBN by a set of nodes representing its internal states and the relationships with the other vehicles and the infrastructure. The policies are learned from data using random forests. It is not obvious how the policy model can guarantee reasonable predictions when presented with new traffic scenes not included in the training set.

Planning-based motion prediction is an intuitive, sound framework that predicts human behavior by incorporating all the different variables relevant to a task. It is based on two assumptions: [START_REF] Fletcher | The MIT-Cornell collision and why it happened[END_REF] The relationships between human agents performing a task and the environment can be modeled in a cost function; and (2) When people perform the task (e.g. walking in the city, driving) they minimize such cost function. Regarding the first assumption, IRL has already been shown as a viable approach to learn the cost function that describes the highway driving task [START_REF] Abbeel | Apprenticeship learning via inverse reinforcement learning[END_REF], [START_REF] Levine | Continuous Inverse Optimal Control with Locally Optimal Examples[END_REF]. Regarding the second assumption, planning-based approaches have been successfully applied to pedestrian motion prediction [START_REF] Ziebart | Planning-based prediction for pedestrians[END_REF], [START_REF] Kitani | Activity Forecasting[END_REF], [START_REF] Vasquez | Novel Planning-based Algorithms for Human Motion Prediction[END_REF]. However, these approaches assume that the pedestrians move in static environments and that the cost function is time-invariant. Recently, Lee and Kitani applied a planningbased approach to predict the trajectories of an attacking player in American football [START_REF] Lee | Predicting wide receiver trajectories in american football[END_REF]. They used a dynamic feature dependent on the motion of the defenders, which was predicted using supervised learning.

In this work, we bring the planning-based motion prediction framework to the intelligent vehicles domain. We propose a planning-based approach to predict the future actions of every traffic participant in high-speed highway traffic scenes. The interactions between drivers are explicitly considered through the dynamic features of a driver model learned using IRL. Such a model captures the common-sense risk-aversive behavior of a driver and it can thus induce reliable predictions even when presented with situations never seen before. The predictive potential of the approach is demonstrated on simulated and real-world scenarios.

III. BACKGROUND

This section presents the theoretical foundations upon which our approach is built. We use the Markov Decision Process framework to model the dynamics of each traffic participant in the scene. With IRL, we can obtain a model that captures the behavior of a driver from driving demonstrations.

A. Markov Decision Processes

Markov Decision Processes (MDPs) provide a framework for modeling sequential decision making problems. A finite MDP (S, A, {P sa }, C, γ) is defined by:

• A finite set S of n states • A finite set A of k actions • A state transition probability P sa (•) upon taking action a in state s. • A cost function C : S → R • A discount factor γ ∈ [0, 1)
A policy is defined as any map π : S → A. The value function for a policy π, can be evaluated at any arbitrary state s ∈ S as follows:

V π (s) = E[ ∞ t=0 γ t C(S t ) | π, S 0 = s]
Solving an MDP implies finding the policy π that minimizes V π , that is, for any arbitrary state s ∈ S we have that:

V * (s) = min π V π (s) = C(s) + min a∈A E s ∼Psa(•) [V * (s )].
where notation s ∼ P sa (•) means the expectation is with respect to s distributed according to P sa (•).

B. Inverse Reinforcement Learning

Inverse reinforcement learning algorithms [START_REF] Ng | Algorithms for inverse reinforcement learning[END_REF] aim to find the cost function C : S → R that can explain observed behavior. In this work, the observed behavior will be a set of M demonstrated, possibly suboptimal, trajectories {ξ 1 , ξ 2 , . . . , ξ M }. A trajectory is defined as a sequence of states of a vehicle ξ = {s 1 , . . . , s T }. The majority of IRL algorithms assume that the cost function can be fully specified as a linear combination of features:

C(s) = θ • f (s) (1)
where θ = (θ 1 , . . . , θ K ) is the unknown weight vector and f (s) = (f 1 (s), . . . , f K (s)) is the feature vector that parameterizes state s, both of dimension K. The goal is to find the weight parameters for which, if we found the optimal policy by solving the underlying planning problem, we would obtain similar trajectories to those demonstrated according to a given statistic. Unfortunately, this is an illposed problem, as there are many different weights that make the demonstrated behavior optimal.

C. Maximum Entropy Inverse Reinforcement Learning

In this work, we use the Maximum Entropy IRL variant presented by Ziebart [START_REF] Ziebart | Maximum entropy inverse reinforcement learning[END_REF]. The similarity statistic of this approach is the sum of features. It resolves the ambiguity described above by applying the principle of maximum entropy by which the distribution over trajectories P (ξ|θ) that does not exhibit any additional preferences beyond matching the empirical sum of features is chosen. The solution has the form:

P (ξ i |θ) ∝ e s j ∈ξ i -θ T f (sj ) (2)
The probability of a certain trajectory ξ i is defined to be proportional to the exponentiated weighted sum of features encountered over the trajectory. It can be shown that the gradient of the constrained optimization problem with respect to θ is the difference between the empirical and expected sum of features. The cost weights can thus be calculated using gradient-based optimization methods. Further details can be found in [START_REF] Ziebart | Maximum entropy inverse reinforcement learning[END_REF].

D. IRL in dynamic environments

Classic IRL was not originally designed to work on dynamic environments, where the features can change over time. In order to adapt the IRL framework to our problem, we follow the procedure previously presented in [START_REF] Henry | Learning to navigate through crowded environments[END_REF]. In a nutshell, the solution involves training on a small window of H timesteps with the environment fixed. Then, successive re-training steps are performed by updating the state of the environment and shifting the window t ≤ H timesteps into the future. The solution is no longer guaranteed to be optimal but it is accepted as a good approximation [START_REF] Vasquez | Inverse reinforcement learning algorithms and features for robot navigation in crowds: An experimental comparison[END_REF].

IV. APPROACH

We address the problem of predicting the development of highway traffic scenes. The proposed approach uses a driver model learned offline from demonstrations to predict the actions of all the vehicles in a highway traffic scene. The model is shaped as a linear feature-based cost function, which takes explicitly into account the interactions between vehicles. In this section, we formalize the problem and show how such a driver model can be used to determine a humanlike policy model.

A. Discretization and notation

Our framework for motion prediction in high-speed highway scenes (V, G, {S i }, {A i }, {T i }, {S i 0 }) is given by: • V a finite set of m vehicles involved in the traffic scene.

• A grid G centered in the position of the ego-vehicle.

• S i a finite set of states for vehicle i ∈ {1, 2, . . . , m}.

Each vehicle i's state s i is a tuple ((x i , y i ), z i , z i • ), where (x i , y i ) denotes the position of the vehicle i in grid G; z i is its absolute speed, and z i

• is the driver's desired speed.

• A i a finite set of actions (or maneuvers) available to vehicle i ∈ {1, 2, . . . , m}. • T i : S i × A i → S i denotes the transition rule, which describes the next-state s i = T i (s i , a i ) of vehicle i after taking action a i in state s i . • S i 0 the initial state for vehicle i ∈ {1, 2, . . . , m}. The cell (x i , y i ) occupied by vehicle i in grid G can be uniquely identified given: a) the lane occupied by vehicle i; and b) the relative distance between the center of mass of vehicle i and that of the ego-vehicle (Fig. 2). In the tuple (x i , y i ), x i indicates the cell index along the longitudinal dimension of the road, and y i indicates the lane index. We denote by r x the longitudinal resolution of the grid.

B. Feature-based cost function in dynamic environments

For any state s i ∈ S i , we can calculate a feature vector f (s i ) that describes the vehicle's state and its context. The highway is a dynamic environment and therefore we need to consider static and dynamic features. Static features are time-invariant and can be directly calculated given a state. Dynamic features are those that change over time in response to the actions of the dynamic agents in the environment. Consequently, the cost associated to a given state, which is a weighted linear combination of the features, will also change over time. We can rewrite equation 1 to explicitly reflect this:

C i t (s i ) = θ i s • f s (s i ) C i s (s i ) + θ i d • f d,t (s i ) C i d,t (s i ) (3)
where θ i s and θ i d are the components of the weight vector associated to the static and dynamic features respectively, f s : S i → R Ks is the time-invariant vector of static features, and f d,t : S i × T → {0, 1} K d is the vector of dynamic features at the different timesteps t ∈ {0, 1, . . . , T -1}.

C. Feature selection

In order for the model to capture the preferences of a highway driver we have selected the following static features:

• Lane: These features aim to capture the preference of an agent to drive on a particular lane. For a highway with n l lanes, the vector of lane features consists of n l mutually-exclusive binary features: f s1 : S i → {0, 1} nl for any vehicle i ∈ {1, . . . , m} • Speed deviation: This feature encodes the penalty of deviating from the agent's desired speed: f s2 : S i → R for any vehicle i ∈ {1, . . . , m}, where

f s2 (s i ) = z i -z i •
for each state s i ∈ S i . The preferred speed of a driver z i • is estimated as the maximum speed observed since the last change in the speed limit.

The dynamic features capture the risk-aversive behavior of drivers. We propose the following features:

• Time-headway: We define the time-headway as the time elapsed between the back of the lead vehicle passing a point and the front of the following vehicle passing the same point. It indicates potentially dangerous situations [START_REF] Vogel | A comparison of headway and time to collision as safety indicators[END_REF]. To calculate the time-headway we define function φ : S i ×S i → R that calculates the time-headway value between any two vehicles i, j ∈ {1, . . . , m}:

φ(s i , s j ) = (x i -x j ) rx z j if x i -x j ≥ 0 (x j -x i ) rx z i otherwise
We consider two separate dynamic features: the timeheadway to the closest car in front in the current lane f d1,t : S i × T → {0, 1} n th , and the timeheadway to the closest trailing car in the current lane f d2,t : S i × T → {0, 1} n th . They are defined as:

f d1,t (s i t ) = d( min j: x i t -x j t ≤0 y i =y j φ(s i t , s j t )) (4)
f d2,t (s i t ) = d( min j: x i t -x j t ≥0 y i =y j φ(s i t , s j t )) (5)
where s i t and s j t are the states of vehicles i and j at timestep t, and d is a discretization operator d : R → {0, 1} n th that returns mutually exclusive binary vectors of dimension n th . If there is no other vehicle at the front or at the back the time-headway is set to infinity.

D. Occupancy distribution

The generic driver model obtained via IRL enables us to predict what action is a driver likely to perform given his preferences and the current state of the environment. In order to keep track of the state of the environment in the current and future timesteps, we maintain a distribution over the cells of grid G for each vehicle. We shall call such distribution an occupancy distribution of vehicle i denoted o i t+1 χ(b i t+1 ) and given by:

o i t+1 (x i , y i ) = z i ,z i • s i =(x i ,y i ,z i ,z i • ) b i t+1 (s i ) (6)
where b i t+1 τ (b i t , π i t ) is the probability distribution over the state space of vehicle i, namely the belief state of vehicle i and given by:

b i t+1 (s i ) = s i a i P (s i |s i , a i ) π i t (a i |s i ) b i t (s i ) (7)
We assume deterministic transitions and thus the transition probability term P (s i |s i , a i ) = 1{s i = T i (s i , a i )} only takes values 0 or 1, where 1{•} is an indicator function. The term π i t (a i |s i ) is the policy model.

E. Policy model

Using IRL, we have obtained a generic driver model that encodes the behavior of highway drivers. This model tells us how comfortable a driver feels in a given state. For example, if the learned model associates high costs to states in which the distance to the car in front is too small, which is usually an indicator of dangerous situations, the driver will tend to avoid taking actions that would lead him to such states. Thus, we propose the following heuristic as a policy model that captures the risk-aversive behavior of drivers:

π i t (a i |s i ) ≈ 1 - C i t (T i (s i , a i )) a i ∈A i C i t (T i (s i , a i )) (8)
The probability of taking one action will be low if it transitions the agent to a state s i in which the cost C i t (s i ) is high and there are other actions available that would lead to states with a lower cost. In this work, we consider only a one timestep look-ahead.

F. Dynamic cost estimation

In order to forecast the development of a traffic scene, we need to predict the state transitions of each agent following [START_REF] Gindele | Learning driver behavior models from traffic observations for decision making and planning[END_REF]. This implies calculating the cost associated to each state and by extension, the value of the dynamic features of the state, in the future. In subsection IV-C, we defined the dynamic features f d1,t (s i t ) and f d2,t (s i t ) for the deterministic case in which each vehicle occupies a single state. The calculation of the cost associated to the dynamic features (hereafter, dynamic cost) is then trivial:

C i d,t (s i ) = θ i d • f d,t (s i ) = θ i d1 • f d1,t (s i ) C i d 1 ,t (s i ) + θ i d2 • f d2,t (s i ) C i d 2 ,t (s i )
where we have decomposed the dynamic cost into its components C i d1,t (s i ) and C i d2,t (s i ). However, the concept of time-headway to the closest car is no longer defined in future timesteps where we have a state distribution for each vehicle in the scene. Instead, we traverse the occupancy distributions of all opposite vehicles calculating the dynamic costs associated to each possible location, and weighting them by the occupancy probability:

ϕ d1,t (s i t ) o j t (x j , y j ) θ i d1 • d φ(s i t , ŝj t ) (9)
∀ŝ j t = ((x j , y j ), z j t , -) : j = i, y j = y i , x j -x i ≥ 0 ϕ d2,t (s i t ) o j t (x j , y j ) θ i d2 • d φ(s i t , ŝj t ) (10)
∀ŝ j t = ((x j , y j ), z j t , -) : j = i, y j = y i , x j -x i ≤ 0

where in the state ŝj t induced by cell (x j , y j ) we calculate the speed z j t as the weighted average of the states that contributed to the occupancy probability o j t (x j , y j ). The dynamic costs C i d1,t (s i ) and C i d2,t (s i ) are then set to be the maximum of the weighted costs obtained above, that is:

C i d1,t (s i ) = ϕ d1,t (s i t ) ∞ (11)
C i d2,t (s i ) = ϕ d2,t (s i t ) ∞ (12)
Note that this is a maximum both across vehicles and across possible locations in grid G. This approach mimics the way human drivers deal with risk: for a given vehicle i, if the probability of another driver cutting in front (and causing thus a low front time-headway feature value) is high, a risk-aversive preemptive maneuver (e.g. braking, changing lane) is expected. Equivalently, if a cell close in front of the vehicle has a high probability of being occupied, the policy model should encourage actions that transition the vehicle to low risk states (either by reducing the speed or changing lanes). In contrast, if a vehicle can cut in front but this is not likely to happen (i.e. there is no reason or evidence that this will happen), vehicle i will not alter its trajectory. In other words, cells with very low occupancy probability should generate a low dynamic cost. The occupancy probability acts here as a gate, letting through the cost associated to dangerous situations when they are likely to occur.

G. Highway scene prediction algorithm

Algorithm 1 sums up the proposed approach. For each prediction timestep within the desired time horizon, and for each vehicle i ∈ V from the front to the back of the scene we calculate the cost function C i t (s i ) using (3) for all states s i ∈ S i . To calculate the dynamic component of the cost, we use [START_REF] Lee | Predicting wide receiver trajectories in american football[END_REF] and [START_REF] Ziebart | Maximum entropy inverse reinforcement learning[END_REF]. Once the costs are computed, we can calculate each vehicle's risk-aversive policy using [START_REF] Gindele | Learning driver behavior models from traffic observations for decision making and planning[END_REF]. Finally, we update the probability distribution over the state space b i t+1 and the occupancy distribution

o i t+1 = χ(b i t+1 ).
Algorithm 1 Highway scene prediction with feature-based driver models Require: T

1: for t = 0 . . . T -1 do 2:
for all i ∈ V from front to back do 3:

Update cost function C i t using [START_REF] Ziebart | Planning-based prediction for pedestrians[END_REF][START_REF] Lee | Predicting wide receiver trajectories in american football[END_REF][START_REF] Ziebart | Maximum entropy inverse reinforcement learning[END_REF] 4:

Compute vehicle i's policy π i t using [START_REF] Gindele | Learning driver behavior models from traffic observations for decision making and planning[END_REF] 5:

Maintain belief and occupancy dist. using [START_REF] Schwarting | Recursive conflict resolution for cooperative motion planning in dynamic highway traffic[END_REF][START_REF] Ng | Algorithms for inverse reinforcement learning[END_REF] 6:

end for 7: end for

The algorithm outputs at each timestep the expected occupancy of the road. This can be used by a planner to estimate the risk of different candidate trajectories.

H. Complexity of algorithm 1

Algorithm 1 consists of three main operations (3), ( 8) and [START_REF] Ng | Algorithms for inverse reinforcement learning[END_REF]. Let |A * | and |S * | be the maximum number of actions and states for all vehicles; and G x and G y the transversal and longitudinal sizes of grid G, respectively. a) Complexity of cost-function updates: The first operation (3) is the update of the cost function for all states. This involves the update of the static and dynamic parts of the cost function for all states. However, the static part can be computed offline so it is not considered. The complexity of computing the dynamic part of the cost function is linear in the number of states for each vehicle i ∈ V and each timestep t ∈ {0, 1, . . . , T -1}. As seen in subsection IV-F, to calculate these costs it is necessary to traverse longitudinally the occupancy grids of all opponent vehicles. Hence

V. EVALUATION

To evaluate the presented approach we developed a 3lane highway simulator inspired by the one presented in [START_REF] Abbeel | Apprenticeship learning via inverse reinforcement learning[END_REF]. We used this simulator to generate demonstrated trajectories from which a driver model was learned. Using this model, we tested our scene prediction algorithm on simulated highway traffic scenarios and on real-world traffic scenes from data gathered on a French highway.

A. Settings

In the simulator, the discrete set of possible actions A i for each vehicle i includes lane and speed changes, and any combination of the two. The vehicle speeds are discretized into a set Z of 11 evenly spaced bins between 0 m/s and 40 m/s (144 km/h). We assume that a vehicle can switch to an adjacent lane or speed per timestep.

The simulator was used to generate training data by driving a vehicle through different highway traffic scenes. A total of 2 minutes of demonstrations were recorded and sampled at 10Hz. Using this dataset, we trained a driver model following the procedure described in subsection IV-B.

B. Simulation Results

The driver model learned was used to predict the evolution of different simulated highway traffic scenes. The length of the grid was set to twice the range of a Velodyne LiDAR, i.e. 240m., with a resolution in the longitudinal dimension of 0.5m. Fig. 3 shows the results obtained for the two highway traffic situations presented in the introduction in figures 1a and 1b. The figure shows the result of summing up across the occupancy distributions of all the vehicles in the scene (note that the result is no longer a probability distribution, but it is convenient to visualize the results). We assume that a vehicle changes lanes each time a new lane contains the majority of occupancy probability mass for that vehicle. The model captured correctly the demonstrated behavior. In Fig. 3a, the system predicted that the trailing car would switch lanes in order to overtake the slower vehicle and maintain its speed. In Fig. 3b, the system anticipated that the trailing vehicle on lane 1, would not switch lanes to overtake the slower vehicle in front, but instead slow down to maintain a security distance while waiting for lane 2 to be free of obstacles.

C. Real-World Highway Traffic Scenario

In order to verify if the intuitive results obtained in simulation apply as well to real-world situations, we used an instrumented vehicle to gather data on a French 3-lane highway. Fig. 4 shows a given traffic scene encountered I (the vehicles are indexed from front to back). Vehicle i = 5 was approaching fast in the middle lane. Our approach successfully predicted the evolution of this traffic scene. In particular, it was predicted that vehicle i = 5 would change lanes to the left around t = 2.8s in order to keep its high speed and overtake the vehicle in front (Fig. 4f).

VI. CONCLUSIONS

This paper proposes a novel highway scene prediction framework that takes into account the interactions between traffic participants through the use of a driver model learned from demonstrated driving tasks. The model is composed of static and dynamic features that capture the preferences and the risk-aversive behavior of drivers. The potential of this framework to predict the long-term development of highway traffic scenes has been demonstrated in simulated and realworld scenarios

In contrast with other approaches that take into account the mutual influence between drivers, the complexity of our approach does not grow exponentially in the number of vehicles in the scene. Instead, we showed that the complexity scales quadratically in the number of vehicles. As a direct application of the framework presented here, we can think of an advanced collision avoidance system that automatically learns the preferences of the driver and uses such knowledge to predict the driver's future maneuvers and to monitor the collision risk.

Fig. 1 :

 1 Fig. 1: Two traffic situations commonly found in highway driving.

1 Fig. 2 :

 12 Fig. 2: Evolution of the occupancy distribution of a vehicle over the cells of grid G in one timestep. The occupancy probabilities at timestep t + 1 will depend on the available actions in the previous timestep.

  , it results in complexity O(T • |V||S * ||V -1|G y ). b) Complexity of decision-rule updates: The second operation is the computation of the decision rule for all state and action of a vehicle i ∈ V and each timestep t ∈ {0, 1, . . . , T -1}. That is about time complexity O(|S * ||A * |). Notice that the denominator of (8) is computed only once for each state and vehicle, i.e., O(|S * ||A * |). Overall the complexity of maintaining the decision rules for all vehicles and all timesteps is about O(T • |V||S * ||A * |) c) Complexity of information-measure updates: The belief-and occupancy-update rules require time complexities O(|A * ||S * | 2 ) and O(|S * |), respectively for each vehicle at every timestep. That results in an overall complexity of about O(T • |V||A * ||S * | 2 ).

  (a) Simulation of the traffic scene presented in figure1a. The model predicts an overtaking maneuver from the trailing vehicle.(b) Simulation of the traffic scene presented in figure1b. The model predicts that the trailing vehicle on lane 1 will slow down (notice the low occupancy probabilities on lane 1 at t = 1.7s that correspond to states in which the vehicle would maintain/increase its speed).

Fig. 3 :

 3 Fig.3: Prediction of the traffic scenes from figures 1a and 1b using the driver model learned with the simulator. We show the result of summing up the occupancy probabilities across the occupancy distributions of all vehicles in the scene. One timestep corresponds to 0.1s. Each action (lane change, speed change) takes one timestep to be completed.

  Sum of the initial probability occupancy distributions (d) Front view (e) Back view (f) Sum of the probability occupancy distributions at t = 2.8s

Fig. 4 :

 4 Fig. 4: Typical 3-lane highway scene (t = 2.8s). Our approach predicted a lane change for vehicle i = 4, that was advancing fast in the middle lane

TABLE I :

 I Data from the traffic scene in Fig.4i z i [km/h] rel. dist. [m] lane

	1	86	24.2	1
	2	101	2.1	2
	3	86	0	1
	4	84	-26.6	1
	5	107	-36.7	2

ACKNOWLEDGMENT

The authors would like to thank Nicolas Vignard, Gabriel Othmezouri, Dizan Vasquez, and Victor Romero-Cano for the helpful discussions and the feedback on earlier versions of the paper.