Rapidly-exploring Random Tree (RRT)

The RRT (Rapidly-exploring Random Tree) solver implements the classic incremental tree-growth motion planning algorithm. It explores continuous configuration spaces by iteratively sampling random points, finding their nearest neighbor in the tree, steering toward the sample by a step size \eta, and adding valid nodes/edges to the roadmap.

Architectural Design & Algorithm Flow

  • Base Contract: Inherits from SamplingSolver.

  • Multi-Robot C-Space: Operates in composite d-dimensional configuration space using Point_d representations, enabling joint single- and multi-robot tree expansion.

  • Steering Function: Implements steer(p_near, p_rand, eta) to project incremental motion vectors bounded by step length \eta.

  • Roadmap Construction: build_roadmap() initializes the tree root at the start configuration, repeatedly samples free configurations via injected Sampler, queries NearestNeighbors, performs collision verification on edges, and attempts final connection to the goal configuration.

digraph rrt_algorithm_flow { rankdir=TB; node [fontname="Helvetica", fontsize=10, margin="0.15,0.1"]; edge [fontname="Helvetica", fontsize=9]; start [label="Start Configuration\n(Tree Root Node)", shape=ellipse, style=filled, fillcolor="#E3F2FD", color="#1565C0"]; sample [label="Sample Free Point\n(Sampler Strategy)", shape=box, style="filled,rounded", fillcolor="#C8E6C9", color="#2E7D32"]; nn [label="Find 1-Nearest Neighbor\n(k-d Tree Search)", shape=box, style="filled,rounded", fillcolor="#FFF3E0", color="#E65100"]; steer [label="Steer Vector by eta\nsteer(p_near, p_rand, eta)", shape=box, style="filled,rounded", fillcolor="#FFFDE7", color="#F57F17"]; collision [label="Edge Collision Check\n(collision_detection)", shape=diamond, style=filled, fillcolor="#F3E5F5", color="#7B1FA2"]; add_node [label="Add New Node & Edge\nto Tree Graph", shape=box, style="filled,rounded", fillcolor="#D1C4E9", color="#512DA8"]; discard [label="Discard Candidate\n(In Collision)", shape=box, style="filled,rounded", fillcolor="#FFCDD2", color="#C62828"]; check_target [label="Num Landmarks Met?", shape=diamond, style=filled, fillcolor="#E0F7FA", color="#00838F"]; connect_goal [label="Connect Nearest Node\nto Target Goal", shape=box, style="filled,rounded", fillcolor="#B2EBF2", color="#006064"]; search [label="Run A* Search on Tree", shape=ellipse, style=filled, fillcolor="#C8E6C9", color="#2E7D32"]; start -> sample; sample -> nn; nn -> steer; steer -> collision; collision -> add_node [label="Collision Free"]; collision -> discard [label="Collision Found"]; discard -> sample [label="Next Sample"]; add_node -> check_target; check_target -> sample [label="No (N < limit)"]; check_target -> connect_goal [label="Yes (N >= limit)"]; connect_goal -> search; }

RRT Incremental Tree Expansion Flow

Parameters & Configuration

RRT Parameters

Parameter

Description

Default

Type

num_landmarks

Number of successful landmark samples to add to the tree

2000

int

eta

Maximum steering step distance

1

FT

sampler

Sampling strategy distribution

UniformPointSampler

Sampler

metric

Distance metric policy

EuclideanMetric

Metric

Usage Example

from discopygal.solvers.rrt.rrt import RRT
from discopygal.solvers_infra import Scene

# Load scene and construct solver
solver = RRT.init_solver(num_landmarks=1500, eta=0.5)
path_collection = solver.solve(scene)

API Reference

class discopygal.solvers.rrt.rrt.RRT(num_landmarks, eta, **kwargs)

Bases: SamplingSolver

Implementation of the plain RRT algorithm. Supports multi-robot motion planning, though might be inefficient for more than two-three robots.

Parameters:

  • num_landmarks (int) – number of landmarks to sample

  • eta (FT) – maximum distance when steering

  • nearest_neighbors (NearestNeighbors or None) – a nearest neighbors algorithm. if None then use sklearn implementation

  • metric (Metric or None) – a metric for weighing edges, can be different then the nearest_neighbors metric! If None then use euclidean metric

  • sampler (Sampler) – sampling algorithm/method. if None then use uniform sampling

build_roadmap() → Roadmap

Constructs the roadmap of points in the configuration space which a path will be searched on to find a solution. Every sampling solver should implement how to build the roadmap.

Returns:

The built roadmap. Each node represents a point in configuration space (dimension = 2*robots_num)

Return type:

Roadmap

classmethod get_arguments()

Return a list of arguments and their description, defaults and types. Can be used by a GUI to generate fields dynamically. Should be overridded by solvers.

Returns:

arguments dict

Return type:

dict

steer(p_near, p_rand, eta) → Point_d

Steer in eta units from p_near towards p_rand