Мультиагентная система поддержки принятия решений "Координатор"

Размещено на http://www.allbest.ru/

мультиагентная система поддержки принятия решений «Координатор»

П.А. Паршиков, В.К. Гулаков, А.К. Буйвал

Аннотация

искусственный интеллект мультиагентный система

Проанализированы особенности применения технологий распределенного искусственного интеллекта к согласованию интересов исполнителей работ. Рассмотрены модель, архитектура и алгоритмы функционирования мультиагентной системы поддержки принятия решений, основанной на распределенном взаимодействии интеллектуальных агентов. Предложена методика применения программной системы для решения задачи управления процессом согласования изменений графика проекта в области информационных технологий.

Ключевые слова: распределенный искусственный интеллект, мультиагентный подход, интеллектуальный агент, коллективное принятие решений, протокол коммуникации, язык коммуникации, кооперация агентов.

Основная часть

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

Задача управления процессом согласования интересов приобретает особую актуальность в случае совместной продуктивной деятельности многих организаций и предприятий, связанных между собой технологически и вносящих определенный вклад в общий результат. Совокупность процессов планирования, координации и контроля совместной целенаправленной деятельности отдельных исполнителей в условиях ограниченных ресурсов является предметом изучения теории управления проектами. Отношения между исполнителями и руководителем регламентируются условиями договора, который является одним из основных инструментов обеспечения контроля и мотивации участников проекта [1].

Если взаимовыгодные для обеих сторон параметры договора в процессе выполнения проекта становятся неоптимальными в связи с изменением внешних условий, неточностями прогнозирования и планирования, то у исполнителя может возникнуть желание изменить условия договора. И в этой ситуации необходимо своевременно согласовать между исполнителями возможные изменения в параметрах договоров, чтобы избежать реактивных и неоптимальных решений.

Каждый исполнитель принимает решение, исходя из собственных предпочтений, на основе информации о своих возможностях и условиях функционирования, которая не разглашается и не доступна другим участникам проекта. Поэтому в процессе согласования интересов необходимо использовать новые распределенные методики коллективного принятия решений, основанные на совместных действиях независимых участников организационной системы, результатом которых является возникшее состояние равновесия.

Распределенные системы поддержки принятия решений создаются с использованием технологий распределенного искусственного интеллекта, основным направлением развития которых является методология мультиагентного моделирования. Основным компонентом мультиагентной системы выступает автономный интеллектуальный агент, способный воспринимать состояние окружающей среды, вырабатывать решение и взаимодействовать с другими агентами. Агент действует от имени пользователя и ведет переговоры, снимая тем самым с человека избыточную информационную нагрузку.

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

На основе существующих моделей открытых мультиагентных систем, предложенных В.Б. Тарасовым [2], А.Н. Швецовым [3], И. Шохам [4], была разработана модель мультиагентной системы поддержки принятия решений по управлению процессом согласования интересов исполнителей работ по проекту, базирующаяся на взаимодействии распределенных интеллектуальных агентов (рис. 1).

Рис. 1 Модель мультиагентной системы

Мультиагентная система определяется кортежем

,

где - множество агентов; - среда; - множество отношений агентов; - протокол коммуникации; - множество состояний мультиагентной системы.

Мультиагентная система является многоосновной алгебраической системой, состоящей из множества интеллектуальных агентов, которые действуют совместно для достижения общих целей. Количество агентов в системе - . Задача коллектива интеллектуальных агентов ставится центром или метаагентом.

Интеллектуальный агент описывается кортежем

,

где - множество состояний агента; - множество языков коммуникации; - множество действий агентов; - множество социальных ограничений; - функция переходов. Каждое социальное ограничение определяется набором из двух компонентов:

.

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

Агент оказывает влияние на среду путем множества действий . Среда реагирует на влияние агентов множеством ответных действий . Среда определяется кортежем

,

где - множество состояний среды; - начальное состояние среды; - функция поведения среды.

В процессе коллективного принятия решений по согласованию интересов можно выделить четыре этапа [5; 6]:

1. Распознавание. Агент распознает целесообразность коллективного действия, так как не может достичь своей цели без кооперации с другими агентами.

2. Формирование группы агентов. Агент формирует в процессе переговоров группу готовых к совместным обязательствам агентов, способных к коллективным действиям.

3. Формирование совместного плана. Агенты вырабатывают совместный план, который позволит достичь цели и заинтересовать всех агентов в его выполнении.

4. Совместные действия. Агенты соглашаются принять согласованный план и придерживаться его в соответствии со взятыми обязательствами.

На этапе формирования совместного плана агенты пытаются добиться такого состояния, при котором все агенты были бы согласны с совместным планом и готовы действовать по нему. Совместный план формируется в процессе переговоров. Во время переговоров агенты предлагают планы, уточняют их с другими агентами, модифицируют предложенные планы до тех пор, пока все агенты не согласятся с единым планом.

Коммуникация агентов основана на механизме последовательного принятия решений, заключающемся в обмене предложениями и контрпредложениями, после получения которых возможно установление обратной связи. Распределенным алгоритмом взаимодействия агентов в процессе переговоров является разработанный протокол коммуникации [7].

Наиболее простой вариант переговоров заключается в том, что агенты при изменении плана работ не затрагивают работы других агентов или работы лишь одного из агентов. В таком случае можно применить так называемые парные переговоры. Однако в процессе согласования интересов исполнителей работ по проекту одновременно несколько агентов пытаются достигнуть взаимного соглашения. Поэтому в протокол коммуникации была введена пара команд «confirm/renege», уведомляющая группу агентов о совместном согласии или отказе одного из агентов в перезаключении договоров (табл. 1).

Таблица 1

Перечень команд протокола коммуникации в мультиагентной системе

Команды мультиагентных переговоров делятся на две группы: команды коммуникации между агентами и команды управления процессом переговоров. Команды коммуникации между агентами позволяют обмениваться знаниями и взаимодействовать с удаленными агентами. Команды управления процессом переговоров используются для передачи управляющих сигналов между агентами.

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

На основе построенной модели в интегрированной среде разработки Anylogic 5.4.1 была реализована мультиагентная система поддержки принятия решений (СППР) «Координатор». Anylogic 5.4.1 представляет собой среду для графического создания мультиагентных моделей с использованием объектно-ориентированного языка Java и является одной из немногих российских разработок в области имитационного моделирования, получивших признание за рубежом [8]. После графического описания мультиагентной модели и проводимых экспериментов средой автоматически была сгенерирована программа имитационного моделирования.

Применение технологии коммуникации распределенных по сети программных агентов определило разбиение системы «Координатор» на центральный модуль, используемый руководителем проекта, и клиентский модуль, используемый распределенными агентами-исполнителями (рис. 2).

Рис. 2 Архитектура мультиагентной СППР «Координатор»

Клиентский модуль включает в себя 5 компонентов.

Агент «Исполнитель» инкапсулирует в себе набор данных об отдельном исполнителе и определяет состояние, в котором он находится в процессе переговоров. Агент хранит информацию об имени исполнителя, реплицированное множество агентов «Работа», агент «Коммуникация», агент «Графический интерфейс» (GUI) и диаграмму состояний (стейтчарт), описывающую состояния и последовательность их изменений.

Агент «Коммуникация» осуществляет общение по сети с роутером сообщений и ответственен за прием и передачу сообщений. Для взаимодействия используется технология вызова удаленных процедур (Remote Method Invocation, RMI), позволяющая удаленно вызывать методы моделей Anylogic, запущенных на других компьютерах, из таких же моделей Anylogic.

Набор агентов «Работа» инкапсулирует в себе набор сведений об отдельной работе исполнителя: ее название, даты начала и окончания, текущее состояние в процессе переговоров и последовательность переходов между возможными состояниями. Сведения о последовательности выполнения работ отражаются в наборе предшествующих и последующих работ, включающем в себя данные о названии и исполнителе, выполняющем их.

Диаграмма состояний отражает возможные состояния агента в процессе переговоров и последовательность переходов между этими состояниями. Диаграмма состояний в виде ориентированного графа с вершинами - состояниями и дугами - переходами в среде Anylogic представлена на рис. 3.

Рис. 3 Визуализация состояния агента в процессе переговоров

Переходы между состояниями происходят при возникновении сигналов, вызываемых приходом сообщений исполнителю и инициированных агентом «Коммуникация». Рефлексивные связи некоторых состояний означают прием всех соответствующих сообщений от исполнителей и лишь затем выполнение нужного действия. Это необходимо для поддержания синхронности процесса переговоров.

Агент «Графический интерфейс» позволяет пользователю посредством визуальных компонентов взаимодействовать со своим агентом, передавать ему исходные данные и отслеживать процесс обмена сообщениями (рис. 4).

Центральный модуль предназначен для управления процессом взаимодействия распределенных по сети агентов и помимо агента «Графический интерфейс» и диаграммы состояний, аналогичных по назначению соответствующим компонентам клиентского модуля, включает агенты «Роутер сообщений» и «Проект».

Размещено на http://www.allbest.ru/

Рис. 4 Интерфейс управления интеллектуальным агентом

Агент «Роутер сообщений» осуществляет регистрацию распределенных агентов, поддерживает связь с ними и передает сообщения между зарегистрированными агентами. Агент контролирует доступность в момент переговоров всех заинтересованных агентов и кэширует сообщения для исключения их потери.

Агент «Проект» позволяет взаимодействовать с базой данных проектов или загружать проект из файла специального формата. Агент выбирает сведения о работах, выполняемых по проекту, их логической последовательности, сроках, исполнителях и закрепленных за ними агентах.

Разработанная мультиагентная СППР «Координатор» была использована для моделирования процесса согласования интересов исполнителей работ в области информационных технологий. На примере проекта по разработке мультимедийного приложения с использованием Flash-технологий, реализуемого несколькими независимыми организациями с общим координатором - ООО «E-Style Software House» (г. Брянск), была определена экономическая эффективность управления процессом согласования интересов.

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

Основные характеристики исследуемого проекта: продолжительность - 50 дней, количество исполнителей - 6, количество работ - 28. Оценка возможных затрат по двум работам (A и F) при выполнении в определенные договором сроки оказалась выше, чем при заключении договора. Выполняющие данные работы исполнители могут оценить выигрыш при перезаключении договоров с изменением сроков выполнения работ и принять решение: перейти к новому графику с компенсацией дополнительных затрат другим исполнителям или придерживаться первоначального графика.

На основе полученных данных была построена мультиагентная модель с шестью агентами-исполнителями и одним агентом-координатором. В результате моделирования процесса согласования изменений было выявлено, что изменение сроков выполнения работы A менее предпочтительно, чем следование первоначальному графику. По работе F привлечение дополнительных ресурсов для выполнения в срок оказывается дороже, чем сдвиг последующих работ по срокам и переход к новому графику проекта.

На рис. 5 в виде диаграммы Ганта изображены исходный и измененный графики проекта. Новый график проекта в процессе мультиагентных переговоров оказался более предпочтительным, чем исходный, и для перехода к нему необходимо осуществить стимулирующие воздействия на проигравших исполнителей. Исполнитель d при этом стимулирует за готовность перейти к новому графику исполнителей a и f, выполняющих работы G, H, I, J и K, сроки которых будут изменены. При этом им будут компенсированы возникшие дополнительные затраты в размере: по работе G - 4800 руб., по работе H - 3000 руб., по работе I - 1500 руб. и по работе K - 1600 руб.

Рис. 5 Предпочтительный график выполнения работ

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

Применение методики согласования интересов в процессе разработки мультимедийного приложения позволило снизить суммарные дополнительные затраты исполнителей на 35% и повысить общую эффективность выполнения работ по проекту. Результаты моделирования согласования интересов исполнителей работ по проекту были использованы в системе управления ООО «E-Style Software House» в 2010-2011 гг.

Таблица 2

Результаты функционирования системы при изменении внешних условий

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

Список литературы

1. Гулаков, В.К. Математическое обеспечение управления процессом согласования интересов субподрядчиков при выполнении работ по проекту / В.К.Гулаков, А.К.Буйвал, П.А.Паршиков // Вестн. БГТУ. 2010. №4. С.75-81.

2. Тарасов, В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика / В.Б.Тарасов. М.: Эдиториал УРСС, 2002. 352 с.

3. Швецов, А.Н. Агентно-ориентированные системы: от формальных моделей к промышленным приложениям / А.Н. Швецов. Вологда: ВоГТУ, 2000. 116 с.

4. Shoham, Y. Mulriagent systems: algorithmic, game-theretic and logical foundations / Y. Shoham, K. Leyton_Brown. London: Cambridge University Press, 2010. 513 p.

5. Городецкий, В.И. Многоагентные системы (обзор) / В.И. Городецкий, М.С. Грушинский, А.В. Хабалов // Новости искусственного интеллекта. 1998. №2. С. 23-57.

6. Wooldridge, M. Towards a Theory of Cooperative Problem Solving / M. Wooldridge, N. Jennings // Proceedings of the MAAMAW'94 / Ed. by Y. Demazeau, J.-P. Muller and J. Perram. London: ACM Press, 1994. P. 192-224.

7. Гулаков, В.К. Распределенный подход как метод оперативного управления проектом / В.К.Гулаков, А.К.Буйвал, П.А.Паршиков // Вестн. БГТУ. 2010. №1. С. 54-63.

8. Карпов, Ю.Г. Имитационное моделирование систем. Введение в моделирование с AnyLogic 5 / Ю.Г.Карпов. СПб.: БХВ-Петербург, 2005. 400 с.

Размещено на Allbest.ru