Россия
Архитектура многоагентной системы (МАС) представляет собой совокупность ролей и связей агентов, а также множества базовых правил, определяющих их генезис. Целью данной работы является разработка метода, обладающего следующими характеристиками: возможность модификации базовых правил, определяющих условия установления и разрыва вертикальных и горизонтальных связей между агентами; возможность автоматической адаптации архитектуры (в процессе решения поставленной задачи) к изменениям значений показателей окружающей среды, а также в количественном и качественном составе множества агентов; возможность моделирования более трех архитектур МАС. Разработанный метод первоначального формирования и последующей адаптации архитектуры МАС полностью удовлетворяет обозначенным характеристикам. Определение оптимального множества базовых параметров МАС производится с помощью «генетического алгоритма» путем обучения на виртуальной модели окружающей среды. Существует возможность моделирования архитектур МАС следующих типов: «коалиция», «команда», «федерация», «конгрегация». Проведенная экспериментальная оценка подтвердила эффективность разработанного метода по показателю «общее время выполнения поставленной задачи» в сравнении со следующими подходами: применение «генетического алгоритма» к «хромосоме», содержащей множество вертикальных связей между агентами (изменение архитектуры МАС возможно лишь на новой итерации); множество вертикальных связей фиксировано и на каждой новой итерации остается неизменным. Преимущество предложенного подхода в сравнении с аналогами заключается в возможности автоматической адаптации архитектуры МАС в процессе решения поставлен-ной задачи (а не с началом новой итерации), с адаптацией к вариациям множества агентов либо к новым значениям параметров окружающей среды.
многоагентная система, архитектура, вертикальная связь, горизонтальная связь, агент, адаптация, генетический алгоритм
Введение
Введение
Архитектура многоагентной системы (МАС) представляет совокупность ролей и связей агентов, а также множества базовых правил, определяющих их генезис [1]. Очевидно, что от выбора архитектуры и ее способности к адаптации к изменениям окружающей среды в существенной мере зависит производительность МАС. Существующие подходы к формированию архитектуры МАС могут быть классифицированы следующим образом:
1) по глубине модификации (под модификацией будем понимать изменение параметров архитектуры МАС с целью ее адаптации к текущим условиям окружающей среды):
а) модификация множества связей между агентами в зависимости от состава множества агентов, поставленной задачи, текущих параметров окружающей среды [2–6]. При этом корректировке подвергается именно древовидная структура, описывающая множество связей агентов МАС, а базовые правила, описывающие, например, условия возникновения или разрыва этих связей, остаются неизменными;
б) модификация множества базовых правил, опи-
сывающих фундаментальные условия функционирования и взаимодействия агентов МАС [7, 8]. При этом установление и разрыв связей между агентами осуществляется в автоматическом режиме в зависимости от их состояния, параметров окружающей среды, условий поставленной задачи;
2) по уровню адаптивности:
а) статическая архитектура [2, 4, 5]. Модификация архитектуры производится по результатам выполнения поставленной задачи после останова процедуры функционирования МАС;
б) динамическая архитектура [3, 6–8]. Связи между агентами МАС могут изменяться в процессе решения поставленной задачи;
3) по степени масштабируемости:
а) наличие возможности интеграции новых агентов в процессе работы МАС [3, 7];
б) отсутствие возможности приема новых агентов в процессе функционирования МАС [2, 4, 6, 8];
4) по числу моделируемых архитектур (например, «команда» – предусматривается наличие горизонтальных и вертикальных связей между агентами, максимизация группового выигрыша; «коалиция» – наличие только горизонтальных связей, максимизация индивидуального, а не группового выигрыша; «федерация» – члены группы взаимодействуют только с агентом-координатором, т. е. разрешены только вертикальные связи; «конгрегация» – формирование долговременных структур, остающихся неизменными в процессе решения поставленной задачи [5]):
а) одна [2–6];
б) две [7, 8];
в) три и более (в настоящее время отсутствуют работы, удовлетворяющие данному критерию).
Очевидно, что повышение вариативности при выборе архитектур МАС будет способствовать большей гибкости при адаптации к различным условиям окружающей среды. Таким образом, целью данной работы является разработка метода первоначального формирования и последующей адаптации архитектуры МАС, обладающего следующими характеристиками: по глубине модификации – модификация множества базовых правил, описывающих фундаментальные условия функционирования
и взаимодействия агентов МАС; по уровню адаптивности – динамическая архитектура; по степени масштабируемости – наличие возможности интеграции новых агентов в процессе работы МАС; по числу моделируемых архитектур – три и более.
Постановка задачи и методы
Дано: 
– МАС, функционирующая в двух режимах: обучения (цель – изучение окружающей среды), основной (цель – максимизация производительности); 
в момент времени 
; , , .
, описывающих ее архитектуру ;
- множество выходных параметров, описывающих результат выполнения множеством агентов 
поставленной задачи ;
;
– общее время выполнения поставленной задачи (глобальный параметр эффективности, фиксируется в момент времени
где под траекторией
– «коэффициент обесценивания»,
Таким образом, необходимо разработать метод 
) и последующей модификации (для
при условии
где на интервале 
на интервале
При этом агенты
1) Число «бонусов» :
где (),
где 
(коэффициент, определяющий скорость «забывания» вознаграждений, полученных ранее). Данная характеристика является индикатором, как технического состояния, так и востребованности агента (если агент обладает небольшим числом «бонусов», то он либо имеет технические неполадки и не справляется с заданием, либо оно ему не было назначено, и он является лишним). Каждый агент стремится к максимизации данного показателя, т.е.
Примечание: агент, длительное время имеющий нулевой показатель «бонусов» исключается из МАС и отзывается на базу.
2) «Престиж» , тем он обладает большим «престижем»):
где учитываются только значения
3) Территориальные ограничения:
а) «Личная зона» - окрестность агента, представляющая окружность с радиусом
б) «Социальная зона» - окружность с радиусом
в) «Публичная зона» - окружность с радиусом
4) Множество связей
а) Горизонтальные связи – коммуникационное взаимодействие двух равноправных агентов, которое может заключаться в следующем: репликация опыта (под опытом понимается множество кортежей (2)); арбитраж «коллизий» (спорных ситуаций, например, когда два агента планируют переход в одну и ту же область окружающей среды, что может повлечь их столкновение).
б) Вертикальные связи – коммуникационное взаимодействие двух неравноправных агентов (агент-подчиненный и доминирующий над ним агент-координатор): трансляция агенту-подчинённому подзадач
При этом для множества связей
1)
2)
3) Применяемые правила арбитража «коллизий» (ситуации, при которых действия, планируемые к выполнению, влекут попадание агентов в личные зоны друг друга) для равноправных агентов (может быть разрешено только одно из перечисленных)
а) учет «престижа» агентов, непосредственно участвующих в «коллизии»:
- решение выносится в пользу агента, имеющего больший «престиж» (стимуляция «расслоения» агентов по числу «бонусов») (
- решение выносится в пользу агента, имеющего меньший «престиж» (попытка выровнять показатели производительности агентов) (
б) учет «престижа» агентов вышестоящего уровня, с которыми участники «коллизии» установили вертикальные связи:
- решение выносится в пользу агента-подчиненного, имеющего вертикальную связь с агентом-координатором, обладающим более высоким «престижем» (
- решение выносится в пользу агента-подчиненного, имеющего вертикальную связь с агентом-координатором, имеющим меньший «престиж» (
Примечание: при арбитраже коллизий между неравноправными агентами (агент-подчиненный и агент-координатор) решение всегда выносится в пользу доминирующего агента.
При установлении вертикальных связей между агентами
а) Свободный агент
(8)
где
б) На вероятность установления вертикальной связи также оказывает влияние расстояние между потенциальными агентом-координатором и агентом-подчиненным:
(9)
где
в) Вероятность разрыва агентом-подчиненным вертикальной связи и перехода в разряд свободных агентов (данный механизм подробно описывается в работе [2]):
(10)
где 
, 
; 
– радиусы личной, социальной, публичной зон агента соответственно; 
– применяемое правило арбитража «коллизий»,
Очевидно, что
где 
– соответственно, вид множества (10) в основном режиме и режиме обучения [7].
На основании (1) может быть определена ценность выбора действия 
в состоянии 
, которая может быть выражена в значении Q (Q-Learning) [9]. В целях побуждения агентов к исследованию окружающей среды вероятность выбора агентом пары
(11)
может быть обозначена как 
, при этом по мере обучения МАС она может возрастать:
(12)
где 
– минимальная вероятность выполнения условия (11) при выборе действия; – максимальное значение усредненного вознаграждения по всем траекториям 
, при котором π = πmin;
– величина показателя Rp, при которой активируется режим обучения либо происходит переход в основной режим βπ > 0. Дополним множество (10) параметрами из (12):
(13)
при этом будем считать, что
где 
– см. (10).
Ниже представлен алгоритм функционирования рассматриваемой МАС:
1) формирование 
– архитектура МАС в режиме обучения, соответствующая 
;
2) МАС работает в режиме обучения, пока
(14)
в ином случае активируется основной режим;
3) формирование 
– архитектура МАС в основном режиме, соответствующая 
4) МАС работает в основном режиме, пока
(15)
иначе снова происходит переход в режим обучения;
5) шаги 1–4 повторяются, пока не будет решена поставленная задача T.
Следует отметить, что выражение 
не является истинным. Множества (10), (13) лишь задают базовые правила формирования и функционирования МАС. При этом построенная на их основе архитектура может иметь большое множество вариаций, зависящих как от состава множества агентов A, так и от текущих параметров окружающей среды E, а также условий задачи T. Таким образом, связь множеств (10), (13) и архитектуры МАС может быть описана следующим выражением:
При переходе между режимами происходит смена базовых правил формирования и функционирования МАС, описанных в (10), (13), что возможно в случае достижения целей обучения МАС либо при изменениях состава множества агентов или параметров окружающей среды, влекущих существенное падение величины среднего вознаграждения Rp, получаемого агентами (т. е. при ложности условий (14) или (15)). Таким образом, будем расценивать условие, представленное в формуле (2), как применяемое в рамках одного режима работы МАС при истинности условий (14) или (15). В этом случае модифицирующее воздействие 
вырабатывается автоматически в рамках одного режима и заключается в формировании (или разрыве) вертикальных или горизонтальных связей между агентами.
Для определения значений множеств 
позволяющих оптимизировать работу МАС по глобальному показателю эффективности t, применим «генетической алгоритм» со следующими параметрами:
1) «хромосома» объединяет множества (10), (13);
2) функция приспособленности: t → min (общее время выполнения поставленной задачи T);
3) применяемые «генетические операторы»: «скрещивание» методом рулетки с использованием «видовых стратегий» (препятствование «скрещиванию» между особями с близкими «хромосомами»), «равномерная мутация» [10].
Результаты
Цель эксперимента: в результате выполнения компьютерного моделирования доказать эффективность применения предложенного метода первоначального формирования и последующей адаптации архитектуры МАС, основанного на применении генетического алгоритма.
Описание решаемой задачи: достижение агентами в лабиринте всех сгенерированных целевых состояний.
Описание внешней среды: виртуальный лабиринт, сформированный в среде Microsoft Unity, размерностью 150 × 150 (фрагмент представлен на рис. 1).
Рис. 1. Фрагмент виртуального лабиринта: 1 – агенты; 2 – целевое состояние
Fig. 1. A fragment of the virtual maze: 1 – agents; 2 – target state
Под единицей размерности понимается клетка, которая может иметь одно из следующих состояний: проходимая, непроходимая (в этом случае соответствует квадратному блоку, применяемому для формирования стен). В лабиринте не допускаются замкнутые контуры, т. е. все проходимые клетки должны быть достижимы для агентов. Структура лабиринта меняется случайным образом (изменение типа одной случайной клетки происходит с периодичностью в 5 с, при этом периодически допускается одновременное изменение состояния на противоположное для 30 % клеток лабиринта). Одновременно на карте отображаются только 5 целевых состояний, при этом обнаруженное агентами целевое состояние заменяется на новое. Общее число целей, генерируемых за все время выполнения задачи, составляет 100. Координаты целевых состояний определяются случайным образом. Периодически выполняется ограничение мобильности (обездвижение) случайных агентов (на 10–30 с), при этом одновременно может быть обездвижено не более 20 % агентов. Версии окружающей среды, включая все флуктуации в структуре лабиринта и мобильности агентов, абсолютно одинаковы для обоих тестируемых методов (как для предложенного в данной работе, так и для его аналога [2]).
Число, типы применяемых агентов: всего 40 ед. Виртуальные агенты, имитирующие мобильных роботов на колесной транспортной платформе, оснащенных видеокамерой [3], генерируются в трех комплектациях (в зависимости от возможностей вычислительной системы): агенты, имеющие наиболее производительную вычислительную систему (потенциальные агенты-координаторы) – 3 ед.; агенты, имеющие вычислительную систему со средней производительностью – 12 ед. (могут быть как агентами-координаторами, так и агентами-подчиненными); агенты, имеющие вычислительную систему с низкой производительностью – 25 ед. (потенциальные агенты-подчиненные, вероятность выдвижения такого агента в агенты-координаторы очень низкая). Моделирование различных уровней производительности вычислительной системы осуществлялось путем применения задержки при выполнении алгоритмов функционирования агентов.
Механизм выбора стартовых положений агентов: координаты стартовых положений генерируются случайным образом на каждой итерации.
Механизм выбора целевых состояний: координаты целевых состояний генерируются случайным образом на каждой итерации.
Критерий, позволяющий утверждать об успешном решении задачи: обнаружение всех целевых состояний.
Число итераций (попыток): 300. При этом итерация считается выполненной в случае достижения критерия решения задачи.
Имитация загруженности вычислительной системы агента-координатора: при назначении задач, а также при расчете подкреплений на каждого агента-подчиненного генерировалась задержка в 0,3 с [3].
Имитация задержки в канале связи в зависимости от расстояния: агент-подчиненный получал информационные сообщения от агента-координатора с задержкой из расчета 0,2 с на 5 клеток прямого расстояния между ними [3].
Критерий оценки эффективности метода: время выполнения одной итерации.
Количество «хромосом», генерируемых на каждой итерации: 100.
Результаты, полученные в ходе эксперимента, представлены на рис. 2 (оценка выполнялась по показателю t – общее время выполнения поставленной задачи T), при этом показаны результаты для лучшей «хромосомы» в популяции, приняты следующие условные обозначения: «Аналог [2]» – алгоритм, описанный в [2] («генетический алгоритм», «хромосома» содержит множество вертикальных связей между агентами); «Связи агентов – статичны» – алгоритм с вертикальными связями в статике (5 агентов-координаторов, 35 агентов-подчиненных, по 8 агентов в подчинении у одного агента-координатора), тип архитектуры МАС – «конгрегация» [1]; во всех рассматриваемых алгоритмах функционирование агентов основано на парадигме «обучения с подкреплением».
Рис. 2. Результаты эксперимента
Fig. 2. Experimental results
Обсуждение
Как видно на рис. 2, методы, предусматривающие последовательную адаптацию множества связей агентов к условиям окружающей среды, показали лучшие результаты, чем метод, предполагающий неизменную структуру этого множества, для которого уменьшение показателя «общее время выполнения поставленной задачи» происходило лишь за счет повышения степени изученности окружающей среды на каждой новой итерации.
В частности, метод, описанный в [2], уже на 100-й итерации показал результат, лучший на 13 %. Аналогичный результат для разработанного метода составил 37 %, что объясняется его гибкостью –
в отличие от [2] архитектура МАС может автоматически изменяться в процессе решения поставленной задачи (а не с началом новой итерации), адаптируясь к вариациям множества агентов либо к новым значениям параметров окружающей среды.
Также была достигнута цель данной работы,
а именно разработка метода первоначального формирования и последующей адаптации архитектуры МАС, обладающего следующими характеристиками:
1) по глубине модификации – модификация множества базовых правил, описывающих фундаментальные условия функционирования и взаимодействия агентов МАС. Имеется возможность модификации показателей, определяющих вероятность возникновения или разрыва вертикальных и горизонтальных связей различных видов, в том числе в зависимости от показателей работы самих агентов (число «бонусов», уровень «престижа»). Базовые параметры архитектур МАС задаются в «хромосомах». «Хромосома», содержащая оптимальные параметры архитектуры МАС для окружающей среды конкретного типа, определяется с помощью «генетического алгоритма» в процессе обучения на виртуальной модели окружающей среды («модель мира»);
2) по уровню адаптивности – динамическая архитектура. Агенты могут автоматически устанавливать и разрывать вертикальные и горизонтальные связи в процессе решения задачи;
3) по степени масштабируемости – наличие возможности интеграции новых агентов в процессе работы МАС. Разработан механизм, позволяющий выполнять перестроение множества связей в случае выхода агента из строя (включая агента-координатора – в этом случае агенты-подчиненные, не получая подзадачи для выполнения, просто разорвут с ним вертикальные связи), в случае добавления в МАС новых агентов (новый агент сначала получает роль «свободный агент», далее, в зависимости от базовых параметров МАС, например, может установить вертикальную связь с агентом-координатором);
4) по числу моделируемых архитектур – 3 и более. Ниже приводятся достаточные значения параметров «хромосом», определяющих следующие типы архитектур (приведены согласно [1]):
а) «коалиция» (наличие только горизонтальных связей, максимизация индивидуального выигрыша): при Pvert = 0, Rsocial = Rpublic (см. (10)) (запрет вертикальных связей);
б) «команда» (наличие горизонтальных и вертикальных связей, максимизация группового выигрыша): при Phor > 0, Pvert > 0 (см. (10)).
в) «федерация» (члены группы взаимодействуют только с агентом-координатором): при Phor = 0, Rsocial = Rprivate (запрет горизонтальных связей), 
(агенты-подчиненные не обмениваются напрямую информацией с целью арбитража «коллизий») (см. (10)).
г) «конгрегация» (формирование долговременных структур): при Bsup = 0 (вероятность разрыва вертикальных связей всегда будет равна нулю) (см. (10)).
Заключение
В результате выполнения данной работы был разработан метод первоначального формирования и последующей адаптации архитектуры многоагентной системы (МАС), основанный на применении генетического алгоритма, обладающий следующими характеристиками: по глубине модификации – модификация множества базовых правил, описывающих фундаментальные условия функционирования и взаимодействия агентов МАС; по уровню адаптивности – динамическая архитектура МАС; по степени масштабируемости – наличие возможности интеграции новых агентов в процессе работы МАС; по числу моделируемых архитектур – 3 и более. Разработанный метод может быть использован при управлении МАС, применяемых в таких областях, как мониторинг состояния инфраструктурных объектов, складская логистика и доставка грузов, выполнение сельскохозяйственных работ (сбор урожая, внесение удобрений, обработка сельскохозяйственных культур от вредителей).
1. Horling B., Lesser V. A Survey of Multi-Agent Or-ganizational Paradigms // The Knowledge Engineering Review. 2005. N. 19 (04). P. 281–316.
2. Ling Yu, Zhiqi Shen, Chunyan Miao, Victor Lesser V. Genetic Algorithm Aided Optimization of Hierarchical Multi-Agent System Organization // 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011) (Taipei, Taiwan, May 2–6, 2011). V. 1–3. URL: https://www.researchgate.net/publication/221456103_Genetic_algorithm_aided_optimization_of_hierarchical_multiagent_system_organization (дата обращения: 22.09.2023).
3. Дубенко Ю. В., Дышкант Е. Е., Обозовский А. А. Метод оптимизации организационной структуры цен-трализованных многоагентных систем в автоматическом режиме // Вестн. Астрахан. гос. техн. ун-та. Сер.: Управление, вычислительная техника и информатика. 2024. № 1. С. 46–55.
4. Bistaffa F., Farinelli F., Cerquides J., Rodríguez-Aguilar J., Ramchurn S. D. Anytime Coalition Structure Generation on Synergy Graphs. URL: https://www.researchgate.net/publication/269092245_Anytime_coalition_structure_generation_on_synergy_graphs (дата обращения: 22.09.2023).
5. Rahwan T., Michalak T. P. Coalition Structure Generation on Graphs. URL: https://doi.org/10.48550/arXiv.1410.6516 (дата обращения: 24.09.2023).
6. Ghrieb N., Mokhati F., Tahar G. Maintaining Organizational Multi-agent Systems: A Reorganization-based Preventive Approach. URL: https://www.scitepress.org/Link.aspx?doihttps://doi.org/10.5220/0010314803840389 (дата обращения: 04.10.2024).
7. Дубенко Ю. В., Дышкант Е. Е., Обозовский А. А. Метод автоматической реорганизации структуры многоагентных систем, основанный на применении алгоритма симулированного закаливания // Изв. высш. учеб. заведений. Поволж. регион. Техн. науки. 2024. № 1 (69). С. 5–18.
8. Mahani M. N. Strategic Structural Reorganization in Multi-agent Systems Inspired by Social Organization Theo-ry: Dissertation, Degree Level - Ph.D., Discipline - Electrical Engineering & Computer Science. University of Kansas, 2012. 105 p.
9. Саттон Р. С., Барто Э. Дж. Обучение с подкреплением: введение: практ. рук. / пер. с англ. А. А. Слинкина. М.: ДМК Пресс, 2020. 552 с.
10. Дэн Саймон. Алгоритмы эволюционной оптимизации / пер. с англ. А. В. Логунова. М.: ДМК Пресс, 2020. 1002 с.
