Rapidly-exploring Random Tree (RRT)

RRT is probabilistically complete, meaning that if a feasible path exists, the probability of the algorithm finding it approaches 1 as the number of samples (or iterations) goes to infinity. This is a weaker guarantee than deterministic completeness (guaranteed to find a path if one exists) but is highly effective in practice for complex, high-dimensional spaces where exhaustive search is impossible.

• Key Implication: It will almost always find a path given enough time, but there is no upper bound on the time required.
• Contrast with A*: Unlike grid-based A*, which is resolution-complete, RRT does not require discretization of the state space.

The core mechanism driving RRT's efficiency is its biased exploration of the configuration space (C-space). It does not search uniformly but expands most aggressively into the largest unexplored regions.

• Process: At each iteration, the algorithm samples a random point in C-space. It then finds the nearest node already in the tree and extends a new branch from that node toward the random sample by a fixed step size.
• Voroni Bias: This simple rule gives the tree a Voroni bias—the probability of a tree node being selected for expansion is proportional to the volume of its Voronoi region (the region of space for which it is the closest node). This naturally leads the tree to rapidly explore unsampled areas.

A major strength of RRT is its ability to incorporate system dynamics and kinematic constraints directly into the planning process, leading to variants like RRT* and Kinodynamic RRT.

• Nonholonomic Constraints: For systems like cars that cannot move sideways, the extension step from the nearest node is not a straight line. Instead, a local planner or steering function is used to generate a feasible, constraint-satisfying trajectory segment.
• Dynamics Integration: Kinodynamic RRT samples in the full state-space (including velocity) and uses a forward simulation of the system's dynamics model to generate new branches, ensuring the resulting path is dynamically feasible.

The basic RRT finds any feasible path, not necessarily a good one. RRT* is a seminal extension that introduces rewiring to achieve asymptotic optimality.

• Rewiring Process: After adding a new node, RRT* examines nearby nodes to see if connecting through the new node provides a lower-cost path. If so, it rewires the tree, making the new node the parent. This process continuously refines the tree toward lower-cost paths.
• Asymptotic Guarantee: As the number of samples approaches infinity, the cost of the best path found by RRT* converges to the global optimum. This makes it a cornerstone of optimal sampling-based motion planning.

RRT is fundamentally a single-query planner. It builds a new tree from scratch for each specific start-goal pair. This contrasts with multi-query planners like the Probabilistic Roadmap (PRM), which builds a reusable roadmap of the entire free space.

• Advantage: For one-off planning problems, RRT is often faster than building a comprehensive roadmap, as it focuses computational effort on exploring the space between the given start and goal.
• Disadvantage: If multiple paths need to be found in the same static environment, PRM may be more efficient after its initial construction phase.

RRT's computational complexity is relatively independent of the dimensionality of the C-space, making it a primary tool for planning for robots with many degrees of freedom (DOF).

• Curse of Dimensionality: Grid-based planners become intractable for >4 DOF. RRT's random sampling avoids explicit discretization.
• Typical Use Cases:
  • Robotic Manipulators: Planning arm trajectories around clutter in a 7+ DOF C-space.
  • Mobile Robot Base + Arm: Planning in a combined 9+ DOF space.
  • Molecular Folding: Modeling protein conformation in extremely high-dimensional spaces.

Probabilistic Roadmap (PRM) is a sampling-based motion planning algorithm that operates in two distinct phases. First, in the learning phase, it randomly samples collision-free configurations (nodes) in the robot's configuration space and connects nearby nodes with simple, collision-free local paths to form a graph, or roadmap. Second, in the query phase, the start and goal configurations are connected to this pre-computed roadmap, and a standard graph search (e.g., A*) finds a path between them.

• Key Difference from RRT: PRM is a multi-query planner. It builds a global roadmap of the free space once, which can then be efficiently reused for many different start-goal queries. RRT is typically a single-query planner, building a new tree from scratch for each problem.
• Use Case: PRM excels in static environments where many paths need to be computed, such as in virtual prototyping. RRT is often preferred for dynamic or changing environments or when a solution is needed quickly for a single query.

Configuration Space (C-Space) is the fundamental mathematical abstraction that transforms physical motion planning into a geometric search problem. A robot's configuration is a complete specification of the position of every point on the robot (e.g., all joint angles for an arm). The set of all possible configurations forms the C-Space.

• Obstacle Transformation: Physical obstacles in the workspace are mapped to forbidden regions, called C-obstacles, within the C-Space. The remaining area is the free space.
• Dimensionality: The C-Space's dimension equals the number of degrees of freedom (DOF) of the robot. A 6-DOF arm has a 6D C-space. This high dimensionality is why sampling-based planners like RRT are necessary, as explicitly representing complex C-obstacles is computationally infeasible.
• RRT's Domain: RRT operates directly in this C-Space. Its random samples are configurations, and the tree grows within the free space, avoiding C-obstacles.

Trajectory Optimization is a complementary paradigm to path planning algorithms like RRT. While RRT finds a feasible (collision-free) path, trajectory optimization finds an optimal trajectory with respect to a cost function (e.g., minimal energy, time, or jerk).

• Mathematical Framework: It is typically formulated as a Nonlinear Programming (NLP) problem: minimize a cost subject to dynamics, collision avoidance, and actuator constraints.
• Common Methods: Sequential Quadratic Programming (SQP) and direct collocation are standard numerical solvers. Model Predictive Control (MPC) is a receding-horizon form of online trajectory optimization.
• Synergy with RRT: A common pipeline uses RRT (or its variant, RRT*) to find an initial, feasible path. This path is then used as a warm start for a trajectory optimizer, which "smooths" it and optimizes it for dynamic feasibility and performance, resulting in a high-quality, executable trajectory.

Model Predictive Control (MPC) is an advanced, online control strategy that repeatedly solves a finite-horizon trajectory optimization problem. At each control cycle, it uses a model of the system dynamics to predict future states, optimizes a sequence of control inputs to minimize a cost, executes only the first control input, and then repeats the process.

• Real-Time Replanning: This receding horizon approach allows MPC to continuously adapt to new sensor data, disturbances, and moving obstacles.
• Relation to Motion Planning: MPC can be viewed as a very short-horizon, dynamically-feasible motion planner running at high frequency. It is often used for local planning and control.
• Complement to RRT: RRT can provide a global reference path in a complex static environment. MPC then tracks this path while handling local dynamics, constraints, and unexpected obstacles in real-time, blending global intent with local reactivity.

A* is a classic graph search algorithm that finds the shortest path from a start node to a goal node. It is optimal and complete for graphs with non-negative edge costs. It works by maintaining a priority queue of nodes to explore, prioritized by the sum of the cost from the start (g(n)) and a heuristic estimate of the cost to the goal (h(n)).

• Heuristic-Driven: The heuristic h(n) (e.g., Euclidean distance) guides the search efficiently toward the goal. If h(n) is admissible (never overestimates), A* is guaranteed to find the optimal path.
• Contrast with RRT: A* requires a discretized graph of the state space (like a grid). RRT does not require discretization; it builds its own graph by sampling a continuous space. A* is excellent for low-dimensional, discretizable spaces (e.g., 2D grid maps). RRT is designed for high-dimensional, continuous spaces where graph construction via sampling is the only tractable approach.