Pathplanning.ru :: автоматическое планирование траектории (проект) — различия между версиями
Kyakovlev (обсуждение | вклад) м |
(увеличилось количество студентов) |
||
| (не показано 8 промежуточных версии 3 участников) | |||
| Строка 3: | Строка 3: | ||
|mentor=Яковлев Константин | |mentor=Яковлев Константин | ||
|mentor_login={{URLENCODE:Kyakovlev|WIKI}} | |mentor_login={{URLENCODE:Kyakovlev|WIKI}} | ||
| − | |semester=Осень | + | |semester=Осень 2017 |
|course=2 | |course=2 | ||
|summer=on | |summer=on | ||
| − | |number_of_students= | + | |number_of_students=10 |
|categorize=yes | |categorize=yes | ||
}} | }} | ||
=== Что это за проект? === | === Что это за проект? === | ||
| − | Планирование траектории - одна из основополагающих способностей любого интеллектуального агента (робота, персонажа в компьютерной игре и т.д.), поэтому методам планирования пространственных перемещений всегда уделялось (и продолжает уделяться) большое внимание в искусственном интеллекте. В научной лаборатории, в которой я работаю, мы с коллегами уже не первый год занимаемся этой интересной тематикой: ведем научные исследования, публикуемся в научных журналах, делаем доклады о наших новых разработках на конференциях и семинарах. Предлагаю и вам познакомиться с областью path finding и овладеть базовыми алгоритмами, которые в дальнейшем можно будет развивать, совершенствовать и применять в реальных системах (навигационные сервисы, робототехника и др.). | + | Планирование траектории - одна из основополагающих способностей любого интеллектуального агента (робота, персонажа в компьютерной игре и т.д.), поэтому методам планирования пространственных перемещений всегда уделялось (и продолжает уделяться) большое внимание в искусственном интеллекте. Несмотря на кажущуюся простоту это нетривиальная (challenging) задача, для решение которой необходимо не только уверенное знание математических и компьютерных наук, но и изобретательность. |
| + | |||
| + | [[Файл:Pplru-robo.jpg|320px]] | ||
| + | |||
| + | В научной лаборатории, в которой я работаю, мы с коллегами уже не первый год занимаемся этой интересной тематикой: ведем научные исследования, публикуемся в научных журналах, делаем доклады о наших новых разработках на конференциях и семинарах. Предлагаю и вам познакомиться с областью path finding и овладеть базовыми алгоритмами, которые в дальнейшем можно будет развивать, совершенствовать и применять в реальных системах (навигационные сервисы, робототехника и др.). | ||
[[Файл:Pplru-1.png|320px]][[Файл:Pplru-2.png|320px]] | [[Файл:Pplru-1.png|320px]][[Файл:Pplru-2.png|320px]] | ||
| − | В рамках предлагаемого проекта вы познакомитесь с основными '''методами планирования траектории на плоскости | + | В рамках предлагаемого проекта вы познакомитесь с основными '''методами планирования траектории на плоскости''', такими как A*, Theta*, JPS, изучите теоретические основы их работы, а также программно их реализуете. |
В дальнейшем возможно развитие проекта с его трансформацией в дипломную работу (выпускную квалификационную работу бакалавра) высокого уровня, содержащую как научную часть (методы и алгоритмы интеллектуального планирования траектории), так и практическую – программную реализацию алгоритмов. В дальнейшем также возможно участие в научных исследованиях и проектах по этой тематике (написание статей, поездки на конференции и т.д.). | В дальнейшем возможно развитие проекта с его трансформацией в дипломную работу (выпускную квалификационную работу бакалавра) высокого уровня, содержащую как научную часть (методы и алгоритмы интеллектуального планирования траектории), так и практическую – программную реализацию алгоритмов. В дальнейшем также возможно участие в научных исследованиях и проектах по этой тематике (написание статей, поездки на конференции и т.д.). | ||
| − | PS: Пример системы, разработанной моими студентами в | + | PS: Пример системы, разработанной моими студентами в рамках проектных/курсовых/дипломных работ: '''[http://pathplanning.ru pathplanning.ru]''' (используется привязка к реальным данным Openstreetmaps + собственноручно реализованные алгоритмы планирования). |
PPS: Обратите также внимание на проекты [http://wiki.cs.hse.ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Panov.ai А.Панова]. | PPS: Обратите также внимание на проекты [http://wiki.cs.hse.ru/%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Panov.ai А.Панова]. | ||
| Строка 30: | Строка 34: | ||
=== Какие начальные требования? === | === Какие начальные требования? === | ||
| + | * базовая математическая и алгоритмическая подготовка. | ||
* С/С++. | * С/С++. | ||
* основы ООП. | * основы ООП. | ||
| Строка 40: | Строка 45: | ||
=== Темы вводных занятий === | === Темы вводных занятий === | ||
| − | * О проблеме планирования траектории, ее месте в искусственном интеллекте | + | * О проблеме планирования траектории, ее месте в искусственном интеллекте и робототехнике |
| − | * О планировании траектории, как о задаче поиска пути на графе специального вида | + | * О планировании траектории, как о задаче поиска пути на графе специального вида (формальная постановка задачи, основные методы и алгоритмы) |
* О среде разработки Qt.Creator, об используемых форматах входных/выходных данных | * О среде разработки Qt.Creator, об используемых форматах входных/выходных данных | ||
| + | * Об эвристических алгоритмах поиска пути на графе специального вида | ||
| + | * О программной реализации алгоритмов семейства A* (декомпозиция на функциональные блоки, выбор структур и контейнеров для хранения данных поиска) | ||
| + | |||
| + | |||
| + | Занятия будут проводится в течении всего срока выполнения проекта и соответствовать текущей фазе (сначала - общие вопросы, потом - специализированные). | ||
=== Направления развития === | === Направления развития === | ||
* Планирование в 3D | * Планирование в 3D | ||
| − | * | + | * Any-angle и angle-constrained планирование (ANYA*, LIAN и др.) |
* Многоагентное планирование (M*, CBS и др.) | * Многоагентное планирование (M*, CBS и др.) | ||
* Планирование в динамической среде (D*, D* Lite) | * Планирование в динамической среде (D*, D* Lite) | ||
| + | * Алгоритмы семейства RRT | ||
* Разработка GUI-утилит для систем планирования (редакторы карт, трассировщики, отладчики, визуализаторы и др.) | * Разработка GUI-утилит для систем планирования (редакторы карт, трассировщики, отладчики, визуализаторы и др.) | ||
| + | |||
| + | Отдельное направление развития - интеграция разработанных методов в системы управления мобильными роботами. Как первый шаг в этом нарпавлении - интеграция с ROS, Gazebo (для TurtleBot). | ||
=== Критерии оценки === | === Критерии оценки === | ||
| − | 4-5: Функционал A* реализован в программном коде, проект компилируется и корректно работает | + | 4-5: Функционал A* реализован в программном коде, все опции (разрешенные движения, вес эвристики, breaking ties стратегии и пр.) hard-coded, проект компилируется и корректно работает (выходной файл требуемого формата). |
| + | |||
| + | 6-7: Функционал A* реализован в программном коде, поддерживаются различные опции поиска (вес эвристики, breaking ties стратегии, разрешенные движения и пр.), проект компилируется и корректно работает (выходной файл требуемого формата). | ||
| − | + | 8-9: Функционал A*, Theta* и JPS реализован в программном коде с использованием грамотной иерархии классов (наследование, не дублирование основного функционала и пр.), поддерживаются различные опции поиска (вес эвристики, breaking ties стратегии, разрешенные движения и пр.), проект компилируется и корректно работает (выходной файл требуемого формата). | |
| − | + | 10: Программный код встроен в ROS и используется для планирования траектории TurtleBot (симуляция в Gazebo). | |
| − | 10 | + | PS: После выполнения задания на 10 возможно перенесение кода для управления реальным роботом, который будет куплен в нашу лабораторию на ФКН в октябре-ноябре 2017, и дальнейшая доработка ПО (см. направления развития). |
=== Ориентировочное расписание занятий === | === Ориентировочное расписание занятий === | ||
| − | По договоренности. | + | По договоренности. В 2016/2017 уч. году был ПН 16:40-18:00. |
Текущая версия на 14:53, 1 сентября 2017
| Ментор | Яковлев Константин |
| Учебный семестр | Осень 2017 |
| Учебный курс | 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* реализован в программном коде, все опции (разрешенные движения, вес эвристики, breaking ties стратегии и пр.) hard-coded, проект компилируется и корректно работает (выходной файл требуемого формата).
6-7: Функционал A* реализован в программном коде, поддерживаются различные опции поиска (вес эвристики, breaking ties стратегии, разрешенные движения и пр.), проект компилируется и корректно работает (выходной файл требуемого формата).
8-9: Функционал A*, Theta* и JPS реализован в программном коде с использованием грамотной иерархии классов (наследование, не дублирование основного функционала и пр.), поддерживаются различные опции поиска (вес эвристики, breaking ties стратегии, разрешенные движения и пр.), проект компилируется и корректно работает (выходной файл требуемого формата).
10: Программный код встроен в ROS и используется для планирования траектории TurtleBot (симуляция в Gazebo).
PS: После выполнения задания на 10 возможно перенесение кода для управления реальным роботом, который будет куплен в нашу лабораторию на ФКН в октябре-ноябре 2017, и дальнейшая доработка ПО (см. направления развития).
Ориентировочное расписание занятий
По договоренности. В 2016/2017 уч. году был ПН 16:40-18:00.
