The Quest For "Always-On" Autonomous Mobile Robots

1 Introduction

We seek the ultimate goal of having autonomous service mobile robots working in human environments, performing tasks accurately and robustly on demand. Such robots should be capable of working for not minutes, hours, or days, but for years at a stretch. Developing, testing, and overcoming failures for algorithms that can execute robustly and accurately over such protracted time scales involves unique challenges. First, perception algorithms must be robust to changes in the environment. Second, over such long deployments, robots will inevitably make errors. They will have to anticipate errors, and overcome their failures without requiring the assistance of robotics experts. Finally, testing for robustness over such a long duration is a challenge in of itself: we need new approaches to process logs to gain insights into why algorithms failed, to support the development of techniques to overcome such limitations. In this paper, we summarize our research towards addressing all of these challenges.

In Section 2, we present Episodic non-Markov Localization (EnML), a localization algorithm for changing environments that reasons about the nature of its observations: whether they correspond to permanent objects, movable objects termed, or moving objects. EnML reasons about unmapped objects in real time, at the time of deployments, without relying on up-to-date static maps of the environment.

To demonstrate the robustness and accuracy of localization using these contributions, a few years ago, we proposed the 1, 000km Challenge: Demonstrate, on a team of deployed autonomous mobile robots, in multiple real-world human environments, the robustness and accuracy of localization over long-term deployments covering a total distance of more than 1, 000km. In Section 3 we summarize our results from the 1, 000km Challenge, including accuracy, and robustness in different environments over the 1, 000km Challenge.

Over long-term deployments, autonomous robots will inevitably make mistakes. In Section 4, we present our work on predicting such errors. From data collected over the 1, 000km Challenge, we demonstrate that the dynamics of the environment correlates with the robustness of localization. We further present our work on introspective vision to use supervisory sensing to learn models of failure of stereo vision used for obstacle avoidance. The learned models are capable of not only accurately predicting failures, but also inferring the number of distinct classes of failures.

Next, in Section 5 we present our research on overcoming failures of robots by incorporating approximate, partially specified corrections from non-technical users. Specifically, we present our work on human-in-the-loop SLAM [Nashed and Biswas, b] to overcome mapping failures, and SMTbased robot transition repair [Holtz et al., ] to overcome action failures arising from incorrect transitions in robot state machines.

We conclude with a discussion of open challenges and promising directions for future work in Section 6.

2 Episodic non-Markov Localization

In support of the goal of long-term autonomy, there have been a number of approaches proposed to address the inevitable changes in human environments that robots must adapt to. Some such approaches include reasoning about the different discrete states of the environment [Meyer-Delius et al., 2012; Stachniss and Burgard, ], expanding occupancy grid maps with temporal Markov chains [Saarinen et al., ], and timebased map-switching [Biber and Duckett, 2005; Krajn´ık et al., 2017]. In our work, we realize that maintaining multiple discrete states of the world, or dynamic models of all the parts of the environment may be infeasible for robots deployed over long periods of time, in large environments. Hence, we introduced Episodic non-Markov Localization (EnML) [Biswas et al., ; Biswas and Veloso, a], an algorithm that 1) explicitly reasons in real-time about its observations that do not match the long-term map, and 2) jointly accounts for the relative pose corrections from such unmapped objects concurrently with global pose corrections from mapped objects, in 3) a single sound probabilistic framework that enables efficient inference of the maximum likelihood estimate of the robot's trajectory.

At each time step, EnML classifies observations as arising from Long-Term Features (LTFs), Short-Term Features (STFs), or Dynamic Features (DFs). To represent the varying nature of localization in the presence of unmapped observations, we introduce a new graphical model, the Varying Graphical Network [Biswas and Veloso, b]. As in the Dynamic Bayesian Network for Markov Localization, a Varying Graphical Network (VGN) includes certain periodically repeating nodes and edges that do not change with the belief. A VGN includes two additional structural elements: varying nodes and varying edges to track the presence and correlations between STFs and DFs. Figure 1 shows an example instance of a VGN. By reasoning about observations from STFs and DFs over extended deployments, we have also shown how we can build model-instance object maps [Biswas and Veloso, 2014] and long-term vector maps [Nashed and Biswas, a].

Given the initial pose of the robot x0, observations s1:n, odometry u1:n, and a static map M, EnML factorizes the belief over the robot's trajectory x1:n, according to the correlations in the VGN. We do not track DFs for localization, hence they assume a constant value based on priors. Exploiting the fact that different classes of observations (m STFs and n LTFs) are independent of each other, the belief for EnML is given by

Since the VGN for non-Markov localization has no predefined structure, it might seem that computation of the belief would require storing the complete history of all states and observations of the robot. However, in practice this is not necessary. Suppose there exists a time step ti such that all observations and state estimates made after ti, given xi, are independent of all prior observations and state estimates. This conditional independence implies that there are no STF observations after ti that correspond to STF observations before ti. In such a case, the history of states and observations prior to ti, called the "episode" t0:i-1, can be discarded when estimating Bel(xi:n) over the episode ti:n. We thus define an episode tj:k to be a consecutive sequence of time-steps from tj to tk such that the observations made between tj and tk are independent of all observations made before tj , given the pose xj , and the permanent map M.

In order to explicitly account for the effect of the past robot pose estimates x0:n on future observations and pose estimates, we solve for the Belief over the complete history of robot poses, Bel(x0:n). Due to the prohibitively large state space, we concentrate on evaluating the Belief in the neighborhood of its maximum likelihood estimate, computed via non-linear least squares optimization of its log-likelihood.

3 Evaluating Long-TermAutonomy in the Real World

One of the challenges of working on long-term autonomy is that real-world evaluation is hard - there is no good surrogate for the rich diversity of scenarios that the real world offers, in order to stress-test algorithms for long-term autonomy. We therefore decided to evaluate our robot localization algorithms over the 1, 000km Challenge, which spanned several years of deployments in real human environments. The localization algorithms tested included depth-based localization using plane filtering [Biswas and Veloso, a], LIDAR-based localization using Corrective Gradient Refinement [Biswas et al., ] for particle filters, and Episodic non-Markov Localization [Biswas and Veloso, b; Biswas and Veloso, 2017]. The 1, 000km Challenge was conducted on a group of autonomous service mobile robots, the CoBots, from May 17, 2011 to November 18, 2014. Over the course of their deployments, four CoBots autonomously performed various tasks [Veloso et al., ] for users, including escorting visitors, transporting objects, and engaging in semiautonomous telepresence.

The robots were deployed in several buildings, including the Gates Hillman Center (GHC) and Newell-Simon Hall

(NSH) at Carnegie Mellon University, and the Center for Urban Science and Progress, 1 Metrotech Center at New York University (NYU). There were 12 floors in total across all the buildings that the CoBots were deployed on.

The 1, 000km Challenge resulted in the collection of over 168GB of compressed data logs, which are available online 1 . We quantitatively evaluated the accuracy and robustness in localization over the 1, 000km Challenge by 1) comparison to scan matching, 2) comparison to sparse ground truth, and 3) tracking operator interventions. The complete results include analysis of the accuracy and robustness as a function of the envrionment [Biswas and Veloso, 2016], and here we present a short excerpt of accuracy by comparison to ground truth.

CoBot2 and CoBot3 were equipped with Hagisonic StarGazer sensors, which detect StarGazer marker patterns mounted on the ceiling. We had 46 StarGazer markers placed on the ceiling throughout the Gates-Hillman Center to provide sparse ground-truth location estimates. When a CoBot detected a StarGazer marker, the localization estimates were compared to the global location of the observed StarGazer marker to compute the error in localization.

In addition to localization accuracy, we also logged when operator intervention was required to reset robot localization. By calculating the mean distance traversed between such interventions, we were ably to quantify the robustness of localization as a function of location and algorithm used. In the next section, we summarize our findings of the primary predictors of robustness over the 1, 000km Challenge.

4 Predicting Failures

Robots will inevitably make errors when deployed over extended periods of time. Can we learn to predict the conditions under which the robot is likely to encounter errors? We have investigated this question across two settings: predicting localization failures from the 1, 000km Challenge, and learning to predict failures of vision-based obstacle avoidance.

4.1 Analyzing Localization Failures

Over the duration of the 1, 000km Challenge, Corrective Gradient Refinement (CGR) [Biswas et al., ] was used for localization from September 2011 to January 2014, while Episodic non-Markov Localization (EnML) was used from February 2014 onwards. Table 2 compares the Mean Distance Between Interventions (MDBI) for each map in the Gates-Hillman Center building when using CGR, and when using EnML for localization. The MDBI for EnML is 8.13km, which is significantly higher than the MDBI for CGR, 4.79km, thus demonstrating the higher reliability of EnML for localization in real-world human environments.

1 http://www.cs.cmu.edu/∼coral/cobot/data.html

The variations in the MDBI across the different floors are due to the differences in the number of movable objects and variations over time between the different floors. Table 2 highlights the different characteristics of each floor by enumerating the median fraction of observations that were LTFs, STFs, and DFs. Floors GHC6, GHC7, GHC8, and GHC9 were observed to have the fewest number of unmapped observations (STFs and DFs), and correspondingly had longer MDBI for both CGR and EnML. Floors GHC4 and GHC5 had significant human traffic and movable objects - note that only 12% of the observations on GHC4 matched the map. These floors are where EnML had a higher MDBI compared to CGR, thus demonstrating the robustness of EnML while localizing in challenging dynamic environments.

4.2 Introspective Vision for Obstacle Avoidance

Vision, as an inexpensive yet information rich sensor, is commonly used for perception on autonomous mobile robots. Unfortunately, accurate vision-based perception requires a number of assumptions about the environment to hold - some examples of such assumptions, depending on the perception algorithm at hand, include purely Lambertian surfaces, texturerich scenes, and absence of aliasing features or refractive surfaces. Such assumptions are hard to frame mathematically, hard to detect, and may even be unknown a-priori. We introduce an approach for introspective vision for obstacle avoidance (IVOA) to automatically predict when a vision system used for obstacle avoidance is likely to produce erroneous results, stemming from such invalid assumptions. By leveraging a supervisory sensor that is occasionally available, IVOA detects failures of stereo vision by divergence in plans between those generated by vision and by the supervisory sensor. By projecting the 3D coordinates where the plans agree and disagree onto the images used for vision-based perception, IVOA generates a training set of reliable and unreliable image patches for perception. We then use this training dataset to learn a model of which image patches are likely to cause failures of the vision-based perception algorithm. Using this model, IVOA is then able to predict whether the relevant image patches in the observed images are likely to cause failures due to vision (both false positives and false negatives).

Different vision algorithms that make different assumptions about the world, are likely to have differing failure conditions. We demonstrate the ability of IVOA to predict failures specific to different algorithms. For evaluating this ability of IVOA, we used two vision algorithms: a simplified variant of Joint Perception and Planning [Ghosh and Biswas, ] that assumes there are no textureless surfaces (JPP-C), and ELAS [Geiger et al., 2010], a dense stereo matching algorithm. IVOA is trained separately using the supervisory input along with each of these vision algorithms, and the two separate models are then used to predict failures of their respective vision algorithms. Figure 2 shows the failures predicted by IVOA for each vision algorithm.

5 Overcoming Failures

An inevitable challenge for long-term autonomy is that no matter how sophisticated, no perception algorithm is perfect, and robots will inevitably make mistakes. From our own 1, 000km Challenge, we showed how EnML [Biswas and Veloso, 2017] significantly improves over Markov Localization on the mean distance traversed between interventions, but there were still a number of inevitable interventions (Section 4.1). To compound the problem of inevitable failures, state of the art robots deployed in the real world need expert roboticists to come to their aid to overcome errors. There are two reasons for this: first, algorithms make strong assumptions about their models, and second, they depend on precise parameter values for robust execution. Fixing such domainspecific parameter values, or inducing the algorithms to overcome their assumptions, are well beyond what non-roboticists are capable of. However, while non-technical users may not know about the internal workings of algorithms, when robots make mistakes in terms of perceptual estimates or actions, it is often easy to understand what the correction should be, in terms of the correct perceptual estimate, or the correct action to take. With this key insight, we introduced human in the loop SLAM [Nashed and Biswas, b] for correcting errors in mapping,and interactive robot transition repair with SMT [Holtz et al., ] for correcting action errors.

5.1 Human in the Loop SLAM

Building large-scale, globally consistent maps is a challenging problem, made more difficult in environments with limited access or sparse features, or when using data collected by novice users. For such scenarios, where state-of-theart mapping algorithms produce globally inconsistent maps, we introduced Human-in-the-Loop Simultaneous Localization and Mapping (HITL-SLAM) [Nashed and Biswas, b], which incorporates approximate, non-expert corrections into pose graph SLAM, while explicitly reasoning about the potential inaccuracies in the corrections. HITL-SLAM graphically presents the map estimate to the user, and allows the user to paint over sets of observations to specify relative geometric constraints between them - collinear, parallel, coincident, or perpendicular. There are three challenges to incorporating such corrections: 1) the user input will be ambiguous, and HITL-SLAM needs to interpret it; 2) the corrections may be partial, with the user only selecting part of a larger single entity such as a wall; and 3) the corrections need to be applied jointly with the existing correlations between observations in the SLAM problem. HITL-SLAM overcomes the first two problems by running an EM optimization to interpret the user input, and the third problem by using a novel set of human correction factors in a factor graph SLAM fomrulation to jointly solve for the map estimate with user corrections.

5.2 SMT-Based Robot Transition Repair

When a robot makes errors while performing actions instead of during perception, we use a different approach to interactive corrections. Complex robot actions are typically structured as state machines, where each state encapsulates a feedback controller. Even if each state is correct, the transitions between states depend on parameters that are hard to get right, even for experienced roboticists. It is very common for parameter values to work in simulation but fail in the real world, to work in one physical environment but fail in another, or to work on one robot but fail with another.

We introduced SMT-based Robot Transition Repair (SRTR) [Holtz et al., ], an approach to adjusting the parameters of robot state machines using sparse, partial specifications of corrections from humans. During execution, we log execution traces of the transition function. After execution, the human examines the execution trace and corrects a handful of transitions as needed. SRTR then takes as input the transition function source code, the trace, and the corrections, and produces adjustments to the parameter values in three major steps. 1) It parses the transition function code and converts it to an abstract syntax tree for repair. 2) It uses a lightweight program analysis to identify parameters that cannot be repaired, and for each user-provided correction, it partially evaluates the transition function for the inputs and variable values at the time of correction, yielding residual transition functions. 3) Finally, it uses the residual transition functions to formulate an optimization problem for an off-the-shelf MaxSMT solver [Bjørner et al., 2015]. The solution to this problem is an adjustment to the parameter values that satisfies as many human corrections as possible while simultaneously minimizing adjustments to the parameters.

The full paper for SRTR [Holtz et al., ] includes extensive empirical results demonstrating that SRTR 1) finds parameter adjustments fast; 2) produces adjustments that perform as well as those found by exhaustive search; 3) finds adjustments that generalize to new scenarios; and 4) outperforms a domain-expert at repairing state machines.

6 Discussion and Conclusion

In this paper, we presented our research towards the ultimate goal of "always on" autonomous mobile robots in everyday human environments. While significant progress has been made towards this goal, it still remains elusive. There are many topics of active research in support of this goal. On the topic of long-term mapping and localization, there is growing interest in using semantic-level understanding of environments to reason about changes in the world. Simultaneously, competency-aware machine learning and adversarial machine learning are promising areas of research with the aim of accounting for, predicting, and overcoming inevitable errors made by autonomous systems, including robots. Finally, there is considerable interest in programming and correcting robots through non-technical means of input, including interactions with novice users. We are excited to contribute to, and support the exciting new developments along these directions and others in support of long-term autonomy.

Acknowledgements

I would like to thank my collaborators and mentors, including Manuela Veloso, Reid Simmons, Arjun Guha, and Shlomo Zilberstein - and also my students Samer Nashed, Jarrett Holtz, Sadegh Rabiee, Kyle Vedder, Spencer Lane, Sourish Ghosh, David Balaban, Alyxander Burns, and Emily Pruc. This work was partially supported by AFRL and DARPA under agreement #FA8750-16-2-0042, and by NSF award IIS1724101.