{'fraction_non_alphanumeric': 0.0344735435595938, 'fraction_numerical': 0.009906848896693899, 'mean_word_length': 4.981845170130167, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Personalized Dynamics Models for Adaptive Assistive Navigation Systems

Consider an assistive system that guides visually impaired users through speech and haptic feedback to their destination. Existing robotic and ubiquitous navigation technologies (e.g., portable, ground, or wearable systems) often operate in a generic, user-agnostic manner. However, to minimize confusion and navigation errors, our real-world analysis reveals a crucial need to adapt the instructional guidance across different end-users with diverse mobility skills. To address this practical issue in scalable system design, we propose a novel model-based reinforcement learning framework for personalizing the system-user interaction experience. When incrementally adapting the system to new users, we propose to use a weighted experts model for addressing data-efficiency limitations in transfer learning with deep models. A real-world dataset of navigation by blind users is used to show that the proposed approach allows for (1) more accurate long-term human behavior prediction (up to 20 seconds into the future) through improved reasoning over personal mobility characteristics, interaction with surrounding obstacles, and the current navigation goal, and (2) quick adaptation at the onset of learning, when data is limited.


Introduction
Generalized assistive navigation systems for people with visual impairments have been extensively studied in the robotics community over the past decades [1,2,3,4,5,6,7,8,9]. However, many of these systems have not considered personalization, to take into account individual differences between users [10,11]. Differences between users can significantly impact the navigation experience and the ultimate success of the assistive navigation system. Based on our analysis of real-world user data, we observe high variability in the reaction time and response to instructional guidance provided by the navigation system. Towards a more personalized interaction experience, we envision an assistive navigational system that is able to automatically identify the user's specific information needs (e.g., environmental context, walking speed, reaction time, and cane strategies) and adapt the timing and content of its instructions accordingly in real-time.
Designing a system which can personalize its interaction across users is challenging. Consider an assistive system (e.g., a service robot, wearable, or smartphone system) that instructs a blind person along the planned path in Fig. 1. As the system observes the user approaching a turn, it must determine when to announce 'turn right.' In this scenario, a slight delay or premature signaling of a turn can result in a navigation error. For instance, the user could miss the turn or get confused by proceeding into the wrong hallway or encountering a wall. Hence, we can see that the ability of a navigational system to give appropriately timed instruction is critical, in particular when guiding a blind person in intricate indoor environments. However, appropriately selecting the time and content of instructional feedback requires knowledge of the user's dynamics, which are not known a priori (as we demonstrate) and must be inferred on the fly.
We propose to frame the interaction between the assistive navigational system and the blind user as a Markov Decision Process (MDP). We term our complete reinforcement learning (RL) framework PING (for Personalized INstruction Generation). Actions in this dynamical system are sampled  Figure 1: Blind user dynamics modeling for adaptive assistive navigation interfaces. Towards a more personalized interaction experience, our approach (PING) learns robust dynamics models of user behavior and plans for a sequence of instructions for arrival to a navigation goal. from a policy P (a|s) (the solution to the MDP), which maps the current spatial context and user state s (e.g., user position and orientation) to an instructional guidance action a (e.g., 'turn left' or 'proceed forward').
While adaptive human-robot interaction (HRI) systems have been previously proposed [12,13,14,15,16,17,18], quick adaptation to new users of a system is still an open problem. For instance, model-free RL algorithms do exist for learning optimal policies by sampling state-action transitions during interaction with the environment [19,20], yet those approaches can require much time and exploration (i.e., trial and error) to find the optimal policy. In the context of navigating a blind person through a new environment, we simply do not have the capacity for such costly exploration of the policy space. Instead, to minimize navigation errors in our application, we must develop a technique that can adapt as fast as possible to the user's behavior. As model-based approaches are known to benefit from sample efficiency [21,22], we emphasize approximating the state transition function P (s |s, a), which in our scenario is a model of how a specific user will react to the guidance.
Dataset for Predicting Real-World Navigation by Blind People. To understand practical issues in assistive navigation, we study a large dataset collected in real-world assisted navigation. The dataset is used to perform long-term user prediction, and includes unique challenges compared to common trajectory prediction datasets which observe humans passively (e.g., surveillance or social settings [24]), such as delayed reactions, veering, and highly non-linear trajectories during turns. We use the dataset to identify a practical aspect of the interaction which has been little explored beforethe extent of inter-user variability and need for real-time personalization in assistive navigation.
User-Specific Dynamics Model via an Efficient Weighted Experts Algorithm. Our main contribution is in a personalization scheme which allows for training high capacity and sample efficient dynamics models. We demonstrate that a weighted experts model is able to quickly adapt the state transition dynamics model to match the reactions of the user nearly an order of magnitude faster when compared to the common transfer learning (i.e., adaptation) baseline of single model finetuning. When evaluating long-term future prediction of user position with a 20 second horizon, the proposed model is able to improve prediction accuracy by nearly the width of a hallway on average compared to the baseline, especially at the crucial navigation junctions of turns or veering paths.
Assistive Navigation System with Adaptive Instruction Generation for Blind People. Towards a system which can adapt to a variety of blind walkers, we pair the proposed dynamics personalization scheme with a Model Predictive Control (MPC)-based planner, and evaluate it on a diverse set of simulated walkers. To the best of our knowledge, PING is the first application of ideas from modelbased RL and online learning to develop a continuously adapting assistive navigation system for people with visual impairments.

Related Research
Modeling Human Dynamics. The goal of our work is to adapt an assistive interface to the current user by learning a personalized dynamics model. By formulating assistive navigation in a modelbased framework, our work is related to data-efficient RL frameworks [30,43,31,44,21,22,45,32].
Model-based approaches often employ a non-parametric Gaussian Process [21] or Neural Network [29] dynamics model, as in our study. Modeling the dynamics of people is an important yet challenging problem, extensively studied in literature [12,13,46,14,15]. Much attention has been given to predicting human behavior under passive observation (e.g., surveillance or social settings [47,23,48,49,24,50,25,26,27,28,51,29]). While relevant, such studies do not generally model interaction with an instructional interface, nor do they study the role of personalization for modeling the behavior of a blind person. Moreover, the prediction horizon studied in related literature is often short, not allowing for planning over delayed reactions, navigation tasks which may span multiple seconds (as users may stop to listen to instructions, scan the environment with their cane before proceedings, etc.), and allow for sufficient plan-ahead (i.e., including several seconds of instruction utterance). In contast, we focus on long-term prediction of blind users' trajectories during interaction with a navigation system of up to 20 seconds into the future.
Designing Instructional Guidance Systems. Previous studies suggest that users with visual impairements generally prefer speech output during navigation [52]. Designing appropriate instructional guidance for such users has been extensively studied in research [53,54,55]. In particular, a diverse set of factors is known to contribute to navigation performance, including perceptions towards technology and previous experience [56,57], Orientation and Mobility (O&M) skills and the ability to deal with unknown environments, level of impairment, and more [9,58,2,59,60,40,61,62,11]. The possible design choices motivate our approach of an adaptive interface which can better meet the dynamic and specific needs of different types of endusers.
Reinforcement Learning for Adaptive Assistive Interfaces. We aim to find a policy that is optimized to provide clear and concise navigation instructions. Hence, the research in learning instructional timing and content is related to dialogue and human-robot communication systems [18]. RL provides a framework for interactive learning with an end-user, in particular for assistive applications [63,64,65,66,67]. Several previous studies formulated general collaborative navigation interfaces (i.e., for sighted users) in an MDP framework [68,69,70,71]. To select and realize humanlike instructions, methods may also employ a database of human-generated instructions [16,17]. In contrast, we do not assume access to such demonstrations, and complement previous studies by emphasizing efficient system adaptation. Specifically in the domain of assistive technologies for blind people, the overall majority of systems are not adaptive but static in their operation, and an in-depth analysis of the role of real-time personalization is lacking in literature. Instead, related studies often provide a preliminary prototype or analysis in a highly simplified environment [4,34,35], limiting insight into the role of personalized instruction.

Personalized Instruction Generation for Navigation
In order to provide a personalized instructional interface for navigation, we will model the interaction between the navigation system (agent) and the user (environment) as an MDP, described in Section 3.1. The MDP will be adapted to each user by learning a user-specific dynamics model in an while s i = EndGoal do 6: s g ← DetermineNextWayPoint(L, p, s i ) 7: 12: if is model update then 13: θ ← UpdateWeights(D, θ, η, λ) (Algorithm 2) i ← i + 1 22: end while 23: end procedure incremental manner. Specially, the user-specific dynamics models will be learned using a weighted majority algorithm and a recurrent network based function approximator to represent the user's dynamics model, described in Section 3.2. Based on the MDP and the learned user-specific dynamics model, we employ Model Predictive Control to determine the optimal instructional feedback (i.e., action of the MDP) for a personalized human-computer interface, described in Section 3.3.

Formulation
The adaptive navigation system PING is an MDP defined by a tuple (S, I, T , R, γ). S and I are the sets of states and possible actions (i.e., navigation instructions), respectively. Given a state s t ∈ S at time t, the instructional system performs an action a t ∈ I and observes a reward and an updated state s t+1 = T (s t , a t ) (the transition function). The learning goal is to solve for a policy, π(s t ) = p(a t |s t ), which is a mapping from state to action. Actions taken should maximize the discounted sum of future rewards, where γ ∈ (0, 1] is a discount factor and 1 < L < ∞ a time horizon for planning.
States. As the blind user is reacting to the instructions provided by the interface as well as the environmental context, we decompose the observations of the system to two components, a human user component s H , and a surrounding occupancy component s O . The state is then defined as where the state of the human is the position (x, y) and heading α of the user in the map, and the surrounding state s O includes occupancy and landmark features. For the obstacle descriptor o a vector of binary values encoding obstacles in discretized ego-centered and ego-oriented polar spatial bins around the user is used (we use 8 orientation and 3 distance bins). A similar encoding is used to represent landmark types (annotated in the floor plan) l as one-hot vectors.
Actions. We define a set of actions for the interface to provide instructional guidance. While current state-of-the-art assistive turn-by-turn navigation systems [72] select speech instructions from a fixed vocabulary of about 100 possibilities, their possible combinations (e.g., distance amounts, landmark types) lead to a problematically large action set. Instead of directly operating in this large set, the instructions are clustered into a set of semantically similar groups including 'Landmark,' 'Forward,' 'Approaching a Turn,' 'Turn,' 'Diagonal Turn,' 'Slight Turn,' 'Obstacle,' 'Information,' and 'Distance from Point of Interest.' These types (a type ) may be joined with additional arguments, the ego-centered direction (a dir , e.g., 'Left,' 'Right') or a quantity amount (a amount , e.g., 'Diagonal Turn', 'Slight Turn'). Also, two types of vibration feedback occur during turns, once at a turn onset notification, and again when correct heading is achieved. The actions a ∈ I are encoded as a concatenation of three one-hot vectors, In this work, this semantically clustered language space is used to efficiently learn dynamics models. Clustering is commonly employed in related studies for learning navigational interfaces, and decoding it further into natural language (i.e., realization) can be studied in the future [16].
Reward. While we focus on quickly learning personalized dynamics models, a suitable reward function for path-following is also defined for planning instructions with PING. The navigation task reward is a function of the current state, a planned path, a set of waypoints, and the floor plan layout. First, we reduce the map into a graph of connected links and nodes in the floor plan (i.e., corridors are reduced to a single link placed at the center of the corridor) and plan a global path with A* [73]. The task is decomposed into subtasks (e.g., completing a turn), defined via waypoints at fixed distance thresholds following turns and landmarks. Arrival to within a distance of 1.5 meters to a waypoint with the correct heading results in a trivial reward 0. The agent receives a negative reward of at every time step to encourage timely arrival to the destination. This magnitude is decreased further depending on the distance to the planned graph link (-1 within 1.5m, lower otherwise). We select 1.5m as a conservative bound for path following in environments with dense layout characteristics and adjacent corridors.

Learning a User-specific Dynamics Model
Model-based RL can be used to quickly compute an optimal policy due to lower sample complexity [21]. We learn a model for approximating T , denoted as f θ , which is a function parameterized by a set of weights θ that are being updated over incoming observations. The model is then used for sampling future trajectories, i.e., predicting behavior of a specific blind user, and finding the sequence of actions which maximizes expected future rewards. The goal is to learn a predictive model, with a basic understanding of how the blind user will react (a process of interpretation and decision making which is known to be complex [74,57,10]). To reason over scenarios where the blind user exhibits delayed responses to instructions on the order of multiple seconds, we require a model which can reason over a history of observations. Hence, we employ a state-of-the-art Recurrent Neural Network (RNN) with Long-Short Term Memory (LSTM) units [75,76].
User State Parameterization. Efficiently learning a dynamics model for navigation scenarios is difficult with limited data. If a 'Left Turn' instruction always results in similar changes to the regression output space, the model can more easily learn a basic understanding of what a left turn is, regardless of the user position, initial heading, or initial velocity direction. We therefore propose to change the output space to reflect the underlying dynamics during a turn motion in navigation, and find that it results in significantly more robust predictions around turns. Specifically, we convert the user's state to velocity values, so that it is invariant to actual user position, and convert these to polar coordinates (the appendix contains additional information). This modified output space is denoted asŝ H , such thatŝ When updating the model over incoming observations, the Mean Squared Error (MSE) of the three components inŝ H t+1 is used. Multi-step prediction is achieved by re-applying the dynamics function over previously predicted values and the updated instruction (sampled from the planner).
Personalized Dynamics with Weighted Experts. Adaptation of the dynamics is performed by updating the model parameters over incoming observations. When adapting the dynamics model to a new user, the model should be able to efficiently leverage the data from previously observed users. Figure 2: Weighted experts model.

Algorithm 2 Update Weighted Experts Dynamics Model
Hence, adaptation can be formulated as a form of transfer learning [77], where a deep network is pre-trained over the source data (in our case, a transitions dataset obtained by previous users of the system) and fine-tuned to the new target data (i.e., incoming data from the new user). However, while a single Neural Network model provides a popular high-capacity model choice [22], it can also have high sample complexity (i.e., when data is limited at the onset of adaptation).
We propose to use a weighted experts approach [78] to adapt the dynamics model in a sample efficient manner, where data from previously observed users is leveraged by using predictions of person-specific models as the experts. In adaptation to a new user, the off-line dataset is clustered to train M experts (person-specific dynamics models). To avoid issues with the experts pool, i.e., a small number of similar experts or a very different new user's distribution, we learn a weighted experts model over both previous users' models and a new user model learned from scratch.
Formally, when adapting to a new user, we learn a combination module θ W (i.e., a fully-connected layer) over the previously learned personal user-specific models' output (f θ i=1:M ) and the current user-specific model where we drop the input notation of state and action at the current time for convenience, and note that θ i=1:M are color coded as they are kept frozen during the adaptation phase (only [θ W , θ M +1 ] are updated, see Fig. 2). In this manner, the model can leverage the well-trained person-specific models while the predictions of the new person-specific model improve, and both modules can complement each other when making predictions. We demonstrate this approach to have both high data efficiency and modeling capacity when adapting the dynamics to a new blind user in real-world settings.

Personalized Instructional Guidance Planning with Model Predictive Control
For adaptive instructions with PING, the incremental personalized dynamics model needs to be paired with a planning algorithm. Model-based planning involves making future predictions and using the navigation task's reward function r to select the instructions provided by the interface. Due to the continuous state space, we employ an approximate solution method which is suitable for our navigation application domain. The MPC-based planner [31,79,80] can handle compensating for errors in the model by re-planning at every step and adds minimal learning overhead.
Given a finite planning horizon (L), we aim to find the sequence of actions that maximizes, where 'Integrate' is an operation to recover the original state parameterization for calculating the reward, p is a globally planned path, and w is a set of waypoints. The discount factor is set to γ = 1.
We approximate the solution to Equation (6) by sampling a set of plausible instructional sequences and choose the one which maximizes expected cumulative reward. Specifically, we unroll the trajectory with the current policy to obtain an initial action sequence, and use random sampling and time-shifting to generate additional plausible sequences [81]. This approximate solution to Equation 6 can be used to select the next action to be executed, observe the resulting state, and re-plan the instructions. The planned path is re-planned in cases where the walker drifts off too much (Alg. 1).

Formative Study and Experimental Results
Robust prediction of the user state is a main challenge in instructional planning with PING. Hence, we begin our work by analyzing a large dataset of real-world user dynamics. Besides uncovering the impact of personalization on the end-user experience, the dataset is used to (1) train personspecific dynamics models as experts, (2) perform on the fly personalization to new users, (3) evaluate long-term prediction as adaptation occurs to compare personalization schemes, and (4) inform the dynamics of a set of diverse simulated walkers for evaluating PING.
Platform. To understand and model dynamics of real users, we employ a dataset collected with the smartphone app of [72]. While several other assistive navigation solutions have been proposed, including a service [11] or portable robot [4], the open-source smartphone app [72] can be quickly disseminated across researchers and blind users. Using a smartphone also allows users to use their preferred mobility aid while navigating without much difference to their daily mobility. Besides the possibility of reaching wide-spread adoption, we made efforts to keep our formulation as general as possible, so that it may be useful for other applications in assisted navigation. For instance, studying adaptation of the dynamics model is not just relevant to transferring to new users, but also to different use modes, platforms, and mobility aids.
One participant used a guide-dog and the rest white cane. Following a training session, each user was asked to navigate in a large public space. The ∼400 meters route spanned three floors with over 200 Bluetooth beacons placed every 6 to 8 meters. The smartphone's IMU and environment's Bluetooth beacon sensor measurements are fused with a particle filter [82] to provide continuous user position and heading information. As in any real-world system, the measurements contain inherent noise. The localization error, evaluated by manual annotation of the position of the users from video, averages 1.8m, which is competitive for indoor settings.
Data Processing. Each trajectory was resampled to 500 millisecond intervals. Given over two hours of total data analyzed, this results in ∼15K samples overall. Prediction is fixed at T = 20 seconds into the future in most of the experiments. When visualizing motion during this time span (Fig. 1) we can see how this challenging long time horizon for predicting human behavior takes into account the approaching, task onset, re-orientation, and motion continuation along turns. Also, the interface must be given sufficient time to plan ahead, including announcement time.
Evaluation Measures. Emphasizing long-term prediction of human behavior, we compute endpoint displacement error (EPE), in meters, between the predicted future trajectory and the observed trajectory. We also employ the average displacement error between the two trajectories.
Adaptation Experiment. When adapting to new users, data from a new test user is partitioned into two temporally disjoint sets, an adaptation set and a test set. As the model observes the new user's motion from the onset of the experiment at time 0, we collect the transitions, update the model weights, discard the collected data, and repeat. Following each update, we use the dynamics model to perform long-term prediction on all transitions in the test set and average the errors across all sampled points along the trajectory as a summarizing evaluation measure. As the model observes more from the adaptation set, the test set remains fixed. Unlike batch error, this evaluation procedure provides a constant measure for the improvement, and therefore a more meaningful way to benchmark the impact of personalization schemes while ensuring generalization across environments. We update the weights in batches of 30 second intervals to provide some learning stability while identifying clear performance trends, yet this update rule can be modified as needed in practice.

Formative Study: Characterizing the Dynamics of Blind Users
To motivate our adaptive approach, we performed statistical analysis of user behavior which can be found in the appendix, as well as Fig 3. Analyzed by leveraging continuous tracking of the users, the extent of this phenomenon has not been rigorously studied in related studies. With the aim of understating the role of personalization, we find that in long real-world navigation routes with diverse stimuli, user variability has significant implications to system design. Specifically, beyond individual walking pace, we find user reaction (e.g., speed change, task timing) varies in a person-specific manner, in particular during the most crucial elements of the navigation such as when turning and encountering obstacles. For instance, users with similar initial speeds may respond very differently to the same instruction, e.g., one slows down to a near stop during turns and another maintaining pace, so that a constant velocity or user-agnostic dynamics model will perform poorly in long-term prediction. We also observe user-specific consistency in under/over-turning and behavior around obstacles. We found such individual differences in the dynamics to result in navigation errors in open spaces and turns, motivating an adaptive interface which can predict ahead and adjust accordingly.

Evaluation of Learned User-specific Dynamics Model
Based on our analysis of blind user dynamics, we expect personalization to be essential in predicting future user behavior. As shown in Fig. 4, several adaptation schemes are benchmarked to understand issues in personalizing the dynamics model. A person-specific RNN baseline involves learning a single model (i.e.,f θ M +1 ) from scratch. We also analyze the de-facto standard in transfer learning of fine-tuning a pre-trained model. In the experiments, we consider two variants of fine-tuning. In one variant, initial pre-training is done in a person-agnostic manner (i.e., a model learned with all previous users' data) and weights are updated for the new user's motion dynamics. In the second variant, the pre-training is done with multiple network heads [83,84] (a separate head for each previous user). These approaches can learn to leverage shared motion patterns across different users and are the most widespread approaches for transfer learning. However, relying on the fine-tuning mechanism to learn and adapt a general hidden representation can be prone to optimization issues, in particular when data is limited at the onset of adaptation. Fig. 4 depicts the results for the adaptation experiments, where a large reduction in long-term prediction error across all the personalization techniques can be observed. Due to the inherent variability, we find all models perform similarly at the onset of the experiment as it begins after an initial batch of new user's data. For this challenging prediction task, we can see a significant reduction in prediction errors once the entire adaptation set has been observed by the models. For instance, adaptation translates to a 2.23m (19.7%) reduction in 20 second end-point prediction error for the fine-tuning adaptation baseline that is pre-trained with multiple separate network heads (FineTune-MH), 1.92m (17.1%) reduction for the standard fine-tuning baseline (FineTune), and 1.81m (16.8%) for the experts model. For a complete analysis, we also show results of a weighted experts model without the jointly trained new user-specific dynamics model as one of the experts (Experts-NS). Overall, the success of the improved long-term user behavior prediction is directly due to user-specific consistency in reactions, as the models are required to generalize to disjoint part of the navigation in our evaluation procedure.
When contrasting to the model that is trained from scratch in Fig. 4, we can see how both finetuning baselines are able to leverage previously observed user data. Multi-head training is found to improve learning of a generalizable representation which can be better transferred across different users. However, despite ablative experiments with model size and learning rates, the model shows slower adaptation performance compared to the experts model (which is shown to achieve the same performance rates in half the time or less), and only minimal improvement during turns compared to the model that is trained from scratch. While turn events are rare, they result in the most interuser variability. This performance issue is a significant limitation as navigation errors occur most frequently during turns in the dataset. In this case, we find that the model is unable to fully account for personal variability, and instead results in a more generic or averaged motion model. This can be seen when visualizing the predicted trajectories in Fig. 5 (the appendix contains more examples). Specifically, the model incorrectly estimates user's reaction and fails to account for individual veering behavior (Fig. 5(c)). Although adaptation through fine-tuning a shared-weights model has many benefits (e.g., computational efficiency), it comes with a trade-off when adapting to large changes in the input-output variable relationship when observing a new user.
The experts model shows the best performance in terms of data-efficiency, often converging in under 2 minutes with minimal 'over-fitting' to the user behavior thereafter (i.e., the observed phenomenon where additionally observed data increases testing error). By leveraging outputs from a set of specialized dynamics models, this adaptation method can quickly identify which previously observed models most match the current user's dynamics. This adaptation process is therefore found to be more efficient when compared to single model fine-tuning. In terms of prediction results, we find that unlike the other adaptation baselines this architecture is able to balance both short and longterm prediction accuracy across different types of instructional events and environmental scenarios, as can be seen by inspecting the T = 5 and T = 10 seconds prediction plots in the appendix.
Isolating turn events in the evaluation (Fig. 4-right) demonstrates that the proposed experts model outperforms other baselines at both adaptation (lower errors at the onset of learning) and convergence. Since the performance is averaged over thousands of events, the results are statistically significant (p < .001). The results are also statistically significant up to minute 3 over the entire dataset Fig. 4-left (p < .01). These findings suggest that employing the proposed model could mean the difference between a successful turn or a early/late turning and consequently slower arrival to destination. While we expect the model to eventually prefer the new user's personal model (hence matching performance with the user-specific model that is trained from scratch), we find that the model learns to generalize better through the majority voting, even when ample data is available.
We note that at times, predictions may pass through walls or obstacles. Despite the high accuracy indoor navigation system used in the study, there is still an inherent localization error which leads to such instances in the training data. Since observed transitions sometimes go through walls (especially thin walls or wall corners), the trained models also predict such behavior. Nonetheless, we find that the models do learn a notion of interactivity between obstacles and blind users. For instance, certain mobility strategies by users such as tracing along poles and walls can be observed (e.g., Fig. 5(f)). Fig. 6 shows challenging prediction scenarios, where the prediction model overestimates a veering or incorrectly predicts interaction of the user with obstacles. Although minimal veering can lead to large differences over the prediction horizon, the proposed model still produces plausible predictions. For instance, in Fig. 6(c) the model considers the orientation of the current user to assume veering to the left, which is reasonable. Also, the response to a 'turn diagonally to the left' instruction and the interaction with the wall are a reasonable scenario.

Evaluation of Personalized Instruction Generation
Towards evaluating a complete adaptive system on diverse walkers, we create simulated walkers in the same floor layout as the real-world studies. The simulated users are informed by the statistics of the real-world study, and used to create a larger variety of walking types in the same settings. Hence, we can test PING extensively before the final deployment in a safe manner. We emphasize Figure 5: Visualization of long-term prediction results. The weighted experts personalization scheme is compared with a fine-tuning adaptation baseline. Instruction points from the policy are only shown along the ground truth future trajectory.
(a) (b) (c) Figure 6: Challenging cases. Even under challenging cases, such as around pillars and significant veering, the proposed approach results in more reasonable predictions by better capturing long-term motion patterns of the specific user.
appropriate timing of instructions during turns, so that walking parameters are randomized over reaction time for instructions, speed change during turns, and amount of veering from the planned path. All experiments begin with 30 seconds of data collection with the static baseline policy of [72]. The results, averaged over 100 random trails in Fig. 7, show that using the experts model for adapting the system on walkers with greater diversity translates into longer periods of the user staying on the path and timely arrival to the destination. Specifically, we observe a 49% reduction in instances of large deviation (over 1.5m) compared to the non-adaptive baseline.

Conclusion
Adaptive assistive navigation systems have the potential to better meet the dynamic information needs of the blind end-user. Informed by a real-world navigation study, we proposed an approach for adapting a dynamics model across users. The models can be used to personalize instructional guidance, hence taking a step towards less manual design of generic interfaces that fail to flexibly accommodate large variability in blind user behavior.
Our study focused on understanding and learning user dynamics, with several future directions. First, we would like to continue and study issues in scalability of navigation interfaces, where the personalization must efficiently deal with an ever increasing pool of users. Although the weighted experts model was designed to handle scenarios where the pre-trained expert models may be suboptimal, a practical realization could involve an additional sampling mechanism over the experts. Learning more robust long-term prediction models that can reason over uncertainty can also be pursued in the future. Extending the personalized navigation interface framework to plan over the path and the instructions concurrently can allow it to choose more user-friendly routes. While we emphasized prediction and timing during the most critical navigation task of turning (i.e. concise notifications), we can see how a more elaborate instruction generation planner (i.e. natural language) could be added. Surrounding pedestrians can also be detected and incorporated into the state. Given that we studied practical design issues in scalable adaptive navigation interfaces, an important next step would be further validation in real-world, large-scale studies.

Acknowledgments
This work was sponsored in part by a JST CREST (JPMJCR14E1), NSF NRI award (1637927), and the Shimizu Corporation. We greatly appreciate assistance of collaborators Daisuke Sato, Hironobu Takagi (IBM Research Tokyo), João Guerreiro, and Dragan Ahmetovic (Cognitive Assistance Lab).

A.1 Model Training Details
Hyper-parameter settings were determined for each model type by a grid search over layer size ∈ {10, 25, 50, 100, 200}, depth ∈ {1, 2, 3, 4}, and learning rate ∈ {10 0 , 10 −1 , . . . , 10 −5 }. All training objectives used the MSE between model's prediction and observed (reparameterized) transitions. For a person-specific model, a single layer LSTM with 50 hidden units was used, followed by a fully connected layer. The person-agnostic fine-tuning baseline model (learned over data from all users) was found to benefit from increased model capacity, hence we used two stacked LSTM layers of 100 hidden units each. All models were trained with Stochastic Gradient Descent (SGD) with momentum.

A.2 Reparameterization for Efficient State Regression
The parameterization of the state space can significantly impact the training of a predictor, in particular when data is limited. If a 'left turn' instruction results in similar dynamic changes, the model can more easily learn a basic understanding of what a left turn is, regardless of the user position or initial direction. For instance, instead of regressing future orientation and position values of the user which can result in overfitting or poor convergence with limited data, we may regress velocity values, i.e., the difference in s H ,ṡ H = [ẋ,ẏ,α] = [ ∆x ∆t , ∆y ∆t , ∆α ∆t ] for more meaningful and general learning of user behavior across environments. Yet, we still encountered issues in predicting such state differences, especially around the critical non-linear components of the navigation.
We found it useful to modify the state space to better accommodate learning user behavior during such events by converting all parameters inṡ H to polar coordinates. The idea is that a 'turn left' action would result in a similar signal to be regressed, regardless of the initial direction of the user. While similar turn types (e.g., 'turn left') result in similar values ofα (in radians per second), this is not the case for [ẋ,ẏ] throughout a turn, which depend on the initial velocity direction and magnitude. This implies that learning the mapping from actions to changes in the state is more challenging, e.g., the dynamics during a 90-degree turn are more complex. In our experiments, this resulted in models which poorly behaved around turns.
For instance, in Fig. 1 in the main paper, the changes in the x and y positions over an entire turn will change depending on the starting heading of the user. Changing this heading will result in very different velocity dynamics values in these components. To simplify training, we convert [ẋ,ẏ] to polar coordinates, [ρ, β] (linear velocity magnitude and orientation). We emphasize the difference betweenα, which is the user's heading, and β, which is the direction of the user velocity vector (the two are independent). Specifically, the user may rotate in place (changingα while β is 0), or step to the right (changing β, but notα).
β encodes a motion direction, and therefore will have different values in the same type of turn. To ensure that the model learns a basic understanding of turn types (without having to show it examples at all initial user motion directions), we predict the change in β instead,β, so that With this parameterization the coordinates are invariant to the original directionality of both heading and velocity, but only vary with the turn amount and turn direction. This straightforward modification was found to impact the learning performance of the regressor during turns.

A.3 Additional Model Evaluation
We preform ablative evaluation to benchmark different approaches in prediction over the entire dataset. Training and evaluation is performed across all users to determine impact of different model choices on general motion modeling. By comparing different prediction approaches, including a simple constant velocity model, Kalman filter [85], Logistic regression [86], we can better understand the impact of our model choice on the end-user's experience. Fig. 8 shows the benchmarking of different model choices for user motion prediction. The models were all trained to predict velocity measurements, as commonly done [22], besides LSTM-ŝ H . The analysis shows discriminative training to be useful for handling of highly non-linear trajectory components, where users may reach full stops for multiple seconds or encounter obstacles and veer in different directions. We notice how reparameterization of the regression output space (ŝ H instead ofṡ H [22] for the other baselines) is beneficial for better prediction, both in end-point prediction of the trajectory-error drops significantly from 10.5 to 9.1 meters on average end-point prediction at T = 20 seconds prediction, as well as orientation prediction. The difficulty in learning a rotational and initial-state invariance from the data automatically, in particular without samples at all initial orientations, can be easily alleviated with an appropriate parameterization of the output space. Fig. 9 shows summarizing plots for adaptation evaluation of the dynamics model to new users. As more data becomes available from the adaptation set (time into the experiment) the model better predicts the future trajectory of the user. In addition to the T = 20 second prediction results for end-point error in the paper, we also show shorter term prediction results for T = 5 and T = 10 seconds. For evaluation, we employ average displacement error (in meters) across all points along the predicted and actual trajectories and the end-point displacement error between the trajectory end-points.

Prediction T=20s
All Events Turn Events EPE -All Events EPE -Turn Events

A.5 Dataset Analysis
User reactions to the interface ultimately determine the success of the navigation task. To motivate the proposed approach for accommodating individual differences in blind navigation, we include a data-driven analysis of this critical issue in system design. The analysis reveals the impact of personalization on navigation success and end-user experience. To analyze per-user variability in the data, we will plot speed measures on an individual basis within each instruction type (the measures we are ultimately trying to model and predict in the main paper). We study average speed over a time window of 6 seconds following an instruction onset to capture user motion (linear speed in meters per second and angular speed in radians per second, often averaged across all events in the dataset). We also report average speed change following an instruction [10].
Statistical testing is performed to ensure statistical significance in user behavior variability. For each test, we set the participant id as the independent variable (for studying inter-user variability). When reporting findings, we fix a motion measure (e.g., average angular speed) as the dependent variable. In all experiments normality is first verified using a Shapiro-Wilk test, and followed by ANOVA under normality or a t-test otherwise, with an alpha level of .05.

A.5.1 Turn Events -User Variability Analysis
Turning events require a detailed analysis, as they exhibit the most significant variability, take multiple seconds to perform, and are crucial to the overall navigation task [40]. The majority of navigation errors in the dataset occur during turns. The figures show the spectrum of variability among users. Variability in linear speed is significant both for large turns (F (8, 130) = 5.7, p < .001) and small turns (F (8, 106) = 2.63, p = .011). We find that the guide-dog user P4 is generally faster than other participants, but cane users (e.g., P3) can maintain a similar speed during turns, so that even when testing without the guide-dog user variability among participants is still significant (p < .001).

Large Turns
Since reactions to 'turn' notifications involve the largest reduction in speed among all instruction types, the statistical difference remains in average speed change (p < .001 for both large and small turns among users). The large spectrum includes P3, who tends to maintain speed at turns with only a slight overall reduction, and P1, P2, and P9, who reduce their speed significantly. Beyond just using a velocity-based timing of instructions, a user-specific model of motion reaction to 'turn' notifications can potentially reduce the chance of missing a turn (especially considering inherent localization errors).  Figure 12: To better understand the relationship between user motion, instruction timing, and navigation errors, we plot the distance traveled by users during two components of a turning task, (a) initial reaction (between instruction onset to turning motion onset), and (b) entire turn task (instruction onset to turning motion completion). We can see how adaptive timing of instructions can prevent navigation errors in situations of open space or multiple corridors, as the distance traveled during the entire turning task (or even the initial reaction before turning begins) can span several meters. Figure 13: Example event definition for an instructed turn in the data. Grid lines are at 1 meter intervals, and in black are obstacles/walls. Due to high variability in turns, we decompose turns by defining 5 temporal subevents, I S the instruction beginning time (in green), I E instructions end (pink), T S , onset of turning by user (black), I H heading feedback from the interface (dark blue), and T E the end of the re-orientation by the user. Trajectory before and after the entire sequence is dashed. We then compute timing statistics between these events.

Distance Statistics -Turns
Significant Variability in Angular Speed During Small Turns. In the case of large turns, we do not find the angular speed variability to be statistically significant among users (p = .576), yet it is significant for small turns (p = .003). This can be explained by the physically easier task of gauging orientation during a sharp turn (90 degrees) compared to diagonal or slighter turns. While all users were instructed and trained of the differences between turn types and their extent before the study onset, variations in small turning could easily result in over or under-turning, and consequently veering off the planned path. As a concrete example, we find that a diagonal turn in an open space area along the route caused P7, P4, and P5 to get off the path. In one instance in the dataset, P5 over-turns following an instruction to turn diagonally to the left, and veers off the path in an open space. Hence, we can see how considering personal characteristics in reactions to turn instructions can be useful for developing interfaces which better prevent user-related navigation errors.
Significant Variability in Timing. We further analyze reaction and task completion statistics following turning instructions, also finding significant variability among users. Following a 'turn' notification, task timing can be clearly identified between the onset of the turning action and its completion. As a result, a variety of timing statistics can be computed. Here, we analyze the reaction time, overall task performance, and reaction to the vibration and sound feedback at the end of the turn indicating a correct heading has been achieved (the feedback is purposed to be used by the user for proper re-orientation during the turn, yet we find reaction to it takes another 0.91s on average, SD=0.71).
The reaction time between onset of instruction and beginning of the turning action is shown to be highly variable among users (F (8, 236) = 2.15, p = .032). While the average reaction time (average 1.37s, SD=1.08) is close to the one reported in related literature [42], other studies are often performed in controlled settings with short routes, thereby missing the crucial finding of significant variability among users. In contrast, we show it to be highly variable. We also find that the total time to complete this task may last over 4 seconds for some users (average 3.54s, SD=1.17), and is statistically significant among users (p = .006).
Is It Due to Age Differences? One possible explanation for the variability could be users' age, but this was not confirmed by our data. While our user population is generally older (4 participants are under 46 years old), we attempted to group participants into two groups using several age group definitions, but found no statistically significant differences with respect to reaction time or overall (a) (b) (c) Figure 16: Individual differences among users when responding to assistive guidance. (a) Average speed (over a 6 second window) following the onset of instructional guidance, (b) speed change following the onset of instructional guidance (difference between end speed and starting speed divided by the time change of 6 second window), and (c) angular speed following different instructions.
task time. While we found older users (over vs. under 46 years old) to move slower towards the end of the turn (p = .007), which is somewhat to be expected, it does not fully explain the variability in turn timing. Additional data is required for this type of analysis.
Large Variability in Mobility Skills & Strategies During Turns. Instead, we are able to explain this phenomenon by inspecting each user's mobility during the navigation. Specifically, some users are able to better anticipate upcoming turns by leveraging their mobility skills. The insight came by inspecting the video data, in particular between the fastest 'turner' P3 compared to a slower one, such as P1. P3 is able to use several navigation strategies to achieve correct and quick turning. Since users are informed of the upcoming navigation turning point and turn direction after completion of the previous turn, P3 constantly checks for an available turn with the cane in the notified direction (only with the cane, while still walking forward). Hence, the moment a turn is available, P3 immediately begins turning, even before the turn notification completes. On the other hand, P5 appears to heavily depend on the instructional guidance while walking in the middle of the hallway. P1 does not employ a similar strategy, and simply awaits the next instruction while using the cane to avoid obstacles (but not for anticipating or seeking turns). Also, P1 pauses before turning, and turns very cautiously as if hesitating before acting due to a notification. Inspecting videos with other users, we found each to be on a spectrum, between the behavior of P3 and P1 in terms of mobility strategies. Hence, we conclude that personal differences in mobility skill and style help explain variability in reaction to turn notifications.
Timing Variability Among Turn Types. Timing results can be further analyzed by the turn type (small vs. large). When comparing among turn types in terms of timing, we observe more inter-user variability occurring during the large turns as opposed to small turns. Particularly relevant to our analysis is the finding that some users treat small turns with less care on a consistent basis. In the dataset, several users which over/under-turn got off the planned path in an open space area.

A.6 Walker Visualization
To evaluate PING we use the real-world motion statistics and environment to generate a large number of walkers ( Fig. 18) with greater motion diversity and measure cumulative reward.