Sampling-Based Planning

A sampling-based planner is probabilistically complete if the probability of finding a solution, when one exists, approaches 1 as the number of samples approaches infinity. This is a key theoretical guarantee, contrasting with resolution completeness (guaranteed for grid-based searches at sufficient resolution). It means the algorithm will eventually find a path if given enough time, but offers no worst-case time bound.

• Examples: RRT, PRM, and their variants are probabilistically complete.
• Implication: For real-time systems, this property is balanced with anytime characteristics, where a feasible (if suboptimal) solution can be returned quickly and improved over time.

The core innovation is bypassing the computationally prohibitive task of constructing an explicit geometric representation of the configuration space (C-space) and its obstacle region (C_obs). Instead, the planner relies on a collision detection module as a black-box oracle.

• Process: The algorithm samples a point in C-space and queries the collision checker to determine if it lies in free space (C_free).

• Benefit: This makes planning tractable for robots with many degrees of freedom (DOF), where C_obs has an extremely complex geometry. The complexity shifts from geometric modeling to efficient sampling and graph/tree search.

Sampling-based planners are designed to explore high-dimensional state spaces efficiently. They do not require a dense discretization, which suffers from the curse of dimensionality (exponential growth in grid cells with each added DOF).

• RRT Strategy: Biases exploration toward unexplored regions by extending its tree preferentially toward random samples.

• PRM Strategy: Builds a sparse probabilistic roadmap—a network of feasible configurations—that captures the connectivity of C_free.

• Key Metric: The rate at which the planner's graph/tree coverage of C_free increases, measured by the dispersion of the sample set.

A major distinction lies in single-query vs. multi-query paradigms.

• Single-Query Planners (e.g., RRT): Build a search tree from a specific start state to a specific goal state for a single planning problem. The constructed data structure is typically discarded after use. Ideal for dynamic environments where start/goal changes frequently.

• Multi-Query Planners (e.g., PRM): Perform a lengthy preprocessing phase to construct a global roadmap graph that captures the connectivity of C_free. Once built, multiple start-goal queries can be answered rapidly using graph search (e.g., A*). Ideal for static environments where many paths need to be computed.

Early sampling-based planners like basic RRT were not asymptotically optimal—the cost of the solution path does not converge to the optimal cost as computation time increases. This led to the development of optimal variants.

• RRT*: An asymptotically optimal version of RRT. It incorporates a rewiring step in the growing tree, where new samples are connected to the lowest-cost parent in a local neighborhood, and nearby nodes are rewired if the new sample offers a lower-cost path. This ensures convergence to an optimal path.

• PRM*: Similarly, an optimal PRM variant uses more sophisticated connection strategies during roadmap construction to guarantee optimality in the limit.

Modern sampling-based planners extend beyond geometric path planning to handle kinodynamic constraints (non-holonomic dynamics, velocity/acceleration limits) and task constraints (end-effector orientation, closed-chain kinematics).

• Kinodynamic Planning: Planners like Kinodynamic RRT sample in the full state space (including velocity) and use a steering function to generate dynamically feasible trajectory segments between samples.

• Constraint-Aware Sampling: Techniques like projection-based sampling generate samples that inherently satisfy constraints (e.g., sampling on a manifold defined by closed-chain equations), drastically improving planning efficiency for constrained systems.

RRT (RRT-Star)* and its variants are used for real-time local path planning in dynamic urban environments. These algorithms generate smooth, collision-free trajectories by sampling the vehicle's state space (position, heading, velocity).

• Dynamic Obstacle Avoidance: Continuously replans paths around moving pedestrians and other vehicles.
• Parking Maneuvers: Solves complex, constrained motion problems in tight parking spaces by sampling feasible steering and velocity profiles.
• Highway Lane Changes: Computes optimal merging trajectories that satisfy vehicle dynamics and safety margins.

In cluttered industrial and domestic settings, Probabilistic Roadmaps (PRM) precompute a network of collision-free arm configurations. This enables rapid querying for tasks like:

• Bin Picking: Finding collision-free paths to grasp randomly oriented parts from a container.
• Assembly Sequencing: Planning the motion to insert a peg into a hole while avoiding the workcell structure.
• Human-Collaborative Workspaces: Generating safe, predictable arm trajectories that can be executed near human operators.

The high-dimensional configuration space for a 7-DOF arm makes exhaustive search impossible, necessitating sampling.

Sampling-based planners ensure safety and precision in constrained anatomical spaces.

• Steerable Needle Path Planning: RRT variants plan paths for flexible needles to navigate around critical tissues to reach a tumor for biopsy or ablation.
• Endoscope Navigation: Guides a semi-autonomous endoscopic capsule through the gastrointestinal tract by sampling feasible orientations and positions.
• Prosthetic Limb Control: Plans natural-looking, stable grasping motions for advanced robotic prostheses by sampling from a library of learned motion primitives.

Drones inspecting infrastructure like bridges, wind turbines, or power lines use sampling-based planners to autonomously navigate complex 3D structures.

• Complete Coverage Planning: Algorithms like RRT with coverage objectives ensure every surface of a structure is viewed by an onboard camera.
• Constrained Environments: Plans paths through the interior of pipes, between refinery scaffolding, or inside aircraft hangars by sampling in SE(3) space (3D position + orientation).
• Reactive Replanning: Adjusts the path in real-time due to wind gusts or unexpected obstacles using fast RRT regrowth.

For on-orbit servicing, docking, and debris avoidance, planners must operate in dynamic environments with complex orbital mechanics.

• Docking Maneuver Planning: RRT or Kinodynamic RRT* samples in the state space that includes position, velocity, and attitude to find fuel-optimal, collision-free approaches to a target satellite.
• Debris Field Navigation: Plans a trajectory through a cloud of non-cooperative debris objects for a servicing vehicle.
• Arm Deployment on Space Stations: Plans the movement of large robotic arms (like the Canadarm2) to manipulate payloads without contacting the station structure.

Sampling-based planning is a core tool within physics simulators for validating robotic systems before physical deployment (Sim-to-Real).

• Automated Test Generation: Systematically explores edge-case scenarios in simulation by sampling different object placements, lighting conditions, and robot start states to stress-test control policies.
• Factory Layout Optimization: Uses PRM to evaluate the reachability and efficiency of a proposed robotic workcell layout by sampling millions of potential robot configurations.
• Training Data for Learning: Generates diverse, feasible state-action trajectories to serve as training data for imitation learning or to pre-train world models.

The Configuration Space (C-Space) is a fundamental mathematical abstraction where every possible state of a robot is mapped to a single point. This transforms the physical problem of navigating around obstacles into the computational problem of navigating a point through forbidden regions in this abstract space. It is the foundational representation for most motion planning algorithms.

• Key Insight: A robot with n degrees of freedom has an n-dimensional C-Space.
• Obstacle Mapping: Physical obstacles become C-obstacles, complex regions the planning point must avoid.
• Purpose: Enables planners like RRT and PRM to reason about collisions and connectivity without modeling the robot's complex geometry at every step.

RRT (Rapidly-exploring Random Tree) is a quintessential single-query sampling-based planner. It incrementally builds a tree of collision-free configurations rooted at the start state, aggressively exploring the C-Space by biasing growth toward randomly sampled points.

• Mechanism: On each iteration, it samples a random point, finds the nearest node in the tree, and extends a short step toward the sample.
• Strength: Exceptionally efficient at exploring high-dimensional, non-convex spaces and finding a feasible, though not necessarily optimal, path quickly.
• Variants: RRT* converges to an optimal path given infinite time. Bi-directional RRT grows trees from start and goal simultaneously.

PRM (Probabilistic Roadmap) is a multi-query sampling-based planner. It operates in two distinct phases: a learning phase that constructs a graph (roadmap) of random, collision-free configurations connected by local paths, and a query phase that uses this roadmap to find paths between specific start and goal pairs.

• Learning Phase: Randomly samples C-Space, retains collision-free nodes, and connects nearby nodes if a simple local planner (e.g., a straight line) finds a valid path.
• Use Case: Ideal for static environments where many pathfinding queries will be made, as the roadmap is built once and reused.
• Contrast to RRT: PRM is designed for multiple queries; RRT is for a single start-goal pair.

Motion Planning is the overarching algorithmic challenge of computing a sequence of valid configurations or states that move a robot from a start to a goal. It must satisfy constraints like collision avoidance, kinematic limits, and dynamics.

• Hierarchy: Sampling-based planning is a primary strategy within the broader field of motion planning.
• Core Problem: Find a continuous path in the robot's state space that connects start and goal while lying entirely within the free space (non-collision regions).
• Complementary Methods: Includes combinatorial (exact) planners for simple spaces, potential field methods, and optimization-based approaches like Trajectory Optimization.

Collision Detection is the computational geometry subroutine critical to sampling-based planning. It answers the binary question: is a given robot configuration or path segment in collision with any obstacle in the environment?

• Performance Bottleneck: Often the most computationally expensive operation in planners like RRT and PRM, as it is called thousands of times per second.
• Techniques: Uses bounding volume hierarchies (BVHs), spatial hashing, and signed distance fields to accelerate queries.
• Role in Planning: Every sampled point and every local connection between nodes must be validated by the collision detector before being added to the plan.

Trajectory Optimization is a planning paradigm that formulates the motion problem as the minimization of a cost function (e.g., energy, time, jerk) subject to constraints (dynamics, collisions). It often refines the output of a sampling-based planner.

• Relationship to Sampling: A sampling-based planner (e.g., RRT) finds a feasible, often sub-optimal, collision-free path. Trajectory optimization then smooths and optimizes this path into a high-quality, dynamically feasible trajectory.
• Methods: Includes STOMP, CHOMP, and sequential quadratic programming (SQP) solvers.
• Output: Produces a time-parameterized trajectory specifying positions, velocities, and accelerations.