Rapidly-Exploring Random Tree (RRT)

RRT is probabilistically complete, meaning if a feasible path exists, the probability that the algorithm will find it approaches 1 as the number of samples approaches infinity. This is a critical guarantee for planners in complex spaces.

• Key Implication: It will eventually find a solution, but offers no strict upper bound on time or samples required.
• Contrast with Optimality: This property is about existence, not quality. The basic RRT does not guarantee the shortest or optimal path.
• Application in Dexterous Manipulation: Essential for exploring the high-dimensional configuration space of a multi-fingered hand, where feasible paths may be narrow and complex.

The algorithm's growth is biased toward large, unexplored regions of the space, leading to rapid coverage. This is achieved by sampling a random point and extending the tree's nearest node toward it.

• Mechanism: At each iteration, a random configuration is sampled. The tree node closest to this sample (by a distance metric) is selected, and a new node is created by extending from it a fixed step size toward the random sample.
• Benefit: This Voronoi bias ensures the tree expands quickly into voids, making it highly efficient for initial exploration compared to grid-based searches.
• Visualization: The tree structure resembles branches rapidly shooting out to fill an empty area, which is the origin of the algorithm's name.

RRT can be extended to plan for systems with non-holonomic or dynamic constraints (e.g., cars, drones, manipulators with inertia) through the use of a steering function.

• Core Extension: The basic EXTEND operation is replaced with a more complex function that computes a feasible local trajectory from the current state toward the target, respecting the system's kinematics and dynamics.
• RRT Variant: This leads to algorithms like Kinodynamic RRT, which plans directly in the state space (including velocities) rather than just the configuration space.
• Robotics Relevance: Critical for dexterous manipulation where finger motions have acceleration limits and complex contact dynamics.

RRT is a sampling-based planner that relies on a collision detection module rather than an explicit analytical representation of free space. This makes it adaptable to complex, cluttered environments.

• How it Works: The algorithm only needs to answer binary queries: "Is this specific configuration in collision?" and "Is this short path segment collision-free?"
• Advantage: It can be applied to environments with obstacles of arbitrary shape, which are difficult to model with simple polygons or equations.
• Integration: This feature allows RRT to serve as a high-level planner in a task and motion planning (TAMP) hierarchy, where the geometric world is provided by a perception system.

A major performance enhancement is the RRT-Connect variant, which grows two trees simultaneously: one from the start and one from the goal. This dramatically speeds up convergence.

• Algorithm Process: Each iteration attempts to extend one tree toward a random sample, then aggressively extends the other tree toward the newest node of the first tree.
• CONNECT Heuristic: This aggressive extension continues until collision or the trees meet, which often happens quickly in open areas.
• Practical Impact: RRT-Connect is often the default implementation used in robotics software libraries like MoveIt! for manipulator arm planning due to its significant speed improvement.

The RRT* algorithm introduces a rewiring step to the tree, enabling it to converge toward an optimal solution (e.g., shortest path) as the number of samples increases—a property called asymptotic optimality.

• Rewiring Process: After adding a new node, RRT* examines nearby nodes to see if their path cost from the root can be reduced by routing through the new node. If so, it changes the parent connection.
• Trade-off: This optimality comes at a computational cost per iteration, making RRT* slower than basic RRT for initial solution finding.
• Usage: In dexterous manipulation, RRT* is valuable for finding smooth, efficient finger trajectories that minimize energy or time when fine-tuning a grasp.

In minimally invasive surgery, RRT helps plan safe insertion paths for surgical tools and robotic needles.

• Steerable needle path planning: Navigating around critical anatomical structures to reach a tumor.
• Collision avoidance for robotic endoscopes: Ensuring flexible surgical robots do not damage sensitive tissue.
• Radiotherapy beam planning: Optimizing the path of a radiation source to target a tumor while sparing healthy organs. These applications often use Anytime RRT variants, which improve the path quality as computation time allows, and Informed RRT*, which focuses sampling within an ellipsoidal subset of the space once an initial solution is found.

In computer graphics, RRT is used to generate natural-looking motions for digital characters and crowds.

• Humanoid robot and character animation: Planning whole-body motions through cluttered virtual environments.
• Crowd simulation: Generating diverse, collision-free paths for hundreds of agents.
• Interactive applications: Allowing characters in games or simulations to dynamically navigate unpredictable worlds. The planner operates in a high-dimensional space representing the character's joint angles, efficiently finding poses that satisfy balance and collision constraints.

The core RRT concept has spawned numerous influential variants, each addressing specific limitations:

• RRT*: An asymptotically optimal version that rewires the tree to continuously improve path cost.
• RRT-Connect: A bi-directional variant that grows trees from both start and goal, dramatically speeding up convergence.
• Anytime RRT: Continues to optimize the best-found path until computational time is exhausted.
• Kinodynamic RRT: Plans directly in the state-space (including velocity), ensuring dynamically feasible trajectories.
• Informed RRT*: Restricts sampling to a prolate hyperspheroid after an initial solution, focusing computation on potentially better paths.

Trajectory optimization is the process of computing a sequence of robot states and control inputs that minimizes a cost function while satisfying dynamic constraints and task goals. Unlike RRT, which focuses on finding a feasible path, trajectory optimization refines that path for optimality in terms of energy, time, or smoothness.

• Key Methods: Include direct collocation and shooting methods.
• Relation to RRT: An RRT can provide an initial, collision-free trajectory which is then smoothed and optimized.
• Use Case: Generating the final, executable joint command sequence for a robotic arm after a rough path is planned.

Model Predictive Control is an advanced, real-time control method where a dynamic model of the system is used to predict future behavior and optimize a sequence of control inputs over a receding horizon. It is often used for dynamic, contact-rich tasks.

• Core Principle: Solves a finite-horizon optimization problem at each time step and applies only the first control input.
• Contrast with RRT: MPC is for closed-loop, reactive control, while RRT is typically for open-loop, global planning. They can be combined in a hierarchical architecture.
• Application: Dexterous manipulation tasks requiring constant force adjustment and disturbance rejection.

Task and Motion Planning is a hierarchical approach that integrates high-level symbolic task planning with low-level geometric motion planning (like RRT). It solves problems where achieving a goal requires a sequence of actions, each with associated motion constraints.

• Hierarchy: The task planner decides what to do (e.g., pick up A, then place on B), and the motion planner figures out how to do it.
• RRT's Role: Often serves as the geometric motion planner within a TAMP framework, checking feasibility for individual actions.
• Example: Planning to clear a cluttered table involves sequencing multiple pick-and-place motions, each requiring a collision-free path.

A Probabilistic Roadmap is another foundational sampling-based path planning algorithm. It operates in two distinct phases: a learning phase that builds a graph (roadmap) of random, collision-free configurations, and a query phase that searches this graph for a path between start and goal.

• Key Difference from RRT: PRM is multi-query (builds a reusable map), while basic RRT is single-query (builds a tree for one problem).
• Best For: Static environments where many path planning queries will be made.
• Limitation: Less efficient than RRT for dynamic or rapidly changing environments.

An inverse kinematics solver computes the set of joint angles required for a robotic manipulator to achieve a desired position and orientation (pose) of its end-effector. It is a critical downstream component after path planning.

• RRT Integration: An RRT typically plans in the robot's configuration space (joint angles). Each node in the RRT tree is a valid set of joint angles, inherently solving IK for the end-effector poses along the path.
• Challenge: For redundant manipulators, there are infinite joint solutions for one pose; the RRT explores this space.
• Use: Translating a Cartesian-space goal (e.g., "grasp here") into the joint-space parameters an RRT can plan with.

Contact-implicit trajectory optimization is a planning method that optimizes robot motions without pre-specifying the sequence or timing of contacts. The optimization discovers when and where contacts should occur to achieve a goal, such as pushing or pivoting an object.

• Contrast with RRT: Standard RRT assumes a known, fixed environment geometry. Contact-implicit optimization co-optimizes the robot's motion and its interaction forces with movable objects.
• Complexity: Formulated as a challenging, non-convex optimization problem.
• Application: Essential for non-prehensile manipulation (e.g., using a robot arm to push a box across a table).