Russian Federation
Russian Federation
The organizational structure of a multi-agent system (MAS) is a set of roles and relationships of agents, com-ponents that control their behavior, as well as rules governing the interaction of system elements. The effectiveness of the MAS largely depends on the characteristics of the organizational structure used. Existing solutions in this area have a significant disadvantage, namely low adaptability to changes in environmental parameters or adjustment of the conditions of the task, which consists in the need to restart the procedure for synthesizing the organizational structure of the MAS. The problem of automatic optimization of the organizational structure of centralized MAS in the conditions of changed environmental parameters or the task is of particular relevance for centralized MAS with a strict hierarchical structure, whose agents can be divided into two classes – agents-managers, agents-subordinates. The subject of the study is the methods of synthesis of the organizational structure of the MAS. The aim of the work is to develop a method for optimizing the organizational structure of centralized MAS in automatic mode. To achieve this goal, the concepts of primary and secondary agent resources were introduced, based on a biogeographic algorithm, a method was developed that regulates the movement of subordinate agents between groups depending on the degree of attractiveness of the agent manager (depends on the sum of estimates of the effectiveness of subordinate agents managed by him, as well as on the distance from this subordinate agent). The developed method can find its practical application in the implementation of the following tasks: inspection or patrolling (protection) of infrastructure facilities by mobile robots, the implementation of artificial intelligence in computer games.
multi-agent system, organizational structure, group, agent, optimization, biogeographic algorithm
Введение
Теория многоагентных систем (МАС) является одним из важнейших направлений искусственного интеллекта. Значительная роль в ней отводится решению задачи синтеза (а также автоматической корректировки в процессе работы) организационной структуры МАС, обеспечивающей ее функционирование с максимальной производительностью.
В работах [1–5] для решения обозначенной задачи предлагаются подходы, основанные на применении генетических алгоритмов, динамического программирования, методов теории графов. Основным их недостатком является низкая адаптивность даже к незначительным изменениям параметров окружающей среды или корректировке условий поставленной задачи, которая заключается в необходимости повторного запуска процедуры синтеза организационной структуры МАС.
Таким образом, имеет место проблема автоматической оптимизации организационной структуры МАС в условиях изменившихся параметров окружающей среды или поставленной задачи. Целью данной работы является разработка методов решения обозначенной проблемы.
Постановка задачи и методы
Дано:
– S – МАС;
– X = {A, T} – множество входных парамет-
ров, где T – поставленная задача; A – множест-
во интеллектуальных агентов, A = {ai}, при
этом существует хотя бы одна пара агентов 
– множество технических характеристик агента ai, 
– множество технических характеристик агента ai+1
(т. е. агенты гетерогенные, т. к. их множества технических характеристик не совпадают, при этом под техническими характеристиками понимают тип и параметры транспортной платформы, вычислительной подсистемы, подсистемы машинного зрения, коммуникационной подсистемы, постоянного запоминающего устройства и т. д.), 
,
где N – число интеллектуальных агентов. Каждый агент ai обладает множеством ресурсов ,
– некоторый ресурс, которым обладает агент ai (под ресурсом понимается некоторая услуга, которую может предоставить агент, например сбор, обработка, хранение, передача данных), 
– свободный объем ресурса (выраженный в некоторых условных единицах), которым обладает агент ai в текущий момент времени t; 
– максимально возможный объем ресурса 
, которым может обладать агент ai, ,
;
– 
– множество внутренних параметров S, описывающих ее организационную структуру OS (совокупность ролей и связей агентов, компонентов, осуществляющих управление их поведением, а также правил, регламентирующих взаимодействие элементов системы [6]);
– Y – множество выходных параметров, описывающих результат выполнения множеством агентов A поставленной задачи T;
– E – множество параметров окружающей среды;
– Q = {t} – множество показателей эффективности системы, где t – время выполнения поставленной задачи T.
Таким образом, необходимо разработать метод M, предназначенный для оптимизации организационной структуры OS, при этом
M:{S, X, Z, Y, E, Q} → {∆t | ∆t > 0},
где 
– значение показателя t ∈ Q до применения метода M; ta – значение показателя t ∈ Q после применения метода M.
В рамках рассматриваемой задачи автоматической оптимизации организационной структуры централизованной МАС агенты в зависимости от роли могут быть разделены на две группы: агенты-менеджеры (множество Alead); агенты-подчиненные (множество Asub).
Для агентов-менеджеров выделим следующие типы ресурсов:
1. Первичный ресурс 
– множество ресурсов (вычислительные, коммуникационные ресурсы, постоянная память, оборудования для сбора данных об окружающей среде), которыми обладают агенты
, находящиеся в подчинении у агента-менеджера 
– некоторой группы Gk,
,
где 
– число агентов-подчиненных группы Gk. К числу первичных ресурсов в данном случае также относится опыт агентов-подчиненных 
, 
где 
– база знаний агента ai. При этом относительная величина первичного ресурса, которым обладает группа (подгруппа) Gk, может быть выражена следующей функцией:
где – объем ресурса типа type, которым обладает агент ai; 
– коэффициент важности ресурса типа 
.
2. Вторичный ресурс (
) – величина, отражающая эффективность действий агентов-подчиненных 
при решении задач Tj,
, (1)
где 
– функция эффективности агента-подчиненного ai при решении задачи (подзадачи) Tj, 
– число задач (подзадач), назначенных агентам-подчиненным группы Gk, 
– коэффициент затухания (реализует уменьшение значений функции 
с течением времени), 
– число групп, на которые разбито множество агентов системы S, t – некоторый интервал времени, 
.
Замечание: понятия первичный и вторичный ресурс группы (подгруппы) Gk тождественны понятиям первичный и вторичный ресурс агента-менеджера 
.
Цель любого агента-менеджера заключается в максимизации вторичного ресурса 
для ∀t:
(2)
Для выражения (2) имеют место следующие условия:
(3)
т. е. в случае роста первичного ресурса группы Gk (
) вероятность максимизации вторичного ресурса (
) также увеличивается,
. Таким образом, чем большим первичным ресурсом обладает агент 
, тем больше вероятность достижения им условия (2). При этом увеличение первичного ресурса возможно исключительно за счет роста числа агентов-подчиненных в группе (подгруппе). Следовательно, имеет место зависимость вторичного ресурса от величины первичного ресурса:
(4)
В случае с (4), чем большим первичным ресурсом обладает агент-менеджер, тем больше вероятность достижения (2), т. к. агенты-подчиненные, обладающие высокопроизводительной аппаратной составляющей, могут выполнять поставленные задачи с большей эффективностью.
Однако большое число агентов-подчиненных может также повлечь и уменьшение функции (1) за счет чрезмерной нагрузки на вычислительную и коммуникационную подсистемы агента-менеджера (агент-менеджер не сможет оперативно получать и обрабатывать входящие сообщения от агентов-подчиненных, а также генерировать и высылать ответные сообщения). Обозначенная зависимость величины вторичного ресурса от объема первичного ресурса иллюстрируется на рис. 1.
Таким образом, с учетом ситуации, представленной на рис. 1, можно утверждать о неполноте условия (3), которое должно быть скорректировано следующим образом:
где 
– значение аргумента, при котором величина 
достигает максимума, т. е.
где f соответствует (4).
Замечание: важную роль при формировании 
имеет способность агента-менеджера оптимально распределять задачи Tj между агентами-подчиненными таким образом, чтобы 
, где type – опыт агента-менеджера.
Таким образом, необходимость максимизации первичного и вторичного ресурсов должна побуждать агента-менеджера к вербовке агентов-подчиненных в свою группу. Однако важно и наличие факторов, побуждающих агентов-подчиненных к миграции, величина которых может зависеть от успешности действий агента-менеджера (т. е. у агентов-подчиненных должен быть стимул для перехода в группу к более успешному агенту-менеджеру). Следовательно, для агентов-подчиненных также необходимо ввести понятия первичный
и вторичный ресурс 
. В качестве первичного ресурса для агента-подчиненного могут выступать технические ресурсы агента-менеджера (прежде всего вычислительная и коммуникационная составляющие), а также его опыт, а в качестве вторичного – показатель эффективности самого агента-менеджера, который рассчитывается для каждой решаемой задачи. Таким образом, первичный ресурс находится в функциональной зависимости от технических ресурсов и опыта агента-менеджера:
,
где ai – агент-подчиненный,
– агент-менеджер, 
– объем ресурса типа type (включая опыт), которым обладает агент
– коэффициент важности ресурса типа type, 
При этом вторичный ресурс агента-подчиненного ai находится в функциональной зависимости от показателя его эффективности при решении назначенных ему задач:
, (5)
где 
– коэффициент затухания (реализует уменьшение значений 
с течением времени), 
t – некоторый интервал времени, 
,
Таким образом, цель любого агента-подчиненного заключается в следующем:
(6)
Для первичного и вторичного ресурсов агента-подчиненного также допустимо следующее соотношение:
(7)
В отличие от первичного и вторичного ресурсов агента-менеджера, в данном случае наличие соотношения (7) не столь очевидно, однако необходимо учитывать, что величина (5) складывается из двух составляющих: функции эффективности агента-подчиненного feffic, а также коэффициента затухания kdamp. Следовательно, в случае, если агент-менеджер aprim редко назначает задачи агенту-подчиненному ai, то 
, поскольку с течением времени kdamp → 0. Подобная ситуация (редкость получения заданий от агента-менеджера) возможна в двух случаях:
– в группе Gk достаточно агентов, и агент является невостребованным (вне зависимости от величины 
);
– вычислительная и коммуникационная системы агента-менеджера aprim перегружены, и он не успевает назначить задачу агенту ai (имеет место зависимость от величины 
, т. е. агент-менеджер, обладающий значительными аппаратными возможностями, может с высокой производительностью координировать действия большого числа агентов-подчиненных).
При этом в случае регулярного назначения задач на величину функции эффективности агента-подчиненного feffic влияет способность агента-менеджера правильно распределять задачи, которая, в свою очередь, находится в зависимости от его опыта, также учитываемая при расчете первичного ресурса .
Таким образом, можно утверждать, что соотношение (7) имеет место, однако его необходимо переписать со следующим ограничением:
где 
– пары агент – назначенная задача; 
– число сформированных пар 
– число отдельных задач, на которые была разложена задача T.
В [7] рассматривается алгоритм биогеографической оптимизации, основанный на моделировании процесса миграции животных и заселения ими различных территорий. Основная суть алгоритма заключается в анализе значения такого параметра, как привлекательность территории для миграции. При этом она может зависеть от таких характеристик, как климат, объем пищевых ресурсов, степень заселенности территории (чем больше видов проживает на этой территории, тем менее привлекательной для миграции она становится). Обозначенные принципы могут быть перенесены на рассматриваемую задачу оптимизации организационной структуры централизованных многоагентных систем в части обеспечения миграции агентов между группами. Для этого необходимо рассмотреть следующие понятия.
Eattr – показатель привлекательности агента-менеджера для агентов-подчиненных. Агенты-подчиненные заинтересованы в максимизации собственного вторичного ресурса, что возможно лишь при условии регулярного получения задач от агента-менеджера. При этом от опыта агента-менеджера зависит и выполнимость заданий, получаемых агентами-ведомыми (т. е. агент-менеджер распределяет задания, учитывая опыт, технические характеристики и местоположение агентов-подчинен-
ных). Следовательно, агенты-подчиненные, в случае неудовлетворения их потребности во вторичном ресурсе, будут стремиться перейти к более успешному агенту-менеджеру. Таким образом, имеем
. (8)
Рассмотрим применимость выражения (8) для нескольких ситуаций.
1. Число агентов-подчиненных в группе Gk настолько велико, что вычислительная и коммуникационная системы агента-менеджера 
работают с существенной задержкой, следовательно, агенты-подчиненные также получают новые задачи с задержкой, в связи с чем величина их вторичного ресурса падает (
) вопреки условию (6), что автоматически ведет к падению вторичного ресурса агента-менеджера, поскольку в выражении 
значение коэффициента затухания kdamp → 0 (т. е. чем меньше задач в единицу времени выполняют агенты-ведомые, тем меньше вторичный ресурс агента-менеджера). Таким образом, в ситуации, когда имеем 
. Падение привлекательности агента-менеджера (и возглавляемой им группы) побуждает агентов-подчиненных искать нового агента-менеджера:
(9)
где 
– новый (более привлекательный) агент-менеджер, 
; aprim – старый (утративший привлекательность) агент-менеджер;
– показатель привлекательности агента-менеджера aprim (и группы Gk); 
– показатель привлекательности агента-менеджера 
(и группы Gnew).
2. Агент-менеджер 
потерял способность к передвижению, сохранив при этом работоспособность вычислительной и коммуникационной системы. При этом значение 
не будет падать, пока отсутствие мобильности агента-менеджера не будет негативным образом отражаться на эффективности взаимодействия с агентами-подчиненными. Однако в случае территориального смещения зоны выполнения задач, переданных от лица, принимающего решения (либо от агента-менеджера вышестоящего уровня), будет наблюдаться некоторая задержка (или потеря) связи между агентами-менеджерами и агентами-подчиненными, которая в итоге приведет к возникновению ситуации (9). Однако здесь возникает проблема выбора новых агентов-менеджеров при равенстве их показателей привлекательности. Очевидно, что в этом случае выбор должен быть сделан в пользу ближайшего агента-менеджера, однако возможны ситуации, при которых доступ к нему может быть ограничен или невозможен (что в ближайшей перспективе может привести к повторению описываемой ситуации), например, в случае наличия некоторого физического препятствия (стена, пропасть, водная преграда и т. п.). Таким образом, более целесообразным видится определение меры близости на основании следующих критериев:
– прямое расстояние до агента-менеджера (без учета препятствий);
– возможность прокладки кратчайшего пути к агенту-менеджеру по разведанной территории (может быть построен путем применения эвристических алгоритмов, например алгоритма Дейкстры), при этом необходимо учитывать актуальность имеющейся информации.
Следовательно, показатель привлекательности агента-менеджера должен рассчитываться с точки зрения агента-подчиненного и может быть записан в следующем виде:
, (10)
где 
– коэффициент привлекательности агента-менеджера 
для агента-подчиненного ai; dshw – оценка кратчайшего пути между 
и ai.
Согласно [7], в рамках биогеографической оптимизации заселенные территории становятся менее привлекательными для миграции. Применительно к рассматриваемой ситуации перегруженный агент-менеджер должен обладать меньшей привлекательностью. Таким образом, перепишем формулу (8), добавив коэффициент «желания» агента-менеджера в привлечении новых агентов-подчиненных:
,
где
– показатель желания агента aprim принимать новых агентов-подчиненных, 
– ресурс type, которым обладает агент aprim, 
, Rst – свободный объем ресурса type в текущий момент времени t, Rsmax – максимально возможный объем ресурса type, Type – множество типов ресурсов, допустимых для агента aprim.
– показатель готовности агентов-подчиненных к миграции. Складывается из «недовольства» агентов-подчиненных получаемым вторичным ресурсом, а также из степени территориальной удаленности агента-подчиненного от агента-менеджера. Является вспомогательным показателем, величина которого обратно пропорциональна коэффициенту привлекательности агента-менеджера для агента-подчиненного:
.
Таким образом, метод обеспечения механизма миграции агентов между группами, основанный на применении алгоритма биогеографической оптимизации, сводится к выполнению следующих шагов.
Для агента-менеджера 
1. Получение задачи T от лица, принимающего решения (либо агента-менеджера более высокого уровня иерархии). Декомпозиция задачи T на отдельные задачи (подзадачи) Tj.
2. Назначение задач (подзадач) Tj агентам-подчиненным 
3. Анализ результатов выполнения задач (подзадач) Tj агентами-подчиненными 
– вычисление ∀ai значений функции feffic(ai, Tj) (функция определения показателя эффективности агента ai при решении задачи (подзадачи) Tj).
4. На основании feffic(ai, Tj) выполняется расчет (обновление) значений вторичного ресурса агента-менеджера 
в соответствии с (1).
5. Привлечение новых агентов-подчиненных 
, для групп, в которых они состоят, имеет место условие (9).
6. Повторение шагов 1–5 до достижения цели задачи, поставленной группе Gk (результат выполнения задачи 
).
Для агентов-подчиненных:
1. Получение задачи (подзадачи) Tj от агента-менеджера 
.
2. Расчет (обновление) вторичного ресурса 
по формуле (5).
3. Расчет показателя привлекательности агента-менеджера 
(см. (10)) и показателя готовности к миграции 
, то повторение шагов 1–3, иначе – выполнение оценки других агентов-менеджеров, переход к такому 
.
Результаты
Цель эксперимента: в результате выполнения компьютерного моделирования доказать эффективность применения предложенного метода оптимизации организационной структуры, реализованного на основе биогеографического алгоритма, на примере централизованных МАС, основанных на применении парадигмы обучения с подкреплением с выполнением обмена опытом между агентами. Рассматриваемая многоагентная система и алгоритмы ее работы описываются в [8–11].
Описание решаемой задачи: достижение всеми агентами некоторого целевого положения на ограниченной территории (с наличием препятствий).
Описание внешней среды: виртуальный лабиринт, сформированный в среде Microsoft Unity, при этом стены в лабиринте устанавливаются случайным образом. Размерность лабиринта – 150 × 150, при этом под единицей размерности понимается клетка, соответствующая одному квадратному блоку, применяемому для формирования стен (для оценки размеров блока можно учитывать тот факт, что толщина стены соответствует одному блоку). Структура лабиринта в ходе эксперимента меняется случайным образом (изменение типа одной случайной клетки происходит с периодичностью в 5 с).
Тип применяемых агентов: виртуальные агенты, имитирующие мобильных роботов на колесной транспортной платформе, оснащенных видеокамерой.
Число агентов: 26, при этом первоначальное формирование групп выполнялось на основании алгоритма, приводимого в [9, 10]. Случайное обездвижение агента-менеджера выполнялось в среднем на 14 с (продолжительность времени обездвижения также выбиралась случайным образом из интервала 5–20 с, максимальное число одновременно обездвиженных агентов-менеджеров – 2). Минимальное число агентов в группе – 3 (включая агента-менеджера).
Механизм выбора стартовых положений агентов: координаты стартовых положений генерируются случайным образом на каждой итерации.
Механизм выбора целевого состояния: координаты целевого состояния генерируются случайным образом на каждой итерации.
Критерий, позволяющий утверждать об успешном решении задачи: перемещение всех агентов в целевое состояние.
Число итераций (попыток): 200, при этом итерация считается выполненной в случае достижения критерия решения задачи.
Имитация загруженности вычислительной системы агента-менеджера: при назначении задач, а также при расчете подкреплений на каждого агента-подчиненного генерировалась задержка в 0,3 с.
Имитация задержки в канале связи в зависимости от расстояния: агент-подчиненный получал информационные сообщения от агента-менеджера с задержкой из расчета 0,2 с на 5 клеток прямого расстояния между ними.
Критерий оценки эффективности метода: время выполнения одной итерации.
Результаты, полученные в ходе эксперимента, в виде зависимости времени выхода всех агентов из лабиринта от номера итерации представлены на рис. 2.
Рис. 2. Результаты эксперимента
(зависимость времени выхода всех агентов из лабиринта от номера итерации):
bg_opt – МАС [8–11] с применением разработанного метода оптимизации организационной структуры МАС; standart – МАС [8–11] без применения разработанного метода
Fig. 2. Experiment results
(dependence of the exit time of all agents from the maze on the iteration number):
bg_opt is MAS [8-11] using the developed method of optimizing MAS organizational structure; standart is MAS [8-11] without using the developed method
Обсуждение
Применение разработанного метода позволило уже к 50-й итерации улучшить время выполнения поставленной задачи в среднем на 12,3 % в сравнении со стандартной системой, а к 200-й итерации этот показатель достиг 53,3 % (см. рис. 2). Полученный выигрыш в производительности обусловлен минимизацией издержек (связанных с загруженностью вычислительных систем агентов-менеджеров, а также с задержкой при обмене данными с агентами-подчиненными), которая достигается за счет оперативной адаптации состава групп агентов к изменениям параметров окружающей среды. Полученные экспериментальные данные свидетельствует о целесообразности применения разработанного метода в централизованных МАС.
Заключение
В результате выполнения данной работы был проведен анализ источников, посвященных задаче формирования организационной структуры МАС, предложен метод оптимизации организационной структуры централизованной МАС в автоматическом режиме (выполняется в случае незначительных изменений условий задачи или параметров окружающей среды), основанный на применении биогеографического алгоритма.
1. Zhiqi Shen, Ling Yu, Han Yu. An Evolutionary Ap-proach for Optimizing Hierarchical Multi-Agent System Organization. Available at: https://doi.org/10.48550/arXiv.1411.6202 (accessed: 20.09.2023).
2. Bistaffa F., Farinelli F., Cerquides J., Rodríguez-Aguilar J., Ramchurn S. D. Anytime Coalition Structure Generation on Synergy Graphs. Available at: https://www.researchgate.net/publication/269092245_Anytime_coalition_structure_generation_on_synergy_graphs (accessed: 22.09.2023).
3. Sims M., Corkill D., Lesser V. Knowledgeable Auto-mated Organization Design for Multi-Agent Systems. Available at: http://mas.cs.umass.edu/Documents/07-43.pdf (accessed: 22.09.2023).
4. Rahwan T., Michalak T. P., Wooldridg M., Jennings N. R. Coalition structure generation: A survey. Artificial Intelli-gence, 2015, no. 229, pp. 139-174.
5. Rahwan T., Michalak T. P. Coalition Structure Generation on Graphs. Available at: https://doi.org/10.48550/arXiv.1410.6516 (accessed: 24.09.2023).
6. Horling B., Lesser V. A Survey of Multi-Agent Or-ganizational Paradigms. The Knowledge Engineering Re-view, 2005, no. 19 (04), pp. 281-316.
7. Saimon D. Algoritmy evoliutsionnoi optimizatsii [Evolutionary optimization algorithms]. Moscow, DMK Press, 2020. 1002 p.
8. Dubenko Iu. V. Metod povtornogo primeneniia i obmena opytom pri kollektivnom vzaimodeistvii intellek-tual'nykh agentov [The method of repeated application and exchange of experience in the collective interaction of intelligent agents]. Vestnik Voronezhskogo gosudarstvennogo tekhnicheskogo universiteta, 2022, vol. 18, no. 1, pp. 62-72.
9. Dubenko Iu. V., Rudeshko N. A. Algoritm obucheniia s podkrepleniem dlia detsentralizovannykh mnogoagentnykh sistem, osnovannyi na obmene opytom i obuchenii agentov sluchainomu vzaimodeistviiu [A reinforcement learning algorithm for decentralized multi-agent systems based on the exchange of experience and training of agents in random interac-tion]. Vestnik Voronezhskogo gosudarstvennogo tekhnicheskogo universiteta, 2022, vol. 18, no. 4, pp. 30-36.
10. Dubenko Iu. V. Algoritm kollektivnogo vzai-modeistviia intellektual'nykh agentov v tsentralizovannykh mno-goagentnykh sistemakh [The algorithm of collective interaction of intelligent agents in centralized multi-agent systems]. Vestnik komp'iuternykh i informatsionnykh tekhnologii, 2022, vol. 19, no. 10 (220), pp. 30-42.
11. Dubenko Iu. V., Dyshkant E. E., Timchenko N. N., Rudeshko N. A. Gibridnyi algoritm formirovaniia kratchaishei traektorii, osnovannyi na primenenii mnogoagentnogo obucheniia s podkrepleniem i obmena opytom [A hybrid algorithm for the formation of the shortest trajectory based on the use of multi-agent reinforcement learning and experience exchange]. Vestnik komp'iuternykh i informatsionnykh tekhnologii, 2021, vol. 18, no. 11 (209), pp. 13-26.
