Электронный научный журнал
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,931

СРАВНИТЕЛЬНЫЙ АНАЛИЗ МУЛЬТИАГЕНТНЫХ МОДЕЛЕЙ ПРОЦЕССОВ ПРЕОБРАЗОВАНИЯ РЕСУРСОВ

Зраенко А.С. 1 Аксенов К.А. 2 Федотов В.П. 1
1 Институт машиноведения УрО РАН
2 ФГАОУ ВПО Уральский Федеральный университет им. первого Президента России Б.Н. Ельцина
В работе определены требования и приведено описание коалиционной модели мультиагентного процесса преобразования ресурсов (МППР), разработанной для предметной области процессов преобразования ресурсов (ППР). Целью разработки коалиционной модели МППР является описание процессов взаимодействия агентов и формирования коалиций при решении вопросов коллективного использования ресурсов и средств в условиях параллельного выполнения МППР. Проведен сравнительный анализ коалиционной модели МППР и аналогичных мультиагентных моделей: модель ППР И.М. Москалева; модель открытой мультиагентной системы П.О. Скобелева; модель интеллектуального агента и агента с состоянием Д.Ю. Бугайченко. Рассмотренные модели, являясь адекватным математическим описанием процессов преобразования ресурсов, не обеспечивают всех требований для коалиционной модели МППР. Разработанная модель может быть применена для решения задач планирования и управления процессами производства на промышленных предприятиях.
коалиция.
процесс преобразования ресурсов
система поддержки при¬нятия решений
мультиагентная система
агент
1. Аксенов К.А. Динамическое моделирование мультиагентных процессов преобразования ресурсов / К.А. Аксенов, Н.В. Гончарова. – Екатеринбург : УГТУ-УПИ, 2006. – 311 с.
2. Бугайченко Д.Ю. Разработка и реализация методов формально-логической спецификации самонастраивающихся мультиагентных систем с временными ограничениями : дис. … канд. физ-мат. наук. – М. : РГБ, 2007.
3. Зраенко А.С. Разработка системы поддержки принятия решений с использованием средств мультиагентного моделирования / А.С. Зраенко, К.А. Аксёнов, Е.М. Лазарев // XVI международная конференция молодых ученых : сборник статей. – Екатеринбург : УГТУ-УПИ, 2009. – С. 40-45.
4. Москалев И.М. Система анализа и оптимизации процессов преобразования ресурсов : дис. … канд. техн. наук. – Екатеринбург : УГТУ-УПИ, 2006.
5. Скобелев П.О. Открытые мультиагентные системы для оперативной обработки информа-ции в процессах принятия решений : дис. … докт. техн. наук. – М. : РГБ, 2003.

Введение

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

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

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

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

Рецензенты:

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

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


Библиографическая ссылка

Зраенко А.С., Аксенов К.А., Федотов В.П. СРАВНИТЕЛЬНЫЙ АНАЛИЗ МУЛЬТИАГЕНТНЫХ МОДЕЛЕЙ ПРОЦЕССОВ ПРЕОБРАЗОВАНИЯ РЕСУРСОВ // Современные проблемы науки и образования. – 2013. – № 4.;
URL: http://science-education.ru/ru/article/view?id=9640 (дата обращения: 16.01.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074