Stanford OnlineStanford AA274A Principles of Robotic Autonomy | Autumn 2019 | Motion Planning Graph Search Methods
Stanford Online
Course pace and scope 0:04
The hardest stretch is said to be over after the first two weeks. Those weeks covered harder math and the basic tools at the same time, like the terminal and Python. From here on, the pace is expected to stay steady, and you should be able to focus on the material itself.
Motion planning basics 1:30
Motion planning is framed as a kind of optimal control with hard state limits, especially obstacle avoidance. The goal is to find a sequence of actions that moves a robot from start to finish while respecting motion limits and, sometimes, a cost function. The lecture points to graph search and label-correcting methods, then explains how grid choice and neighborhood links affect solution quality and computation.
Frontier expansion 24:31
The search takes one node from the frontier and checks each neighbor. For each neighbor, it asks whether reaching it through the current node gives a lower cost than the path found before. If so, the path label is updated and the neighbor is added to the frontier. This is the basic label-correcting step.
Known maps and search order 27:01
The map is assumed to be known, and the robot is treated as a point after any body shape is folded into the obstacles. The cost to reach a node is usually path length. The search starts at the initial node with all other costs set to infinity, so each new route found is better than what came before. A node is expanded, then its neighbors, in a wave moving outward from the start.
Stopping and priorities 34:31
The algorithm stops when the frontier is empty. If a path to the goal exists, the method finishes in finite time and returns an optimal path. Different versions choose frontier nodes in different ways. One common version keeps a best cost to the goal as an upper bound and skips nodes whose reach cost already exceeds it. Dijkstra’s version picks the node with the lowest reach cost, while depth-first and breadth-first versions use stack or queue order instead.
Why use heuristics 46:30
Dijkstra-like search expands evenly in all directions, so it can waste work in areas that do not help reach the goal. Heuristic search adds an estimate of the remaining cost, and that estimate must be a lower bound. The idea is to rank nodes by reach cost plus estimated remaining cost, so the search is pushed toward the goal instead of spreading everywhere.
A* and Heuristics 49:01
The search is ordered by the path cost so far plus a guess at the cost left to the goal. A simple guess is the straight-line, Euclidean distance, which ignores obstacles. For the method to stay sound, that guess must never be larger than the true remaining cost, and it should be fast to compute. With that in place, A* uses fewer priority-queue entries than plain Dijkstra search and still finds the optimal path.
Configuration Space 53:31
Motion planning is then recast as path finding in configuration space, where a robot is treated as a point and the obstacles are enlarged to match that simplification. For a triangle robot, the configuration may include x, y, and heading, and heading must be handled as circular, so zero and 2π are the same. The hard part is mapping real obstacles into this higher-dimensional space. That step is usually expensive or unavailable, which is why these explicit methods are mostly conceptual and lead to sampling methods later.
Concluding notes 1:12:30
CGAL can make the geometry work much easier. It supports basic computations like Voronoi diagrams and solid constructions, and the speaker points you to it if you want to use computational geometry. Combinatorial methods are complete, but they become impractical beyond three or four degrees of freedom.
What to remember 1:14:30
The main takeaway is grid-based motion planning, especially A*. That is the tool to remember for the rest of the course. For the midterm, expect conceptual questions about grid methods and about the sampling methods covered next class, but not about combinatorial planning.
AI-generated summary. It can be wrong or incomplete - check anything that matters against the original.
