Lesson 13 · Book chapter pointer
Path planning
Read the chapter source: pathplanning.tex — do not treat this note as the book.
Learning goals
- State a planning problem as start, goal, free space, and a cost.
- Run A* on a grid in your head: g, h, admissible heuristics.
- Know what sampling methods (RRT-family) buy you in continuous spaces.
- Treat potential fields as a cheap local method with known traps.
- Separate a geometric path from a dynamically feasible trajectory.
Teaching note
Planning is search with a map and a promise. You need a start, a goal, a definition of free, and a cost (distance, time, risk). If any of those is fuzzy, the algorithm will still return a polyline — it will just be a polyline through the wrong problem. Write the four pieces on the board before you name A*.
Grid A* is the algorithm every roboticist should be able to implement on a napkin. \(g\) is cost from start. \(h\) is a hopeful remaining cost. If \(h\) never overestimates, the first time you pop the goal you have an optimal path on that graph. Manhattan distance is admissible if you only move 4-connected; Euclidean is the usual continuous hope. The studio sketch lets you paint walls and watch the flood. Use it. Then ask what the grid forgot: turning radius, speed, the fact that the robot is not a point.
Sampling-based planners exist because six-dimensional arms do not enjoy million-cell grids. You sprinkle configurations, connect neighbors if the edge is free, and grow toward the goal (RRT) or keep a roadmap (PRM). They are probabilistically complete under assumptions, not optimal unless you pay extra (RRT*). They return jagged paths you should smooth. They also fail silently in narrow passages if you do not sample enough. Show a bug trap.
Potential fields are the impatient cousin: attract to the goal, repel from obstacles, follow the gradient. They are wonderful until they park in a local minimum. Teach them as a local controller, not as a global planner. Mixing A* globally with a field or DWA locally is a standard, respectable stack.
A path is a shape. A trajectory is a shape with time and a motor who can track it. Differential-drive robots cannot follow an arbitrary polyline sideways. After you have a path, you still owe the kinematics lesson a favor. Read the book chapter for the algorithms and proofs this note is only allowed to advertise. Then break the studio A* on purpose.
A* ranking: \(f(n)=g(n)+h(n)\), with \(h\) admissible. Optimism in \(h\) is allowed; lying about remaining cost is not.