Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,791

COMPARATIVE ANALYSIS OF MULTI-AGENT MODEL FOR THE TRANSFORMATION RESOURCES

Zraenko A.S. 1 Aksenov K.A. 2 Fedotov V.P. 1
1 Institute of Mechanical Engineering
2 Ural Federal University named after the first Russian President Boris Yeltsin
В работе определены требования и приведено описание коалиционной модели мультиагентного процесса преобразования ресурсов (МППР), разработанной для предметной области процессов преобразования ресурсов (ППР). Целью разработки коалиционной модели МППР является описание процессов взаимодействия агентов и формирования коалиций при решении вопросов коллективного использования ресурсов и средств в условиях параллельного выполнения МППР. Проведен сравнительный анализ коалиционной модели МППР и аналогичных мультиагентных моделей: модель ППР И.М. Москалева; модель открытой мультиагентной системы П.О. Скобелева; модель интеллектуального агента и агента с состоянием Д.Ю. Бугайченко. Рассмотренные модели, являясь адекватным математическим описанием процессов преобразования ресурсов, не обеспечивают всех требований для коалиционной модели МППР. Разработанная модель может быть применена для решения задач планирования и управления процессами производства на промышленных предприятиях.
In work requirements are defined and the description of coalition model of the multi-agent process of transformation of resources (MPTR) developed for subject domain of the processes of transformation of resources (PTR) is provided. The purpose of development of the MPPR coalition model is the description of processes of interaction of agents and formation of coalitions at the solution of questions of collective use of resources and means in the conditions of parallel performance of MPPR. The comparative analysis of the MPPR coalition model and similar multi-agent models is carried out: PPR model I.M of Moskalev; model of open multiagentny system of P. O. Skobelev; model of the intellectual agent and the agent with condition of D.Y. Bugaychenko. The considered models, being the adequate mathematical description of processes of transformation of resources, don´t provide all requirements for the MPPR coalition model. The developed model can be applied to the solution of problems of planning and management of production processes at the industrial enterprises.
the coalition.
the process of trans¬formation of resources
decision support system
multiagent system
agent

Введение

В системном анализе мультиагентное моделирование является эффек­тивным средством нахождения оптимального (либо приемлемого) решения задач, возника­ющих в сложных системах, средством поддержки принятия управленческих решений. Для определения адекватности модели, разработанной авторами данной статьи, проведен сравнительный анализ ряда мультиагентных моделей, применимых для решения задач планирования и управления процессами производства на промышленных предприятиях.

Описание коалиционной модели

Целью разработки коалиционной модели мультиагентного процесса преобразования ресурсов (МППР) является описание процессов взаимодействия агентов и формирования коалиций при решении вопросов коллективного использования ре­сурсов и средств в условиях параллельного выполнения МППР. Разработанная модель отвечает следующим требованиям.

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

Рецензенты:

Сесекин Александр Николаевич, д.ф.-м.н., профессор, заведующий кафедрой прикладной математики, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина», г. Екатеринбург.

Залазинский Александр Георгиевич, д.т.н., профессор, заведующий лабораторией системного моделирования, Институт машиноведения УрО РАН, г. Екатеринбург.