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

• Скрынник Алексей Александрович
• кандидат наук
• 2023

Оглавление диссертации кандидат наук Скрынник Алексей Александрович

Введение

Глава 1. Обучение с подкреплением в задачах навигации

1.1 Обучение с подкреплением

1.1.1 Марковский процесс принятия решений

1.1.2 Методы на основе функции полезности

1.1.3 Методы, на основе оптимизации градиента стратегии

1.1.4 Частичная наблюдаемость

1.1.5 Многоагентность

1.2 Обучение агентов решению задач навигации

1.2.1 Пространство наблюдений и действий

1.2.2 Показатели качества

1.3 Состояние исследований

1.3.1 Классические алгоритмы решения задачи навигации

1.3.2 Машинное обучение с учителем для задач навигации

1.3.3 Обучение с подкреплением для задач навигации

Глава 2. Навигация в 2Б средах со стохастическими препятствиями

2.1 Среда со стохастическими препятствиями

2.1.1 Задача навигации в клеточной среде

2.1.2 Стохастические препятствия

2.2 Решение на основе планирования

2.3 Решение на основе обучения

2.4 Постановка эксперимента

2.5 Результаты

2.5.1 Навигация в стохастических средах

2.5.2 Сравнение качества найденных решений

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

Глава 3. Визуальная навигация в 3В средах

3.1 Среда МтвсгаА

3.2 Алгоритм ForgER

3.2.1 "Забывание" при обучении по демонстрациям

3.2.2 Иерархическая аугментация

3.3 Постановка эксперимента

3.3.1 Формирование иерархии навыков

3.3.2 Разделение экспертных данных по навыкам

3.3.3 Функция псевдо-вознаграждения для навыков

3.3.4 Параметры для обучения модели

3.4 Результаты

3.4.1 Получение ресурсов в среде МтвсгаА

3.4.2 Анализ значимых участков наблюдения при предсказании полезности

3.4.3 Влияние иерархической аугментации на стратегию агента

3.4.4 Влияние составляющих функции потерь на процесс обучения

3.4.5 Выбор функции "забывания" при обучении по демонстрациям

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

Глава 4. Интеграция методов планирования и обучения с

подкреплением в задачах многоагентной навигации

4.1 Задача многоагентной навигации

4.2 Решение на основе планирования

4.3 Решение на основе обучения

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

4.4.1 Эвристический переключатель

4.4.2 Переключатель на основе результатов планирования

4.4.3 Обучаемый переключатель

4.5 Постановка эксперимента

4.6 Результаты

4.6.1 Качество работы предложенных алгоритмов

4.6.2 Сравнение с современными обучаемыми и централизованными алгоритмами

4.6.3 Масштабируемость алгоритмов в сценарии автоматизированного склада

4.6.4 Анализ компонент алгоритма RePlan

4.6.5 Влияние Grid Memory на результаты обучения EPOM

4.6.6 Влияние радиуса обзора и информации из предыдущих наблюдений на результаты алгоритма EPOM

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

Глава 5. Симуляционная среда для задач навигации

5.1 Клеточные среды для задач навигации

5.1.1 Среда ProcgenMaze

5.1.2 Среда Flatland

5.1.3 Набор сред MAGENT

5.1.4 Среда DeepMind Lab2D

5.1.5 Проект Griddly

5.1.6 Набор сред Melting Pot

5.1.7 Другие среды

5.2 Среда POGEMA

5.2.1 Сценарии исчезновения агентов в целевой точке

5.2.2 Сценарий бесконечных целей

5.2.3 Сценарий кооперативного завершения эпизода

5.2.4 Пространство наблюдений

5.2.5 Пространство состояний

5.2.6 Интерфейсы для библиотек обучения с подкреплением

5.3 Генерация и наборы карт

5.3.1 Случайные карты

5.3.2 Набор случайных сценариев

5.3.3 Набор карт для тестирования

5.3.4 Положения агентов и целей

5.3.5 Скоро сть работы среды

5.4 Базовые решения

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

Заключение

Список сокращений и условных обозначений

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

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

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

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

Введение

В настоящее время активно разрабатываются новые методы принятия решений в условиях неопределённости на основе моделей искусственного интеллекта (ИИ). В этом контексте особую роль играет обучение с подкреплением, которое демонстрирует высокую эффективность при решении сложных и практически значимых задач [8—10].

Особое внимание заслуживают задачи навигации из-за их сложности и разнообразия. Под навигацией здесь понимается планирование перемещения агента на основе наблюдений, таких как вид от первого лица или вид сверху. Такие условия требуют разработки новых алгоритмов, способных адаптироваться к изменениям, эффективно работать при частичной наблюдаемости и координировать действия множества агентов в одной системе. Однако многие существующие методы до сих пор сталкиваются с проблемами в таких условиях [11; 12]. К проблемам можно отнести низкую эффективность выборки при обучении, а также ограниченные возможности сред для многоагентных задач навигации. Классические методы [13] часто требуют полной информации о среде, испытывают трудности при её изменении и, как правило, адаптированы под конкретную задачу.

На протяжении длительного времени задачи одноагентной и многоагентной навигации решались с помощью классических методов планирования, таких как алгоритм Дейкстры [14] или А* [15]. Эти методы предполагают полное понимание системы и требуют полного графа для планирования. Однако у них есть ограничения: они не адаптивны, что затрудняет планирование при изменении структуры графа. Многие из них централизованы, что может вызвать проблемы с масштабируемостью при увеличении числа агентов. Несмотря на их эффективность в некоторых ситуациях, такие методы могут быть неэффективными в динамичных или сложных условиях, где граф постоянно меняется или требуется быстрая адаптация [16; 17].

Современные исследования в области навигации акцентируют внимание на сочетании машинного обучения с традиционными алгоритмами. Например, в работе [18] рассматривается применение свёрточных сетей для улучшения алгоритмов A*иD*. Работа [19] представляет дифференцируемый вариант А*, в

то время как [20] фокусируется на ЛР-трудных задачах с применением графовых нейронных сетей.

Применение методов обучения с подкреплением в сложных задачах, например таких, как робототехника или автономные транспортные средства, требуют учета больших пространств состояний и действий, высокой эффективности выборки и поддержания иерархических целей. Хотя есть работы, решающие эти задачи [21; 22], но они сильно уступают централизованным планировщикам, как в качестве, так и в скорости работы. Для применения методов обучения с подкреплением в реальных условиях требуются более сложные задачи и алгоритмы для их решения, включая сценарии, где среда меняется, или где агенты сталкиваются с новыми вызовами, такими как процедурно-генерируемые среды или ЗЛ-окружения, а также многоагентные задачи.

Опираясь на вышесказанное, была поставлена цель и задачи.

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

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

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

2. Разработать эффективные методы одноагентной навигации для сред с наблюдением от первого лица.

3. Предложить и разработать методы многоагентной навигации для частично наблюдаемых сред с видом сверху.

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

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

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

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

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

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

Практическая значимость

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

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

Метод обучения с подкреплением для задачи навигации агента в стохастической среде разработан в рамках проекта №075-15-2020-799 «Методы построения и моделирования сложных систем на основе интеллектуальных и суперкомпьютерных технологий, направленные на преодоление больших вызовов».

Методология и методы исследования. Разрабатываемые алгоритмы основываются на методах машинного обучения, теории графов, методах оптимизации и статистике. При создании алгоритмов применяется методология постепенного улучшения: каждый добавленный компонент проверяется на эффективность (например, архитектура нейронной сети или введение определенных элементов). Основным методом оценки эффективности представленных в работе подходов служит численный эксперимент. Для обеспечения статистической значимости сравнение алгоритмов проводится с учетом множественных запусков и различных сценариев. Несмотря на то, что эти запуски независимы, начальные условия для всех алгоритмов совпадают, гарантируя честное сравнение. В процессе разработки использовались библиотеки глубокого обучения Tensorflow 2 [23] и РуТог^ [24], в качестве метода оптимизации использовался стохастический градиентный спуск с

адаптивной оценкой моментов Adam [25]. Для реализации всех подходов был использован язык программирования Python3, а также множество открытых модулей, предоставляющих различные функции - от визуализации до библиотек обучения нейронных сетей. При проведении экспериментов применялся подход контейнеризации, позволяющий воспроизводить эксперименты на различных устройствах. Для этого был использован инструмент контейнеризации Docker. Для логирования результатов экспериментов применялась библиотека Wandb.

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

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

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

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

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

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

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

- «NeurIPS 2019», Thirty-third Conference on Neural Information Processing Systems, «Competition and Demonstration Track», 8-14 December, Vancouver

- «OpenTalks.AI 2020», Открытая конференция по искусственному интеллекту, 20-21 февраля, Москва

- «КИИ-2021», XIX Национальной конференции по искусственному интеллекту с международным участием, 11-16 октября, Таганрог

- «AIJ 2021» Международная конференция по искусственному интеллекту AI Journey, 10-12 ноября, Москва

- «ICAPS 2022», Thirty-second International Conference on Automated-Planning and Scheduling, «Planning and Reinforcement Learning workshop», 13 June, virtually

- «IJCAI 2023», Thirty-second International Joint Conference on Artificial Intelligence, «Planning and Reinforcement Learning workshop», 19-25 Aug, Macao

Личный вклад. В статье [1] автор лично разработал и реализовал структуру алгоритма иерархического обучения с подкреплением с использованием демонстраций. В работе [2] автор предложил метод постепенного уменьшения зависимости стратегии агента от экспертных данных. В работах [3; 4] автор представил и реализовал обучаемые подходы к задаче клеточной навигации, а также методики переключения между планировочной и обучаемой стратегиями, разработал среду и методологию тестирования алгоритмов. В работе [5] автором реализована обучаемая стратегия для достижения цели, а также метод тестирования алгоритмов. В работе [6], автором подготовлены разделы по обучаемым методам и средам для тестирования алгоритмов. Среда POGEMA и базовые решения на основе обучения, представленные в статье [7], разработаны лично автором.

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

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

- 8. Многоагентные системы и распределенный ИИ.

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

Публикации. Основные результаты по теме диссертации изложены в 6 печатных изданиях [1—6], 6 — в периодических научных журналах,

индексируемых Web of Science и Scopus, в том числе 4 из которых опубликованы в журналах первого квартиля и 2 в журналах второго квартиля.

Объем и структура работы. Диссертация состоит из введения, 5 глав, заключения. Полный объём диссертации составляет 146 страниц, включая 39 рисунков и 13 таблиц. Список литературы содержит 106 наименований.

Глава 1. Обучение с подкреплением в задачах навигации

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

1.1 Обучение с подкреплением

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

1.1.1 Марковский процесс принятия решений

Математически процесс взаимодействия агента со средой формулируется как конечный Марковский процесс принятия решений (МППР, MDP, Markov Decision Process), определяемый как кортеж (S, A, P, R, у), где

- S - множество состояний среды,

- A - множество возможных действий агента в среде,

- P - неизвестная для агента функция перехода P : S х S х A ^ [0,1], которая определяет вероятность Pr(si+i ,rt\s,at) перейти в состояние st+1 Е S, при выборе действия at Е A в состоянии st Е S,

- Я : 5 х А ^ [гшт,гтах] - функция вознаграждения определяет

вероятность Рт(г\в,а^ агентом получить вещественное вознаграждение Г € Я при выборе действия аг € А в состоянии st € - у (0 ^ у ^ 1) - дисконтирующий множитель, который определяет то,

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

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

Используя некоторую стратегию п(а^\st) для последовательного выбора действий, можно получить траекторию т = ...). Для любой

стратегии Q-функция (функция полезности) определяется как:

Данная функция представляет математическое ожидание дисконтированного суммарного вознаграждения. Цель агента - обучиться оптимальной стратегии п*, которая максимизирует Q-функцию (1.1) для каждого состояния s. Существует множество алгоритмов для поиска стратегии п. В данной работе используются два подхода, один из них основан на оценке функции полезности, а второй на оптимизации градиента стратегии.

(1.1)

1.1.2 Методы на основе функции полезности

Оптимальную функцию полезности Q*(s, а) в общем виде можно получить решением уравнения Беллмана [26]:

Q*(st,at) = E

R{st,at) + у У^ Pr(si+i\st,at) max Q*(sm, am)

' * n.t I 1

at+1

(1.2)

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

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

£(Q,st,at,rt,st+1) =

Q(st,at; 6) - (rt + у • maxQ(st+i,at+i; 0))

at+i

2

(1.3)

Оценка функции полезности, которая будет получена при минимизации данной функции потерь является смещенной, но хорошо зарекомендовала себя на практике [26]. Обновления весов сети происходит, как минимизация функции потерь:

6t+1 = arg min L(0t,st,at,rt,st+i), (1.4)

6

где rt вознаграждение и состояние st+i получены, при выполнении £-жадного действия at, которое выбирается с учетом текущих оценок полезности, зависящих от весов сети 6t через функцию Q.

Эта функция потерь была применена в методе DQN (Deep Q-Network), которая впервые позволила решать сложные задачи, с использованием изображения игровой среды в качестве исходных. Предложенный подход привлек множество исследователей, как практиков, так и теоретиков, к области обучения с подкреплением. Помимо описанной функции потерь было еще два основных компонента, которые позволили улучшить стабильность и эффективность подхода DQN: память прецедентов и целевая сеть.

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

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

L(6, St,at,rt, St+1, б target) = [Q(st, at, в)

- (rt + Y • max Q(st+i , am; 6target)

\ at+i

(1.5)

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

0к+1 = arg min ESuaurust+1~v [L(9fc, suat,ru st+i, 0target)] • (1.6)

e

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

2

1.1.3 Методы, на основе оптимизации градиента стратегии

Вторым классом алгоритмов являются методы оптимизации градиента стратегии. В отличие от методов, основанных на оценке функции полезности, методы градиента стратегии напрямую обучают стратегию, отображающую состояния в действия. Классическим примером такого алгоритма является подход Reinforce [26].

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

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

Одним из самых широко используемых алгоритмов типа актор-критик является метод оптимизации ближайшей стратегии [28] (PPO, Proximal Policy Optimization). Идея подхода состоит в том, чтобы избегать сильных изменений стратегии при её обновлении. Нейронная сеть данного алгоритма состоит из двух компонент: сети критика, параметризованная её весами ф. Входом сети является состояние s, а выходом - средняя полезность Vp(s); сеть актора, параметризованная весами 6, принимает на вход состояние среды и выдает на выход вероятности выбора каждого из действий. Обозначим n6(a|s), как вероятность выбора действия a в состоянии s, при стохастической стратегии п6.

Обучение стратегии методом PPO происходит с помощью суррогатной функции потерь, которая вводит явный штраф за сильное отклонение новой стратегии п6 от стратегии предыдущего шага обновления nold. Для этого считается отношение вероятностей выбора действия дП^ф) текущей стратегией и стратегией с предыдущего шага. Функция clip заставляет это значение быть в диапазоне (1 — е, 1 + е), где е - это небольшая положительная константа. Таким образом, функция потерь для обновления сети актора:

Lactor(s,a, 0, Gold) = min

Пв(йИ Ае (s,a),

^Gold W

(a Is) \

(1.7)

( Wals) , , \ . , Л

clip -—, 1 - e, 1 + e Ane (s, a)

Wid (als) )

где АПе (s, a) = Rt — Vv(s) - это функция преимущества, показывающая улучшение или ухудшение стратегии актора, относительно полученной на траектории отдаче Rt и предсказания полезности критика V9(s). Обучение сети критика происходит, используя следующую функцию потерь:

Г - I2

Lcritic(s, y,Rt)= Vp(s) — Rt , (1.8) где Rt - это дисконтированная отдача:

œ

Rt = rt + yrt+1 + Y2rt+2 + Y3rt+3 + ... = ^ Y rt+k. (1.9)

k=0

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

6^1 = а^шахЕ^пе, [£аЛог(5,а, 6к, 6ои)] , (1.10)

а к

6к

Сеть критика минимизирует ошибку оценки полезности по отдаче:

Фк+1 = argmin Es^n0old £critic(s, Фк, Rt) (1.11)

Фк o

Популярность алгоритма PPO не случайна. По сравнению с другими методами алгоритм является устойчивым к выбору гиперпараметров обучения. Есть множество успешных примеров его использования во многих областях, начиная от игровых сред: Atari [29], StarCraftMulti-Agent Challenge [30—32], Dota 2 [33], Minecraft [34]; продолжая робототехникой [35] и заканчивая дообучением больших языковых моделей [36; 37]. К недостаткам алгоритма можно отнести его низкую эффективность выборки. Другими словами, алгоритму необходимо большое количество шагов в среде, чтобы выйти на высокие результаты. Проблема решается ускорением генерации данных, а также распараллеливанием симуляционных сред.

1.1.4 Частичная наблюдаемость

В практических сценариях агенту зачастую не известно полное состояние среды, поэтому используется частично-наблюдаемый Марковский процесс принятия решений (POMDP, Partially Observable Markov Decision Process). В этом случае агент опирается на уверенность состояния (belief state), представляющую вероятностное распределение по всем возможных состояниям среды. POMDP определяется как: (S,O,A,P,R,у), где O(st,at, st+i) = Pr(o\st+i,at, st) -функция наблюдения, ot G O - наблюдение, то есть частичная информация, которую получает агент, когда среда находится в состоянии st.

В классическом MDP новое состояние среды не зависит от тех состояний, в которых она находилась на предыдущих шагах:

Pr(st+i\st,at) = Pr(st+i\si,ai,s2,a2,.. .,st,at). (1.12)

Однако в POMDP агент получает наблюдения, и это свойство нарушается. Вероятность нахождения агента в определенном состоянии st зависит от истории его наблюдений o1,...,ot. Обучение стратегии для решения POMDP является сложной задачей. Методы, созданные для таких сред, характеризуются высокой сложностью и низкой вычислительной эффективностью. Среди них можно выделить: Point-Based Value Iteration [38], Partially Observable Monte Carlo Planning [39].

На практике эффективны модификации нейросетевых методов обучения с подкреплением, которые учитывают историю наблюдений агента. Например, в DQN этой историей служат последние наблюдения среды, которые формируют стек кадров. Пусть у нас есть среда, которая возвращает наблюдения ot на каждом временном шаге t. Если необходимо включить последние N наблюдений в стек кадров, то стек кадров в момент времени t будет выглядеть следующим образом: stackt = [ot-N+1,ot-N+2, • • •, ot-i, ot]. Такой стек кадров теперь может использоваться, как вход для нейронной сети. Например, для визуальной среды, с размером входа M х M в качестве наблюдений, при использовании стека из N последних кадров, размерность входного слоя будет M х M х N. Такой подход направлен на решение проблемы частичной наблюдаемости. В средах, где динамика объектов влияет на стратегию агента, один текущий кадр не дает полного представления о движении, в то время как стек кадров может помочь агенту понимать динамику на непродолжительном интервале времени.

Альтернативным подходом для учета длительной истории является применение рекуррентных нейронных сетей. Расширенное наблюдение агента аппроксимируется скрытым состоянием рекуррентной нейронной сети ht, которое обусловлено предыдущим скрытым состоянием и текущим наблюдением: ht = f (ht-1,ot). Таким образом, стратегия агента зависит не только от текущего наблюдения, но и от скрытого состояния на предыдущем шаге: n(at|ot,ht-1). Процесс обучения в таком случае включает в себя фрагменты траектории ограниченной длины, обычно меньше 100 шагов. В обоих методах контекст, на основе которого агент принимает решения, ограничен искусственно.

1.1.5 Многоагентность

Актуальными являются задачи навигации для группы агентов, где им необходимо решать задачу навигации, избегая конфликтов. В таких случаях можно применить частично наблюдаемый многоагентный марковский процесс принятия решений [40; 41]: (S,A,U,P,R,O,у). На каждом временном шаге, каждый агент u £ U, где U = {1,... ,n}, выбирает действие au £ A, формируя совместное действие j £ J = Jn. Это совместное действие приводит среду к новому состоянию, согласно функции перехода P(s'|s, j) : S х J х S ^ [0,1]. После этого каждый агент получает индивидуальное наблюдение ou £ O на основе глобальной функции наблюдения O(s,a) : S х A ^ O, а также индивидуальное вознаграждение R(s,u, j) : S х U х J ^ R, основанное на текущем состоянии, конкретном агенте и совместном действии.

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

Алгоритм QMIX [42] можно рассматривать как адаптацию подхода DQN для многоагентных сред. Этот метод использует схему централизованного обучения и децентрализованного исполнения. В процессе обучения используется полное состояние среды, что позволяет обучить агентов поведению, максимизирующему общую полезность. Также существуют модификации данного алгоритма, которые улучшают сходимость [43] и позволяют применять его в средах с непрерывным пространством действий [44].

Алгоритм MAPPO [32] (Multi-Agent Proximal Policy Optimization) является адаптацией PPO для кооперативных многоагентных сред. Подобно QMIX, он использует схему централизованного обучения и децентрализованного исполнения. Во время обучения полное состояние среды подается на вход критику, тогда как для актор использует только наблюдение агента. Поскольку критик применяется исключительно при обучении, при применении подходу будет достаточно только наблюдений.

1.2 Обучение агентов решению задач навигации

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

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

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

8. Q-Transformer: Scalable Offline Reinforcement Learning via Autoregressive Q-Functions [Текст] / Y. Chebotar [и др.] // 7th Annual Conference on Robot Learning. — 2023.

9. Controlling commercial cooling systems using reinforcement learning [Текст] / J. Luo [и др.] // arXiv preprint arXiv:2211.07357. — 2022.

10. Discovering faster matrix multiplication algorithms with reinforcement learning [Текст] / A. Fawzi [и др.] // Nature. — 2022. — Т. 610, № 7930. — С. 47—53.

11. Minerl: A large-scale dataset of minecraft demonstrations [Текст] / W. H. Guss [и др.] // arXiv preprint arXiv:1907.13440. — 2019.

12. Measuring sample efficiency and generalization in reinforcement learning benchmarks: Neurips 2020 procgen benchmark [Текст] / S. Mohanty [и др.] // arXiv preprint arXiv:2103.15332. — 2021.

13. Stern, R. Multi-agent path finding-an overview [Текст] / R. Stern // Artificial Intelligence. — 2019. — С. 96—115.

14. A note on two problems in connexion with graphs [Текст] / E. W. Dijkstra [и др.] // Numerische mathematik. — 1959. — Т. 1, № 1. — С. 269—271.

15. 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. — Т. 4, № 2. — С. 100—107.

16. Flatland-rl: Multi-agent reinforcement learning on trains [Текст] / S. Mohanty [и др.] // arXiv preprint arXiv:2012.05893. — 2020.

17. Scalable rail planning and replanning: Winning the 2020 flatland challenge [Текст] / J. Li [и др.] // Proceedings of the International Conference on Automated Planning and Scheduling. Т. 31. — 2021. — С. 477—485.

18. Learning heuristic functions for mobile robot path planning using deep neural networks [Текст] / T. Takahashi [и др.] // Proceedings of the International Conference on Automated Planning and Scheduling. Т. 29. — 2019. — С. 764—772.

19. Path planning using neural A* search [Текст] / R. Yonetani [и др.] // International conference on machine learning. — PMLR. 2021. — С. 12029—12039.

20. Li, Z. Combinatorial optimization with graph convolutional networks and guided tree search [Текст] / Z. Li, Q. Chen, V. Koltun // Advances in neural information processing systems. — 2018. — Т. 31.

21. Emergent Tool Use From Multi-Agent Autocurricula [Текст] / B. Baker [и др.] // International Conference on Learning Representations. — 2019.

22. PRIMAL2: Pathfinding via reinforcement and imitation multi-agent learning-lifelong [Текст] / M. Damani [и др.] // IEEE Robotics and Automation Letters. — 2021. - Т. 6, № 2. - С. 2666-2673.

23. TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems [Текст] / Martin Abadi [и др.]. — 2015. — URL: https : / / www . tensorflow.org/ ; Software available fromtensorflow.org.

24. Pytorch: An imperative style, high-performance deep learning library [Текст] / A. Paszke [и др.] // Advances in neural information processing systems. — 2019. —Т. 32.

25. Kingma, D. P. Adam: A method for stochastic optimization [Текст] / D. P. Kingma, J. Ba // arXiv preprint arXiv:1412.6980. — 2014.

1. Forgetful experience replay in hierarchical reinforcement learning from expert demonstrations [Текст] / A. A. Skrynnik [и др.] // Knowledge-Based Systems. — 2021. — Т. 218. — С. 106844.

2. Hierarchical deep q-network from imperfect demonstrations in minecraft [Текст] / A. A. Skrynnik [и др.] // Cognitive Systems Research. — 2021. — Т. 65. — С. 74—78.

3. Pathfinding in stochastic environments: learning vs planning [Текст] / A. A. Skrynnik [и др.] // PeerJ Computer Science. — 2022. — Т. 8. — e1056.

4. When to Switch: Planning and Learning for Partially Observable Multi-Agent Pathfinding [Текст] / A. A. Skrynnik [и др.] // IEEE Transactions on Neural Networks and Learning Systems. — 2023.

5. Hybrid policy learning for multi-agent pathfinding [Текст] / A. A. Skrynnik [и др.] // IEEE Access. — 2021. — Т. 9. — С. 126034—126047.

6. Planning and learning in multi-agent path finding [Текст] / K. S. Yakovlev [и др.] // Doklady Mathematics. Т. 106. — Springer. 2022. — S79—S84.

7. POGEMA: Partially observable grid environment for multiple agents [Текст] / A. A. Skrynnik [и др.] // arXiv preprint arXiv:2206.10944. — 2022.

26. Sutton, R. S. Reinforcement learning: An introduction [Текст] / R. S. Sutton, A. G. Barto. — MIT press, 2018.

27. Rainbow: Combining improvements in deep reinforcement learning [Текст] / M. Hessel [и др.] // Thirty-second AAAI conference on artificial intelligence. — 2018.

28. Proximal policy optimization algorithms [Текст] / J. Schulman [и др.] // arXiv preprint arXiv:1707.06347. — 2017.

29. Exploration by random network distillation [Текст] / Y. Burda [и др.] // International Conference on Learning Representations. — 2018.

30. The StarCraft Multi-Agent Challenge [Текст] / M. Samvelyan [и др.] // CoRR. — 2019.-Т. abs/1902.04043.

31. SMACv2: An Improved Benchmark for Cooperative Multi-Agent Reinforcement Learning [Текст] / B. Ellis [и др.] // arXiv preprint arXiv:2212.07489.-2022.

32. The Surprising Effectiveness of MAPPO in Cooperative, Multi-Agent Games [Текст] / C. Yu [и др.] // CoRR. — 2021. — Т. abs/2103.01955. — arXiv: 2103. 01955. — URL: https://arxiv.org/abs/2103.01955.

33. Dota 2 with large scale deep reinforcement learning [Текст] / C. Berner [и др.] // arXiv preprint arXiv:1912.06680. — 2019.

34. Video pretraining (vpt): Learning to act by watching unlabeled online videos [Текст] / B. Baker [и др.] // Advances in Neural Information Processing Systems. - 2022. - Т. 35. - С. 24639-24654.

35. Learning dexterous in-hand manipulation [Текст] / O. M. Andrychowicz [и др.] // The International Journal of Robotics Research. — 2020. — Т. 39, № 1. — С. 3-20.

36. Learning to summarize with human feedback [Текст] / N. Stiennon [и др.] // Advances in Neural Information Processing Systems. — 2020. — Т. 33. — С. 3008-3021.

37. Training language models to follow instructions with human feedback [Текст] / L. Ouyang [и др.] // Advances in Neural Information Processing Systems. — 2022. — Т. 35. — С. 27730—27744.

38. Point-based value iteration: An anytime algorithm for POMDPs [Текст] / J. Pineau, G. Gordon, S. Thrun [и др.] // Ijcai. Т. 3. — 2003. — С. 1025—1032.

39. Silver, D. Monte-Carlo planning in large POMDPs [Текст] / D. Silver, J. Veness // Advances in neural information processing systems. — 2010. — Т. 23.

40. The complexity of decentralized control of Markov decision processes [Текст] / D. S. Bernstein [и др.] // Mathematics of operations research. — 2002. — Т. 27, № 4. — С. 819-840.

41. Kaelbling, L. P. Planning and acting in partially observable stochastic domains [Текст] / L. P. Kaelbling, M. L. Littman, A. R. Cassandra // Artificial intelligence. — 1998. — Т.101, № 1/2. — С. 99—134.

42. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning [Текст] / T. Rashid [и др.] // International conference on machine learning. — PMLR. 2018. — С. 4295—4304.

43. Weighted qmix: Expanding monotonic value function factorisation for deep multi-agent reinforcement learning [Текст] / T. Rashid [и др.] // Advances in neural information processing systems. — 2020. — Т. 33. — С. 10199—10210.

44. Facmac: Factored multi-agent centralised policy gradients [Текст] / B. Peng [и др.] // Advances in Neural Information Processing Systems. — 2021. — Т. 34. — С. 12208-12221.

45. Deep residual learning for image recognition [Текст] / K. He [и др.] // Proceedings of the IEEE conference on computer vision and pattern recognition. — 2016. — С. 770—778.

46. Impala: Scalable distributed deep-rl with importance weighted actor-learner architectures [Текст] / L. Espeholt [и др.] // International Conference on Machine Learning. — PMLR. 2018. — С. 1407—1416.

47. Dechter, R. Generalized best-first search strategies and the optimality of A [Текст] / R. Dechter, J. Pearl // Journal of the ACM (JACM). — 1985. — Т. 32, №3. —С. 505—536.

48. Stentz, A. The D* Algorithm for Real-Time Planning of Optimal Traverses. [Текст] : тех. отч. / A. Stentz ; Carnegie-Mellon Univ Pittsburgh Pa Robotics Inst. — 1994.

49. Koenig, S. Lifelong planning A* [Текст] / S. Koenig, M. Likhachev, D. Furcy // Artificial Intelligence. — 2004. — Т. 155, № 1. — С. 93—146.

50. Koenig, S. DA* lite [Текст] / S. Koenig, M. Likhachev // Proceedings of the 18th AAI Conference on Artificial Intelligence (AAAI 2002). — 2002. — С. 476-483.

51. Multi-agent pathfinding: Definitions, variants, and benchmarks [Текст] / R. Stern [и др.] // Twelfth Annual Symposium on Combinatorial Search. —

2019.

52. Conflict-based search for optimal multi-agent pathfinding [Текст] / G. Sharon [и др.] // Artificial Intelligence. — 2015. — Т. 219. — С. 40—66.

53. ICBS: Improved conflict-based search algorithm for multi-agent pathfinding [Текст] / E. Boyarski [и др.] // Twenty-Fourth International Joint Conference on Artificial Intelligence. — 2015.

54. Adding heuristics to conflict-based search for multi-agent path finding [Текст] / A. Felner [и др.] // Proceedings of the International Conference on Automated Planning and Scheduling. Т. 28. — 2018. — С. 83—87.

55. Silver, D. Cooperative pathfinding [Текст] / D. Silver // Proceedings of the aaai conference on artificial intelligence and interactive digital entertainment. Т.1. — 2005. — С. 117-122.

56. Reciprocal n-body collision avoidance [Текст] / J. v. d. Berg [и др.] // Robotics research. — Springer, 2011. — С. 3—19.

57. Differentiation of blackbox combinatorial solvers [Текст] / M. V. Pogancic [и др.] // International Conference on Learning Representations. — 2020.

58. Panov, A. I. Grid path planning with deep reinforcement learning: Preliminary results [Текст] / A. I. Panov, K. S. Yakovlev, R. Suvorov // Procedia computer science. — 2018. — Т. 123. — С. 347—353.

59. Leveraging procedural generation to benchmark reinforcement learning [Текст] / K. Cobbe [и др.] // International conference on machine learning. — PMLR.

2020. - С. 2048-2056.

60. Minigrid & Miniworld: Modular & Customizable Reinforcement Learning Environments for Goal-Oriented Tasks [Текст] / M. Chevalier-Boisvert [и др.] // arXiv preprint arXiv:2306.13831. — 2023.

61. Hafner, D. Benchmarking the Spectrum of Agent Capabilities [Текст] / D. Hafner // International Conference on Learning Representations. — 2021.

62. Mastering Atari with Discrete World Models [Текст] / D. Hafner [и др.] // International Conference on Learning Representations. — 2020.

63. Habitat: A platform for embodied ai research [Текст] / M. Savva [и др.] // Proceedings of the IEEE/CVF international conference on computer vision. — 2019. — С. 9339-9347.

64. Making efficient use of demonstrations to solve hard exploration problems [Текст] / C. Gulcehre [и др.] // International conference on learning representations. — 2019.

65. Primal: Pathfinding via reinforcement and imitation multi-agent learning [Текст] / G. Sartoretti [и др.] // IEEE Robotics and Automation Letters. — 2019. - Т. 4, № 3. - С. 2378-2385.

66. Ferner, C. ODrM* optimal multirobot path planning in low dimensional search spaces [Текст] / C. Ferner, G. Wagner, H. Choset // 2013 IEEE International Conference on Robotics and Automation. — IEEE. 2013. — С. 3854—3859.

67. Asynchronous methods for deep reinforcement learning [Текст] / V. Mnih [и др.] // International conference on machine learning. — PMLR. 2016. — С. 1928-1937.

68. Simonyan, K. Very deep convolutional networks for large-scale image recognition [Текст] / K. Simonyan, A. Zisserman // arXiv preprint arXiv:1409.1556. — 2014.

69. Hochreiter, S. Long short-term memory [Текст] / S. Hochreiter, J. Schmidhuber // Neural computation. — 1997. — Т. 9, № 8. — С. 1735—1780.

70. Multi-agent path finding with prioritized communication learning [Текст] / W. Li [и др.] // 2022 International Conference on Robotics and Automation (ICRA). — IEEE. 2022. - С. 10695-10701.

71. Mobile robot path planning in dynamic environments through globally guided reinforcement learning [Текст] / B. Wang [и др.] // IEEE Robotics and Automation Letters. — 2020. — Т. 5, № 4. — С. 6932—6939.

72. Mapper: Multi-agent path planning with evolutionary reinforcement learning in mixed dynamic environments [Текст] / Z. Liu [и др.] // 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). — IEEE. 2020. — С. 11748-11754.

73. Li, B. Multi-robot path planning method based on prior knowledge and Q-learning algorithms [Текст] / B. Li, H. Liang // Journal of Physics: Conference Series. Т. 1624. — IOP Publishing. 2020. — С. 042008.

74. Multi-robot path planning method using reinforcement learning [Текст] / H. Bae [и др.] // Applied sciences. — 2019. — Т. 9, № 15. — С. 3057.

75. Zhi, /.Learning to herd agents amongst obstacles: Training robust shepherding behaviors using deep reinforcement learning [Текст] / J. Zhi, J.-M. Lien // IEEE Robotics and Automation Letters. — 2021. — Т. 6, № 2. — С. 4163—4168.

76. Meerza, S. I. A. Q-learning based particle swarm optimization algorithm for optimal path planning of swarm of mobile robots [Текст] / S. I. A. Meerza, M. Islam, M. M. Uzzal // 2019 1st international conference on advances in science, engineering and robotics technology (ICASERT). — IEEE. 2019. — С. 1-5.

77. Wesselhoft, M. Controlling fleets of autonomous mobile robots with reinforcement learning: a brief survey [Текст] / M. Wesselhoft, J. Hinckeldeyn, J. Kreutzfeldt // Robotics. - 2022. — Т. 11, № 5. - С. 85.

78. Human-level performance in 3D multiplayer games with population-based reinforcement learning [Текст] / M. Jaderberg [и др.] // Science. — 2019. — Т. 364, № 6443. - С. 859-865.

79. Simultaneous localization and mapping: A survey of current trends in autonomous driving [Текст] / G. Bresson [и др.] // IEEE Transactions on Intelligent Vehicles. — 2017. — Т. 2, № 3. — С. 194—220.

80. Mastering chess and shogi by self-play with a general reinforcement learning algorithm [Текст] /D. Silver [и др.] // arXiv preprint arXiv:1712.01815. — 2017.

81. Sample factory: Egocentric 3d control from pixels at 100000 fps with asynchronous reinforcement learning [Текст] / A. Petrenko [и др.] // International Conference on Machine Learning. — PMLR. 2020. — С. 7652-7662.

82. Sturtevant, N. R. Benchmarks for grid-based pathfinding [Текст] / N. R. Sturtevant // IEEE Transactions on Computational Intelligence and AI in Games. - 2012. - Т. 4, № 2. - С. 144-148.

83. The Malmo Platform for Artificial Intelligence Experimentation. [Текст] / M. Johnson [и др.] // Ijcai. — Citeseer. 2016. — С. 4246-4247.

84. Mastering atari, go, chess and shogi by planning with a learned model [Текст] / J. Schrittwieser [и др.] // Nature. — 2020. — Т. 588, № 7839. — С. 604—609.

85. Grandmaster level in StarCraft II using multi-agent reinforcement learning [Текст] / O. Vinyals [и др.] // Nature. - 2019. - Т. 575, № 7782. - С. 350-354.

86. Sutton, R. S. Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning [Текст] /R. S. Sutton, D. Precup, S. Singh// Artificial intelligence. — 1999. — Т. 112, № 1/2. — С. 181—211.

87. Deep q-learning from demonstrations [Текст] / T. Hester [и др.] // Proceedings of the AAAI Conference on Artificial Intelligence. Т. 32. — 2018.

88. Playing Atari with Deep Reinforcement Learning [Текст] / V. Mnih [и др.] // arXiv: 1312.5602.— 2013. —С. 1—9.— arXiv: 1312.5602.—URL: http:

//arxiv.org/abs/1312.5602.

89. Simonyan, K. Deep inside convolutional networks: Visualising image classification models and saliency maps [Текст] / K. Simonyan, A. Vedaldi, A. Zisserman // arXiv preprint arXiv:1312.6034. — 2013.

90. Population based training of neural networks [Текст] / M. Jaderberg [и др.] // arXiv preprint arXiv:1711.09846. — 2017.

91. A Survey on Population-Based Deep Reinforcement Learning [Текст] / W. Long [и др.] // Mathematics. - 2023. - Т.11, № 10. - С. 2234.

92. Empirical evaluation of gated recurrent neural networks on sequence modeling [Текст] / J. Chung [и др.] // arXiv preprint arXiv:1412.3555. — 2014.

93. Learning to run a power network challenge for training topology controllers [Текст] / A. Marot [и др.] // Electric Power Systems Research. — 2020. — Т. 189. — С. 106635.

94. Optimizing industrial hvac systems with hierarchical reinforcement learning [Текст] / W. Wong [и др.] // arXiv preprint arXiv:2209.08112. — 2022.

95. Magent: A many-agent reinforcement learning platform for artificial collective intelligence [Текст] / L. Zheng [и др.] // Proceedings of the AAAI conference on artificial intelligence. Т. 32. — 2018.

96. Deepmind lab2d [Текст] / C. Beattie [и др.] // arXiv preprint arXiv:2011.07027. — 2020.

97. Bamford, C. Griddly: A platform for AI research in games [Текст] / C. Bamford // Software Impacts. — 2021. — Т. 8. — С. 100066.

98. Scalable evaluation of multi-agent reinforcement learning with melting pot [Текст] / J. Z. Leibo [и др.] // International Conference on Machine Learning. — PMLR. 2021. - С. 6187-6199.

99. VMAS: A Vectorized Multi-Agent Simulator for Collective Robot Learning [Текст] / M. Bettini [и др.] // arXiv preprint arXiv:2207.03530. — 2022.

100. Starcraft ii: A new challenge for reinforcement learning [Текст] / O. Vinyals [и др.] // arXiv preprint arXiv:1708.04782. — 2017.

101. Openaigym [Текст] / G. Brockman [и др.] // arXiv preprint arXiv:1606.01540. — 2016.

102. Pettingzoo: Gym for multi-agent reinforcement learning [Текст] / J. Terry [и др.] // Advances in Neural Information Processing Systems. — 2021. — Т. 34. — С. 15032-15043.

103. PRIMAL 2 : Pathfinding Via Reinforcement and Imitation Multi-Agent Learning-Lifelong. [Текст] / D. Mehul [и др.] // IEEE Robotics and Automation Letters. — 2021. - Т. 6, № 2. - С. 2666-2673.

104. Value-decomposition networks for cooperative multi-agent learning [Текст] / P. Sunehag [и др.] // arXiv preprint arXiv:1706.05296. — 2017. — URL:

https://arxiv.org/abs/1706.05296.

105. Tan, M. Multi-agent reinforcement learning: Independent vs. cooperative agents [Текст] / M. Tan // Proceedings of the tenth international conference on machine learning. — 1993. — С. 330—337.

106. Mastering diverse domains through world models [Текст] / D. Hafner [и др.] // arXiv preprint arXiv:2301.04104. — 2023.

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

2.1 Примеры проблем, связанные с поиском пути в стохастических средах. Верхний ряд: робот с неограниченным обзором застрял в колебательном цикле, из-за блокировки/разблокировки одной клетки карты (что может соответствовать открытию/закрытию двери людьми). Нижний ряд: из-за частичной наблюдаемости робот не знает, что ранее заблокированная клетка становится проходимой (дверь открывается) и, таким образом, робот не может спланировать путь к цели. Оба случая могут быть успешно решены с помощью предложенной обучаемой стратегии. Данная стратегия, как показано эмпирически, учится такому поведению, как «ждать, пока исчезнет препятствие», «продолжать исследовать среду в поисках дополнительных вариантов достижения цели» и т.п............31

2.2 Примеры клеточных сред с различным количеством стохастических препятствий, представленных оранжевым цветом. Статические препятствия, которые агент не видел - прозрачны. Поле зрения

агента выделено красным квадратом....................34

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

2.4 Тепловая карта показывает количество блоков остатков и фильтров в них в процессе настройки архитектуры нейронной сети. Во всех экспериментах используется версия архитектуры с 60 фильтрами и 3 блоками остатков в качестве кодировщика в модели АРРО, так как она показала лучшую производительность в данном эксперименте по подбору гиперпараметров..........................43

2.5 Показатель успешности для алгоритмов A*, SA* и APPO для каждой карты из тестового набора по количеству стохастических препятствий. Заштрихованная область показывает доверительный интервал 95%.................................46

2.6 Сравнение решений, полученных с использованием SA* и APPO, проведено в зависимости от коллекции карт и количества стохастических препятствий. Точки на линиях SA* и APPO отмечают количество карт, на которых один из подходов показал лучшее качество решения по сравнению с другим. Линия Equal отображает долю экземпляров, на которых оба метода показали решения одинакового качества. Линия Failed, в свою очередь, указывает на долю экземпляров, которые не были успешно решены ни с помощью SA*, ни с помощью APPO..........................48

3.1 Примеры кадров из среды Minecraft..................... 50

3.2 Одна из возможных последовательностей получения ресурсов и предметов для решения задачи MineRL...................52

3.3 Обучение начинается с фазы имитации, на которой используются только экспертные демонстрации. При обучении стратегии для каждого навыка производится выборка мини-пакета данных из памяти прецедентов Ddgemo, принадлежащему текущему навыку g, и из дополнительной памяти прецедентов Dgxtra с обнуленными вознаграждениями, и флагом отключения маржинальной функции потерь Л2. Фаза объединения включает в себя взаимодействие агента с окружением, которое пополняет память прецедентов агента (показан зелёным). Выборка мини-пакета данных определяется скоростью "забывания" р = frg (t)...................... 56

3.4 Пример последовательности навыков для получения булыжника. ... 62

3.5 Карта заметности для имитационной стратегии, алгоритма DQfD и алгоритма ForgER...............................69

3.6 Результаты алгоритма ForgER с добавлением и отключением иерархической аугментации.........................70

3.7 Результаты агента при отключении различных компонентов функции потерь.....................................71

3.8 Влияние маржинальной функции потерь на результаты во время

фазы имитации................................72

3.9 Результаты алгоритма ForgER в среде LunarLander-v2 при отключении различных компонентов функции потерь...........73

3.10 а) Влияние функции "забывания" на значение функции потерь

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

3.11 Результаты алгоритмов с различными функциями "забывания".....74

4.1 Пример задачи многоагентной навигации в частично-наблюдаемой среде. Красный агент видит только часть среды вокруг себя. Красный круг, в правой части изображения, указывает целевое положение, к которому агент должен двигаться. Другие агенты показаны бирюзовым цветом..............................77

4.2 Архитектура нейронной сети для алгоритма EPOM объединяет кодировщик на основе ResNet и модули GRU для актора-критика. Сеть обрабатывает расширенные наблюдения из модуля Grid Memory, которые включают в себя координаты препятствий и агентов, а также цель или её проекцию. Кодировщик создаёт векторное представление, которое конкатенируется с нормализованными координатами текущего и целевого положений агента. Для нормализации этих координат значения ограничиваются

диапазоном [—64, 64] и делятся на 64....................80

4.3 Обработка наблюдений с помощью Grid Memory в рамках подхода EPOM. Данный модуль дополняет наблюдение агента препятствиями, обнаруженными на предыдущих шагах в среде, формируя расширенное наблюдение....................81

4.4 Общая схема подхода переключения между стратегиями. Пространство наблюдения среды состоит из двух матриц, кодирующих препятствия и агентов, а также относительного положения агента и цели. Эта информация подается в обучаемую стратегию EPOM и планировочную стратегию RePlan. Затем переключатель решает, какое действие предпринять на основе дополнительной информации. На рисунках (a), (b) и (c) показаны разные способы переключения между стратегиями. Эвристический переключатель (Heuristic Switcher) выбирает EPOM, когда в наблюдении достигается пороговое значение количества агентов. ASwitcher (Assistant Switcher) передает управление EPOM, когда планировочная стратегия не может найти путь или обнаруживает цикл. В обучаемом переключателе (Learnable Switcher) используются две дополнительные нейронные сети, которые оценивают полезность каждого из подходов по текущему наблюдению, и жадно выбирают лучший....................................83

4.5 a) Соотношение успешных эпизодов (CSR), (b) соотношение успешных эпизодов по каждому из агентов (ISR), (с) длительность эпизода и (d) использование EPOM для каждого числа агентов, усредненное по всем оцениваемым случаям. Заштрихованная область показывает доверительный интервал 95%.................88

4.6 Сравнение алгоритмов на картах 20 х 20, взятых из репозитория PICO. Основное отличие между этими картами заключается в рассматриваемой плотности препятствий: 0%, 10%, 20% и 30%. Карты с плотностью 0% довольно просты, и все алгоритмы показывают на них хорошие результаты. Для карт с более высокой плотностью наилучшие результаты показывают подходы с переключением стратегий. Заштрихованная область показывает доверительный интервал 95%........................91

4.7 Сравнение алгоритмов на картах mazes. Coopérative A* предоставлен полный доступ к состоянию среды, поэтому он показывает лучшие результаты и решает все сценарии. Лучший алгоритм среди тех, которые работают в рамках частичной наблюдаемости, - это ASwitcher. Заштрихованная область показывает доверительные интервалы 95%................................92

4.8 График (a) показывает, что в экспериментах на карте склада EPOM по средней пропускной способности близок к лучшему комбинированному алгоритму ASwitcher. На графике (b) видно, что количество шагов в секунду остается постоянным даже при увеличении числа агентов. Кроме того, скорость работы алгоритма ASwitcher увеличивается с ростом числа агентов, поскольку EPOM используется чаще..............................93

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

ISR. Заштрихованная область показывает доверительный интервал 95%. 95

4.10 Эффект модуля Grid Memory для задач навигации в одноагентных заданиях. Заштрихованная область показывает доверительный интервал 95%. Использование Grid Memory позволяет агенту достигать более высокого соотношения успешных эпизодов (а), а

также решать сценарии быстрее (b).....................96

4.11 (a) Результаты алгоритма EPOM с различным радиусом наблюдения, а также при отключении рекуррентной памяти (RNN). Заштрихованная область показывает доверительный интервал 95%. (b) Визуализация различных радиусов наблюдения на карте Lifelong Warehouse...................................97

5.1 Пример задачи в среде POGEMA. Агент, для которого строится путь, обозначен красным кругом, его цель - белый круг с красной границей, его зона наблюдения - квадрат с красной границей. Статические препятствия показаны серым цветом, а другие агенты -бирюзовым. Каждый из агентов является децентрализованным, видит лишь ограниченную информацию вокруг себя, а также не может общаться с другими агентами....................99

5.2 Примеры задач одноагентной навигации в лабиринте в среде Procgen Maze. На рисунке a) показано визуальное наблюдение агента (т.е. те данные, которые агент получает на вход) для простой среды. На рисунках b), c), d) показана визуализация в привычном для человека формате. Среды расположены в порядке их сложности. В последнем случае среда является частично-наблюдаемой для агента, и ему нужно запоминать предыдущие наблюдения, чтобы успешно её

решить.....................................100

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

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

5.5 Пример сценария, когда агенты после достижения своей цели получают новую. Красный агент достигает своей цели и получает

новую, и отходит чтобы пропустить синего агента. Эпизод не завершён. 106 5.6 Пример сценария с кооперативным завершением эпизода. Красный агент пропускает синего, а затем оба агента одновременно достигают

своих целей. В этом случае эпизод завершается досрочно........107

5.7 Пространство наблюдения POGEMA для алгоритмов обучения с подкреплением. Пространство наблюдения состоит из трех матриц, соответствующих препятствиям, другим агентам и цели или ее проекции....................................108

5.8 Примеры карт 16 х 16 с различной плотностью препятствий. При плотности 60% карта распадается на несколько компонент связности. . 111

5.9 Примеры конфигураций случайных карт для размера 16 х 16 и

разной сложности, зависящей от плотности агентов............111

5.10 Примеры карт для тестирования алгоритмов. Помимо случайных карт в набор вошли карты улиц, лабиринты, карты из игр StarCraft II

и Warcraft III..................................113

5.11 Результаты обучения алгоритмов QMIX [42], VDN [104] и IQL [105]

на карте ExtraHard8x8............................119

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

1 Гиперпараметры обучаемого подхода...................42

2 Усредненные результаты алгоритмов А* SA*, и АРРО; агрегированные по всем тестовым картам. Выделенные значения показывают лучший результат........................45

3 Функция вознаграждения в среде МтеЯЕ.................53

4 Пространство действий в среде МтвЯЬ................... 53

5 Дискретизация словаря действий, используемая при выполнении

всех навыков. Для перевода гибридных действий эксперта, каждое

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

6 Последовательность навыков для получения железной кирки, полученная по экспертной траектории...................63

7 Последовательность навыков для получения алмаза, составленная экспертом...................................64

8 Параметры обучения.............................66

9 Результаты применения алгоритмов на 1000 тестовых эпизодах. Для каждого предмета указано соотношение успешных эпизодов, в которых предмет был добыт, к общему числу эпизодов. В первой колонке показаны результаты лучшего решения в соревновании NeurlPS 2019 MineRL Diamond, которое использовало ту же версию среды. Алгоритм ForgER (expert) смог получить один алмаз за 1000

эпизодов....................................68

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

для каждой карты и числа агентов...................... 87

11 Встроенные случайные конфигурации среды POGEMA..........113

12 Скорость работы среды POGEMA для разных сценариев и разного количества агентов на карте.........................118

13 Процент успешно решенных задач планировщиком на базе А*. GA -

жадные действия. FL - обнаружение циклов................119