Planning
Finding a route before driving it: the configuration space, a grid as a graph, breadth first, Dijkstra, A* and what makes a heuristic admissible, potential fields and their local minima, and a sampling planner for when the grid is the wrong tool.
Start in the simulator- U9.1 The configuration space Grow the obstacles by the robot's radius and the robot becomes a point, which is the whole reason planning is tractable.
- U9.2 A grid is a graph Cells are nodes, neighbours are edges, and breadth first search is the shortest path when every step costs the same.
- U9.3 Dijkstra and the cost of a step When steps cost different amounts, the cheapest route is not the shortest one, and a queue sorted by cost finds it.
- U9.4 A* and the heuristic Guessing what is left to pay, why the guess must never be too high, and why greedy best first is not A*.
- U9.5 Potential fields The goal pulls, the obstacles push, and the robot slides downhill into a local minimum.
- U9.6 Sampling: the RRT Throwing darts at the free space instead of enumerating it, and what probabilistic completeness does and does not…
- U9.7 Project: plan a route and drive it A plan computed on board, shortened, and then followed across a mat with two walls in it.