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.

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.

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.