Dynamic Region-biased Rapidly-exploring Random Trees

Current state-of-the-art motion planners rely on samplingbased planning to explore the problem space for a solution. However, sampling valid configurations in narrow or cluttered workspaces remains a challenge. If a valid path for the robot correlates to a path in the workspace, then the planning process can employ a representation of the workspace that captures its salient topological features. Prior approaches have investigated exploiting geometric decompositions of the workspace to bias sampling; while beneficial in some environments, complex narrow passages remain challenging to navigate. In this work, we present Dynamic Region-biased RRT, a novel samplingbased planner that guides the exploration of a Rapidly-exploring Random Tree (RRT) by moving sampling regions along an embedded graph that captures the workspace topology. These sampling regions are dynamically created, manipulated, and destroyed to greedily bias sampling through unexplored passages that lead to the goal. We show that our approach reduces online planning time compared with related methods on a set of maze-like problems.