Courses / theory

Path Planning Algorithms

intermediate~13 hours12 lessonsEnvironment: pyodide

Prerequisites: python3, maths-for-robotics, kinematics-mobile-robots

Start: The planning problem: states, actions, costsPractice questions

Modules

Module 1 — Search on grids
  1. 1The planning problem: states, actions, costs
  2. 2Dijkstra: flood the world with cost
  3. 3A*: heuristics, admissibility, and the speedup
  4. 4Widget: grid planner sandbox
Module 2 — Sampling-based planning
  1. 1Why grids die in high dimensions
  2. 2RRT and RRT-Connect
  3. 3Widget: watch the tree grow
Module 3 — Fields, smoothing, and real robots
  1. 1Potential fields: gradient descent to the goal
  2. 2Path smoothing and shortcutting
  3. 3Kinodynamic constraints: planning for robots that can't sidestep
Module 4 — The shootout
  1. 1A benchmark harness: success rate, cost, expansions, time
  2. 2Project: planner shootout on standard worlds

Textbooks

  • Planning Algorithms — Steven M. LaVallefree-book
  • Principles of Robot Motion — Choset, Lynch, Hutchinson et al.book