Введение
В системном анализе мультиагентное моделирование является эффективным средством нахождения оптимального (либо приемлемого) решения задач, возникающих в сложных системах, средством поддержки принятия управленческих решений. Для определения адекватности модели, разработанной авторами данной статьи, проведен сравнительный анализ ряда мультиагентных моделей, применимых для решения задач планирования и управления процессами производства на промышленных предприятиях.
Описание коалиционной модели
Целью разработки коалиционной модели мультиагентного процесса преобразования ресурсов (МППР) является описание процессов взаимодействия агентов и формирования коалиций при решении вопросов коллективного использования ресурсов и средств в условиях параллельного выполнения МППР. Разработанная модель отвечает следующим требованиям.
1. Ориентация на моделирование мультиагентных процессов преобразования ресурсов. Необходимо отражение следующих основных особенностей МППР: учет различных типов ресурсов (материальных, информационных, энергетических, трудовых, финансовых); наличие возможности задания начальных состояний операций над ресурсами; учет возникновения и разрешения конфликтов; наличие возможности иерархического представления структуры процесса и расчета различных характеристик процесса на каждом уровне иерархии.
2. Наличие возможности описания гибридных моделей агентов, в т.ч.: определение целей агента, описание базы знаний агента, выбор определенной стратегии взаимодействий агента.
3. Наличие механизма формирования коалиций, обеспечивающего следующие основные возможности: определение целей коалиции, описание базы знаний коалиции.
4. Наличие механизма описания мультиагентных систем (МАС), позволяющего определение: множества агентов и коалиций МАС, множества установленных связей между агентами и коалициями, общей базы знаний МАС.
5. Наличие аппарата организации взаимодействий агентов и коалиций, включающего: язык общения агентов, соответствующий проблемной области МППР и разработанный на основе стандарта взаимодействия агентов; механизм обмена сообщениями между агентами и коалициями и множество методов взаимодействий агентов и коалиций в МАС.
6. Наличие механизма разрешения конфликтов между агентами, основанного на использовании стратегий взаимодействий и организации аукционов.
7. Наличие механизма составления планов действий для агентов и коалиций.
Реализация вышеперечисленных требований обеспечивается с помощью применения имитационного моделирования, теории процессов преобразования ресурсов (ППР), теории мультиагентных систем, теории аукционов и теории составления расписаний.
Основой для создания коалиционной модели МППР является математическая модель, разработанная Аксеновым К.А. и Гончаровой Н.В. [1]. В коалиционной модели МППР функционируют процессы, представленные на рис. 1.
Рис. 1 – Схемы процессов в коалиционной модели МППР
Сравнение коалиционной модели с моделью И.М. Москалева
В работе И.М. Москалева [4] представлена математическая модель ППР из пассивных преобразователей, модель из активных преобразователей и смешанная модель.
Модель активных и пассивных ППР [4]:
,
где 
– множество активных элементов модели ППР; 
– множество пассивных элементов модели ППР;
– хранилища ресурса; 
– множество разделяемых парков средств; 
– множество возможных потоков ресурса между элементами модели; 
– множество потоков средств между элементами модели; 
– множество информационных потоков между преобразователями; 
– множество ресурсов в сети.
Пассивный преобразователь может находиться в трех состояниях: ожидания входных ресурсов, преобразования ресурсов и блокирования. Для представления переходов его состояний используется граф состояний [4].
Достоинства модели (относительно требований к коалиционной модели):
– развитые средства описания информационных потоков;
– деление на активные и пассивные преобразователи ППР;
– модель позволяет работать с онтологиями предметной области.
Недостатки модели (относительно требований к коалиционной модели):
– отсутствие ориентации на мультиагентный подход;
– отсутствие возможности формирования коалиций;
– отсутствие встроенного механизма составления планов действий агентами;
– отсутствие встроенного механизма разрешения конфликтов.
Таким образом, рассмотренная модель не удовлетворяет ряду требований, предъявляемых к коалиционной модели МППР, специально не разработана для предметной области МППР.
Сравнение коалиционной модели с моделью открытой мультиагентной системы П.О. Скобелева
Открытая мультиагентная система (ОМАС) для поддержки процессов принятия решений на основе ПВ-сетей (сетей потребностей и возможностей) П.О. Скобелева [5] базируется на холистическом подходе, состоящем в следующем:
- модель ОМАС декомпозируется на автономные сущности (деталь, материал, работник, станок, автомобиль и т.д.);
- каждая сущность имеет собственных агентов потребностей и возможностей;
- агенты возможностей ищут себе наиболее выгодное применение, а агенты потребностей − максимально удовлетворить свои требования;
- потребности и возможности (например, заказы и ресурсы) находятся в постоянном поиске соответствия (матчинга), обусловленного заданными индивидуальными критериями для каждой из сторон.
В такой открытой системе агенты потребностей и возможностей реагируют на любые изменения в системе, разрывая имеющиеся и устанавливая новые связи. МСППР рассматривается как система, состоящая из агентов возможностей и потребностей, соревнующихся или кооперирующихся между собой, в зависимости от ситуации, с целью выполнения поставленной задачи. Главной особенностью подхода (относительно предлагаемой авторами статьи коалиционной модели) является самоорганизация заказов и ресурсов. Под самоорганизацией при этом понимается возможность системы автономно устанавливать новые связи между компонентами и разрывать существующие.
Порождающей ПВ-сетью [5] называется множество N вида:
N = {A, R, P, G},
где А − множество агентов потребностей и возможностей для заданной предметной области; R − множество возможных отношений между агентами потребностей и возможностей; Р − множество правил принятия решений и установления (разрыва) связей; G − множество целей, заданных агентам.
Архитектура ОМАС для построения ПВ-сетей состоит из базы знаний предметной области, включающей набор онтологий деятельности; сцены текущего виртуального мира; исполняющей системы; библиотеки расширений и интерфейсной системы (рис. 2).
Рис. 2. Общая архитектура ОМАС
Достоинства модели (относительно требований к коалиционной модели):
– простота реализации мультиагентной модели, позволившей унифицировать агентов потребностей и возможностей;
– непрерывный процесс принятия и пересмотра решений агентами позволяет системе гибко реагировать на любые события и изменения;
– агенты в модели обладают способностью самоорганизации;
– модель позволяет работать с онтологиями предметной области.
Недостатки модели (относительно требований к коалиционной модели):
– каждый ресурс и каждый заказ имеет собственных агентов, что порождает большое количество агентов, при этом любое событие в системе порождает многочисленные переговоры агентов, а также разрыв существующих связей и установление новых (такое нестабильное поведение модели требует значительное количество вычислительных ресурсов);
– отсутствие возможности формирования коалиций.
Таким образом, рассмотренная модель не удовлетворяет ряду требований, предъявляемых к коалиционной модели МППР, специально не разработана для предметной области МППР.
Сравнение коалиционной модели с моделью Д.Ю. Бугайченко
Одной из моделей, позволяющих описывать МППР, является модель Д.Ю. Бугайченко [2]. Для описания агента в модели предложена следующая архитектура. Внешняя среда агента описывается с помощью множества S-состояний среды. Возможные действия агента описываются с помощью множества А-действий. Таким образом, агента можно представить в виде функции: S → A [2]. Выбор конкретного действия из возможных агент осуществляет на основании текущего состояния внешней среды, а также истории, описывающей предыдущие состояния. При этом действия агента могут влиять на окружающую среду, но не контролировать ее полностью. Взаимодействие агента и внешней среды можно представлять с помощью истории (history) [2]:
h: so(a0)→s1(a1)→s2(a2)→… ,
где s0 – начальное состояние внешней среды; ai – i-е действие, выбранное агентом; si – состояние внешней среды после осуществления агентом (i-1)-го действия.
Для описания агента используется модель восприятия окружающей среды. Для этого введено множество P возможных восприятий и функция see: S → P, описывающие, каким образом определенные состояния среды воспринимаются агентом. В этом случае агент описывается с помощью функции action: P* → A, т.е. действие агента определяется текущим восприятием состояния внешней среды, а также множеством предыдущих восприятий.
Еще одной модификацией архитектуры Д.Ю. Бугайченко является агент с состоянием [2]. Такой агент содержит внутренние структуры данных, которые он модифицирует в зависимости от восприятия текущего состояния внешней среды, и на основе полученных результатов выбирает действие. Для формализации этого процесса введено множество I внутренних состояний агента и функция refine: I × P → I, отвечающая за обновление внутреннего состояния в соответствии с текущим восприятием среды. Агент в этом случае описывается с помощью функции action: I → A, т. е. действие будет выбираться на основе текущего внутреннего состояния.
Описанная выше архитектура обладает одним существенным недостатком: определенный таким образом агент не получает информации о совершенных им самим действиях, что резко ограничивает его возможности в накоплении опыта и анализе потенциальных последствий действий. Можно считать, что информация о действиях агента является частью информации об окружающей среде, но такой подход не является наглядным и интуитивно понятным. Д.Ю. Бугайченко предложено включение информации о совершаемых действиях явно во входные данные функции выбора действия action: (P × A)* → A. В таком виде агент явно получает информацию обо всей истории взаимодействия с окружающей средой, а не только о последовательности состояний, в которые окружающая среда переходила.
Достоинства модели (относительно требований к коалиционной модели):
– детальное описание агентов, его целей, базы знаний;
– использование модели агента с состоянием, позволяющим основывать выбор действия не на последовательности входных данных, а на одном конкретном элементе состояния;
– ведение истории действий агента.
Недостатки модели (относительно требований к коалиционной модели):
– модель является слишком общей и требует детальной проработки при описании сложных МППР;
– отсутствие возможности формирования коалиций;
– отсутствие встроенного механизма составления планов действий агентами;
– отсутствие встроенного механизма разрешения конфликтов.
Таким образом, рассмотренная модель не удовлетворяет ряду требований, предъявляемых к коалиционной модели МППР, специально не разработана для предметной области МППР.
Выводы
Рассмотренные модели, являясь адекватным математическим описанием процессов преобразования ресурсов, не обеспечивают всех требований для коалиционной модели МППР. Коалиционная модель МППР разработана для предметной области ППР и имеет ряд отличительных особенностей, определяющих нишу ее адекватного применения:
1) ориентация на моделирование МППР;
2) наличие возможности описания гибридных моделей агентов;
3) наличие механизма формирования коалиций;
4) наличие механизма описания мультиагентных систем;
5) наличие аппарата взаимодействий агентов и коалиций, включающего язык, разработанный на основе стандарта взаимодействия агентов для проблемной области МППР;
6) наличие механизма разрешения конфликтов между агентами, основанного на использовании стратегий взаимодействий и организации аукционов;
7) наличие механизма составления планов действий для агентов и коалиций.
Разработанная коалиционная модель мультиагентного процесса преобразования ресурсов может быть применена для решения задач планирования и управления процессами производства на промышленных предприятиях.
Работа выполнена в рамках государственного контракта 02.740.11.0512
Рецензенты:
Сесекин Александр Николаевич, д.ф.-м.н., профессор, заведующий кафедрой прикладной математики, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина», г. Екатеринбург.
Залазинский Александр Георгиевич, д.т.н., профессор, заведующий лабораторией системного моделирования, Институт машиноведения УрО РАН, г. Екатеринбург.