Week 9 — Advanced Motion Planning Day 1 of 7 | Difficulty: ⭐⭐⭐⭐
What Is Motion Planning?
Motion planning answers the question: “How do I get from here to there without hitting anything?”
It is one of the oldest and most studied problems in robotics. Every autonomous vehicle, warehouse robot, and surgical arm relies on a motion planner running behind the scenes.
There are two related but distinct concepts:
| Concept | Output | Constraints | Examples |
|---|---|---|---|
| Path planning | A geometric curve in space | Collision-free | A*, RRT, PRM |
| Trajectory planning | A curve + time parameterization | Collision-free + velocity/acceleration limits | CHOMP, STOMP, TrajOpt |
This week focuses on both, starting with the mathematical foundation: C-space.
Configuration Space (C-space)
A robot’s configuration is a complete specification of its position. For a 2-DOF arm, it is the pair of joint angles $(q_1, q_2)$. For a mobile robot, it is $(x, y, \theta)$.
The configuration space (C-space) is the set of all possible configurations. If each joint ranges $[0, 2\pi)$, the C-space is $[0, 2\pi)^n$ for an $n$-joint arm.
Why C-space Matters
Planning in the robot’s physical workspace (the 3D room) is hard because the robot has a shape. In C-space, the robot is a single point, and obstacles become regions. This transforms a geometry problem into a point-navigation problem.
Definition: The C-obstacle $C_{obs}$ is the set of all configurations where the robot collides with a workspace obstacle. The free space is $C_{free} = C_{space} \setminus C_{obs}$.
Example: 2-DOF Planar Arm
A 2-link arm with lengths $L_1, L_2$ and joint limits $[0, \pi]$ has a rectangular C-space $[0, \pi]^2$.
An obstacle in the workspace maps to a curved region in C-space. Computing $C_{obs}$ exactly is mathematically difficult — sampling-based planners avoid this by using collision checking instead.
Visibility Graphs (Exact Planning)
For polygonal robots and polygonal obstacles in 2D, visibility graphs provide an exact solution:
- Place a vertex at every obstacle corner.
- Place a vertex at the robot’s start and goal.
- Connect every pair of vertices with an edge if the straight line between them does not intersect an obstacle.
- Run Dijkstra or A* on this graph.
Key Data: Visibility graphs find the shortest path in 2D with $O(n^3)$ edges for $n$ vertices. They are exact but impractical in high-dimensional C-spaces.
Path vs. Trajectory: The Critical Difference
| Path | Trajectory | |
|---|---|---|
| Variable | Spatial coordinates $s$ | Time $t$ |
| Output | $q(s)$ — a curve | $q(t)$ — a curve with timing |
| Smoothness | Geometric smoothness | Dynamic feasibility (vel/acc limits) |
| Use case | ”Which doorway?" | "How fast through the doorway?” |
A path planner produces a sequence of waypoints. A trajectory planner assigns timing, ensuring the robot can actually follow it given motor torque and speed limits.
Review Week 8
Week 8 covered control systems: PID, LQR, EKF, and ROS2 implementation. The control loop executes trajectories. Week 9 covers how to generate those trajectories.
Preview Week 9
| Day | Topic |
|---|---|
| 2 | Search-based planning: A*, Dijkstra, Hybrid A* |
| 3 | Sampling-based planning: RRT, RRT*, PRM |
| 4 | Trajectory optimization: CHOMP, STOMP, TrajOpt |
| 5 | Kinodynamic planning with dynamic constraints |
| 6 | Python practice: RRT* for a 2-DOF arm |
| 7 | Week 9 summary |
Further Reading
- “Planning Algorithms” (Steven M. LaValle) — The definitive free textbook on motion planning
- “Probabilistic Roadmaps” (Kavraki et al., 1996) — Foundational PRM paper
- “Rapidly-Exploring Random Trees” (LaValle, 1998) — Foundational RRT paper
FAQ
Q: Why not plan directly in workspace instead of C-space?
A: Workspace planning requires checking collision for every link at every step. C-space reduces the robot to a point — collision becomes a simple membership test ($q \in C_{free}$?).
Details: For a 6-DOF arm, workspace collision checking requires computing the forward kinematics of all links and testing against every obstacle. In C-space, you only check one point. The tradeoff is that C-space is 6-dimensional and hard to visualize.
Q: When are visibility graphs better than sampling methods?
A: Only for 2D polygonal problems where exact shortest paths matter. In 3D or with articulated robots, sampling methods (RRT, PRM) dominate.
Details: Visibility graphs scale poorly — $O(n^3)$ edges for $n$ vertices. A 6-DOF arm has an infinite C-space (continuous angles), making exact methods impossible. Sampling methods trade optimality for scalability.
Q: What is the difference between holonomic and non-holonomic robots?
A: A holonomic robot can move in any direction in C-space from any configuration (e.g., a hover drone). A non-holonomic robot has velocity constraints that limit its instantaneous motion (e.g., a car cannot slide sideways).
Details: Holonomic planners can directly interpolate between any two configurations. Non-holonomic planners must respect differential constraints — turning a car requires forward motion. This makes planning significantly harder and requires kinodynamic methods (Day 5).