An adaptive roadmap guided Multi-RRTs strategy for single query path planning

摘要

During the past decade, Rapidly-exploring Random Tree (RRT) and its variants are shown to be powerful sampling based single query path planning approaches for robots in high-dimensional configuration space. However, the performance of such tree-based planners that rely on uniform sampling strategy degrades significantly when narrow passages are contained in the configuration space. Given the assumption that computation resources should be allocated in proportion the geometric complexity of local region, we present a novel single-query Multi-RRTs path planning framework that employs an improved Bridge Test algorithm to identify global important roadmaps in narrow passages. Multiple trees can grown from these sampled roadmaps to explore sub-regions which are difficult to reach. The probability of selecting one particular tree for expansion and connection, which can dynamically updated by on-line learning algorithm based on the historic results of exploration, guides the tree through narrow passage rapidly. Experimental results show that the proposed approach gives substantial improvement in planning efficiency over a wide range of single-query path planning problems.