Планирование траектории движения мобильного агента с учетом кинематических ограничений на основе классических и обучаемых методов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Ангуло Яури Бриан Флориан

• Ангуло Яури Бриан Флориан
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Ангуло Яури Бриан Флориан

Введение

Глава 1. Задача планирования траектории

1.1 Постановка задачи планирования траектории

1.2 Обзор методов решения задачи планирования траектории

1.2.1 Методы локального планирования

1.2.2 Методы глобального планирования

1.3 Выводы по главе

Глава 2. Метод планирования на основе пост-обработки

геометрической траектории

2.1 Алгоритм локального планирования

2.2 Метод пост-обработки траектории

2.3 Экспериментальное исследование предложенного метода

2.3.1 Эксперименты на искусственных картах

2.3.2 Эксперименты в симуляции

2.3.3 Эксперименты на реальном роботе

2.4 Выводы по главе

Глава 3. Гибридный метод планирования траектории в среде с

динамическими препятствиями

3.1 Обучаемая стратегия локального планирования

3.2 Классические алгоритмы глобального планирования

3.3 Экспериментальное исследование предложенного метода

3.3.1 Обученные стратегии

3.3.2 Эксперименты в статической среде

3.3.3 Эксперименты в динамической среде

3.4 Выводы по главе

Глава 4. Метод планирования траектории с учетом безопасных

ограничений

4.1 Безопасная стратегия

4.2 Иерархическая стратегия

Стр.

4.3 Безопасная стратегия с подцелями

4.4 Экспериментальное исследование предложенного метода

4.4.1 Сравнение качества предлагаемого метода с базовыми версиями

4.4.2 Эксперименты в среде с опасными зонами

4.4.3 Эксперименты в среде с узкими коридорами

4.5 Выводы по главе

Заключение

Список рисунков

Список таблиц

Приложение А. Акт о внедрении и использовании результатов

исследования

Введение диссертации (часть автореферата) на тему «Планирование траектории движения мобильного агента с учетом кинематических ограничений на основе классических и обучаемых методов»

Введение

Актуальность темы. Планирование траектории движения мобильных агентов является одной из фундаментальных задач в области робототехники, искусственного интеллекта и машинного обучения [5—8]. Решение этой задачи состоит в построении траектории, по которой в дальнейшем мобильный агент (например, мобильный колесный робот) сможет автономно перемещаться в окружающей среде. Зачастую исследователи сфокусированы на создании методов решения базовой версии задачи планирования траектории, когда результирующая траектория представляет собой последовательность прямолинейных сегментов [9; 10]. Такой вид планирования, зачастую называемый геометрическим, подходит для мобильных агентов, которые имеют возможность поворота на месте. Однако, мобильные агенты с кинематической моделью автомобильного типа не могут точно следовать по таким траекториям из-за ограничения на минимальный радиус поворота, что ведет к повышению вероятности столкновения с препятствиями [11—14]. Для снижения подобного риска и повышения безопасности следования по траектории целесообразно учитывать кинематические ограничения мобильного агента уже на этапе планирования. Однако, планирование с учетом подобных ограничений представляет собой сложную и ресурсоемкую задачу, и, несмотря на активно ведущиеся исследования в этой области и достигнутый прогресс, в настоящее время все еще наблюдается недостаток универсальных и высокоэффективных методов решения этой задачи [15]. При этом весьма перспективным представляется использование методов и моделей искусственного интеллекта и машинного обучения для создания подобных алгоритмов планирования [16; 17]. Именно этой проблематике и посвящено данное исследование, что обуславливает его актуальность.

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

траектории и последующей её модификации, направленной на учет кинематических ограничений [18; 19]. Обычно начальная траектория ищется в виде последовательности отрезков с помощью известных методов искусственного интеллекта, таких как [9; 10; 20; 21]. Затем на этих траекториях выбираются промежуточные состояния и соединяются локальными переходами, учитывающими кинематические ограничения. Эта процедура сглаживания выполняется до тех пор, пока не будет построена искомая кинематически-согласованная траектория, либо не будет превышен лимит на число итераций локального сглаживания. Несмотря на то, что методы этого класса являются эффективными в вычислительном смысле (быстро решают задачу), они в общем случае не гарантируют корректное преобразование начальной траекторию в ту, которая учитывает кинематические ограничения. Особенно этот недостаток ярко проявляется, когда речь идет о роботах с кинематикой автомобильного типа, т.е. тогда, когда имеется ограничение на минимальный радиус поворота [22]. Другой подход к построению кинематически-согласованных траекторий состоит в том, что учет кинематических ограничений происходит уже на этапе планирования. В рамках этого подхода зачастую вводят понятия глобального и локального планирование. Методы глобального планирования нацелены на исследование пространства поиска и систематическое разложение начальной проблемы на набор локальных подзадач, которые легче решаются с учетом заданных ограничений. Глобальное планирование обычно осуществляется с помощью известных алгоритмов поиска (как эвристического, так и случайного) [9; 10], а решение подзадач осуществляется с помощью процедуры, которая генерирует локальные переходы (примитивы), удовлетворяющие кинематическим ограничениям. При этом, обычно, процедура генерация выполнимых переходов не учитывает расположение препятствий. Это учитывается на глобальном уровне, где примитивы, пересекающие препятствия, просто отбрасываются, и алгоритм переходит к рассмотрению следующей локальной подзадачи. Таким образом алгоритмы глобального планирования оперируют в своей работе большим числом различных вариантов локальных переходов. Зачастую это число становится чрезмерным, что снижает вычислительную эффективность планирования. По этой причине в последнее время получают развитие методы планирования, использующие машинное обучение для построения примитивов движения, учитывающих препятствия [23]. Однако, пока такие обучаемые

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

Также, когда речь заходит об использовании методов машинного обучения, в частности - обучения с подкреплением, возникает проблема минимизации риска в процессе обучения стратегии генерации локальной траектории [24]. Это особенно актуально, если обучение проводится не в симуляторе, а на реальном роботе. Эту проблему призваны решить методы безопасного обучения с подкреплением [25]. Ожидается, что с помощью этой методологии агент не просто должен научиться перемещаться до заданной цели, но еще и избегать рискованных маневров. Эта область находится на ранних этапах развития и известные методы безопасного обучения с подкреплением не могут эффективно решать задачи в сложно-структурированных средах, характерных для задач планирования траектории.

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

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

Для достижения поставленной цели необходимо было решить следующие задачи:

1. Разработать алгоритм планирования траектории движения мобильного агента с кинематической моделью автомобильного типа на основе пост-обработки геометрической траектории.

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

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

4. Провести экспериментальное исследование разработанных алгоритмов и их сравнение с современными аналогами.

Научная новизна:

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

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

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

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

Практическая значимость работы заключается в реализации разработанных алгоритмов и моделей в виде комплекса программных средств для реальных мобильных робототехнических систем. В частности, первые два предложенных метода были реализованы в виде отдельных модулей планирования на базе операционной системы ROS и успешно внедрены в комплексы программных средств мобильной робототехнической платформы для компании ООО «ИнтеграНТ», специализирующейся на разработке мобильных колесных роботов и систем управления ими. Такие модули предоставляют функционал для построения траектории, по которой мобильные робототехнические платформы могут безопасно перемещаться без столкновения с препятствиями. Эти модули позволяют повысить степень автономности и безопасности мобильной робототехнической платформы в сложно-структурированных средах, характерных для задач планирования траектории.

Полученные в ходе работы теоретические и практические результаты могут быть использованы для повышения степени автономности и безопасности робототехнических систем различного типа и назначения.

Методология и методы исследования. Разрабатываемые алгоритмы основываются на методах теории графов, численных методов оптимизации, машинного обучения с подкреплением, дискретной оптимизации. Основным методом оценки эффективности представленных в работе подходов является численный эксперимент. При проведении экспериментального исследования и сравнения предлагаемых методов с аналогами использовалась одна и та же вычислительная инфраструктура, а также методология, обеспечивающая корректность сравнения получаемых результатов. Для программной реализации методов были использованы языки программирования C++ и Python3, а также множество открытых модулей, предоставляющих различные функции - от визуализации до библиотек обучения нейронных сетей. В процессе разработки использовались широко известные библиотеки для алгоритмов планирования траектории движения, такие как OMPL, SBPL, BENCH-MR и др. При разработке нейросетевых алгоритмов были использованы общеизвестные и общепринятые в области машинного обучения и искусственного интеллекта программные библиотеки, такие как PyTorch, SampleFactory, Rllib, StableBaselines3 и CleanRL.

Основные положения, выносимые на защиту:

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

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

3. Оригинальный обучаемый метод планирования траектории движения, учитывающий дополнительно ограничения по безопасности агента. Для этого используется комбинированный метод на основе безопасного и иерархического обучения с подкреплением. Благодаря такой комбинации, агент способен увеличивать глубину исследования безопасных состояний в сложных средах во время обучения, что в первую очередь приводит к повышению успешности решения задачи планирования и соблюдению ограничений по безопасности, накладываемых на мобильного агента.

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

Апробация работы. Основные результаты работы докладывались на следующих конференциях:

1. «IROS 2023», 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems, 1-5 October, Detroit

2. «TAROS 2023», Towards Autonomous Robotic Systems 2023, 13-15 September, Cambridge

3. VI Всероссийский научно-практический семинар "Беспилотные транспортные средства с элементами искусственного интеллекта" (БТС- ИИ 2021)

4. «ECMR 2021», European Conference on Mobile Robots 2021, 1-3 September, Bonn

5. «SibCon 2021», Siberian Conference on Control and Communications 2021, 13-15 May, Kazan

Личный вклад. В статье [1] автор предложил и разработал модификацию алгоритма для учета кинематических ограничениях робота автомобильного типа. В статье [2] автор разработал и реализовал структуру алгоритма гибридного подхода с использованием классических алгоритмов планирования и обучения с подкреплением. В работе [3] автор предложил комбинированный метод на основе иерархического и безопасного обучения с подкреплением для учета безопасных ограничений робота и разработал безопасный компонент этого метода.

Содержание диссертации соответствует паспорту специальности 1.2.1. Искусственный интеллект и машинное обучение, в частности, пунктам:

— 6. Формализация и постановка задач управления и (поддержки) принятия решений на основе систем искусственного интеллекта и машинного обучения. Разработка систем управления с использованием систем искусственного интеллекта и методов машинного обучения в том числе - управления роботами, автомобилями, БПЛА и т.п.

— 7. Разработка специализированного математического, алгоритмического и программного обеспечения систем искусственного интеллекта и машинного обучения. Методы и средства взаимодействия систем искусственного интеллекта с другими системами и человеком-оператором.

— 13. Методы и средства формирования массивов условно-реальных данных и прецедентов, необходимых для решения задач искусственного интеллекта и машинного обучения.

Публикации. Основные результаты по теме диссертации изложены в 4 печатных работах, 1 статья [2] - в изданиях из собственного перечня журналов МФТИ категории К1 и 2 статьи [1; 4] - в изданиях, индексируемых Web of Science и/или Scopus. Также, опубликован 1 препринт [3]. Получено одно свидетельство о регистрации программы для ЭВМ.

Объем и структура работы. Диссертация состоит из введения, 4 глав, заключения. Полный объём диссертации составляет 125 страниц, включая 50 рисунков и 6 таблиц. Список литературы содержит 0 наименований.

Глава 1. Задача планирования траектории

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

Рисунок 1.1 — Модульная схема многоуровневой системы управления беспилотного автомобиля. Рисунок взят из [6].

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

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

1.1 Постановка задачи планирования траектории

Неформально задачу планирования можно описать как нахождение последовательности состояний, через которые робот должен перемещаться между двумя конкретными состояниями — начальным и конечным. В простейшем случае такие состояния могут быть рассмотрены как положения в двумерном пространстве. Построенная траектория должна избежать столкновения с препятствиями на основе предоставленной карты от модуля восприятия, как показано на рисунке 1.2.

(а) (Ъ) (с)

Рисунок 1.2 — Решение задачи планирования (а), где X — рабочее пространство, — начало, хдоа1 — цель и Х0ь8 С X — занятое рабочее

пространство. Траектория должна проходить исключительно через состояния, которые не имеют пересечения с занятым рабочим пространством Xfree := с1(Х \ Х0ь3). Для этой задачи существует множество допустимых решений а' Е ^, (Ь), но только одно оптимальное решение а*, например, с наименьшей длиной траектории, (с). Рисунок взят из [26].

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

С практической точки зрения важно, что некоторые роботы не могут мгновенно изменять направление своего движения и разворачиваться на месте. Один из таких видов робота — робот с кинематикой автомобильного типа. Если не учитывать кинематику робота, то некоторые построенные траектории могут иметь резкие повороты, т.е. два последующих состояния могут иметь резкое изменение по ориентации. Это приведет робота с такой кинематикой к неточному следованию по таким траекториям из-за ограничения на минимальный радиус поворота. Следовательно, повышается вероятность того, что движение приведет к нежелательному последствию: столкновению. Таким образом, возникает необходимость учета кинематических ограничений мобильного агента на этапе планирования, чтобы следование по таким траекториям было безопасным. Пример построенной траектории с учетом кинематических ограничений, показан на рисунке 1.2 (с). Как видно на изображении, траектория не содержит резких поворотов, так как при построении траектории учитывались кинематические ограничения робота.

Перейдем к формальной постановке задачи.

Формальная постановка задачи планирования траектории Задача планирования траектории некоторого объекта в пространстве в общем случае может быть сформулирована следующим образом.

Пусть С С ^ замкнутое и ограниченное подмножество в ^-мерном пространстве — конфигурационное пространство состояния мобильного агента, где каждое состояние это ^-мерный вектор. Например, для робота с кинематикой автомобильного типа можно рассматривать состояние как вектор (х,у, 6,у, у), где (х,у) — положения, 6 — ориентация, V - скорость и у — угол поворота колес (см. рисунок 1.3).

ilA-stfl \л±а i^eoits, oei^ter \N ч of rotatio 1Л/

Рисунок 1.3 — Робот с кинематикой автомобильного типа, где система координат робота показана красным цветом, а система координат мира —

синим. (изображение взято из [27]).

Пусть W С R2 (W С R3) замкнутое и ограниченное подмножество в двумерном или трехмерном пространстве — рабочее пространство. В простейшем случае рабочее пространство представляет собой область плоскости, на которую можно проецировать робота и его окружающую среду (см. рисунок 1.4).

Пусть Obs(t) = {Obs\(t),...,Obsn(t)} — множество препятствий, где каждое препятствие формально задает отображение:

Obsi : Т ^ 2W (1.1)

где Obsi — препятствие из множества препятствий Obs(t), Т — множество моментов времени [0, то] и момент времени t G Т. Препятствия разделяются на статические и динамические, где статическое препятствие — это такое препятствие, что Vt : Obs^(t) = Obs^(0), а динамическое препятствие — такое, что 3t : Obsi(t) = Obsi(0), т.е. статические препятствия стоят на месте со временем, а динамические движутся.

Обозначим область, занимаемую всеми препятствиями в каждый момент времени, как W0bs(t):

Wobs(t) = [Uni=1(ObSi (i))]

(1.2)

Рабочее пространство можно разбить на два подмножества Wfree(t) и W0bs (t), для которых верно:

Wfree(t) = cl(W \ Wobs(t))

(1.3)

где — свободное рабочее пространство, — занятое рабочее

пространство и с1(.) — замыкание множества.

я

Рисунок 1.4 — Пример рабочего пространства робота в среде с препятствиями. Слева показана сцена из симулятора, а справа — то как его видят датчики робота, где черное — это занятое пространство, темно-серое — неизвестное, а

светло-серое — свободное.

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

Р : С ^ (1.4)

Определение 1. Траектория мобильного агента а — это отображение

(1.5)

вида:

^ : [0? Ртах] ^ Сj О"(0) = Cstart? 3 tend £ [0, Ртах] : &(tend) Cgoal ?

yt £ [0, tend] : P(o(t)) П Wobs (t) = 0,

где <r(0) = cstart — начальное состояние, v(tend) = cgoai — конечное состояние, tend — время достижения конечного состояния и Ртах — верхняя граница времени (горизонт планирования).

С учетом введенных обозначений и определений задача планирования задается следующим набором:

,Ттах} (I-6)

где W — рабочее пространство, С — конфигурационное пространство, Р -функция определения занимаемой области рабочего пространства, с81ан,Сдоа1 £ С — начальные и конечные состояния и Ттах — горизонт планирования.

Здесь и далее в работе будем рассматривать частный случай представленной задачи, а именно случай, когда время задается как дискретная величина с шагом дискретизации ДЪ и горизонтом планирования Ттах, который кратен ДЪ. Без ограничения общности будем считать, что ДЪ =1.

Определение 2. Дискретная траектория мобильного агента а — это отображение вида:

а : {0,1, 2,...,Ттах}^ С,

а(0) = Cstart,

3 ten(l £ {0, 1, 2,..., Ттах} . a(ten^) Cg0al ,

Vt £ {0,1,.. .,ten,i] : Р (o(t)) П Wob,(t) = 0,

(1.7)

где P(a(t)) — область рабочего пространства, занимаемая роботом в момент времени t при следовании по траектории a(t). Обозначим множество траекторий через

Введем в рассмотрение функцию стоимости траектории cost (а) : ^ ^ R^o, которая каждой траектории а сопоставляет некоторое вещественное число (стоимость) и зададим ее следующим образом:

^end

cost(а) = Y_l cost (а (t), a(t + 1)); (1.8)

i=0

где cost(а^), а(Ъ+1)) : С x С ^ R^0 — фукнция стоимости перехода, например, евклидово расстояние.

Определение 3. Оптимальная траектория а* £ ^ — это траектория, которая обладает наименьшей стоимостью:

Vа £ ^ : cost(а) ^ cost(а*) (1.9)

Кроме того, часто требуется учет кинематических ограничений робота. Для того чтобы учитывать эти ограничения робота, будем считать, что известна

модель движения робота в следующем виде:

с = / (с,и); (1.10)

где / — модель движения, с Е С — состояние робота, а и Е и — управление, где и это множество управлений.

Например, в частности будем рассматривать модель движения робота с кинематикой автомобильного типа:

X = УСОв(в)

у = увт(в) (1.11)

в = ^

где х,у — положения робота относительно передней оси робота, в — ориентация, Ь — колесная база, V — линейная скорость, у угол поворота колес. Вектор состояния описывается тройкой: с(Ъ) = (х,у,в), а вектор управления и(Ъ) = (V, у) (см. рисунок 1.3).

Определение 4. Траектория является кинематически согласованной, если для каждой пары состояний а(1) и а(Ъ + 1) из последовательности а можно найти такие управления и Е и, которые переводят робота из одного состояния в другое. Такие управления можно получить в явном виде через решение уравнений 1.10 или с помощью аппроксиматора, обученного на заранее определенной выборке данных.

Список литературы диссертационного исследования кандидат наук Ангуло Яури Бриан Флориан, 2024 год

Список литературы

5. Likhachev, M. Planning long dynamically feasible maneuvers for autonomous vehicles / M. Likhachev, D. Ferguson // The International Journal of Robotics Research. — 2009. — Vol. 28, no. 8. — P. 933—945.

6. Baidu apollo em motion planner / H. Fan [et al.] // arXiv preprint arXiv:1807.08048. — 2018. — URL: https://arxiv.org/abs/1807.08048.

7. PRM-RL: Long-range Robotic Navigation Tasks by Combining Reinforcement Learning and Sampling-Based Planning / A. Faust [et al.] // 2018 IEEE International Conference on Robotics and Automation (ICRA). — 2018. — P. 5113—5120.

8. Learning interaction-aware trajectory predictions for decentralized multi-robot motion planning in dynamic environments / H. Zhu [et al.] // IEEE Robotics and Automation Letters. — 2021. — Vol. 6, no. 2. — P. 2256—2263.

9. Hart, P. E. A formal basis for the heuristic determination of minimum cost paths / P. E. Hart, N. J. Nilsson, B. Raphael // IEEE transactions on Systems Science and Cybernetics. — 1968. — Vol. 4, no. 2. — P. 100—107.

10. LaValle, S. M. Rapidly-exploring random trees: A new tool for path planning / S. M. LaValle. — 1998.

11. Path planning for autonomous vehicles in unknown semi-structured environments / D. Dolgov [et al.] // The international journal of robotics research. — 2010. — Vol. 29, no. 5. — P. 485—501.

12. LaValle, S. M. Randomized kinodynamic planning / S. M. LaValle, J. J. Kuffner Jr // The international journal of robotics research. — 2001. — Vol. 20, no. 5. — P. 378—400.

13. Toward asymptotically optimal motion planning for kinodynamic systems using a two-point boundary value problem solver / C. Xie [et al.] //. — In Proceedings of the IEEE International Conference on Robotics, Automation (ICRA), 2015.

14. Betts, J. T. Survey of numerical methods for trajectory optimization / J. T. Betts // Journal of guidance, control, and dynamics. — 1998. — Vol. 21, no. 2. — P. 193—207.

15. A review of motion planning techniques for automated vehicles / D. González [et al.] // IEEE Transactions on Intelligent Transportation Systems. —

2015. — P. 1135—1145.

16. A survey of motion planning and control techniques for self-driving urban vehicles / B. Paden [et al.] // IEEE Transactions on intelligent vehicles. —

2016. — Vol. 1, no. 1. — P. 33—55.

17. Aradi, S. Survey of deep reinforcement learning for motion planning of autonomous vehicles / S. Aradi // IEEE Transactions on Intelligent Transportation Systems. — 2020. — Vol. 23, no. 2. — P. 740—759.

18. Gradient-informed path smoothing for wheeled mobile robots / E. Heiden [et al.] // Proceedings of the 2018 IEEE International Conference on Robotics and Automation. — 2018. — P. 1710—1717.

19. Palmieri, L. RRT-based nonholonomic motion planning using any-angle path biasing / L. Palmieri, S. Koenig, K. O. Arras // Proceedings of the 2016 IEEE International Conference on Robotics and Automation. — 2016. — P. 2775—2781.

20. Harabor, D. Online Graph Pruning for Pathfinding On Grid Maps / D. Harabor, A. Grastien // Proceedings of the 25th AAAI Conference on Artificial Intelligence. — 2011. — P. 1114—1119.

21. Theta*: Any-angle path planning on grids / K. Daniel [et al.] // Journal of Artificial Intelligence Research. — 2010. — Vol. 39. — P. 533—579.

22. A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles / B. Paden [et al.] // IEEE Transactions on Intelligent Vehicles. — 2016. — Vol. 1, no. 1. — P. 33—55.

23. RL-RRT: Kinodynamic Motion Planning via Learning Reachability Estimators from RL Policies / H. T. L. Chiang [et al.] // IEEE Robotics and Automation Letters. — 2019. — Vol. 4, issue 4.

24. A review of safe reinforcement learning: Methods, theory and applications / S. Gu [et al.] // arXiv preprint arXiv:2205.10330. — 2022. — URL: https : //arxiv.org/abs/2205.10330.

25. Altman, E. Constrained Markov decision processes. Vol. 7 / E. Altman. — CRC press, 1999.

26. Gammell, J. D. Informed anytime search for continuous planning problems / J. D. Gammell. — University of Toronto (Canada), 2017.

27. Corke, P. Robotics, Vision and Control: Fundamental Algorithms in MATLAB / P. Corke. — Springer Publishing Company, 2013.

28. Kinodynamic motion planning / B. Donald [et al.] // Journal of the ACM (JACM). — 1993. — Vol. 40, no. 5. — P. 1048—1066.

29. Schöls, T. Optimization based robot motion planning in dynamic environments : PhD thesis / Schöls T. — Master's thesis, Albert-Ludwigs University Freiburg, 2018.

30. Sakçak, B. Optimal kinodynamic planning for autonomous vehicles / B. Sakçak // Politecnico di Milano. — 2018.

31. Palmieri, L. A novel RRT extend function for efficient and smooth mobile robot motion planning / L. Palmieri, K. O. Arras // 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. — IEEE. 2014. — P. 205—211.

32. Dubins, L. E. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents / L. E. Dubins // American Journal of mathematics. — 1957. — Vol. 79, no. 3. — P. 497—516.

33. Reeds, J. Optimal paths for a car that goes both forwards and backwards / J. Reeds, L. Shepp // Pacific journal of mathematics. — 1990. — Vol. 145, no. 2. — P. 367—393.

34. Sucan, I. A. The open motion planning library / I. A. Sucan, M. Moll, L. E. Kavraki // IEEE Robotics & Automation Magazine. — 2012. — Vol. 19, no. 4. — P. 72—82.

35. Limpert, N. A local planner for Ackermann-driven vehicles in ROS SBPL / N. Limpert, S. Schiffer, A. Ferrein // 2015 Pattern Recognition Association of South Africa and Robotics and Mechatronics International Conference (PRASA-RobMech). — IEEE. 2015. — P. 172—177.

36. Bench-mr: A motion planning benchmark for wheeled mobile robots / E. Heiden [et al.] // IEEE Robotics and Automation Letters. — 2021. — Vol. 6, no. 3. — P. 4536—4543.

37. Webb, D. J. Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics / D. J. Webb, J. Van Den Berg // Proceedings of the 2013 IEEE International Conference on Robotics and Automation (ICRA 2013). — 2013. — P. 5054—5061.

38. Sussmann, H. J. Shortest paths for the Reeds-Shepp car: a worked out example of the use of geometric techniques in nonlinear optimal control / H. J. Sussmann, G. Tang // Rutgers Center for Systems and Control Technical Report. — 1991. — Vol. 10. — P. 1—71.

39. Astolfi, A. Exponential Stabilization of a Wheeled Mobile Robot Via Discontinuous Control / A. Astolfi // Journal of Dynamic Systems, Measurement, and Control. — 1999. — Vol. 121, no. 1. — P. 121—126.

40. Pivtoraiko, M. Kinodynamic motion planning with state lattice motion primitives / M. Pivtoraiko, A. Kelly // 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. — IEEE. 2011. — P. 2172—2179.

41. Search-Based Online Trajectory Planning for Car-like Robots in Highly Dynamic Environments / J. Lin [et al.] // 2021 IEEE International Conference on Robotics and Automation (ICRA). — 2021. — P. 8151—8157.

42. Sutton, R. S. Reinforcement learning: An introduction / R. S. Sutton, A. G. Barto. — MIT press, 2018.

43. Zhu, K. Deep reinforcement learning based mobile robot navigation: A review / K. Zhu, T. Zhang // Tsinghua Science and Technology. — 2021. — Vol. 26, no. 5. — P. 674—691.

44. Ray, A. Benchmarking safe exploration in deep reinforcement learning / A. Ray, J. Achiam, D. Amodei // arXiv preprint arXiv:1910.01708. —2019. — Vol. 7, no. 1. — P. 2. — URL: https://arxiv.org/abs/1910.01708.

45. Jayant, A. K. Model-based safe deep reinforcement learning via a constrained proximal policy optimization algorithm / A. K. Jayant, S. Bhatnagar // Advances in Neural Information Processing Systems. — 2022. — Vol. 35. — P. 24432—24445.

46. Risk conditioned neural motion planning / X. Huang [et al.] // 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). — IEEE. 2021. — P. 9057—9063.

47. Pivtoraiko, M. Differentially constrained mobile robot motion planning in state lattices / M. Pivtoraiko, R. A. Knepper, A. Kelly // Journal of Field Robotics. — 2009. — Vol. 26, no. 3. — P. 308—333.

48. Rufli, M. On the design of deformable input-/state-lattice graphs / M. Rufli, R. Siegwart // 2010 IEEE International Conference on Robotics and Automation. — 2010. — P. 3071—3077.

49. Ziegler, J. Spatiotemporal state lattices for fast trajectory planning in dynamic on-road driving scenarios / J. Ziegler, C. Stiller // 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems. — 2009. — P. 1879—1884.

50. Schleich, D. Search-based planning of dynamic MAV trajectories using local multiresolution state lattices / D. Schleich, S. Behnke // 2021 IEEE international conference on robotics and automation (ICRA). — IEEE. 2021. — P. 7865—7871.

51. Likhachev, M. ARA* : Anytime A* with Provable Bounds on Sub-Optimality / M. Likhachev, G. J. Gordon, S. Thrun // Advances in Neural Information Processing Systems 16 (NIPS 2003) / ed. by S. Thrun, L. K. Saul, B. Schölkopf. — MIT Press, 2003. — P. 767—774. — URL: http:// papers.nips.cc/paper/2382-ara-anytime- a-with-provable-bounds-on-sub-optimality.pdf.

52. Practical search techniques in path planning for autonomous driving / D. Dolgov [et al.] // Ann Arbor. — 2008. — Vol. 1001, no. 48105. — P. 18—80.

53. Kurzer, K. Path planning in unstructured environments: A real-time hybrid a* implementation for fast and deterministic path generation for the kth research concept vehicle / K. Kurzer. — 2016.

54. Anytime Motion Planning using the RRT* / S. Karaman [et al.] // Proceedings of the 2011 IEEE International Conference on Robotics and Automation. — 2011. — P. 1478—1483.

55. Gammell, J. D. Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic / J. D. Gammell, S. S. Srinivasa, T. D. Barfoot. — 2014.

56. Gammell, J. D. Bit*: Batch informed trees for optimal sampling-based planning via dynamic programming on implicit random geometric graphs / J. D. Gammell, S. S. Srinivasa, T. D. Barfoot // arXiv preprint arXiv:1405.5848. — 2014.

57. Strub, M. P. Advanced BIT*(ABIT*): Sampling-based planning with advanced graph-search techniques / M. P. Strub, J. D. Gammell. — 2020.

58. Towards an online RRT-based path planning algorithm for Ackermann-steering vehicles / J. Peng [et al.] // 2021 IEEE International Conference on Robotics and Automation (ICRA). — IEEE. 2021. — P. 7407—7413.

59. Smooth-RRT*: Asymptotically optimal motion planning for mobile robots under kinodynamic constraints / Y. Kang [et al.] // 2021 IEEE International Conference on Robotics and Automation (ICRA). — IEEE. 2021. — P. 8402—8408.

60. Karaman, S. Optimal kinodynamic motion planning using incremental sampling-based methods / S. Karaman, E. Frazzoli // 49th IEEE conference on decision and control (CDC). — IEEE. 2010. — P. 7681—7687.

61. LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics / A. Perez [et al.] // 2012 IEEE International Conference on Robotics and Automation. — IEEE. 2012. — P. 2537—2542.

62. Randomized kinodynamic motion planning with moving obstacles / D. Hsu [et al.] // The International Journal of Robotics Research. — 2002. — Vol. 21, no. 3. — P. 233—255.

63. Allen, R. Toward a real-time framework for solving the kinodynamic motion planning problem / R. Allen, M. Pavone // 2015 IEEE international conference on robotics and automation (ICRA). — IEEE. 2015. — P. 928—934.

64. Li, Y. Asymptotically optimal sampling-based kinodynamic planning / Y. Li, Z. Littlefield, K. E. Bekris // The International Journal of Robotics Research. — 2016. — Vol. 35, no. 5. — P. 528—564.

65. Jeon, J. hwan. Anytime computation of time-optimal off-road vehicle maneuvers using the RRT / J. hwan Jeon, S. Karaman, E. Frazzoli // 2011 50th IEEE Conference on Decision and Control and European Control Conference. — 2011. — P. 3276—3282.

66. Vailland, G. Cubic Bezier Local Path Planner for Non-holonomic Feasible and Comfortable Path Generation / G. Vailland, V. Gouranton, M. Babel // IEEE. — 2021. — May. — P. 7894—7900.

67. Kuffner, J. J. RRT-connect: An efficient approach to single-query path planning / J. J. Kuffner, S. M. LaValle // Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065). Vol. 2. — IEEE. 2000. — P. 995—1001.

68. Sampling-based optimal kinodynamic planning with motion primitives / B. Sakcak [et al.] // Autonomous Robots. — 2019. — Vol. 43, no. 7. — P. 1715—1732.

69. Otte, M. RRTX: Asymptotically optimal single-query sampling-based motion planning with quick replanning / M. Otte, E. Frazzoli // The International Journal of Robotics Research. — 2016. — Vol. 35, no. 7. — P. 797—822.

70. Sucan, I. A. The Open Motion Planning Library / I. A. Sucan, M. Moll, L. E. Kavraki // IEEE Robotics Automation Magazine. — 2012. — Vol. 19, no. 4. — P. 72—82.

71. Erdmann, M. On multiple moving objects / M. Erdmann, T. Lozano-Perez // Proceedings. 1986 IEEE International Conference on Robotics and Automation. Vol. 3. — 1986. — P. 1419—1424.

72. Kim, D. H. Local path planning using a new artificial potential function composition and its analytical design guidelines / D. H. Kim, S. Shin // Advanced Robotics. — 2006. — Vol. 20. — P. 115—135.

73. LaValle, S. Planning Algorithms: Cambridge University Press, 2006 / S. LaValle. — 2006.

74. An NMPC approach using convex inner approximations for online motion planning with guaranteed collision avoidance / T. Schoels [et al.] // Proceedings of the 2020 IEEE International Conference on Robotics and Automation. — 2020. — P. 3574—3580.

75. Bergman, K. On motion planning using numerical optimal control. Vol. 1843 / K. Bergman. — Linköping University Electronic Press, 2019.

76. Probabilistic roadmaps for path planning in high-dimensional configuration spaces / L. E. Kavraki [et al.] // IEEE transactions on Robotics and Automation. — 1996. — Vol. 12, no. 4. — P. 566—580.

77. Model-free neural lyapunov control for safe robot navigation / Z. Xiong [et al.] // 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). — IEEE. 2022. — P. 5572—5579.

78. Motion planning networks / A. H. Qureshi [et al.] // 2019 International Conference on Robotics and Automation (ICRA). — IEEE. 2019. — P. 2118—2124.

79. Gammell, J. D. Batch informed trees (BIT*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs / J. D. Gammell, S. S. Srinivasa, T. D. Barfoot // 2015 IEEE international conference on robotics and automation (ICRA). — IEEE. 2015. — P. 3067—3074.

80. Felzenszwalb, P. F. Distance transforms of sampled functions / P. F. Felzenszwalb, D. P. Huttenlocher // Theory of computing. — 2012. — Vol. 8, no. 1. — P. 415—428.

81. Sturtevant, N. Benchmarks for Grid-Based Pathfinding / N. Sturtevant // Transactions on Computational Intelligence and AI in Games. — 2012. — Vol. 4, no. 2. — P. 144—148.

82. ROS: an open-source Robot Operating System / M. Quigley [et al.] // Proceedings of the Third ICRA Workshop on Open Source Software. — 2009.

83. Strub, M. P. Advanced BIT* (ABIT*): Sampling-Based Planning with Advanced Graph-Search Techniques / M. P. Strub, J. D. Gammell // 2020 IEEE International Conference on Robotics and Automation (ICRA). — 2020.

84. Vailland, G. Cubic bezier local path planner for non-holonomic feasible and comfortable path generation / G. Vailland, V. Gouranton, M. Babel // 2021 IEEE International Conference on Robotics and Automation (ICRA). — IEEE. 2021. — P. 7894—7900.

85. Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor / T. Haarnoja [et al.] // Proceedings of the 35th International Conference on Machine Learning, PMLR. Vol. 80. — 2018. — P. 1861—1870. — arXiv: 1801.01290.

86. Maximum a posteriori policy optimisation / A. Abdolmaleki [et al.] // 6th International Conference on Learning Representations. — 2018. — arXiv: 1806.06920. — URL: https://arxiv.org/abs/1806.06920.

87. Muesli: Combining Improvements in Policy Optimization / M. Hessel [et al.] // Proceedings of the 38th International Conference on Machine Learning, PMLR. Vol. 139. — 2021. — P. 4214—4226. — arXiv: 2104.06159. — URL: http: //arxiv.org/abs/2104.06159%20http://proceedings.mlr.press/v139/ hessel21a.html.

88. Hsieh, M.-R. Drone-Based Object Counting by Spatially Regularized Regional Proposal Network / M.-R. Hsieh, Y.-L. Lin, W. H. Hsu // 2017 IEEE International Conference on Computer Vision (ICCV). — 2017. — P. 4165—4173.

89. Fox, D. The dynamic window approach to collision avoidance / D. Fox, W. Burgard, S. Thrun // IEEE Robotics Automation Magazine. — 1997. — Vol. 4, no. 1. — P. 23—33.

90. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor / T. Haarnoja [et al.] // International conference on machine learning. — PMLR. 2018. — P. 1861—1870.

91. Learning to Walk in the Real World with Minimal Human Effort / S. Ha [et al.] // Conference on Robot Learning. — PMLR. 2021. — P. 1110—1120.

92. Chane-Sane, E. Goal-conditioned reinforcement learning with imagined subgoals / E. Chane-Sane, C. Schmid, I. Laptev // International Conference on Machine Learning. — PMLR. 2021. — P. 1430—1440.

93. Safe Robot Navigation Using Constrained Hierarchical Reinforcement Learning / F. S. Roza [et al.]. — 2022.

94. Lyapunov-based safe policy optimization for continuous control / Y. Chow [et al.] // arXiv preprint arXiv:1901.10031. — 2019.

95. Hindsight experience replay / M. Andrychowicz [et al.] // Advances in neural information processing systems. — 2017. — Vol. 30.

96. Constrained policy optimization / J. Achiam [et al.] // International conference on machine learning. — PMLR. 2017. — P. 22—31.

97. Anytime motion planning using the RRT / S. Karaman [et al.] // 2011 IEEE international conference on robotics and automation. — IEEE. 2011. — P. 1478—1483.

Список рисунков

1.1 Модульная схема многоуровневой системы управления беспилотного автомобиля. Рисунок взят из [6].............. 12

1.2 Решение задачи планирования (а), где X — рабочее пространство, хstart — начало, xgoai — цель и Х0ъа С X — занятое рабочее пространство. Траектория должна проходить исключительно через состояния, которые не имеют пересечения с занятым рабочим пространством Xfree := cl(X \ Х0ъа). Для этой задачи существует множество допустимых решений а' £ ^, (b), но только одно оптимальное решение а*, например, с наименьшей длиной

траектории, (с). Рисунок взят из [26]................... 13

1.3 Робот с кинематикой автомобильного типа, где система координат робота показана красным цветом, а система координат мира —

синим. (изображение взято из [27]).................... 15

1.4 Пример рабочего пространства робота в среде с препятствиями. Слева показана сцена из симулятора, а справа — то как его видят датчики робота, где черное — это занятое пространство,

темно-серое — неизвестное, а светло-серое — свободное......... 16

1.5 Глобальное и локальное планирование.................. 20

1.6 Слева показаны кривые Дубинса, по центру — кривые Ридса-Шеппа и справа — кривые POSQ................. 22

1.7 Решетка примитов движения....................... 23

1.8 Онлайн-примитивы движений. Слева показаны примитивы, сгенерированные с помощью разных углов поворота колес но с одним линейным ускорением а. Справа показана база примитивов, которая была сгенерирована с помощью разных управлений иг. Изображение взято из [41] ........................ 24

1.9 Примитивы на основе обучения с подкреплением для одноагентного

и многоагентного случаев (Изображения взяты из [8; 41])....... 25

1.10 Примитивы на основе обучения с подкреплением. Изображение

взято из [41] ................................ 26

1.11 Группа примитивов с разным разрешением и найденная траектория (взято из[50])................................ 27

1.12 Алгоритм Hydrid A* в среде парковки [53]............... 28

1.13 Сценарий тестирования алгоритма в среде с динамическими препятствиями. Изображение взято из [41]..............................29

1.14 Алгоритм SmoothRRT. Изображение взято из [59]......................30

1.15 Алгоритм RRT для робота с кинематикой автомобильного типа. Изображение взято из [58] ................................................31

1.16 Алгоритм RRTX для работы с динамическими препятствиями. Изображение взято из [69] ................................................31

1.17 Алгоритм Theta*-RRT. Изображение взято из [31]......................32

1.18 Алгоритм BSpline..........................................................33

1.19 Алгоритм метода искусственных потенциальных полей..................34

1.20 Алгоритм сглаживания траекторий........................................34

1.21 Алгоритма PRM-RL (взято из[7]) ........................................35

1.22 Алгоритм LyapunovRRT [77]..............................................36

1.23 Алгоритм Dynamic Motion Planning Networks [78]......................36

2.1 Построение кинематически согласованной траектории на основе пост-обработки геометрической траектории. Желтым цветом отмечена геометрическая траектория, красным — траектория, учитывающая кинематические ограничения, полученная из геометрической с помощью пост-обработки............... 40

2.2 Робот с кинематикой автомобиля, который двигается из одного состояния в другое. Здесь В — это ось автомобиля и С — это ось

цели (изображение взято из [27])..................... 41

2.3 Процедуры схемы пост-обработки. Слева (1) — исходная начальная траектория (показана красным), соединяющая опорные состояния с помощью кривых Ридса-Шеппа (показаны черным). По центру (2) — этап добавления и перемещения состояний от препятствий. По центру (3) — этап удаления состояний, результирующая траектория показана зеленым. Справа — карта расстояний, где красным цветом показана ближайшая область к препятствиям, а по мере отдаления меняется свет в сторону бирюзового цвета. Изображение взято из [18]. 43

2.4 Состояния локальных минимумов. Изображение взято из [18] .... 44

2.5 Процедура нахождения оптимального пути между двумя обязательными состояниями. Изображение взято из [18] ....... 48

2.6 Желтые прямолинейные сегменты — это начальная траектория. Кривые и состояния Фиолетовые, Синие, Зеленые обозначают SkipStates, ReachNextStates и ExtraStates, соответственно. Красные состояния обозначают состояния итоговой траектории......... 49

2.7 Карты для тестирования. Зеленые и красные кружки показывают начальные и конечные состояния (200 для каждой карты)....... 54

2.8 Результаты планирования на созданных картах (успешность решения, средняя длина траектории и среднее время работы алгоритма).................................. 56

2.9 Выполняемая миссия и пройденная траектория робота в симуляции. 57

2.10 Робот-уборщик компании ООО ИнтеграНТ............... 59

2.11 Площадки для уборки "Остров мечты". Синие многоугольники -запрашиваемая территория для уборки, а розовые линии — маршруты покрытия этой территории.................. 60

3.1 Среда с динамическими препятствиями. Красная стрелка — начальное состояние, синяя стрелка — конечное. Черные и синие прямоугольники обозначают статические и динамические препятствия, соответственно. Голубая кривая — траектория, сгенерированная A*-POLAMP....................... 63

3.2 Среда для обучения. Зеленый прямоугольник с Красной стрелкой — это текущее состояние робота. Зеленый прямоугольник с Бирюзовой ориентацией — конечное состояние. Синие прямоугольники — статические препятствия, а Синий прямоугольник с Розовой стрелкой — динамическое препятствие. Оранжевые линии — это лидарные данные................ 65

3.3 Нейросетевая архитектура Actor-Critic для обучения функции локального планирования ......................... 66

3.4 Тестовые карты (1-3). Красные прямоугольники и стрелки показывают начальные состояния (начальная скорость v = 0 и угол поворота у = 0), аГолубые прямоугольники и стрелки показывают конечные состояния............................. 67

3.5 Алгоритм A* с примитивами движения. Красным отмечены состояния, лежащие в списке CLOSED. Синим — состояния, лежащие в списке OPEN. Розовым отмечена итоговая траектория, найденная алгоритмом........................... 70

3.6 Решения алгоритма ККТ(слева) и алгоритма RRT с кривыми Cubic Bezier (справа). Изображение взято из [84]............... 72

3.7 Сравнение кривых обучения для обычной стратегии и стратегии с возрастающей сложностью. Пунктирные линии представляют собой переходы между этапами обучения.................... 76

3.8 Результаты экспериментальных исследований в среде с динамическими препятствиями (успешность решения, время достижения и количество сэмплов).................... 83

4.1 Среда обучения показана на левом рисунке. Синий прямоугольник с красной стрелкой — текущее состояние робота. Зеленый прямоугольник — желаемое конечное состояние. Синие прямоугольники — статические препятствия. Оранжевые линии — лучи лидара, а Голубые линии — радиус безопасности. Центральная и правая фигуры представляют собой траекторию, созданную безопасной стратегией LPPO и базовой стратегией PPO для одной

и той же задачи соответственно...................... 85

4.2 На рисунке показана схема обучения в среде Safety-gym и обновления стратегий ........................... 88

4.3 Безопасное исследование подцелей. Вверху: безопасной стратегии не хватает достаточного исследования для эффективного решения задач с длительным горизонтом. Внизу: для решения этой проблемы, предлагается создать подцели внутри безопасного пространства, чтобы увеличить возможности исследования и, следовательно, повысить вероятность успешного достижения отдаленной цели............................... 91

4.4 Рассмотренные роботы: робот-сканер, точечный, робот с дифференциальным приводом и робособака............... 93

4.5 Сравнение прогнозируемых подцелей SPEIS-noSAFETY на левом рисунке и SPEIS на правом рисунке. Подцель от SPEIS более отдалена от препятствий (имеет большее расстояние до препятствий) благодаря ограничениям по безопасности........ 94

4.6 Левый рисунок показывает одно из заданий уровня 1, а правый рисунок — уровня 2............................. 95

4.7 Сравнение обучения стратегий между SAC, SAC-LAG, SPEISnoSAFETY и SPEIS для точечной среды............. 96

4.8 Сравнение SPEIS и LyapunovRRT с разным количеством опасных

зон (препятствий)..............................101

Список таблиц

1 Результаты экспериментов в симуляции..................................58

2 Результаты обучения агента DDPG в различных конфигурациях. . . 77

3 Результаты экспериментальных исследований в статической среде. . 79

4 Размеры пространства действий и пространства состояний каждого робота указаны для сред POLAMP и safety-gym..........................92

5 Результаты экспериментов в среде Safety-gym............................99

6 Результаты экспериментов в среде с узкими коридорами........103

Приложение А

Акт о внедрении и использовании результатов исследования

ОБЩЕСТВО С ОГРАНИЧЕННОЙ ОТВЕТСТВЕННОСТЬЮ

«ИНТЕГРАЦИЯ НОВЫХ ТЕХНОЛОГИЙ»

АКТ

об использовании результатов диссертационной работы Ангуло Яури Бриана Флориана

г. Москва 17.09.2024

на тему «Планирование траектории движения мобильного агента с учетом кинематических ограничений на основе классических и обучаемых методов», представленной на соискание ученой степени кандидата технических наук

Результаты диссертационной работы «Планирование траектории движения мобильного агента с учетом кинематических ограничений на основе классических и обучаемых методов» обладают высокой актуальностью и представляют практический интерес для решения задач планирования траектории в системах управления мобильной робототехнической платформы.

В диссертационной работе Ангуло Я.Б.Ф. были разработаны два метода в областях обучения с подкреплением и планирования траектории: метод планирования траектории на основе постобработки начальной траектории и гибридный метод планирования траектории в среде с динамическими препятствиями. Также на базе полученных теоретических результатов диссертации созданы элементы программного инструментария перечисленных методов в виде отдельных модулей планирования для операционной системы ROS. Данный инструментарий служит для построения в реальном времени траектории, по которой мобильные робототехнические платформы могут безопасно перемещаться без столкновения со статическими и динамическими препятствиями. Эти модули позволяют повысить эффективность, степень автономности и безопасности мобильной робототехнической платформы в сложноструктурированных средах, разделяемых с людьми.

Полученные теоретические результаты нашли свое практическое применение в научно-исследовательской работе (НИР) «Исследование и разработка программно-аппаратного комплекса автоматического управления сервисными роботами и беспилотными транспортными средствами» в виде двух экспериментальных программных реализаций алгоритмов.

Первая программная реализация на базе метода планирования траектории на основе пост-обработки траектории помогает существенно сократить время, отведенное на решение задачи планирования траектории в системе управления. В частности, время планирования траектории сокращается до 40 мс, что на 50% лучше по сравнению с существующими решениями на выборке задач, созданных в реальных условиях эксплуатации на городских объектах города Москвы. Этот эффект достигается за счет декомпозиции исходной задачи на две подзадачи: построение начальной траектории в виде последовательности сегментов в 2Б пространстве, которая не учитывает кинематические ограничения робота, и ее последующее преобразование в кинематически согласованную траекторию. Такой способ позволяет избежать явного поиска в многомерном конфигурационном пространстве состояний робота, который требует больших вычислительных ресурсов.

Вторая программная реализация на основе гибридного метода планирования траектории в среде с динамическими препятствиями повышает гибкость и степень автономности системы управления робототехнической платформы. Благодаря использованию этого метода, время выполнения миссий мобильной робототехнической платформой, проводимых в сложно-структурированных средах с большим потоком людей на городских объектах города Москвы, сокращается на 25%. Это достигается за счет построения траектории, учитывающей в явном виде динамические препятствия с их прогнозируемыми траекториями с помощью обучаемого алгоритма, что позволяет мобильной платформе эффективнее работать в сложно-структурированных средах, характерных для задач планирования траектории. Такой способ позволяет лучше объезжать динамические препятствия по сравнению с теми методами, которые на каждой итерации рассматривают динамические препятствия как статические.

Генеральный директор

Т. В. Михайлова