Rapidly-Exploring Random Tree (RRT)

The algorithm's defining characteristic is its probabilistic, sampling-driven approach. Instead of exploring the entire configuration space, it incrementally builds a tree by randomly sampling points and extending the nearest node in the tree towards them. This creates a bias towards unexplored regions, causing the tree to rapidly expand and fill the free space. It is particularly effective in high-dimensional spaces where exhaustive search is computationally infeasible.

RRT is designed as a single-query planner. Given a specific start and goal configuration, it builds a search tree from scratch for that single problem instance. This contrasts with multi-query planners (like PRM) that pre-compute a roadmap reusable for many queries. This makes RRT highly efficient for problems where only one path is needed, but less so for environments requiring repeated planning from varying start/goal pairs.

While basic RRT is probabilistically complete (guaranteed to find a path if one exists, given infinite time), it does not guarantee path quality. The RRT variant* introduces a rewiring step to achieve asymptotic optimality. After adding a new node, RRT* examines nearby nodes to see if connecting through the new node provides a lower-cost path, locally optimizing the tree structure. Given infinite samples, RRT* converges to an optimal solution.

A key strength is its adaptability to complex kinematic and dynamic constraints. The core EXTEND function can be tailored. For car-like robots with non-holonomic constraints, extensions use dubins or reeds-shepp curves. For systems with dynamics (e.g., drones), extensions can simulate forward dynamics over a short timestep. This allows RRT to plan feasible trajectories in the robot's state-space, not just its geometric configuration space.

RRT-Connect is a major efficiency improvement that grows two trees simultaneously: one from the start and one from the goal. Each iteration alternately extends one tree towards a random sample and then tries to extend the other tree directly towards the newest node of the first tree. This greedy connection heuristic often leads to rapid connection of the two trees, significantly reducing planning time compared to growing a single tree.

In agentic systems for corrective action planning, RRT provides a model for exploring the space of possible recovery actions. When an error is detected, the agent's state is the start node. The goal region is the set of valid, corrected states. RRT's random exploration allows the agent to discover novel, non-obvious sequences of tool calls or state adjustments to recover from failures, especially in complex, constrained software environments.

The computational problem of finding a sequence of valid configurations or states that moves an object, such as a robot or autonomous vehicle, from a start to a goal while avoiding obstacles and satisfying kinematic or dynamic constraints. RRT is a sampling-based algorithm specifically designed to solve this problem in high-dimensional or complex spaces where traditional grid-based methods fail. Key approaches include:

• Probabilistic Roadmaps (PRM): Builds a network of feasible configurations in the free space.
• Potential Fields: Guides a robot using attractive (goal) and repulsive (obstacle) forces.
• Optimization-based methods: Directly optimize a trajectory for smoothness and efficiency.

A heuristic search algorithm for sequential decision processes that, like RRT, builds a tree through random sampling. However, MCTS is designed for decision-making in discrete spaces (like games) rather than continuous motion planning. It operates by iterating four phases:

• Selection: Traverse the tree using a policy (e.g., UCB) to select a node.
• Expansion: Add a new child node to the tree.
• Simulation (Rollout): Run a random simulation from the new node to a terminal state.
• Backpropagation: Update the node statistics (e.g., win count, value) back up the tree. This balance of exploration vs. exploitation makes it powerful for games like Go and complex planning under uncertainty.

A classic graph traversal and pathfinding algorithm that guarantees finding the shortest path. Unlike the sampling-based RRT, A* requires a discretized representation of the space (e.g., a grid). It combines:

• g(n): The exact cost from the start node to node n.
• h(n): A heuristic estimate of the cost from n to the goal (e.g., Euclidean distance). It expands the node with the lowest f(n) = g(n) + h(n). While optimal, it suffers from the curse of dimensionality in high-dimensional continuous spaces, which is the primary motivation for algorithms like RRT.

An advanced control method that uses an explicit dynamic model of a system to predict its future behavior over a finite horizon. At each control step, it solves a constrained optimization problem to compute optimal control actions, then executes the first step and repeats. In the context of motion planning, MPC can be used for local trajectory optimization and execution. RRT can provide a feasible global path, which MPC then refines and tracks while handling dynamic constraints and disturbances in real-time, creating a powerful hierarchical planning and control stack.

A seminal sampling-based motion planning algorithm that, like RRT, is designed for high-dimensional spaces. The key difference lies in its two-phase approach:

1. Learning Phase: Randomly sample configurations in the free space and connect nearby ones with simple local planners to form a graph (roadmap).
2. Query Phase: Connect the start and goal to the roadmap and find a path within the graph. PRM is multi-query (the roadmap is built once for many queries), whereas basic RRT is single-query (builds a new tree for each problem). PRM excels in static environments where many paths need to be found.

An asymptotically optimal variant of the RRT algorithm. While standard RRT finds a feasible path, RRT* iteratively rewires the tree to improve path quality (e.g., minimize length). After adding a new node, it examines nearby nodes to see if they could be reached with a lower cost via the new node, and if so, it changes their parent. This rewiring process allows the tree to converge towards the optimal solution as the number of samples increases. RRT* is a foundational algorithm in optimal sampling-based motion planning, balancing the exploration efficiency of RRT with convergence to optimality.