Robot control
Rapidly-exploring random tree
Definition
A rapidly-exploring random tree is a sampling-based structure that grows through a configuration or state space toward sampled targets. Motion planners use it to search for feasible routes through spaces with obstacles and movement constraints.
Also known as: RRT, Rapidly-exploring random trees
Updated
Samples pull the tree into new regions
An RRT starts from an initial state. It samples a target, finds a nearby tree node, and attempts a short extension toward the target. LaValle's description explains how this procedure encourages exploration of high-dimensional spaces rather than simply taking a random walk.
A humanoid arm planner can use an RRT to search among joint configurations when a direct reach intersects an obstacle.
The local planner determines feasible growth
The Modern Robotics treatment identifies sampling, the distance metric, and the local extension method as key design choices. An extension must respect the relevant movement constraints and pass collision checks before becoming part of a valid plan.
Finding a route is not optimizing it
Basic RRT planning does not guarantee the shortest or lowest-cost path. Continuing to grow an ordinary RRT is also not equivalent to using RRT*, whose rewiring supports asymptotic optimality under its assumptions. A returned route still needs appropriate timing and execution control. The tree is one component of a motion-planning system.
Sources
Related terms
Motion planning
Motion planning finds a robot movement from an initial state to a goal while satisfying constraints such as collision avoidance. A planner may produce a geometric path, a timed trajectory, or a sequence of controls.
Configuration space
Configuration space is the set of all possible configurations of a robot or mechanical system. Each point specifies the entire modeled arrangement, and the space has as many local dimensions as the system has degrees of freedom.
Probabilistic roadmap
A probabilistic roadmap is a motion-planning graph built by sampling collision-free configurations and connecting nearby samples with feasible local paths. The graph can then answer start-to-goal queries within the modeled environment.