Автоматическое планирование траектории. Программа для оптимального поиска пути от одной точки до другой в двумерном пространстве

Август 8, 2022

Главная
Математика
Автоматическое планирование траектории. Программа для оптимального поиска пути от одной точки до другой в двумерном пространстве

Содержание

2. Высшая школа экономики, Москва, 2019 КРАТКОЕ ОПИСАНИЕ ПРОЕКТА фото фото фото Программа предназначена для оптимального поиска
3. Высшая школа экономики, Москва, 2019 ОСНОВНЫЕ ПОНЯТИЯ, ОПРЕДЕЛЕНИЯ, ТЕРМИНЫ фото фото фото Open-вершины – вершины, минимальное
4. Высшая школа экономики, Москва, 2019 АКТУАЛЬНОСТЬ РАБОТЫ фото фото фото Программа может быть предназначена для пользователей,
5. Высшая школа экономики, Москва, 2019 ЦЕЛЬ И ЗАДАЧИ РАБОТЫ фото фото фото Цель работы Программа находит
6. Высшая школа экономики, Москва, 2019 ВЫБОР АЛГОРИТМОВ ДЛЯ РЕАЛИЗАЦИИ фото фото фото Для реализации поиска пути
7. Высшая школа экономики, Москва, 2019 ОПИСАНИЕ A* фото фото Алгоритм работает следующим образом. Для начала достаётся
8. Высшая школа экономики, Москва, 2019 ДЕМОНСТРАЦИЯ РАБОТЫ A* фото фото
9. Высшая школа экономики, Москва, 2019 ОПИСАНИЕ ТИПОВ ДВИЖЕНИЯ фото фото фото Allowdiagonal – разрешено перемещение в
10. Высшая школа экономики, Москва, 2019 ОПИСАНИЕ ТИПОВ ЭВРИСТИК фото фото фото Манхэттенская – dx + dy
11. Высшая школа экономики, Москва, 2019 ТЕХНОЛОГИИ И ИНСТРУМЕНТЫ РЕАЛИЗАЦИИ фото фото фото Для написания кода используется
12. Высшая школа экономики, Москва, 2019 ТЕХНОЛОГИИ И ИНСТРУМЕНТЫ РЕАЛИЗАЦИИ фото фото фото Требуется найти следующее: существует
13. Высшая школа экономики, Москва, 2019 ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ фото фото фото Программа определяет наличие пути между
14. Высшая школа экономики, Москва, 2019 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ фото фото https://www.cs.helsinki.fi/u/bmmalone/heuristic-search-fall-2013/Korf1996.pdf http://www.cs.cmu.edu/~maxim/files/ad_aij08_preprint.pdf https://www.cs.cmu.edu/~maxim/files/tutorials/robschooltutorial_oct10.pdf http://theory.stanford.edu/~amitp/GameProgramming/ https://ru.wikipedia.org/wiki/A* http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_A*
16. Скачать презентацию

Слайд 2

Высшая школа экономики, Москва, 2019
КРАТКОЕ ОПИСАНИЕ ПРОЕКТА
фото
фото
фото
Программа предназначена для оптимального поиска

пути от одной точки до другой
в двумерном пространстве, используя в качестве приближения клетчатое поле, в итоге построив наиболее оптимальную ломанную. Задача сводится к поиску пути в графе между парой вершин. Областью применения может быть построение оптимальной траектории для роботов.

Слайд 3

Высшая школа экономики, Москва, 2019
ОСНОВНЫЕ ПОНЯТИЯ, ОПРЕДЕЛЕНИЯ, ТЕРМИНЫ
фото
фото
фото
Open-вершины – вершины, минимальное

расстояние до которых на данной стадии алгоритма ещё не найдено в процессе алгоритма.
Close-вершины – вершины, минимальное расстояние до которых найдено в процессе алгоритма.
Open – список, хранивший open-вершины.
Close – список, хранивший close-вершины.
В процессе работы алгоритма рассчитывается функция f пути от стартовой вершины до конечной. f = g + h.
g – наименьшее расстояние, найденное в процессе до от cтартовой до конкретной вершины.
h – эвристическое приближение до конечной вершины.

Слайд 4

Высшая школа экономики, Москва, 2019
АКТУАЛЬНОСТЬ РАБОТЫ
фото
фото
фото
Программа может быть предназначена для пользователей,

требующим возможность оптимального поиска пути в двумерном пространстве. Например при нахождении оптимального пути для беспилотных роботов, поиска пути на карте для курьера и других задачах на поиск пути в двумерном пространстве.

Слайд 5

Высшая школа экономики, Москва, 2019
ЦЕЛЬ И ЗАДАЧИ РАБОТЫ
фото
фото
фото
Цель работы Программа находит оптимальное

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

Слайд 6

Высшая школа экономики, Москва, 2019
ВЫБОР АЛГОРИТМОВ ДЛЯ РЕАЛИЗАЦИИ
фото
фото
фото
Для реализации поиска

пути используется алгоритмы: A*, дейкстра, а также различные эвристики, предназначенные для соответственного типа карты. Также реализованы разные типы движений. Среди эвристик используются: манхэттенская, диагональная, Евклидова и эвристика Чебышева.

Слайд 7

Высшая школа экономики, Москва, 2019
ОПИСАНИЕ A*
фото
фото
Алгоритм работает следующим образом. Для

начала достаётся одна из вершин c минимальным расстоянием из open, c наиболее благоприятным для нас потенциалом, изменяя минимальное расстояние до всех вершин в open и соответственно потенциал, добавляет данную вершину в сlose.
Все вершины из OPEN отбираются по f, при этом задействован BREAKINGTIES, определяющий, по какому критерию стоит отбирать вершину, в случае равенства f: при меньшем значении g или при меньшем значении h. Вершины в OPEN добавляются в качестве соответственной пары в приоритетную очередь.
Вершины в CLOSE добавляются в хеш-таблицу в качестве значения соответственного указателя, при этом хранится в значении относительном размеру таблицы(если weight – ширина, а height – длина, x, y – координаты, то weight * x + y – соответствующее значение для нужной вершины).

Слайд 8

Высшая школа экономики, Москва, 2019
ДЕМОНСТРАЦИЯ РАБОТЫ A*
фото
фото

Слайд 9

Высшая школа экономики, Москва, 2019
ОПИСАНИЕ ТИПОВ ДВИЖЕНИЯ
фото
фото
фото
Allowdiagonal – разрешено перемещение в

случае, когда обе угловые клетки при перемещении свободны.
cutcorners – разрешено лишь в случае если занято не более одной клетки из угловых.
allowsqueeze – разрешено перемещение по диагонали независимо от боковых клеток во время перемещения.

Слайд 10

Высшая школа экономики, Москва, 2019
ОПИСАНИЕ ТИПОВ ЭВРИСТИК
фото
фото
фото
Манхэттенская – dx + dy
Евклидова

– √(dx * dx + dy * dy)
Диагональная – (dx + dy) + (√2 - 2) * min(dx, dy)
Чебышева – (dx + dy) - min(dx, dy)

Пусть dx абсолютное расстояние по абсциссе, dy по ординате, тогда эвристики имеют вид

Слайд 11

Высшая школа экономики, Москва, 2019
ТЕХНОЛОГИИ И ИНСТРУМЕНТЫ РЕАЛИЗАЦИИ
фото
фото
фото
Для написания кода

используется qt, код написан на c++. Использован алгоритм A* с различными эвристиками, аналогично приведённым ниже ссылками. Для реализации поиска пути использована стандартная приоритетная очередь, находящаяся в STL.
Все вершины хранятся в структуре Node, которая содержит в себе координаты вершины, указатель на предка, а также f, g, h показатели, которые отвечают за нужный потенциал. Т.е g = минимальное найденное расстояние до конкретной вершины, h – некий потенциал(величина эвристики), отвечающий за оценку расстояния до конечной вершины. f = g + h, т.е f – ф-ция, отвечающая за оценку расстояния, проходящую через данную вершину. Эти показатели нужны для A*. В дейкстре мы считаем h(v) = 0 для любой v.
Алгоритм представляет из себя поиск пути от одной вершины до другой, храня список open-вершин и close-вершин.
Для open и close используется STL. Используется приоритетная очередь из STL(priotiy_queue), которая хранит список из open-вершин. Для close используется хеш-таблица пар ключей(unordered_map).

Слайд 12

Высшая школа экономики, Москва, 2019
ТЕХНОЛОГИИ И ИНСТРУМЕНТЫ РЕАЛИЗАЦИИ
фото
фото
фото
Требуется найти следующее:

существует ли путь(отвечает булевская переменная pathfound), длину пути(pathlength отвечает за длину, но принимает нулевое значение в случае отсутствии пути), список вершин, заданный в Node, по которым проходит путь в том виде, как его нашёл алгоритм(указатель на список в lppath), список вершин, заданный в Node, сокращённый по вектору направления, т.е в случае, когда соседние 3 координаты образуют прямую, то 2-я удаляется, т.к направление в данном случае не меняется(необходим для Theta*, указатель в hppath), общий список задействованных вершин(т.е суммарное кол-во вершин, находящихся в open и close, хранящихся в переменной nodescreated), общее число шагов алгоритма(хранится в numberofsteps). Все значения хранятся в структуре SearchResult.

Слайд 13

Высшая школа экономики, Москва, 2019
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
фото
фото
фото
Программа определяет наличие пути между

вершинами, находит расстояние, а также сам путь с учётом всех эвристик.

Слайд 14

Высшая школа экономики, Москва, 2019
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
фото
фото
https://www.cs.helsinki.fi/u/bmmalone/heuristic-search-fall-2013/Korf1996.pdf
http://www.cs.cmu.edu/~maxim/files/ad_aij08_preprint.pdf
https://www.cs.cmu.edu/~maxim/files/tutorials/robschooltutorial_oct10.pdf
http://theory.stanford.edu/~amitp/GameProgramming/
https://ru.wikipedia.org/wiki/A*
http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_A*

Автоматическое планирование траектории. Программа для оптимального поиска пути от одной точки до другой в двумерном пространстве

Содержание

Высшая школа экономики, Москва, 2019КРАТКОЕ ОПИСАНИЕ ПРОЕКТАфотофотофотоПрограмма предназначена для оптимального поиска

Высшая школа экономики, Москва, 2019ОСНОВНЫЕ ПОНЯТИЯ, ОПРЕДЕЛЕНИЯ, ТЕРМИНЫфотофотофотоOpen-вершины – вершины, минимальное

Высшая школа экономики, Москва, 2019АКТУАЛЬНОСТЬ РАБОТЫфотофотофотоПрограмма может быть предназначена для пользователей,

Высшая школа экономики, Москва, 2019ЦЕЛЬ И ЗАДАЧИ РАБОТЫфотофотофотоЦель работы Программа находит оптимальное

Высшая школа экономики, Москва, 2019ВЫБОР АЛГОРИТМОВ ДЛЯ РЕАЛИЗАЦИИ фотофотофотоДля реализации поиска

Высшая школа экономики, Москва, 2019ОПИСАНИЕ A*фотофото Алгоритм работает следующим образом. Для

Высшая школа экономики, Москва, 2019ДЕМОНСТРАЦИЯ РАБОТЫ A*фотофото

Высшая школа экономики, Москва, 2019ОПИСАНИЕ ТИПОВ ДВИЖЕНИЯфотофотофотоAllowdiagonal – разрешено перемещение в

Высшая школа экономики, Москва, 2019ОПИСАНИЕ ТИПОВ ЭВРИСТИКфотофотофотоМанхэттенская – dx + dyЕвклидова

Высшая школа экономики, Москва, 2019ТЕХНОЛОГИИ И ИНСТРУМЕНТЫ РЕАЛИЗАЦИИфотофотофото Для написания кода

Высшая школа экономики, Москва, 2019ТЕХНОЛОГИИ И ИНСТРУМЕНТЫ РЕАЛИЗАЦИИфотофотофото Требуется найти следующее:

Высшая школа экономики, Москва, 2019ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫфотофотофотоПрограмма определяет наличие пути между

Похожие презентации