МетодЫ Планирования Совокупности Траекторий для Коалиции интеллектуальных агентов
Российский университет дружбы народов, *****@***com
В работе представлен аналитический обзор наиболее распространенных методов планирования совокупности траекторий для коалиции интеллектуальных агентов.
Ключевые слова: планирование траектории, поиск пути, мультиагентное планирование
Введение
Задача планирования траектории в искусственном интеллекте обычно рассматривается как задача поиска пути на взвешенном графе. В отличие от планирования траектории для отдельного агента, где сложность задачи зависит лишь от размера графа, сложность задачи планирования траекторий для множества агентов в большей степени зависит от числа агентов. Использование классического алгоритма A*[1] при планировании траекторий для множества агентов приведет к тому, что на каждой итерации алгоритма будет порождаться Mn новых состояний, где M – количество возможных переходов из текущего состояния, n – количество агентов. То есть сложность алгоритма A* экспоненциально зависит от числа агентов, что делает его неприменимым на практике, когда количество агентов велико. В связи с этим для решения задачи планирования совокупности траекторий для коалиции интеллектуальных агентов предлагаются специализированные алгоритмы.
Аналитический обзор
Алгоритмы планирования траекторий для множества агентов можно разделить на две группы. В первую группу входят алгоритмы, принцип работы которых основывается на централизованном подходе к решению задачи, то есть имеется один глобальный планировщик, который строит траектории для всех агентов и при этом учитывает положения в пространстве каждого из них в каждый момент времени. Подобные алгоритмы теоретически являются полными, то есть гарантируют нахождение решения, если оно существует, и могут быть оптимальными, то есть гарантируют, что построенные траектории будут кратчайшими.
Одним из наиболее известных и эффективных оптимальных алгоритмов, использующих централизованный подход является алгоритм OD+ID описанный в работе [2]. В основе алгоритма OD+ID лежит алгоритм A*. Особенностью алгоритма OD+ID является использование методов, позволяющих ускорить процесс и сократить пространство поиска. Первый – Independence Detection(ID) разбивает исходную задачу на несколько подзадач, но при этом не нарушает оптимальность искомого решения. Второй метод – Operator Decomposition(OD) применяется для того чтобы сократить пространство поиска. Вместо того чтобы перемещать всех агентов одновременно, агенты движутся по очереди, тем самым уменьшая количество различных состояний с Mn до M*n.
Однако оптимальные алгоритмы остаются слишком ресурсоемкими и не применимыми к практическим задачам, где количество агентов велико, а пространство поиска состоит из десятков и даже сотен тысяч состояний. Существуют алгоритмы, которые также используют централизованный подход и являются полными, но при этом не гарантируют нахождение оптимального решения.
Первый подобный алгоритм был предложен в работе [3]. Принцип работы этого алгоритма основан на преобразовании исходного графа к дереву, элементами которого являются части исходного графа, которые составляют цикл. Ребрами дерева являются «узкие места» исходного графа, которые не образуют циклы. Данный алгоритм работает за полиномиальное время и при этом гарантирует, что количество шагов не превысит O(n3), где n-количество вершин в графе. Однако на практике он оказался слишком сложным и неэффективным.
К этой же группе относится алгоритм OA(Optimal Anytime)[4], предложенный авторами алгоритма OD+ID. Принцип его работы схож с алгоритмом OD+ID. Разница заключается в том, что при обнаружении конфликтов агенты не пытаются построить совместные оптимальные траектории. Они также объединяются в группу, но строят свои пути, учитывая других агентов лишь как движущиеся препятствия. Такой подход работает быстрее, но не гарантирует, что найденные пути являются кратчайшими.
Push and Swap - еще один алгоритм, использующий централизованный подход, но при этом не являющийся оптимальным, описан в работе [5]. Целью алгоритма Push and Swap является нахождение субоптимального решения за полиномиальное время. Push and Swap является полным для тех задач, где количество вершин в графе больше чем количество агентов по крайней мере на 2. Алгоритм использует две операции – Push и Swap. С помощью операции Push агенты движутся к своей цели до тех пор, пока это возможно. Операция Swap позволяет поменять местами двух агентов, при этом, не изменяя положение всех остальных агентов (см. Рис.1).
Рис.1 Принцип работы операции Swap.
Алгоритмы второй группы используют децентрализованный подход. В основе этих алгоритмов лежит принцип декомпозиции, который заключается в разбиении исходной задачи на несколько более простых задач. Алгоритмы использующие децентрализованный подход вычислительно более эффективны, но не гарантирует нахождение оптимального решения и не являются полными.
Одним из первых и наиболее применимых на практике алгоритмов, использующих децентрализованный подход, является алгоритм LRA*(Local Repair A*), предложенный в работе[6]. Алгоритм работает в два этапа. На первом этапе каждый агент находит путь, используя алгоритм A*, при этом игнорируя всех остальных агентов. На втором этапе агенты движутся по построенным траекториям до тех пор, пока не возникнет конфликт. Всякий раз, когда агент не может пройти дальше из-за того, что впереди находится другой агент, происходит перерасчет найденного пути. Однако из-за того, что каждый агент независимо перепланирует свою траекторию, это приводит к возникновению новых конфликтов и в итоге могут возникнуть циклические конфликты, неразрешимые подобным подходом.
Позднее появились более совершенные методы планирования траектории для множества агентов, использующие децентрализованный подход. Например, алгоритм WHCA*(Windowed Hierarchical Cooperative A*), описанный в работе [7]. Как и LRA*, алгоритм WHCA* работает в два этапа и для планирования траектории использует алгоритм A*. Ускорение работы алгоритма происходит за счет того, что поиск пути для каждого агента происходит в «окне» - абстрактной области карты размером w*w. Постепенно «окно» сдвигается в сторону цели. В алгоритме используется 3х-мерная пространственно-временная таблица, в которой хранятся позиции всех агентов в каждый момент времени (см. Рис.2).
Рис.2 Пример работы алгоритма WHCA*.
Использование подобной таблицы помогает избежать конфликтов, когда два агента пытаются занять одну и ту же вершину, но при этом не отслеживает конфликты, когда агенты пытаются пройти сквозь друг друга. Данный алгоритм решает большее количество заданий, чем LRA*, но при этом требует дополнительных затрат памяти на хранение 3х-мерной таблицы.
Выводы
Существующие алгоритмы планирования совокупности траекторий для коалиции интеллектуальных агентов используют либо централизованный, либо децентрализованный подход к решению задачи. Алгоритмы, использующие централизованный подход, могут обладать такими важными свойствами как полнота и оптимальность. Однако с вычислительной точки зрения алгоритмы, использующие децентрализованный подход, являются значительно более эффективными, что обуславливает их большую применимость в практических задачах.
Работа выполнена при поддержке РФФИ в рамках научного проекта № 15-37-20893.
Литература
1. Hart, P., Nilsson, N., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100– 107.
2. Standley., T. Finding optimal solutions to cooperative pathfinding problems. In AAAI, 2010.
3. Kornhauser, D., Miller, G., & Spirakis, P. (1984). Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. In Proceedings of the 25th Annual Symposium on Foundations of Computer Science, FOCS, pp. 241–250.
4. Standley, T., & Korf, R. (2011). Complete algorithms for cooperative pathfinding problems. In Proceedings of the Twenty-Second international joint conference on Artificial Intelligence – Volume One, IJCAI, pp. 668–673. AAAI Press.
5. Luna, R., & Bekris, K. E. (2011b). Push and Swap: fast cooperative path-finding with completeness guarantees. In Proceedings of the Twenty-Second international joint conference on Artificial Intelligence – Volume One, IJCAI, pp. 294–300. AAAI Press.
6. Zelinsky, A. 1992. A mobile robot exploration algorithm. IEEE Transactions on Robotics and Automation 8(6).
7. Silver, D. (2005). Cooperative pathfinding. In Proceedings of the 1st Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE, pp. 117–122.
Pathplanning methods for coalitions of INTELLIGENT agents
Andreychuk A.
Peoples’ Friendship University of Russia, *****@***com
This paper presents an analytical review of the existing widespread pathplanning methods for coalitions of intelligent agents.
Кеу words: pathplanning, path searching, multiagent pathplanning.
