Методы и алгоритмы многоагентного планирования в непрерывном времени

05.03.2021
Антон Андрейчук, ассистент кафедры Информационных технологий, РУДН. Дата и время проведения мероприятия: 05.03.2021 в 16:00 - 17:00 Место: Online
Задача многоагентного планирования - это задача поиска совокупности неконфликтных траекторий для множества агентов, каждый из которых обладает собственным стартовым и целевым положением. Классическим подходом для решения этой задачи являются эвристические алгоритмы планирования, использующие в качестве модели пространства поиска графы специального вида. Большинство существующих алгоримтов, применимых к задаче многоагентного планирования, используют ряд допущений. В частности, считается, что время дискретно и все действия агентов имеют одинаковую продолжительность эквивалетнтную одному дискретному шагу времени. В данном докладе будет представлен алгоритм CCBS (Continuous Conflict Based Search), который не использует это допущение и позволяет агентам совершать действия произвольной продолжительности. Представленный алгоритм обладает свойством полноты, а также гарантирует нахождение оптимальных решений. Также будет представлена улучшенная версия алгоритма, I-CCBS (Improved Continuous Conflict Based Search), обладающая повышенной вычислительной эффективностью. Как показали результаты проведенных экспериментальных исследований, благодаря тому, что агенты могут совершать действия произвольной продолжительности, стоимость отыскиваемых решений в среднем может быть уменьшена вплоть до 20%.
Метки: #seminars