Angelic abstractions for optimal robotic planning

Using abstraction, robots can address complicated tasks without sacrificing completeness or optimality.

Fast uncertainty quantification

Generalized kernel estimation allows autonomous agents to better understand what they do not know, improving robustness and performance.

Selected Publications

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.
In IJCAI, 2018

We present the first asymptotically optimal algorithm for motion planning problems with piecewise-analytic differential constraints, like manipulation or rearrangement planning. This class of problems is characterized by the presence of differential constraints that are local in nature: a robot can only move an object once the object has been grasped. These constraints are not analytic and thus cannot be addressed by standard differentially constrained planning algorithms. We demonstrate 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. This approach does not require a hand-coded symbolic abstraction. We demonstrate our approach in simulation on a simple manipulation planning problem, and show it generates lower-cost plans than a sequential task and motion planner.
In WAFR, 2016

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 $\mathcal{O}(\log N)$ time and $\mathcal{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.
In NIPS, 2014


. Sensor-Based Reactive Symbolic Planning in Partially Known Environments. In ICRA, 2018.

PDF Project Video

. PROBE-GK: Predictive Robust Estimation using Generalized Kernels. In ICRA, 2016.

Preprint PDF Project Supplement

. Nonparametric Bayesian inference on multivariate exponential families. In NIPS, 2014.

PDF Project

. CELLO-EM: Adaptive Sensor Models without Ground Truth. In IROS, 2013.

PDF Project

. Predictive Parameter Estimation for Bayesian Filtering. Master’s thesis, 2013.

PDF Project

. CELLO: A Fast Algorithm for Covariance Estimation. In IROS, 2013.

PDF Project

. Sensor-Based Reactive Execution of Symbolic Rearrangement Plans by a Legged Mobile Manipulator. In IROS, 0001.

PDF Project Video


  • 32 Vassar St, 32-33x, Cambridge, Massachusetts, 02139, USA