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

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

The paper considers the problem of finding a combination of collision-free trajectories for a set of agents capable of performing actions of arbitrary duration. To solve this problem, two bounded-suboptimal modifications of the continuous-time conflict-based search algorithm are proposed. The results of the carried out model experimental studies have demonstrated the high computational efficiency of the proposed modifications.