|
Tree-based path planners have been shown to be well suited to solve
various high dimensional motion planning problems. Here we
present modifications that can be made to the Rapidly-Exploring Random
Tree (RRT) path planning algorithm that allows it to explore narrow
passages or difficult areas more effectively. We show that both
workspace obstacle information and C-space information can be
used when deciding which direction to grow. The method includes
many ways to grow the tree, some taking into account the obstacles in
the environment.
 |
|
 |
|
A tree grown using basic expansion |
|
A tree grown using obstacle information |
The presented algorithm modifies the basic RRT expansion algorithm. Modifications
are made to how a source node is expanded and how extension is done from a source
configuration.
Possible Obstacle Vectors
|
Growth Methods:
Basic Extension
Random position, Same orientation
Random obstacle vector, Random orientation
Random obstacle vector, Same orientation
Rotation followed by Extension
Trace obstacle, Random Orientation
Trace obstacle, Same Orientation
Trace C-space obstacle
Medial Axis Push
|
Using obstacle hints for directions to grow a tree for path planning can be beneficial,
especially when exploring difficult areas. Results can be viewed in the paper (listed below).
The proposed planner performs best when expanding from narrow or difficult areas.
Papers
An Obstacle-Based Rapidly-Exploring Random Tree, Samuel Rodriguez, Xinyu Tang, Jyh-Ming Lien, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot.
Autom. (ICRA), pp. 895-900, Orlando, FL, May 2006. Also, Technical Report, TR05-009, Parasol Laboratory, Department of Computer Science, Texas A&M University, Sep 2005.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)
|
