Взаимодействие, коммуникация, кооперация агентов

Помимо ранее рассмотренных представлений об агентах, объектах и средах, при разработке МАС необходимо предварительное определение и моделирование таких базовых теоретических понятий и характеристик, как взаимодействие, кооперация (сотрудничество), координация, организация, управление.

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

Для определения базовых типов взаимодействия агентов в МАС можно взять следующие критерии группообразования: а) совместимость целей агентов; б) потребность в чужом опыте (знаниях); в) совместное использование ресурсов. Тогда, если обозначить наличие указанных признаков знаком +, а их отсутствие — знаком, получаем восемь базовых ситуаций взаимодействия [72], сведенных в табл.2. Здесь граничный случай независимости агентов равносилен отсутствию МАС (полностью автономные агенты). Простое сотрудничество предполагает интеграцию опыта отдельных агентов (выражающуюся в распределении задач и обмене знаниями), когда не требуются дополнительные мероприятия по координации их действий. Непродуктивное сотрудничество реализует известную ситуацию «лебедя, рака и щуки» из басни И. А. Крылова, когда агенты, не имея потребности в опыте друг друга, но совместно используя.

Табл.2. К определению базовых ситуаций взаимодействия агентов

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

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

конкурирующие группы способствуют ликвидации монополий и расширению рынка услуг.

Диапазон реального взаимодействия агентов очень широк: в частности, на полярной шкале «конкуренция — кооперация» он может определяться парой чисел, характеризующих степень соперничества — сотрудничества, например, (1, 0) при полном антагонизме агентов и (0, 1) при полном сотрудничестве. Здесь средняя точка «серой» (по терминологии Д.А.Поспелова) шкалы (0.5, 0.5) есть точка наиболее противоречивого (двусмысленного) взаимодействия, а соответствующая точка разрыва на «черно-белой» шкале дает нам неопределенность (?, ?). Из этих соображений в результате получаем четырехзначную базовую логику взаимодействия. Удачный выбор исходного набора организационных критериев (базиса полярных шкал) и использование признака"централизация-децентрализация" позволяет социально структурировать МАС. Здесь исходными критериями могут быть, например, а) тип организации в зависимости от уровня согласования целей агентов (шкала унитарная — федеральная); б) тип управления (шкала иерархия — гетерархия); в) тип мировосприятия агентов (шкала эгоцентризм — полицентризм).

Понятие кооперации агентов играет центральную роль в МАС. Кооперация — это основная форма организации взаимодействия между агентами, характеризующаяся объединением их усилий для достижения совместной цели при одновременном разделении между ними функций, ролей и обязанностей. В общем случае это понятие можно определить формулой: кооперация = сотрудничество + координация действий + разрешение конфликтов (см. табл.2). Кооперацию можно рассматривать двояко: а) извне, с точки зрения внешнего для данной МАС наблюдателя; б) изнутри МАС как форму поведения агентов, решивших работать совместно. В первом случае, наблюдатель, начего не знающий о ментальных состояниях или намерениях агентов, стремится установить измеримые, квантифицируемые показатели кооперации. Здесь исходными критериями служат эффективность групповой деятельности агентов в МАС и наличие механизмов разрешения конфликтов.

Более детально, уровень кооперации агентов в МАС можно определить на основе следующих показателей [67]: 1) высокая степень распределения ресурсов (в том числе знаний); 2) избегание (или малая длительность конфликтов; 3) координация действий, включая согласование направления действий агентов в пространстве и во времени; 4) высокая степень запараллеливания (совмещения) задач, решаемых различными агентами; 5) неизбыточность действий, довольно малое число дублирующих, повторяющих друг друга действий; 5) устойчивость, понимаемая как способность МАС пережить отказ или потерю агента.

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

Во втором случае, когда кооперация как совместная деятельность отождествляется с формой преднамеренного поведения [55,78], базовую формулу можно записать в виде: кооперация = общая цель + обязательства агентов. Примерами использования подобной формы могут служить уставы различных ассоциаций, члены которых принимают общую цель и берут на себя обязательства совместно участвовать в некоторой работе. Очевидно, что кооперация зависит не только от установки, намерения сотрудничать, но и от поведения, а главное, от результатов совместной деятельности.

В контексте кооперации остановимся подробнее на вопросах распределения задач между агентами и согласования их действий. Можно указать три типичных способа централизованного распределения задач: 1) командное управление или система «господин-раб» (master-slave), когда агент-менеджер самостоятельно распределяет все задачи между заранее определенными агентами-исполнителями и контролирует их выполнение; 2) распределение по принципу торгов (или «объявление конкурса»), когда агент-менеджер распространяет объявление об общем задании, а потенциальные агенты-исполнители предлагают свои услуги, т. е. исполнители заранее не определены, а отбираются в результате конкурса; однако и распределение отдельных задач, и контроль остаются прерогативой менеджера; 3) распределение путем соревнования, когда агенты-исполнители дают свои предложения уже на уровне отдельных задач, т. е. происходит подбор исполнителя под конкретную задачу, а роль менеджера сводится к контролю и координации их действий.

Под координацией обычно понимается управление зависимостями между действиями [102]. Здесь возможны такие случаи как зависимость от общих ресурсов, зависимость из-за требования одновременности действий и пр.

Взаимодействия между агентами могут иметь различную степень сложности. К простейшим видам взаимодействия агентов относится их связь через сообщения от среды, как это делается в моделях коллективного поведения автоматов. Следующими по уровню сложности являются отношения взаимодействия между слабо персонофицированными агентами (например, на основе «доски объявлений»). Сложнее организовать коммуникацию между персонофицированными агентами. Здесь ведущую роль начинают играть отношения кооперации, координации и коалиции. В такие отношения вступают агенты, занятые решением общей задач или планирующие свою деятельность с учетом деятельности других агентов. И наконец, отношения неоднородности и конфликтности на множестве агентов. Переход от однородных агентов к взаимодействию неоднородных агентов позволяет решать задачи, который однородный коллектив в принципе решить не может, а конфликты в ряде случаев могут рассматриваться как положительное явление [12,78] при организации коллективного поведения агентов, способствуя достижению общей цели.

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

Механизм посылки сообщений был вначале исследован в рамках модели акторов [87,35]. Двумя важными преимуществами систем, основанных на акторах, являются модульная структура и локализация знаний (отсутствие глобальной базы знаний, доступной для всех акторов).

Механизм опосредованной коммуникации реализуется с помощью архитектуры «доски объявлений» (blackboard) [69,91] (рис.4). Здесь основная идея состоит в воспроизведении взаимодействия нескольких агентов посредством доски объявлений, на которой написаны все известные сведения и указаны решаемые задачи. Агенты в зависимости от их опыта пытаются заполнить доску объявлений. При этом доска объявлений рассматривается как промежуточный модуль — посредник для осуществления различных взаимодействий между агентами.

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

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

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

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

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

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

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

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

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

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

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

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

Соответственно, важнейшей сферой исследований в области коммуникации агентов является построение протоколов для ведения переговоров. К разработке протоколов обычно предъявляются следующие требования [44,120,121]: а) простота; б) децентрализация (переговоры осуществляются напрямую, без централизованного управления); в) симметричность (все агенты являются равноправными участниками переговоров); г) устойчивость (протоколы переговоров не должны позволять агентам, отклонившимся от установленных правил ведения переговоров, извлекать дополнительную пользу); д) эффективность (как по отношению к отдельным агентам, так и по отношению к их коалициям).

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

Построение протокола ведения переговоров включает три шага: 1) определение пространства возможных соглашений; б) введение правил взаимодействия (например, на основе теории речевых актов[39,122] в терминах «предложение — контрпредложение»); в) задание оптимальных стратегий агентов.

Классическими методами исследования переговорных процессов являются методы теории полезности и теории игр, в частности, известные модели и условия оптимальности, выраженные в виде принципов равновесия. Так принцип Парето применяется для сильно централизованных систем, подсистемы которых имеют широкие возможности обмена информацией о принимаемых решениях, а равновесие по Нэшу характеризует децентрализованные системы. Эти типы оптимальности имеют разные «идейные основания»: основой оптимальности по Нэшу является устойчивость системы, обусловленная интересами и возможностями отдельных подсистем, тогда как принцип оптимальности по Парето опирается на идею полезности, выгоды для системы в целом, понимаемой как выгода сразу для всех ее подсистем. С учетом вышеприведенных требований к разработке протоколов в МАС большее применение находит арбитражная схема Нэша или математически эквивалентная ей модель Зейтена [39]. Однако, эти схемы годятся далеко не всегда (например, равновесие по Нэшу не является исчерпывающим решением для некооперативных игр).

Наиболее распространенными специальными моделями коммуникации (кооперации) агентов в РИИ являются:

модель договорных (контрактных) сетей Смита протокол монотонных минимальных уступок (по Розеншайну и Злоткину) модель социальных зависимостей Кастельфранши и Контэ.

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

Множество схем организации переговоров в МАС можно представить себе как варианты описанной двусторонней модели (bilateral model), согласно которой переговорный процесс рассматривается как последовательность контрпредложений, выдвигаемых взаимодействующими агентами. Такой процесс может моделироваться как множество переходов в пространстве состояний.

В свою очередь, многосторонняя модель (multilateral model) рассматривается как множество двусторонних переговоров, описываемых, например, сетью Петри, т. е. сетью вида предикат/ переход.

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

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

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

В любых МАС центральную роль играют структуры управления и принятия решений. Управление определяет ограничения на взаимодействие между агентами, вид организации и характер эволюции МАС. Классическая структура управления предполагает субординацию агентов, т. е. способ заставить одних агентов выполнять поручения других. Иерархия отношений субординации представляет собой древовидную структуру. В противоположность этому в МАС могут вводиться и эгалитарные структуры, когда всякий агент может попросить любого другого агента выполнить некоторую задачу, и потенциальный исполнитель всегда может отказаться. Суть теории социальных зависимостей [49−51,55] заключается в том, что взаимодействие агентов рассматривается в контексте социальных зависимостей и властных отношений, которые считаются включенными в когнитивные структуры агентов. Теория социальных зависимостей в РИИ тесно связана с теорией обязательств (commitments) и основана на логике действий [54]. Осознание социальных зависимостей ведет к началу переговоров об обмене ресурсами (их купле-продаже) и принятию обязательств. Рассматриваются два основных типа зависимостей: по отношению к действию и по отношению к ресурсу.

Ниже изложим элементы теории организации применительно к МАС.