  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.

Robotics