Path Planning

The Configuration Space (C-Space) is a fundamental mathematical abstraction that transforms the physical robot into a single point. Every possible state of the robot (defined by its joint angles, position, and orientation) is mapped to a unique point in this space. Physical obstacles in the world become forbidden regions, or C-obstacles, within C-Space. This transformation simplifies the path planning problem from navigating a complex articulated body to moving a point through an abstract, often higher-dimensional, space.

• Key Insight: A path for the robot exists in the physical world if and only if a corresponding curve for the point exists in the free C-Space.
• Dimensionality: The number of degrees of freedom (DOF) of the robot defines the dimensionality of its C-Space (e.g., a 6-DOF arm has a 6D C-Space).

Sampling-based planners are the dominant approach for high-dimensional path planning problems where explicitly modeling C-obstacles is computationally infeasible. They avoid exact geometric modeling by probing the free space with random or quasi-random samples.

• Rapidly-exploring Random Tree (RRT): An incremental algorithm that grows a tree rooted at the start configuration by randomly sampling the C-Space and extending the tree toward the sample. It is particularly effective for single-query problems (one start-goal pair) in non-convex spaces. Variants like RRT* are asymptotically optimal.
• Probabilistic Roadmap (PRM): A multi-query method that performs a preprocessing phase to build a graph (roadmap) of collision-free configurations. Paths are found by connecting start and goal to this roadmap and searching the graph. Ideal for planning in static environments where many queries will be made.

When the planning problem can be discretized into a graph (e.g., a grid), classic graph search algorithms find optimal paths. They operate on an explicit representation of states (nodes) and transitions (edges).

• A Algorithm*: A best-first search that finds the least-cost path by evaluating nodes using a cost function f(n) = g(n) + h(n), where g(n) is the cost from the start node, and h(n) is a heuristic estimating the cost to the goal. It is complete and optimal if the heuristic is admissible (never overestimates).
• D (Dynamic A)**: An incremental search algorithm that efficiently replans when edge costs in the graph change (e.g., due to newly discovered obstacles). It is widely used in real-time robotic navigation where the map is updated by sensor data.

Trajectory optimization refines a geometrically feasible path into a smooth, time-parameterized trajectory that respects the robot's dynamics and actuator limits. While path planning answers "where to go," trajectory optimization answers "how and when to move."

• Input: A collision-free geometric path (from a sampler or graph search).
• Process: Formulates and solves an optimization problem to minimize a cost function (e.g., total time, energy, jerk) subject to constraints (dynamics, torque limits, velocity/acceleration bounds).
• Methods: Include direct collocation, shooting methods, and quadratic programming (QP) solvers. It is closely related to Model Predictive Control (MPC) for online, receding-horizon optimization.

In hierarchical Task and Motion Planning (TAMP), path planning is a subordinate module. A high-level task planner (e.g., using PDDL or an HTN) reasons about symbolic actions and logical preconditions, but each primitive action like Navigate(Kitchen, LivingRoom) or PickUp(Bottle) requires a feasible motion plan.

• The Interface: The task planner sends a motion planning query (start, goal, constraints) to the path planner.
• Feasibility Checking: If the path planner fails, it signals infeasibility back to the task planner, which must then try an alternative action sequence.
• Semantic Constraints: Path goals may be defined semantically ("in front of the cabinet") and must be grounded into specific coordinates via visual grounding and scene understanding.

Practical robotic deployment introduces complexities that extend the basic path planning formulation.

• Dynamic Environments: Planning amidst moving obstacles requires predictive models or reactive collision avoidance layers (e.g., velocity obstacles, potential fields).
• Kinodynamic Planning: Directly plans in the state space that includes velocity and other derivatives, satisfying differential constraints. RRT variants exist for this.
• Multi-Agent Path Finding (MAPF): Coordinates paths for multiple robots to avoid inter-agent collisions while optimizing global efficiency. Used in warehouse automation.
• Constrained Manipulation: For robotic arms, planning must consider inverse kinematics solutions, reachability, and grasp planning for manipulation tasks.

In minimally invasive surgery, robotic systems use precise motion planning to guide tools along collision-free paths through constrained anatomical spaces. This involves:

• High-fidelity patient-specific models derived from CT/MRI scans to define the configuration space.
• Sampling-based planners like RRT* to find paths that avoid critical tissues and blood vessels.
• Jerk-limited trajectory generation to ensure smooth, tremor-free tool movement essential for patient safety.

Drones for delivery, inspection, and mapping require 3D path planning in unstructured environments. Challenges include:

• Computing energy-efficient paths considering wind, aerodynamics, and payload.
• Coverage path planning for systematic inspection of infrastructure like wind turbines or pipelines.
• Exploration in GPS-denied environments, using SLAM-generated maps for online replanning.
• Ensuring regulatory compliance by planning paths that avoid no-fly zones and maintain safe altitudes.

Rovers like NASA's Perseverance use autonomous path planning to navigate Martian terrain between ground-sent waypoints. This extreme case highlights:

• Severe latency constraints: Signals take minutes to reach Earth, necessitating full autonomy.
• Uncertainty modeling: Planners must account for wheel slippage on loose soil and sensor noise.
• Risk-aware planning: Algorithms evaluate traversability cost based on slope, roughness, and scientific value to avoid getting stuck.
• Field-proven algorithms: Grid-based search and state lattice planners are commonly used due to their predictability and robustness.

The overarching algorithmic process of computing a full trajectory—including path geometry, timing, velocities, and dynamics—for a robot to move from a start to a goal state while satisfying all physical and environmental constraints. Path planning is a geometric subset of motion planning.

• Broader Scope: Considers robot dynamics, actuator limits, and time parameterization.
• Output: A time-parameterized trajectory, not just a geometric path.
• Example: Planning a drone's flight that accounts for acceleration limits and wind, not just a collision-free curve through the air.

The process of refining a geometric path into a smooth, time-parameterized trajectory that minimizes a cost function (e.g., energy, jerk, time) while satisfying dynamic constraints.

• Follows Path Planning: Takes a collision-free path as input.
• Key Methods: Include quadratic programming, direct collocation, and CHOMP (Covariant Hamiltonian Optimization for Motion Planning).
• Goal: Produce a trajectory that is physically executable and efficient for the robot's motors and controllers.

A fundamental mathematical abstraction where every possible pose of a robot is mapped to a single point. This transforms the complex problem of planning for a multi-jointed body into the simpler problem of planning for a point robot navigating forbidden regions.

• Core Concept: Obstacles in the physical world become expanded 'C-obstacles' in this abstract space.
• Dimensionality: Defined by the robot's degrees of freedom (e.g., a 6-DOF arm has a 6D C-Space).
• Utility: Enables the use of generic geometric planning algorithms like A* or RRT on the point robot in C-Space.

A class of algorithms that construct paths by randomly or quasi-randomly sampling the robot's configuration space, avoiding the computational complexity of explicitly modeling all obstacles. These are the workhorses for high-dimensional planning problems.

• Key Algorithms: RRT (Rapidly-exploring Random Tree) and PRM (Probabilistic Roadmap).
• Advantage: Efficiently handles complex, non-convex spaces with many degrees of freedom.
• Property: Probabilistically complete—guaranteed to find a solution if one exists, given enough time.

The computational geometry process of determining whether two or more objects (e.g., a robot link and an environment obstacle) intersect or are in contact. It is a critical, low-level subroutine called millions of times during path planning.

• Performance Critical: Often the bottleneck in planning algorithms.
• Techniques: Use bounding volume hierarchies (BVH), spatial hashing, and signed distance fields for acceleration.
• Distinction: Collision avoidance is the high-level reactive behavior; collision detection is the geometric check that enables it.

An informed graph search algorithm optimal for path planning in discrete or discretized spaces (like grids). It uses a heuristic function to estimate the cost to the goal, prioritizing the exploration of the most promising paths.

• Algorithm: A* combines the cost-to-come (g(n)) and the estimated cost-to-go (h(n)).
• Application: Foundational for 2D grid-based navigation (e.g., warehouse AMRs).
• Requirement: The heuristic must be admissible (never overestimates) to guarantee optimality.