Pathplanning.ru :: автоматическое планирование траектории (проект)

Ментор	Яковлев Константин
Учебный семестр	Осень 2017
Учебный курс	2-й курс
Проект можно развивать на летней практике
Максимальное количество студентов, выбравших проект: 6

Что это за проект?

Планирование траектории - одна из основополагающих способностей любого интеллектуального агента (робота, персонажа в компьютерной игре и т.д.), поэтому методам планирования пространственных перемещений всегда уделялось (и продолжает уделяться) большое внимание в искусственном интеллекте. Несмотря на кажущуюся простоту это нетривиальная (challenging) задача, для решение которой необходимо не только уверенное знание математических и компьютерных наук, но и изобретательность.

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

В рамках предлагаемого проекта вы познакомитесь с основными методами планирования траектории на плоскости, такими как A*, Theta*, JPS, изучите теоретические основы их работы, а также программно их реализуете.

В дальнейшем возможно развитие проекта с его трансформацией в дипломную работу (выпускную квалификационную работу бакалавра) высокого уровня, содержащую как научную часть (методы и алгоритмы интеллектуального планирования траектории), так и практическую – программную реализацию алгоритмов. В дальнейшем также возможно участие в научных исследованиях и проектах по этой тематике (написание статей, поездки на конференции и т.д.).

PS: Пример системы, разработанной моими студентами в рамках проектных/курсовых/дипломных работ: pathplanning.ru (используется привязка к реальным данным Openstreetmaps + собственноручно реализованные алгоритмы планирования).

PPS: Обратите также внимание на проекты А.Панова.

Чему вы научитесь?

• алгоритмам эвристического поиска на практике
• основам ООП на практике (работа с классами)
• современным технологиям разработки ПО (IDE, отладка и др.)
• основам разработки кросс-платформенных приложений

Какие начальные требования?

• базовая математическая и алгоритмическая подготовка.
• С/С++.
• основы ООП.
• технический английский (для чтения статей).

Какие будут использоваться технологии?

• C++ в качестве языка программирования.
• Qt.Creator в качестве IDE.
• XML в качестве формата входных/выходных данных.

Темы вводных занятий

• О проблеме планирования траектории, ее месте в искусственном интеллекте и робототехнике
• О планировании траектории, как о задаче поиска пути на графе специального вида (формальная постановка задачи, основные методы и алгоритмы)
• О среде разработки Qt.Creator, об используемых форматах входных/выходных данных
• Об эвристических алгоритмах поиска пути на графе специального вида
• О программной реализации алгоритмов семейства A* (декомпозиция на функциональные блоки, выбор структур и контейнеров для хранения данных поиска)

Занятия будут проводится в течении всего срока выполнения проекта и соответствовать текущей фазе (сначала - общие вопросы, потом - специализированные).

Направления развития

• Планирование в 3D
• Поддержка новых алгоритмов планирования (ANYA*, LIAN и др.)
• Многоагентное планирование (M*, CBS и др.)
• Планирование в динамической среде (D*, D* Lite)
• Разработка GUI-утилит для систем планирования (редакторы карт, трассировщики, отладчики, визуализаторы и др.)

Критерии оценки

4-5: Функционал A* реализован в программном коде, проект компилируется и корректно работает на корректных входных данных.

6-7: Функционал A*, JPS и Theta* реализован в программном коде, проект компилируется и корректно работает на корректных входных данных.

8-9: Функционал A*, JPS и Theta* реализован в программном коде с использованием грамотной иерархии классов (наследование, не дублирование основного функционала и пр.). Проект компилируется и корректно работает на корректных входных данных.

10: Функционал A*, JPS и Theta* реализован в программном коде с использованием грамотной иерархии классов (наследование, не дублирование основного функционала и пр.). Проект компилируется и корректно работает в том числе и на любых (в т.ч. "испорченных") входных данных.

Ориентировочное расписание занятий

По договоренности. Предпочтительное время занятий: СР 15:00-20:00 ЧТ 15:00-20:00 ПТ 15:00-18:00