Sparser Sparse Roadmaps
This work addresses offline roadmap generation for robotic planning, offering significant memory reduction and faster planning for high-dimensional spaces, though it is incremental in nature.
The paper tackles the problem of generating sparse roadmap spanners for robotic planning by presenting a hybrid sampling method that produces graphs 79% smaller than existing approaches while maintaining equivalent path quality.
We present methods for offline generation of sparse roadmap spanners that result in graphs 79% smaller than existing approaches while returning solutions of equivalent path quality. Our method uses a hybrid approach to sampling that combines traditional graph discretization with random sampling. We present techniques that optimize the graph for the L1-norm metric function commonly used in joint-based robotic planning, purposefully choosing a $t$-stretch factor based on the geometry of the space, and removing redundant edges that do not contribute to the graph quality. A high-quality pre-processed sparse roadmap is then available for re-use across many different planning scenarios using standard repair and re-plan methods. Pre-computing the roadmap offline results in more deterministic solutions, reduces the memory requirements by affording complex rejection criteria, and increases the speed of planning in high-dimensional spaces allowing more complex problems to be solved such as multi-modal task planning. Our method is validated through simulated benchmarks against the SPARS2 algorithm. The source code is freely available online as an open source extension to OMPL.