Dancing PRM*: Simultaneous Planning of Sampling and Optimization with Configuration Free Space Approximation

Abstract

A recent trend in optimal motion planning has broadened the research area toward the hybridization of sampling, optimization and grid-based approaches. We can expect that synergy from such integrations leads to overall performance improvement, but seamless integration and generalization is still an open problem. In this paper, we suggest a hybrid motion planning algorithm utilizing a sampling-based and optimization-based planner while simultaneously approximating a configuration free space. Unlike conventional optimization-based approaches, the proposed algorithm does not depend on a priori information or resolution-complete factors, e.g., a distance field. Ours instead learns spatial information on the fly by exploiting empirical information during the execution, and decentralizes the information over the constructed graph for efficient access. With the help of the learned information, our optimization-based local planner exploits the local area to identify the connectivity of configuration free space without depending on the precomputed domain knowledge. To show the novelty of proposed algorithm, we evaluate it against other asymptotic optimal planners in both synthetic and complex benchmarks with varying degrees of freedom. We also discuss the performance improvement, properties and limitations we have observed.