A slicing connection strategy for constructing PRMs in high-dimensional cspaces

Abstract

This paper presents a connection strategy for PRM-based motion planning in high-dimensional configuration spaces. The connection strategy identifies components of motion during the roadmap construction and plans the roadmap edges on a sequence of configuration slices approximating the configuration spaces of the components. The goal of the approach is to extend the dimensionality of the problems PRM planners can solve, and the strategy it deploys is dimensional subdivision. We report experimental results on serpentine robots with up to 150 degrees-of-freedom and multi-robot systems with up to 144 degrees-of-freedom. The test problems are beyond the capability of a representative state-of-the-art PRM based planner, and the approach presented in this paper enables the use of motion planning methods in solving new high-dimensional problems