Posterior Sampling for Anytime Motion Planning on Graphs with Expensive-to-Evaluate Edges

By Brian Hou, Sanjiban Choudhury, Gilwoo Lee, Aditya Mandalika, Siddhartha S. Srinivasa. 2020

14 citations recorded by the source corpus.

Collision checking is a computational bottleneck in motion planning, requiring lazy algorithms that explicitly reason about when to perform this computation. Optimism in the face of collision uncertainty minimizes the number of checks before finding the shortest path. However, this may take a prohibitively long time to compute, with no other feasible paths discovered during this period. For many real-time applications, we instead demand strong anytime performance, defined as minimizing the cumulative lengths of the feasible paths yielded over time. We introduce Posterior Sampling for Motion Planning (PSMP), an anytime lazy motion planning algorithm that leverages learned posteriors on edge collisions to quickly discover an initial feasible path and progressively yield p shorter paths. PSMP obtains an expected regret bound of $\tilde O(\sqrt {\mathcal{S}\mathcal{A}T} )$ and outperforms comparative baselines on a set of 2D and 7D planning problems.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Probabilistic & Bayesian Methods, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Probabilistic & Bayesian Methods

In Algorithms & Complexity

Citations in the corpus

Habitat 2.0: Training Home Assistants to Rearrange their Habitat (2021, background): “[91] Brian Hou, Sanjiban Choudhury, Gilwoo Lee, Aditya Mandalika, and Siddhartha S Srinivasa.”