RRT (Rapidly-exploring Random Tree)

RRT is probabilistically complete, meaning if a feasible path exists, the probability of the algorithm finding it approaches 1.0 as the number of samples (iterations) goes to infinity. This is a key guarantee that differentiates it from heuristic methods, which may get stuck in local minima.

• Not deterministic: It does not guarantee a solution in finite time, only that the chance of failure decays with more computation.
• Contrast with Resolution Completeness: Grid-based search (like A*) is resolution-complete—it will find a path if one exists at the given discretization level, but scales poorly with dimensionality.

RRT is designed as a single-query planner. It builds a search tree from a specific start configuration toward a goal, without any precomputation of the environment's structure. This makes it ideal for problems where the start and goal change frequently.

• On-demand computation: No expensive preprocessing phase is required, unlike multi-query planners like PRM (Probabilistic Roadmap).
• Efficient for dynamic goals: The tree is grown until a node satisfies the goal condition, making it responsive to new task specifications.

The algorithm's exploration speed stems from a Voronoi bias. At each iteration, a random sample is drawn from the free space. The tree is extended from the node nearest to this sample, which is always the node in the largest Voronoi region of the tree.

• Key Mechanism: This bias ensures growth is preferentially directed into large, unexplored volumes of the configuration space.
• Result: The tree 'rapidly explores' and quickly disperses through free space, rather than refining areas already covered.

RRT excels in non-convex spaces (like environments with complex obstacles and narrow passages) and high-dimensional configuration spaces (like robotic arms with 7+ degrees of freedom).

• Avoids explicit obstacle representation: It uses a collision-checking oracle, probing samples and connections. This bypasses the computationally intractable problem of explicitly computing the geometry of high-dimensional free space.
• Dimensionality scaling: Computational cost grows more manageably with dimensions compared to grid-based methods, which suffer from the curse of dimensionality.

The foundational RRT finds a feasible path, but not necessarily an optimal one. RRT* is a seminal extension that provides asymptotic optimality. As the number of samples increases, the cost of the best path in the tree converges almost surely to the global optimum.

• Rewiring: After adding a new node, RRT* examines nearby nodes to see if connecting through the new node provides a lower-cost path, 'rewiring' the tree for continuous improvement.
• Trade-off: This optimality comes at increased computational cost per iteration due to the nearest-neighbor search and rewiring process.

The core RRT algorithm has inspired numerous variants tailored to specific challenges:

• RRT-Connect: Grows two trees simultaneously from start and goal, biasing growth toward each other for faster connection.
• Kinodynamic RRT: Plans in state space (including velocity) with dynamics constraints, not just geometric configuration space.
• Anytime RRT: Continues to refine and shorten the initial feasible path as computation time allows.
• Informed RRT*: Samples within an informed subset (an ellipsoid) once an initial solution is found, focusing computation on potentially better paths.

A sampling-based motion planning algorithm that operates in two distinct phases. In the preprocessing phase, it randomly samples the robot's configuration space (C-space) to build a graph (roadmap) of connected, collision-free nodes. In the query phase, it connects specific start and goal configurations to this roadmap to find a path. Unlike RRT's incremental, goal-biased tree growth, PRM builds a global network useful for multiple queries in static environments.

• Key Distinction: PRM is a multi-query planner; RRT is typically a single-query planner.
• Use Case: Ideal for planning in known, static environments where many start-goal pairs need to be evaluated.

The fundamental mathematical abstraction used in motion planning, where every possible state of a robot is represented as a single point. A robot with n degrees of freedom (e.g., joint angles) has an n-dimensional C-space. Physical obstacles in the workspace become forbidden regions (C-obstacles) within this space. RRT operates directly in C-space by sampling random points and attempting to connect them.

• Core Function: Transforms the complex problem of moving a multi-jointed body into the simpler problem of finding a path for a point.
• Example: A 2D mobile robot's C-space is often (x, y, θ), representing its position and orientation.

The process of refining a geometric path (like one from RRT) into a time-parameterized, dynamically-feasible trajectory. It solves an optimization problem to minimize a cost function (e.g., energy, time, jerk) while satisfying constraints like actuator limits, dynamics, and collision avoidance. RRT often provides an initial, collision-free guess that optimization methods like STOMP or CHOMP can then smooth and improve.

• Purpose: Converts a path (a sequence of states) into a trajectory (states with associated timings and derivatives).
• Output: A smooth sequence of commands specifying positions, velocities, and accelerations over time.

An advanced, online control strategy that uses a model of the system's dynamics to predict future states over a finite horizon. At each control cycle, it solves an optimization problem to determine the optimal sequence of control inputs, executes the first step, and then re-plans. While RRT is a planner, MPC is a receding-horizon controller that can handle dynamic constraints and disturbances in real-time. They are often used in tandem: RRT for global planning, MPC for local, reactive execution.

• Key Feature: Explicitly handles constraints (e.g., velocity, obstacle proximity) within its optimization.
• Real-time Role: Provides robust, feedback-driven control that can adapt to unexpected changes.

A classical AI planning formalism for task decomposition. It breaks down high-level goals using a library of methods that define how compound tasks can be reduced to subtasks, recursively, until primitive actions are reached. HTN operates at the symbolic task level, while RRT operates at the geometric motion level. In a hierarchical planning architecture, an HTN planner might generate a sequence of symbolic actions (e.g., 'Navigate to Room A', 'Pick up Object'), and an RRT planner would then compute the detailed motions for each.

• Abstraction Level: Works with symbolic representations of actions and world states.
• Integration: Forms the 'task planning' layer above the 'motion planning' layer where RRT operates.

A best-first graph search algorithm that finds the shortest path between nodes. It uses a cost function f(n) = g(n) + h(n), where g(n) is the cost from the start node to node n, and h(n) is a heuristic estimating the cost from n to the goal. A* is optimal and complete for finite graphs with an admissible heuristic. Unlike sampling-based RRT, A* requires a discrete, pre-defined graph (like a grid). For motion planning, A* is often used on a discretized representation of the environment, while RRT is used for continuous C-spaces.

• Core Principle: Systematically explores the most promising paths first, guided by the heuristic.
• Contrast to RRT: A* searches a known graph; RRT constructs a tree in an unknown continuous space.