Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Algorithms & Applications Group
OBRRT: An Obstacle-Based Rapidly-Exploring Random Tree

Project Personnel:Samuel Rodriguez,Nancy Amato

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. The proposed planner performs best when expanding from narrow or difficult areas.

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.
Proceedings(ps, pdf, abstract)

Supported by NSF, Dept. of Education, Texas Higher Education Coordinating Board

Project Alumni:Jyh-Ming Lien,Xinyu Tang

Parasol Home | Research | People | General info | Seminars | Resources  

Parasol Laboratory, 425 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112 
parasol-admin@cse.tamu.edu      Phone 979.458.0722     Fax 979.458.0718 

Department of Computer Science and Engineering | Dwight Look College of Engineering Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science and Engineering Engineering TAMU
Web Accessibility Policy and Law - Web Accessibility and Usability Standards  -   Contact Webmaster