Nicholas Roy

ICRA Conference 2025 Conference Paper

Anomalies-by-Synthesis: Anomaly Detection using Generative Diffusion Models for Off-Road Navigation

• Sunshine Jiang
• Siddharth Ancha
• Travis Manderson
• Laura Brandt
• Yilun Du
• Philip R. Osteen
• Nicholas Roy

In order to navigate safely and reliably in off-road and unstructured environments, robots must detect anomalies that are out-of-distribution (OOD) with respect to the training data. We present an analysis-by-synthesis approach for pixel-wise anomaly detection without making any assumptions about the nature of OOD data. Given an input image, we use a generative diffusion model to synthesize an edited image that removes anomalies while keeping the remaining image unchanged. Then, we formulate anomaly detection as analyzing which image segments were modified by the diffusion model. We propose a novel inference approach for guided diffusion by analyzing the ideal guidance gradient and deriving a principled approximation that bootstraps the diffusion model to predict guidance gradients. Our editing technique is purely test-time that can be integrated into existing workflows without the need for retraining or fine-tuning. Finally, we use a combination of vision-language foundation models to compare pixels in a learned feature space and detect semantically meaningful edits, enabling accurate anomaly detection for off-road navigation.

ICRA Conference 2025 Conference Paper

Belief Roadmaps with Uncertain Landmark Evanescence

• Erick Fuentes
• Jared Strader
• Ethan Fahnestock
• Nicholas Roy

We would like a robot to navigate to a goal location while minimizing state uncertainty. To aid the robot in this endeavor, maps provide a prior belief over the location of objects and regions of interest. To localize itself within the map, a robot identifies mapped landmarks using its sensors. However, as the time between map creation and robot deployment increases, portions of the map can become stale, and landmarks, once believed to be permanent, may disappear. We refer to the propensity of a landmark to disappear as landmark evanescence. Reasoning about landmark evanescence during path planning, and the associated impact on localization accuracy, requires analyzing the presence or absence of each landmark, leading to an exponential number of possible outcomes of a given motion plan. To address this complexity, we develop BRULE, an extension of the Belief Roadmap. During planning, we replace the belief over future robot poses with a Gaussian mixture which is able to capture the effects of landmark evanescence. Furthermore, we show that belief updates can be made efficient, and that maintaining a random subset of mixture components is sufficient to find high quality solutions. We demonstrate performance in simulated and real-world experiments. Software is available at https://bit.ly/BRULE.

IROS Conference 2024 Conference Paper

Adaptive multi-altitude search and sampling of sparsely distributed natural phenomena

• Jessica E. Todd
• Seth McCammon
• Yogesh A. Girdhar
• Nicholas Roy
• Dana R. Yoerger

In this paper, we propose a novel method for autonomously seeking out sparsely distributed targets in an unknown underwater environment. Our Sparse Adaptive Search and Sample (SASS) algorithm mixes low-altitude observations of discrete targets with high-altitude observations of the surrounding substrates. By using prior information about the distribution of targets across substrate types in combination with belief modelling over these substrates in the environment, high-altitude observations provide information that allows SASS to quickly guide the robot to areas with high target densities. A maximally informative path is autonomously constructed online using Monte Carlo Tree Search with a novel acquisition function to guide the search to maximise observations of unique targets. We demonstrate our approach in a set of simulated trials using a novel generative species model. SASS consistently outperforms the canonical boustrophedon planner by up to 36% in seeking out unique targets in the first 75-90% of time it takes for a boustrophedon survey. Additionally, we verify the performance of SASS on two real world coral reef datasets.

ICRA Conference 2024 Conference Paper

Amortized Inference for Efficient Grasp Model Adaptation

• Michael Noseworthy
• Seiji Shaw
• Chad C. Kessens
• Nicholas Roy

In robotic applications such as bin-picking or block-stacking, learned predictive models have been developed for manipulation of objects with varying but known dynamic properties (e. g. , mass distributions and friction coefficients). When a robot encounters a new object, these properties are often difficult to observe and must be inferred through interaction, which can be expensive in both inference time and number of interactions. We propose an encoder/decoder action-feasibility model to efficiently adapt to new objects by estimating their unobserved properties through interaction. The encoder predicts a distribution over the unobserved parameters while the decoder predicts action feasibility, which can be used in an uncertainty-aware planner. An explicit representation of uncertainty in the encoder enables information-gathering heuristics to minimize adaptation interactions. The amortized distributions are efficient to compute and perform comparably to particle-based distributions in a grasping domain. Finally, we deploy our method on a Panda robot to grasp heavy objects.

ICRA Conference 2024 Conference Paper

AutoTAMP: Autoregressive Task and Motion Planning with LLMs as Translators and Checkers

• Yongchao Chen
• Jacob Arkin
• Charles Dawson 0001
• Yang Zhang 0001
• Nicholas Roy
• Chuchu Fan

For effective human-robot interaction, robots need to understand, plan, and execute complex, long-horizon tasks described by natural language. Recent advances in large language models (LLMs) have shown promise for translating natural language into robot action sequences for complex tasks. However, existing approaches either translate the natural language directly into robot trajectories or factor the inference process by decomposing language into task sub-goals and relying on a motion planner to execute each sub-goal. When complex environmental and temporal constraints are involved, inference over planning tasks must be performed jointly with motion plans using traditional task-and-motion planning (TAMP) algorithms, making factorization into subgoals untenable. Rather than using LLMs to directly plan task sub-goals, we instead perform few-shot translation from natural language task descriptions to an intermediate task representation that can then be consumed by a TAMP algorithm to jointly solve the task and motion plan. To improve translation, we automatically detect and correct both syntactic and semantic errors via autoregressive re-prompting, resulting in significant improvements in task completion. We show that our approach outperforms several methods using LLMs as planners in complex task domains. See our project website § for prompts, videos, and code.

ICRA Conference 2024 Conference Paper

Deep Evidential Uncertainty Estimation for Semantic Segmentation under Out-Of-Distribution Obstacles

• Siddharth Ancha
• Philip R. Osteen
• Nicholas Roy

In order to navigate safely and reliably in novel environments, robots must estimate perceptual uncertainty when confronted with out-of-distribution (OOD) obstacles not seen in training data. We present a method to accurately estimate pixel-wise uncertainty in semantic segmentation without requiring real or synthetic OOD examples at training time. From a shared per-pixel latent feature representation, a classification network predicts a categorical distribution over semantic labels, while a normalizing flow estimates the probability density of features under the training distribution. The label distribution and density estimates are combined in a Dirichlet-based evidential uncertainty framework that efficiently computes epistemic and aleatoric uncertainty in a single neural network forward pass. Our method is enabled by three key contributions. First, we simplify the problem of learning a transformation to the training data density by starting from a fitted Gaussian mixture model instead of the conventional standard normal distribution. Second, we learn a richer and more expressive latent pixel representation to aid OOD detection by training a decoder to reconstruct input image patches. Third, we perform theoretical analysis of the loss function used in the evidential uncertainty framework and propose a principled objective that more accurately balances training the classification and density estimation networks. We demonstrate the accuracy of our uncertainty estimation approach under long-tail OOD obstacle classes for semantic segmentation in both off-road and urban driving environments.

ICRA Conference 2024 Conference Paper

Generating Sparse Probabilistic Graphs for Efficient Planning in Uncertain Environments

• Yasmin Veys
• Martina Stadler
• Nicholas Roy

Environments with regions of uncertain traversability can be modeled as roadmaps with probabilistic edges for efficient planning under uncertainty. We would like to generate roadmaps that enable planners to efficiently find paths with expected low costs through uncertain environments. The roadmap must be sparse so that the planning problem is tractable, but still contain edges that are likely to contribute to low-cost plans under various realizations of the environmental uncertainty. Determining the optimal set of edges to add to the roadmap without considering an exponential number of traversability scenarios is challenging. We propose the use of a heuristic that bounds the ratio between the expected path cost in our graph and the expected path cost in an optimal graph to determine whether a given edge should be added to the roadmap. We test our approach in several environments, demonstrating that our uncertainty-aware roadmaps effectively trade off between plan quality and planning efficiency for uncertainty-aware agents navigating in the graph.

ICRA Conference 2024 Conference Paper

How to Train Your Neural Control Barrier Function: Learning Safety Filters for Complex Input-Constrained Systems

• Oswin So
• Zachary T. Serlin
• Makai Mann
• Jake Gonzales
• Kwesi Rutledge
• Nicholas Roy
• Chuchu Fan

Control barrier functions (CBFs) have become popular as a safety filter to guarantee the safety of nonlinear dynamical systems for arbitrary inputs. However, it is difficult to construct functions that satisfy the CBF constraints for high relative degree systems with input constraints. To address these challenges, recent work has explored learning CBFs using neural networks via neural CBFs (NCBFs). However, such methods face difficulties when scaling to higher dimensional systems under input constraints. In this work, we first identify challenges that NCBFs face during training. Next, to address these challenges, we propose policy neural CBFs (PNCBFs), a method of constructing CBFs by learning the value function of a nominal policy, and show that the value function of the maximum-over-time cost is a CBF. We demonstrate the effectiveness of our method in simulation on a variety of systems ranging from toy linear systems to a jet aircraft with a 16-dimensional state space. Finally, we validate our approach on a two-agent quadcopter system on hardware under tight input constraints.

ICRA Conference 2024 Conference Paper

Scalable Multi-Robot Collaboration with Large Language Models: Centralized or Decentralized Systems?

• Yongchao Chen
• Jacob Arkin
• Yang Zhang 0001
• Nicholas Roy
• Chuchu Fan

A flurry of recent work has demonstrated that pre-trained large language models (LLMs) can be effective task planners for a variety of single-robot tasks. The planning performance of LLMs is significantly improved via prompting techniques, such as in-context learning or re-prompting with state feedback, placing new importance on the token budget for the context window. An under-explored but natural next direction is to investigate LLMs as multi-robot task planners. However, long-horizon, heterogeneous multi-robot planning introduces new challenges of coordination while also pushing up against the limits of context window length. It is therefore critical to find token-efficient LLM planning frameworks that are also able to reason about the complexities of multi-robot coordination. In this work, we compare the task success rate and token efficiency of four multi-agent communication frameworks (centralized, decentralized, and two hybrid) as applied to four coordination-dependent multi-agent 2D task scenarios for increasing numbers of agents. We find that a hybrid framework achieves better task success rates across all four tasks and scales better to more agents. We further demonstrate the hybrid frameworks in 3D simulations where the vision-to-text problem and dynamical errors are considered. See our project website 4 for prompts, videos, and code.

ICAPS Conference 2023 Conference Paper

Approximating the Value of Collaborative Team Actions for Efficient Multiagent Navigation in Uncertain Graphs

• Martina Stadler
• Jacopo Banfi
• Nicholas Roy

For a team of collaborative agents navigating through an unknown environment, collaborative actions such as sensing the traversability of a route can have a large impact on aggregate team performance. However, planning over the full space of joint team actions is generally computationally intractable. Furthermore, typically only a small number of collaborative actions is useful for a given team task, but it is not obvious how to assess the usefulness of a given action. In this work, we model collaborative team policies on stochastic graphs using macro-actions, where each macro-action for a given agent can consist of a sequence of movements, sensing actions, and actions of waiting to receive information from other agents. To reduce the number of macro-actions considered during planning, we generate optimistic approximations of candidate future team states, then restrict the planning domain to a small policy class which consists of only macro-actions which are likely to lead to high-reward future team states. We optimize team plans over the small policy class, and demonstrate that the approach enables a team to find policies which actively balance between reducing task-relevant environmental uncertainty and efficiently navigating to goals in toy graph and island road network domains, finding better plans than policies that do not act to reduce environmental uncertainty.

ICRA Conference 2022 Conference Paper

A Hierarchical Deliberative-Reactive System Architecture for Task and Motion Planning in Partially Known Environments

• Vasileios Vasilopoulos
• Sebastian Castro
• William Vega-Brown
• Daniel E. Koditschek
• Nicholas Roy

We describe a task and motion planning architecture for highly dynamic systems that combines a domain-independent sampling-based deliberative planning algorithm with a global reactive planner. We leverage the recent development of a reactive, vector field planner that provides guarantees of reachability to large regions of the environment even in the face of unknown or unforeseen obstacles. The reachability guarantees can be formalized using contracts that allow a deliberative planner to reason purely in terms of those contracts and synthesize a plan by choosing a sequence of reactive behaviors and their target configurations, without evaluating specific motion plans between targets. This reduces both the search depth at which plans will be found, and the number of samples required to ensure a plan exists, while crucially preserving correctness guarantees. The result is reduced computational cost of synthesizing plans, and increased robustness of generated plans to actuator noise, model misspecification, or unknown obstacles. Simulation studies show that our hierarchical planning and execution architecture can solve complex navigation and rearrangement tasks, even when faced with narrow passageways or incomplete world information.

ICRA Conference 2021 Conference Paper

Hierarchical Object Map Estimation for Efficient and Robust Navigation

• Kyel Ok
• Katherine Liu
• Nicholas Roy

We propose a hierarchical representation of objects, where the representation of each object is allowed to change based on the quality of accumulated measurements. We initially estimate each object as a 2D bounding box or a 3D point, encoding only the geometric properties that can be well-constrained using limited viewpoints. With additional measurements, we allow each object to become a higher dimensional 3D volumetric model for improved reconstruction accuracy and collision-testing. Our Hierarchical Object Map Estimation (HOME) is robust to deficiencies in viewpoints and allows planning safe and efficient trajectories around object obstacles using a monocular camera. We demonstrate the advantages of our approach on a real-world TUM dataset and during visual-inertial navigation of a quad-rotor in simulation.

ICRA Conference 2021 Conference Paper

Learning and Planning for Temporally Extended Tasks in Unknown Environments

• Christopher Bradley
• Adam Pacheck
• Gregory J. Stein
• Sebastian Castro
• Hadas Kress-Gazit
• Nicholas Roy

We propose a novel planning technique for satisfying tasks specified in temporal logic in partially revealed environments. We define high-level actions derived from the environment and the given task itself, and estimate how each action contributes to progress towards completing the task. As the map is revealed, we estimate the cost and probability of success of each action from images and an encoding of that action using a trained neural network. These estimates guide search for the minimum-expected-cost plan within our model. Our learned model is structured to generalize across environments and task specifications without requiring retraining. We demonstrate an improvement in total cost in both simulated and real-world experiments compared to a heuristic-driven baseline.

ICRA Conference 2021 Conference Paper

MultiViewStereoNet: Fast Multi-View Stereo Depth Estimation using Incremental Viewpoint-Compensated Feature Extraction

• W. Nicholas Greene
• Nicholas Roy

We propose a novel learning-based method for multi-view stereo (MVS) depth estimation capable of recovering depth from images taken from known, but unconstrained, views. Existing MVS methods extract features from each image independently before projecting them onto a set of planes at candidate depths to compute matching costs. By projecting features after extraction, networks must learn rotation and scale invariant representations even though the relative poses of the cameras are known. In our approach, we compensate for viewpoint changes directly in the extraction layers, allowing the network to learn features that are projected by construction and reducing the need for rotation and scale invariance. Compensating for viewpoint changes naively, however, can be computationally expensive as the feature layers must either be applied multiple times (once per depth hypothesis), or replaced by 3D convolutions. We overcome this limitation in two ways. First, we only compute our matching cost volume at a coarse image scale before upsampling and refining the outputs. Second, we incrementally compute our projected features such that the bulk of the layers need only be executed a single time across all depth hypotheses. The combination of these two techniques allows our method to perform competitively with the state-of-the-art, while being significantly faster. We call our method MultiViewStereoNet and release our source code publicly for the benefit of the robotics community.

IROS Conference 2021 Conference Paper

Online High-Level Model Estimation for Efficient Hierarchical Robot Navigation

• Martina Stadler
• Katherine Liu
• Nicholas Roy

We would like to enable a robot to navigate efficiently and robustly in known, structured environments that are large enough to cause traditional planning approaches to incur considerable computational cost. Hierarchical planners are a promising way to increase planning efficiency in such environments because high-level abstract plans can be used to reduce the size of the search space over which detailed planning occurs. However, useful high-level representations of planning problems can be challenging to generate without prior domain knowledge. In this work, we propose a high-level planning representation which can be learned from previous plans considered in the environment and used online during hierarchical, multi-query robot navigation. We treat previous planning results as noisy measurements of high-level navigation properties, then update these properties over time using recursive estimation. We test our approach in standard and risk-aware hierarchical planning schemes, and demonstrate up to an 86% decrease in the number of nodes expanded and a 66% decrease in wallclock time as compared to a baseline A* planner while finding plans that are only 2-10% more expensive.

ICRA Conference 2021 Conference Paper

Reactive Task and Motion Planning under Temporal Logic Specifications

• Shen Li 0003
• Daehyung Park
• Yoonchang Sung
• Julie Shah
• Nicholas Roy

We present a task-and-motion planning (TAMP) algorithm robust against a human operator's cooperative or adversarial interventions. Interventions often invalidate the current plan and require replanning on the fly. Replanning can be computationally expensive and often interrupts seamless task execution. We introduce a dynamically reconfigurable planning methodology with behavior tree-based control strategies toward reactive TAMP, which takes the advantage of previous plans and incremental graph search during temporal logic-based reactive synthesis. Our algorithm also shows efficient recovery functionalities that minimize the number of replanning steps. Finally, our algorithm produces a robust, efficient, and complete TAMP solution. Our experimental results show the algorithm results in superior manipulation performance in both simulated and real-world tasks.

ICRA Conference 2021 Conference Paper

Toward Robust and Efficient Online Adaptation for Deep Stereo Depth Estimation

• Milo Knowles
• Valentin Peretroukhin
• W. Nicholas Greene
• Nicholas Roy

Although deep neural networks have achieved state-of-the-art performance for stereo depth estimation, they can suffer from a significant drop in accuracy when tested on images from novel domains. Recent work has shown that self-supervised online adaptation is a promising approach for closing this performance gap. In this work, we address three unsolved challenges for online adaptation. First, we propose a method for detecting novel environments, allowing us to trigger adaptation and notify downstream systems that depth predictions are unreliable. We find that the feature similarity scores from our deep stereo network can be leveraged for out-of-distribution (OOD) detection, providing the necessary starting criterion for adaptation. Next, we use online validation to terminate adaptation when it stops improving performance, allowing us to free up computational resources. Finally, we demonstrate that existing methods for continuous adaptation cause catastrophic forgetting of the training domain. By augmenting adaptation with experience replay, we retain high accuracy in the training domain while rapidly improving performance in novel environments. In sum, these three contributions form the basis of a more robust and efficient deep stereo system that can recognize and adapt to new environments without forgetting.

IROS Conference 2021 Conference Paper

VoluMon: Weakly-Supervised Volumetric Monocular Estimation with Ellipsoid Representations

• Katherine Liu
• Kyel Ok
• Nicholas Roy

Deep learning approaches to estimating 3D object pose and geometry present an attractive alternative to online estimation techniques, which can suffer from significant estimation latency. However, a practical hurdle to training state-of-the-art deep 3D bounding box estimators is collecting a sufficiently large dataset of 3D bounding box labels. In this work, we present a novel framework for weakly supervised volumetric monocular estimation (VoluMon) that requires annotations in the image space only, i. e. , associated object bounding box detections and instance segmentation. By approximating object geometry as ellipsoids, we can exploit the dual form of the ellipsoid to optimize with respect to bounding box annotations and the primal form of the ellipsoid to optimize with respect to a segmented pointcloud. For a simulated dataset with access to ground-truth, we show monocular object estimation performance similar to a naive online depth based estimation approach and after online refinement when depth images are available, we also approach the performance of a learned deep 6D pose estimator, which is supervised with projected 3D bounding box keypoints and assumes known model dimensions. Finally, we show promising qualitative results generated from a real-world dataset collected using a stereo pair.

ICRA Conference 2020 Conference Paper

Enabling Topological Planning with Monocular Vision

• Gregory J. Stein
• Christopher Bradley
• Victoria Preston
• Nicholas Roy

Topological strategies for navigation meaningfully reduce the space of possible actions available to a robot, allowing use of heuristic priors or learning to enable computationally efficient, intelligent planning. The challenges in estimating structure with monocular SLAM in low texture or highly cluttered environments have precluded its use for topological planning in the past. We propose a robust sparse map representation that can be built with monocular vision and overcomes these shortcomings. Using a learned sensor, we estimate high-level structure of an environment from streaming images by detecting sparse "vertices" (e. g. , boundaries of walls) and reasoning about the structure between them. We also estimate the known free space in our map, a necessary feature for planning through previously unknown environments. We show that our mapping technique can be used on real data and is sufficient for planning and exploration in simulated multi-agent search and learned subgoal planning applications.

ICRA Conference 2020 Conference Paper

Learned Sampling Distributions for Efficient Planning in Hybrid Geometric and Object-Level Representations

• Katherine Liu
• Martina Stadler
• Nicholas Roy

We would like to enable a robotic agent to quickly and intelligently find promising trajectories through structured, unknown environments. Many approaches to navigation in unknown environments are limited to considering geometric information only, which leads to myopic behavior. In this work, we show that learning a sampling distribution that incorporates both geometric information and explicit, object-level semantics for sampling-based planners enables efficient planning at longer horizons in partially-known environments. We demonstrate that our learned planner is up to 2. 7 times more likely to find a plan than the baseline, and can result in up to a 16% reduction in traversal costs as calculated by linear regression. We also show promising qualitative results on real-world data.

ICRA Conference 2020 Conference Paper

Metrically-Scaled Monocular SLAM using Learned Scale Factors

• W. Nicholas Greene
• Nicholas Roy

We propose an efficient method for monocular simultaneous localization and mapping (SLAM) that is capable of estimating metrically-scaled motion without additional sensors or hardware acceleration by integrating metric depth predictions from a neural network into a geometric SLAM factor graph. Unlike learned end-to-end SLAM systems, ours does not ignore the relative geometry directly observable in the images. Unlike existing learned depth estimation approaches, ours leverages the insight that when used to estimate scale, learned depth predictions need only be coarse in image space. This allows us to shrink our network to the point that performing inference on a standard CPU becomes computationally tractable. We make several improvements to our network architecture and training procedure to address the lack of depth observability when using coarse images, which allows us to estimate spatially coarse, but depth-accurate predictions in only 30 ms per frame without GPU acceleration. At runtime we incorporate the learned metric data as unary scale factors in a Sim(3) pose graph. Our method is able to generate accurate, scaled poses without additional sensors, hardware accelerators, or special maneuvers and does not ignore or corrupt the observable epipolar geometry. We show compelling results on the KITTI benchmark dataset in addition to real-world experiments with a handheld camera.

AAAI Conference 2020 Conference Paper

Task and Motion Planning Is PSPACE-Complete

• William Vega-Brown
• Nicholas Roy

We present a new representation for task and motion planning that uses constraints to capture both continuous and discrete phenomena in a unified framework. We show that we can decide if a feasible plan exists for a given problem instance using only polynomial space if the constraints are semialgebraic and all actions have uniform stratified accessibility, a technical condition closely related to both controllability and to the existence of a symbolic representation of a planning domain. We show that there cannot exist an algorithm that solves the more general problem of deciding if a plan exists for an instance with arbitrary semialgebraic constraints. Finally, we show that our formalism is universal, in the sense that every deterministic robotic planning problem can be well-approximated within our formalism. Together, these results imply task and motion planning is PSPACEcomplete.

ICRA Conference 2020 Conference Paper

Visual Prediction of Priors for Articulated Object Interaction

• Caris Moses
• Michael Noseworthy
• Leslie Pack Kaelbling
• Tomás Lozano-Pérez
• Nicholas Roy

Exploration in novel settings can be challenging without prior experience in similar domains. However, humans are able to build on prior experience quickly and efficiently. Children exhibit this behavior when playing with toys. For example, given a toy with a yellow and blue door, a child will explore with no clear objective, but once they have discovered how to open the yellow door, they will most likely be able to open the blue door much faster. Adults also exhibit this behaviour when entering new spaces such as kitchens. We develop a method, Contextual Prior Prediction, which provides a means of transferring knowledge between interactions in similar domains through vision. We develop agents that exhibit exploratory behavior with increasing efficiency, by learning visual features that are shared across environments, and how they correlate to actions. Our problem is formulated as a Contextual Multi-Armed Bandit where the contexts are images, and the robot has access to a parameterized action space. Given a novel object, the objective is to maximize reward with few interactions. A domain which strongly exhibits correlations between visual features and motion is kinemetically constrained mechanisms. We evaluate our method on simulated prismatic and revolute joints 1.

RLDM Conference 2019 Conference Abstract

Joint Goal and Constraint Inference using Bayesian Nonparametric Inverse Reinforcement Learning

• Daehyung Park
• Michael Noseworthy
• Rohan Paul
• Subhro Roy
• Nicholas Roy

Inverse Reinforcement Learning (IRL) aims to recover an unknown reward function from expert demonstrations of a task. Often, the reward function fails to capture a complex behavior (e. g. , a condi- tion or a constraint) due to the simple structure of the global reward function. We introduce an algorithm, Constraint-based Bayesian Non-Parametric Inverse Reinforcement Learning (CBN-IRL), that instead repre- sents a task as a sequence of subtasks, each consisting of a goal and set of constraints, by partitioning a single demonstration into individual trajectory segments. CBN-IRL is able to find locally consistent constraints and adapt the number of subtasks according to the complexity of the demonstration using a computationally efficient inference process. We evaluate the proposed framework on two-dimensional simulation environ- ments. The results show our framework outperforms state-of-the-art IRL on a complex demonstration. We also show we can adapt the learned subgoals and constraints to randomized test environments given a single demonstration.

ICRA Conference 2019 Conference Paper

Robust Object-based SLAM for High-speed Autonomous Navigation

• Kyel Ok
• Katherine Liu
• Kristoffer M. Frey
• Jonathan P. How
• Nicholas Roy

We present Robust Object-based SLAM for High-speed Autonomous Navigation (ROSHAN), a novel approach to object-level mapping suitable for autonomous navigation. In ROSHAN, we represent objects as ellipsoids and infer their parameters using three sources of information - bounding box detections, image texture, and semantic knowledge - to overcome the observability problem in ellipsoid-based SLAM under common forward-translating vehicle motions. Each bounding box provides four planar constraints on an object surface and we add a fifth planar constraint using the texture on the objects along with a semantic prior on the shape of ellipsoids. We demonstrate ROSHAN in simulation where we outperform the baseline, reducing the median shape error by 83% and the median position error by 72% in a forward-moving camera sequence. We demonstrate similar qualitative result on data collected on a fast-moving autonomous quadrotor.

IJCAI Conference 2018 Conference Paper

Admissible Abstractions for Near-optimal Task and Motion Planning

• William Vega-Brown
• Nicholas Roy

We define an admissibility condition for abstractions expressed using angelic semantics and show that these conditions allow us to accelerate planning while preserving the ability to find the optimal motion plan. We then derive admissible abstractions for two motion planning domains with continuous state. We extract upper and lower bounds on the cost of concrete motion plans using local metric and topological properties of the problem domain. These bounds guide the search for a plan while maintaining performance guarantees. We show that abstraction can dramatically reduce the complexity of search relative to a direct motion planner. Using our abstractions, we find near-optimal motion plans in planning problems involving 10^13 states without using a separate task planner.

IROS Conference 2018 Conference Paper

Approximate Distributed Spatiotemporal Topic Models for Multi-Robot Terrain Characterization

• Kevin J. Doherty 0001
• Genevieve Flaspohler
• Nicholas Roy
• Yogesh A. Girdhar

Unsupervised learning techniques, such as Bayesian topic models, are capable of discovering latent structure directly from raw data. These unsupervised models can endow robots with the ability to learn from their observations without human supervision, and then use the learned models for tasks such as autonomous exploration, adaptive sampling, or surveillance. This paper extends single-robot topic models to the domain of multiple robots. The main difficulty of this extension lies in achieving and maintaining global consensus among the unsupervised models learned locally by each robot. This is especially challenging for multi-robot teams operating in communication-constrained environments, such as marine robots. We present a novel approach for multi-robot distributed learning in which each robot maintains a local topic model to categorize its observations and model parameters are shared to achieve global consensus. We apply a combinatorial optimization procedure that combines local robot topic distributions into a globally consistent model based on topic similarity, which we find mitigates topic drift when compared to a baseline approach that matches topics naïvely, We evaluate our methods experimentally by demonstrating multi-robot underwater terrain characterization using simulated missions on real seabed imagery. Our proposed method achieves similar model quality under bandwidth-constraints to that achieved by models that continuously communicate, despite requiring less than one percent of the data transmission needed for continuous communication.

ICRA Conference 2018 Conference Paper

Deep Inference for Covariance Estimation: Learning Gaussian Noise Models for State Estimation

• Katherine Liu
• Kyel Ok
• William Vega-Brown
• Nicholas Roy

We present a novel method of measurement covariance estimation that models measurement uncertainty as a function of the measurement itself. Existing work in predictive sensor modeling outperforms conventional fixed models, but requires domain knowledge of the sensors that heavily influences the accuracy and the computational cost of the models. In this work, we introduce Deep Inference for Covariance Estimation (DICE), which utilizes a deep neural network to predict the covariance of a sensor measurement from raw sensor data. We show that given pairs of raw sensor measurement and ground-truth measurement error, we can learn a representation of the measurement model via supervised regression on the prediction performance of the model, eliminating the need for hand-coded features and parametric forms. Our approach is sensor-agnostic, and we demonstrate improved covariance prediction on both simulated and real data.

NeurIPS Conference 2018 Conference Paper

Efficient inference for time-varying behavior during learning

• Nicholas Roy
• Ji Hyun Bak
• Athena Akrami
• Carlos Brody
• Jonathan Pillow

The process of learning new behaviors over time is a problem of great interest in both neuroscience and artificial intelligence. However, most standard analyses of animal training data either treat behavior as fixed or track only coarse performance statistics (e. g. , accuracy, bias), providing limited insight into the evolution of the policies governing behavior. To overcome these limitations, we propose a dynamic psychophysical model that efficiently tracks trial-to-trial changes in behavior over the course of training. Our model consists of a dynamic logistic regression model, parametrized by a set of time-varying weights that express dependence on sensory stimuli as well as task-irrelevant covariates, such as stimulus, choice, and answer history. Our implementation scales to large behavioral datasets, allowing us to infer 500K parameters (e. g. 10 weights over 50K trials) in minutes on a desktop computer. We optimize hyperparameters governing how rapidly each weight evolves over time using the decoupled Laplace approximation, an efficient method for maximizing marginal likelihood in non-conjugate models. To illustrate performance, we apply our method to psychophysical data from both rats and human subjects learning a delayed sensory discrimination task. The model successfully tracks the psychophysical weights of rats over the course of training, capturing day-to-day and trial-to-trial fluctuations that underlie changes in performance, choice bias, and dependencies on task history. Finally, we investigate why rats frequently make mistakes on easy trials, and suggest that apparent lapses can be explained by sub-optimal weighting of known task covariates.

ICRA Conference 2018 Conference Paper

Efficient Planning for Near-Optimal Compliant Manipulation Leveraging Environmental Contact

• Charlie Guan
• William Vega-Brown
• Nicholas Roy

Path planning classically focuses on avoiding environmental contact. However, some assembly tasks permit contact through compliance, and such contact may allow for more efficient and reliable solutions under action uncertainty. But, optimal manipulation plans that leverage environmental contact are difficult to compute. Environmental contact produces complex kinematics that create difficulties for planning. This complexity is usually addressed by discretization over state and action space, but discretization quickly becomes computationally intractable. To overcome the challenge, we use the insight that only actions on configurations near the contact manifold are likely to involve complex kinematics, while segments of the plan through free space do not. Leveraging this structure can greatly reduce the number of states considered and scales much better with problem complexity. We develop an algorithm based on this idea and show that it performs comparably to full MDP solutions at a fraction of the computational cost.

ICRA Conference 2018 Conference Paper

GeneSIS-Rt: Generating Synthetic Images for Training Secondary Real-World Tasks

• Gregory J. Stein
• Nicholas Roy

We propose a novel approach for generating high-quality, synthetic data for domain-specific learning tasks, for which training data may not be readily available. We leverage recent progress in image-to-image translation to bridge the gap between simulated and real images, allowing us to generate realistic training data for real-world tasks using only unlabeled real-world images and a simulation. GeneSIS-Rtameliorates the burden of having to collect labeled real-world images and is a promising candidate for generating high-quality, domain-specific, synthetic data. To show the effectiveness of using GeneSIS-Rtto create training data, we study two tasks: semantic segmentation and reactive obstacle avoidance. We demonstrate that learning algorithms trained using data generated by GeneSIS-RT make high-accuracy predictions and outperform systems trained on raw simulated data alone, and as well or better than those trained on real data. Finally, we use our data to train a quadcopter to fly 60 meters at speeds up to 3. 4 m/s through a cluttered environment, demonstrating that our GeneSIS-RT images can be used to learn to perform mission-critical tasks.

ICRA Conference 2018 Conference Paper

Near-optimal Irrevocable Sample Selection for Periodic Data Streams with Applications to Marine Robotics

• Genevieve Flaspohler
• Nicholas Roy
• Yogesh A. Girdhar

We consider the task of monitoring spatiotemporal phenomena in real-time by deploying limited sampling resources at locations of interest irrevocably and without knowledge of future observations. This task can be modeled as an instance of the classical secretary problem. Although this problem has been studied extensively in theoretical domains, existing algorithms require that data arrive in random order to provide performance guarantees. These algorithms will perform arbitrarily poorly on data streams such as those encountered in robotics and environmental monitoring domains, which tend to have spatiotemporal structure. We focus on the problem of selecting representative samples from phenomena with periodic structure and introduce a novel sample selection algorithm that recovers a near-optimal sample set according to any monotone submodular utility function. We evaluate our algorithm on a seven-year environmental dataset collected at the Martha's Vineyard Coastal Observatory and show that it selects phytoplankton sample locations that are nearly optimal in an information-theoretic sense for predicting phytoplankton concentrations in locations that were not directly sampled. The proposed periodic secretary algorithm can be used with theoretical performance guarantees in many real-time sensing and robotics applications for streaming, irrevocable sample selection from periodic data streams.

IROS Conference 2018 Conference Paper

Sensor-Based Reactive Execution of Symbolic Rearrangement Plans by a Legged Mobile Manipulator

• Vasileios Vasilopoulos
• T. Turner Topping
• William Vega-Brown
• Nicholas Roy
• Daniel E. Koditschek

We demonstrate the physical rearrangement of wheeled stools in a moderately cluttered indoor environment by a quadrupedal robot that autonomously achieves a user's desired configuration. The robot's behaviors are planned and executed by a three layer hierarchical architecture consisting of: an offline symbolic task and motion planner; a reactive layer that tracks the reference output of the deliberative layer and avoids unanticipated obstacles sensed online; and a gait layer that realizes the abstract unicycle commands from the reactive module through appropriately coordinated joint level torque feedback loops. This work also extends prior formal results about the reactive layer to a broad class of nonconvex obstacles. Our design is verified both by formal proofs as well as empirical demonstration of various assembly tasks.

ICRA Conference 2018 Conference Paper

Sensor-Based Reactive Symbolic Planning in Partially Known Environments

• Vasileios Vasilopoulos
• William Vega-Brown
• Ömür Arslan
• Nicholas Roy
• Daniel E. Koditschek

This paper considers the problem of completing assemblies of passive objects in nonconvex environments, cluttered with convex obstacles of unknown position, shape and size that satisfy a specific separation assumption. A differential drive robot equipped with a gripper and a LIDAR sensor, capable of perceiving its environment only locally, is used to position the passive objects in a desired configuration. The method combines the virtues of a deliberative planner generating high-level, symbolic commands, with the formal guarantees of convergence and obstacle avoidance of a reactive planner that requires little onboard computation and is used online. The validity of the proposed method is verified both with formal proofs and numerical simulations.

RLDM Conference 2017 Conference Abstract

Efficient asymptotically optimal planning with discontinuous dynamics

• William Vega-Brown
• Nicholas Roy

We address the problem of approximately optimal planning for problems with discontinuous or non-analytic dynamics, a broad and important class of problems that includes contact-based manipulation and legged locomotion. Problems of this type are challenging because discontinuities in the dynamics make conventional motion planning algorithms ineffective. In addition, problems involving many objects are computationally challenging due to the high dimensionality of their configuration space. We show that given the ability to sample from the locally reachable subset of the configuration space with positive probability, we can construct random geometric graphs that contain optimal plans with probability one in the limit of infinite samples. We describe an approach that exploits this graph construction, and demonstrate our approach in simulation on a simple manipulation planning problem. We find it generates lower-cost plans than a conventional task and motion planning approach, but is computationally intractable for problems involving more than a few objects. We then propose an extension that incorporates abstraction using angelic semantics, which may render larger problems computationally feasible.

IROS Conference 2017 Conference Paper

Feature discovery and visualization of robot mission data using convolutional autoencoders and Bayesian nonparametric topic models

• Genevieve Flaspohler
• Nicholas Roy
• Yogesh A. Girdhar

The gap between our ability to collect interesting data and our ability to analyze these data is growing at an unprecedented rate. Recent algorithmic attempts to fill this gap have employed unsupervised tools to discover structure in data. Some of the most successful approaches have used probabilistic models to uncover latent thematic structure in discrete data. Despite the success of these models on textual data, they have not generalized as well to image data, in part because of the spatial and temporal structure that may exist in an image stream. We introduce a novel unsupervised machine learning framework that incorporates the ability of convolutional autoencoders to discover features from images that directly encode spatial information, within a Bayesian nonparametric topic model that discovers meaningful latent patterns within discrete data. By using this hybrid framework, we overcome the fundamental dependency of traditional topic models on rigidly hand-coded data representations, while simultaneously encoding spatial dependency in our topics without adding model complexity. We apply this model to the motivating application of high-level scene understanding and mission summarization for exploratory marine robots. Our experiments on a seafloor dataset collected by a marine robot show that the proposed hybrid framework outperforms current state-of-the-art approaches on the task of unsupervised seafloor terrain characterization.

NeurIPS Conference 2017 Conference Paper

Gaussian process based nonlinear latent structure discovery in multivariate spike train data

• Anqi Wu
• Nicholas Roy
• Stephen Keeley
• Jonathan Pillow

A large body of recent work focuses on methods for extracting low-dimensional latent structure from multi-neuron spike train data. Most such methods employ either linear latent dynamics or linear mappings from latent space to log spike rates. Here we propose a doubly nonlinear latent variable model that can identify low-dimensional structure underlying apparently high-dimensional spike train data. We introduce the Poisson Gaussian-Process Latent Variable Model (P-GPLVM), which consists of Poisson spiking observations and two underlying Gaussian processes—one governing a temporal latent variable and another governing a set of nonlinear tuning curves. The use of nonlinear tuning curves enables discovery of low-dimensional latent structure even when spike responses exhibit high linear dimensionality (e. g. , as found in hippocampal place cell codes). To learn the model from data, we introduce the decoupled Laplace approximation, a fast approximate inference method that allows us to efficiently optimize the latent path while marginalizing over tuning curves. We show that this method outperforms previous Laplace-approximation-based inference methods in both the speed of convergence and accuracy. We apply the model to spike trains recorded from hippocampal place cells and show that it compares favorably to a variety of previous methods for latent structure discovery, including variational auto-encoder (VAE) based methods that parametrize the nonlinear mapping from latent space to spike rates with a deep neural network.

IJCAI Conference 2017 Conference Paper

Grounding Abstract Spatial Concepts for Language Interaction with Robots

• Rohan Paul
• Jacob Arkin
• Nicholas Roy
• Thomas M. Howard

Our goal is to develop models that allow a robot to understand or ``ground" natural language instructionsin the context of its world model. Contemporary approaches estimate correspondences between an instruction and possible candidate groundings such as objects, regions and goals for a robot's action. However, these approaches are unable to reason about abstract or hierarchical concepts such as rows, columns and groups that are relevant in a manipulation domain. We introduce a probabilistic model that incorporates an expressive space of abstract spatial concepts as well as notions of cardinality and ordinality. Abstract concepts are introduced as explicit hierarchical symbols correlated with concrete groundings. Crucially, the abstract groundings form a Markov boundary over concrete groundings, effectively de-correlating them from the remaining variables in the graph which reduces the complexity of training and inference in the model. Empirical evaluation demonstrates accurate grounding of abstract concepts embedded in complex natural language instructions commanding a robot manipulator. The proposed inference method leads to significant efficiency gains compared to the baseline, with minimal trade-off in accuracy.

RLDM Conference 2017 Conference Abstract

Safe Visual Navigation via Deep Learning and Novelty Detection

• Charles Richter
• Nicholas Roy

Control systems that use learned models to predict the outcomes of actions in the real world must be able to safely handle cases where they are forced to make decisions in scenarios that are unlike any of their training examples. For example, deep learning methods provide state-of-the-art capabilities for processing raw sensor data such as images. However, they may produce erratic or unsafe predictions when faced with novel inputs. Furthermore, recent methods for quantifying neural network uncertainty, such as MC Dropout, may not provide suitable or efficient uncertainty estimates when queried with novel inputs in domains such as image-based robot navigation. Rather than unconditionally trusting the predictions of a neural network for real-world data, our primary contribution is to show that we can use an autoencoder to recognize when a query is novel, and revert to a safe prior behavior. With this capability, we can deploy an autonomous deep-learning system in arbitrary environments, without concern for whether it has received the appropriate training. We demonstrate our method with a vision-guided robot that can leverage its deep neural network to navigate 50% faster than a safe baseline policy in familiar environments, while reverting to the prior behavior in novel environments so that it can safely collect additional data and continually improve. A video illustrating our approach is available at: http: //www. ccode. ml/XgEhf.

IJCAI Conference 2017 Conference Paper

Temporal Grounding Graphs for Language Understanding with Accrued Visual-Linguistic Context

• Rohan Paul
• Andrei Barbu
• Sue Felshin
• Boris Katz
• Nicholas Roy

A robot’s ability to understand or ground natural language instructions is fundamentally tied to its knowledge about the surrounding world. We present an approach to grounding natural language utterances in the context of factual information gathered through natural-language interactions and past visual observations. A probabilistic model estimates, from a natural language utterance, the objects, relations, and actions that the utterance refers to, the objectives for future robotic actions it implies, and generates a plan to execute those actions while updating a state representation to include newly acquired knowledge from the visual-linguistic context. Grounding a command necessitates a representation for past observations and interactions; however, maintaining the full context consisting of all possible observed objects, attributes, spatial relations, actions, etc. , over time is intractable. Instead, our model, Temporal Grounding Graphs, maintains a learned state representation for a belief over factual groundings, those derived from natural-language interactions, and lazily infers new groundings from visual observations using the context implied by the utterance. This work significantly expands the range of language that a robot can understand by incorporating factual knowledge and observations of its workspace into its inference about the meaning and grounding of natural-language utterances.

ICRA Conference 2016 Conference Paper

An analysis of wind field estimation and exploitation for quadrotor flight in the urban canopy layer

• John Ware
• Nicholas Roy

Although unmanned air vehicles' increasing agility and autonomy may soon allow for flight in urban environments, the impact of complex urban wind fields on vehicle flight performance remains unclear. Unlike synoptic winds at high altitudes, urban wind fields are subject to turbulence generated by the buildings and terrain. The resulting spatial and temporal variation makes inference about the global wind field based on local wind measurements difficult and prevents the use of most simple wind models. Fortunately, the structure of the urban environment provides exploitable predictability given a suitable computational fluid dynamics solver, a representative 3D model of the environment, and an estimate of the expected prevailing wind speed and heading. The prevailing wind speed and direction at altitude and computational fluid dynamics solver can generate the corresponding wind field estimate over the map. By generating wind fields in this way, this work investigates a quadrotor's ability to exploit them for improved flight performance. Along with the wind field estimate, an empirically derived power consumption model is used to find minimum-energy trajectories with a planner both aware of and naive to the wind field. When compared to minimum-energy trajectories that do not incorporate wind conditions, the wind-aware trajectories demonstrate reduced flight times, total energy expenditures, and failures due to excess air speed for trajectories across MIT campus.

ICRA Conference 2016 Conference Paper

Multi-level mapping: Real-time dense monocular SLAM

• W. Nicholas Greene
• Kyel Ok
• Peter Lommel
• Nicholas Roy

We present a method for Simultaneous Localization and Mapping (SLAM) using a monocular camera that is capable of reconstructing dense 3D geometry online without the aid of a graphics processing unit (GPU). Our key contribution is a multi-resolution depth estimation and spatial smoothing process that exploits the correlation between low-texture image regions and simple planar structure to adaptively scale the complexity of the generated keyframe depthmaps to the texture of the input imagery. High-texture image regions are represented at higher resolutions to capture fine detail, while low-texture regions are represented at coarser resolutions for smooth surfaces. The computational savings enabled by this approach allow for significantly increased reconstruction density and quality when compared to the state-of-the-art. The increased depthmap density also improves tracking performance as more constraints can contribute to the pose estimation. A video of experimental results is available at http://groups.csail.mit.edu/rrg/multi_level_mapping.

ICRA Conference 2016 Conference Paper

PROBE-GK: Predictive robust estimation using generalized kernels

• Valentin Peretroukhin
• William Vega-Brown
• Nicholas Roy
• Jonathan Kelly

Many algorithms in computer vision and robotics make strong assumptions about uncertainty, and rely on the validity of these assumptions to produce accurate and consistent state estimates. In practice, dynamic environments may degrade sensor performance in predictable ways that cannot be captured with static uncertainty parameters. In this paper, we employ fast nonparametric Bayesian inference techniques to more accurately model sensor uncertainty. By setting a prior on observation uncertainty, we derive a predictive robust estimator, and show how our model can be learned from sample images, both with and without knowledge of the motion used to generate the data. We validate our approach through Monte Carlo simulations, and report significant improvements in localization accuracy relative to a fixed noise model in several settings, including on synthetic data, the KITTI dataset, and our own experimental platform.

ICRA Conference 2016 Conference Paper

Simultaneous tracking and rendering: Real-time monocular localization for MAVs

• Kyel Ok
• W. Nicholas Greene
• Nicholas Roy

We propose a method of real-time monocular camera-based localization in known environments. With the goal of controlling high-speed micro air vehicles (MAVs), we localize with respect to a mesh map of the environment that can support both pose estimation and trajectory planning. Using only limited hardware that can be carried on a MAV, we achieve accurate pose estimation at rates above 50 Hz, an order of magnitude faster than the current state-of-the-art mesh-based localization algorithms. In our simultaneous tracking and rendering (STAR) approach, we render virtual images of the environment and track camera images with respect to them using a robust semi-direct image alignment technique. Our main contribution is the decoupling of camera tracking from virtual image rendering, which drastically reduces the number of rendered images and enables accurate full camera-rate tracking without needing a high-end GPU. We demonstrate our approach in GPS-denied indoor environments.

RLDM Conference 2015 Conference Abstract

Bayesian Learning for Safe High-Speed Navigation in Unknown Environments

• Charles Richter
• William Vega-Brown
• Nicholas Roy

The focus of this work is to develop a planner for high-speed navigation in unknown environ- ments, for instance locating a specified goal in an unknown building in minimum time or flying as fast as possible through an unmapped forest. We model this problem as a POMDP and discuss why it is so diffi- cult even under the assumption of noiseless dynamics and observations. We then describe our method of predicting probabilities of collision as a way to approximate the POMDP solution. We employ a Bayesian non-parametric learning algorithm to predict probabilities of collision associated with different planning scenarios, and select trajectories in a receding-horizon fashion that minimize cost in expectation with re- spect to those probabilities. We also describe the training procedure for our learning algorithm and draw the similarities between our approach and batch, model-based reinforcement learning. We show two prin- cipal results. First, we show that by using a learned model of collision probability, our robot can navigate significantly faster in certain environments than a robot that enforces absolute safety guarantees, provided that it has access to training data from similar environments. Second, leveraging the Bayesian nature of our learning algorithm, we show that in situations where the robot does not have any relevant training data to draw upon, it seamlessly and automatically reverts to a prior estimate of collision probability that keeps it safe.

ICRA Conference 2015 Conference Paper

Learning models for following natural language directions in unknown environments

• Sachithra Hemachandra
• Felix Duvallet
• Thomas M. Howard
• Nicholas Roy
• Anthony Stentz
• Matthew R. Walter

Natural language offers an intuitive and flexible means for humans to communicate with the robots that we will increasingly work alongside in our homes and workplaces. Recent advancements have given rise to robots that are able to interpret natural language manipulation and navigation commands, but these methods require a prior map of the robot's environment. In this paper, we propose a novel learning framework that enables robots to successfully follow natural language route directions without any previous knowledge of the environment. The algorithm utilizes spatial and semantic information that the human conveys through the command to learn a distribution over the metric and semantic properties of spatially extended environments. Our method uses this distribution in place of the latent world model and interprets the natural language instruction as a distribution over the intended behavior. A novel belief space planner reasons directly over the map and behavior distributions to solve for a policy using imitation learning. We evaluate our framework on a voice-commandable wheelchair. The results demonstrate that by learning and performing inference over a latent environment model, the algorithm is able to successfully follow natural language route directions within novel, extended environments.

ICRA Conference 2015 Conference Paper

Monocular image space tracking on a computationally limited MAV

• Kyel Ok
• Dinesh Gamage
• Tom Drummond
• Frank Dellaert
• Nicholas Roy

We propose a method of monocular camera-inertial based navigation for computationally limited micro air vehicles (MAVs). Our approach is derived from the recent development of parallel tracking and mapping algorithms, but unlike previous results, we show how the tracking and mapping processes operate using different representations. The separation of representations allows us not only to move the computational load of full map inference to a ground station, but to further reduce the computational cost of on-board tracking for pose estimation. Our primary contribution is to show how the cost of tracking the vehicle pose on-board can be substantially reduced by estimating the camera motion directly in the image frame, rather than in the world co-ordinate frame. We demonstrate our method on an Ascending Technologies Pelican quad-rotor, and show that we can track the vehicle pose with reduced on-board computation but without compromised navigation accuracy.

ICRA Conference 2014 Conference Paper

A natural language planner interface for mobile manipulators

• Thomas M. Howard
• Stefanie Tellex
• Nicholas Roy

Natural language interfaces for robot control aspire to find the best sequence of actions that reflect the behavior intended by the instruction. This is difficult because of the diversity of language, variety of environments, and heterogeneity of tasks. Previous work has demonstrated that probabilistic graphical models constructed from the parse structure of natural language can be used to identify motions that most closely resemble verb phrases. Such approaches however quickly succumb to computational bottlenecks imposed by construction and search the space of possible actions. Planning constraints, which define goal regions and separate the admissible and inadmissible states in an environment model, provide an interesting alternative to represent the meaning of verb phrases. In this paper we present a new model called the Distributed Correspondence Graph (DCG) to infer the most likely set of planning constraints from natural language instructions. A trajectory planner then uses these planning constraints to find a sequence of actions that resemble the instruction. Separating the problem of identifying the action encoded by the language into individual steps of planning constraint inference and motion planning enables us to avoid computational costs associated with generation and evaluation of many trajectories. We present experimental results from comparative experiments that demonstrate improvements in efficiency in natural language understanding without loss of accuracy.

ICRA Conference 2014 Conference Paper

High-speed autonomous navigation of unknown environments using learned probabilities of collision

• Charles Richter
• John Ware
• Nicholas Roy

We present a motion planning algorithm for dynamic vehicles navigating through unknown environments. We focus on the scenario in which a fast-moving car attempts to navigate from a start location to a set of goal coordinates in minimum time with no prior information about the environment, building a map in real time from onboard sensor data. Whereas existing planners for exploration confine themselves to a conservative set of constraints to guarantee safety around unknown regions of the environment, we instead learn a hazard function from data, which maps the vehicle's dynamic state and current environment knowledge to a probability of collision. We perform receding horizon planning in which the objective function is evaluated in expectation over those learned probabilities of collision. Our algorithm demonstrates sensible emergent behaviors, like swinging wide around blind corners, slowing down near the map frontier, and accelerating in regions of high visibility. Our algorithm is capable of navigating from start to goal much more quickly than the conservative baseline planner without sacrificing safety. We demonstrate our algorithm on a 1: 8-scale high-performance RC car equipped with a planar laser range-finder and inertial measurement unit, reaching speeds of 4m/s in unknown, indoor spaces. A video of experimental results is available at: http://groups.csail.mit.edu/rrg/nav_learned_prob_collision.

NeurIPS Conference 2014 Conference Paper

Nonparametric Bayesian inference on multivariate exponential families

• William Vega-Brown
• Marek Doniec
• Nicholas Roy

We develop a model by choosing the maximum entropy distribution from the set of models satisfying certain smoothness and independence criteria; we show that inference on this model generalizes local kernel estimation to the context of Bayesian inference on stochastic processes. Our model enables Bayesian inference in contexts when standard techniques like Gaussian process inference are too expensive to apply. Exact inference on our model is possible for any likelihood function from the exponential family. Inference is then highly efficient, requiring only O(log N) time and O(N) space at run time. We demonstrate our algorithm on several problems and show quantifiable improvement in both speed and performance relative to models based on the Gaussian process.

UAI Conference 2013 Conference Paper

Batch-iFDD for Representation Expansion in Large MDPs

• Alborz Geramifard
• Thomas J. Walsh 0001
• Nicholas Roy
• Jonathan P. How

Matching pursuit (MP) methods are a promising class of feature construction algorithms for value function approximation. Yet existing MP methods require creating a pool of potential features, mandating expert knowledge or enumeration of a large feature pool, both of which hinder scalability. This paper introduces batch incremental feature dependency discovery (Batch-iFDD) as an MP method that inherits a provable convergence property. Additionally, Batch-iFDD does not require a large pool of features, leading to lower computational complexity. Empirical policy evaluation results across three domains with up to one million states highlight the scalability of Batch-iFDD over the previous state of the art MP algorithm.

IROS Conference 2013 Conference Paper

CELLO-EM: Adaptive sensor models without ground truth

• William Vega-Brown
• Nicholas Roy

We present an algorithm for providing a dynamic model of sensor measurements. Rather than depending on a model of the vehicle state and environment to capture the distribution of possible sensor measurements, we provide an approximation that allows the sensor model to depend on the measurement itself. Building on previous work, we show how the sensor model predictor can be learned from data without access to ground truth labels of the vehicle state or true underlying distribution, and we show our approach to be a generalization of non-parametric kernel regressors. Our algorithm is demonstrated in simulation and on real world data for both laser-based scan matching odometry and RGB-D camera odometry in an unknown map. The performance of our algorithm is shown to quantitatively improve estimation, both in terms of consistency and absolute accuracy, relative to other algorithms and to fixed covariance models.

ICRA Conference 2013 Conference Paper

CELLO: A fast algorithm for Covariance Estimation

• William Vega-Brown
• Abraham Bachrach
• Adam Bry
• Jonathan Kelly
• Nicholas Roy

We present CELLO (Covariance Estimation and Learning through Likelihood Optimization), an algorithm for predicting the covariances of measurements based on any available informative features. This algorithm is intended to improve the accuracy and reliability of on-line state estimation by providing a principled way to extend the conventional fixed-covariance Gaussian measurement model. We show that in experiments, CELLO learns to predict measurement covariances that agree with empirical covariances obtained by manually annotating sensor regimes. We also show that using the learned covariances during filtering provides substantial quantitative improvement to the overall state estimate.

ICRA Conference 2013 Conference Paper

Reinforcement learning with misspecified model classes

• Joshua Mason Joseph
• Alborz Geramifard
• John W. Roberts
• Jonathan P. How
• Nicholas Roy

Real-world robots commonly have to act in complex, poorly understood environments where the true world dynamics are unknown. To compensate for the unknown world dynamics, we often provide a class of models to a learner so it may select a model, typically using a minimum prediction error metric over a set of training data. Often in real-world domains the model class is unable to capture the true dynamics, due to either limited domain knowledge or a desire to use a small model. In these cases we call the model class misspecified, and an unfortunate consequence of misspecification is that even with unlimited data and computation there is no guarantee the model with minimum prediction error leads to the best performing policy. In this work, our approach improves upon the standard maximum likelihood model selection metric by explicitly selecting the model which achieves the highest expected reward, rather than the most likely model. We present an algorithm for which the highest performing model from the model class is guaranteed to be found given unlimited data and computation. Empirically, we demonstrate that our algorithm is often superior to the maximum likelihood learner in a batch learning setting for two common RL benchmark problems and a third real-world system, the hydrodynamic cart-pole, a domain whose complex dynamics cannot be known exactly.

ICRA Conference 2012 Conference Paper

A Bayesian nonparametric approach to modeling battery health

• Joshua Mason Joseph
• Finale Doshi
• Nicholas Roy

The batteries of many consumer products are both a substantial portion of the product's cost and commonly a first point of failure. Accurately predicting remaining battery life can lower costs by reducing unnecessary battery replacements. Unfortunately, battery dynamics are extremely complex, and we often lack the domain knowledge required to construct a model by hand. In this work, we take a data-driven approach and aim to learn a model of battery time-to-death from training data. Using a Dirichlet process prior over mixture weights, we learn an infinite mixture model for battery health. The Bayesian aspect of our model helps to avoid over-fitting while the nonparametric nature of the model allows the data to control the size of the model, preventing under-fitting. We demonstrate our model's effectiveness by making time-to-death predictions using real data from nickel-metal hydride battery packs.

AIJ Journal 2012 Journal Article

Reinforcement learning with limited reinforcement: Using Bayes risk for active learning in POMDPs

• Finale Doshi-Velez
• Joelle Pineau
• Nicholas Roy

ICRA Conference 2012 Conference Paper

State estimation for aggressive flight in GPS-denied environments using onboard sensing

• Adam Bry
• Abraham Bachrach
• Nicholas Roy

In this paper we present a state estimation method based on an inertial measurement unit (IMU) and a planar laser range finder suitable for use in real-time on a fixed-wing micro air vehicle (MAV). The algorithm is capable of maintaing accurate state estimates during aggressive flight in unstructured 3D environments without the use of an external positioning system. Our localization algorithm is based on an extension of the Gaussian Particle Filter. We partition the state according to measurement independence relationships and then calculate a pseudo-linear update which allows us to use 20x fewer particles than a naive implementation to achieve similar accuracy in the state estimate. We also propose a multi-step forward fitting method to identify the noise parameters of the IMU and compare results with and without accurate position measurements. Our process and measurement models integrate naturally with an exponential coordinates representation of the attitude uncertainty. We demonstrate our algorithms experimentally on a fixed-wing vehicle flying in a challenging indoor environment.

IJCAI Conference 2011 Conference Paper

Active Exploration for Robust Object Detection

• Javier Velez
• Garrett Hemann
• Albert S. Huang
• Ingmar Posner
• Nicholas Roy

Today, mobile robots are increasingly expected to operate in ever more complex and dynamic environments. In order to carry out many of the higher level tasks envisioned a semantic understanding of a workspace is pivotal. Here our field has benefited significantly from successes in machine learning and vision: applications in robotics of off-the-shelf object detectors are plentiful. This paper outlines an online, any-time planning framework enabling the active exploration of such detections. Our approach exploits the ability to move to different vantage points and implicitly weighs the benefits of gaining more certainty about the existence of an object against the physical cost of the exploration required. The result is a robot which plans trajectories specifically to decrease the entropy of putative detections. Our system is demonstrated to significantly improve detection performance and trajectory length in simulated and real robot experiments.

ICRA Conference 2011 Conference Paper

Following and interpreting narrated guided tours

• Sachithra Hemachandra
• Thomas Kollar
• Nicholas Roy
• Seth J. Teller

We describe a robotic tour-taking capability enabling a robot to acquire local knowledge of a human-occupied environment. A tour-taking robot autonomously follows a human guide through an environment, interpreting the guide's spoken utterances and the shared spatiotemporal context in order to acquire a spatially segmented and semantically labeled metrical-topological representation of the environment. The described tour-taking capability enables scalable deployment of mobile robots into human-occupied environments, and natural human-robot interaction for commanded mobility. Our primary contributions are an efficient, socially acceptable autonomous tour-following behavior and a tour interpretation algorithm that partitions a map into spaces labeled according to the guide's utterances. The tour-taking behavior is demonstrated in a multi-floor office building and evaluated by assessing the comfort of the tour guides, and by comparing the robot's map partitions to those produced by humans.

ICML Conference 2011 Conference Paper

Infinite Dynamic Bayesian Networks

• Finale Doshi
• David Wingate
• Joshua B. Tenenbaum
• Nicholas Roy

ICML Conference 2011 Conference Paper

Online Discovery of Feature Dependencies

• Alborz Geramifard
• Finale Doshi
• Josh Redding
• Nicholas Roy
• Jonathan P. How

ICAPS Conference 2011 Conference Paper

Planning to Perceive: Exploiting Mobility for Robust Object Detection

• Javier Vélez
• Garrett Hemann
• Albert S. Huang
• Ingmar Posner
• Nicholas Roy

Consider the task of a mobile robot autonomously navigating through an environment while detecting and mapping objects of interest using a noisy object detector. The robot must reach its destination in a timely manner, but is rewarded for correctly detecting recognizable objects to be added to the map, and penalized for false alarms. However, detector performance typically varies with vantage point, so the robot benefits from planning trajectories which maximize the efficacy of the recognition system. This work describes an online, any-time planning framework enabling the active exploration of possible detections provided by an off-the-shelf object detector. We present a probabilistic approach where vantage points are identified which provide a more informative view of a potential object. The agent then weighs the benefit of increasing its confidence against the cost of taking a detour to reach each identified vantage point. The system is demonstrated to significantly improve detection and trajectory length in both simulated and real robot experiments.

ICRA Conference 2011 Conference Paper

Rapidly-exploring Random Belief Trees for motion planning under uncertainty

• Adam Bry
• Nicholas Roy

In this paper we address the problem of motion planning in the presence of state uncertainty, also known as planning in belief space. The work is motivated by planning domains involving nontrivial dynamics, spatially varying measurement properties, and obstacle constraints. To make the problem tractable, we restrict the motion plan to a nominal trajectory stabilized with a linear estimator and controller. This allows us to predict distributions over future states given a candidate nominal trajectory. Using these distributions to ensure a bounded probability of collision, the algorithm incrementally constructs a graph of trajectories through state space, while efficiently searching over candidate paths through the graph at each iteration. This process results in a search tree in belief space that provably converges to the optimal path. We analyze the algorithm theoretically and also provide simulation results demonstrating its utility for balancing information gathering to reduce uncertainty and finding low cost paths.

AAAI Conference 2011 Conference Paper

Understanding Natural Language Commands for Robotic Navigation and Mobile Manipulation

• Stefanie Tellex
• Thomas Kollar
• Steven Dickerson
• Matthew Walter
• Ashis Banerjee
• Seth Teller
• Nicholas Roy

This paper describes a new model for understanding natural language commands given to autonomous systems that perform navigation and mobile manipulation in semi-structured environments. Previous approaches have used models with fixed structure to infer the likelihood of a sequence of actions given the environment and the command. In contrast, our framework, called Generalized Grounding Graphs (G3 ), dynamically instantiates a probabilistic graphical model for a particular natural language command according to the command’s hierarchical and compositional semantic structure. Our system performs inference in the model to successfully find and execute plans corresponding to natural language commands such as “Put the tire pallet on the truck. ” The model is trained using a corpus of commands collected using crowdsourcing. We pair each command with robot actions and use the corpus to learn the parameters of the model. We evaluate the robot’s performance by inferring plans from natural language commands, executing each plan in a realistic robot simulator, and asking users to evaluate the system’s performance. We demonstrate that our system can successfully follow many natural language commands from the corpus.

AAAI Conference 2010 Conference Paper

A Bayesian Nonparametric Approach to Modeling Mobility Patterns

• Joshua Joseph
• Finale Doshi-Velez
• Nicholas Roy

Constructing models of mobile agents can be difficult without domain-specific knowledge. Parametric models flexible enough to capture all mobility patterns that an expert believes are possible are often large, requiring a great deal of training data. In contrast, nonparametric models are extremely flexible and can generalize well with relatively little training data. We propose modeling the mobility patterns of moving agents as a mixture of Gaussian processes (GP) with a Dirichlet process (DP) prior over mixture weights. The GP provides a flexible representation for each individual mobility pattern, while the DP assigns observed trajectories to particular mobility patterns. Both the GPs and the DP adjust the model’s complexity based on available data, implicitly avoiding issues of over-fitting or under-fitting. We apply our model to a helicopter-based tracking task, where the mobility patterns of the tracked agents—cars—are learned from real data collected from taxis in the greater Boston area.

ICRA Conference 2010 Conference Paper

A voice-commandable robotic forklift working alongside humans in minimally-prepared outdoor environments

• Seth J. Teller
• Matthew R. Walter
• Matthew E. Antone
• Andrew Correa
• Randall Davis
• Luke Fletcher
• Emilio Frazzoli
• James R. Glass

One long-standing challenge in robotics is the realization of mobile autonomous robots able to operate safely in existing human workplaces in a way that their presence is accepted by the human occupants. We describe the development of a multi-ton robotic forklift intended to operate alongside human personnel, handling palletized materials within existing, busy, semi-structured outdoor storage facilities.

ICRA Conference 2010 Conference Paper

Efficient planning under uncertainty for a target-tracking micro-aerial vehicle

• Ruijie He
• Abraham Bachrach
• Nicholas Roy

A helicopter agent has to plan trajectories to track multiple ground targets from the air. The agent has partial information of each target's pose, and must reason about its uncertainty of the targets' poses when planning subsequent actions. We present an online, forward-search algorithm for planning under uncertainty by representing the agent's belief of each target's pose as a multi-modal Gaussian belief. We exploit this parametric belief representation to directly compute the distribution of posterior beliefs after actions are taken. This analytic computation not only enables us to plan in problems with continuous observation spaces, but also allows the agent to search deeper by considering policies composed of multi-step action sequences; deeper searches better enable the agent to keep the targets well-localized. We present experimental results in simulation, as well as demonstrate the algorithm on an actual quadrotor helicopter tracking multiple vehicles on a road network constructed indoors.

ICRA Conference 2010 Conference Paper

Indoor scene recognition through object detection

• Pablo Espinace
• Thomas Kollar
• Alvaro Soto
• Nicholas Roy

Scene recognition is a highly valuable perceptual ability for an indoor mobile robot, however, current approaches for scene recognition present a significant drop in performance for the case of indoor scenes. We believe that this can be explained by the high appearance variability of indoor environments. This stresses the need to include high-level semantic information in the recognition process. In this work we propose a new approach for indoor scene recognition based on a generative probabilistic hierarchical model that uses common objects as an intermediate semantic representation. Under this model, we use object classifiers to associate low-level visual features to objects, and at the same time, we use contextual relations to associate objects to scenes. As a further contribution, we improve the performance of current state-of-the-art category-level object classifiers by including geometrical information obtained from a 3D range sensor that facilitates the implementation of a focus of attention mechanism within a Monte Carlo sampling scheme. We test our approach using real data, showing significant advantages with respect to previous state-of-the-art methods.

ICRA Conference 2010 Conference Paper

Multiple relative pose graphs for robust cooperative mapping

• Been Kim
• Michael Kaess
• Luke Fletcher
• John J. Leonard
• Abraham Bachrach
• Nicholas Roy
• Seth J. Teller

This paper describes a new algorithm for cooperative and persistent simultaneous localization and mapping (SLAM) using multiple robots. Recent pose graph representations have proven very successful for single robot mapping and localization. Among these methods, incremental smoothing and mapping (iSAM) gives an exact incremental solution to the SLAM problem by solving a full nonlinear optimization problem in real-time. In this paper, we present a novel extension to iSAM to facilitate online multi-robot mapping based on multiple pose graphs. Our main contribution is a relative formulation of the relationship between multiple pose graphs that avoids the initialization problem and leads to an efficient solution when compared to a completely global formulation. The relative pose graphs are optimized together to provide a globally consistent multi-robot solution. Efficient access to covariances at any time for relative parameters is provided through iSAM, facilitating data association and loop closing. The performance of the technique is illustrated on various data sets including a publicly available multi-robot data set. Further evaluation is performed in a collaborative helicopter and ground robot experiment.

IROS Conference 2010 Conference Paper

Natural language command of an autonomous micro-air vehicle

• Albert S. Huang
• Stefanie Tellex
• Abraham Bachrach
• Thomas Kollar
• Deb Roy
• Nicholas Roy

Natural language is a flexible and intuitive modality for conveying directions and commands to a robot but presents a number of computational challenges. Diverse words and phrases must be mapped into structures that the robot can understand, and elements in those structures must be grounded in an uncertain environment. In this paper we present a micro-air vehicle (MAV) capable of following natural language directions through a previously mapped and labeled environment. We extend our previous work in understanding 2D natural language directions to three dimensions, accommodating new verb modifiers such as go up and go down, and commands such as turn around and face the windows. We demonstrate the robot following directions created by a human for another human, and interactively executing commands in the context of surveillance and search and rescue in confined spaces. In an informal study, 71% of the paths computed from directions given by one user terminated within 10m of the desired destination.

NeurIPS Conference 2010 Conference Paper

Nonparametric Bayesian Policy Priors for Reinforcement Learning

• Finale Doshi-Velez
• David Wingate
• Nicholas Roy
• Joshua Tenenbaum

We consider reinforcement learning in partially observable domains where the agent can query an expert for demonstrations. Our nonparametric Bayesian approach combines model knowledge, inferred from expert information and independent exploration, with policy knowledge inferred from expert trajectories. We introduce priors that bias the agent towards models with both simple representations and simple policies, resulting in improved policy and model learning.

AAAI Conference 2010 Conference Paper

PUMA: Planning Under Uncertainty with Macro-Actions

• Ruijie He
• Emma Brunskill
• Nicholas Roy

ICRA Conference 2010 Conference Paper

RANGE - robust autonomous navigation in GPS-denied environments

• Abraham Bachrach
• Anton de Winter
• Ruijie He
• Garrett Hemann
• Sam Prentice
• Nicholas Roy

This video highlights our system that enables a Micro Aerial Vehicle (MAV) to autonomously explore and map unstructured and unknown GPS-denied environments. While mapping and exploration solutions are now well-established for ground vehicles, air vehicles face unique challenges which have hindered the development of similar capabilities. Although there has been recent progress toward sensing, control, and navigation techniques for GPS-denied flight, there have been few demonstrations of stable, goal-directed flight in real-world environments. Our system leverages a multi-level sensing and control hierarchy that matches the computational complexity of the component algorithms with the real-time needs of a MAV to achieve autonomy in unconstrained environments.

ICRA Conference 2009 Conference Paper

icLQG: Combining local and global optimization for control in information space

• Vu Anh Huynh
• Nicholas Roy

When a mobile robot does not have perfect knowledge of its position, conventional controllers can experience failures such as collisions because the uncertainty of the position is not considered in choosing control actions. In this paper, we show how global planning and local feedback control can be combined to generate control laws in the space of distributions over position, that is, in information space. We give a novel algorithm for computing “information-constrained” linear quadratic Gaussian (icLQG) policies for controlling a robot with imperfect state information. The icLQG algorithm uses the belief roadmap algorithm to efficiently search for a trajectory that approximates the globally-optimal motion plan in information space, and then iteratively computes a feedback control law to locally optimize the global approximation. The icLQG algorithm is not only robust to imperfect state information but also scalable to high-dimensional systems and environments. In addition, icLQG is capable of answering multiple queries efficiently. We demonstrate performance results for controlling a vehicle on the plane and a helicopter in three dimensions.

JMLR Journal 2009 Journal Article

Provably Efficient Learning with Typed Parametric Models

• Emma Brunskill
• Bethany R. Leffler
• Lihong Li
• Michael L. Littman
• Nicholas Roy

To quickly achieve good performance, reinforcement-learning algorithms for acting in large continuous-valued domains must use a representation that is both sufficiently powerful to capture important domain characteristics, and yet simultaneously allows generalization, or sharing, among experiences. Our algorithm balances this tradeoff by using a stochastic, switching, parametric dynamics representation. We argue that this model characterizes a number of significant, real-world domains, such as robot navigati on across varying terrain. We prove that this representational assumption allows our algorithm to be probably approximately correct with a sample complexity that scales polynomially with all problem-specific quantities including the state-space dimension. We also explicitly incorporate the error introduced by approximate planning in our sample complexity bounds, in contrast to prior Probably Approximately Correct (PAC) Markov Decision Processes (MDP) approaches, which typically assume the estimated MDP can be solved exactly. Our experimental results on constructing plans for driving to work using real car trajectory data, as well as a small robot experiment on navigating varying terrain, demonstrate that our dynamics representation enables us to capture real-world dynamics in a sufficient manner to produce good performance. [abs] [ pdf ][ bib ] &copy JMLR 2009. ( edit, beta )

ICRA Conference 2009 Conference Paper

Utilizing object-object and object-scene context when planning to find things

• Thomas Kollar
• Nicholas Roy

In this paper, our goal is to search for a novel object, where we have a prior map of the environment and knowledge of some of the objects in it, but no information about the location of the specific novel object. We develop a probabilistic model over possible object locations that utilizes object-object and object-scene context. This model can be queried for any of over 25, 000 naturally occurring objects in the world and is trained from labeled data acquired from the captions of photos on the Flickr Website. We show that these simple models based on object co-occurrences perform surprisingly well at localizing arbitrary objects in an office setting. In addition, we show how to compute paths that minimize the expected distance to the query object and show that this approach performs better than a greedy approach. Finally, we give preliminary results for grounding our approach in object classifiers.

ICRA Conference 2009 Conference Paper

Where to go: Interpreting natural directions using global inference

• Yuan Wei
• Emma Brunskill
• Thomas Kollar
• Nicholas Roy

An important component of human-robot interaction is that people need to be able to instruct robots to move to other locations using naturally given directions. When giving directions, people often make mistakes such as labelling errors (e. g. , left vs. right) and errors of omission (skipping important decision points in a sequence). Furthermore, people often use multiple levels of granularity in specifying directions, referring to locations using single object landmarks, multiple landmarks in a given location, or identifying large regions as a single location. The challenge is to identify the correct path to a destination from a sequence of noisy, possibly erroneous directions. In our work we cast this problem as probabilistic inference: given a set of directions, an agent should automatically find the path with the geometry and physical appearance to maximize the likelihood of those directions. We use a specific variant of a Markov Random Field (MRF) to represent our model, and gather multi-granularity representation information using existing large tagged datasets. On a dataset of route directions collected in a large third floor university building, we found that our algorithm correctly inferred the true final destination in 47 out of the 55 cases successfully followed by humans volunteers. These results suggest that our algorithm is performing well relative to human users. In the future this work will be included in a broader system for autonomously constructing environmental representations that support natural human-robot interaction for direction giving.

UAI Conference 2008 Conference Paper

CORL: A Continuous-state Offset-dynamics Reinforcement Learner

• Emma Brunskill
• Bethany R. Leffler
• Lihong Li 0001
• Michael L. Littman
• Nicholas Roy

Continuous state spaces and stochastic, switching dynamics characterize a number of rich, realworld domains, such as robot navigation across varying terrain. We describe a reinforcementlearning algorithm for learning in these domains and prove for certain environments the algorithm is probably approximately correct with a sample complexity that scales polynomially with the state-space dimension. Unfortunately, no optimal planning techniques exist in general for such problems; instead we use fitted value iteration to solve the learned MDP, and include the error due to approximate planning in our bounds. Finally, we report an experiment using a robotic car driving over varying terrain to demonstrate that these dynamics representations adequately capture real-world dynamics and that our algorithm can be used to efficiently solve such problems.

IROS Conference 2008 Conference Paper

Learning predictive terrain models for legged robot locomotion

• Christian Plagemann
• Sebastian Mischke
• Sam Prentice
• Kristian Kersting
• Nicholas Roy
• Wolfram Burgard

Legged robots require accurate models of their environment in order to plan and execute paths. We present a probabilistic technique based on Gaussian processes that allows terrain models to be learned and updated efficiently using sparse approximation techniques. The major benefit of our terrain model is its ability to predict elevations at unseen locations more reliably than alternative approaches, while it also yields estimates of the uncertainty in the prediction. In particular, our nonstationary Gaussian process model adapts its covariance to the situation at hand, allowing more accurate inference of terrain height at points that have not been observed directly. We show how a conventional motion planner can use the learned terrain model to plan a path to a goal location, using a terrain-specific cost model to accept or reject candidate footholds. In experiments with a real quadruped robot equipped with a laser range finder, we demonstrate the usefulness of our approach and discuss its benefits compared to simpler terrain models such as elevations grids.

ICRA Conference 2008 Conference Paper

Planning in information space for a quadrotor helicopter in a GPS-denied environment

• Ruijie He
• Sam Prentice
• Nicholas Roy

This paper describes a motion planning algorithm for a quadrotor helicopter flying autonomously without GPS. Without accurate global positioning, the vehicle’s ability to localize itself varies across the environment, since different environmental features provide different degrees of localization. If the vehicle plans a path without regard to how well it can localize itself along that path, it runs the risk of becoming lost. We use the Belief Roadmap (BRM) algorithm [1], an information-space extension of the Probabilistic Roadmap algorithm, to plan vehicle trajectories that incorporate sensing. We show that the original BRM can be extended to use the Unscented Kalman Filter (UKF), and describe a sampling algorithm that minimizes the number of samples required to find a good path. Finally, we demonstrate the BRM path-planning algorithm on the helicopter, navigating in an indoor environment with a laser range-finder.

ICML Conference 2008 Conference Paper

Reinforcement learning with limited reinforcement: using Bayes risk for active learning in POMDPs

• Finale Doshi
• Joelle Pineau
• Nicholas Roy

AAMAS Conference 2008 Conference Paper

The Permutable POMDP: Fast Solutions to POMDPs for Preference Elicitation

• Doshi Finale
• Nicholas Roy

The ability for an agent to reason under uncertainty is crucial for many planning applications, since an agent rarely has access to complete, error-free information about its environment. Partially Observable Markov Decision Processes (POMDPs) are a desirable framework in these planning domains because the resulting policies allow the agent to reason about its own uncertainty. In domains with hidden state and noisy observations, POMDPs optimally trade between actions that increase an agent’s knowledge and actions that increase an agent’s reward. Unfortunately, for many real world problems, even approximating good POMDP solutions is computationally intractable without leveraging structure in the problem domain. We show that the structure of many preference elicitation problems—in which the agent must discover some hidden preference or desire from another (usually human) agent—allows the POMDP solution to be solved with exponentially fewer belief points than standard point-based approximations while retaining the quality of the solution.

IROS Conference 2007 Conference Paper

Analyzing gaussian proposal distributions for mapping with rao-blackwellized particle filters

• Cyrill Stachniss
• Giorgio Grisetti
• Wolfram Burgard
• Nicholas Roy

Particle filters are a frequently used filtering technique in the robotics community. They have been successfully applied to problems such as localization, mapping, or tracking. The particle filter framework allows the designer to freely choose the proposal distribution which is used to obtain the next generation of particles in estimating dynamical processes. This choice greatly influences the performance of the filter. Many approaches have achieved good performance through informed proposals which explicitly take into account the current observation. A popular approach is to approximate the desired proposal distribution by a Gaussian. This paper presents a statistical analysis of the quality of such Gaussian approximations. We also propose a way to obtain the optimal proposal in a non-parametric way and then identify the error introduced by the Gaussian approximation. Furthermore, we present an alternative sampling strategy that better deals with situations in which the target distribution is multi-modal. Experimental results indicate that our alternative sampling strategy leads to accurate maps more frequently that the Gaussian approach while requiring only minimal additional computational overhead.

IROS Conference 2007 Conference Paper

Collision detection in legged locomotion using supervised learning

• Finale Doshi
• Emma Brunskill
• Alexander C. Shkolnik
• Thomas Kollar
• Khashayar Rohanimanesh
• Russ Tedrake
• Nicholas Roy

We propose a fast approach for detecting collision- free swing-foot trajectories for legged locomotion over extreme terrains. Instead of simulating the swing trajectories and checking for collisions along them, our approach uses machine learning techniques to predict whether a swing trajectory is collision-free. Using a set of local terrain features, we apply supervised learning to train a classifier to predict collisions. Both in simulation and on a real quadruped platform, our results show that our classifiers can improve the accuracy of collision detection compared to a real-time geometric approach without significantly increasing the computation time.

IROS Conference 2007 Conference Paper

Topological mapping using spectral clustering and classification

• Emma Brunskill
• Thomas Kollar
• Nicholas Roy

In this work we present an online method for generating topological maps from raw sensor information. We first describe an algorithm to automatically decompose a map into submap segments using a graph partitioning technique known as spectral clustering. We then describe how to train a classifier to recognize graph submaps from laser signatures using the AdaBoost machine learning algorithm. We demonstrate that the we can perform topological mapping by incrementally segmenting the world as the robot moves through its environment, and we can close the loop when the learned classifier recognizes that the robot has returned to a previously visited location.

ICRA Conference 2006 Conference Paper

Adapting Probabilistic Roadmaps to Handle Uncertain Maps

• Patrycja E. Missiuro
• Nicholas Roy

Randomized motion planning techniques are very good at solving high-dimensional motion planning problems. However, most planners assume complete knowledge of the environment, an assumption that can lead to collisions if there are errors in the world model due to uncertainty. We propose an extension of the probabilistic roadmap algorithm that computes motion plans that are robust to uncertain maps. We show that the adapted PRM generates less collision-prone trajectories with fewer samples than the standard method

ICRA Conference 2006 Conference Paper

Using Reinforcement Learning to Improve Exploration Trajectories for Error Minimization

• Thomas Kollar
• Nicholas Roy

The mapping and localization problems have received considerable attention in robotics recently. The exploration problem that drives mapping has started to generate similar attention, as the ease of construction and quality of map is strongly dependent on the strategy used to acquire sensor data for the map. Most exploration strategies concentrate on selecting the next best measurement to take, trading off information gathering for regular relocalization. What has not been studied so far is the effect the robot controller has on the map quality while executing exploration plans. Certain kinds of robot motion (e. g, sharp turns) are hard to estimate correctly, and increase the likelihood of errors in the mapping process. We show how reinforcement learning can be used to generate good motion control while executing a simple information gathering exploration strategy. We show that the learned policy reduces the overall map uncertainty by reducing the amount of uncertainty generated by robot motion

ICRA Conference 2005 Conference Paper

Global A-Optimal Robot Exploration in SLAM

• Robert Sim
• Nicholas Roy

It is well-known that the Kalman filter for simultaneous localization and mapping (SLAM) converges to a fully correlated map in the limit of infinite time and data [1]. However, the rate of convergence of the map has a strong dependence on the order of the observations. We show that conventional exploration algorithms for collecting map data are sub-optimal in both the objective function and choice of optimization procedure. We show that optimizing the a-optimal information measure results in a more accurate map than existing approaches, using a greedy, closed-loop strategy. Secondly, we demonstrate that by restricting the planning to an appropriate policy class, we can tractably find non-greedy, global planning trajectories that produce more accurate maps, explicitly planning to close loops even in open-loop scenarios.

ICRA Conference 2005 Conference Paper

SLAM using Incremental Probabilistic PCA and Dimensionality Reduction

• Emma Brunskill
• Nicholas Roy

The recent progress in robot mapping (or SLAM) algorithms has focused on estimating either point features (such as landmarks) or grid-based representations. Both of these representations generally scale with the size of the environment, not the complexity of the environment. Many thousand parameters may be required even when the structure of the environment can be represented using a few geometric primitives with many fewer parameters. We describe a novel SLAM model called IPSLAM. Our algorithm clusters sensor data into line segments using the Probabilistic PCA algorithm, which provides a data likelihood model that can be used within a SLAM algorithm for the simultaneous estimation of map and robot pose parameters. Unlike previous work in extracting line-based representations from point-based maps, IPSLAM builds non-point-based maps directly from the sensor data. We demonstrate our algorithm on mapping part of the MIT Stata Centre.

ICRA Conference 2004 Conference Paper

Online Control Policy Optimization for Minimizing Map Uncertainty during Exploration

• Robert Sim
• Gregory Dudek
• Nicholas Roy

Tremendous progress has been made recently in simultaneous localization and mapping of unknown environments. Using sensor and odometry data from an exploring mobile robot, it has become much easier to build high-quality globally consistent maps of many large, real-world environments. To date, however, relatively little attention has been paid to the controllers used to build these maps. Existing exploration strategies usually attempt to cover the largest amount of unknown space as quickly as possible. Few strategies exist for building the most reliable map possible, but the particular control strategy can have a substantial impact on the quality of the resulting map. In this paper, we devise a control algorithm for exploring unknown space that explicitly tries to build as large a map as possible while maintaining as accurate a map as possible. We make use of a parameterized class of spiral trajectory policies, choosing a new parameter setting at every time step to maximize the expected reward of the policy. We do this in the context of building a visual map of an unknown environment, and show that our strategy leads to a higher accuracy map faster than other candidate controllers, including any single choice in our policy class.

IROS Conference 2003 Conference Paper

Perspectives on standardization in mobile robot programming: the Carnegie Mellon Navigation (CARMEN) Toolkit

• Michael Montemerlo
• Nicholas Roy
• Sebastian Thrun

In this paper we describe our open-source robot control software, the Carnegie Mellon Navigation (CARMEN) Toolkit. The ultimate goals of CARMEN are to lower the barrier to implementing new algorithms on real and simulated robots and to facilitate sharing of research and algorithms between different institutions. In order for CARMEN to be as inclusive of various research approaches as possible, we have chosen not to adopt strict software standards, but to instead focus on good design practices. This paper outlines the lessons we have learned in developing these practices.

AAAI Conference 2002 Conference Paper

Experiences with a Mobile Robotic Guide for the Elderly

• Michael Montemerlo
• Nicholas Roy
• and Vandi Verma

This paper describes an implemented robot system, which relies heavily on probabilistic AI techniques for acting under uncertainty. The robot Pearl and its predecessor Flo have been developed by a multi-disciplinary team of researchers over the past three years. The goal of this research is to investigate the feasibility of assisting elderly people with cognitive and physical activity limitations through interactive robotic devices, thereby improving their quality of life. The robot’s task involves escorting people in an assisted living facility—a time-consuming task currently carried out by nurses. Its software architecture employs probabilistic techniques at virtually all levels of perception and decision making. During the course of experiments conducted in an assisted living facility, the robot successfully demonstrated that it could autonomously provide guidance for elderly residents. While previous experiments with fielded robot systems have provided evidence that probabilistic techniques work well in the context of navigation, we found the same to be true of human robot interaction with elderly people.

NeurIPS Conference 2002 Conference Paper

Exponential Family PCA for Belief Compression in POMDPs

• Nicholas Roy
• Geoffrey Gordon

Geoffrey Gordon Department of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 ggordon@cs. cmu. edu Standard value function approaches to finding policies for Partially Observable Markov Decision Processes (POMDPs) are intractable for large models. The in- tractability of these algorithms is due to a great extent to their generating an optimal policy over the entire belief space. However, in real POMDP problems most belief states are unlikely, and there is a structured, low-dimensional manifold of plausible beliefs embedded in the high-dimensional belief space. We introduce a new method for solving large-scale POMDPs by taking advantage of belief space sparsity. We reduce the dimensionality of the belief space by exponential family Principal Components Analysis [1], which allows us to turn the sparse, high- dimensional belief space into a compact, low-dimensional representation in terms of learned features of the belief state. We then plan directly on the low-dimensional belief features. By planning in a low-dimensional space, we can find policies for POMDPs that are orders of magnitude larger than can be handled by conventional techniques. We demonstrate the use of this algorithm on a synthetic problem and also on a mobile robot navigation task.

IROS Conference 2002 Conference Paper

Motion planning through policy search

• Nicholas Roy
• Sebastian Thrun

We propose a motion planning algorithm. for performing policy search in the full pose and velocity space of a mobile robot. By comparison, existing techniques optimize high-level plans, but fail to optimize the low-level motion controls. We use policy search in a high dimensional control space to find plans that lead. to measurably better motion planning. Our experimental results suggest that our approach leads to superior robot motion than many existing techniques.

ICML Conference 2001 Conference Paper

Toward Optimal Active Learning through Sampling Estimation of Error Reduction

• Nicholas Roy
• Andrew McCallum

NeurIPS Conference 1999 Conference Paper

Coastal Navigation with Mobile Robots

• Nicholas Roy
• Sebastian Thrun

The problem that we address in this paper is how a mobile robot can plan in order to arrive at its goal with minimum uncertainty. Traditional motion planning algo(cid: 173) rithms often assume that a mobile robot can track its position reliably, however, in real world situations, reliable localization may not always be feasible. Partially Observable Markov Decision Processes (POMDPs) provide one way to maximize the certainty of reaching the goal state, but at the cost of computational intractability for large state spaces. The method we propose explicitly models the uncertainty of the robot's position as a state variable, and generates trajectories through the augmented pose-uncertainty space. By minimizing the positional uncertainty at the goal, the robot reduces the likelihood it becomes lost. We demonstrate experimentally that coastal navigation reduces the uncertainty at the goal, especially with degraded localization.

ICRA Conference 1999 Conference Paper

Coastal Navigation: Mobile Robot Navigation with Uncertainty in Dynamic Environments

• Nicholas Roy
• Wolfram Burgard
• Dieter Fox
• Sebastian Thrun

Ships often use the coasts of continents for navigation in the absence of better tools such as GPS, since being close to land allows sailors to determine with high accuracy where they are. Similarly for mobile robots, in many environments global and accurate localization is not always feasible. Environments can lack features, and dynamic obstacles such as people can confuse and block sensors. We demonstrate a technique for generating trajectories that take into account both the information content of the environment, and the density of the people in the environment. These trajectories reduce the average positional certainty as the robot moves, reducing the likelihood the robot will become lost at any point. Our method was successfully implemented and used by the mobile robot Minerva, a museum tourguide robot, for a 2 week period in the Smithsonian National Museum of American History.

ICRA Conference 1999 Conference Paper

MINERVA: A Second-Generation Museum Tour-Guide Robot

• Sebastian Thrun
• Maren Bennewitz
• Wolfram Burgard
• Armin B. Cremers
• Frank Dellaert
• Dieter Fox
• Dirk Hähnel
• Charles R. Rosenberg

This paper describes an interactive tour-guide robot, which was successfully exhibited in a Smithsonian museum. During its two weeks of operation, the robot interacted with thousands of people, traversing more than 44 km at speeds of up to 163 cm/sec. Our approach specifically addresses issues such as safe navigation in unmodified and dynamic environments, and short-term human-robot interaction. It uses learning pervasively at all levels of the software architecture.

ICRA Conference 1999 Conference Paper

Online Self-Calibration for Mobile Robots

• Nicholas Roy
• Sebastian Thrun

This paper proposes a statistical method for calibrating the odometry of mobile robots. In contrast to previous approaches, which require explicit measurements of actual motion when calibrating a robot's odometry, the algorithm proposed here uses the robot's sensors to automatically calibrate the robot as it operates. An efficient, incremental maximum likelihood algorithm enables the robot to adapt to changes in its kinematics online, as they occur. The appropriateness of the approach is demonstrated in two large-scale environments, where the amount of odometric error is reduced by an order of magnitude.

AAAI Conference 1996 Conference Paper

Mobile Robot Navigation and Control: A Case Study

• Nicholas Roy

Robotic systems (and in particular mobile autonomous agents) embody a complex interaction of computational processes, mechanical systems, sensors, and communications hardware. System integration can present significant difficulties to the construction of a real system, because the hardware is often built around convenience of design rather than convenience of system integration. Nonetheless, in order for robots to perform real-world tasks such as navigation, localization and exploration, the different subsystems of motion, sensing and computation must be merged into a single, realisable unit. Our group is investigating particular problems in the domain of computational perception, in the context of mobile robotics. In particular, we are concerned with environment exploration, position estimation, and map construction. We have several mobile platforms integrating different sensing modalities, which we are able to control simultaneously from a single source.

ICRA Conference 1996 Conference Paper

Surface sensing and classification for efficient mobile robot navigation

• Nicholas Roy
• Gregory Dudek
• Paul Freedman

Mobile robot navigation and localization is frequently aided by, or even dependent upon, a good estimate of the rate of dead-reckoning error accumulation. Sensor data can be used for position estimation, but this often involves overheads in acquiring and processing the data. By sensing and then classifying the surface type, an estimate of the rate of error accumulation for dead-reckoning allows one to estimate accurately how often localization, including sensor data acquisition, must be performed. The authors describe experiments in which a boom-mounted microphone is tapped on different floor materials, much as a blind man might tap his cane. The acoustic signature arising from the contact is then used to classify the floor type by comparing a windowed power spectrum of the acoustic signature with one of a family of prototypical signatures generated statistically from the same material. The technique is low-cost, involves limited computational expense, and performs very well.