Мультиагентные системы и виртуальные организации

Любая многоагентная система включает следующие основные компоненты:

1) множество организационных единиц, в котором выделяются подмножество объектов и подмножество агентов, манипулирующих объектами;

2) множество задач;

3) окружающую среду, т. е. некоторое пространство, в котором существуют агенты и объекты;

4) множество отношений между агентами;

5) множество действий агентов (например, операций).

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

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

Важным разделом РИИ является кооперативное распределенное решение задач. Речь идет о сети слабо связанных между собой решателей, которые совместно работают в целях решения задач, выходящих за рамки их индивидуальных возможностей. Различные узлы подобной сети, как правило, имеют неодинаковый опыт (знания, точки зрения) и разные ресурсы. Каждый узел должен быть способен модифицировать свое поведение в зависимости от обстоятельств, а также планировать свои стратегии коммуникации и кооперации с другими узлами. Здесь показателями уровня кооперации являются: характер распределения задач, объединение различных точек зрения, возможность решения общей проблемы в заданное время.

Распределенное решение задач несколькими агентами разбивается на следующие этапы:

1) агент-менеджер (центральный орган) проводит декомпозицию исходной проблемы на отдельные задачи;

2) эти задачи распределяются между агентами-исполнителями;

3) каждый агент-исполнитель решает свою задачу, подчас также разделяя её на подзадачи;

4) для получения общего результата производится композиция, интеграция частных результатов, соответствующих выделенным задачам.

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

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

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

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

кооперация = сотрудничество + координация действий +
+ разрешение конфликтов.

Более детально уровень кооперации агентов в MAC можно определить на основе следующих показателей:

1) высокая степень распределения ресурсов (в том числе, знаний);

2) избегание (или малая длительность) конфликтов;

3) координация действий, включая согласование действий агентов в пространстве и во времени;

4) высокая степень запараллеливания (совмещения) задач, решаемых различными агентами;

5) неизбыточность действий, малое число дублирующих, повторяющих друг друга действий;

6) устойчивость, понимаемая как способность МАС пережить отказ или потерю агента.

Механизм опосредованной коммуникации реализуется с помощью архитектуры доски объявлений (blackboard). Здесь основная идея состоит в воспроизведении взаимодействия нескольких агентов посредством доски объявлений, на которой написаны все известные сведения и указаны решаемые задачи.

В принципе модель доски объявлений состоит из трех частей:

· источников знаний;

· структуры данных типа доски объявлений;

· управляющего компонента.

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

· модули стратегий, служащие для планирования и управления процессом принятия решения задачи;

· модули тактик (активации правил), обеспечивающие реализацию стратегий и выполнение действий.

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

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

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

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

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

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

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

Таким образом, механизм вывода состоит из двух компонент: список (последовательность) задач и монитор. В список (agenda – повестка) включаются все задачи, которые получены MAC в текущий период времени. В любой момент времени в нем содержатся все задачи, выполняемые на основе данных доски объявлений.

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

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

1) простота;

2) децентрализация (переговоры осуществляются напрямую, без централизованного управления);

3) симметричность (все агенты являются равноправными участниками переговоров;

4) устойчивость (протоколы переговоров не должны позволять агентам, отклонившимся от установленных правил ведения переговоров, извлекать дополнительную пользу);

5) эффективность (как по отношению к отдельным агентам, так и по отношению к их коалициям).

Построение протокола ведения переговоров включает три шага:

а) определение пространства возможных соглашений;

б) введение правил взаимодействия (например, на основании теории речевых актов в терминах предложение – контрпредложение;

в) задание оптимальных стратегий агентов.

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

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

С учетом вышеприведенных требований к разработке протоколов в MAC большее применение находит арбитражная схема Нэша или математически эквивалентная ей модель Зейтена.

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

В начале 1980-х годов Р. Смит разработал модель распределенного решения задач, названную им контрактной (договорной) сетью (contract net), которая и сегодня имеет большой резонанс. В основе модели договорных сетей лежит простейшая идея рыночных торгов. Имеются два типа агентов: агенты-менеджеры и агенты-исполнители (покупатели). Агент-менеджер распространяет объявление о задании и определяет исходную цену, а потенциальные агенты-исполнители предлагают услуги, посылая свои варианты цен, и подчас участвуют в конкурсе на определение наилучших предложений по исходному заданию. Затем агент-менеджер отбирает самые выгодные для него предложения и заключает соглашение с выбранными агентами-исполнителями, которые становятся агентами-подрядчиками.

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

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

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