Pathplanning.ru :: автоматическое планирование траектории (2018) (проект)
| Ментор | Константин Яковлев |
| Учебный семестр | Осень 2018 |
| Учебный курс | 2-й курс |
| Проект можно развивать на летней практике | |
| Максимальное количество студентов, выбравших проект: 10 | |
Что это за проект?
Планирование траектории - одна из основополагающих способностей любого интеллектуального агента (робота, персонажа в компьютерной игре и т.д.), поэтому методам планирования пространственных перемещений всегда уделялось (и продолжает уделяться) большое внимание в искусственном интеллекте. Несмотря на кажущуюся простоту это нетривиальная (challenging) задача, для решение которой необходимо не только уверенное знание математических и компьютерных наук, но и изобретательность.
В научной лаборатории, в которой я работаю, мы с коллегами уже не первый год занимаемся этой интересной тематикой: ведем научные исследования, публикуемся в научных журналах, делаем доклады о наших новых разработках на конференциях и семинарах. Предлагаю и вам познакомиться с областью path finding и овладеть базовыми алгоритмами, которые в дальнейшем можно будет развивать, совершенствовать и применять в реальных системах (навигационные сервисы, робототехника и др.).
В рамках предлагаемого проекта вы познакомитесь с основными методами планирования траектории на плоскости, такими как A*, Theta*, JPS, изучите теоретические основы их работы, а также программно их реализуете.
В дальнейшем возможно развитие проекта с его трансформацией в дипломную работу (выпускную квалификационную работу бакалавра) высокого уровня, содержащую как научную часть (методы и алгоритмы интеллектуального планирования траектории), так и практическую – программную реализацию алгоритмов. В дальнейшем также возможно участие в научных исследованиях и проектах по этой тематике (написание статей, поездки на конференции и т.д.).
PS: Пример системы, разработанной моими студентами в рамках проектных/курсовых/дипломных работ: pathplanning.ru (используется привязка к реальным данным Openstreetmaps + собственноручно реализованные алгоритмы планирования).
PPS: Обратите также внимание на проекты А.Панова.
Чему вы научитесь?
- алгоритмам эвристического поиска на практике
- основам ООП на практике (работа с классами)
- современным технологиям разработки ПО (IDE, отладка и др.)
- основам разработки кросс-платформенных приложений
Какие начальные требования?
- базовая математическая и алгоритмическая подготовка.
- С/С++.
- основы ООП.
- технический английский (для чтения руководств, статей и пр. научно-технической литературы).
Какие будут использоваться технологии?
- C++ в качестве языка программирования.
- Qt.Creator в качестве IDE.
- XML в качестве формата входных/выходных данных.
Темы вводных занятий
- О проблеме планирования траектории, ее месте в искусственном интеллекте и робототехнике
- О планировании траектории, как о задаче поиска пути на графе специального вида (формальная постановка задачи, основные методы и алгоритмы)
- О среде разработки Qt.Creator, об используемых форматах входных/выходных данных
- Об эвристических алгоритмах поиска пути на графе специального вида
- О программной реализации алгоритмов семейства A* (декомпозиция на функциональные блоки, выбор структур и контейнеров для хранения данных поиска)
Занятия будут проводится в течении всего срока выполнения проекта и соответствовать текущей фазе (сначала - общие вопросы, потом - специализированные).
Направления развития
- Планирование в 3D
- Any-angle и angle-constrained планирование (ANYA*, LIAN и др.)
- Многоагентное планирование (M*, CBS и др.)
- Планирование в динамической среде (D*, D* Lite)
- Алгоритмы семейства RRT
- Разработка GUI-утилит для систем планирования (редакторы карт, трассировщики, отладчики, визуализаторы и др.)
Отдельное направление развития - интеграция разработанных методов в системы управления мобильными роботами. Как первый шаг в этом нарпавлении - интеграция с ROS, Gazebo (для TurtleBot). После успещного выполнения проекта возможент перенос алгоритма на реального робота.
Критерии оценки
4-5: Функционал A* (и Dijkstra) реализован в программном коде, все опции (разрешенные движения, вес и тип эвристики, разрешенные движения и пр.) hard-coded, проект компилируется и корректно работает (выходной файл требуемого формата, результат работы алгоритма совпадает с эталоном).
6: Функционал A* (и Dijkstra) реализован в программном коде, поддерживаются все необходимые опции поиска (разрешенные движения, вес и тип эвристики и пр.), проект компилируется и корректно работает (выходной файл требуемого формата, результат работы алгоритма совпадает с эталоном).
7: Функционал A* (и Dijkstra) реализован в программном коде, поддерживаются все необходимые опции поиска (разрешенные движения, вес и тип эвристики и пр.), проект компилируется и корректно работает (выходной файл требуемого формата, результат работы алгоритма совпадает с эталоном). Поддерживаются разные уровни логирования (вывода промежуточной информации).
8: То же, что и на оценку 7 + реализован алгоритм Theta*.
9: То же, что и на оценку 8 + реализован алгоритм Jump Point Search.
10: Вполнено дополнительное индивидуальное задание по согласованию с ментором (это может быть реализация более продвинутого алгоритма, перенос алгоритма на реального робота и пр.).
Ориентировочное расписание занятий
По договренности: ПН 16:40-18:00; ПТ 16:40-18:00;
+ телеграмм-группа 24/7 для максимально-оперативного решения вопросов.
