Boundaries of computational complexity and optimal cluster's quantity for controlled swarm in non-cooperative games

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