Rapidly-exploring random tree

Rapidly-exploring random tree

A Rapidly-exploring Random Tree (RRT) is a data structure and algorithm designed for efficiently searching nonconvex, high-dimensional search spaces. Simply put, the tree is constructed in such a way that any sample in the space is added by connecting it to the closest sample already in the tree.

RRT has been widely used in robotics path planning.cite journal
author = Lavalle, S.M.
year = 1998
title = Rapidly-exploring random trees: A new tool for path planning
journal = Computer Science Dept, Iowa State University, Tech. Rep. TR
pages = 98-11
url = http://citeseer.ist.psu.edu/311812.html
accessdate = 2008-06-30]

Introduction

RRTs are constructed incrementally in a way that quickly reduces the expected distance of a randomly-chosen point to the tree. RRTs are particularly suited for path planning problems that involve obstacles and differential constraints (nonholonomic or kinodynamic). RRTs can be considered as a technique for generating open-loop trajectories for nonlinear systems with state constraints. An RRT can be intuitively considered as a Monte-Carlo way of biasing search into largest Voronoi regions. Some variations can be considered as stochastic fractals. Usually, an RRT alone is insufficient to solve a planning problem. Thus, it can be considered as a component that can be incorporated into the development of a variety of different planning algorithms. [http://msl.cs.uiuc.edu/rrt/about.html About RRTs, by Steve LaValle]

Algorithm

For a general configuration space "C", the algorithm in pseudocode is as follows:

Input: Initial configuration "q""init", number of vertices in RRT "K", incremental distance "Δq") Output: RRT graph "G" "G".init("q""init") for "k" = 1 to "K" "q""rand" ← RAND_CONF() "q""near" ← NEAREST_VERTEX("q""rand", "G") "q""new" ← NEW_CONF("q""near", "Δq") "G".add_vertex("q""new") "G".add_edge("q""near", "q""new") return "G"

In the algorithm above, "RAND_CONF" grabs a random configuration "q""rand" in "C". This may be replaced with a function "RAND_FREE_CONF" that uses samples in "C""free", while rejecting those in "C""obs" using some collision detection algorithm.

"NEAREST_VERTEX" is a straight-forward function that runs through all vertexes "v" in graph "G", calculates the distance between "q""rand" and "v" using some measurement function thereby returning the nearest vector.

"NEW_CONF" selects a new configuration "q""new" by moving an incremental distance "Δq" from "q""near" in the direction of "q""rand".

Visualization

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Rapidly-exploring random tree — (RRT) (dt. etwa schnell erkundender zufälliger Baum) ist ein Suchalgorithmus (und dessen zugrunde liegende Baum Datenstruktur), der hochdimensionale Suchräume zufällig nach möglichen Pfaden absucht. In der Robotik werden der Algorithmus und… …   Deutsch Wikipedia

  • Randomized algorithm — Part of a series on Probabilistic data structures Bloom filter · Skip list …   Wikipedia

  • RRT — or Rrt may refer to:* Registered Respiratory Therapist * Radio Reconnaissance Platoon * Rapidly exploring random tree * Renal replacement therapy …   Wikipedia

  • RRT — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.   Sigles d’une seule lettre   Sigles de deux lettres > Sigles de trois lettres   Sigles de quatre lettres …   Wikipédia en Français

  • RRT — Rapid Response Team (Community » Law) Rapid Response Team (Governmental » Military) ** Regional Response Team (Community » Law) ** Regional Response Team (Governmental » US Government) ** Regional Response Team (Governmental » Military) * Rail… …   Abbreviations dictionary

  • literature — /lit euhr euh cheuhr, choor , li treuh /, n. 1. writings in which expression and form, in connection with ideas of permanent and universal interest, are characteristic or essential features, as poetry, novels, history, biography, and essays. 2.… …   Universalium

  • evolution — evolutional, adj. evolutionally, adv. /ev euh looh sheuhn/ or, esp. Brit., /ee veuh /, n. 1. any process of formation or growth; development: the evolution of a language; the evolution of the airplane. 2. a product of such development; something… …   Universalium

  • Life Sciences — ▪ 2009 Introduction Zoology       In 2008 several zoological studies provided new insights into how species life history traits (such as the timing of reproduction or the length of life of adult individuals) are derived in part as responses to… …   Universalium

  • Europe, history of — Introduction       history of European peoples and cultures from prehistoric times to the present. Europe is a more ambiguous term than most geographic expressions. Its etymology is doubtful, as is the physical extent of the area it designates.… …   Universalium

  • Ecology — For other uses, see Ecology (disambiguation). Ecology …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”