МФТИ — Весна 2020 — ИСРТ

МФТИ — Весна 2020 — ИСРТ

Интеллектуальные системы в робототехнике [Планирование траектории]

Материалы по теме «Планирование траектории» в рамках курса «Интеллектуальные системы в робототехнике» (МФТИ, 2019-2020 уч.г., 2-й семестр, 3-й курс бакалавриата).

Расписание и программа курса

В связи с карантинными мерами расписание — примерное. Точное расписание уточняйте у старосты.

19.03.2020 // 15:30 — 17:00 // Лекция в дист. формате (через Zoom) // Введение в проблемную область // Презентация.

26.03.2020 // 15:30 — 17:00, 17:20 — 18:50 // Лекция в дист. формате (через Zoom) // Планирование траектории как поиск пути на графе особой структуры. Графовые модели для задачи планирования траектории. // Презентация.

09.04.2020 (дата уточняется) // 15:30 — 17:00, 17:20 — 18:50 // Лекция в дист. формате (через Zoom) // Алгоритм Дейкстры/A*. Принцип работы. Эвристические функции для алгоритма A*. Особенности программной реализации. // Презентация.

16.04.2020 // 15:30 — 17:00 // Прием лабораторного задания (через Zoom).

23.04.2020 // 15:30 — 17:00 // Прием лабораторного задания (через Zoom).

21.05.2020 // 15:30 — 16:10 // Прием лабораторного задания (1/2). Через Zoom.

21.05.2020 // 16:15 — 16:45 // Прием лабораторного задания (2/2). Через Zoom.

Ведомость по курсу

Задание

Задание состоит а) в написании на языке Python алгоритма A* для поиска пути на графе регулярной декомпозиции; б) проведении серии экспериментов с кодом; в) оформлении результатов экспериментального исследования.

Jupyter-тетрадка с заготовкой кода.

Требования к выполнению задания приведены непосредственно в тетрадке (в комментариях к коду и в текстовых ячейках).

Необходимо сдать: работоспособную тетрадку + отчет о тестировании в формате pdf (отчет должен отображать результаты тестирования в виде графиков/таблиц).

Материалы для самостоятельного изучения

Обзоры

  1. Search-based Planning with Motion Primitives — обзорная презентация (tutorial) на тему планирования траектории от Максима Лихачева (Maxim Likhachev), сотрудника Robotics Institute, Carnegie Melon University — одного из ведущих специалистов в этой области.
  2. AAAI 2020 Tutorial on Heuristic Search — материалы обзорных лекций (tutorial) об эвристическом поиске, прочитанных в рамках одной из ведущих конференций по ИИ в мире AAAI 2020.
  3. Amit’s A* Pages — изложение основ алгоритма A* (и других) в научно-популярном стиле.

Демо

  1. http://pathplanning.ru — планирование на реальной карте OpenStreetMaps.
  2. https://qiao.github.io/PathFinding.js/visual/ — пошаговая онлайн-анимация алгоритмов A*, IDA*, Jump Point Search и др.
  3. https://www.redblobgames.com/pathfinding/a-star/introduction.html — множество примеров отдельных процедур алгоритмов поиска пути (+ код на Pytnon, но на него лучше не ориентироваться, он очень упрощён).
  4. https://movingai.com/astar.html — видео, наглядно демонстрирующее эффект применения различных tie-breaking стратегий при реализации A*.

Научные публикации

  1. TBC