Home research People General Info Seminars Resources Intranet
Time - Wednesday, December 14, 2016, 4:00 pm
Location - 302 HRBB

Dynamic Region-biased Rapidly-exploring Random Trees

Read Sandstrom
Parasol Laboratory, Department of Computer Science
Texas A&M University


Current state-of-the-art motion planners rely on sampling-based planning to

rapidly cover and explore the problem space for a solution. However, sampling valid configurations in narrow or cluttered workspaces remains a challenge because the free space is relatively restricted. If a valid path for the robot is highly correlated with a path in the workspace, then the planning process would benefit from a representation of the workspace that captured 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 sampling-based

planner that guides the exploration of a Rapidly-exploring Random Tree (RRT) by dynamically 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 compare our approach with related methods on a set of maze-like problems.


Read Sandstrom is a fourth year PhD student studying motion planning under Dr. Nancy Amato. After receiving his bachelor of science in physics from Texas A&M University in spring 2011, Read worked for Intel as a manufacturing technician for two years before joining Parasol lab. He is currently researching topology-guided motion planning and has recently started investigating methods for the coordination of heterogeneous robot teams. He also has interest in general robotics, AI, and automation.