Authors: Jory Denny, Read Sandström, Andrew Bregger, Nancy M. Amato

Venue: Algorithmic Foundations of Robotics XII. Springer Proceedings in Advanced Robotics (SPAR). The 2016 Workshop on the Algorithmic Foundations of Robotics (WAFR)
DOI: 10.1007/978-3-030-43089-4_41
Link to Publication

Abstract:
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. 

@article{Amato-drrrt-2020, 
 author = {Jory Denny and Read Sandström and Andrew Bregger and Nancy M. Amato}, 
 doi = {10.1007/978-3-030-43089-4\_41}, 
 journal = {Algorithmic Foundations of Robotics XII. Springer Proceedings in Advanced Robotics (SPAR)}, 
 note = {Presented at the 2016 Workshop on the Algorithmic Foundations of Robotics (WAFR).}, 
 pages = {640-655}, 
 publisher = {Springer, Cham.}, 
 title = {Dynamic Region-biased Rapidly-exploring Random Trees}, 
 volume = {13}, 
 year = {2020} 
}