Motion Planning

A sampling-based algorithm that constructs a graph (roadmap) in the free configuration space. It operates in two phases:

• Learning Phase: Randomly sample collision-free configurations (nodes) and connect nearby nodes with simple, collision-free local paths (edges).
• Query Phase: Connect the start and goal configurations to the roadmap and use a graph search (e.g., A*) to find a path.

Key Property: PRM is a multi-query planner. The roadmap is built once and can be reused for multiple start-goal queries, making it efficient for static environments. It excels in high-dimensional spaces where grid-based methods fail.

A sampling-based algorithm that incrementally builds a search tree rooted at the start configuration. At each iteration:

1. Randomly sample a configuration in the space.
2. Find the nearest node in the existing tree.
3. Extend the tree from this nearest node toward the sample by a fixed step size, adding a new node if the path is collision-free.

Key Property: RRT is a single-query planner, designed for one start-goal pair. It is probabilistically complete and particularly effective for problems with differential constraints (kinodynamics). Variants like RRT* are asymptotically optimal, converging to the shortest path.

A graph search algorithm that finds the least-cost path on a discretized representation of the environment (e.g., a grid). It uses a heuristic function h(n) to estimate the cost to the goal, prioritizing the exploration of promising nodes.

Core Function: f(n) = g(n) + h(n), where:

• g(n) is the exact cost from the start to node n.
• h(n) is the admissible heuristic (never overestimates the true cost, e.g., Euclidean distance).

Key Property: A* is optimal and complete for finite graphs with an admissible heuristic. It is the foundation for many grid-based navigation systems but suffers from the curse of dimensionality in high-D spaces.

An online optimization-based control strategy used for trajectory planning and execution. At each control time step:

1. Solve a finite-horizon optimal control problem using a dynamic model of the robot.
2. The optimization minimizes a cost function (e.g., tracking error, control effort) subject to constraints (dynamics, obstacles, actuator limits).
3. Execute only the first control input from the optimized sequence, then re-solve at the next step with updated state feedback.

Key Property: MPC explicitly handles dynamic constraints and obstacle avoidance in a receding horizon fashion, making it robust for controlling drones, autonomous vehicles, and manipulators in dynamic environments.

A trajectory optimization algorithm that refines an initial guess (e.g., from a sampling-based planner) into a smooth, collision-free path. It formulates planning as a nonlinear optimization problem.

Core Mechanics:

• Defines a cost functional combining obstacle avoidance (via a potential field), smoothness, and dynamic constraints.
• Uses covariant gradient descent in the trajectory space, which respects the underlying Riemannian metric of the robot's dynamics for more efficient convergence.

Key Property: CHOMP produces high-quality, continuous trajectories suitable for direct execution, bridging the gap between geometric planning and physical control. It is a precursor to modern STOMP and GPMP2 algorithms.

A continuous grid-based algorithm that computes the arrival time of a wavefront propagating from the goal through the environment, solving the Eikonal equation. The result is a potential field where the gradient descent from any start point yields the optimal (shortest) path.

Core Process:

1. The grid is initialized with the goal cell having zero cost.
2. The wavefront expands, updating neighbor cells with costs proportional to traversal speed (inverse of cell cost).
3. The algorithm guarantees the first arrival time at each cell is the globally optimal cost.

Key Property: FMM generates smooth, globally optimal paths in continuous coordinates from a discrete grid, avoiding the jagged paths of standard grid search. It is widely used in robotic navigation and medical imaging.

A hierarchical approach that decomposes a high-level symbolic task (e.g., 'make coffee') into a sequence of feasible motions. It integrates discrete task planning (logical operators, preconditions/effects) with continuous motion planning.

• Key Challenge: Managing the interdependence between discrete action sequences and continuous geometric feasibility.
• Example: A planner must decide to pick up a cup (task) and then compute a collision-free arm trajectory to the cup's location (motion).

An online, receding-horizon optimal control method. At each time step, MPC solves a finite-horizon optimization problem using a dynamic model of the system to predict future states, then executes only the first control input before re-planning.

• Contrast with Motion Planning: MPC is typically for short-horizon, dynamic control with frequent re-planning, while motion planning often computes a full path from start to goal.
• Use Case: Real-time balancing of a humanoid robot or trajectory tracking for a drone in wind.

The computational process of determining the joint angles required to position a robot's end-effector at a desired pose (position and orientation). It is a fundamental sub-problem within motion planning.

• Multiple Solutions: A single end-effector pose often maps to many joint configurations (kinematic redundancy).
• Integration: Motion planners frequently call IK solvers to check if a sampled end-effector goal or waypoint is kinematically achievable.

The fundamental representation for motion planning. It is the space of all possible configurations of a robot, where each configuration is a complete specification of the position of every point on the robot.

• Obstacles: Physical obstacles in the workspace are mapped to forbidden regions in C-space (C-obstacles).
• Dimensionality: A robot's C-space has one dimension per degree of freedom (e.g., a 6-DOF arm has a 6D C-space). Planning algorithms search for a path in this space.

A seminal sampling-based motion planning algorithm designed for multiple queries in static environments. It operates in two phases:

1. Learning Phase: Randomly samples valid configurations in C-space and connects nearby samples with simple local paths to form a graph (the roadmap).
2. Query Phase: Connects the start and goal configurations to the roadmap and searches the graph for a path.

• Strength: Efficient for complex, high-dimensional spaces once the roadmap is built.

A sampling-based algorithm designed for single-query planning in high-dimensional spaces. It incrementally builds a tree rooted at the start configuration by:

• Randomly sampling a point in C-space.
• Finding the nearest node in the existing tree.
• Extending the tree from that node toward the sample.
• *Variant (RRT)**: An asymptotically optimal version that rewires the tree to find increasingly better paths.
• Use: Standard for robotic arm and mobile robot path planning.