Sparse Multilevel Roadmaps for High-Dimensional Motion Planning

Note: This is a blog post about the paper Sparse Multilevel Roadmaps on Fiber Bundles for High-Dimensional Motion Planning by Andreas Orthey and Marc Toussaint which you can find here: https://arxiv.org/abs/2011.00832

To solve robotic tasks we often need to optimize long-horizon motions involving frequent calls to sampling-based motion planning algorithms. Those planning algorithms search motions by growing roadmaps on the robots state space, but often cannot terminate on infeasible problems. To address infeasible problems we can make use of sparse roadmaps. However, sparse roadmaps often do not work efficiently on high-dimensional state spaces — they basically require a long time to terminate.

To address this problem, we introduce sparse multilevel roadmaps. Sparse multilevel roadmaps generalize sparse roadmaps to multilevel abstractions, while giving guarantees on probabilistic completeness and asymptotic near-optimality, which means that in the limit of time going to infinity we will find a near-optimal path if one exists. The picture below shows the difference of dense roadmaps, sparse roadmaps and sparse multilevel roadmaps on a torus. Sparse multilevel roadmaps can use information from different abstraction levels (here the circle) to quickly determine if a given problem is feasible or infeasible.

To show how sparse multilevel roadmaps improve upon sparse roadmaps, we look at four scenarios (paper has eight). Please see the figure below. In the first two scenarios, a drone has to fly through a net from a green start to a red goal state. Using sparse multilevel roadmaps, we need 0.23s and 0.72 to determine the left problem to be feasible and the right problem to be infeasible. Sparse roadmaps need only 0.16s for the feasible scenario but timeout (>60s) on the infeasible scenario.

The last two scenarios involve a PR2 robot with 34 degrees of freedom. Using sparse multilevel roadmaps, we need 9.25s and 0.32s to determine the problem to be feasible (left) and infeasible (right), respectively. Sparse roadmaps time out on both scenarios (>60s).

Please check out the paper for more scenarios and a proof of asymptotic near-optimality: https://arxiv.org/abs/2011.00832.