Pathplanning.ru :: автоматическое планирование траектории (проект) — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
м
(увеличилось количество студентов)
 
(не показано 9 промежуточных версии 3 участников)
Строка 3: Строка 3:
 
|mentor=Яковлев Константин
 
|mentor=Яковлев Константин
 
|mentor_login={{URLENCODE:Kyakovlev|WIKI}}
 
|mentor_login={{URLENCODE:Kyakovlev|WIKI}}
|semester=Осень 2016
+
|semester=Осень 2017
 
|course=2
 
|course=2
 
|summer=on
 
|summer=on
|number_of_students=5
+
|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*, JPS, Theta*)''', изучите теоретические основы их работы, а также программно их реализуете.
+
В рамках предлагаемого проекта вы познакомитесь с основными '''методами планирования траектории на плоскости''', такими как A*, Theta*, JPS, изучите теоретические основы их работы, а также программно их реализуете.
  
 
В дальнейшем возможно развитие проекта с его трансформацией в дипломную работу (выпускную квалификационную работу бакалавра) высокого уровня, содержащую как научную часть (методы и алгоритмы интеллектуального планирования траектории), так и практическую – программную реализацию алгоритмов. В дальнейшем также возможно участие в научных исследованиях и проектах по этой тематике (написание статей, поездки на конференции и т.д.).
 
В дальнейшем возможно развитие проекта с его трансформацией в дипломную работу (выпускную квалификационную работу бакалавра) высокого уровня, содержащую как научную часть (методы и алгоритмы интеллектуального планирования траектории), так и практическую – программную реализацию алгоритмов. В дальнейшем также возможно участие в научных исследованиях и проектах по этой тематике (написание статей, поездки на конференции и т.д.).
  
PS: Пример системы, разработанной моими студентами в качестве дипломной работы: '''[http://pathplanning.ru pathplanning.ru]''' (используется привязка к реальным данным Openstreetmaps + собственноручно реализованные алгоритмы планирования).
+
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 А.Панова].
  
 
=== Чему вы научитесь? ===
 
=== Чему вы научитесь? ===
Строка 28: Строка 34:
  
 
=== Какие начальные требования? ===
 
=== Какие начальные требования? ===
 +
* базовая математическая и алгоритмическая подготовка.
 
* С/С++.
 
* С/С++.
 
* основы ООП.
 
* основы ООП.
Строка 38: Строка 45:
  
 
=== Темы вводных занятий ===
 
=== Темы вводных занятий ===
* О проблеме планирования траектории, ее месте в искусственном интеллекте
+
* О проблеме планирования траектории, ее месте в искусственном интеллекте и робототехнике
* О планировании траектории, как о задаче поиска пути на графе специального вида
+
* О планировании траектории, как о задаче поиска пути на графе специального вида (формальная постановка задачи, основные методы и алгоритмы)
 
* О среде разработки Qt.Creator, об используемых форматах входных/выходных данных
 
* О среде разработки Qt.Creator, об используемых форматах входных/выходных данных
 +
* Об эвристических алгоритмах поиска пути на графе специального вида
 +
* О программной реализации алгоритмов семейства A* (декомпозиция на функциональные блоки, выбор структур и контейнеров для хранения данных поиска)
 +
 +
 +
Занятия будут проводится в течении всего срока выполнения проекта и соответствовать текущей фазе (сначала - общие вопросы, потом - специализированные).
  
 
=== Направления развития ===
 
=== Направления развития ===
 
* Планирование в 3D
 
* Планирование в 3D
* Поддержка новых алгоритмов планирования (ANYA*, LIAN и др.)
+
* 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 стратегии, разрешенные движения и пр.), проект компилируется и корректно работает (выходной файл требуемого формата).  
  
6-7: Функционал A*, JPS и Theta* реализован в программном коде, проект компилируется и корректно работает на корректных входных данных.
+
8-9: Функционал A*, Theta* и JPS реализован в программном коде с использованием грамотной иерархии классов (наследование, не дублирование основного функционала и пр.), поддерживаются различные опции поиска (вес эвристики, breaking ties стратегии, разрешенные движения и пр.), проект компилируется и корректно работает (выходной файл требуемого формата).
  
8-9: Функционал A*, JPS и Theta* реализован в программном коде с использованием грамотной иерархии классов (наследование, не дублирование основного функционала и пр.). Проект компилируется и корректно работает на корректных входных данных.  
+
10: Программный код встроен в ROS и используется для планирования траектории TurtleBot (симуляция в Gazebo).
  
10: Функционал A*, JPS и Theta* реализован в программном коде с использованием грамотной иерархии классов (наследование, не дублирование основного функционала и пр.). Проект компилируется и корректно работает в том числе и на любых (в т.ч. "испорченных") входных данных.
+
PS: После выполнения задания на 10 возможно перенесение кода для управления реальным роботом, который будет куплен в нашу лабораторию на ФКН в октябре-ноябре 2017, и дальнейшая доработка ПО (см. направления развития).
  
 
=== Ориентировочное расписание занятий ===
 
=== Ориентировочное расписание занятий ===
По договоренности. Предпочтительное время занятий: СР 15:00-20:00 ЧТ 15:00-20:00 ПТ 15:00-18:00
+
По договоренности. В 2016/2017 уч. году был ПН 16:40-18:00.

Текущая версия на 14:53, 1 сентября 2017

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



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

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

Pplru-robo.jpg

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

Pplru-1.pngPplru-2.png

В рамках предлагаемого проекта вы познакомитесь с основными методами планирования траектории на плоскости, такими как 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.