Hierarchical random exploring with multiple linking modes

Abstract

Narrow passages in the configuration space pose challenge for sampling-based planners. In this paper, the conventional wisdom of ”divide and conquer” is adopted to design a hierarchical strategy to address this challenging problem. Rapidly-exploring random tree (RRT) is taken as an example to illustrate the proposed strategy. A hybrid map which consists of a topological map and a set of metric maps is built up to represent the configuration space and information on the narrow passages is included in the topological map. The path from the starting configuration to the goal one is divided into segments using the information on the narrow passages. The RRT runs independently to search for a sub-path for each segment. The overall path is obtained by concatenating all the sub-paths. In addition, to improve the possibility of avoiding obstacles, two more circle-based linking modes are introduced to the RRT planner. Experimental results show that the planning time can be reduced significantly using the proposed planning methods. As a result, the success rate of path planning can be improved if the time for planning is limited.