Stanford выложил лекцию Марко Павоне о планировании движения роботов на графах

Stanford Online выложил на YouTube лекцию 6 из курса AA274A Principles of Robotic Autonomy, посвящённую планированию движения методами поиска на графах (Motion Planning I). Читает её Марко Павоне: ассоциированный профессор аэронавтики и астронавтики Стэнфорда, старший директор по исследованиям автономных автомобилей в NVIDIA, в прошлом исследователь робототехнической группы JPL NASA. Запись сделана осенью 2019 года. Издатели прямо предупреждают, что структура курса, задания и материалы с тех пор могли измениться.

Это учебный материал, а не новость о релизе. Но он закрывает одну из базовых тем любого робототехнического стека, и у него необычно сильный авторский контекст.

О чём лекция

Планирование движения по графу сводит задачу робота к поиску. Пространство возможных положений дискретизируется: узлы обозначают состояния, рёбра обозначают допустимые переходы, а у каждого ребра есть стоимость. Дальше нужно найти путь от старта до цели с минимальной суммарной стоимостью.

Стандартный набор инструментов для этой постановки хорошо известен. Алгоритм Дейкстры находит оптимальный путь, но расширяет вершины во все стороны. A добавляет эвристическую оценку расстояния до цели и ищет направленнее. Если эвристика допустима, то есть не завышает реальную стоимость, A сохраняет гарантию оптимальности. Дейкстра при этом оказывается частным случаем A* с нулевой эвристикой. Конкретный состав разбора в записи лучше проверять по самому видео: описание к нему перечисляет только тему лекции.

Почему автор важен

Павоне работает на стыке академической робототехники и промышленной разработки автономного вождения. Это заметно по самому курсу: он выстроен как путь от восприятия и оценки состояния к планированию и управлению, а не как набор разрозненных алгоритмов. Отдельная лекция про графовый поиск здесь служит фундаментом. На него позже ложатся более сложные планировщики и методы с обучением.

Параметры публикации:

• Курс: AA274A Principles of Robotic Autonomy, лекция 6
• Тема: Motion Planning I, методы поиска на графах
• Спикер: Marco Pavone, Stanford и NVIDIA
• Дата записи: осень 2019 года
• Формат: видео на канале Stanford Online
• Учебник: Principles of Robot Autonomy, бесплатно на porabook.com
• Актуальное расписание: stanfordasl.github.io/PoRA-I

Как использовать материал

Посмотреть лекцию стоит вместе с соответствующей главой учебника. Лучший способ проверить понимание: написать A* на сетке 2D в несколько десятков строк на Python. Затем стоит сравнить его с алгоритмом Дейкстры на одной и той же карте с препятствиями и подсчитать, сколько вершин расширяет каждый из них. Разница в числе раскрытых узлов быстро показывает, что такое эвристика на практике.

Инженерам, которые работают с мобильными платформами или беспилотниками, полезно сопоставить лекцию с планировщиком в собственном стеке. Часто выясняется, что стоимость рёбер, шаг дискретизации и выбор эвристики влияют на поведение робота сильнее, чем сам алгоритм поиска.

Одна оговорка. Запись относится к версии курса 2019 года. Если вам нужна программа в её нынешнем виде, включая новые темы и задания, сверяйтесь с актуальным силлабусом на сайте лаборатории ASL. Лекция подойдёт как бесплатная точка входа для тех, кто хочет разобраться в основах планирования до того, как перейти к более современным подходам.