Dynamic Region RRT

WAFR 2016

Jory Denny, Read Sandström, Andrew Bregger, and Nancy Amato

Motivation

In many motion planning problems, valid solutions are highly correlated with the workspace geometry.

How can we exploit this relationship in a general manner that works for any sampling-based planner?

Core Idea

A Reeb graph (red) of a three dimensional torus (grey).

We can construct a compact model of the workspace topology using a Reeb graph.

This produces a workspace skeleton that captures all of the distinct homotopy classes in the environment.

This workspace skeleton makes an ideal high-level guide for a sampling-based planner.

Dynamic Region RRT

We can use the workspace skeleton in conjunction with dynamic sampling regions to guide a tree-based planner (such as RRT) through an environment.

To begin, we read in a geometric representation of the workspace and compute its workspace skeleton, as shown here.

This step doesn't depend on the robot or query.

Dynamic Region RRT

Next, we consider the query at hand, which describes the start and goal position for our robot.

We direct the edges of the workspace skeleton so that they lead outward from the start position.

We then prune the workspace skeleton of any edges that don't lead towards the goal.

Dynamic Region RRT

The generic workspace skeleton is now customized for our problem.

To use it as a guide for motion planning, we create a dynamic sampling region at the skeleton node that is nearest to the start position.

Dynamic Region RRT

To direct our motion plan along the workspace skeleton, we sample configurations within our dynamic sampling region.

Whenver we succesfully connect to a new sample within a region, we advance that region along the skeleton edge.

Dynamic Region RRT

When the region reaches the next skeleton node, it is removed.

We spawn a new region for each edge that leaves the skeleton node.

Because the skeleton edges represent workspace homotopies that lead to the goal, the RRT is directed through the potentially valid paths in workspace.

Conclusion

Dynamic Region RRT provides topological guidance to a sampling-based planner.

We observe large speedups using this guidance whenver the valid solutions in C_space are strongly correlated to valid solutions in workspace.