Rémy Portelas

Cédric Colas

Katja Hofmann

Pierre-Yves Oudeyer

Teacher algorithms for curriculum learning of Deep RL in continuously parameterized environments

Keywords: Deep Reinforcement Learning, Teacher-Student Learning, Curriculum Learning, Learning Progress, Curiosity, Parameterized Procedural Environments

We consider the problem of how a teacher algorithm can enable an unknown Deep Reinforcement Learning (DRL) student to become good at a skill over a wide range of diverse environments. To do so, we study how a teacher algorithm can learn to generate a learning curriculum, whereby it sequentially samples parameters controlling a stochastic procedural generation of environments. Because it does not initially know the capacities of its student, a key challenge for the teacher is to discover which environments are easy, difficult or unlearnable, and in what order to propose them to maximize the efficiency of learning over the learnable ones. To achieve this, this problem is transformed into a surrogate continuous bandit problem where the teacher samples environments in order to maximize absolute learning progress of its student. We present a new algorithm modeling absolute learning progress with Gaussian mixture models (ALP-GMM). We also adapt existing algorithms and provide a complete study in the context of DRL. Using parameterized variants of the BipedalWalker environment, we study their efficiency to personalize a learning curriculum for different learners (embodiments), their robustness to the ratio of learnable/unlearnable environments, and their scalability to non-linear and high-dimensional parameter spaces. Videos and code are available at https://github.com/flowersteam/teachDeepRL.

Introduction

We address the strategic student problem. This problem is well known in the developmental robotics community [START_REF] Lopes | The Strategic Student Approach for Life-Long Exploration and Learning[END_REF], and formalizes a setting where an agent has to sequentially select tasks to train on to maximize its average competence over the whole set of tasks after a given number of interactions. To address this problem, several works [START_REF] Oudeyer | Intrinsic motivation systems for autonomous mental development[END_REF][START_REF] Baranes | Active learning of inverse models with intrinsically motivated goal exploration in robots[END_REF][START_REF] Moulin-Frier | Self-organization of early vocal development in infants and machines: The role of intrinsic motivation[END_REF] proposed to use automated Curriculum Learning (CL) strategies based on Learning Progress (LP) [START_REF] Blank | Bringing up robot: Fundamental mechanisms for creating a self-motivated, self-organizing architecture[END_REF], and showed that population-based algorithms can benefit from such techniques. Inspired by these initial results, similar approaches [START_REF] Colas | CURIOUS: intrinsically motivated modular multi-goal reinforcement learning[END_REF] were then successfully applied to DRL agents in continuous control scenarios with discrete sets of goals, here defined as tasks varying only by their reward functions (e.g reaching various target positions in a maze). Promising results were also observed when learning to navigate in discrete sets of environments, defined as tasks differing by their state space (e.g escaping from a set of mazes) [START_REF] Matiisen | Teacher-student curriculum learning[END_REF][START_REF] Mysore | Reward-guided curriculum for robust reinforcement learning[END_REF].

In this paper, we study for the first time whether LP-based curriculum learning methods are able to scaffold generalist DRL agents in continuously parameterized environments. We compare the reuse of Robust Intelligent Adaptive Curiosity (RIAC) [START_REF] Baranes | R-IAC: robust intrinsically motivated exploration and active learning[END_REF] in this new context to Absolute Learning Progress -Gaussian Mixture Model (ALP-GMM), a new GMM-based approach inspired by earlier work on developmental robotics [START_REF] Moulin-Frier | Self-organization of early vocal development in infants and machines: The role of intrinsic motivation[END_REF] that is well suited for DRL agents. Both these methods rely on Absolute Learning Progress (ALP) as a surrogate objective to optimize with the aim to maximize average competence over a given parameter space. Importantly, our approaches do not assume a direct mapping from parameters to environments, meaning that a given parameter vector encodes a distribution of environments with similar properties, which is closer to real-world scenarios where stochasticity is an issue.

Recent work [START_REF] Wang | Paired open-ended trailblazer (POET): endlessly generating increasingly complex and diverse learning environments and their solutions[END_REF] already showed impressive results in continuously parameterized environments. The POET approach proved itself to be capable of generating and mastering a large set of diverse 3rd Conference on Robot Learning (CoRL 2019), Osaka, Japan.

arXiv:1910.07224v1 [cs.LG] 16 Oct 2019

BipedalWalker environments. However, their work differs from ours as they evolve a population of agents where each individual agent is specialized for a single specific deterministic environment, whereas we seek to scaffold the learning of a single generalist agent in a training regime where it never sees the same exact environment twice.

As our approaches make few assumptions, they can deal with ill-defined parameter spaces that include unfeasible subspaces and irrelevant parameter dimensions. This makes them particularly well suited to complex continuous parameter spaces in which expert-knowledge is difficult to acquire. We formulate the Continuous Teacher-Student (CTS) framework to cover this scope of challenges, opening the range of potential applications.

Main contributions:

• A Continuous Teacher-Student setup enabling to frame Teacher-Student interactions for ill-defined continuous parameter spaces encoding distributions of tasks. See Sec. 3.

• Design of two parameterized BipedalWalker environments, well-suited to benchmark CL approaches on continuous parameter spaces encoding distributions of environments with procedural generation. See Sec. 4.3.

• ALP-GMM, a CL approach based on Gaussian Model Mixture and absolute LP that is well suited for DRL agents learning continuously parameterized tasks. See Sec. 4.1.

• First study of ALP-based teacher algorithms leveraged to scaffold the learning of generalist DRL agents in continuously parameterized environments. See Sec. 5.

Related work

Curriculum learning, as formulated in the supervised machine learning community, initially refers to techniques aimed at organizing labeled data to optimize the training of neural networks [START_REF] Elman | Learning and development in neural networks: the importance of starting small[END_REF][START_REF] Krueger | Flexible shaping: How learning in small steps helps[END_REF][START_REF] Bengio | Curriculum learning[END_REF].

Concurrently, the RL community has been experimenting with transfer learning methods, providing ways to improve an agent on a target task by pre-training on an easier source task [START_REF] Taylor | Transfer learning for reinforcement learning domains: A survey[END_REF]. These two lines of work were combined and gave birth to curriculum learning for RL, that is, methods organizing the order in which tasks are presented to a learning agent so as to maximize its performance on one or several target tasks.

Learning progress has often been used as an intrinsically motivated objective to automate curriculum learning in developmental robotics [START_REF] Blank | Bringing up robot: Fundamental mechanisms for creating a self-motivated, self-organizing architecture[END_REF], leading to successful applications in population-based robotic control in simulated [START_REF] Moulin-Frier | Self-organization of early vocal development in infants and machines: The role of intrinsic motivation[END_REF][START_REF] Forestier | Modular active curiosity-driven discovery of tool use[END_REF] and real-world environments [START_REF] Oudeyer | Intrinsic motivation systems for autonomous mental development[END_REF][START_REF] Baranes | Active learning of inverse models with intrinsically motivated goal exploration in robots[END_REF]. LP was also used to accelerate the training of LSTMs and neural turing machines [START_REF] Graves | Automated curriculum learning for neural networks[END_REF], and to personalize sequences of exercises for children in educational technologies [START_REF] Clément | Multi-Armed Bandits for Intelligent Tutoring Systems[END_REF].

A similar Teacher-Student framework was proposed in [START_REF] Matiisen | Teacher-student curriculum learning[END_REF], which compared teacher approaches on a set of navigation tasks in Minecraft [START_REF] Johnson | The malmo platform for artificial intelligence experimentation[END_REF]. While their work focuses on discrete sets of environments, we tackle the broader challenge of dealing with continuous parameter spaces that map to distributions over environments, and in which large parts of the parameter space may be unlearnable.

Another form of CL has already been studied for continuous sets of tasks [START_REF] Florensa | Automatic goal generation for reinforcement learning agents[END_REF], however they considered goals (varying by their reward function), where we tackle the more complex setting of learning to behave in a continuous set of environments (varying by their state space). The GOAL-GAN algorithm also requires to set a reward range of "intermediate difficulty" to be able to label each goal in order to train the GAN, which is highly dependent on both the learner's skills and the considered continuous set of goals. Besides, as the notion of intermediate difficulty provides no guarantee of progress, this approach is susceptible to focusing on unlearnable goals for which the learner's competence stagnates in the intermediate difficulty range.

space. In the remainder of this paper, we will refer to parameter sampling and task distribution sampling interchangeably, as one parameter directly maps to a task distribution.

Student In CTS, learning agents, called students, are confronted with episodic Partially Observable Markov Decision Processes (POMDP) tasks τ . For each interaction step in τ , a student collects an observation o P O τ , performs an action a P A τ , and receives a corresponding reward r P R τ . Upon task termination, an episodic reward r e " ř T t"0 r ptq is computed, with T the length of the episode.

Teacher The teacher interacts with its student by selecting a new parameter p P P, mapped to a task distribution T ppq P T , proposing m tasks τ " T ppq to its student and observing r p , the average of the m episodic rewards r e . The new parameter-reward tuple is then added to an history database of interactions H that the teacher leverages to influence the parameter selection in order to maximize the student's final competence return c p " f pr p q across the parameter space. Formally, the objective is

max ż P,t"K w p ¨cK p dp, (1)
with K the predefined maximal number of teacher-student interactions and w p , a factor weighting the relative importance of each task distribution in the optimization process, enabling to specify whether to focus on specific subregions of the parameter space (i.e. harder target tasks). As students are considered as black-box learners, the teacher solely relies on its database history H for parameter sampling and does not have access to information about its student's internal state, algorithm, or perceptual and motor capacities.

Parameter space assumptions The teacher does not know the evolution of difficulty across the parameter space and therefore assumes a non-linear, piece-wise smooth function. The parameter space may also be ill-defined. For example, there might be subregions U Ă P of the parameter space in which competence improvements on any parameter u P U is not possible given the state transition functions F τ of tasks sampled in any T puq P T (i.e tasks are either trivial or unfeasible). Additionally, given a parameter space P P R d , there might exist an equivalent parameter space P 1 P R k with k ă d, constructed with a subset of the d dimensions of P, meaning that there might be irrelevant or redundant dimensions in P.

In the following sections, we will restrict our study to CTS setups in which teachers sample only one task per selected parameter vector (i.e m " 1 and r p = r e ) and do not prioritize the learning of specific subspaces (i.e w p " 1, @p P P ).

Methods

In this section, we will describe our absolute LP-based teacher algorithms, our reference teachers, and present the continuously parameterized BipedalWalker environments used to evaluate them.

Absolute Learning-Progress-Based Teacher Algorithms

Of central importance to this paper is the concept of learning progress, formulated as a theoretical hypothesis to account for intrinsically motivated learning in humans [START_REF] Kaplan | In search of the neural circuits of intrinsic motivation[END_REF], and applied for efficient robot learning [START_REF] Blank | Bringing up robot: Fundamental mechanisms for creating a self-motivated, self-organizing architecture[END_REF][START_REF] Oudeyer | Intrinsic motivation systems for autonomous mental development[END_REF]. Inspired by some of this work [START_REF] Baranes | Active learning of inverse models with intrinsically motivated goal exploration in robots[END_REF][START_REF] Forestier | Intrinsically motivated goal exploration processes with automatic curriculum learning[END_REF], we frame our two teacher approaches as a Multi-Armed Bandit setup in which arms are dynamically mapped to subspaces of the parameter space, and whose values are defined by an absolute average LP utility function. The objective is then to select subspaces on which to sample a distribution of tasks in order to maximize ALP. ALP gives a richer signal than (positive) LP as it enables the teacher to detect when a student is losing competence on a previously mastered parameter subspace (thus preventing catastrophic forgetting).

Robust Intelligent Adaptive Curiosity (RIAC) RIAC [START_REF] Baranes | R-IAC: robust intrinsically motivated exploration and active learning[END_REF] is a task sampling approach whose core idea is to split a given parameter space in hyperboxes (called regions) according to their absolute LP, defined as the difference of cumulative episodic reward between the newest and oldest tasks sampled in the region. Tasks are then sampled within regions selected proportionally to their ALP score. This approach can easily be translated to the problem of sampling distributions of tasks, as is the case in this work. To avoid a known tendency of RIAC to oversplit the space [START_REF] Florensa | Automatic goal generation for reinforcement learning agents[END_REF], we added a few minor modifications to the original architecture to constrain the splitting process. Details can be found in appendix B.

Absolute Learning Progress Gaussian Mixture Model (ALP-GMM) Another more principled way of sampling tasks according to LP measures is to rely on the well known Gaussian Mixture Model [START_REF] Rasmussen | The infinite gaussian mixture model[END_REF] and Expectation-Maximization [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF] algorithms. This concept has already been successfully applied in the cognitive science field as a way to model intrinsic motivation in early vocal developments of infants [START_REF] Moulin-Frier | Self-organization of early vocal development in infants and machines: The role of intrinsic motivation[END_REF]. In addition of testing for the first time their approach (referred to as Covar-GMM) on DRL students, we propose a variant based on an ALP measure capturing long-term progress variations that is well-suited for RL setups. See appendix B for a description of their method.

The key concept of ALP-GMM is to fit a GMM on a dataset of previously sampled parameters concatenated to their respective ALP measure. Then, the Gaussian from which to sample a new parameter is chosen using an EXP4 bandit scheme [START_REF] Auer | The nonstochastic multiarmed bandit problem[END_REF] where each Gaussian is viewed as an arm, and ALP is its utility. This enables the teacher to bias the parameter sampling towards high-ALP subspaces.

To get this per-parameter ALP value, we take inspiration from earlier work on developmental robotics [START_REF] Forestier | Intrinsically motivated goal exploration processes with automatic curriculum learning[END_REF]: for each newly sampled parameter p new and associated episodic reward r new , the closest (Euclidean distance) previously sampled parameter p old (with associated episodic reward r old ) is retrieved using a nearest neighbor algorithm (implemented with a KD-Tree [START_REF] Bentley | Multidimensional binary search trees used for associative searching[END_REF]). We then have

alp new " |r new ´rold | (2)
The GMM is fit periodically on a window W containing only the most recent parameter-ALP pairs (here the last 250) to bound its time complexity and make it more sensitive to recent high-ALP subspaces. The number of Gaussians is adapted online by fitting multiple GMMs (here having from 2 to k max " 10 Gaussians) and keeping the best one based on Akaike's Information Criterion [START_REF] Bozdogan | Model selection and akaike's information criterion (aic): The general theory and its analytical extensions[END_REF].

Note that the nearest neighbor computation of per-parameter ALP uses a database that contains all previously sampled parameters and associated episodic rewards, which prevents any forgetting of long-term progress. In addition to its main task sampling strategy, ALP-GMM also samples random parameters to enable exploration (here p rnd " 20%). See Algorithm 1 for pseudo-code and appendix B for a schematic view of ALP-GMM.

Algorithm 1 Absolute Learning Progress Gaussian Mixture Model (ALP-GMM)

Require: Student S, parametric procedural environment generator E, bounded parameter space P, probability of random sampling p rnd , fitting rate N , max number of Gaussians k max 1: Initialize parameter-ALP First-in-First-Out window W, set max size to N 2: Initialize parameter-reward history database H 3: loop N times Ź Bootstrap phase 4:

Sample random p P P, send Epτ " T ppqq to S, observe episodic reward r p

5:

Compute ALP of p based on r p and H (see equation 2)

6:

Store pp, r p q pair in H, store pp, ALP p q pair in W 7: loop Ź Stop after K inner loops 8:

Fit a set of GMM having 2 to k max kernels on W 9:

Select the GMM with best Akaike Information Criterion Else, sample p from a Gaussian chosen proportionally to its mean ALP value 13:

Send Epτ " T ppqq to student S and observe episodic reward r p 14:

Compute ALP of p based on r p and H

15:

Store pp, r p q pair in H, store pp, ALP p q pair in W 16: Return S

Teacher References

Random Task Curriculum (Random) In Random, parameters are sampled randomly in the parameter space for each new episode. Although simplistic, similar approaches in previous work [START_REF] Baranes | Active learning of inverse models with intrinsically motivated goal exploration in robots[END_REF] proved to be competitive against more elaborate forms of CL.

Oracle A hand-constructed approach, sampling random task distributions in a fixed-size sliding window on the parameter space. This window is initially set to the easiest area of the parameter space and is then slowly moved towards complex ones, with difficulty increments only happening if a minimum average performance is reached. Expert knowledge is used to find the dimensions of the window, the amplitude and direction of increments, and the average performance threshold. Pseudo-code is available in Appendix B.

Parameterized BipedalWalker Environments with Procedural Generation

The BipedalWalker environment [START_REF] Brockman | Openai gym[END_REF] offers a convenient test-bed for continuous control, allowing to easily build parametric variations of the original version [START_REF] Ha | Reinforcement learning for improving agent design[END_REF][START_REF] Wang | Paired open-ended trailblazer (POET): endlessly generating increasingly complex and diverse learning environments and their solutions[END_REF]. The learning agent, embodied in a bipedal walker, receives positive rewards for moving forward and penalties for torque usage and angular head movements. Agents are allowed 2000 steps to reach the other side of the map. Episodes are aborted with a ´100 reward penalty if the walker's head touches an obstacle.

To study the ability of our teachers to guide DRL students, we design two continuously parameterized BipedalWalker environments enabling the procedural generation of walking tracks:

• Stump Tracks A 2D parametric environment producing tracks paved with stumps varying by their height and spacing. Given a parameter vector rµ h , ∆ s s, a track is constructed by generating stumps spaced by ∆ s and whose heights are defined by independent samples in a normal distribution N pµ h , 0.1q.

• Hexagon Tracks A more challenging 12D parametric BipedalWalker environment. Given 10 offset values µ o , each track is constructed by generating hexagons having their default vertices' positions perturbed by strictly positive independent samples in N pµ o , 0.1q. The remaining 2 parameters are distractors defining the color of each hexagon. This environment is challenging as there are no subspaces generating trivial tracks with 0-height obstacles (as offsets to the default hexagon shape are positive). This parameter space also has non-linear difficulty gradients as each vertices have different impacts on difficulty when modified.

All of the experiments done in these environments were performed using OpenAI's implementation of Soft-Actor Critic [START_REF] Haarnoja | Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor[END_REF] as the single student algorithm. To test our teachers' robustness to students with varying abilities, we use 3 different walker morphologies (see Figure 1). Additional details on these two environments along with track examples are available in Appendix E.

Experimental Results

Performance metric To assess the performance of all of our approaches on our BipedalWalker environments, we define a binary competence return measure stating whether a given track distribution is mastered or not, depending on the student's episodic reward r p . We set the reward threshold to 230, which was used in [START_REF] Wang | Paired open-ended trailblazer (POET): endlessly generating increasingly complex and diverse learning environments and their solutions[END_REF] to ensure "reasonably efficient" walking gates for default bipedal walkers trained on environments similar to ours. Note that this reward threshold is only used for evaluation purposes and in the Oracle condition. Performance is then evaluated periodically by sampling a single track in each track distribution of a fixed evaluation set of 50 distributions sampled uniformly in the parameter space. We then simply measure the percentage of mastered tracks. During evaluation, learning in DRL agents is turned off.

Through our experiments we answer three questions about ALP-GMM, Covar-GMM and RIAC:

• Are ALP-GMM, Covar-GMM and RIAC able to optimize their students' performance better than random approaches and teachers exploiting environment knowledge?

• How does their performance scale when the proportion of unfeasible tasks increases?

• Are they able to scale to high-dimensional sampling spaces with irrelevant dimensions?

5.1 How do ALP-GMM, Covar-GMM and RIAC compare to reference teachers?

Emergence of curriculum Figure 2 provides a visualization of the sampling trajectory observed in a representative ALP-GMM run for a default walker. Each plot shows the location of each Gaussian of the current mixture along with the 250 track distributions subsequently sampled. At first (a), the walker does not manage to make any significant progress. After 1500 episodes (b) the student starts making progress on the leftmost part of the parameter space, especially for track distributions with a spacing higher than 1.5, which leads ALP-GMM to focus its sampling in that direction. After 15k episodes (c) ALP-GMM has shifted its sampling strategy to more complex regions. The analysis of a typical RIAC run is detailed in Appendix C (fig. 8). Performance comparison Figure 3 shows learning curves for each condition paired with short, default and quadrupedal walkers. First of all, for short agents (a), one can see that Oracle is the best performing algorithm, mastering more than 20% of the test set after 20 Million steps. This is an expected result as Oracle knows where to sample simple track distributions, which is crucial when most of the parameter space is unfeasible, as is the case with short agents. ALP-GMM is the LP-based teacher with highest final mean performance, reaching 14.9% against 10.6% for Covar-GMM and 8.6% for RIAC. This performance advantage for ALP-GMM is statistically significant when compared to RIAC (Welch's t-test at 20M steps: p ă 0.04), however there is no statistically significant difference with Covar-GMM (p " 0.16). All LP-based teachers are significantly superior to Random (p ă 0.001).

Regarding default bipedal walkers (b), our hand-made curriculum (Oracle) performs better than other approaches for the first 10 Million steps and then rapidly decreases to end up with a performance comparable to RIAC and Covar-GMM. All LP-based conditions end up with a final mean performance statistically superior to Random (p ă 10 ´4). ALP-GMM is the highest performing algorithm, significantly superior to Oracle (p ă 0.04), RIAC (p ă 0.01) and Covar-GMM (p ă 0.01).

For quadrupedal walkers (c), Random, ALP-GMM, Covar-GMM and RIAC agents quickly learn to master nearly 100% of the test set, without significant differences apart from Covar-GMM being superior to RIAC (p ă 0.01). This indicates that, for this agent type, the parameter space of Stump

Tracks is simple enough that trying random tracks for each new episode is a sufficient curriculum learning strategy. Oracle teachers perform significantly worse than any other method (p ă 10 ´5). The mean performance (32 seeded runs) is plotted with shaded areas representing the standard error of the mean.

Through this analysis we answered our first experimental question by showing how ALP-GMM, Covar-GMM and RIAC, without strong assumptions on the environment, managed to scaffold the learning of multiple students better than Random. Interestingly, ALP-GMM outperformed Oracle with default agents, and RIAC, Covar-GMM and ALP-GMM surpassed Oracle with the quadrupedal agent, despite its advantageous use of domain knowledge. This indicates that training only on track distributions sampled from a sliding window that end up on the most difficult parameter subspace leads to forgetting of simpler task distributions. Our approaches avoid this issue through efficient tracking of their students' learning progress.

How does our approaches scale when the amount of unfeasible tasks increases?

A crucial requirement when designing all-purpose teacher algorithms is to ensure their ability to deal with parameter spaces that are ill-defined w.r.t to the considered student. To study this property we performed additional experiments on Stump Tracks where we gradually increased the stump height dimension range, which increases the amount of unfeasible tracks.

Results are summarized in Table 1. To assess whether a condition is robust to increasing unfeasibility, one can look at the p-value of the Welch's t-test performed on the final performance measure between the condition run on the original parameter space and the same condition run on a wider space. High p-value indicates that there is not enough evidence to reject the null hypothesis of no difference, which can be interpreted as being robust to parameter spaces containing more unfeasible tasks. Using this metric, it is clear that ALP-GMM is the most robust condition among the presented LP-based teachers, with a p-value of 0.71 when increasing the stump height range from r0, 3s to r0, 4s compared to p " 0.02 for RIAC and p " 0.05 for Covar-GMM. When going from r0, 3s to r0, 5s, ALP-GMM is the only LP-based teacher able to maintain most of its performance (p " 0.12). Although Random also seems to show robustness to increasingly unfeasible parameter spaces (p " 0.78 when going from r0, 3s to r0, 4s and p " 0.05 from r0, 3s to r0, 5s), it is most likely due to its stagnation in low performances. Compared to all other approaches, ALP-GMM remains the highest performing condition in both parameter space variations (p ă 0.02). These additional experiments on Stump Tracks showed that our LP-based teachers are able to partially maintain the performance of their students in parameter spaces with higher proportions of unfeasible tasks, with a significant advantage for ALP-GMM.

Cond. \

Are our approaches able to scale to ill-defined high-dimensional task spaces?

To assess whether ALP-GMM, Covar-GMM and RIAC are able to scale to parameter spaces of higher dimensionality containing irrelevant dimensions, and whose difficulty gradients are non-linear, we performed experiments with quadrupedal walkers on Hexagon Tracks, our 12-dimensional parametric BipedalWalker environment. Results are shown in Experiments on the Hexagon Tracks showed that ALP-GMM is the most suitable condition for complex high-dimensional environments containing irrelevant dimensions, non-linear parameter spaces and large proportions of initially unfeasible tasks.

Complementary experiments To better grasp the general properties of our teacher algorithms, additional abstract experiments without DRL students were also performed for parameter spaces with increasing number of dimensions (relevant and irrelevant) and increasing ratio of initially unfeasible subspaces, showing that GMM-based approaches performed best (see Appendix A).

Discussion and Conclusion

This work demonstrated that LP-based teacher algorithms could successfully guide DRL agents to learn in difficult continuously parameterized environments with irrelevant dimensions and large proportions of unfeasible tasks. With no prior knowledge of its student's abilities and only loose boundaries on the task space, ALP-GMM, our proposed teacher, consistently outperformed random heuristics and occasionally even expert-designed curricula. ALP-GMM, which is conceptually simple and has very few crucial hyperparameters, opens-up exciting perspectives inside and outside DRL for curriculum learning problems. Within DRL, it could be applied to previous work on autonomous goal exploration through incremental building of goal spaces [START_REF] Laversanne-Finot | Curiosity driven exploration of learned disentangled goal spaces[END_REF]. In this case several ALP-GMM instances could scaffold the learning agent in each of its autonomously discovered goal spaces. Another domain of applicability is assisted education, for which current state of the art relies heavily on expert knowledge [START_REF] Clément | Multi-Armed Bandits for Intelligent Tutoring Systems[END_REF] and is mostly applied to discrete task sets.

A Experiments on an n-dimensional toy parameter space

The n-dimensional toy space An n-dimensional toy parameter space P P r0, 1s n was implemented to simulate a student learning process, enabling the study of our teachers in a controlled deterministic environment without DRL agents. A parameter p directly maps to an episodic reward r p depending on the history of previously sampled parameters. The parameter space is divided in hypercubes and enforces the following rules:

• Sampling a parameter in an "unlocked" hypercube results in a positive reward ranging from 1 to 100 depending on the amount of already sampled parameters in the hypercube: if 10 parameters were sampled in it, the next one will yield a reward of 11. Sampling a parameter located in a "locked" hypercube does not yield any reward. • At first, all hypercubes are "locked" except for one, located in a corner.

• Sampling 75 parameters in an unlocked hypercube unlocks its neighboring hypercubes.

Results on n-dimensional toy spaces Results are displayed in Figure 5. We use the median percentage of unlocked hypercubes as a performance metric. A first experiment was performed on a 2D toy space with 10 hypercubes per dimensions. In this experiment one can see that all LP-based approaches outperform Random by a significant margin. Covar-GMM is the highest performing algorithm. This first toy-space will be used as a point of reference for our following analysis, for which all conditions were tested on a panel of toy spaces with varying number of meaningful dimensions (first row of Figure 5), irrelevant dimensions (second row) and number of hypercubes (third row).

By looking at the first row of Figure 5, one can see that increasing the dimension size seems to have a greater negative impact on RIAC than on GMM-based approaches: RIAC, which was between ALP-GMM and Covar-GMM in terms of median performance in our reference experiment is now clearly under-performing them on all 3 toy spaces. In the 3D and 4D cases RIAC is even outperformed by the Random condition after 70k episodes and 290k episodes, respectively. For the 6D toy space RIAC consistently outperforms Random, reaching a median final performance of 80% after 1M episodes. In this 6D toy space ALP-GMM and Covar-GMM both reach 100% of median performance after 1M episodes. Covar-GMM is the highest performing condition in each toy-space, closely followed by ALP-GMM.

The second row of Figure 5 shows how performances of our approaches vary when adding irrelevant dimensions to the 2D toy-space. To better grasp the properties of these additional dimensions, one can see that Random is not affected by them. With 10,20 and 50 additional useless dimensions, RIAC is consistently inferior to GMM-based conditions in terms of median performance. RIAC median performance is only above Random during the first 55k episodes. ALP-GMM is the highest performing algorithm throughout training for toy spaces with 20 and 50 irrelevant dimensions, closely followed by Covar-GMM. In the toy space with 10 irrelevant dimensions, ALP-GMM outperforms Covar-GMM in the first 40k episodes but end up reaching a 100% median performance after 52k episodes against only 44k episodes for Covar-GMM.

The last row shows how performance changes according to the number of hypercubes. Given our toy space rules, increasing the number of hypercubes reduces the initial area where reward is obtainable in the parameter space, and therefore allows us to study the sensitivity of our approaches to detect learnable subspaces. Random struggles in all 3 toy-spaces compared to other conditions and to its performances on the reference experiment with 10 hypercubes per dimensions. Covar-GMM and RIAC are the best performing conditions for toy-spaces with 20 hypercubes per dimensions. However, when increasing to 50 and 100 hypercubes per dimensions, Covar-GMM remains the best performing condition but RIAC is now under-performing compared to ALP-GMM.

Overall these experiments showed that GMM-based approaches scaled better than RIAC on parameter spaces with large number of relevant or irrelevant dimensions, and large number of (initially) unfeasible parameter spaces. Among these GMM-based approaches, contrary to experiments with DRL students on BipedalWalker environments, Covar-GMM proved to be better than ALP-GMM for these toy spaces.

B Implementation details

Soft-Actor Critic All of our experiments were performed with OpenAI's implementation1 of SAC as our DRL student. We used the same 2-layered (400, 300) network architecture with ReLU for the Q, V and policy networks. The policy network's output uses tanh activations. The entropy coefficient and learning progress were respectively set to 0.005 and 0.001. Gradient steps are performed every 10 environment steps by selecting 1000 samples from a replay buffer with a fixed sized of 2 millions.

RIAC To avoid a known tendency of RIAC to oversplit the parameter space [START_REF] Florensa | Automatic goal generation for reinforcement learning agents[END_REF], we added a few modifications to the original architecture. The essence of our modified RIAC could be summarized as follows (hyperparameters settings are given in parenthesis):

1. When collecting a new parameter-reward pair, it is added to its respective region. If this region reaches its maximal capacity max s (" 200), a split attempt is performed.

2. When trying to split a parent region p into two children regions, n (" 50) candidate splits on random dimensions and thresholds are generated. Splits resulting in one of the child regions, c 1 or c 2 , having less than min s (" 20) individuals are rejected. Likewise, to avoid having extremely small regions, a minimum size min d is enforced for each region's dimensions (set to 1{6 of the initial range of each dimensions of the parameter space). The split with the highest score, defined as cardpc 1 q ¨cardpc 2 q ¨|alppc 1 q ´alppc 2 q|, is kept. If no valid split was found, the region flushes its oldest points (the oldest quarter of pairs sampled in the region are removed).

3. At sampling time, several strategies are combined:

• 20%: a random parameter is chosen in the entire space.

• 70%: a region is selected proportionally to its ALP and a random parameter is sampled within the region. • 10%: a region is selected proportionally to its ALP and the worst parameter with lowest associated episodic reward is slightly mutated (by adding a Gaussian noise N pp, 0.1q).

We send the reader back to the original papers of RIAC [START_REF] Baranes | R-IAC: robust intrinsically motivated exploration and active learning[END_REF][START_REF] Baranes | Active learning of inverse models with intrinsically motivated goal exploration in robots[END_REF] for detailed motivations and pseudo-code descriptions.

Covar-GMM Originating from the developmental robotic field [START_REF] Moulin-Frier | Self-organization of early vocal development in infants and machines: The role of intrinsic motivation[END_REF], this approach inspired the design of ALP-GMM. In Covar-GMM, instead of fitting a GMM on the parameter space concatenated with ALP as in ALP-GMM, they concatenate each parameters with its associated episodic return and time (relative to the current window of considered parameters). New parameters are then chosen by sampling on a Gaussian selected proportionally to its positive covariance between time and episodic reward, which emulates positive LP. Contrary to ALP-GMM, they ignore negative learning progress and do not have a way to detect long term LP (i.e LP is only measured for the currently fitted datapoints). Although not initially present in Covar-GMM, we compute the number of Gaussians online as in ALP-GMM to compare the two approaches solely on their LP measure. Likewise, Covar-GMM is given the same hyperparameters as ALP-GMM (see section 4).

Oracle Oracle has been manually crafted based on knowledge acquired over multiple runs of the algorithm. It uses a step size σ W " 1 30 R, with R a vector containing the maximal distance for each dimension of the parameter space. Before each new episode, the window (W size " 1 6 R) is slid toward more complex task distributions by σ W only if the average episodic reward of the last 50 proposed tasks is above r thr " 230. See Algorithm 2 for pseudo-code.

Figure 7 provides a visualization of the evolution of Oracle's parameter sampling for a typical run in Stump Tracks. One can see that the final position of the parameter sampling window (corresponding to a subspace that cannot be mastered by the student) is reached after 10500 episodes (c) and remains the same up to the end of the run, totaling 15000 episodes. This end-of-training focus on a specific part of the parameter space is the cause of the forgetting issues of Oracle (see section 5.1). Additional investigations on the data revealed that, by sliding its sampling window towards track distributions with higher stump heights and lower stump spacing, Oracle's runs mostly failed to master track distributions that were both hard and distant from its sampling window within the parameter space: that is, tracks with both high stump heights (ą 2.5) and high spacing (ą 3.0). ALP-GMM is the most robust LP-based teacher and maintains a statistically significant performance advantage over all other conditions in all 3 settings. Random performances are most impacted when increasing the number of unfeasible tracks. ALP-GMM is more robust than RIAC when going from a maximal stump height of 3 to 4 and 3 to 5. Note that for all 3 experiments, for comparison purposes, the same test set was used and contained only track distributions with a maximal stump height of 3.

E Parameterized BipedalWalker Environments

In BipedalWalker environments, observations vectors provided to walkers are composed of 10 lidar sensors (providing distance measures), the hull angle and velocities (linear and angular), the angle and speed of each hip and knee joints along with a binary vector which informs whether each leg is touching the ground or not. This sums up to 24-dimensions for our two bipedal walkers and 34 for the quadrupedal version. To account for its increased weight and additional legs, we increased the maximal torque usage and reduced the torque penalty for quadrupedal agents.

Parameter bounds of Stump Tracks In Stump Tracks, the range of the mean stump height µ h is set to r0, 3s, while the spacing ∆ s range lies in r0, 6s. Examples of randomly generated tracks are left for consultation in Figure 12.

Parameter bounds of Hexagon Tracks In Hexagon Tracks, the range of the 12 dimensions of the space are set to r0, 4s. Figure 13 provides a visual explanation of how hexagons are generated. Figure 14 shows examples of randomly generated tracks.

Figure 1 :

 1 Figure 1: Multiple students and environments to benchmark teachers. (a): In addition to the default bipedal walker morphology (middle agent), we designed a bipedal walker with 50% shorter legs (left) and a bigger quadrupedal walker (right). (b): The quadrupedal walker is also used in Hexagon Tracks.

Figure 2 :

 2 Figure 2: Example of an ALP-GMM teacher paired with a Soft Actor-Critic student on Stump Tracks.Figures (a)-(c) show the evolution of ALP-GMM parameter sampling in a representative run. Each dot represents a sampled track distribution and is colored according to its Absolute Learning Progress value. After initial progress on the leftmost part of the space, as in (b), most ALP-GMM runs end up improving on track distributions with 1 to 1.8 stump height, with the highest ones usually paired with spacing above 2.5 or below 1, indicating that tracks with large or very low spacing are easier than those in r1, 2.5s. Figure (d) shows for the same run which track distributions of the test set are mastered (i.e rt ą 230, shown by green dots) after 17k episodes.

Figure 3 :

 3 Figure 3: Evolution of mastered track distributions for Teacher-Student approaches in Stump Tracks.

Figure 4 .

 4 In the first 20 Millions steps, one can see that Oracle has a large performance advantage compared to LP-based teachers, which is mainly due to its knowledge of initial progress niches. However, by the end of training, ALP-GMM significantly outperforms Oracle (p ă 0.02), reaching an average final performance of 80% against 68% for Oracle. Compared to Covar-GMM and RIAC, the final performance of ALP-GMM is also significantly superior (p ă 0.01 and p ă 0.005, respectively) while being more robust and having less variance (see appendix D). All LP-based approaches are significantly better than Random (p ă 0.01).

Figure 4 :

 4 Figure 4: Teacher-Student approaches in Hexagon Tracks. Left: Evolution of mastered tracks for Teacher-Student approaches in Hexagon Tracks. 32 seeded runs (25 for Random) of 80 Millions steps where performed for each condition. The mean performance is plotted with shaded areas representing the standard error of the mean. Right: A visualization of which track distributions of the test-set are mastered (i.e rt ą 230, shown by green dots) by an ALP-GMM run after 80 million steps.

Figure 6 :loop 3 : 4 :Figure 9 :

 6349 Figure 6: Schematic view of an ALP-GMM teacher's workflow

  max stump height of 5

Figure 10 :

 10 Figure10: Evolution of mean performance of Teacher-Student approaches when increasing the amount of unfeasible tracks in Stump Tracks with default bipedal walkers. 32 seeded runs where performed for each condition. The mean performance is plotted with shaded areas representing the standard error of the mean. ALP-GMM is the most robust LP-based teacher and maintains a statistically significant performance advantage over all other conditions in all 3 settings. Random performances are most impacted when increasing the number of unfeasible tracks. ALP-GMM is more robust than RIAC when going from a maximal stump height of 3 to 4 and 3 to 5. Note that for all 3 experiments, for comparison purposes, the same test set was used and contained only track distributions with a maximal stump height of 3.

Figure 12 :

 12 Figure 12: Example of tracks generated in Stump Tracks.

Figure 13 :

 13 Figure 13: Generation of obstacles in Hexagon Tracks. Given a default hexagonal obstacle, the first 10 values of a 12-D parameter are used as positive offsets to the x and y positions of all vertices (except for the y position of the first and last ones, in order to ensure the obstacle has at least one edge in contact with the ground.

Figure 14 :

 14 Figure 14: Example of tracks generated in Hexagon Tracks with additional examples of encounterable obstacles.

Table 1 :

 1 Impact

	Stump height	r0, 3s	r0, 4s	r0, 5s
	ALP-GMM	39.6 ˘9.6 38.6 ˘11.6 (p " 0.71) 34.3 ˘15.8 (p " 0.12)
	Covar-GMM	33.3 ˘7.1 27.6 ˘14.0 (p " 0.05) 24.1 ˘14.7 (p " 0.01)
	RIAC	32.1 ˘12.2 23.2 ˘17.2(p " 0.02) 20.5 ˘15.4 (p " 0.002)
	Random	18.2 ˘11.5 17.4 ˘11.8 (p " 0.78) 12.6 ˘11.0 (p " 0.05)

of increasing the proportion of unfeasible tasks. The average performance with standard deviation (after 20 Million steps) on the original Stump Tracks' test-set is reported (32 seeds per condition).The additional p-values inform whether conditions run in the original Stump Tracks (r0, 3s) are significantly better than when run on variations with higher maximal stump height.

The Continuous Teacher-Student Framework (CTS)In this section, we formalize our Continuous Teacher-Student framework. It is inspired from earlier work in developmental robotics[START_REF] Baranes | R-IAC: robust intrinsically motivated exploration and active learning[END_REF][START_REF] Lopes | The Strategic Student Approach for Life-Long Exploration and Learning[END_REF] and intelligent tutoring systems[START_REF] Clément | Multi-Armed Bandits for Intelligent Tutoring Systems[END_REF]. The CTS framework is also close to earlier work on Teacher-Student approaches for discrete sets of tasks[START_REF] Matiisen | Teacher-student curriculum learning[END_REF]. In CTS however, teachers sample parameters mapping to distributions of tasks from a continuous parameter

https://github.com/openai/spinningup

Acknowledgments

This work was supported by Microsoft Research through its PhD Scholarship Programme. Experiments were carried out using the PlaFRIM experimental testbed, supported by Inria, CNRS (LABRI and IMB), Université de Bordeaux, Bordeaux INP and Conseil Régional d'Aquitaine (see https://www.plafrim.fr/) and the Curta platform (see https://redmine.mcia.fr/).

D Additional visualization for Hexagon Tracks experiments

To better understand the properties of all of the tested conditions in Hexagon Tracks, we analyzed the distributions of the percentage of mastered environments of the test set after training for 80 Millions (environment) steps. Using Figure 11, one can see that ALP-GMM both has the highest median performance and narrowest distribution. Out of the 32 repeats, only Oracle and ALP-GMM always end-up with positive final performance scores whereas Covar-GMM, RIAC and Random end-up with 0% performance in 8{32, 5{32 and 16{25 runs, respectively. Interestingly, in all repeats of any condition, the student manages to master part of the test set at some point (i.e non-zero performance), meaning that runs that end-up with 0% final test performance actually experienced catastrophic forgetting. This showcase the ability of ALP-GMM to avoid this forgetting issue through efficient tracking of its student's absolute learning progress.

Oracle ALP-GMM Covar-GMM RIAC Random 0 Gold lines are medians, surrounded by a box showing the first and third quartile, which are then followed by whiskers extending to the last datapoint or 1.5 times the inter-quartile range. Beyond the whiskers are outlier datapoints.


Heekwon No

Jérémy Vezinet

ENAC Carl Milner

Simplified GNSS Fusion-based Train Positioning System and its Diagnosis

His research interests are the multi-sensor fusion based navigation, guidance and control system of

INTRODUCTION

Stakeholders in European railways are interested in the introduction of a GNSS-based positioning system for trains. GNSS is successfully implemented in the aeronautical domain. However, its introduction to rail faces an entirely different challenge. Firstly, its stringent safety requirement, set to a hazard rate of 10-9 per hour subjected to Safety Integrity Level (SIL) 4 [START_REF] Rispoli | GNSS for ERTMS train localization: A step-change technology and new business model[END_REF] and secondly the railway user is exposed to greater interference and severe multipath in the local environment. The use of GNSS in the railway sector has been postulated on the notion of a virtual balise (VB). Existing railway positioning systems are based on various trackside infrastructures including physical balises (PBs) installed in groups between the tracks and odometry installed on-board. However, due to the high cost of installing and maintaining the PB, a GNSS-based VB positioning performed within on-board system has been proposed to reduce the role of PBs. The VB-based positioning system works by setting a VB point on the railway track and determining the passage of the VB point using the position solution from the GNSS receiver, replacing the existing PB. However, the train user on the ground suffers from the local effect generated by the ground environment such as terrain, buildings and tunnels. The needs for a diagnostic function of the GNSS-based positioning system arises from the possibility of failures of GNSS due to the effect of the local environment. The diagnosis can be performed by using redundant measurements fro m other sensors.

Fusing multiple sensors provides redundant information that is useful to improve positioning accuracy and to suppress the local effects. However, additional sensors make the assessment of integrity more challenging due to the complexity of the system and various error sources which cannot be easily modeled with high confidence. Installation of additional sensors also requires more cost. Therefore, a simple and minimal approach which fits the demand and requirements of the railway is desirable. In this paper, two simple GNSS-based positioning methods are proposed and their diagnostic functions for GNSS failure are tested. Firstly, the odometer-based method, which are proposed in our previous research, is concretized to be implemented for general cases. Secondly, single-axis accelerometer-based approach is newly proposed. The latter method is expected to give greater sensitivity to detect GNSS failures while maintaining a relatively simple positioning architecture. Both methods are tested in simulation, and their abilities for detecting fault in GNSS signal are investigated and compared. This paper is organized as follows. Firstly, PB-based and VB-based positioning system of train are mentioned briefly. Then two fault detection method, odometer-based method and single-axis accelerometer-based method are introduced. After that, these two methods are compared by Monte Carlo simulation, and conclusion will be followed.

POSITIONING SYSTEM OF TRAIN

Figure 1 Current PB-based positioning system of train (left) and GNSS-based VB positioning system (right)

Current train positioning system is based on PB which is installed on track side. On the train, balise detector and odometer is equipped. When the train passes over the point where the PB is installed, the balise detector receives a telegram message which contains the identification number of detected balise. From this message the train determines its current position. The train propagates its position by using measurements from the odometer when it located between balises (Figure 1). On the other hand, the concept of GNSSbased VB is proposed to reduce the role of PBs because of its cost for installation and maintenance. VB points are set on the track instead of installation of PB. When position solution of GNSS receiver, which is installed on the train, passes a VB point, the onboard VB system generates a telegram message which is similar to that of PB-based system. In this way, the VB-based positioning system can substitute PB-based system with maintaining compatibility to previous system. The train is moving on the ground. Not only a fault of GNSS satellite but also ground objects can affect to the received ranging signal of train user and can generate positioning failure of VB system. The positioning failure of train user should be monitored and warned in order to meet the safety requirement of train system.

ODOMETER-BAS ED METHOD

In our previous research, the odometer-based method was proposed and tested under simplified assumptions. This method detects fault in position solution of GNSS by using odometer and track information which are embedded on the train. The concept of this method will be briefly introduced, and the details of this method can be found in [START_REF] No | Diagnostics of GNSS-based Virtual Balise in Railway Using Embedded Odometry and Track Geometry[END_REF]. Raw monitors for along-track direction, (1), cross track direction, (2), and vertical direction, (3) are defined as follows:

( ) ( ) ( ) gnss odo x q k x k x k ∆ = ∆ -∆ (1)
( ) ( ) ( )

gnss map y q k y k y k ∆ = ∆ -∆ (2) ( ) ( ) ( ) gnss map z q k z k z k ∆ = ∆ -∆ (3)
where

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
x k x k x k x k x k x k y k y k y k z k z k z k y k y k y k z k z k z k ∆ = - - ∆ = - - ∆ = - - ∆ = - - ∆ = - - ∆ = - - gnss gnss gnss
, and x y z represent GNSS position solution for along-track direction, cross track direction and vertical direction, odo x represents traveling distance measurement from odometer, map map and y z represent cross track and vertical position from track information. These raw monitors have limited detectability for faults with slow mean rate because of its high noise level. Moving average is introduced to reduce the noise level of raw monitors as follows:

( ) ( ) 1 1 for along-track monitor N x x N m q k q k m N N ∆ ∆ = = + - ∑ (4)
where N represents window size of moving average. Bigger window size makes better sensitivity for slow rated fault, but it also induces later detection for fast rated fault than smaller window. Therefore, bank of monitors is constituted with raw monitor and moving averaged monitors with different window sizes for all three direction in order to achieve both of fast detection for fast rated fault and sensitivity for slow rated fault. In our previous research [START_REF] No | Diagnostics of GNSS-based Virtual Balise in Railway Using Embedded Odometry and Track Geometry[END_REF], exponentially weighted moving average (EWMA) was implemented. However, addressing threshold for EWMA monitor requires heavy computation due to time-correlated nature of GNSS range measurements. So, moving average is implemented instead of EWMA for light computation and similar performance.

We have four monitors for each of three directions, total 12 monitors. All monitors are monitored simultaneously, and if at least one monitor reaches its threshold value the detection of fault is declared. Entire architecture of odometer-based method is shown in Figure 2. In our previous research, several assumptions, such as fixed constellation of GNSS, and fixed heading of train, are made for easier feasibility analysis. In this paper, non-fixed constellation of GNSS, and arbitrary heading of train are considered in the calculation of threshold values for more realistic test environments. Note that the odometer-based method is just for detection of fault, not for improving position accuracy of train.

SINGLE-AXIS ACCELEROMETER METHOD IN TRAVELING DISTANCE DOMAIN

If we think about the moving characteristics of trains, its movement is constrained on the track. Therefore, the position of a train can be parameterized by one-dimensional traveling distance on the track (Figure 3) without considering all three-dimensional position. This is expected to simplify positioning and integrity analysis of train.

Figure 3 Parameterization of train position on traveling distance domain

If we set a known reference position ref ( ) P on track, such as a position where a PB is installed, the traveling distance ( ) s from reference position can represent current position ( ) P of train. The traveling distance can be propagated by measurement of sensors, such as odometer, and its error can be estimated and corrected by measurement of GNSS. For the propagation of traveling distance, a single-axis accelerometer installed along the direction of track is considered. The accelerometer is a self-contained sensor, and it has robustness for environmental condition compared to the odometer. The accuracy of radar odometer is sensitive to the reflective surface. Its accuracy can be degraded by rain or snow on track. The tachometer type odometer suffer from slipping or sliding when the train is accelerating or braking. Pure acceleration along forward direction is needed for the propagation of traveling distance. However, the accelerometer measures specific force which is sum of acceleration and gravity. The gravity in accelerometer measurement must be eliminated. In strapdown inertial navigation system, the gravity is eliminated by using estimated attitude information. Fortunately, inclination of track can be provided by the track geometry information. Due to the uncertainty of track geometry information the gravity cannot be eliminated completely. In that case, the odometer can be used together to suppress the effect of residual gravity. Dynamics of the system is simple as follows:

s s v =  ( 5
)
s s v a =  (6)
where and s s v a are speed and acceleration along track direction. And the accelerometer measurement model is given as

0 1 sin a s a a a f a g b b w θ = + + + + (7) 0 0 a b =  (8) 1 1 1 1 a a ba a b b w τ = - +  (9)
where a f is accelerometer measurement, g is gravitational acceleration, θ is inclination angle, 0 a b is constant accelerometer bias, 1 a b is time-varying accelerometer bias, and a w is accelerometer noise. The time-varying bias is modeled by 1 st order Gauss-Markov process with time constant, a τ and driving white noise, 1 ba w . Receiver clock bias and drift error model for tightly-coupled integration of GNSS are introduced as dB B w dt

φ = +  (
1 T s a a x s v b b B B δ δ δ δ δ δ δ   =    (12) 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1/ 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 a ba a f w g w x x w w φ δθ δ δ τ           - - -               = +     - -             -         -          ( 13
)
As measurements of Kalman filter, speed measurement of odometer and pseudorange measurement of GNSS are considered. The measurement equations for odometer and pseudorange are as follows:

[ ] ε is measurement noise of pseudorange after applying SBAS correction. In (15), along-track position error is regarded as error of traveling distance, and crosstrack and vertical position error from track geometry are absorbed to i v ρ as components of measurement noise. For detection of fault, innovation-based monitor is defined as follows [START_REF] Tanil | An INS Monitor to Detect GNSS Spoofers Capable of Tracking Vehicle Position[END_REF]:

odo odo ˆ0 1 0 0 0 0 s s v v v x w δ δ = - = - (14) ( ) T , , 1 ˆ0 0 0 1 0 b i i i b i b i b b i i x e y B z e x v ρ ρ δ δρ ρ ρ δ δ ε δ δ     = -= + -         = +   (15) where , , , , 1 2 3 ,
1 1 k T k i i i i q S γ γ - = = ∑ (
k k k k k k T k k k k k k k k k k k k k i z H x N S S H P H V z H x v v N V q m i m k γ γ χ - - = = - = + = +       ∑
The innovation-based monitor assumes independence of measurements over time. However, error in pseudorange measurement is generally time-correlated, and it can affect to false alarm and missed detection probability. As a temporary solution for this, the update rate of pseudorange measurement is reduced to 0.1 Hz, and standard deviation of measurement noise is exaggerated by 3times. This issue needs to be resolved carefully in future work.

ERROR MODELS

Error models for GNSS range measurements are identical to those of our previous research [START_REF] No | Diagnostics of GNSS-based Virtual Balise in Railway Using Embedded Odometry and Track Geometry[END_REF]. Modeling of GNSS errors follows previous work [START_REF] Salos Andrés | Integrity monitoring applied to the reception of GNSS signals in urban environments[END_REF] and standard assumptions [START_REF] Rtca | Minimum Operational Performance Standards for Global Positioning System/Satellite-Based Augmentation System Airborne Equipment (SBAS MOPS)[END_REF]. A Gauss Markov 1 st order model is assumed for each error source including ionospheric error, tropospheric error, satellite orbit and clock error and the user error consisting of nominal multipath and noise [START_REF] Pervan | Test statistic auto-and cross-correlation effects on monitor false alert and missed detection probabilities[END_REF].

The ionospheric error and the satellite orbit and clock errors are assumed to be remaining errors after application of SBAS correction. Details of GNSS error model are shown in Table 1. Embedded track geometry data is assumed to give the cross-track and vertical coordinate of the train position with 1 m noise considering surveying error, track deformation error, and interpolation error along the surveyed points. It is assumed that the inclination of track can be provided perfectly by track geometry information. This assumption seems too optimistic for now. However, given the smoothness of rail tracks, we think precise knowledge of inclination should be feasible. False alarm probability is set to 10 -7 as a temporary value for the simulation. This value can be changed according to the requirements of rail system.

SIMULATION SETUP

To test fault detection capability of two proposed method, Monte Carlo simulation was performed. Repetition number of the simulation was 10 4 . In the simulation, full GPS (24 satellites) and Galileo (24 satellites) constellation were considered (Figure 4). Fault in range measurement of GNSS was assumed to be a ramp type range fault in single satellite. The tested range of ramp rate was from 0.01 m/s to 5.0 m/s. The fault was injected to GPS satellite #8 (pink color thick line in Figure 4) during the simulation.

Figure 4 Skyplot of simulation, GPS (left) Galileo (right)

The duration of single run of simulation was 40000 seconds (11.1 hours). The user was assumed to move on a horizontal rectangularshaped trajectory with rounded corners (Figure 5). Its distance for one lap was 160 km and the user ran 5 laps with 20 m/s of speed in a single run of simulation. Initial position of user was set on Toulouse, France (latitude 43.6154 deg, longitude 1.3656 deg, height 524 m). In the simulation, the range error was inserted from 15000 seconds. Time of Position failure was defined as the momen t when along-track position error reaches 20 meters.

Figure 5 User trajectory of simulation

SIMULATION RESULTS

We will start to check single run results for normal and faulty condition, and then we will move to Monte Carlo simulation results for various rates of ramp fault. The odometer-based method shows earlier mean detection time results than 1-D KF. Note that odometer-based method has earlier mean detection time, but it has bigger standard deviation for its detection time because it tried to detect faults using total 12 monitors, and some of its monitors, especially raw monitors, have high noise level. On the other hand, 1-D KF detects faults using one innovation-based monitor, and the monitor itself is calculated by accumulation. These feature makes narrow distribution of its detection time.

Figure 9 Time of detection results of Monte Carlo simulation

In Figure 10, probability of missed detection ( md P ) results according to time-to-alert (TTA) are shown. TTA is defined as the time of position failure subtracted by the time of detection. Negative TTA value means the fault is detected before the position failure. In the odometer-based method, the train used GNSS position solution for its position, and TTA for odometer-based method calculated by using the time of position failure of GNSS. The results show that md P value reaches zero on negative TTA value for both methods for all rates of ramp error. This means that the both methods succeeded to detect all faults before the position failure.

Figure 10 Probability of missed detection results of Monte Carlo simulation

Figure 11 shows mean and maximu m TTA results for various rates of range error. The odometer-based method shows better (smaller) mean TTA results. However, in aspect of maximu m TTA, both methods show similar results even if 1-D KF has simpler architecture for fault detection. These results were induced by narrow distribution of detection time of 1-D KF because the single-axis accelerometer method used single accumulated innovation-based monitor to detect faults. We can see potential of improved performance of single-axis accelerometer method by sophisticating its architecture by using multiple monitors with different accumulation time. This will be investigated in future work.

CONCLUSION

Skateholders in European railways are interested in the introduction of GNSS-based positioning system for trains. However, they are facing difficulties of the vulnerability of GNSS user on the ground and the high safety requirement of train. As a part of research for detecting failures of GNSS-based positioning system for train user, two fault detection methods are proposed and compared. The odometer-based method can detect ramp type range fault up to 0.01m/s mean rate using embedded odometer and track geometry information. Newly proposed single-axis accelerometer-based method handled the problem in one-dimensional traveling distance domain. It implemented the innovation-based monitor to detect fault for simpler architecture. This method has similar detection sensitivity for slow rated ramp type range fault with the odometer-based method. It shows bigger mean TTA results, but in aspect of maximu m TTA, it shows similar performance because of narrow distribution of TTA. It also expected to have robust performance for environmental effects, such as weather condition or acceleration of train, because the accelerometer is not affected by those effects, but the odometer is. In the results, there is uncertainty for assumed accuracy for provided track geometry information. It will be investigated in the future work.

Figure 2

 2 Figure 2 Architecture of odometer-based method

  vector represented in b-frame, and i ρ

  number of measurement at k-epoch

Figure 6

 6 shows single-run results of along-track position error of normal condition. 1-D KF represents the results of single-axis accelerometer-based method. The 1-D KF shows better root-mean-square (RMS) error of 0.56 m than 0.96 m of GNSS position. It is obvious that integration of accelerometer and odometer with GNSS reduces RMS position error.

Figure 6

 6 Figure 6 Along track position error results of normal conditionIn single-run results of faulty condition, ramp range error of 0.1 m/s rate is inserted. In case of faulty condition, the 1-D KF still shows better RMS error of 115.04 m than 169.35 m of GNSS, but it cannot prevent the occurrence of position failure (Figure7). It just delays the position failure about 250 seconds from 17721 seconds to 17971 seconds.

Figure 7

 7 Figure 7 Along track position error results of faulty condition (left) and zoom (right) In the Monte Carlo simulation, ramp range errors from 0.01 m/s to 5.0 m/s rate are tested. In the results of time of position failure, 1-D KF shows delayed time of position failure for all rates of range error compared to GNSS as shown in single-run results (Figure 8).

Figure 8

 8 Figure 8 Time of position failure results of Monte Carlo simulationIn Figure9, time of detection results for odometer-based method and single-axis accelerometer-based method are shown. Odo represents odometer-based method. The odometer-based method shows earlier mean detection time results than 1-D KF. Note that odometer-based method has earlier mean detection time, but it has bigger standard deviation for its detection time because it tried to detect faults using total 12 monitors, and some of its monitors, especially raw monitors, have high noise level. On the other hand, 1-D KF detects faults using one innovation-based monitor, and the monitor itself is calculated by accumulation. These feature makes narrow distribution of its detection time.

Figure 11

 11 Figure 11 Time-to-alert results of Monte Carlo simulation

  10)

					dB w dt = 	f		(11)
	where	B	and	B  represent receiver clock bias and drift error,	w φ	and f w	are driving white noise for and B	B  . Error equation in state
	space representation for implementation of Kalman filter is given by
						0

Table 1 GNSS

 1 Error model parametersFor odometer and accelerometer, a radar type odometer and an automotive grade single-axis accelerometer are assumed. Detailed specifications are provided in Table2.

	Error	𝑹𝑹 ( 𝟎𝟎 )	𝝉𝝉	𝑹𝑹 ( ∆= 𝟏𝟏𝟎𝟎𝟏𝟏 )	𝑹𝑹 ( ∆= 𝟏𝟏𝟏𝟏 )
	Source			𝑹𝑹 ( 𝟎𝟎 )	𝑹𝑹 ( 𝟎𝟎 )
	Units	[ 𝒎𝒎 𝟐𝟐 ]	[ 𝟏𝟏 ]
	Ionosphere	vary /w El [5]	360s	0.9726	0.9972
	Troposphere	vary /w El [5]	1800s	0.9945	0.9994
	Orbit/Clock	0.3	3600s	0.9987	0.9997
	User	1.5	100s	0.9048	0.9900

32nd International Technical Meeting of the Satellite Division of the Institute of Navigation (ION GNSS+ 2019), Miami, Florida, September 16-20, 2019

https://doi.org/10.33012/2019.16967

ACKNOWLEDGMENTS

This work has been funded by the ASTRail project. This project received funding from the Shift2Rail Joint Undertaking under the European Union's Horizon 2020 research and innovation programme under grant agreement No 777561.