Sparse Multilevel Roadmaps for High-Dimensional Robot Motion Planning
This work addresses the problem of efficient motion planning for robots in complex, high-dimensional environments, representing an incremental improvement over prior methods by generalizing sparse roadmaps with multilevel abstractions.
The paper tackles the scalability issue of sparse roadmaps in high-dimensional robot motion planning by introducing a novel algorithm, the sparse multilevel roadmap planner (SMLR), which uses multilevel abstractions and fiber bundles to improve performance, demonstrating superior results on challenging problems including high-dimensional, narrow passage, and infeasible cases.
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.