Методы децентрализованной навигации групп мобильных агентов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Дергачев Степан Алексеевич

• Дергачев Степан Алексеевич
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Дергачев Степан Алексеевич

Введение

Глава 1. Постановка задачи децентрализованной навигации

групп мобильных агентов

1.1 Формальная постановка задачи

1.2 Модель агента

1.3 Модель рабочей области

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

Глава 2. Обзор методов решения задачи децентрализованной

навигации групп мобильных агентов

2.1 Обзор методов классической много-агентной навигации

2.2 Обзор методов децентрализованного много-агентного избегания столкновений

2.3 Обзор методов навигации групп взаимозаменяемых агентов

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

Глава 3. Кооперативная децентрализованная много-агентная

навигация

3.1 Алгоритм децентрализованной кооперативной много-агентной навигации

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

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

Глава 4. Децентрализованная навигация групп

взаимозаменяемых агентов

4.1 Алгоритм навигации групп взаимозаменяемых агентов в дискретной среде

4.2 Алгоритм навигации групп взаимозаменяемых агентов в непрерывной среде

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

Стр.

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

Глава 5. Децентрализованная много-агентная навигация с

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

5.1 Алгоритм много-агентного избегания столкновений с учетом кинематических ограничений

5.2 Теоретический анализ алгоритма

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

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

Заключение

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

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

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

Приложение А. Обзор методов планирования траектории

индивидуального мобильного агента

Приложение Б. Дополнительное экспериментальное

исследование алгоритма много-агентного избегания столкновений с учетом

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

Б.1 Эксперименты с моделью движения автомобильного типа

Б.2 Сравнение с подходом, основанным на обучении с подкреплением 178 Б.3 Эксперименты с разнородными агентами и неопределенность во

входных данных

Введение диссертации (часть автореферата) на тему «Методы децентрализованной навигации групп мобильных агентов»

Введение

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

Существующие подходы к решению задачи много-агентной навигации можно условно разделить на централизованные и децентрализованные. В централизованном случае предполагается существование единого контроллера, обладающего полной информацией о состоянии всех агентов и окружающей их среды [1—4]. Задача навигации решается за счёт планирования совокупности неконфликтных траекторий для всех агентов. С одной стороны, такой подход может гарантировать достижения всех целей агентами, а также позволяет находить траектории с наименьшим временем выполнения. Однако применение централизованного подхода ограничено рядом факторов.

Во-первых, централизованные системы требуют высокой вычислительной мощности и стабильной связи всех агентов с центральным контроллером, что затрудняет их использование в условиях ограниченной коммуникации или ненадёжной сети. Во-вторых, использование централизованных систем зачастую предполагает высокую точность исполнения команд, полученных от центрального контроллера, так как в ином случае потребуется осуществлять перепланирование для всех агентов при отклонении от заданных траекторий. Эти ограничения значительно снижают надёжность и масштабируемость таких систем, что делает централизованные подходы не вполне подходящими для применения в реальных условиях [5—8].

Альтернативой централизованным системам является децентрализованный подход к управлению мобильными агентами. В рамках этого подхода предполагается, что у агентов ограничена коммуникация и область видимости, и они действуют опираясь исключительно на доступную им локальную информацию [6; 9—11]. Такие методы обладают рядом преимуществ, включая более

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

Степень разработанности темы. Значительная часть существующих работ, посвящённых задаче много-агентной навигации [1], фокусируется на сценарии, где для всех агентов централизованно строится общий неконфликтный план действий, после чего он выполняется всеми агентами. При этом отдельные централизованные алгоритмы обладают различными теоретическими свойствами. В частности, некоторые из них обеспечивают построение решения за полиномиальное время [3; 12], другие - гарантируют оптимальность [2; 13] или ограниченную субоптимальность [14; 15] получаемых траекторий. Однако, такой подход опирается на существование центрального контроллера, обладающего полной информацией о среде и стабильной связью со всеми агентами. Выполнение таких условий может быть затруднительно, поэтому на практике предпочтительнее использовать децентрализованные алгоритмы, где каждый агент выбирает действия независимо, используя только доступную ему информацию.

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

Кроме того, наиболее изученной постановкой задачи много-агентной навигации является случай, когда каждому агенту необходимо достичь конкретной целевой точки. Помимо классической постановки, существуют альтернативные формулировки. Так, одним из вариантов является задача навигации взаимозаменяемых агентов, которая отличается тем, неважно, какой агент достигнет конкретную цель [1]. И хотя был создан ряд централизованных методов решения этой задачи [4; 16; 17], но существует лишь небольшое число работ, рассматривающих децентрализованный сценарий [18—21]. Однако, все они опираются на то, что агентам доступно согласованное начальное назначение целей, что невозможно в полностью децентрализованном случае. Более того, предло-

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

Отдельно стоит отметить, что существующие исследования, независимо от доступности начального назначения целей, преимущественно сфокусированы на рассмотрении такого варианта задачи, где предполагается, что агент может произвольно изменять направление движения в любой момент времени, а так же моментально тормозить и ускоряться. Иначе говоря, никак не учитывают кинематические ограничения агента, что может привести к столкновениям при применении таких алгоритмов на практике (например, на реальных роботах). Некоторые методы (зачастую централизованные) опираются на использование дискретного представление пространства, в котором результирующие траектории представляют собой последовательность прямолинейных сегментов, например [2; 3]. Другие (обычно децентрализованные) осуществляют итеративный выбор действий в непрерывном пространстве, однако без учета кинематических ограничений [10; 22].

Существуют работы, в которых рассматриваются кинематические ограничения, но они либо ориентированы исключительно на конкретные кинематические модели движения [23—26], либо требуют значительной подготовительной работы, например, создания специальных таблиц [9; 27; 28] или примитивов для планирования [29; 30].

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

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

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

1. Выполнить анализ существующих алгоритмов и методов навигации групп мобильных агентов;

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

3. Разработать новые децентрализованные алгоритмы навигации группы взаимозаменяемых агентов;

4. Разработать новый алгоритм децентрализованной много-агентной навигации с учетом кинематических ограничений;

5. Провести теоретические и эмпирические исследования разработанных методов.

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

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

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

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

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

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

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

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

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

3. Decentralized-Unlabeled-Navigation3 - библиотека с подробной документацией, реализующая новый метод децентрализованной навигации для группы взаимозаменяемых агентов в непрерывной среде. Репозиторий также содержит код и полный набор данных для проведения экспериментальной оценки и анализа полученных результатов;

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

1https://github.com/PathPlanning/ORCA-algorithm

2https://github.com/PathPlanning/TP-SWAP

3https://github.com/PathPlanning/Decentralized-Unlabeled-Navigation

4https://github.com/PathPlanning/MPPI-Collision-Avoidance

Часть представленных результатов была получена в рамках выполнения научно-исследовательских проекта Министерства науки и высшего образования РФ № 075-15-2024-544 «Математические модели и численные методы как основа для разработки робототехнических комплексов, новых материалов и интеллектуальных технологий конструирования».

Методология и методы исследования. В диссертационной работе применяются методы дискретной математики, теории графов, теории оптимизации, вычислительной геометрии, исследования операций. Основным методом оценки эффективности представленных в работе алгоритмов является численный эксперимент. При проведении экспериментального исследования и сравнения предлагаемых алгоритмов с аналогами использовалась одна и та же вычислительная инфраструктура, а также методология, обеспечивающая корректность и воспроизводимость сравнения получаемых результатов. Для программной реализации методов были использованы языки программирования С++ и РуЬНоиЗ.

Основные результаты, выносимые на защиту:

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

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

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

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

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

1. "Методы много-агентной децентрализованной навигации", Научные семинары Центра когнитивного моделирования МФТИ (Семинар ЦКМ МФТИ 2025), 17 апреля 2025, г. Долгопрудный, МО, Россия

2. "Decentralized unlabeled multi-agent pathfinding via target and priority swapping", Европейская конференция по искусственному интеллекту (ECAI 2024), 19-24 октября 2024, г. Сантьяго-де-Компостела, Испания

3. "Decentralized unlabeled multi-agent navigation in continuous space", Девятая международная конференция по интерактивной коллаборативной робототехнике (ICR 2024), 14-18 октября 2024, г. Мехико, Мексика

4. "Применение управления с прогнозирующими моделями и стохастической оптимизацией в задаче децентрализованного много-агентного избегания столкновений", XIV Всероссийское совещание по проблемам управления (ВСПУ 2024), 17-20 июня 2024, г. Москва, Россия

5. "Методы децентрализованного избегания столкновений и навигация взаимозаменяемых агентов", Научные семинары Центра когнитивного моделирования МФТИ (Семинар ЦКМ МФТИ 2023), 15 июня 2023, г. Долгопрудный, МО, Россия

6. "Задача децентрализованной навигации взаимозаменяемых агентов в непрерывной среде", Научные семинары Центра когнитивного моделирования МФТИ (Семинар ЦКМ МФТИ 2023), 23 ноября 2023, г. Долгопрудный, МО, Россия

7. "Метод интеграции централизованного много-агентного планирования и децентрализованного избегания столкновений", Научные семинары Центра когнитивного моделирования МФТИ (Семинар ЦКМ МФТИ 2021), 8 апреля 2021, г. Долгопрудный, МО, Россия

8. "Distributed multi-agent navigation based on reciprocal collision avoidance and locally confined multi-agent path finding", Семнадцатая международная конференция по автоматизации и инженерии Института инженеров электротехники и электроники (IEEE CASE 2021), 23-27 августа 2021, г. Лион, Франция

9. "Метод интеграции централизованного много-агентного планирования и децентрализованного избегания столкновений", Шестой всероссийский научно-практический семинар "Беспилотные транспортные сред-

ства с применением искусственного интеллекта" (БТС-ИИ-2021), 16-19 ноября 2021, г. Москва, Россия 10. "A combination of Theta*, ORCA and Push and Rotate for multi-agent navigation", Пятая международная конференция по интерактивной коллаборативной робототехнике (ICR 2020), 7-9 октября 2020, г. Санкт-Петербург, Россия

Публикации. Основные результаты по теме диссертации изложены в 7 публикациях, 5 из них - в печатных изданиях, индексируемых Web of Science и Scopus (в том числе, одна публикация уровня Scopus Q1 и одна публикация уровня Scopus Q2), 4 - в трудах научных конференций (в том числе, одной конференции уровня Core A).

Объем и структура работы. Диссертация состоит из введения, 5 глав, заключения и 2 приложений. Полный объём диссертации составляет 183 страницы, включая 50 рисунков и 12 таблиц. Список литературы содержит 169 наименований.

Глава 1. Постановка задачи децентрализованной навигации групп

мобильных агентов

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

Рисунок 1.1 — Иллюстрация классической поставноки задачи навигации группы мобильных агентов

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

Одним из широко распространённых допущением, используемым при решении такой задачи является использование предположение о существование представления пространства в виде графа специального вида. Тогда решение сводится к поиску набора неконфликтных путей на графе. Задачу в такой постановке называют "(классическим) много-агентным поиском пути" (Multi-Agent Pathfinding, MAPF) [1—3]. Кроме того, существуют расширенные постановки задачи MAPF, в которых могут учитываться размер или форма агента, а так же кинематические ограничения агентов.

Если требуется найти не только набор траекторий, но и управляющие воздействия, необходимые для реализации этих траекторий (а так же при этом учесть размер/форму агента), то в этом случае говорят о планировании движения (Motion Planning). Соответственно, задачу называют "много-агентное планирование движения" (Multi-Agent Motion Planning) [1; 31].

Другой вариант постановки задачи известен как навигация группы взаимозаменяемых агентов [32]. Аналогично классической задаче навигации, может рассматриваться поиск набора геометрических путей. Тогда задача именуется "немаркированным/анонимным много-агентным поиском путей" (Unlabeled Multi-Agent Pathfinding, Anonymous Multi-Agent Pathfinding, AMAPF) [1; 4; 17]. Для более общих случаев используются названия "немаркированное много-агентное планирование движения" (Unlabeled Multi-Agent Motion Planning) [33; 34].

Существуют и другие варианты задачи навигации. Можно выделить обобщение классической навигации и навигации взаимозаменяемых агентов, где агенты разбиты на команды, внутри каждой из которых агенты взаимозаменяемы (Colored MAPF или k-Color Motion Planning) [1; 35]. Кроме того, существует онлайн версия задачи навигации (так же известная как Lifelong), когда после достижения очередной цели ему сразу же назначается следующая [1; 11; 36].

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

коммункиацию представлена справа на рисунке 1.1. Так, область коммуникации/видимости изображена как цветной диск, а ее граница отмечена пунктирной линией.

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

1.1 Формальная постановка задачи

Рассмотрим множество агентов М = {1, 2,...,N}, действующих в общей двумерной среде W С R2. Рабочая область W состоит из свободного пространства Wfree и области статических препятствий W0bs = W \ Wfree. Пространство состояний агентов обозначим как X С Rn, а пространство допустимых управляющих воздействий как U С Rm.

Каждому агенту i £ М задано начальное состояние s1 £ X. Множество начальных состояний обозначим S = {s1,..., sN}. Кроме того, задано множество целевых состояний Т = {т1,...,TN}, причём |Т| = N.

Пусть Т = 0, At, 2At,..., - дискретное время. Для упрощения положим, что At = 1, таким образом, время задаётся как Т = 0,1, 2,....В каждый момент времени t каждый агент i £ М находится в состоянии xj £ X и выбирает действие u't £ U С Rm, которое перемещает его из текущего состояния в некоторое следующее xj+1. В общем виде дискретная модель движения агента задаётся в следующем виде:

xj+i = Т (xj, uj) (1.1)

где F : Rn х Rm ^ Rn - функция, определяющая модель движения агентов.

Состояние агента обязательно включает его позицию (px,t,py,t) в пространстве W и может включать дополнительные компоненты, например, угол рысканья: xt = (pXlt,Pylt, 0t,...). Поскольку в данной работе рассматривается модель движения с дискретным временем, предполагается, что при переходе между позицией (pxj,py,t) и (pxj+i,pyj+i) в смежные моменты времени t,t + 1, движение агента происходит равномерно и прямолинейно. Здесь и далее для

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

(0,0)

®t+l = (Px,t+l,Py,t+l)

щ = (vXit,Vyj)

Xt = (Px,t,Py,t)

xt+1 = (Px,t+l,Py,t+l,6t+l)

Ut = (vt,wt)

Xt = (Px,t,Py,t,6t)

Голономная модель

(0,0)

Модель движения двухколесного робота

Рисунок 1.2 — Иллюстрация голономной модели движения агента (слева) и модели движения двухколесного робота (справа).

Пример 1. Одной из наиболее используемых моделей движения в работах, посвящённых много-агентной навигации является голономная модель (рисунок 1.2). Она предполагает, что агент может двигаться в произвольном направлении, а также мгновенно ускоряться или замедляться. Кроме того, предполагается, что каждое действие выполняется идеально. Таким образом, состояние агента задаётся его позицией xt = (px,t,Py,t), а в качестве действия используется желаемая скорость ut = (vx,t,vy,t). Скорость может быть ограничена по модулю ||wt||2 ^ итах. Уравнение движения тогда имеет следующий вид:

xt+1 = Xt + ut; (1.2)

Пример 2. Рассмотрим модель движения двухколесного робота, широко используемую при решении задачи планирования траектории наземных роботов (рисунок 1.2). В данном случае состояние робота описывается как xt = (px,t,Py,t, 9t), где Qt направление движения агента (угол рысканья). Управляющее воздействие задаётся как ut = (Vt,Wt)T, где Vt - линейная скорость (vmm < Vt < Vmax), а Wt - угловая скорость (wmm < wt < wmax). Уравнение

движения, описывающие движение робота, имеет следующий вид:

/cos Qt 0\

Xt+1 = Xt +

со

(1.3)

sin et 0

V 0 1

Определение 1.1. Управляющая последовательность (или просто управление) и1 для агента i представляет собой упорядоченный набор управляющих воздействий и задаётся как иг = {u0, u|,..., u¡,...}.

Последовательное применение управления иг к системе (1.1) в дискретные шаги времени, для агента, находящегося в некотором начальном состоянии x0 £ X порождает траекторию в пространстве состояний.

Определение 1.2. Траектория (путь) П агента i представляет собой последовательность состояний агента i во времени П = {x0, x|, x2,...}.

Для удобства записи траектория также может интерпретироваться как отображение П : Т ^ X, задающее состояние агента в каждый момент времени t £ Т. Термины "путь" и "траектория" будут использоваться как синонимы.

Определение 1.3. Пусть s1 £ X - заданное состояние агента i в начальный момент времени (x0 = s1), а т £ X - некоторое целевое состояние. Будем говорить, что управляющая последовательность иг сходится из состояния зг к т, если при применении иг к системе (1.1) порождает такую траекторию Пг, что для заданного произвольного £ > 0 существует tljin £ Т, что для всех t ^ fjin справедливо:

- т||2 ^ £. (1.4)

Иными словами, при выполнении агентом i управляющей последовательности иг существует такой конечный момент времени t^in, когда агент достигает окрестности В£(т) заданного целевого состояния т и больше не покидает её. При этом длительностью или стоимостью соответствующей траектории П называется шаг времени fjin £ Т:

duration(n%) = t%jin (1.5)

Определение 1.4. Управляющая последовательность иг = {u0,u^,...,uj,...} для агента i £ N является допустимой, если для каждого шага времени t £ Т действие Wj. принадлежит множеству допустимых управляющих воздействий u¿ £U.

Введем отображение вЫ : X ^ , которая задает, какую область зани-

мает агент в состоянии х^.

Определение 1.5. Пусть б1 € X - заданное состояние агента г € М в начальный момент времени (х0 = б1). Будем говорить, что управляющая последовательность иг называется безопасной, если применение иг к системе (1.1) порождает такую траекторию пг (так же называемую безопасной), что для всех £ € Т справедливо:

зК(пгЦ)) П = 0 (1.6)

Иными словами, траектория пг и соответствующее управление иг считаются безопасными, если агент % € М, следующий вдоль траектории, никогда не сталкиваются со статическими препятствиями.

Определение 1.6. Пусть б1, б-1 € X - заданные состояния агентов г € N и ] € М в начальный момент времени (х0 = б1 , х0 = б1). Будем говорить, что управляющие последовательности иг и и3 называется неконфликтными, если применение иг и и3 к системе (1.1) порождает такие траектории п\ п3 (так же называемые неконфликтными), что для всех Ь € Т справедливо:

Список литературы диссертационного исследования кандидат наук Дергачев Степан Алексеевич, 2025 год

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

1. Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks [Текст] / R. Stern [et al.] // Proceedings of the 12th Annual Symposium on Combinatorial Search (SoCS 2019). — 2019. — P. 151—158.

2. Conflict-Based Search for Optimal Multi-Agent Pathfinding [Текст] / G. Sharon [et al.] // Artificial Intelligence. — 2015. — Vol. 219. — P. 40—66.

3. De Wilde, B. Push and Rotate: A Complete Multi-Agent Pathfinding Algorithm [Текст] / B. De Wilde, A. W. Ter Mors, C. Witteveen // Journal of Artificial Intelligence Research. — 2014. — Vol. 51. — P. 443—492.

4. Okumura, K. Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution [Текст] / K. Okumura, X. Défago // Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS 2022). Vol. 32. — 2022. — P. 270—278.

5. Multi-Robot Path Planning by Predicting Structure in a Dynamic Environment [Текст] / C. S. Olive [et al.] // IFAC Proceedings Volumes. — 2000. — Vol. 33, no. 26. — P. 555—560.

6. Decentralized Non-Communicating Multiagent Collision Avoidance with Deep Reinforcement Learning [Текст] / Y. F. Chen [et al.] // Proceedings of the 2017 IEEE International Conference on Robotics and Automation ({ICRA} 2017). — 2017. — P. 285—292.

7. §enba§lar, B. RLSS: Real-Time, Decentralized, Cooperative, Networkless Multi-Robot Trajectory Planning Using Linear Spatial Separations [Текст] / B. §enba§lar, W. Honig, N. Ayanian // Autonomous Robots. — 2023. — Vol. 47, no. 7. — P. 921—946.

8. Zhang, S. A Comprehensive Research about Multi-Robot Control Models [Текст] / S. Zhang, Z. Zheng, S. Zu // 2023 International Conference on Image, Algorithms and Artificial Intelligence (ICIAAI 2023). — Atlantis Press, 2023. — P. 723—735.

9. Optimal Reciprocal Collision Avoidance for Multiple Non-Holonomic Robots [Текст] / J. Alonso-Mora [et al.] // Distributed Autonomous Robotic Systems. — 2013. — P. 203—216.

10. Fast, on-Line Collision Avoidance for Dynamic Vehicles Using Buffered Voronoi Cells [Текст] / D. Zhou [et al.] // IEEE Robotics and Automation Letters. — 2017. — Vol. 2, no. 2. — P. 1047—1054.

11. Learn to Follow: Decentralized Lifelong Multi-Agent Pathfinding via Planning and Learning [Текст] / A. Skrynnik [et al.] // Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. — 2024. — P. 17541—17549.

12. Surynek, P. A Novel Approach to Path Planning for Multiple Robots in Bi-Connected Graphs [Текст] / P. Surynek // Proceedings of the 2009 IEEE International Conference on Robotics and Automation. — 2009. — P. 3613—3619.

13. The Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding [Текст] / G. Sharon [et al.] // Artificial Intelligence. — 2013. — Vol. 195. — P. 470—495.

14. Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem [Текст] / M. Barer [et al.] // Proceedings of the 7th Annual Symposium on Combinatorial Search, SoCS 2014. — 2014. — P. 19—27.

15. Li, J. EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding [Текст] / J. Li, W. Ruml, S. Koenig // Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021). — 2021. — P. 12353—12362.

16. Yu, J. Multi-Agent Path Planning and Network Flow [Текст] / J. Yu, S. M. LaValle // Proceedings of the Workshop on the Algorithmic Foundations of Robotics (WAFR 2013). — 2013. — P. 157—173.

17. Ali, Z. A. Improved Anonymous Multi-Agent Path Finding Algorithm [Текст] / Z. A. Ali, K. Yakovlev // Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. — 03/24/2024. — P. 17291—17298.

18. Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments [Текст] / R. Lowe [et al.] // Proceedings of the Advances in neural information processing systems ({NIPS} 2017). — 2017. — Vol. 30.

19. Panagou, D. Decentralized Goal Assignment and Safe Trajectory Generation in Multirobot Networks via Multiple Lyapunov Functions [Текст] / D. Panagou, M. Turpin, V. Kumar // IEEE Transactions on Automatic Control. — 2019. — Vol. 65, no. 8. — P. 3365—3380.

20. Learning Safe Unlabeled Multi-Robot Planning with Motion Constraints [Текст] / A. Khan [et al.] // Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2019). — 2019. — P. 7558—7565.

21. Khan, A. Large Scale Distributed Collaborative Unlabeled Motion Planning with Graph Policy Gradients [Текст] / A. Khan, V. Kumar, A. Ribeiro // IEEE Robotics and Automation Letters. — 2021. — Vol. 6, no. 3. — P. 5340—5347.

22. Reciprocal N-Body Collision Avoidance [Текст] / J. van den Berg [et al.] // Robotics Research. — 2011. — P. 3—19.

23. The Hybrid Reciprocal Velocity Obstacle [Текст] / J. Snape [et al.] // IEEE Transactions on Robotics. — 2011. — Vol. 27, no. 4. — P. 696—706.

24. Reciprocal Collision Avoidance with Acceleration-Velocity Obstacles [Текст] / J. Van Den Berg [et al.] // Proceedings of the International Conference on Robotics and Automation (ICRA2011). — 2011. — P. 3475—3482.

25. Smooth and Collision-Free Navigation for Multiple Robots under Differential-Drive Constraints [Текст] / J. Snape [et al.] // Proceedings of the 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems ({IROS} 2010). — 2010. — P. 4584—4589.

26. Smooth Coordination and Navigation for Multiple Differential-Drive Robots [Текст] / J. Snape [et al.] // Experimental Robotics. — 2014. — P. 601—613.

27. Collision Avoidance under Bounded Localization Uncertainty [Текст] / D. Claes [et al.] // 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems. — 2012. — P. 1192—1198.

28. Multi-Robot Collision Avoidance with Localization Uncertainty [Текст] / D. Hennes [et al.] // Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1. — 2012. — P. 147—154.

29. Cirillo, M. A Lattice-Based Approach to Multi-Robot Motion Planning for Non-Holonomic Vehicles [Текст] / M. Cirillo, T. Uras, S. Koenig // 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. — 2014. — P. 232—239.

30. Conflict-Based Search for Multi-Robot Path Planning Using Optimal Motion Primitives [Текст] / Y. He [et al.] // 2025 International Conference on Electrical Automation and Artificial Intelligence (ICEAAI). — 2025. — P. 1249—1254.

31. Optimal and Bounded-Suboptimal Multi-Agent Motion Planning [Текст] / L. Cohen [et al.] // Proceedings of the 12th International Symposium on Combinatorial Search, SoCS 2019. — 2019. — P. 44—51.

32. Goal Assignment and Trajectory Planning for Large Teams of Interchangeable Robots [Текст] / M. Turpin [et al.] // Autonomous Robots. — 2014. — Vol. 37, no. 4. — P. 401—415.

33. Motion Planning for Unlabeled Discs with Optimality Guarantees [Текст] / K. Solovey [et al.] // Proceedings of Robotics: Science and Systems (RSS 2015). — 2015.

34. Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds [Текст] / B. Banyassady [et al.] // 38th International Symposium on Computational Geometry (SoCG 2022). — 2022.

35. Solovey, K. K-Color Multi-Robot Motion Planning [Текст] / K. Solovey, D. Halperin // The International Journal of Robotics Research. — 2014. — Vol. 33, no. 1. — P. 82—97.

36. Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks [Текст] / H. Ma [et al.] // arXiv. — International Foundation for Autonomous Agents and Multiagent Systems, 2017. — P. 837—845.

37. den Berg, J. Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation [Текст] / J. den Berg, M. Lin, Manocha // Proceedings of The 2008 IEEE International Conference on Robotics and Automation ({ICRA} 2008). — IEEE, 2008. — P. 1928—1935.

38. Wang, L. Safety Barrier Certificates for Collisions-Free Multirobot Systems [Текст] / L. Wang, A. D. Ames, M. Egerstedt // IEEE Transactions on Robotics. — 2017. — Vol. 33, no. 3. — P. 661—674.

39. Wooden, D. T. Graph-Based Path Planning for Mobile Robots [Текст] : PhD thesis / Wooden David T. — 2006.

40. Казаков, К. А. Обзор современных методов планирования движения [Текст] / К. А. Казаков, В. А. Семенов // Труды Института системного программирования РАН. — 2016. — Т. 28, № 4. — С. 241—293.

41. A Note on Two Problems in Connexion with Graphs [Текст] / E. W. Dijkstra [et al.] // Numerische mathematik. — 1959. — Vol. 1, no. 1. — P. 269—271.

42. 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.

43. Яковлев, К. С. Графовые Модели в Задаче Планирования Траектории На Плоскости [Текст] / К. С. Яковлев, Е. С. Баскин // Искусственный интеллект и принятие решений. — 2013. — № 1. — С. 5—12.

44. Yap, P. Grid-Based Path-Finding [Текст] / P. Yap // Proceedings of the 15th Conference of the Canadian Society for Computational Studies of Intelligence. — 2002. — P. 44—55.

45. 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.

46. Masehian, E. A Voronoi Diagram-Visibility Graph-Potential Field Compound Algorithm for Robot Path Planning [Текст] / E. Masehian, M. R. Amin-Naseri // Journal of Robotic Systems. — 2004. — Vol. 21, no. 6. — P. 275—300.

47. Seda, M. Robot Motion Planning Using Generalised Voronoi Diagrams [Текст] / M. Seda, V. Pich // Iscgav'08: Proceedings of the 8th Wseas International Conference on Signal Processing, Computational Geometry and Artificial Vision. — 2008. — P. 215—220.

48. Far planner: Fast, attemptable route planner using dynamic visibility update [Текст] / F. Yang [et al.] // 2022 ieee/rsj international conference on intelligent robots and systems (iros). — 2022. — P. 9—16.

49. Computational geometry: algorithms and applications [Текст] / M. De Berg [et al.]. — Springer, 2008.

50. Kavraki, L. E. Analysis of Probabilistic Roadmaps for Path Planning [Текст] / L. E. Kavraki, M. N. Kolountzakis, J.-C. Latombe // IEEE Transactions on Robotics and Automation. — 1998. — Vol. 14, no. 1. — P. 166—171.

51. Zhu, H. Decentralized Probabilistic Multi-Robot Collision Avoidance Using Buffered Uncertainty-Aware Voronoi Cells [Текст] / H. Zhu, B. Brito, J. Alonso-Mora // Autonomous Robots. — 2022. — Vol. 46, no. 2. — P. 401—420.

52. De Marinis, A. A Minimum-Time Obstacle-Avoidance Path Planning Algorithm for Unmanned Aerial Vehicles [Текст] / A. De Marinis, F. Iavernaro, F. Mazzia // Numerical Algorithms. — 2022. — Vol. 89, no. 4. — P. 1639—1661.

53. Luo, W. Multi-Robot Collision Avoidance under Uncertainty with Probabilistic Safety Barrier Certificates [Текст] / W. Luo, W. Sun, A. Kapoor // Advances in Neural Information Processing Systems. — 2020. — Vol. 33. — P. 372—383.

54. Kaymaz, M. Obstacle Identification and Ellipsoidal Decomposition for Fast Motion Planning in Unknown Dynamic Environments [Текст] / M. Kaymaz, N. K. Ure // 2023 IEEE International Conference on Robotics and Automation (ICRA). — 2023. — P. 1694—1700.

55. Efficient Avoidance of Ellipsoidal Obstacles with Model Predictive Control for Mobile Robots and Vehicles [Текст] / M. Rosenfelder [et al.] // Mechatron-ics. — 2025. — Vol. 110. — P. 103386.

56. Yu, J. Structure and Intractability of Optimal Multi-Robot Path Planning on Graphs [Текст] / J. Yu, S. LaValle // Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 27. — 2013. — P. 1443—1449.

57. Cáp, M. Complete Decentralized Method for On-Line Multi-Robot Trajectory Planning in Well-Formed Infrastructures [Текст] / M. Cáp, J. Vokrínek, A. Kleiner // Proceedings International Conference on Automated Planning and Scheduling, ICAPS. 2015—Janua. — 2015. — P. 324—332. — eprint: 1501.07704.

58. Tordesillas, J. MADER: Trajectory Planner in Multiagent and Dynamic Environments [Текст] / J. Tordesillas, J. P. How // IEEE Transactions on Robotics. — 2021. — Vol. 38, no. 1. — P. 463—476.

59. Efficient SAT Approach to Multi-Agent Path Finding under the Sum of Costs Objective [Текст] / P. Surynek [et al.] // Proceedings of the 22nd European Conference on Artificial Intelligence ({ECAI} 2016). — IOS Press, 2016. — P. 810—818.

60. Yu, J. Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics [Текст] / J. Yu, S. M. LaValle // IEEE Transactions on Robotics. — 2016. — Vol. 32, no. 5. — P. 1163—1177. — eprint: 1507.03290.

61. Standley, T. Finding Optimal Solutions to Cooperative Pathfinding Problems [Текст] / T. Standley // Proceedings of the National Conference on Artificial Intelligence. Vol. 1. —2010. — P. 173—178.

62. ICBS: The Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding [Текст] / E. Boyarski [et al.] // Proceedings of the International Symposium on Combinatorial Search. Vol. 6. — 2015. — P. 223—225.

63. Aljalaud, F. Finding Bounded Suboptimal Multi-Agent Path Planning Solutions Using Increasing Cost Tree Search [Текст] / F. Aljalaud, N. Sturte-vant // Proceedings of the International Symposium on Combinatorial Search. Vol. 4. — 2013. — P. 203—204.

64. Modifying Optimal SAT-based Approach to Multi-Agent Path-Finding Problem to Suboptimal Variants [Текст] / P. Surynek [et al.] // Proceedings of the International Symposium on Combinatorial Search. Vol. 8. — 2017. — P. 169—170.

65. Surynek, P. Bounded Sub-Optimal Multi-Robot Path Planning Using Satisfiability modulo Theory (SMT) Approach [Текст] / P. Surynek // 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). — 2020. — P. 11631—11637.

66. Luna, R. Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees [Текст] / R. Luna, K. E. Bekris // IJCAI International Joint Conference on Artificial Intelligence. — 2011. — P. 294—300.

67. Yu, J. Pebble Motion on Graphs with Rotations: Efficient Feasibility Tests and Planning Algorithms [Текст] / J. Yu, D. Rus // Algorithmic Foundations of Robotics XI. — 2015. — P. 729—746.

68. Erdmann, M. On Multiple Moving Objects [Текст] / M. Erdmann, T. Lozano-Pérez // Algorithmica. — 1987. — Vol. 2, no. 1—4. — P. 477—521.

69. Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots [Текст] / M. Cáp [et al.] // IEEE Transactions on Automation Science and Engineering. — 2015. — Vol. 12, no. 3. — P. 835—849.

70. Learning a priority ordering for prioritized planning in multi-agent path finding [Текст] / S. Zhang [et al.] // Proceedings of the International Symposium on Combinatorial Search. Vol. 15. — 2022. — P. 208—216.

71. Сергеевич, Ю. Б. Синтез нейросетевой системы планирования траекторий для группы мобильных роботов [Текст] / Ю. Б. Сергеевич // Системы управления, связи и безопасности. — 2019. — № 4. — С. 163—186.

72. Graph Neural Networks for Decentralized Multi-Robot Path Planning [Текст] / Q. Li [et al.] // 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). — 2020. — P. 11785—11792.

73. Primal: Pathfinding via Reinforcement and Imitation Multi-Agent Learning [Текст] / G. Sartoretti [et al.] // IEEE Robotics and Automation Letters. — 2019. — Vol. 4, no. 3. — P. 2378—2385.

74. SCRIMP: Scalable Communication for Reinforcement-and Imitation-Learning-Based Multi-Agent Pathfinding [Текст] / Y. Wang [et al.] // Proceedings of the 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2023). — 2023. — P. 9301—9308.

75. Mapf-Gpt: Imitation Learning for Multi-Agent Pathfinding at Scale [Текст] / A. Andreychuk [et al.] // Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 39. — 2025. — P. 23126—23134.

76. Improving Continuous-time Conflict Based Search [Текст] / A. Andreychuk [et al.] // AAAI Conference on Artificial Intelligence. Vol. 35. — 2021. — P. 11220—11227.

77. Multi-Agent Pathfinding with Continuous Time [Текст] / A. Andreychuk [et al.] // Artificial Intelligence. — 2022. — Vol. 305. — P. 103662.

78. Multi-Agent RRT: Sampling-Based Cooperative Pathfinding [Текст] / M. Cáp [et al.] // Proceedings of the 2013 International Conference on Autonomous Agents and Multi-Agent Systems. — 2013. — P. 1263—1264.

79. Desaraju, V. R. Decentralized Path Planning for Multi-Agent Teams in Complex Environments Using Rapidly-Exploring Random Trees [Текст] / V. R. Desaraju, J. P. How // 2011 IEEE International Conference on Robotics and Automation. — IEEE, 2011. — P. 4956—4961.

80. Robust MADER: Decentralized and Asynchronous Multiagent Trajectory Planner Robust to Communication Delay [Текст] / K. Kondo [et al.] // 2023 IEEE International Conference on Robotics and Automation (ICRA). — 2023. — P. 1687—1693.

81. Hai Zhu. Chance-Constrained Collision Avoidance for Mavs in Dynamic Environments [Текст] / Hai Zhu, Javier Alonso-Mora // IEEE Robotics and Automation Letters. — 2019. — Vol. 4, no. 2. — P. 776—783.

82. Salimi Lafmejani, A. Nonlinear MPC for Collision-Free and Deadlock-Free Navigation of Multiple Nonholonomic Mobile Robots [Текст] / A. Salimi Lafmejani, S. Berman // Robotics and Autonomous Systems. — 2021. — Vol. 141. — P. 103774.

83. Robust Collision Avoidance for Multiple Micro Aerial Vehicles Using Nonlinear Model Predictive Control [Текст] / M. Kamel [et al.] // 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2017). — 2017. — P. 236—243.

84. Decentralized Navigation of Multiple Agents Based on ORCA and Model Predictive Control [Текст] / H. Cheng [et al.] // 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). — 2017. — P. 3446—3451.

85. Mao, R. A Novel Collision-Free Navigation Approach for Multiple Nonholonomic Robots Based on ORCA and Linear MPC [Текст] / R. Mao, H. Gao, L. Guo // Mathematical Problems in Engineering. — 2020. — Vol. 2020, no. 1. — P. 4183427.

86. Collision Avoidance with Differential Drive Robots Using MPC-ORCA [Текст] / G. R. Leite [et al.] // Simposio Brasileiro de Automagao Inteligen-te-SBAI. Vol. 1. — 2021.

87. Fiorini, P. Motion Planning in Dynamic Environments Using Velocity Obstacles [Текст] / P. Fiorini, Z. Shiller // The International Journal of Robotics Research. — 1998. — Vol. 17, no. 7. — P. 760—772.

88. Independent Navigation of Multiple Mobile Robots with Hybrid Reciprocal Velocity Obstacles [Текст] / J. Snape [et al.] // 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2009). — 2009. — P. 5917—5922.

89. Douthwaite, J. A. Velocity obstacle approaches for multi-agent collision avoidance [Текст] / J. A. Douthwaite, S. Zhao, L. S. Mihaylova // Unmanned Systems. — 2019. — Vol. 7, no. 01. — P. 55—64.

90. Alonso-Mora, J. Cooperative Collision Avoidance for Nonholonomic Robots [Текст] / J. Alonso-Mora, P. Beardsley, R. Siegwart // IEEE Transactions on Robotics. — 2018. — Vol. 34, no. 2. — P. 404—420.

91. PRVO: Probabilistic Reciprocal Velocity Obstacle for Multi Robot Navigation under Uncertainty [Текст] / B. Gopalakrishnan [et al.] // 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). — IEEE, 2017. — P. 1089—1096.

92. Weighted Buffered Voronoi Cells for Distributed Semi-Cooperative Behavior [Текст] / A. Pierson [et al.] // 2020 IEEE International Conference on Robotics and Automation (ICRA). — 2020. — P. 5611—5617.

93. Arul, S. H. V-RVO: Decentralized Multi-Agent Collision Avoidance Using Voronoi Diagrams and Reciprocal Velocity Obstacles [Текст] / S. H. Arul, D. Manocha // 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). — 2021. — P. 8097—8104.

94. Wang, M. Distributed Collision Avoidance of Multiple Robots with Probabilistic Buffered Voronoi Cells [Текст] / M. Wang, M. Schwager // 2019 International Symposium on Multi-Robot and Multi-Agent Systems (MRS). — IEEE, 2019. — P. 169—175.

95. Wang, L. Safety Barrier Certificates for Heterogeneous Multi-Robot Systems [Текст] / L. Wang, A. Ames, M. Egerstedt // 2016 American Control Conference (ACC). — 2016. — P. 5213—5218.

96. Long, P. Deep-Learned Collision Avoidance Policy for Distributed Multiagent Navigation [Текст] / P. Long, W. Liu, J. Pan // IEEE Robotics and Automation Letters. — 2017. — Vol. 2, no. 2. — P. 656—663.

97. Towards Optimally Decentralized Multi-Robot Collision Avoidance via Deep Reinforcement Learning [Текст] / P. Long [et al.] // Proceedings of the 2018 IEEE International Conference on Robotics and Automation ({ICRA} 2018). — 2018. — P. 6252—6259.

98. Distributed Multi-Robot Collision Avoidance via Deep Reinforcement Learning for Navigation in Complex Scenarios [Текст] / T. Fan [et al.] // The International Journal of Robotics Research. — 2020. — Vol. 39, no. 7.

99. Everett, M. Collision Avoidance in Pedestrian-Rich Environments with Deep Reinforcement Learning [Текст] / M. Everett, Y. F. Chen, J. P. How // IEEE access : practical innovations, open solutions. — 2021. — Vol. 9. — P. 10357—10377.

100. Least-Restrictive Multi-Agent Collision Avoidance via Deep Meta Reinforcement Learning and Optimal Control [Текст] / S. Asayesh [et al.] // International Conference on Robot Intelligence Technology and Applications. — Springer, 2022. — P. 213—225.

101. Reinforcement Learned Distributed Multi-Robot Navigation with Reciprocal Velocity Obstacle Shaped Rewards [Текст] / R. Han [et al.] // IEEE Robotics and Automation Letters. — 2022. — Vol. 7, no. 3. — P. 5896—5903.

102. Model Predictive Control for Multi-MAV Collision Avoidance in Dynamic Environments [Текст]. —2019. —URL: https://github.com/tud-amr/mrca-mav (visited on 05/05/2025).

103. Optimal Reciprocal Collision Avoidance [Текст]. — 2013. — URL: https: //github.com/snape/RVO2 (visited on 05/05/2025).

104. The Hybrid Reciprocal Velocity Obstacle [Текст]. — 2015. — URL: https: //github.com/snape/HRVO (visited on 05/05/2025).

105. ROS Multi Robot Collision Avoidance [Текст]. — 2015. — URL: https: //github.com/daenny/collvoid (visited on 05/05/2025).

106. Decentralized Probabilistic Multi-Robot Collision Avoidance Using Buffered Uncertainty-Aware Voronoi Cells [Текст]. — 2022. — URL: https://github. com/tud-amr/mrca_vc (visited on 05/05/2025).

107. Multi-Robot Collision Avoidance under Uncertainty with Probabilistic Safety Barrier Certificates [Текст]. — 2020. —URL: https://github.com/wenhaol/ PrSBC (visited on 05/05/2025).

108. CrowdNav [Текст]. —2018. — URL: https://github.com/vita-epfl/ CrowdNav (visited on 05/05/2025).

109. Towards Optimally Decentralized Multi-Robot Collision Avoidance via Deep Reinforcement Learning [Текст]. — 2018. — URL: https://github.com/ Acmece/rl-collision-avoidance (visited on 05/05/2025).

110. Reinforcement Learned Distributed Multi-Robot Navigation with Reciprocal Velocity Obstacle Shaped Rewards [Текст]. — 2022. — URL: https:// github.com/hanruihua/rl_rvo_nav (visited on 05/05/2025).

111. Kloder, S. Path Planning for Permutation-Invariant Multirobot Formations [Текст] / S. Kloder, S. Hutchinson // IEEE Transactions on Robotics. — 2006. — Vol. 22, no. 4. — P. 650—665.

112. Turpin, M. CAPT: Concurrent Assignment and Planning of Trajectories for Multiple Robots [Текст] / M. Turpin, N. Michael, V. Kumar // The International Journal of Robotics Research. — 2014. — Vol. 33, no. 1. — P. 98—112.

113. DC-CAPT: Concurrent Assignment and Planning of Trajectories for Dubins Cars [Текст] / M. Whitzer [et al.] // 2020 IEEE International Conference on Robotics and Automation (ICRA). — 2020. — P. 8791—8797.

114. Efficient Multi-Robot Motion Planning for Unlabeled Discs in Simple Polygons [Текст] / A. Adler [et al.] // Selected Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics (WAFR 2015). — 2015. — P. 1—17.

115. Le, D. Multi-Robot Motion Planning with Unlabeled Goals for Mobile Robots with Differential Constraints [Текст] / D. Le, E. Plaku // 2021 IEEE International Conference on Robotics and Automation (ICRA). — 2021.

116. Panagou, D. Decentralized Goal Assignment and Trajectory Generation in Multi-Robot Networks: A Multiple Lyapunov Functions Approach [Текст] / D. Panagou, M. Turpin, V. Kumar // Proceedings of IEEE International Conference on Robotics and Automation (ICRA 2014). — 2014. — P. 6757—6762.

117. Learning Graph-Enhanced Commander-Executor for Multi-Agent Navigation [Текст] / X. Yang [et al.]. — 2023.

118. Perception Field Based Imitation Learning for Unlabeled Multi-Agent Pathfinding [Текст] / W. Chu [et al.] // Science China Information Sciences. — 2024. — Vol. 67, no. 5. — P. 152107.

119. Decentralized, Unlabeled Multi-Agent Navigation in Obstacle-Rich Environments Using Graph Neural Networks [Текст] / X. Ji [et al.] // Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2021). — 2021. — P. 8936—8943.

120. Generalizability of Graph Neural Networks for Decentralized Unlabeled Motion Planning [Текст] / S. Muthusamy [et al.] // arXiv preprint arXiv:2409.19829. — 2024. — arXiv: 2409.19829.

121. Multi-Agent Target Assignment and Path Finding for Intelligent Warehouse: A Cooperative Multi-Agent Deep Reinforcement Learning Perspective [Текст] / Q. Liu [et al.] // arXiv preprint arXiv:2408.13750. — 2024. — arXiv: 2408.13750.

122. Theta*: Any-angle Path Planning on Grids [Текст] / K. Daniel [et al.] // Journal of Artificial Intelligence Research. Vol. 39. — 2010. — P. 533—579.

123. Сергеевич, П. А. Методика Планирования Траектории Движения Группы Мобильных Роботов в Неизвестной Замкнутой Среде с Препятствиями [Текст] / П. А. Сергеевич // Системы управления, связи и безопасности. — 2021. — № 3. — С. 38—59.

124. Mikula, J. TriVis: Versatile, Reliable, and High-Performance Tool for Computing Visibility in Polygonal Environments [Текст] / J. Mikula, M. Kulich, L. Preucil // 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). — 2024. — P. 10503—10510.

125. Sturtevant, N. R. Benchmarks for Grid-Based Pathfinding [Текст] / N. R. Sturtevant // IEEE Transactions on Computational Intelligence and AI in Games. — 2012. — Vol. 4, no. 2. — P. 144—148.

126. Information Theoretic MPC for Model-Based Reinforcement Learning [Текст] / G. Williams [et al.] // 2017 IEEE International Conference on Robotics and Automation (ICRA). — 2017. — P. 1714—1721.

127. Model Predictive Path Integral Control for Car Driving with Autogenerated Cost Map Based on Prior Map and Camera Image [Текст] / A. Buy-val [et al.] // 2019 IEEE Intelligent Transportation Systems Conference (ITSC). — 2019. — P. 2109—2114.

128. Multi-Agent Path Integral Control for Interaction-Aware Motion Planning in Urban Canals [Текст] / L. Streichenberg [et al.] // 2023 IEEE International Conference on Robotics and Automation (ICRA). — 2023. — P. 1379—1385.

129. Safety Embedded Stochastic Optimal Control of Networked Multi-Agent Systems via Barrier States [Текст] / L. Song [et al.] // 2023 American Control Conference (ACC). — 2023. — P. 2554—2559.

130. Aggressive Driving with Model Predictive Path Integral Control [Текст] / G. Williams [et al.] // Proceedings of the 2016 IEEE International Conference on Robotics and Automation (ICRA 2016). — 2016. — P. 1433—1440.

131. Williams, G. Model Predictive Path Integral Control: From Theory to Parallel Computation [Текст] / G. Williams, A. Aldrich, E. A. Theodorou // Journal of Guidance, Control, and Dynamics. — 2017. — Vol. 40, no. 2. — P. 344—357.

132. Robust model predictive path integral control: Analysis and performance guarantees [Текст] / M. S. Gandhi [et al.] // IEEE Robotics and Automation Letters. — 2021. — Vol. 6, no. 2. — P. 1423—1430.

133. Constrained covariance steering based tube-mppi [Текст] / I. M. Balci [et al.] // 2022 American Control Conference (ACC). — 2022. — P. 4197—4202.

134. Control barrier function augmentation in sampling-based control algorithm for sample efficiency [Текст] / C. Tao [et al.] // 2022 American Control Conference (ACC). — 2022. — P. 3488—3493.

135. Path integral methods with stochastic control barrier functions [Текст] / C. Tao [et al.] // 2022 IEEE 61st Conference on Decision and Control (CDC). — 2022. — P. 1654—1659.

136. Smooth model predictive path integral control without smoothing [Текст] / T. Kim [et al.] // IEEE Robotics and Automation Letters. — 2022. — Vol. 7, no. 4. — P. 10406—10413.

137. Sampling-Based Optimization for Multi-Agent Model Predictive Control [Текст] / Z. Wang [et al.]. — 2022.

138. Williams, G. R. Model Predictive Path Integral Control: Theoretical Foundations and Applications to Autonomous Driving [Текст] / Williams Grady Robert. -Georgia Institute of Technology, 2019.

139. Gulzar, M. A Survey on Motion Prediction of Pedestrians and Vehicles for Autonomous Driving [Текст] / M. Gulzar, Y. Muhammad, N. Muhammad // IEEE access : practical innovations, open solutions. — 2021. — Vol. 9. — P. 137957—137969.

140. Liu, B. Theory and Practice of Uncertain Programming [Текст]. Vol. 239 / B. Liu, B. Liu. — Springer, 2009.

141. Murty, K. G. Some NP-complete Problems in Quadratic and Nonlinear Programming [Текст] / K. G. Murty, S. N. Kabadi. — 1985.

142. Nemirovski, A. Interior Point Polynomial Time Methods in Convex Programming [Текст] / A. Nemirovski // Lecture notes. — 2004. —Vol. 42, no. 16. — P. 3215—3224.

143. Kuo, Y.-J. Interior Point Methods for Second-Order Cone Programming and OR Applications [Текст] / Y.-J. Kuo, H. D. Mittelmann // Computational Optimization and Applications. — 2004. — Vol. 28. — P. 255—285.

144. Diamond, S. CVXPY: A Python-embedded Modeling Language for Convex Optimization [Текст] / S. Diamond, S. Boyd // Journal of Machine Learning Research. — 2016. — Vol. 17, no. 83. — P. 1—5.

145. A Rewriting System for Convex Optimization Problems [Текст] / A. Agrawal [et al.] // Journal of Control and Decision. — 2018. — Vol. 5, no. 1. — P. 42—60.

146. Domahidi, A. ECOS: An SOCP Solver for Embedded Systems [Текст] / A. Domahidi, E. Chu, S. Boyd // 2013 European Control Conference (ECC). — 2013. — P. 3071—3076.

147. Koenig, S. D* Lite [Текст] / S. Koenig, M. Likhachev // Proceedings of the 18th AAI Conference on Artificial Intelligence ({AAAI} 2002). — 2002. — P. 476—483.

148. Optimal Any-Angle Pathfinding in Practice [Текст] / D. Harabor [et al.] // Journal of Artificial Intelligence Research. — 2016. —Vol. 56. — P. 89—118.

149. Any-Angle Path Planning for Computer Games [Текст] / P. Yap [et al.] // Proceedings of the 7th AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE 2011. — 2011. — P. 201—207.

150. Thorpe, C. Path Relaxation: Path Planning for a Mobile Robot [Текст] / C. Thorpe, L. Matthies // Oceans 1984. — 1984. — P. 576—581.

151. 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.

152. Likhachev, M. Planning Long Dynamically-Feasible Maneuvers for Autonomous Vehicles [Текст] / M. Likhachev, D. Ferguson // Robotics: Science and Systems. — 2009. — Vol. 4, no. 8. — P. 214—221.

153. Hybrid A* Based Motion Planning for Autonomous Vehicles in Unstructured Environment [Текст] / K. Tu [et al.] // 2019 IEEE International Symposium on Circuits and Systems (ISCAS). — 2019. — P. 1—4.

154. Kushleyev, A. Time-Bounded Lattice for Efficient Planning in Dynamic Environments [Текст] / A. Kushleyev, M. Likhachev // 2009 IEEE International Conference on Robotics and Automation. — 2009. — P. 1662—1668.

155. LaValle, S. Rapidly-Exploring Random Trees: A New Tool for Path Planning [Текст] / S. LaValle // Research Report 9811. — 1998.

156. Karaman, S. Sampling-Based Algorithms for Optimal Motion Planning [Текст] / S. Karaman, E. Frazzoli // The International Journal of Robotics Research. — 2011. — Vol. 30, no. 7. — P. 846—894.

157. LaValle, S. M. Planning Algorithms [Текст] / S. M. LaValle. — Cambridge university press, 2006.

158. Zhang, S. Optimal Control Based Trajectory Planning under Uncertainty [Текст] / S. Zhang, M. Hadji, A. Lisser // International Conference on Intelligent Transport Systems. — 2022. — P. 73—88.

159. CHOMP: Gradient Optimization Techniques for Efficient Motion Planning [Текст] / N. Ratliff [et al.] // 2009 IEEE International Conference on Robotics and Automation. — 2009. — P. 489—494.

160. Finding Locally Optimal, Collision-Free Trajectories with Sequential Convex Optimization. [Текст] / J. Schulman [et al.] // Robotics: Science and Systems. Vol. 9. — 2013. — P. 1—10.

161. B-Spline Path Planner for Safe Navigation of Mobile Robots [Текст] / N. T. Nguyen [et al.] // 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). — 2021. — P. 339—345.

162. An Optimization-Based Planner with b-Spline Parameterized Continuous-Time Reference Signals [Текст] / C. Tao [et al.] // 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). — 2024. — P. 3100—3107.

163. Aggressive Flight of Fixed-Wing and Quadrotor Aircraft in Dense Indoor Environments [Текст] / A. Bry [et al.] // The International Journal of Robotics Research. — 2015. — Vol. 34, no. 7. — P. 969—1002.

164. A Survey of Learning-Based Robot Motion Planning [Текст] / J. Wang [et al.] // IET Cyber-Systems and Robotics. — 2021. — Vol. 3, no. 4. — P. 302—314.

165. Path Planning Using Neural A* Search [Текст] / R. Yonetani [et al.] // Proceedings of the 38th International Conference on Machine Learning. Vol. 139. — 2021. — P. 12029—12039.

166. Neural RRT*: Learning-based Optimal Path Planning [Текст] / J. Wang [et al.] // IEEE Transactions on Automation Science and Engineering. — 2020. — Vol. 17, no. 4. — P. 1748—1758.

167. Sutton, R. S. Integrated Architectures for Learning, Planning, and Reacting Based on Approximating Dynamic Programming [Текст] / R. S. Sutton // Machine Learning Proceedings 1990. — 1990. — P. 216—224.

168. Jurgenson, T. Harnessing Reinforcement Learning for Neural Motion Planning [Текст] / T. Jurgenson, A. Tamar // Proceedings of Robotics: Science and Systems (RSS 2019). — 2019.

169. A Framework for Real-World Multi-Robot Systems Running Decentralized GNN-based Policies [Текст] / J. Blumenkamp [et al.] // International Conference on Robotics and Automation (ICRA 2022). — 2022. — P. 8772—8778.

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

1.1 Иллюстрация классической поставноки задачи навигации группы мобильных агентов............................. 12

1.2 Иллюстрация голономной модели движения агента (слева) и

модели движения двухколесного робота (справа)............ 15

1.3 Иллюстрация различных моделей представления рабочей области на примере задачи навигации двух мобильных агентов. (a) Изначальное представление задачи в непрерывном виде. (b) Представление среды в виде 4-связанной сетки. (с) Представление среды в виде 8-связанной сетки. (d) Представление среды в виде графа видимости.............................. 23

1.4 Иллюстрация добавления нового семпла в граф в алгоритме PRM. Иллюстрации из [40]............................ 24

1.5 Иллюстрация примера задачи много-агентной навигации для которой использование графов регулярной декомпозиции может быть затруднительно. (a) Изначальное представление задачи в непрерывном виде. (b) Представление среды в виде сетки. (с) Представление среды в виде графа видимости.............. 24

1.6 Иллюстрация решения задач планирования траектории с учетом препятствий, заданных в виде окружностей и эллипсов. Иллюстрации из [52]............................ 25

1.7 Иллюстрация решения задачи много-агентной навигации в пространстве с препятствиями, заданными как многоугольники. Иллюстрация из [51]............................ 26

2.1 Иллюстрация базового подхода к избеганию столкновений с использованием MPC, основанном на использовании

известных/предсказанных траекторий. Иллюстрации из [82]...... 33

2.2 Иллюстрация принципов работы алгоритма ORCA [22]. Слева

представлена визуализация "скоростного препятствия" и получения на его основе линейного ограничения. Справа представлена визуализация построения подмножества безопасных скоростей на

основе набора линейных ограничений в задаче много-агетной

навигации. Иллюстрации из [22]...................... 34

2.3 Визуализация таблицы максимальной ошибки движения вдоль голономной траектории агентом с кинематической моделью автомобиля. Иллюстрация из [90]..................... 36

2.4 Иллюстрация последовательного выполнения задачи навигации методом БУС. На каждом шаге агенты (изображены как круги разных цветов) остаются внутри соответствующих им областей буферных ячеек Вороного (границы диаграммы Вороного изображены серыми линиями, границы ячеек изображены

цветными линиями). Иллюстрация из [10] ............... 36

2.5 Иллюстрация работы метода SBC с опорой на внешний контроллер, продвигающего агента к цели. Иллюстрации из [95] . . 38

2.6 Иллюстрация, демонстрирующая шаг RL алгоритма в решении

задачи навигации с двумя агентами. (а) Визуализация состояний агентов. (Ь) Визуализация полезности скоростей с точки зрения приближения одного из агентов к цели. (с) Визуализация оценки опасности скоростей с точки зрения возможных столкновений. (^ Визуализация итоговой функции полезности и оптимальной

скорости . Иллюстрации из [99] ..................... 39

3.1 Иллюстрация возникновения ситуации взаимной блокировки агентами при преодолении узкого прохода................ 50

3.2 Схема базовой архитектуры построения алгоритма децентрализованной навигации в синхронном (сверху) и асинхронном исполнении (снизу)..................... 53

3.3 Иллюстрация процесса обновления глобальной траектории агента

при отклонении от исходной ....................... 54

3.4 Иллюстрация создания координированной группы агентов и преодоления ситуации взаимоблокировки с помощью создания координированного плана действий ................... 56

3.5 Иллюстрация создания задания для распределенного запуска централизованного алгоритма...................... 60

3.6 Иллюстрация карт, которые были использованы в экспериментальной оценке алгоритма кооперативной

много-агентной навигации......................... 64

3.7 Общая стоимость решений и доля координированного режима в их стоимости в зависимости от числа агентов на картах gaps-1 и room-32-32-4 ................................ 67

3.8 Результаты выполнения алгоритмов MAPF на заданиях, полученных в ходе основного эксперимента............... 68

4.1 Иллюстрация классической задачи навигации (слева) и задачи навигации взаимозаменяемых агентов (справа)............. 71

4.2 Иллюстрация децентрализованного сценария навигации взаимозаменяемых агентов с согласованным (слева) и несогласованным (справа) начальными назначениями целей...... 75

4.3 Примеры разрешения (а) конфликтов и (b) взаимных блокировок с использованием механизма обмена целями ............... 76

4.4 Пример децентрализованного решения задачи AMAPF алгоритмом TP-SWAP .................................. 83

4.5 Иллюстрация карт, которые были использованы в экспериментальной оценке алгоритмов навигации

взаимозаменяемых агентов........................ 97

4.6 Средние значения показателя flowtime и соответствующее стандартное отклонение, полученные в рамках экспериментальной оценки алгоритмов. Меньше - лучше.................. 99

4.7 Средние значения показателя makespan и соответствующее стандартное отклонение, полученные в рамках экспериментальной оценки алгоритмов. Меньше - лучше..................101

5.1 Иллюстрация выполнения одного шага алгоритма MPPI.......112

5.2 Пример сценария, при котором выбор действия на основе предсказанных траекторий может привести к столкновению между агентами...................................117

5.3 Иллюстрация выбора действия агентом и использованием семплирования из заранее заданного распределения и распределения, построенного на основе безопасных параметров. . . 118

5.4 Общая схема работы алгоритма избегания столкновений на основеМРР1. Красным цветом выделены элементы, которые были добавлены к процедуре МРР1 для её адаптации к децентрализованному много-агентному сценарию. (*) Основным результатом текущего исследования является разработка метода

учета линейных ограничений в процессе семплирования. Соответствующий компонент отмечен звёздочкой на схеме.......119

5.5 Иллюстрация сценариев, использованных в экспериментальной

оценке алгоритма много-агентного избегания столкновений......130

5.6 Средние значения показателя makespan и их стандартное отклонение для оцениваемых алгоритмов при различном

количестве агентов в сценарии Circle. Меньше - лучше.......133

5.7 Иллюстрация решений для сценария Circle с 10 агентами для оцениваемых алгоритмов. В верхней части представлены визуализации траекторий. В нижней части - график средней

скорости агентов относительно времени (синяя линия) и средняя скорость всех агентов за весь период моделирования (оранжевая линия)....................................133

5.8 Средние значения makespan и их стандартное отклонение для оцениваемых алгоритмов при различной плотности агентов в сценарии Grid. В расчет включены только те случаи, где все алгоритмы успешно решили задачу во всех запусках. Меньше - лучше135

5.9 Иллюстрация траекторий для сценария Grid-Sparse с 9 агентами для оцениваемых алгоритмов. В верхней части изображена визуализация траекторий. В нижней части представлен график изменения средней скорости агентов во времени (синяя линия), а также средняя скорость всех агентов за весь период симуляции (оранжевая линия).............................136

5.10 Средние значения показателя makespan и их стандартное отклонение для оцениваемых алгоритмов при различном количестве агентов в сценарии Random. В расчет включены только те случаи, где все алгоритмы успешно решили задачу во всех

5.11 Иллюстрация решений для сценария Random с 20 агентами для оцениваемых алгоритмов. В верхней части представлены визуализации траекторий. В нижней части - график средней скорости агентов относительно времени (синяя линия) и средняя скорость всех агентов за весь период моделирования (оранжевая линия)....................................138

5.12 Значение среднего пройденного расстояния и соответствующее стандартное отклонение для оцениваемых алгоритмов при различном количестве агентов в сценарии Circle. Значение для конкретного задания добавлялся учитывался в результате только

если все алгоритмы успешно решили это задание. Меньше - лучше. . 138

5.13 Значение среднего пройденного расстояния и соответствующее стандартное отклонение для оцениваемых алгоритмов при различной плотности агентов в сценарии Grid. Значение для конкретного задания добавлялся учитывался в результате только

если все алгоритмы успешно решили это задание. Меньше - лучше . 139

5.14 Значение среднего пройденного расстояния и соответствующее стандартное отклонение для оцениваемых алгоритмов при различном количестве агентов в сценарии Random. Значение для конкретного задания добавлялся учитывался в результате только

если все алгоритмы успешно решили это задание. Меньше - лучше . 140

А.1 Иллюстрация решения задач планирования траектории

индивидуального агента с помощью различных методов поиска

пути на графе ...............................170

А.2 Иллюстрация формирования графа в пространстве состояний с помощью примитивов движения и пример траектории для кинематической модели движения автомобиля. Иллюстрации

запусках. Меньше - лучше

из [152; 154]

171

А.3 Иллюстрация итеративного построения дерева состояний алгоритмом RRT* и соответствующее изменение итоговой

траектории. Иллюстрация из [156]....................172

А.4 Иллюстрация траектории, заданной с использованием полиномиальных кривых, соединяющих дискретную последовательность опорных точек. Слева показана траектория в трёхмерном пространстве, справа - соответствующие траектории по

каждой из координат и углу рысканья. Иллюстрация из [163].....173

А.5 Сравнение классического алгоритма A* и его модификации - Neural A*, использующей методы машинного обучения. Иллюстрация из [165]....................................174

Б.1 Иллюстрация решений для задачи Circle с 2, 5, 10 и 15 агентами с динамикой автомобильного типа для алгоритма MPPI-ORCA. На верхней части рисунка представлены визуализации траекторий. В нижней части изображен график средней скорости агентов во времени (синяя линия), а также средняя скорость всех агентов за

весь период симуляции (оранжевая линия)................177

Б.2 Визуализация траекторий для предложенного метода (a-c) и метода на основе обучения (d-f) с 4, 5 и 6 агентами для оцениваемых

алгоритмов.................................180

Б.3 Средние значения makespan и стандартные отклонения для предложенного алгоритма при различных уровнях неопределённости данных и различном количестве агентов в сценарии Random с разнородными агентами...............182

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

2.1 Сравнительная таблица ключевых методов децентрализованного

много-агентного планирования движений ................ 44

3.1 Доля успешно решенных заданий в зависимости от числа агентов

на 4 различных картах. Больше - лучше................ 66

3.2 Статистика по заданиям MAPF, полученным в результате запуска предложенного алгоритма. Столбцы Nmapf содержат данные о среднем числе заданий, столбцы Nag - среднем числе

агентов-участников ............................ 68

4.1 Среднее значение показателя makespan для децентрализованных алгоритмов с различными диапазонами коммуникации на карте maze-32-32-4 ................................ 102

4.2 Среднее значение показателя flowtime для децентрализованных алгоритмов с различными диапазонами коммуникации на карте maze-32-32-4 ................................ 102

4.3 Среднее число агентов в подгруппах для децентрализованных алгоритмов с различными диапазонами коммуникации на карте maze-32-32-4 ................................ 103

4.4 Среднее число связанных подгруп для децентрализованных алгоритмов с различными диапазонами коммуникации на карте maze-32-32-4 ................................ 103

5.1 Средние значения success rate для оцениваемых алгоритмов при различной плотности и различном количестве агентов в сценарии

Grid......................................134

5.2 Средние значения success rate для оцениваемых алгоритмов при различном количестве агентов в сценарии Random............136

Б.1 Значение success rate и средние значения makespan для предложенного метода в сценарии Circle с динамикой автомобильного типа............................176

Б.2 Средние значения saccess rate для предложенного алгоритма в сравнении с методом на основе обучения для разного количества

агентов...................................179

Б.3 Средние значения success rate для предложенного алгоритма при различных уровнях неопределённости данных и различном количестве агентов в сценарии Random с разнородными агентами . . 182

Приложение А

Обзор методов планирования траектории индивидуального

мобильного агента

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

Поиск пути на графе: Одним из наиболее распространённых вариантов решения задачи планирования индивидуальной траектории является представление этой задачи, как задачи поиска пути на графе. В этом случае могут быть использованы модели представления среды, описанные в разделе 1.3 и классические алгоритмы поиска путей на графах, такие как алгоритм Дейкстры [41] или эвристические алгоритмы семейства А* [42; 122; 147—149]. Иллюстрация задачи, заданной в непрерывном пространстве и решений полученных графовым подходом представлена на рисунке А.1.

Так, использование графов видимости позволяет эффективно находить кратчайшие траектории на плоскости (рисунок А.1-Ь), однако алгоритмы построения графов видимости обладают в лучшем случае временной сложностью 0(п1одп + к) (где п - число вершин многоугольников, к - число ребер в графе) [49], что ограничивает их применимость в практических задачах, особенно при необходимости динамически обновлять граф. Возможный вариант решения этой проблемы описан в [48], где предлагается строить граф лишь для локально наблюдаемых областей небольшого размера. После того, как для локальной

(а) Задача (Ь) Граф видимости + А* (Ь)ГРД + А" (Ь) ГРД + ТЬе1а*

Рисунок А.1 — Иллюстрация решения задач планирования траектории индивидуального агента с помощью различных методов поиска пути на графе

области был построен соответствующий граф, он добавляется в глобальную карту, а перекрывающиеся (близкие) вершины локального и глобального графа объединяются.

При использовании представления среды в виде сетки применение классических алгоритмов поиска может привести к нахождению путей большой стоимости, состоящих их большого числа коротких сегментов (рисунок А.1-с). Для решения этой проблемы могут быть использованы алгоритмы сглаживания [150], либо алгоритмы any-angle поиска, такие как ТНеЬа* [122] или ЛХУЛ [148] (рисунок А.1-ё).

Поиск с использованием примитивов движения: Развитием идеи использования алгоритмов поиска пути на графах, но позволяющий учитывать кинематические ограничения, является подход с использованием примитивов движения [151—154]. Пространство состояний X дискретизируется не только по положению, но и другим переменным состояния (например, по ориентации). В каждой вершине-состоянии рассматривается набор допустимых траекторий, приводящих к новым состояниям. Поиск траектории осуществляется на графе достижимых состояний, сформированном на лету, с использованием методов графового поиска. Проверка проходимости вдоль того или иного ребра может осуществляться как с применением дискретного описания пространства, так и аналитического/непрерывного. Этот подход позволяет строить физически выполнимые траектории и учитывать ограничения движения на этапе планирования. Иллюстрации, демонстрирующие принцип формирования графа в пространстве состояний с помощью примитивов движения, а так же пример траектории представлены на рисунке А.2.

Рисунок А.2 — Иллюстрация формирования графа в пространстве состояний с помощью примитивов движения и пример траектории для кинематической модели движения автомобиля. Иллюстрации из [152; 154]

Стохастические методы: Помимо методов, основанных на полной дискретизации рабочей области или пространства состояний, широкое распространение получили также стохастические подходы, действующие напрямую в непрерывном пространстве. В этих методах пространство состояний не дискре-тизируется заранее, а исследуется путем последовательного случайного выбора (семплирования) отдельных элементов. Одним из наиболее известных алгоритмов этого типа является Rapidly-exploring Random Tree (RRT) [155], который строит ориентированное дерево достижимых состояний, итеративно увеличивая его путем добавления случайно выбранных точек пространства.

Алгоритм RRT * [156] представляет собой усовершенствованную версию RRT, обеспечивающую асимптотическую оптимальность: по мере роста числа семплов построенный путь стремится к минимальному по стоимости (иллюстрация этого процесса представлена на рисунке А.3).

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

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

Рисунок А.3 — Иллюстрация итеративного построения дерева состояний алгоритмом ЯЯТ* и соответствующее изменение итоговой траектории. Иллюстрация из [156].

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

Среди таких методов можно выделить несколько основных направлений исследований. Одно из них рассматривает построение траектории как задачу поиска оптимального управления [157; 158]. Другие оптимизируют последовательности состояний [159; 160] и рассматривают гладкость траектории с точки зрения разницы между последовательно идущими состояниями. Третьи фокусируется на поиске коэффициентов параметрических кривых [161—163] (рисунок А.4), что позволяет генерировать гладкие и кинематически выполнимые траектории.

Стоит отметить, что такие методы позволяют работать в пространствах большой размерности, что делает их применимыми не только для колёсных роботов, но и для манипуляторов с большим числом степеней свободы [159; 160]. Однако, многие из них опираются на некоторое начальное решение (начальное приближение, начальную догадку) для инициализации процесса оптимизации, которое часто получают с помощью дискретных алгоритмов поиска пути. Кроме того, из-за вычислительной сложности, такие методы зачастую применяются

£ 0.5

Time (s)

Рисунок А.4 — Иллюстрация траектории, заданной с использованием полиномиальных кривых, соединяющих дискретную последовательность опорных точек. Слева показана траектория в трёхмерном пространстве, справа - соответствующие траектории по каждой из координат и углу рысканья. Иллюстрация

из [163].

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

Методы, основанные на обучении: Всё большую популярность приобретают обучаемые методы планирования траектории, что связано с их способностью преодолевать ограничения классических алгоритмов, испытывающих затруднения при работе в высокоразмерных или динамически меняющихся средах. Подобные методы могут применяться как для полной замены традиционных планировщиков, так и для усовершенствования отдельных их компонентов [164].

Так, например, в алгоритме Neural A* [165] машинное обучение используется для ранжирования вершин в очереди, позволяя повысить эффективность поиска по сравнению с классическим A*. Рисунок А.5 иллюстрирует решение задачи классическим подходом и методом Neural A*. На левой части рисунка представлена исходная постановка задачи. Центральный и правый части иллюстрируют решения, полученные с помощью алгоритмов A* и Neural A* соответственно. Зелёным цветом обозначены вершины, посещённые в процессе поиска. Видно, что Neural A* рассматривает меньшее количество вершин, что свидетельствует о более эффективной стратегии поиска.

В методе Neural RRT* [166] нейросетевые модели применяются для генерации информированных распределений, ускоряющих сходимость алгоритма

(a) Input

Neural А*

IGpail

ГИГИ ПНГ

Рисунок А.5 — Сравнение классического алгоритма A* и его модификации -Neural A*, использующей методы машинного обучения. Иллюстрация из [165].

RRT. Отдельного внимания заслуживают подходы, основанные на обучении с подкреплением, в которых задача планирования формулируется как марковский процесс принятия решений. Это позволяет агенту осваивать стратегии поведения путём взаимодействия с окружающей средой [167; 168]. Тем не менее, остаются открытыми вопросы, касающиеся обобщающей способности обученных моделей и их адаптивности к условиям, существенно отличающимся от тех, в которых осуществлялось обучение [164].

Приложение Б

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

ограничений

Б.1 Эксперименты с моделью движения автомобильного типа

Б.1.1 Постановка эксперимента

Данная серия экспериментов была направлена на проверку предложенного метода для управления роботами с автомобильной моделью движения. Для этого использовалась следующая модель. Состояние робота xt = (Px,t,Py,t, Qt)T в данном случае аналогично состоянию робота с двухколесным роботом. Однако управление ut = (vt, фг)Т состоит из линейной скорости Vt и угла поворота колес ф^. Как и в случае двухколесного робота, диапазон управляющих воздействий ограничен (vmm < vt < vmax, -f/2 < фтт < фt < фтоаж < п/2). Уравнения движения для этой модели следующие:

px,t+i = px,t + vt cos QtAt,

Py,t+i = py,t + vt sin QtAt, (Б.1)

v

Qt+i = Qt + j tg фíAí,

где L - расстояние между задней и передней осями.

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

Для всех роботов использовались следующие параметры: размер роботов (радиус соответствующих дисков) г = 0.3 т, пределы линейной скорости vTO¡n = -1.0 м/c, vmax = 1.0 м/c, пределы угла поворота фтот = -f рад, фтоах = f рад, расстояние между осями L = 0.2 м, радиус обзора/связи R не ограничен.

Для эксперимента был использован сценарий Circle с теми же наборами входных данных, что и для двухколесных роботов. Значения At, £ и кцто

были установлены равными 0.1 с, 0.3 м и 1000 шагов соответственно. Также применялся дополнительный буфер безопасности £г = 0.05 м, как и в случае с двухколесными роботами. Каждое задание запускалось по 10 раз.

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

Таблица Б.1 — Значение success rate и средние значения makespan для предложенного метода в сценарии Circle с динамикой автомобильного типа.

Число агентов 2 3 4 5 6 7 8 9 10 11 12 13 14 15

success rate 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100%

makespan 166.8 169.8 193.4 211.2 216.8 247.0 276.6 285.4 298.7 319.4 342.0 355.5 368.7 392.7

Основными показателями, измеряемыми в рамках эксперимента, были success rate и makespan. Результаты запусков предложенного метода представлены в таблице Б.1. Отметим, что во всех случаях предложенный метод успешно решил все задачи.

Однако следует отметить, что показатели makespan увеличились по сравнению предыдущим экспериментом. Например, для 2 агентов значение увеличилось примерно на 25%, а для 15 - на 66%. Этот рост может быть связан с тем, что, в отличие от двухколесных роботов, модель движения автомобильного типа не предполагает возможности разворота на месте. Таким образом, в условиях плотного расположения агентов им приходится либо двигаться назад, либо, в некоторых случаях, даже выполнять длительный маневр объезда.

Подобные эффекты можно наблюдать на визуализации траекторий на рисунке Б.1, полученных во время выполнения задач. Видно, что для небольшого числа агентов (2 и 5) траектории являются плавными и схожи с траекториями двухколесных роботов, но в случаях с 10 и 15 агентами траектории содержат осциляции и значительные маневры для объезда.

(а) 10 agents (b) 15 agents

Рисунок Б.1 — Иллюстрация решений для задачи Circle с 2, 5, 10 и 15 агентами с динамикой автомобильного типа для алгоритма MPPI-ORCA. На верхней части рисунка представлены визуализации траекторий. В нижней части изображен график средней скорости агентов во времени (синяя линия), а также средняя скорость всех агентов за весь период симуляции (оранжевая линия).

Б.2 Сравнение с подходом, основанным на обучении с

подкреплением

Б.2.1 Постановка эксперимента

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

Основное изменение заключалось в исключении препятствий из среды. Также были сняты ограничения на ускорение для метода, основанного на обучении. Для эксперимента использовались следующие параметры. Предложенный подход применял модель движения двухколесного робота (уравнение (1.3)). Размеры роботов (радиус соответствующих дисков) составляли г = 0.25 м, ограничение линейной скорости vmin = -1.0 м/c, vmax = 1.0 м/c, ограничение угловой скорости wmin = -2.0 рад/c, wmax = 2.0 рад/c, радиус видимости/связи R не был ограничен. Также использовался дополнительный буфер безопасности размером £г = 0.05 м для обоих алгоритмов для минимизации вероятности столкновения. Значения At, £ и кцт составляли 0.1 c, 0.3 м и 1000 шагов, соответственно. Каждое задание запускалось 10 раз. Для обучения использовался сценарий с 5 агентами, предложенный авторами метода.

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

В данном сценарии начальные и целевые позиции роботов располагались аналогично сценарию Circle, описанному ранее. Радиус круга был установлен равным 0.7 м, но центры начального и целевого кругов располагались на случайном расстоянии друг от друга. Кроме того, все позиции в начальных и целевых кругах были смещены на случайный угол (разный для начальных и

целевых позиций). Количество агентов варьировалось от 4 до 6 с шагом 1, и для каждого количества агентов было сгенерировано 50 различных заданий.

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

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

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

Таблица Б.2 — Средние значения saccess rate для предложенного алгоритма в сравнении с методом на основе обучения для разного количества агентов

Число агентов MPPI-ORCA Multi-Agent RL

4 98 % 48%

5 98 % 42%

6 87 % 16%

На рисунке Б.2 представлены визуализации решений для предложенного и обученного методов в задачах с 4, 5 и 6 агентами. Из рисунка видно, что в случаях, когда алгоритм на основе обучения находил решение, траектории могли быть более прямолинейными. Однако это обусловлено тем, что предложенный алгоритм учитывает ограничения динамики двухколесного робота, тогда как метод на основе обучения этого не делает.

(e) RL, 5 agents

Рисунок Б.2 — Визуализация траекторий для предложенного метода (a-c) и метода на основе обучения (d-f) с 4, 5 и 6 агентами для оцениваемых алгоритмов

Б.3 Эксперименты с разнородными агентами и неопределенность

во входных данных

Б.3.1 Постановка эксперимента

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

Для этого использовался модифицированный сценарий Random с двухколесными роботами. Все агенты были разделены на две группы. В первой группе роботы имели размер 0.2 м, ограничения линейной скорости Vmin = -1.0 м/c, Vmax = 1.0 м/c, ограничения угловой скорости Wmin = -2.0 рад/c, wmax = 2.0 рад/c. Во второй группе роботы имели размер 0.5 м,

ограничения линейной скорости vmin = -3.0 м/c, vmax = 3.0 м/c, ограничения угловой скорости wmin = -6.0 рад/c, wmax = 6.0 рад/c. Для обработки погрешностей в данных буфер безопасности был увеличен до 0.15 м.

Неопределенность в данных вводилась следующим образом. На каждом шаге алгоритму предоставлялись измененные данные о положении, скорости и направлении агента, а также о положениях и скоростях соседних агентов. Каждое значение дополнялось случайным шумом с заданными отклонениями (иху для шума в данных о позиции, uv для шума в данных о скорости, Uq для шума в данных о направления). В эксперименте использовались следующие уровни неопределенности. Первый шаг включал запуск алгоритма без искажений в данных (обозначен в результатах экспериментов как " Perfect"). Далее рассматривались три уровня неопределенности: иху = 0.01, Uq = 0.02 (первый уровень), uxy = 0.08, uq = 0.04 (второй уровень), иху = 0.16, uq = 0.08 (третий уровень). Уровень неточности в данных о скорости задавался на основе уровня неточности в данных о позициях: uv = yjU2xy + U2xy.

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

Основными исследуемыми показателями в эксперименте были success rate и критерий качества makespan. Средние значения success rate для всех уровней неопределенности приведены в таблице Б.3. В большинстве запусков, за исключением экспериментов с наивысшим уровнем неопределенности, снижение success rate было связано с превышением лимита времени. Однако при наивысшем уровне неопределенности наблюдались отдельные случаи столкновений агентов (1 случай для задач с 15 и 20 агентами, 4 случая для задач с 25 агентами).

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

Таблица Б.3 — Средние значения success rate для предложенного алгоритма при различных уровнях неопределённости данных и различном количестве агентов в сценарии Random с разнородными агентами

Число агентов Oxy = 0 ое = 0 оху = 0.01 ое = 0.02 оху = 0.08 ое = 0.04 оху = 0.16 ое = 0.08

5 100 % 100 % 100 % 100 %

10 100 % 100 % 100 % 99 %

15 98 % 99 % 100 % 84 %

20 94 % 97% 100 % 47 %

25 93 % 96 % 99 % 12 %

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

Интересно отметить эффект, при котором при небольшом увеличении неопределенности доля успешных решений может возрастать. Это может быть связано с тем, что небольшая случайность в данных помогает преодолевать взаимоблокировки или симметричные ситуации, аналогично тому, как небольшое случайное значение добавлялось к вектору, направленному на цель, в методах ОЯСЛ-ВВ и Б-иЛУС.

5 10 15 20 25

Number of agents

Рисунок Б.3 — Средние значения makespan и стандартные отклонения для предложенного алгоритма при различных уровнях неопределённости данных и различном количестве агентов в сценарии Random с разнородными агентами

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

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