Author name cluster

William Vega-Brown

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers

2 author rows

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.

Details

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 uniﬁed 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 stratiﬁed 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.

PDF Details

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.

PDF Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

PDF Details

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.

Details

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.

PDF Details

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.

PDF Details

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.

Details

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.

Details