RRT*

The defining property of RRT* is its asymptotic optimality. This guarantees that as the number of sampled states approaches infinity, the cost of the best-found path converges to the true optimal cost with probability one. This is a strict improvement over the basic RRT, which is only probabilistically complete (guaranteed to find a solution, but not necessarily the best one).

• Key Mechanism: The rewiring step enables this property by allowing the algorithm to replace parent connections in the tree if a new, lower-cost connection to a node is discovered.
• Practical Implication: In real-world applications with finite computation time, RRT* produces significantly better paths than RRT after the same number of iterations.

RRT* maintains a cost-to-come value for every node in the tree, representing the total cost of the path from the root (start) to that node. The rewiring process is the core of RRT*'s optimization.

• Near Node Selection: For a new sample x_new, the algorithm finds a set of near nodes within a ball of radius r(n) (which shrinks as the number of nodes n increases).
• Best Parent Connection: It connects x_new to the near node that provides the minimum cost-to-come to x_new via a collision-free local path.
• Rewiring Near Nodes: Crucially, it then checks if connecting existing near nodes to x_new* would lower their cost-to-come. If so, it rewires the tree by changing their parent to x_new`. This local optimization propagates cost improvements throughout the tree over time.

RRT* is an anytime algorithm that provides a feasible solution quickly and then incrementally improves it. Unlike batch optimization methods that require a complete re-solve, RRT* refines the solution incrementally with each new sample.

• Initial Solution: Like RRT, it finds an initial, possibly suboptimal, path relatively fast.
• Continuous Refinement: Every new random sample offers an opportunity to discover a shorter path segment or a more efficient connection via the rewiring process.
• Use Case: This makes it highly suitable for real-time replanning scenarios where computation time is bounded; the system can execute the current best path while the planner continues to refine it in the background.

As a sampling-based planner, RRT* does not require an explicit representation of the configuration space's obstacles. It explores the space by randomly sampling states and attempting to connect them to the growing tree.

• Bias towards Exploration: The algorithm inherently biases growth towards large, unexplored regions of the space, making it efficient for high-dimensional problems (e.g., robotic arms with many joints).
• Probabilistic Completeness: It shares the probabilistic completeness of RRT: if a feasible path exists, the probability of finding it approaches 1 as the number of samples goes to infinity.
• Handles Complex Constraints: This random sampling approach allows it to naturally handle non-holonomic and kinodynamic constraints by using a steering function to generate feasible local paths between nodes.

A critical component of RRT* (and RRT) is the steering function. This function is responsible for generating a feasible, collision-free trajectory from a parent node x_near towards a target sample x_rand or x_new.

• Role: It acts as a local planner. For holonomic systems, this may be a simple straight-line connection. For systems with dynamics (kinodynamic planning), it is a more complex controller that respects velocity and acceleration limits.
• Connection Validation: The output of the steering function must be checked for collisions before a node is added to the tree.
• Impact on Optimality: The quality and reachability of the steering function directly influence the efficiency of the search and the smoothness of the final path. Poor steering can limit the algorithm's ability to find the true optimum.

RRT* sits within a family of sampling-based and optimal planners, each with distinct trade-offs.

• vs. RRT: The core differentiator is the rewiring for optimality. RRT finds a solution; RRT* improves it.
• vs. PRM (Probabilistic Roadmap): PRM is a multi-query method that builds a global roadmap. RRT* is a single-query, tree-based method that is often more efficient for finding an initial solution.
• vs. A/D/LPA***: These are graph-search algorithms optimal for discrete, low-dimensional grids. RRT* is designed for continuous, high-dimensional spaces where building a full graph is infeasible.
• Evolution: RRT* has spawned many variants like Informed RRT* (which uses an ellipsoidal heuristic to focus sampling) and RRT*-Smart (which uses path optimization waypoints to guide sampling).

The foundational algorithm upon which RRT* is built. An RRT is a sampling-based motion planning algorithm that incrementally builds a space-filling tree from an initial state to explore high-dimensional search spaces. It is probabilistically complete but not optimal.

• Core Mechanism: Randomly samples the configuration space and extends the nearest node in the tree toward the sample.
• Key Use Case: Effective for non-holonomic and kinodynamic planning problems where completeness is more critical than optimality.
• Limitation: The resulting path is often suboptimal and jerky, as the algorithm focuses on exploration over path quality.

A sampling-based method that constructs a graph of collision-free configurations during a preprocessing phase. Unlike RRT's incremental tree growth, PRM builds a global roadmap of the free space.

• Two-Phase Process: 1) Learning Phase: Randomly sample configurations and connect nearby ones to form a roadmap graph. 2) Query Phase: Use the roadmap to find a path between specific start and goal states.
• Advantage: Efficient for multiple queries in the same static environment, as the roadmap is built once and reused.
• Contrast with RRT*: PRM is multi-query, while RRT* is typically single-query. PRM does not inherently include an optimality-guaranteeing rewiring step.

A classic graph traversal and path search algorithm that guarantees an optimal path. A* uses a best-first search strategy guided by a heuristic function h(n) to estimate the cost to the goal.

• Optimality: Guarantees the shortest path if the heuristic is admissible (never overestimates the true cost).
• Contrast with Sampling-Based Planners: A* requires a discrete graph representation of the state space. RRT* was developed for continuous spaces where constructing such a graph is infeasible.
• Hybrid Use: Often used in a hierarchical planner, where A* plans a coarse grid-based path that is then refined by RRT* in continuous configuration space.

The problem of finding a trajectory that satisfies both kinematic constraints (e.g., non-holonomic wheel constraints) and dynamic constraints (e.g., acceleration, torque limits). RRT* is frequently extended to solve kinodynamic variants.

• Beyond Geometry: Plans in the state space (e.g., [x, y, θ, v, ω]) instead of just configuration space ([x, y, θ]).
• RRT Extensions*: Algorithms like Kinodynamic RRT* use motion primitives or forward integration to generate dynamically feasible edges in the tree.
• Application: Essential for autonomous vehicles and agile drones where dynamics fundamentally limit possible motions.

Algorithmic families crucial for real-time replanning. RRT* exhibits anytime behavior, improving its solution with computation time.

• Incremental Algorithm: Efficiently updates its output given a small input change. RRT* is incremental in its tree growth and rewiring.
• Anytime Algorithm: Can return a valid solution at any time, with quality improving over time. RRT* provides an initial feasible path quickly, then asymptotically optimizes it.
• Replanning Context: These properties make RRT* suitable for scenarios where the planner must run continuously, refining paths as the environment changes or more compute time is available.

A leading optimal algorithm for Multi-Agent Path Finding (MAPF). While RRT* plans for a single agent, CBS coordinates paths for multiple agents to avoid inter-agent collisions.

• Two-Level Search: High-level search resolves conflicts between individual agent paths by imposing constraints. Low-level search finds optimal paths for each agent under those constraints.
• Contrast with RRT*: CBS operates on a discrete graph, often using A* for low-level planning. Multi-agent extensions of RRT* exist but face scalability challenges.
• Use Case: Critical for warehouse robotics and heterogeneous fleet orchestration where coordinated, collision-free paths for dozens of agents are required.