Stanford выложил лекцию Павоне о планировании движения: RRT, PRM и FMT*

Stanford Online выложил на YouTube седьмую лекцию курса AA274A Principles of Robotic Autonomy, «Motion Planning II: Sampling-Based Methods». Запись сделана осенью 2019 года. Читает Марко Павоне, адъюнкт-профессор кафедры аэронавтики и астронавтики Stanford и Senior Director по исследованиям автономных автомобилей в NVIDIA. До университета он работал в Jet Propulsion Laboratory NASA. Это не релиз продукта, а учебный материал, но тема напрямую определяет, как роботы и беспилотные машины строят траектории. Сам Stanford оговаривает, что структура курса, задания и материалы с 2019 года менялись, а ссылки в описании ведут на актуальную версию.

Почему планировщику нужны случайные точки

Классический поиск на графе (Dijkstra, A*) требует дискретизировать пространство конфигураций. Для плоского робота это терпимо. Для манипулятора с семью суставами и сеткой в 100 значений на ось получается 100 в седьмой степени, то есть около 10^14 ячеек. Хранить и обходить такую сетку невозможно.

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

Какие алгоритмы входят в этот блок

Тема лекции в описании заявлена общим названием, но стандартный набор для сэмплингового планирования выглядит так:

• PRM (Kavraki, Švestka, Latombe, Overmars, 1996): строит граф из случайных точек один раз и отвечает на множество запросов. Подходит для статичной среды.
• RRT (LaValle, 1998): растит дерево от старта в сторону случайных точек. Быстро находит путь в многомерных пространствах и для одного запроса удобнее PRM.
• RRT* (Karaman, Frazzoli, 2011): добавляет перестройку дерева и даёт асимптотическую оптимальность. Стоимость пути сходится к оптимуму при росте числа выборок.
• FMT* (Janson, Schmerling, Clark, Pavone, 2015): разработка группы Павоне. Обходит выборку в порядке, близком к методу быстрого марша, и часто достигает хорошего пути с меньшим числом проверок столкновений.
• Радиус соединения в PRM*: масштабируется как (log n / n)^(1/d), где d задаёт размерность пространства. Эта оценка лежит в основе доказательств оптимальности.

Главное теоретическое понятие здесь вероятностная полнота. Если путь существует, вероятность его найти стремится к единице с ростом числа точек. Гарантий по времени нет, и это важная оговорка.

Почему лекции 2019 года не устарели

Сэмплинговые планировщики никуда не делись. В библиотеке OMPL, которую MoveIt использует для планирования по умолчанию, есть реализации PRM, RRT, RRT* и FMT. Современные направления строятся поверх этой базы: обучаемые распределения для выбора точек, параллельная проверка столкновений на GPU, как в cuRobo от NVIDIA, и гибриды с оптимизацией траекторий. Узкое место у всех то же: проверка столкновений обычно съедает основную часть времени планирования.

У курса есть бесплатный учебник Principles of Robot Autonomy на porabook.com и открытый силлабус на stanfordasl.github.io/PoRA-I. Для самостоятельного изучения это редкий случай, когда лекции, текст и задания лежат в одном месте.

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

Начните с учебника, затем посмотрите лекцию. Реализуйте RRT на плоскости примерно в сотню строк кода и посчитайте, сколько вызовов проверки столкновений уходит на один путь. Потом подключите OMPL и сравните RRT, RRT и FMT на одной сцене с узким проходом. Именно там видна главная слабость методов: вероятность попасть в узкий коридор мала, и время поиска резко растёт.

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