Benoît Barbot

Béatrice Bérard

Yann Duplouy

Serge Haddad

Statistical Model-Checking for Autonomous Vehicle Safety Validation

Keywords: Statistical Model Checking, Simulation, Autonomous Vehicle, Controller

We present an application of statistical model-checking to the verification of an autonomous vehicle controller. Our goal is to check safety properties in various traffic situations. More specifically, we focus on a traffic jam situation. The controller is specified by a C++ program. Using sensors, it registers positions and velocities of nearby vehicles and modifies the position and velocity of the controlled vehicle to avoid collisions. We model the environment using a stochastic high level Petri net, where random behaviors of other vehicles can be described. We use HASL, a quantitative variant of linear temporal logic, to express the desired properties. A large family of performance indicators can be specified in HASL and we target in particular the expectation of travelled distance or the collision probability. We evaluate the properties of this model using COS-MOS 1 . This simulation tool implements numerous statistical techniques such as sequential hypothesis testing and most confidence range computation methods. Its efficiency allowed us to conduct several experiments with success.

Recently several ITS projects aim at providing assistance to drivers and focus on partially automatized roads. Researchers have first chosen an approach based on a fully automatized infrastructure (see project PATH [START_REF] Horowitz | Control design of an automated highway system[END_REF]) in the nineties. This approach has been gradually replaced by a new research direction, more oriented on strategies to ensure specific properties like collision avoidance or preserving safety distances [START_REF]Saving lives through advanced vehicle safety technology[END_REF]. In particular the control of an autonomous vehicle may be switched between the driver and an automatic controller depending on the traffic situation and the road structure. 1

Statistical Concepts and Tools for Stochastic Models

Goal. This work takes place in the SVA 2 project, hosted by IRT SystemX. Our long term aim is to be able to verify the controller developped in this project for a traffic jam situation. As a first step in this direction, our goal here is to propose a methodology to check whether in a given situation the controller ensures a specific property. Such a work raises difficult issues:

(1) the modelling of the environment and the vehicle requires a careful study to define which parameters are relevant and (2) the variety of possible incidents that may occur during the travel triggers a combinatory explosion that may forbid any verification procedure. Our approach. From a modelling point of view, we selected a stochastic high-level Petri net based approach. Indeed [START_REF] Ballarini | Hasl: A new approach for performance evaluation and model checking from concepts to experimentation[END_REF] the parallelism induced by the moves of the cars requires a model able to handle this feature (hence Petri nets), (2) this model should manage user-defined data structures and code (hence high-level Petri nets) and (3) the model should quantify the frequency of the different incidents as well as the unpredictability of the behaviour of the other cars (hence stochastic high-level Petri nets). In order to evaluate performance indicators of stochastic systems there are currently two main approaches. Numerical methods require to restrict the probability distributions occurring in the system in order to exhibit a Markovian-like behaviour. In addition, except in very particular cases, they cannot handle large scale systems. Statistical methods are more robust although they only provide confidence intervals for the performance indices. However for most of the applications, these intervals are sufficient. Contributions. With the approach described above, we propose a stochastic high-level Petri net modeling a traffic jam situation. Besides the probabilistic features representing the environment, this model takes into account the control of the autonomous vehicle by a C++ program. It is then given as input to the tool COSMOS, with two performance indicators: the expected travelled distance and the probability of collision. Using simulations in various situations, we produce estimations of these indices with confidence intervals.

We have considered two simple controllers: a basic one that adjusts its speed on the vehicle preceeding it without changing its lane and a slightly more evolved one that may change its lane depending on the situation. We have taken into account two behaviours for the other vehicles: either smooth speed changes or unpredictible ones. Our experimentations have established that a small increase in the controller capacities triggers a large increase about the vehicle safety performances. On the other hand the simulation time that we observed confirm that our approach is able to manage large scale models. Outline. The modeling formalism is described in Section 2 and the case study is presented in Section 3. We briefly explain the main features of the tool COSMOS in Section 4 and show our experimental results in Section 5. Finally, we present work in progress and perspectives in Section 6.

Formalism

In this section, we briefly describe the formalisms used in this work: Petri net variants to represent the model of the motorway and HASL formulas for the properties.

Petri nets

A Petri net is a bipartite graph, whose nodes are either places or transitions. Places may contain tokens, and depict the states of the system. Transitions represent the activities of the system, which correspond to state changes. Arcs from the input places of a transition are labeled by a condition on the tokens under which the transition can be fired. When the transition is fired (atomically), these tokens are consumed, while new tokens are produced in the output places of a transition, again according to the labels of the associated arcs. A marking is a mapping giving the number of tokens in each place.

p 1 t 1 p 2 p 3 t 2 p 4 t 3 Figure 1: A Petri net
For instance, in the Petri net of Figure 1, the absence of labels on arcs indicates a default value of 1. From the initial marking, which can be represented by the vector (1, 0, 2, 1), transition t 2 cannot fire because there is no token in input place p 2 , and firing t 3 results in marking (1, 0, 2, 0). On the other hand, from the same initial marking, sequence t 1 t 2 reaches marking (1, 0, 2, 2). High-level Petri nets are an extension of Petri nets where tokens carry information. Data types, called color sets, are associated with places and transitions and tokens respect the typing of places. The type of a transition specifies how it might be fired and is called a binding (since it binds local variables of the transition to values, see below).

Figure 2: A high-level Petri net, before and after firing a transition

For instance, the high-level Petri net of Figure 2 describes how processes might acquire resources. On edges, the tokens are described by variables x (a process) and y (a resource). In this example, process b has acquired resource 2 which is represented by the presence of token (b, 2)) in the rightmost place. It might have been any other combination of process in {a, b, c} and resource in {1, 2}.

To further increase the expressiveness of such Petri nets, we associate C code with some transitions, which will be executed at the end of the firing process. The global state of the net is thus defined as a tuple containing the marking (tokens present in the various places of the net) and the current values of the global variables of the C code. For instance one could manage a variable count that records the number of synchronisations between process and resource and would be incremented by the firing of the transition. Stochastic high-level Petri nets are a further extension, where a probabilistic distribution is associated with each color of a transition, to specify the random delay between the enabling of the transition and its possible firing. These distributions can be markingdependent and describe the stochastic behaviour of the model. Thus the configuration of such a net consists of: (1) the marking of the net, (2) the values of global C variables, (3) for any transition binding associated with an enabled transition firing a scheduled time and (4) the current simulation time. The configuration change involves the following stages: (1) determine the next firing among those with the earliest schedule, (2) advance the simution time, (3) update the marking w.r.t. the transition firing, (4) delete the disabled transition firings, and (5) for any newly enabled transition firings sample its delay distribution in order to get its schedule. The selection of the next transition firing is based first on the priority of the transitions and in case of multiple transition firings with same priority by a random choice related to the transition weights.

The model of the motorway depicted in Figure 4 is an example of such stochastic high-level Petri net, that will be explained in more details in Section 3.

HASL formulas

Properties of such stochastic high-level Petri nets are specified by performance indices, expressed in the logic HASL 3 . A formula of this logic is described by two components:

• a linear hybrid automaton which is, during execution, synchronized with the Petri net, in order to gather additional information, based on the LHA variables; • an expression which includes the state variables of the automaton, path operators (i.e. max, min, last), alongside with probability operators such as the expectation over successful runs, or the probability of a successful run. Example. We end this section with a toy example illustrating our approach on the computation of an estimation of π by the Monte-Carlo method. The idea is to select randomly points (x, y) in the square [0, 1] × [0, 1] and to check if they belong to the quarter disc with measure π/4 by testing x 2 + y 2 ≤ 1. Figure 3 depicts a simple Petri net with two transitions and a HASL formula composed of a LHA and the expression E(last(r)). A trajectory is obtained by synchronizing the LHA with the Petri net, first on transition e 1 , then on e 2 , producing random values for x (firing delay of e 1 ) and y (firing delay of e 2 ) respectively. The last value of r is then 4 if x 2 + y 2 ≤ 1, leading to one final state and 0 otherwise, leading to the other final state.

Case study

The case study concerns a (one way) motorway section shared by the controlled vehicle and other vehicles with trajectories that are randomized, but respect some constraints to keep them realistic. The controller is given by a C++ program and its goal is to avoid collision for the autonomous vehicle.

Model of the motorway

As shown in Figure 4, with the controlled vehicle drawn in red, the motorway section is discretized into cells, the cell with coordinates (i, j) representing position i on lane j. The model of the motorway with vehicles is the 3 Hybrid Automata Stochastic Language 5, with parameters the length N pos of the section, the number N l of lanes, the maximal speed v max , and the maximal number N veh of vehicles, given by the types of the tokens. The execution of the model starts with transition initGeneration, which is fired only once and produces the initial configuration (via the dashed arcs). The orange part handles the behaviour of the controlled vehicle while the blue part handles the other vehicles, represented by tokens in the associated places:

ẋ = 1 ẏ = 0 s 0 ẋ = 0 ẏ = 1 s 1 s 2 s 3 e 1 e2 ; x 2 + y 2 ≤ 1; r := 4 e 2 ; x 2 + y 2 > 1; r := 0 E(LAST(r)) (c)
• An environment vehicle is a token of the form (x, y, ẋ, ẏ) where (x, y) corresponds to the current cell and ( ẋ, ẏ) is the speed vector, composed of horizontal and vertical speed (on each axis, in cells per time unit). These tokens can be either in place otherVehicles or in place inProcess when an update is performed. • The controlled vehicle is a token stored in place selfVehicle. In addition to the elements used for The green part of the Petri net controls the different phases of the simulation. The model runs quasisynchronously, with a time step δ equal to the time step of the controller. Synchronously, the sim_step1 transition fires for each δ (with the Dirac distribution) and starts the following process:

exit x > xmax pri=2 update_self pri=2 selfVehicle Controller collision end x > xmax < x, y, ẋ, ẏ > < x, y, ẋ, ẏ > < x, y, ẋ, ẏ > < x, y, ẋ, ẏ > < x, y, ẋ, ẏ > < x, y, ẋ, ẏ > < x, y, ẋ, ẏ, ẍ, ÿ > < x, y, ẋ, ẏ, ẍ, ÿ > < x, y, ẋ, ẏ > < x, y, ẋ , ẏ , ẍ, ÿ > < x, y, ẋ, ẏ, ẍ, ÿ > < x, y, ẋ, ẏ, ẍ, ÿ > < x, y, ẋ, ẏ, ẍ, ÿ > initialized initGeneration C code C code C code C code C code
• In transition sim_step2, the new position of environment vehicles is computed using their current speed. The new speed is then randomly generated using a distribution that depends on environment parameters. • In transition sim_step3, the new position and speed of controlled vehicle is computed, using its current speed and acceleration. • The last step uses transition Controller which executes the associated C++ program, resulting in the update of the controlled vehicle acceleration.

Asynchronously, new vehicles are added at the start of the section, using transition enter. This transition is equipped with a uniform distribution on interval [a, b] where a and b are parameters, which influence the load of the motorway.

The pink part on the right of the model handles the end of the simulation: either the controlled vehicle reaches the end of the section, which corresponds to the test x > x max , with x max = N pos or a collision happens between the controlled vehicle and one of the environment vehicles.

All informations about the controlled vehicle are given to the controller, together with a view on the other vehicles modeling the input received from sensors. For instance, Figure 6 shows a possible realization of this communication.

← vmax → ← vmax → For the first one, we use the HASL formula represented in the upper part of Figure 7, where T denotes the set of all transitions of the Petri net in Figure 5. The synchronization implies that the state s col is reached exactly when transition collision is fired in the simulation and the expression PROB means that the value returned is the probability of reaching s col .

The second performance indice is obtained via the HASL formula depicted in the bottom part of Figure 7.

With respect to the previous automaton, we add a new transition reaching state s end that will be synchronized with the transition end of the Petri net, and a variable x that will take the current value of the horizontal position when the transition is fired. The expression E(LAST(x)) (expected value of the last value of x) yields the desired indice.

Cosmos

We now give a brief description of the tool COSMOS used to compute the performance indices. 4.1 Architecture COSMOS is a statistical model checker accepting Discrete Event Dynamic System (DEDS) as input models. In particular COSMOS takes as input several types of stochastic Petri nets with general distributions. As shown above in Figures 3 and7, the specification to be checked is given as an HASL formula described by a Linear Hybrid Automaton (LHA) and an expression. The main algorithm of this tool randomly simulates the DEDS according to its stochastic semantics and synchronizes it with the execution of the automaton. During the synchronization, it evaluates HASL expressions. A statistical procedure decides when to stop the simulation and produces a confidence interval for a HASL expression. The tool COSMOS consists of about 22000 lines of C++ code and is freely available at [2] under the Gnu General Public License version 3 (GPLv3). The tool relies on code generation to perform efficient simulation. It is divided into three main parts:

1. The parsing and code generation part reads the input files and the command line to build data structures for the DEDS and the automaton. Then optimised C++ code simulating both the behaviors of the DEDS and the automaton is generated. The resulting code is compiled by a C++ compiler and linked with the simulator library. The resulting binary is the simulator program. 2. The simulator part is a library implementing the algorithm synchronizing the DEDS and the automaton. It also implements the stochastic generation of events using the pseudo random number generator provided by the BOOST library and handles these events in an event queue. 3. The server part launches several copies of the simulator and aggregates their results. According to statistical parameters, a procedure decides whether enough trajectories have been simulated and stops all simulators when needed. Then, HASL expressions are evaluated and several output files are produced according to options. The computation of confidence intervals uses the BOOST library for the computation of quantiles of the normal distribution function and binomial distribution.

Several tools interact with COSMOS either by calling it or by being called by it:

• A C++ compiler is required to build the simulator from the generated code. Until now, GCC and Clang have been used. • When the model is Markovian and the automaton has no clock, PRISM can be called by the simulator.

In this case a state space generator is used and the CTMC of the product between the model and the automaton is given to PRISM. The vector of probabilities computed by PRISM on this model is parsed by COSMOS. This allows one to use PRISM to compute transient and steady state probabilities. • The plotter GnuPlot can be called by COSMOS to produce a graph providing visualization of the results. • Several OCaml scripts shipped with COSMOS perform benchmark, testing and plotting.

Application fields

In addition to the statistical model checking of DEDS on which COSMOS has shown its efficiency (see [START_REF] Ballarini | Hasl: A new approach for performance evaluation and model checking from concepts to experimentation[END_REF] for benchmarks with other tools), the particular architec-ture of COSMOS have proven useful in several projects:

• The simulation engine has been specialised to handle simulation of rare events. By altering the sampling of distribution in the simulation algorithm efficient estimations of rare event probability have been computed [START_REF] Barbot | Coupling and importance sampling for statistical model checking[END_REF]. • Thank to the very small footprint of the generated simulator, COSMOS has been used for the cosimulation of a pacemaker software with a model of the human heart. The generated simulator was small enough to fit in the memory of microcontroller on which live power consumption was measured [START_REF] Barbot | Building Power Consumption Models from Executable Timed I/O Automata Speci-fications[END_REF]. • Custom probability distribution defined by polynomials have been used to sample uniform trajectory for timed automata [START_REF] Barbot | Uniform Sampling for Timed Automata with Application to Language Inclusion Measurement[END_REF].

Statistical procedures

We now detail the different statistical procedures proposed by COSMOS for evaluating HASL expression depending on several criteria.

• Sequential hypothesis testing [START_REF] Wald | Sequential tests of statistical hypotheses[END_REF]. This procedure checks whether a probability is above a threshold. Parameters of this procedure are the probability of an error for a positive answer and a negative answer and the width of the indifference region. When the value of the probability is outside the indifference interval, the probability of an error is bounded by the parameter corresponding to the answer.

• Chernoff-Hoeffding bounds [8].

This static method requires three related parameters, each of them can be determined by the two others. These parameters are the interval width, the confidence level and the number of samples. It outputs a confidence interval whose width satisfies the requirement and where the probabilistic guarantee is exact. It applies to estimate the expectation of a bounded random variable.

• Chow-Robbins bounds [6].

This sequential method requires two parameters: the interval width and the confidence level. It outputs an interval whose width satisfies the requirement and where the probabilistic guarantee is asymptotic w.r.t. the width of the interval. It applies to estimate the expectation of a random variable, when no known bound is available.

• Gaussian approximation. This static method requires two parameters. The number of samples has to be given. The second parameter is either the confidence level or the interval width, one of these determining the other one. It ouputs an interval whose width satisfies the requirement and where the probabilistic guarantee is asymptotic w.r.t. the number of samples. It applies to estimate the expectation of a random variable. It is based on the central limit theorem. • Clopper-Pearson bound [START_REF] Clopper | The use of confidence or fiducial limits illustrated in the case of the binomial[END_REF] This static method computes confidence intervals for binomial distribu-tions. It takes as input three parameters, the total number of samples, the confidence level and the number of successful samples and outputs a confidence interval for the probability of a sample to be successful.

Evaluation Description.

To evaluate our approach we have modelled simple controllers. We first study a basic controller which only aims at monitoring the vehicle in front of it and aligns its velocity to avoid collision with it. When there is no vehicle in front of it or if it is far ahead, this basic controller speeds up until it reaches a maximal velocity v max . Then we study a more advanced controller which is able to change its lane to take over the vehicle in front of it. In order to change its lane the controller monitors vehicles in the two adjacent lanes. The controller initiates a take over only when the speed of the vehicle in front of him is slower than the speed v max and when there is no vehicle in one of the adjacent lanes. In the positive case, the controller goes to the vehicle-free lane. We have evaluated the controllers in the environment described in section 3 with two kinds of behaviours for other vehicles. One set of experiments in which all speed changes of other vehicles are smooth, at each step of simulation vehicles either stay at the same speed, moderately accelerate (the speed is increased by 1) or moderately decelerate (the speed is increased by 1). Those behaviours produce a highly predictive environment making the controller job easier. In contrast the second set of experiment involves vehicles which speed changes considerably: at each step of simulation, every vehicle randomly selects a new speed in a predefined interval. Evaluation. The first objective of this benchmark is to compare the performances of the two controllers in different situations. As explained in Section 3.2, two performance indices have been measured: the probability of a collision and the expected covered distance before collision if any. The second objective is to quantify the influence of these parameters on the simulation time.

Observation. The results of our simulations are collected in Table 1. For these computations we simulate a motorway with 2 lanes and 1000 cells. The controlled vehicle is surrounded by 20 other vehicles whom speed varies between 3 and 5 cells per step. More precisely, all vehicles (including the controlled one) are generated randomly, with an uniform distribution on both lane and cells (up to the 200 th ). If a vehicle is generated on a cell where there is another vehicle, we generate new values for both lane and cell. We perform all the simulations on a single machine with 12 Intel Xeon cores using 8 parallel threads. Table 1: Evaluation of controllers. For each measure, controller and other vehicle behaviours we provide a 99% confidence interval of the measure, the time in second require to perform the simulation and the number of simulated trajectories.

Comparing the probability of collision between the two

Smooth velocity change

Aggressive velocity change

controllers, we observe that the lane changing controller is far better than the basic one: 2.3% probability of collision vs 83.8% in the smooth environment and 2.2% vs 84.7% it the more aggressive one. We notice that the behaviours of other vehicles do not have a major impact on the probability of collisions. Similarly, the average travelled distance before collision is highly different between the two controllers. We also have identified several limits of our simulation which we should overtake to produce more precise results.

Compared to real vehicles which feature turn signals and braking lights, there is no communication between vehicles in our simulation. This prevents the controller from synchronising its action with those of other vehicles. The behaviours of vehicles on the motorway should be enhanced to feature some communication.

We observe in table 1 that when the probability of collisions became small, the number of simulation required to obtain relevant estimates became large. This is clear when comparing the required time to estimate the average distance before collision for the two controllers (71s vs 4147s and 74s vs 3766s). Thus the simulation could be intractable when the probability of collisions becomes close to zero. This is a well-known difficulty in presence of rare event for which several theoretical techniques and practical tools have been developed in the literature and can be used to improve this simulation.

In Table 1 we observe that most collisions occurred at the beginning of the simulation. They occur around cell 104 for the lane changing controller and around cell 275 for the basic one. This shows that the simulation is biased by its initial state. More reliable results could be obtained by simulating a sliding window of the motorway around the controlled vehicle. Instead of simulating the controlled vehicle on the entire motorway we could make the controlled vehicle static in the middle of a short motorway and simulate all vehicles relatively to the controlled one.

Conclusion

In this work, we conducted with COSMOS several experiments on autonomous vehicle controllers, where the environment is modeled by a stochastic high level Petri net. With this model, it is possible to change easily the parameters of the simulations, producing different settings for the flow of other vehicles and their speed. However, the motorway section still corresponds to a basic situation. Therefore, future research directions concern the design of refined models, where other situations could be taken into account. This could include for instance the addition of an emergency lane where the controlled vehicle could be led if there is no other way to avoid collision. Other interesting situations correspond to the presence of arrival or exit lanes, or of an alredy existing collision between other vehicles blocking one of the lanes. Finally, considering a controller designed with Simulink would lead to check more elaborated versions of it.

  1. Introduction Context. Intelligent Transport Systems (ITS) address the numerous challenges faced by the design of safe softwares dedicated to (almost) autonomous transportation systems.

Figure 3 :Figure 4 :

 34 Figure 3: Computing an approximation of π (a) with a Petri net (b) and an associated HASL formula (c)

Figure 5 :

 5 Figure 5: Motorway model

Figure 6 :

 6 Figure 6: A possible view of the controller

Figure 7 :

 7 Figure 7: Two HASL formulas (a) for the probability of collision and (b) for expected travelled distance

Simulation pour la Sécurité du Véhicule Autonome (Simulation for the Safety of Autonomous Vehicle)

Acknowledgement

This research work has been carried out in the framework of IRT SystemX, Paris-Saclay, France, and therefore granted with public funds within the scope of the French Programme "Investissements d'Avenir".


Mihai Dascălu
email: mihai.dascalu@cs.pub.ro

Ștefan Trăușan-Matu

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

Towards an Integrated Approach for Evaluating Textual Complexity for Learning Purposes

Keywords: textual complexity, Latent Semantic Analysis, readability, Support Vector Machines

Understanding a text in order to learn is subject to modeling and is partly dependent to the complexity of the read text. We transpose the evaluation process of textual complexity into measurable factors, identify linearly independent variables and combine multiple perspectives to obtain a holistic approach, addressing lexical, syntactic and semantic levels of textual analysis. Also, the proposed evaluation model combines statistical factors and traditional readability metrics with information theory, specific information retrieval techniques, probabilistic parsers, Latent Semantic Analysis and Support Vector Machines for best-matching all components of the analysis. First results show a promising overall precision (>50%) and near precision (>85%).

Introduction

Measuring textual complexity is in general a difficult task because the measure itself is relative to the reader and high differences in the perception for a given lecture can arise due to prior knowledge in the specific domain, familiarity with the language or to personal motivation and interest. Readability ease and comprehension are related to the readers' education, cognitive capabilities and background experiences. Therefore a cognitive model of the reader must be taken into consideration and the measured complexity should be adapted to this model. Additionally, software implementing such functionalities should be adaptive in the sense that, for a given target audience, the estimated levels of textual complexity measured for specific texts should be adequate and relevant. Fortunately, the target texts processed in this paper were accessible from a syntactical and vocabulary viewpoint by primary school pupils, and the required level of knowledge to grasp the read story was also on the same range.

Assessing the textual complexity of the material given to pupils is a common task that teachers encounter very often. However, this assessment cannot be performed without taking into account the actual pupils' reading proficiency and this point makes it time-consuming. Moreover, the impact of textual complexity on instruction and learning is important: pupils read faster and learn better if textual materials are not too complex nor too easy. A web-based system can help teachers select and calibrate the appropriate texts presented to students and also help the latter attain their own learning objectives in selecting not too simple nor too difficult reading materials.

Our aim is to design and implement a system that automatically gives a measure of the complexity of texts read by children by studying the relations between human vs. computer measures of this textual complexity, similar to some extent to [START_REF] Petersen | A machine learning approach to reading level assessment[END_REF]. Although there are numerous applications that give estimates regarding textual complexity, they often do not rely on cognitive models of human reading or use only simple lexical or syntactic factors. An example of a complex system covering multiple perspectives of discourse analysis is Coh-Metrix 2 [START_REF] Mcnamara | Coh-Metrix: Capturing linguistic features of cohesion[END_REF] that automatically calculates the coherence of texts and determines how text elements and constituents are connected for specific types of cohesion. Besides lexical and syntactic factors, POS tagging and Latent Semantic Analysis (LSA), used also within Coh-Metrix 2, we provide an integrated approach through Support Vector Machines (SVMs) that covers in a novel manner all previous dimensions, tightly connected to the implemented discourse model. Therefore, our model is capable of automatically adapting its categories based on the training corpus, enabling us to personalize even further the classification process and the assigned weights to each evaluation factor.

Due to the fact that textual complexity cannot be determined by enforcing a single factor of evaluation, we propose a multitude of factors, categorized in a multilayered pyramid [START_REF] Trausan-Matu | Considering textual complexity and comprehension in Computer-Supported Collaborative Learning[END_REF], from the simplest to the more complex ones, that combined provide relevant information to the tutor regarding the actual "hardness" of a text. The first and simplest factors are at a surface (word) level and include readability metrics, utterance entropy at stem level and proxies extracted or derived from Page's [START_REF] Page | The imminence of grading essays by computer[END_REF] automatic essay grading technique. At the syntactic level, structural complexity is estimated from the parsing tree in terms of max depth and size of the parsing structure [START_REF] Gervasi | Quantitative assessment of textual complexity[END_REF]. Moreover, normalized values of occurrences of specific parts of speech (mostly prepositions) provide additional information at this level. Semantics is addressed through topics that are determined by combining Tf-Idf with cosine similarity between the utterance vector and that of the entire documents. The textual complexity at this level is expressed as a weighted mean of the difficulty of each topic, estimated in computations as the number of syllables of each word. Moreover, textual complexity is evaluated in terms of semantic cohesion determined upon social networks analysis metrics applied at macroscopic level upon the utterance graph [START_REF] Trausan-Matu | A polyphonic model and system for inter-animation analysis in chat conversations with multiple participants[END_REF]. Discourse markers, co-references, rhetorical schemas and argumentation structures are also considered, but are not included in current experiments.

By considering the disparate facets of textual complexity and by proposing possible automatic methods of evaluation, the resulted measurement vectors provide tutors valuable information regarding the hardness of presented texts. The remainder of this paper details the various metrics. All the measures used to evaluate textual complexity are then unified into a single result by using SVMs in the effort to best align automatic results to the classes manually assigned by teachers. The paper ends with conclusions and future improvements

Surface Analysis

Surface analysis addresses lexical and syntactic levels and consists of measures computed to determine factors like fluency, complexity, readability taking into account lexical and syntactic elements (e.g., words, commas, phrase length, periods).

Readability

Traditional readability formulas [START_REF] Brown | An EFL readability index[END_REF] are simple methods for evaluating a text's reading ease based on simple statistical factors as sentence length or word length. Although criticized by discourse analysts [START_REF] Davison | On the failure of readability formulas to define readable texts: A case study from adaptations[END_REF] as being weak indicators of comprehensibility and for not closely aligning with the cognitive processes involved in text comprehension, their simple mechanical evaluation makes them appealing for integration in our model. Moreover, by considering the fact that reading speed, retention and reading persistence are greatly influenced by the complexity of terms and overall reading volume, readability formulas can provide a viable approximation of the complexity of a given text, considering that prior knowledge, personal skills and traits (e.g. intelligence), interest and motivation are at an adequate level or of a similar level for all individuals of the target audience. In addition, the domain of texts, itself, must be similar because subjectivity increases dramatically when addressing cross-domain evaluation of textual complexity. Starting from simple lexical indicators, numerous mathematical formulas were developed to tackle the issue of readability. The following three measures can be considered the most famous:

1. The Flesch Reading Ease Readability Formula scores texts on a 100 point scale, providing a simple approach to assess the grade-level of pupils: the higher the score, the easier the text is to read (not necessarily to be understood). 2. The Gunning's Fog Index (or FOG) Readability Formula estimates the number of years of formal education a reader of average intelligence needs to understand the given text on the first reading. Although considering that words with more than two syllables are complex can be seen as a drawback, we chose this estimation due to its high precision and simplicity. 3. The Flesch Grade Level Readability Formula uses the same factors as the first readability metric and rates texts based on U.S. grade school levels.

Trins and proxes

Page's initial study was centered on the idea that computers can be used to automatically evaluate and grade student essays using only statistically and easily detectable attributes, as effective as human teachers [START_REF] Page | The imminence of grading essays by computer[END_REF][START_REF] Trausan-Matu | A polyphonic model and system for inter-animation analysis in chat conversations with multiple participants[END_REF]. In order to perform a statistical analysis, Page correlated two concepts: proxes (computer approximations of interest) with human trins (intrinsic variables -human measures used for evaluation) for better quantifying an essay's complexity. A correlation of 0.71 proved that computer programs could predict grades quite reliably, similar to the inter-human correlation. Starting for Page's metrics of automatically grading essays and taking into consideration Slotnick's method of grouping proxes based on their intrinsic values, the following categories were used for estimating complexity (see Table 1). Normalization is inspired from Data-Mining and our results improved by applying the logarithmic function on some of the previous factors in order to smooth results, while comparing documents of different size. All the above proxes determine the average consistency of sentences and model adequately their complexity at surface level in terms of the analyzed lexical items.

Complexity, Accuracy and Fluency

Complexity, accuracy, and fluency (CAF) measures of texts have been used in linguistic development and in second language acquisition (SLA) research.

Complexity captures the characteristic of a learner's language, reflected in a wider range of vocabulary and grammatical constructions, as well as communicative functions and genres [START_REF] Schulze | Measuring textual complexity in student writing[END_REF]. Accuracy highlights a text's conformation to our experience with other texts, while fluency, in oral communication, captures the actual volume of text produced in a certain amount of time. Similar to the previous factors, these measures play an important role in automated essay scoring and textual complexity analysis. Schulze [START_REF] Schulze | Measuring textual complexity in student writing[END_REF] considered that selected complexity measures should be divided into two main facets of textual complexity: sophistication (richness) and diversity (variability of forms). The defined measures depend on six units of analysis: letter (l), word form (w), bigram (bgroups of two words) and period unit (p), word form types (t) and unique bigrams (u). Additionally, textual complexity is devised into lexical and syntactic complexity: Lexical Complexity:  Diversity is measured using Carroll's Adjusted Token Type Ratio (Eq. 1) [START_REF] Schulze | Measuring textual complexity in student writing[END_REF]:

𝑣 = √ , 𝑤𝑖𝑡ℎ √ ≤ 𝑣 ≤ (1)
 Sophistication estimates the complexity of a word's form in terms of average number of characters (Eq. 2) [START_REF] Schulze | Measuring textual complexity in student writing[END_REF]:

𝑣 = , 𝑤𝑖𝑡ℎ 1 ≤ 𝑣 ≤ 𝑙 (2)
Syntactic Complexity:  Diversity captures syntactic variety at the smallest possible unit of two consecutive word forms. Therefore Token Type Ratio is also used, but at a bigram level (Eq. 3) [START_REF] Schulze | Measuring textual complexity in student writing[END_REF]:

𝑣 = √ , 𝑤𝑖𝑡ℎ √ ≤ 𝑣 ≤ (3)
 Sophistication is expressed in terms of mean number of words per period unit length and it's intuitive justification is that longer clauses are, in general, more complex than short ones (Eq. 4) [START_REF] Schulze | Measuring textual complexity in student writing[END_REF]:

𝑣 = , 𝑤𝑖𝑡ℎ 1 ≤ 𝑣 ≤ 𝑝 (4)
All the previous measures can be integrated into a unique measure of textual complexity at lexical and syntactic levels. Following this idea, these factors were balanced by computing a rectilinear distance (Raw Complexity -RC) as if the learner had to cover the distance along each of these dimensions [START_REF] Schulze | Measuring textual complexity in student writing[END_REF]. Therefore, in order to reach a higher level of textual complexity, the learner needs to improve on all four dimensions (Eq. 5) [START_REF] Schulze | Measuring textual complexity in student writing[END_REF]:

𝑅𝐶 = 𝑣 - √ + |𝑣 -1| + 𝑣 - √ + |𝑣 -1| (5)
Afterwards, CAF is computed as a balanced complexity by subtracting the range of the four complexity measures (max -min) from the raw complexity measure (Eq. 6): 𝐶𝐴𝐹 = 𝑅𝐶 -(max(𝑣 , 𝑣 , 𝑣 , 𝑣 ) -min(𝑣 , 𝑣 , 𝑣 , 𝑣 ))

The ground argument for this adjustment is that if one measure increases too much, it will always be to the detriment of another. Therefore, the measure of raw complexity is decreased by a large amount if the four vector measures vary widely and by a small amount if they are very similar. Moreover, the defined measure captures lexical and syntactic complexity evenly, provides two measures for sophistication and two measures for diversity and, in the end, compensates for large variations of the four vector measures.

Entropy

Entropy, derived from Information Theory, models the text in an ergodic manner and provides relevant insight regarding textual complexity at character and word level by ensuring diversity among the elements of the analysis. The presumption of induced complexity pursues the following hypothesis: a more complex text contains more information and requires more memory and more time for the reader to process. Therefore, disorder modeled through entropy is reflected in the diversity of characters and of word stems used, within our implemented model, as analysis elements. The use of stems instead of the actual concepts is argued by their better expression of the root form of related concepts, more relevant when addressing diversity at syntactic level.

Part of Speech Tagging and Parsing Tree Structure

Starting from different linguistic categories of lexical items, our aim is to convert morphological information regarding the words and the sentence structure into relevant metrics to be assessed in order to better comprehend textual complexity. In this context, parsing and part of speech (POS) tagging play an important role in the morphological analysis of texts, in terms of textual complexity, by providing two possible vectors of evaluation: the normalized frequency of each part of speech and the structural factors derived from the parsing tree. Although the most common parts of speech used in discourse analysis are nouns and verbs, our focus was aimed at prepositions, adjectives and adverbs that dictate a more elaborate and complex structure of the text. Moreover, pronouns, that through their use indicate the presence of co-references, also indicate a more inter-twined and complex structure of the discourse. On the other hand, multiple factors can be derived from analyzing the structure of the parsing tree: an increased number of leafs, a greater overall size of the tree and a higher maximum depth indicate a more complex structure, therefore an increased textual complexity. Our implemented system uses the log-linear Part of Speech Tagger publicly available from Stanford University [START_REF] Klein | Accurate Unlexicalized Parsing[END_REF] with the "bidirectional-wsj-0-18.tagger" package as English tagger, therefore ensuring an accuracy of 97.18% on WSJ 19-21 concepts and of 89.30% on unknown words.

Semantic Analysis -Coherence through LSA

Coherence is a central issue to text comprehension and comprehension is strongly related to textual complexity. In order to understand a text, the reader must first create a well-connected representation of the information withheld. This connected representation is based on linking related pieces of textual information that occur throughout the text. Coherence is determined and maintained through the links identified within the utterance graph [START_REF] Trausan-Matu | A polyphonic model and system for inter-animation analysis in chat conversations with multiple participants[END_REF]. Our implemented discourse model characterizes the degree of semantic relatedness between different segments through means of Information Retrieval (Term Frequency -Inverse Document Frequency) reflected in word repetitions [START_REF] Trausan-Matu | Considering textual complexity and comprehension in Computer-Supported Collaborative Learning[END_REF] and of LSA, capable of measuring similarity between discourse segments through concepts of the vector space [START_REF] Mcnamara | Coh-Metrix: Capturing linguistic features of cohesion[END_REF]. The power of computing semantic similarity with LSA comes from analyzing a large corpus from which LSA builds relationships between a set of documents and terms contained within. The main assumption is that semantically related words will co-appear throughout documents of the corpus and will be indirectly linked by concepts after the Single Value Decomposition specific to LSA.

Coherence is determined using the utterance graph modeled as a Directed Acyclic Graph (DAG) of sentences, ordered sequentially through the ongoing discourse. The first thing that needs to be addressed is semantic cohesion between two sentences which is seen as the degree of inter-connection among them [START_REF] Trausan-Matu | Considering textual complexity and comprehension in Computer-Supported Collaborative Learning[END_REF]. This similarity is computed by combining repetitions of stems and Jaccard similarity as measures of lexical cohesion, with semantic similarity computed by means of LSA (Eq. 7 and 8):

𝑐𝑜ℎ(𝑢, 𝑣) = |𝑟𝑒𝑝𝑒𝑡𝑖𝑜𝑛𝑠| × | , | | | × 𝑐𝑜𝑠(𝑣𝑒𝑐𝑡𝑜𝑟(𝑢), 𝑣𝑒𝑐𝑡𝑜𝑟(𝑣)) (7)
𝑣𝑒𝑐𝑡𝑜𝑟 (𝑢) = ∑ (1 + |𝑤𝑜𝑟𝑑 ∈ 𝑢| ) × | | | ∈ | × 𝑈 [𝑤𝑜𝑟𝑑 ] (8)
where 𝑈 [𝑤𝑜𝑟𝑑 ] is the vector of 𝑤𝑜𝑟𝑑 in the 𝑈 matrix from LSA.

After determining all possible connections between the sentences of a text through the previous equations, the utterance graph is built by selecting the links that have their corresponding values above a threshold (in our experiments, the best empirical value was the mean value of all viable cohesion values determined for any possible link within our initial text). Overall, coherence is evaluated at a macroscopic level as the average value for all links in the constructed utterance graph. Co-references and other specific discourse analysis methods (e.g., argumentation acts) will be used to further refine the previous DAG.

Support Vector Machines

All the measures previously defined capture in some degree different properties of the analyzed text (readability, fluency, accuracy, language diversity, coherence, etc.) and therefore can be viewed as attributes that describe the text. In order to use these attributes to estimate the complexity of the text, we have used a classifier that accepts as inputs text attributes and outputs the minimum grade level required by a reader to comprehend the specified text. Therefore multiple Support Vector Machine (SVM) classifiers are used to achieve the desired result. A SVM is typically a binary linear classifier that maps the input texts seen as d-dimensional vectors to a higher dimensional space (hyperspace) in which, hopefully, these vectors are linearly separable by a hyperplane. Due to the fact that binary classifiers can map objects only into two classes, our multiclass problem can be solved using multiple SVM, each classifying a category of texts with different predefined classes of complexity. A one-versus-all approach implementing the winner-takes-all strategy is used to deal with the problem of multiple SVM kernel returning 1 for a specific text (the classifier with the highest output function assigns the class).

LIBSVM [START_REF] Chang | LIBSVM: a library for support vector machines[END_REF] was used to ease the implementation of the classifier. An RBF with degree 3 was selected and a Grid Search method was enforced to increase the effectiveness of the SVM through the parameter selection process. Exponentially growing sequences for C and γ were used (𝐶 ∈ {2 , 2 , … , 2 , 2 }, 𝛾 ∈ {2 , 2 , … , 2 , 2 }) and each combination of parameter choices was checked using a predefined testing corpus. In the end, the parameters with the best obtained precision were picked.

Preliminary validation results

The preliminary validation experiments were run on 249 reading assignments given by teachers to pupils ranging from 1st grade to the 5th grade (29 -C1, 41 -C1, 66 -C3, 71 -C4, 42 -C5). All the previous measurements have been automatically extracted for each these texts and were later used as inputs for the SVM. The split between the training corpus and the testing one was manually performed by assigning 166 texts as training set and the remaining for evaluation. Additional to data normalization that was previously performed, all factors were linearly scaled to the [-1; 1] range. Two types of measures were used to evaluate the performance of our model: Precision (P), as the percent to which the SVM predicted the correct classification for the test input, and Near Precision (NP), as the percent to which the SVM was close in predicting the correct classification (i.e. answered n th grade instead of (n+1) th grade). NP was introduced due to the subjectivity of the evaluation of the corresponding grade level and also due to the fact that the complexity of the finishing n th year text may be very close to one from the beginning of the (n+1) th year.

Table 2 presents in detail the optimum C and 𝛾 parameters determined for the SVMs via Grid Search method, precision and near precision for all classes, average and weighted average of both precision and near precision. cohesive than a text from C1). Also, the most difficult class to identify was the last one because, in general, there are relatively small changes in comparison to the previous class and it's difficult to highlight the differences.

Conclusions and Future Development

By combining different factors as readability, lexical and syntactic complexity, accuracy and fluency metrics, part of speech evaluation and characteristics of the parsing tree with LSA embedded within the discourse model, we obtained an elaborate and multi-perspective model capable of providing an overall balanced measure for textual complexity. In order to fine-tune even further the results, additional investigations and experiments are to be conducted to find the best parameters for the SVM, making predictions more reliable, whereas additional coherence measurement techniques will be included for enriching the semantic perspective of our analysis. Our research can be easily extended to any online materials and can be considered a cornerstone in developing an adaptive system for proposing personalized reading materials. This adaptive system would also assess the relation between textual complexity and pupils' understanding, as measured by online questionnaires.

Table 1 .

 1 Surface analysis proxes

	Quality	Proxes
	Fluency	Normalized number of commas
		Normalized number of words
		Average number of words per sentence
	Diction	Average word length
		Average number of syllables per word
		Percent of hard words (extracted from FOG Formula)
	Structure	Normalized number of blocks (paragraphs)
		Average block (paragraph) size
		Normalized number of utterances (sentences)
		Average utterance (sentence) length

Table 2 .

 2 Precision (P%) and Near Precision (NP%) for all evaluation factors

	Factor	C	𝜸	C1 P / NP	C2 P / NP	C3 P / NP	C4 P / NP	C5 P / NP	Avg. P/NP	Weig. Avg. P/NP
	Readability	128	0.125	90 /	14 /	27 /	78 /	14 /	44.6 /	44.5 /
	Flesch			90	64	91	100	86	86.2	88.2
	Readability FOG	32	0.5	80 /	29 /	32 /	83 /	7 /	46.2 /	47.4 /
				90	64	100	91	79	84.8	86.8
	Readability	32768	2	90 /	7 /	45 /	57 /	14 /	42.6 /	42.2 /
	Kincaid			90	57	95	100	57	79.8	83.2
	Normalized no. of	0.5	2	0 /	29 /	14 /	83 /	0 /	25.2 /	32.2 /
	commas			80	57	100	91	71	79.8	83.1
	Avg. sentence	32	2	80 /	7 /	55 /	61 /	36 /	47.8 /	48.5 /
	length			80	93	82	100	50	81	83.3
	Normalized no. of	2048	0.008	50 /	79 /	0 /	83 /	0 /	42.4 /	42.5 /
	words			100	86	91	83	71	86.2	85.6
	Avg. word length	2048	0.008	80 /	43 /	50 /	61 /	29 /	52.6 /	51.9 /
				80	93	86	96	50	81	83.2
	Avg. no. of	128	0.031 100/	0 /	5 /	100/	0 /	41 /	41.5 /
	words/ sentence			100	21	95	100	93	81.8	84.5
	Avg. no. of	2	0.125	60 /	0 /	41 /	87 /	0 /	37.6 /	42.7 /
	syllables/word			60	71	100	100	79	82	87
	Percent of	0.5	0.5	70 /	0 /	41 /	83 /	0 /	38.8 /	42.7 /
	complex words			70	86	91	100	79	85.2	88.3
	Word Entropy	0.125	8	80 /	57 /	23 /	65 /	0 /	45 /	43.3 /
				100	100	95	83	64	88.4	87.8
	Character Entropy	8	0.5	70 /	7 /	18 /	87 /	0 /	36.4 /	38.9 /
				70	14	100	96	86	73.2	78.8

Taking into consideration the previous experiment, we have obtained a promising overall precision (>50%) and an excellent near precision (>85%), taking into consideration the difficulty and the subjectivity of the task at hand. Moreover, as expected, the effectives of our method increased by combining multiple factors and, although simple in nature, readability formulas, average sentence length, average word length and balanced CAF provided the best alternatives at lexical and syntactic level. Also, character entropy proved to be a lesser relevant factor than word entropy that reflects vocabulary diversity. In term of parts of speech tagging, prepositions had the highest correlation of all types of parts of speech, whereas depth and size of the parsing tree provided a good insight of textual complexity. In contrast, semantic factors had lower scores because the evaluation process at this level is based on the links between sentences; but texts used in educational environments are characterized by a low variance between different classes in terms of the computed semantic cohesion function (a text belonging to C3 does not necessarily have to be more


Dalia Marcela Rojas-Castro
email: dalia_marcela.rojas_castro@univ-lr.fr

Arnaud Revel
email: arnaud.revel@univ-lr.fr

Michel Ménard
email: michel.ménard@univ-lr.fr

Robotic and Document Analysis Cross-Fertilization: Improving Place Cells Based Robot Navigation

Keywords:

This paper proposes a place cell model allowing place recognition in the context of robot autonomous navigation. The robustness of this approach lies in the fact that even if one or several patterns characterizing the place are removed or not visible anymore, a place can still be recognized. The recognition process in this work is improved with respect to the state-of-theart place cells approach. Additionally, the interconnection of the modules is made such that the robot is able to learn new places as it navigates and interacts with the environment to get to its final destination. Experimental results validate the advantage of the incremental learning allowing the robot to cope with any unforeseen changes and thus adapting itself to the environment.

Place-cells recognition; robot navigation; visual

INTRODUCTION

Robot navigation based on visual perception systems (such as onboard camera systems) has been especially prevalent over the last three decades. These systems are robust and reliable as they provide detailed information about the environment, which may be overlooked by other types of sensors.

Several researches have focus their work on visual place recognition, particularly in the context of autonomous robot navigation, where different approaches have been proposed for solving mapping and robot localization problems. They endow the robot the capacity of "understanding" its surrounding environment, knowing its position with respect to a reference point and thus facilitating its navigation task.

Place recognition is used since a place can be identified as a stable reference point that can be learned by keeping in memory the location of the most relevant perceived patterns within the panoramic visual field of the robot. Returning to this place then consists in navigating until recognizing the same learned patterns.

In the state-of-the-art, Gaussier [START_REF] Gaussier | From view cells and place cells to cognitive map learning: processing stages of the hippocampal system[END_REF] has proposed a biologically inspired approach for recognizing places within the navigation environment. The robustness of this approach lies in the fact that even if one or several patterns characterizing the place are removed or not visibly available anymore, a place can still be recognized. Additionally, by means of a triangulation process it is possible to obtain information about the robot's position with respect to the surrounding environment. Therefore, the underlying idea of this paper is to extend this system to allow a robust navigation of a humanoid robot... Our approach addresses the problem in a manner that differs mainly in two points:

Firstly, the procedure for detecting the landmarks undertakes two-classification process. The SIFT local descriptor [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF] and a visual bag of words model are first used in order to describe distinctly the salient features of all the images. Then, the features are clustered according to their proximity in terms of distance and the resulting groups are considered as salient landmarks. Finally, each landmark is compared to others by computing the norm of the difference between the features describing them.

Secondly, the internal computation of the neural components are modified in order to allow the robot to compare the landmarks perceived from different places during navigation, by using a vigilance term inspired by the work of Grossberg [START_REF] Carpenter | Fuzzy ARTMAP: a neural network architecture for incremental supervised learning of analog multidimensional maps[END_REF] and learn them when not recognized. Consequently, the system learns incrementally.

This system has been conceived such that it is able to interact with the other layers of our control neural architecture that we have previously presented in [START_REF] Rojas Castro | Document image analysis by a mobile robot for autonomous indoor navigation[END_REF] and [START_REF] Rojas Castro | A Robust Neural Robot Navigation Using a Combination of Deliberative and Reactive Control Architectures[END_REF]. The overall architecture is based on a combination of a top-down and bottom-up approach. It allows the robot to emulate human behavior in navigating inside an unknown building by "reading" a map or a floor plan with its camera and "remembering" a sequence of signs to follow on the way.

In this article, by injecting the place recognition model into our previous architecture, we make the robot capable of coping with any unforeseen changes such as the occlusion of the expected signs. It allows the robot to find new references points by itself and learn them to get to its final destination.

II. RELATED WORK

The visual place recognition problem is usually tackled by retrieving images of the scene, training them and comparing them to other images thereafter. The undertaken process for place recognition can be considered as a more generalized version of the pattern recognition process and can be distinguished in two types of recognition depending on the application: topological place recognition and place categorization. In the context of robot navigation, a topological place recognition consists in endowing the robot with the capability of recognizing previously observed places in known environments. Appearance-based SLAM techniques such as the FAB-MAP [START_REF] Cummins | FAB-MAP: Probabilistic Localization and Mapping in the Space of Appearance[END_REF], [START_REF] Ho | Detecting loop closure with scene sequences[END_REF], [START_REF] Eade | Unified loop closing and recovery for real time monocular slam[END_REF] convert the images from a set of local features into a bag-of-words representation in order to match the appearance of the current scene to train the data. Place categorization instead, allows the robot to give a semantic labeling to the places by classifying different locations of a new environment into categories [START_REF] Ramos | A Bayesian approach for place recognition[END_REF], [START_REF] Wu | Visual place categorization: Problem, dataset, and algorithm[END_REF], [START_REF] Nguyen | A spatio-temporal Long-term Memory approach for visual place recognition in mobile robotic navigation[END_REF].

Biological approaches propose place recognition models which emulate similar behaviors seen in living organisms based on allothetic information when performing goalorientated navigation tasks [START_REF] Redish | Cognitive maps beyond the hippocampus[END_REF], [START_REF] Filliat | Global Localization and Topological Map Learning for Robot Navigation[END_REF]. Indeed, many studies on insects like bees, ants and wasps have shown that they could store multiples views of a place with different positions in order to learn the place. Then, by comparing and matching the stored images to the newly perceived one, they are able to recognize the place and return to their nests [START_REF] Gallistel | The Organization of Learning[END_REF], [START_REF] Judd | Multiple stored views and landmark guidance in ants[END_REF]. Similarly, neurobiological studies in mammals like primates and rats have revealed that they also use surrounding visual cues in order to achieve a particular place in a comparable way to insects. However, mammals show higher generalization capabilities and more complex processing when performing recognition of a scene or a place. Experiments conducted by 0'Keefe & Dostrovsky [START_REF] O'keefe | The hippocampus as a spatial map. Preliminary evidence from unit activity in the freely-moving rat[END_REF] led to the discovery of pyramidal neurons in the rat hippocampus that fire at their maximal activity when the animal is at a particular location in the environment and decreases as it goes away from it. They are called "place cells" and the regions at which they fire at are called place fields, which are almost similar to the receptive fields of sensory neurons. Based on this insight, Gaussier [START_REF] Gaussier | The visual homing problem: An example of robotics/biology cross fertilization[END_REF] and Giovannangeli [START_REF] Giovannangeli | Autonomous vision-based navigation: goal-orientated planning by transient states prediction, cognitive map building, and sensorymotor learning[END_REF], proposed a model of the hippocampal systems where "place cells" are learned as a result of the recognition of a particular configuration merging which our model is based on.

The robustness of such model lies in the use of the spatial information of the set of local features composing the place in addition to the description of the place itself as seen in some of the SLAM techniques.

III. OVERVIEW OF THE HYBRID NEURAL CONTROL

ARCHITECTURE

Before entering into the core of the Place-cells recognition system, an overview of the overall architecture is first given. The complete architecture integrates a floor plan analysis into an organized neural structure. It is composed of three modules (as illustrated in Fig. 1): a deliberative module and two reactive modules. The deliberative module corresponds to the processing chain in charge of extracting a sign sequence from the floor plan by computing a navigation path. On one hand, the analysis of the floor plan in real time, represented by the box in the top half of Fig. 1, undertakes a thorough process permitting the robot to extract the relevant information for its integration into the system. It consists of (1) an information segmentation process, which identifies and separates different types of information; (2) followed by a structural analysis where the information is extracted (walls and navigation signs separately); (3) and finally a semantic analysis allowing the extraction of the sign sequence based on the computation of the path and the information of the signs.

On the other hand, the neural structure of the two reactive modules represented by the two boxes in the lower half of Fig. 1 follows a perception-action mechanism that constantly evolves because of the dynamic interaction between the robot and its environment. Whereas the first reactive module integrates the sequence information coming from the deliberative module and constantly uses it in order to control its online navigation [START_REF] Rojas Castro | A Robust Neural Robot Navigation Using a Combination of Deliberative and Reactive Control Architectures[END_REF]; the second module learns places as new reference points when the expected signs are not visibly available. These modules are further composed of two levels of data streams corresponding to perception and action flows. The first level uses a reflex mechanism that controls directly the robot's action based on Figure 1. Functional overview and implementation of the neural architecture the information extracted from the perceived input. The second level uses a cognitive mechanism performing recognition of the perceptive flow.

Since the whole system works in parallel, a competitive mechanism allows to decide on the best behavior for controlling the robot according to the stimulus received. Hence, the neural interconnection is done by either excitatory or inhibitory connections allowing or preventing the activation of neurons respectively.

IV. PLACE CELLS LEARNING AND RECOGNITION LAYER

A. Natural Landmarks detection and extraction

A robust visual place recognition algorithm needs to combine descriptive, discriminative and generalization properties. Therefore, in order to capture all these properties this paper presents a model for place recognition, which learns and recognizes places. Each place is represented by place cells resulting from the recognition of a particular configuration merging two flows of information: what and where [START_REF] Ungerleider | What'and 'where'in the human brain[END_REF]. While, the former is in charge of identifying and recognizing the patterns (landmarks in this work) perceived in the visual scene of the place, the latter is involved in the analysis of the spatial location of the same. In order to achieve this, it is necessary to, on one hand, describe the perceived landmarks in a distinctive way and on the other hand, find their respective location within the scene (section A details the extraction of such information).

Figure 2 illustrates the complete neural layer allowing to learn different places (9 places tested in this work as shown in the right part of the figure) of a given environment. Each place is characterized by a set of landmarks surrounding the robot within its panoramic view (360°) and the information extracted from all landmarks is used as the input of the network system: On one side, the information related to the description of each landmark is gathered in the landmark histogram neural group, which is connected, to the what group. On the other side, the information related to the position of each landmark, given by its X-coordinate within the image with respect to a global reference point, is immediately fed into the where group to be processed. Then, the information coming from both groups converges on a two-dimensional array of neurons, which keeps in memory the resulting value of all the landmarks perceived in the panorama. As a result, a landmark constellation is formed in the landmark merging matrix group leading to learn a new place by recruiting a new neuron in the place cell group.

B. Natural Landmarks detection and extraction

In this work, the natural landmarks are considered as patterns that can be described by their distinguishable features (key-points). Hence, in order to detect these patterns all images acquired by the sensor camera are first pre-processed and transformed into gray color space. Then, for each image, the salient features along with their descriptors are computed. Since the viewpoint of a pattern can drastically change from one position to another, the SIFT descriptor is used. As a result, each feature is described as unique and differ from one another according to the composition of their visual characteristics.

This process is performed for two different sets of images: A set of template images to build the vocabulary and a set of query images to build, detect and recognize the landmarks during the robot run-time navigation.

1) Vocabulary construction The set of template images used here depicts the navigation environment from different viewpoints.

For each template image, all interest features (key-points) are detected and their descriptors are computed with the SIFT descriptor and stored in a vector. Then the k-means algorithm is used in order to group all the descriptors into k different clusters according to their similarity. This whole process is only performed once; therefore, it was computed before the robot navigation. At the end, the clusters centers centroids are stored and used as inputs in the following stage.

2

) Landmark construction

In order to build the landmarks, the extracted features from the query images are first compared and assigned to the clusters of the vocabulary according to the descriptors similarity. Then, the same descriptors are grouped into k different clusters according to their spatial distance (see Fig. 3a). This is done by using the Euclidean distance and the x and y coordinates of each key-point. The k number of clusters corresponds to the total number of landmarks in each image composing the panoramic view.

As a result, each spatial cluster is considered as a "natural landmark", which comprises of a certain number of key-points close to each other and belonging, each of them, to different clusters of the vocabulary.

3 Since the number of key-points belonging to each "natural landmark" varies from one another, it is not possible to compare them by the same standards. Therefore, each landmark is represented by a histogram composed of as many bins as there are clusters (size n) in the vocabulary. Then, for each landmark, each bin counts the total number of key-points that are associated with the cluster corresponding to that bin. As a result, all landmarks have the same number of parameters to be compared to, regardless the number of keypoints comprising them (see Fig. 3b). Henceforth, each landmark is characterized by three elements:

) Landmark representation

• A Landmark histogram based on a n-sized vector • An x-coordinate, corresponding to the relative position of the landmark-cluster center with respect to the horizontal axis of the image ; • A y-coordinate, corresponding to the relative position of the landmark-cluster center with respect to the vertical axis of the image.

C. Landmark histogram group

This group comprises of as many neurons as there are feature classes in the system, which corresponds to the vocabulary clusters. Thus, each neuron corresponds to one type of feature class and their activity value is computed by calculating the number of key-points comprised within the landmark belonging to each class. In other words, the neurons are considered as bins, where each key-point belonging to a landmark is thrown into its corresponding neuron class. Thus, a form of histogram is created for each landmark where each neuron of the landmark histogram group adds up the number of key-points that belong to it as shown in figure 4. If for instance, there is no key-point belonging to a given class inside the landmark, the final value of its corresponding neuron class is zero.

Once the activities of all neurons have been computed, the resulting vector is injected into the what group to be either learned or recognized. Afterwards, the activity values of the neurons are reset to zero so that the same process can be repeated with the other landmarks of the same panorama view.

D. What group

This group is composed of a sufficient number of neurons to encode the total amount of landmarks that can be found in a given exploration environment. Two different procedures have been implemented, one for learning and the other for recognizing. The first one consists in recruiting and learning one neuron for every landmark perceived in the panoramic view of the first place. The recruited neuron is then associated with the landmark by performing a one-shot learning. The synaptic connection weights are modified according to the following rule.

∆ = *

(1)

Where, the current activity neuron a j equals to 1 when the what neuron is recruited and 0 otherwise; and a i is the activity of the landmark input neuron. The second procedure consists in comparing the landmarks of a new place to those already learned to find out if the new landmarks can be recognized. To this end, all the neurons activities are computed accordingly to the following equation:

= 1 - ∑ - =0 (2)
Where, a j gets the maximum value when the Euclidean distance between the synaptic weights Wij and the input value a j are nil.

The resulting values determine how similar the current landmark is to the previously learned. Then, by verifying if its activity value is bigger than a "vigilance" term, it is possible to conclude that the landmark has been recognized. Otherwise, it has to be learned as a new one by following [START_REF] Gaussier | From view cells and place cells to cognitive map learning: processing stages of the hippocampal system[END_REF].

E. Where group

The where group, is composed of a limited amount of neurons encoding a preferred direction covering in all the total 360 degrees of the panoramic view in order to compute the position of each landmark. As the angular position of each landmark is given by its distance in pixels with respect to the reference point (azimuth), the preferred directions are also given in pixels. For every landmark position, the where group is expressed as a non-normalized Gaussian activity profile:

= - ( -) 2 2 2
(3) Where, α represents the azimuth of the j th landmark and μ j the preferred direction of the neuron j. Each preferred direction is computed as:

= 2 + * , (1,2,3 … )
(4) Where, dist is the distance in pixels between each preferred direction and dist= Xtotal / dim. With, Xtotal the total number of pixels in the panorama view and dim the number of neurons in the where group.

The same computation is performed for each neuron in the group with the same α. Since their preferred direction is different, only the neuron with the closest value to α results with the maximum activity value, and consequently gets to Additionally, by means of a lateral diffusion, its neighbor neurons are set to a value that decays in function of their distance among them in order to allow a better tolerance in the robustness.

L 1 L 2 L 3 K 4 ] K 1 K5 K 2 K 3 L 1 Landmark vector 0.3 0.1 0 ] L 1 K 1 K 2 K3 K4 Landmarks histogram

F. Spatio-temporal merging matrix and place cells learning

In order to learn a place, the robot needs to keep in mind the information of all the surrounding landmarks perceived from its point of view. However, as the analysis of the place, which is given by the analysis of the landmarks within the panoramic view, can only be done in a sequential mode (the system cannot recognized several landmarks in parallel), it is necessary to keep in memory the overall information.

Thus, in order to suppress the sequential aspect of the scene exploration, a matrix of neurons stores the information of all landmarks perceived in the panoramic view. In fact, the information coming from both what and where groups of each landmark converges into the matrix allowing a spatio-temporal integration. The activity of the detected landmark in the what group and the activity of its position in the where group, enable the activity of the corresponding neuron in the matrix merging group. As a result, after having processed all the landmarks from a place, a landmark constellation is formed allowing to learn a new location by encoding a neuron in the Place cell group (see Fig. 2).

V. EXPERIMENTAL RESULTS

A. Procedure

In order to validate the proposed approach, the place cell learning and recognition layer was implemented in the humanoid robot NAO and tested in a 2.5m x 2.5m room space.

To this end, a simple scenario was created such that a certain number of positions scattered all over the test environment was chosen to code different places within it in order to allow the robot to depict its environment by learning and recognizing each place at which it is located.

Figure 5 (top part) depicts the test environment composed of nine different places representing nine different positions covering in all the entire navigation test environment.

Each place is characterized by the set of patterns (landmarks) and their corresponding positions perceived by the robot within a panoramic view (360°). The position of the landmarks is calculated with respect to a north (here an artificial landmark was used as the global reference point as illustrated in the top part of figure 5).The panoramic view is obtained by taking snapshots of the environment with the camera's robot while rotating around itself. In overall, twelve overlapping images were enough to complete one panoramic view and thus build a robust representation of a place. As illustrated, each image is composed of ten landmarks, but as each image overlaps with the previous and next images, a filter is used in order to consider only the landmarks that are within the 60 % of the center of the image.

B. Test and Results

Three different tests were carried out in order to prove the feasibility and robustness of the learning and recognition approach:

TEST #1: To begin with, a single place in the environment was chosen to be learned and tested. The idea was to prove if after being learned it could easily be recognized not only when the robot was positioned at the same place but also when the robot was positioned at any place within the environment test.

RESULT #1: When the robot was at the exact same place where it had previously been, the corresponding place cell was activated with the higher possible value: 1, whereas as the robot went away from the place, the recognition value decreased proportionally to the distance (see Fig. 6.1).

TEST #2: In this test, all the nine places depicted in fig. 5 were first learned. Then, the robot was placed at only one of them and the activity of all places was computed.

RESULT #2: Figure 6.2 shows the activity of all places when the robot was positioned on the 6 th place. As expected, the activity of the corresponding place cell got the maximum value. Since the other places were previously learned, the corresponding place cells were activated, although with a minimum activation value.

TEST #3: This test consisted in verifying if the robot could learn different places as it navigates the environment in an incremental way.

RESULT #3: Whenever, a place was not recognized the robot would automatically learn it as a new one. Indeed, when the place's activity was below a given threshold, a vigilance term mechanism was activated indicating that the perceived place had not been recognized and needed to be learned. Figure 6.3 illustrates the activity probability of the place cells as the robot gets far from the learned "place 6 in orange". Then, since the value is little compared to the threshold value, it learns the place as a new one: "place 3 in blue".

In all tests, when the robot was placed at the exact same location of any of the learned places, the recognition rate was of 100 %. While the results of the first and second tests allowed us to validate the recognition of one or several places after having been learned, those of the third test allowed us to validate the incremental learning as the robot navigated the environment. This is an essential property for an autonomous navigation allowing the robot to adapt itself to the environment.

However, even though the recognition of the learned places was ensured at a 100% when the robot happened to be positioned at the exact learned places, different results showed that the recognition of the place dropped drastically when the robot's position was slightly modified with respect to the tested one. Since, the recognition of the landmarks was accurate; we suppose that the limitation comes from the determination of the threshold value and possibly the management of the lateral diffusion explained previously. This problem opens new perspectives for the improvement of the proposed algorithm.

VI. CONCLUSIONS

A biologically inspired approach for recognizing places within an environment has been presented in this paper as a robust solution for an autonomous robot navigation. The presented paper shows the robustness of the approach when navigating in complex environments where unforeseen situations are prone to happen such as the occlusion or absence of an expected sign serving as reference in the navigation task. Experimental results show the efficacy of the implemented algorithm. The robot is able to detect by itself what it considers to be relevant from the environment as natural landmarks and learns them as such. The ambiguity given by clusters with similar descriptors is dealt by the additional cluster position information which together are used to learn new places and recognize them during robot navigation. The learning task is performed in an incremental way allowing the robot to adapt itself to the environment.

Thanks to the generic composition of our previous neural architecture, the proposed model can be injected into it to further develop it with respect to robustness and completeness. The high activation of place 6 indicates that the robot is positioned at that place and it recognized it as such. 3) Place "6" is learned and recognized, then as the robot navigates the environment, the activity value is inferior to the threshold value and the robot learns place "3" as a new one.

Figure 2 .

 2 Figure 2. Place cells learning and recognition layer. A place cell is formed by the combination of two neural groups (what and where) carrying the information from the extracted landmarks.

Figure 3 .

 3 Figure 3. a) Natural Landmarks composed of key-points belonging to different classes according to their descriptors similarity. b) Landmark histogram of size 100.

WhereFigure 4 .

 4 Figure 4. Computation of the what and where groups

Figure 5 .

 5 Figure 5. Top part: Test environment composed of nine different places. An artificial landmark is used as a global reference to compute the position of the landmarks. Bottom part: Three overlapping images extracted by the robot's camera. Only the landmarks in the center are considered.

Figure 6 . 1 )

 61 Figure 6. 1) Place "6" learned and recognized. 2) All nine places are learned.The high activation of place 6 indicates that the robot is positioned at that place and it recognized it as such. 3) Place "6" is learned and recognized, then as the robot navigates the environment, the activity value is inferior to the threshold value and the robot learns place "3" as a new one.

I

Research work supported by European regional development Funds(Contract35053) and the Poitou Charente Region