  Sparse roadmaps are important to compactly represent state spaces, to
determine problems to be infeasible and to terminate in finite time. However,
sparse roadmaps do not scale well to high-dimensional planning problems. In
prior work, we showed improved planning performance on high-dimensional
planning problems by using multilevel abstractions to simplify state spaces. In
this work, we generalize sparse roadmaps to multilevel abstractions by
developing a novel algorithm, the sparse multilevel roadmap planner (SMLR). To
this end, we represent multilevel abstractions using the language of fiber
bundles, and generalize sparse roadmap planners by using the concept of
restriction sampling with visibility regions. We argue SMLR to be
probabilistically complete and asymptotically near-optimal by inheritance from
sparse roadmap planners. In evaluations, we outperform sparse roadmap planners
on challenging planning problems, in particular problems which are
high-dimensional, contain narrow passages or are infeasible. We thereby
demonstrate sparse multilevel roadmaps as an efficient tool for feasible and
infeasible high-dimensional planning problems.
