Мультиагентный поиск пути

Пример многоагентного поиска пути в среде сетки.

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

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

Формализация задачи

Элементы классического MAPF проблема в следующем:

• набор $A=\{1,2,...,k\}$ из $k$ агенты;
• неориентированный граф $G=(V,E)$, где $V$ - это набор узлов, и $E$ это набор ребер. Узлы представляют возможные местоположения агентов, а дуги — возможные связи между такими позициями;
• карта $s:A\to V$ который связывает каждого агента с его отправной точкой;
• карта $t:A\to V$ который связывает каждого агента с его целевой точкой.

Предполагается, что время дискретно и что каждый агент может выполнить одно действие на каждом временном шаге. Существует два возможных типа действий: действие ожидания, при котором агент остается в своем узле, и действие перемещения, позволяющее агенту переместиться в соседний узел. Действие формализуется как функция $a:V\to V$, это означает, что $a(v)=v'$ представляет собой действие перехода от $v$ к $v'$ если $v'$ находится рядом с $v$ и отличается от $v'$или остаться в узле $v$ если $v=v'$.

Агенты выполняют последовательность действий, чтобы добраться от начальной точки до целевого местоположения. Последовательность действий, выполняемых агентом $i$ обозначается $\pi _{i}=(a_{1},a_{2},...,a_{n})$ и называется планом. Если агент $i$ начинается с его местоположения $s(i)$ и прибывает в целевое место $t(i)$ план выполнения $\pi _{i}$, затем $\pi _{i}$ называется одноагентным планом для агента $i$. Допустимым решением проблемы MAPF является набор $k$ планы одного агента (по одному для каждого агента), так что планы не конфликтуют друг с другом. Как только агент достигнет своей цели, он может либо остаться в целевом месте, либо исчезнуть.

Типы столкновений

Чтобы иметь правильное решение проблемы MAPF, необходимо, чтобы одноагентные планы $k$ агенты не сталкиваются друг с другом. Данный план $\pi _{i}$, выражение $\pi _{i}[x]$ обозначает позицию агента $i$ после выполнения $x$ этапы плана $\pi _{i}$. Между двумя планами можно выделить пять различных типов коллизий. $\pi _{i}$ и $\pi _{j}$.

Типы конфликтов: (а) конфликт ребер, (б) конфликт вершин, (в) конфликт следования, (г) конфликт цикла и (д) конфликт перестановки.

• Конфликт вершин: между планами существует конфликт вершин. $\pi _{i}$ и $\pi _{j}$ когда два агента одновременно занимают одно и то же место. Формально конфликт вершин возникает, когда $\pi _{i}[x]=\pi _{j}[x]$.
• Конфликт ребер: конфликт ребер возникает всякий раз, когда два агента пересекают одно и то же ребро в одном и том же направлении в одно и то же время, т.е. $\pi _{i}[x]=\pi _{j}[x]$ и $\pi _{i}[x+1]=\pi _{j}[x+1]$. Если конфликты вершин не разрешены, то и конфликтов ребер не может быть.
• Последующий конфликт: следующий конфликт возникает, когда на определенном временном шаге агент занимает место, которое было занято другим агентом на предыдущем временном шаге. Математически следующий конфликт описывается как $\pi _{i}[x+1]=\pi _{j}[x]$.
• Конфликт циклов: конфликт циклов возникает всякий раз, когда набор агентов (минимум три) движутся так, как будто они вращаются в цикле. Это означает, что каждый агент занимает позицию, которую ранее занимал другой агент, на шаг вперед в цикле. Если последующие конфликты запрещены, то конфликты циклов не могут произойти.
• Конфликт обмена: конфликт обмена — это случай, когда два агента обмениваются своими позициями, проходя по одному и тому же ребру одновременно в двух разных направлениях. Это выражается как $\pi _{i}[x+1]=\pi _{j}[x]$ и $\pi _{j}[x+1]=\pi _{i}[x]$.

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

Целевые функции

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

• время потока: эта мера получается путем суммирования временных шагов, затраченных каждым агентом для достижения целевого местоположения. Формально оно равно $\sum _{i\in A}|\pi _{i}|$, где планы $\pi _{i},i\in A$ являются одноагентными планами без коллизий;
• makepan: количество временных шагов, необходимых для того, чтобы все агенты выполнили свои задачи, определяемые как $\max _{i\in A}|\pi _{i}|$, где $\pi _{i}$$,i\in A$ являются частью допустимого решения;
• максимизация достигнутых целей в заданный срок: цель состоит в том, чтобы найти действенное решение, которое максимизирует количество агентов, достигающих своей цели в заданный срок.

Алгоритмы

Для решения проблемы MAPF было предложено несколько алгоритмов. Проблема в том, что NP-трудно найти оптимальные решения по продолжительности изготовления или времени потока. также при рассмотрении плоских графов , или графики, похожие на сетки. Что касается ограниченных субоптимальных решений, показано, что NP-трудно найти оптимальное решение с коэффициентом субоптимальности, меньшим, чем ${\tfrac {4}{3}}$. Оптимальные решатели MAPF возвращают решения высокого качества, но их эффективность низкая. Вместо этого ограниченно-субоптимальные и субоптимальные решатели более эффективны, но их решения менее эффективны. Также машинного обучения . для решения проблемы MAPF были предложены подходы

Приоритетное планирование

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

Первым шагом является присвоение каждому агенту уникального номера. $\{1,2,...,k\}$ это соответствует приоритету, данному агенту. Затем, следуя порядку приоритетов, для каждого агента рассчитывается план достижения целевого местоположения. При планировании агенты должны избегать столкновений с путями других агентов с более высоким приоритетом, которые уже рассчитали свои планы.

Поиск решения проблемы MAPF в такой постановке соответствует задаче о кратчайшем пути в графе временного расширения. Граф расширения во времени — это график, учитывающий течение времени. Каждый узел состоит из двух записей $(v,t)$, где $v$ это имя узла и $t$ это шаг по времени. Каждый узел $(v,t)$ связан с узлами $(u,t+1)$ такой, что $u$ находится рядом с $v$ и $u$ не занят на временном шаге $t+1$.

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

MAPF

Можно выделить четыре различные категории оптимальных решателей MAPF:

• Расширения A* : алгоритмы этой категории используют модифицированные версии подхода A* .
• Поиск в дереве увеличения стоимости: предложена новая формализация задачи MAPF, включающая возрастающее дерево поиска и соответствующий алгоритм. Алгоритм состоит из двух уровней и основан на предположении, что правильное решение проблемы MAPF состоит из набора решений для отдельных агентов.
• Поиск на основе конфликта: этот алгоритм вычисляет пути, как при решении задач поиска пути с одним агентом, а затем постепенно добавляет ограничения, чтобы избежать коллизий.
• Программирование ограничений : При таком подходе проблемы MAPF преобразуются в набор ограничений, а затем решаются с использованием конкретных решателей ограничений, таких как SAT и решатели смешанного целочисленного программирования (MIP).

MAPF

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

Вариации

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

Анонимный MAPF

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

прием

Проблема MAPF не способна охватить некоторые аспекты реальных приложений. Например, на автоматизированных складах бывает, что роботам приходится выполнять несколько задач одну за другой. По этой причине предлагается расширенная версия MAPF, называемая Multi-Agent Pick-up and Delivery (MAPD). В настройке MAPD агенты должны выполнить поток задач, где каждая задача состоит из места получения и места доставки. При планировании выполнения задачи путь должен начинаться с текущего положения робота и заканчиваться в месте доставки задания, проходя через точку погрузки. MAPD считается «пожизненной» версией MAPF, в которой задачи поступают постепенно.

За пределами классического MAPF

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

Приложения

MAPF может применяться в нескольких реальных сценариях:

• Автоматизированные склады : складская логистика представляет собой основное промышленное применение MAPF. Показано, что автоматизация складов позволяет повысить уровень производительности.
• Операции в аэропортах. Алгоритмы MAPF можно использовать в переполненных аэропортах для координации буксирующих транспортных средств, перевозящих самолеты. Возможность оптимизировать такого рода проблемы также приносит пользу окружающей среде.
• Автономные мобильные сервисные роботы : сервисные роботы — это автоматизированные агенты, выполняющие опасные и повторяющиеся задачи для людей в непромышленной среде. Их главная цель – помощь людям.
• Видеоигры: полезность MAPF в таких условиях можно обнаружить, когда игроку приходится перемещать команду агентов в перегруженной среде видеоигры.

См. также

• Мультиагентные системы
• Мультиагентное планирование
• Поиск пути
• Задача о кратчайшем пути

Внешние ссылки

• MAPF.info