Введение 3
2. Постановка задачи 5
3. Обзор литературы 8
4. Алгоритмы и метод 11
4.1. Алгоритмы эвристического поиска 11
4.1.1 Картографическая модель среды 11
4.1.2 Алгоритм Дейкстры 11
4.1.3 Алгоритм A* и эвристики 13
4.1.4 Универсальные эвристики 14
4.1.5 Алгоритм WA* 15
4.2. Метод 16
4.2.1 Предсказанные эвристики 16
4.2.2 Обучающий набор данных 17
4.2.3 Генерация обучающего набора данных 18
4.2.4 Архитектура нейросети 20
4.2.5 Обучение модели 21
4.2.6 Тестирование с планировщиком 21
5. Эксперименты 23
5.1. Сложность задания 23
5.2. Обучающий набор данных 24
5.3. Параметры нейросети 24
5.4. Смещение в сторону заданий низкой сложности 25
5.5. Оценка сложности заданий 26
5.6. Тестирование 27
5.7. Основные результаты 28
6. Выводы 29
7. Заключение 30
8. Благодарность 30
Список литературы 31
Планирование траектории является одной из наиболее важных исследовательских задач в робототехнике. Многие задачи в различных областях решаются с помощью планирования траектории, например, автономное управление мобильным роботом для достижения конкретной цели. Подходящая траектория пути генерируется как последовательность действий для поддержания движения робота из начального состояния в целевую точку через несколько промежуточных состояний. Мобильные роботы могут найти оптимальный или почти оптимальный путь, обходящий препятствия, от начального до целевого состояния на основе одного или нескольких показателей производительности, таких как длина найденного пути или время, потраченное на его прохождение.
Поиск пути выполняется в установленной картографической модели среды, в которой расположен мобильный робот. Построение картографической модели среды подразумевает создание точного описания пространственного местоположения различных объектов (например, препятствий) в среде, в которой находится робот. Цель построения карты окружающей среды — помочь мобильному роботу спланировать оптимальный путь от начальной до целевой точки в установленной модели окружающей среды с препятствиями. Существует множество методов создания модели среды для планирования траектории движения мобильного робота. В качестве базовой модели среды часто используется граф декомпозиции сетки или граф видимости.
Значительную часть всех алгоритмов планирования траектории составляют методы эвристического поиска. Алгоритм A*, разработанный на основе алгоритма Дейкстры, является отправной точкой большинства алгоритмов эвристического поиска, которые в большинстве своем являются его различными модификациями. Алгоритм A* позволяет находить путь наименьшей стоимости в графе от стартовой вершины до конечной и часто используется для планирования траектории движения роботов в графовой картографической модели среды. Многие научные статьи посвящены разработке новых усовершенствованных эвристических методов поиска путем модификации алгоритма A*.
Эффективность работы алгоритма Л* во многом зависит от используемой эвристической функции, оценивающей расстояние до цели. Так, слишком неточная эвристическая оценка может негативно сказаться на производи-тельности алгоритма, а вычисление точной эвристической оценки (идеальной эвристики) может оказаться нецелесообразным: самый простой способ вы-числить точную эвристическую оценку расстояния от всех вершин графа до цели - запустить алгоритм Дейкстры на этом графе из цели, однако, такой способ позволяет сразу найти оптимальный путь от старта до цели и является очень неэффективным.
В связи с этим, предлагается использовать методы машинного обучения для разработки предсказанных эвристических оценок, которые позволят эффективнее решать задачу планирования траектории методами эвристического поиска. Модели машинного обучения, такие как нейронные сети, позволяют не решать задачу вычисления идеальной эвристики напрямую, а обучившись выявлять сложные зависимости между значениями идеальной эвристики и входными данными на некотором наборе задач, впоследствии выдавать хорошее приближение точной эвристической оценки на совершенно новой задаче.
Данная работа направлена на повышение эффективности алгоритма Л* за счёт разработки универсального нейросетевого метода, позволяющего получить аппроксимацию идеальной эвристической функции - предсказанную эвристику, для её использования в алгоритме Л*в рамках задачи планирования траектории, решаемой на графах регулярной декомпозиции. Универсальность метода заключается в возможности его применения для решения задачи планирования в разнообразных картографических моделях среды, в том числе тех, о строении которых не было информации при обучении нейросети. Использование, полученной в результате работы метода, предсказанной аппроксимации идеальной эвристики должно значительно уменьшать количество раскрытых состояний в ходе работы алгоритма Л*, тем самым увеличивая его эффективность.
В работе рассматривается одна из наиболее важных задач в робототехнике - задача планирования траектории. Был проведен анализ научной литературы в области этой задачи, а также в области применения методов машинного обучения и эвристического поиска для её решения. Была разработана и реализована модификация алгоритма A*, в основе которой лежит нейросетевой подход, позволяющая решать задачу планирования траектории на графах регулярной декомпозиции эффективнее, чем базовая версия алгоритма A* и его модификация - алгоритм WA*.
