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

МНОГОАГЕНТНЫЕ СИСТЕМЫ

(обзор)

В.И. Городецкий, М.С. Грушинский, А.В. Хабалов



Введение

агент поведение коллективный теория

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

Как отмечено в работе [30], первоначально идея интеллектуального посредника ("агента") “возникла в связи с желанием упростить стиль общения конечного пользователя с компьютерными программами, поскольку доминирующий, в основном, и ныне стиль взаимодействия пользователя с компьютером предполагает, что пользователь запускает задачу явным образом и управляет ее решением. Но это совершенно не подходит для неискушенного пользователя. Иначе говоря, сначала идея интеллектуального посредника возникла как попытка интеллектуализации пользовательского интерфейса.”

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

Главная особенность интерфейса, обеспечиваемого ПА, состоит в том, что этот интерфейс оказывается персонифицированным. Последнее достигается за счет того, что ПА наделяется способностью к обучению. В самом простом варианте, ПА получает информацию о привычках пользователя путем, как говорят, "подглядывания из-за плеча" за работой своего пользователя. Обучаясь интересам, привычкам и предпочтениям пользователя, а также окружающего его сообщества пользователей (это те, кто доступен персональному ассистенту через компьютерную сеть), ПА может стать весьма полезным, причем в различных аспектах: выполнять решение задач по поручению пользователя, тренировать его, управлять событиями и процедурами. Заметим, что по существу персонификация пользовательского интерфейса- это новый резерв его интеллектуализации, который удачно дополняет “интеллектуальность интерфейса”, которая традиционно ассоциируется только с экранными графическими средствами.

Исследования и экспериментальные программные разработки довольно быстро показали, что множество задач, в которых ПА с большой пользой может ассистировать пользователю, практически неограниченно: отбор информации, просмотр информации, поиск в Internet, управление электронной почтой, календарное планирование встреч, выбор книг, кино, музыки и т.д. Разработки в этой области поддерживались и поддерживаются такими известными фирмами, как Apple, Hewlett Packard, Digital, японскими фирмами. Метафора "персонального ассистента" была заменена метафорой "интеллектуального посредника", или, как стали чаще говорить на русском языке - "интеллектуального агента" (ИА).

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

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



1. Исследования в области многоагентных систем

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

-теория агентов, в которой рассматриваются формализмы и математические методы для описания рассуждений об агентах и для выражения желаемых свойств агентов;

-методы кооперации агентов (организации кооперативного поведения) в процессе совместного решения задач или при каких-либо других вариантах взаимодействия;

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

-языки программирования агентов;

-методы, языки и средства коммуникации агентов;

-методы и программные средства поддержки мобильности агентов (миграции агентов по сети).

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

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

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



2. Свойства агентов и терминология

В настоящее время вопрос о том, какую компьютерную программу следует квалифицировать как агента и/или многоагентную систему, находится в стадии интенсивного обсуждения. Причина такого интереса к этому вопросу объясняется тем, что исследователи в этой области опасаются, что термины “интеллектуальный агент” и “многоагентная система” станут расхожими терминами, как это по сути и случилось с термином “интеллектуальная система”. Этот вопрос обсуждался, в частности, на нескольких семинарах FIPA (Federation of Intelligent Physical Agents)-международной организации, созданной летом 1996 года и имеющей целью продвижение идей многоагентных систем в область практических приложений. В частности, на Токийской встрече в октябре 1996 года мнение FIPA по этому вопросу сформулировано следующим образом Приводимый в материалах FIPA по этому поводу материал в значительной мере повторяет точку зрения, изложенную в работе [58], возможно потому, что автор указанной работы является одним из директоров FIPA. Тем не менее, здесь мы предпочитаем ссылаться на “более официальный” документ. [www:15]:

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

Принято различать два определения интеллектуального агента - “слабое” и “сильное”[www:15, 58].

Под интеллектуальным агентом в слабом смысле понимается программно или аппаратно реализованная система, которая обладает такими свойствами:

-автономность - способность ИА функционировать без вмешательства человека и при этом осуществлять самоконтроль над своими действиями и внутренним состоянием;

-общественное поведение (social ability) - способность функционировать в сообществе с другими агентами, обмениваясь с ними сообщениями с помощью некоторого общепонятного языка коммуникаций;

-реактивность (reactivity) - способность воспринимать состояние среды и своевременно отвечать (реагировать) на те изменения, которые в ней происходят;

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

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

-знания (knowledge) - это постоянная часть знаний агента о себе, среде и других агентах, т.е. та часть, которая не изменяется в процессе его функционирования;

-убеждения (beliefs, вера) - знания агента о среде, в частности, о других агентах; это те знания, которые могут изменяться во времени и становиться неверными, однако агент может не иметь об этом информации и продолжать оставаться в убеждении, что на них можно основывать свои выводы;

-желания (desires) - это состояния, ситуации, достижение которых по разным причинам является для агента желательным, однако они могут быть противоречивыми и потому агент не ожидает, что все они будут достигнуты;

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

-цели (goals) - конкретное множество конечных и промежуточных состояний, достижение которые агент принял в качестве текущей стратегии поведения;

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

Первые два из перечисленных понятий называют “позицией агента”, его “точкой зрения” (attitudes), остальные характеризуют в англоязычной литературе общим термином “pro-attitude”, суть которого в том, что они “направляют” поведение агента таким образом, чтобы сделать отвечающие данному термину содержательные и формальные утверждения истинными Аналог этого термина на русском языке в краткой, понятной и адекватной форме еще предстоит найти..

Некоторые авторы считают, что агент должен обладать также рядом других свойств. К ним относятся [www:15, 58]

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

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

-правдивость (veracity) - свойство агента не манипулировать информацией, про которую ему заведомо известно, что она ложна;

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

Можно заметить, что исследователи в области многоагентных систем заходят очень далеко в проведении антропоморфного взгляда на интеллектуальных агентов. Это сходно с позицией первых исследователей в области искусственного интеллекта в 50-60-е годы, и эта позиция, по-видимому, в ближайшее время будет, с одной стороны, источником некоторых разочарований среди специалистов, которые предпринимают активные попытки построения формальных моделей перечисленного множества ментальных свойств, а с другой стороны- объектом традиционной критики со стороны философов, как это уже не раз было с искусственным интеллектом [64].

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

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



3. Теория агентов

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

Рассмотрим вопрос о моделях ментальных понятий. Первые попытки построить такие модели базировались на языках исчисления предикатов первого порядка, однако они не оказались удачными. Можно привести пример, из которого становится очевидным неадекватность исчисления предикатов первого порядка для формализации ментальных понятий Этот пример фактически взят из работы [58] , однако в нем изменена семантическая интерпретация.. Например, мы хотим представить формальную модель утверждения "Агент А убежден, что агент Б имеет информацию X“:

Bel( Aгент_А, Имеет(Агент_Б, X)).

Очевидно, что приведенная формула не является правильно построенной формулой исчисления предикатов первого порядка, поскольку вторым аргументом предиката Bel(*,*) является, в свою очередь, предикат. Однако это чисто синтаксическая проблема и она преодолевается, например, использованием мета-языка. Но есть потенциально и еще гораздо более серьезная семантическая проблема. Например, предположим, что некий третий агент имеет информацию Y, имя которой является другим именем той же информации X. Тогда допустимое для предикатов первого порядка равенство (X=Y) приводит в нем к выводу:

Bel( Aгент_А, Имеет(Агент_Б, Y)).

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

Очевидно, что отмеченные выше трудности объясняются тем, что ментальные понятия, вообще говоря, сами по себе являются, как отмечено в работе [58], относительно “темными”, “неясными”, “в которых стандартные правила подстановки исчисления предикатов первого порядка вообще не работают”.

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

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

-использование мета-языков (имеется в виду многосортная логика первого порядка с термами, которые обозначают формулы других языков, при этом ментальные понятия представляются предикатами мета-языка);

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

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

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

Семантика множества возможных миров хорошо известна и восходит к работам [24, 27]. В этой семантике ментальные понятия интерпретируются множеством возможных миров и отношением достижимости (доступности) между ними. С каждым возможным миром ассоциируется некоторая теория (множество формул и атомарных предикатов- фактов, про которые известно, что они истинны). Например [58], если один их игроков в покер получил какую-то карту, скажем, пиковую даму, то он может сделать некоторые выводы о допустимых н недопустимых раскладах карт у других игроков, и множество всех допустимых раскладов карт образует возможный мир игрока (агента) А для теории “Игрок (агент) А получил пиковую даму”. Другое дело, что построить такое множество раскладов и им руководствоваться в своей стратегии для игрока (агента) А нереально.

Представляется, что семантика возможных миров сложна для применения в практических задачах многоагентных систем, что видно уже из приведенного только что примера. Семантика множества возможных миров предполагает по умолчанию так называемое “логическое всеведение” (“logical omniscience'), т.е. предположение о том, что агенту на любом шаге выбора решения доступно все, что истинно в каждом возможном мире (может быть выведено из теории). Тем не менее, в ряде формализаций, одна их которых рассматривается ниже в данном разделе, используется именно такой подход к заданию семантики.

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

С эволюцией взглядов на формализацию синтаксиса и семантики языков описания ментальных понятий можно познакомиться кратко по работе [58], хотя с автором можно соглашаться не во всем.

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

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

Авторы называют убеждения информационной компонентой состояния агента, желания- мотивационным состоянием (компонентой), а намерения - его “рассудительной” (deliberative)Термин, для которого пока не удалось найти более точного аналога в русском языке. компонентой. Приведем небольшой пример, построенный по аналогии с примером из работы [19], для того, чтобы пояснить с помощью семантики возможных миров содержание названных компонент ментального состояния агента.

Пусть некий месье Жилизю, который в настоящее время является Председателем оппозиционной партии, имеет желание перейти в Правительство. При этом может заручиться поддержкой партии или действовать самостоятельно. Партия может поддержать его действие (“Да”) или не поддержать (“Нет”), причем при удаче он должен будет покинуть место председателя партии, а при неудаче “товарищи по партии” могут не простить ему такую попытку, и тогда месье Жилизю должен будет покинуть политику вообще.

На рис.1 представлено дерево решений. В этом дереве имеются три вида вершин:

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

-недетерминированные, в которых решения принимает “внешняя среда” (они обозначены квадратами) и

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

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

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

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



Рис.1. Обычное дерево решений

недетерминированным действиям среды (“склеивая дуги” входящую в такой узел и выходящую из него) и фиксируя вероятности соответствующих исходов как вероятности возможных миров. Эти возможные миры с сопоставленными им вероятностями представлены на рис.2.

Рис.2.Возможные миры для убеждений



Рис.3. Возможные миры для желаний

Рис.4.Возможные миры для намерений

Множество возможных (достижимых) миров для желаний отличается от таковых для убеждений тем, что, во-первых, отлучение от политики (соответствующий узел помечен на рис.2 меткой “пенсия”) не является желаемым состоянием для месье Жилизю, а во-вторых, в этих мирах терминальным узлам ставится в соответствие еще значение функции выгоды. Множество возможных (достижимых) миров для желаний изображено на рис.3.

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

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

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

Язык этой логики включает в себя традиционные компоненты:

-непустое множество примитивных пропозиций ;

-пропозициональные связки и ;

-модальные операторы (“агент убежден, верит”), (“агент желает”) и (“агент намерен”);

-временные операторы (“следующий”), ("до тех пор, пока"), (“когда-нибудь в будущем”), (“некоторый путь в будущем”).

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

Правильно построенные формулы языка вводятся практически обычным образом с некоторыми особенностями, которые к цели данного описания особого отношения н имеют. Далее авторы вводят семантику возможных миров, на формальной стороне которой здесь нет смысла останавливаться, а суть ее может быть пояснена вышеприведенным примером (см. рис.2-4). Не будем также останавливаться на той части аксиоматизации, которая относится к правилам манипуляций с временными операторами. Остановимся лишь на аксиоматике модальных операторов.

Аксиоматика на операторах убеждения, желания и намерения включает в себя следующие группы аксиом.

K-аксиомы:

G-аксиомы (аксиомы обобщения - “каждая тождественно истинная формула содержится в убеждениях, желаниях и намерениях агента”):

|- then |-,

|- then |-,

|- then |-.

Следующие три аксиомы выражают непротиворечивость убеждений (D-аксиома), позитивную (4-аксиома - в терминологии авторов) и негативную (5-аксиома - тоже в терминологии авторов) способность агента к интроспекции (убеждений о своих убеждениях):

(D)

(4)

Непротиворечивость желаний и намерений выражается следующей парой так называемых D-аксиом:

,

.

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

Интересным является вопрос о формальных отношениях, в которых могут находиться ментальные понятия. Принято [19] различать два типа отношений между ними. Одно из них- это теоретико-множественное отношение порядка, а другое- структурное отношение порядка. Возможные варианты теоретико-множественных отношений для пары ментальных понятий - “убеждения- желания” приведены на рис.5 а,б,в,г.

а) б) в) г)

Рис.5.Теоретико множественные отношения миров ментальных понятий

Рис.5а отвечает случаю, когда множество желаемых миров является подмножеством тех, в возможности которых агент убежден. Например, агент убежден, что он может “разбогатеть”, если будет играть в “Русское лото” и стать “бедным”, если вложит средства в разведение винного сорта кукурузы в условиях вечной мерзлоты Он может быть ярым сторонником идей партии начала 60-х годов с коммерческой жилкой современных демократов.. Очевидно, что второй путь для него не включается в множество его желаний. Вариант б) отвечает случаю, когда не все желаемые миры таковы, что агент убежден в их достижимости. Например, агент может желать разбогатеть, играя в “Русское лото” или победив на выборах в губернаторы г.Москвы. Однако, он не убежден, что второй вариант для него достижим. Аналогичные примеры можно привести и для двух других оставшихся вариантов- в) и г), хотя последний из них не имеет практического смысла. Очевидно, что такие же теоретико-множественные отношения могут быть заданы и для пар “желания- намерения” и “убеждения-намерения”.

Рассмотрим теперь структурные отношения порядка. Эти отношения определяются в связи с тем, что убеждения, желания и намерения могут представлять собой древовидные структуры, последовательность ветвей которых отвечает последовательности дискретных моментов времени, т.е. ментальные понятия в возможном мире являются временными деревьями. Четыре варианта таких отношений приведены на рис. 6 а, б, в и г (рисунок заимствован из работы [19]).

а) б)

в) г)

Рис.6. Структурные отношения на ментальных понятиях - временных деревьях

На рис. 6а представлен вариант, когда Desire- возможный мир является под-миром возможного мира убеждений. Рис. 6б отвечает обратному отношению. В случае, представленном на рис.6в, эти миры совпадают, а на рис.6г миры несравнимы.

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

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



4. Коллективное поведение агентов

Идея многоагентности предполагает кооперацию агентов при коллективном решении задач. В многоагентной системе aгент, который не способен решить некоторую задачу самостоятельно, может обратиться к другим агентам. Другой вариант, когда необходима кооперация- это использование коллектива агентов для решения одной общей трудной задачи. При этом агенты могут строить планы действий, основываясь уже не только на своих возможностях, но и “думать” о планах и намерениях других агентов. Известно, что коллективы даже простейших автоматов, в которых каждый автомат преследует только свои примитивные цели, в целом способны решать очень сложные задачи [61]. В качестве иллюстрации можно взять, например, пчелиный улей или муравейник. Можно надеяться, что система, в которой агенты могут учитывать планы и интересы других агентов, будет являться во многих случаях еще более гибкой.

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



4.1 Модели коллективного поведения

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

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

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

Теория игр [29, 37, 60]. Аппарат теории игр часто используется для исследования коллективов интеллектуальных агентов. Многие ситуации, возникающие в многоагентной системе, находят подходящие аналоги в теории игр. Исследуются кооперативные игры, различные стратегии ведения торгов (переговоров), игры в размещения и др., которые являются аналогами ряда моделей коллективного поведения агентов.

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

Биологические, экономические и социальные модели.

В последние годы координацией агентов наиболее интенсивно занимаются в сообществе исследователей распределенного искусственного интеллекта. Значительное множество работ посвящено исследованию коллективного поведения агентов в процессе совместного решения задач в рамках Belief-Desire-Intention (BDI)- архитектур (см. разделы 2, 3 и 5 данной работы).

Рассмотрим кратко различные модели кооперации агентов.

Модель кооперативного решения проблем (CPS) [57]. Эта модель рассматривает взаимодействие агентов, построенных согласно BDI-архитектуре. В модели ментальные понятия формализуются с помощью операторов временной логики. Используя формализм временной логики, в этих работах вводятся определения для таких понятий, как потенциал для кооперации, групповые действия, достижимость цели агентом и т. д. Остановимся на этих понятиях подробнее.

В процессе формирования кооперативного решения в рамках рассматриваемой CPS-модели [57] выделяют четыре этапа:

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

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

Формирование совместного плана. Это та стадия, на которой агенты переговариваются с целью выработать совместный план, который по их убеждению приведет к желаемой цели.

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

Рассмотрим кратко суть перечисленных этапов.

Распознавание основывается на определении потенциала для кооперации агентов [57]:

По отношению к цели f агента i имеется потенциал для кооперации тогда и только тогда, когда (1) имеется некоторая группа g, такая, что i верит, что g может совместно достичь f, и, либо (2) i не может достичь f в изоляции, либо (3) i верит, что для каждого действия a, которое он мог бы выполнить для достижения цели f, он имеет иную цель, влекущую невыполнение действия a.

К сожалению, формальные процедуры распознавания наличия потенциала для кооперации авторы работы [57] не рассматривают.

Формирование группы агентов описано в работе [57]. Неформально, процедура образования группы заключается в том, что агент i (имеющий цель f), у которого имеется потенциал для кооперации с группой g, пытается реализовать в группе g состояние, в котором группа может совместно достичь цели f, и в котором группа g обязуется выполнять действия совместно в соответствии со своими обязательствами.

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

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

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

Более подробное описание рассмотренной модели можно найти в работах [56, 57].

4.2 Конфликты в многоагентных системах

Возможность возникновения конфликтов в многоагентной среде является неизбежным следствием децентрализованности таких систем. Локальные убеждения одного агента могут, например, противоречить убеждениям других агентов. Агент может сформировать цель, которая будет конфликтовать с целями других агентов. При этом под конфликтом, обычно, понимают ситуацию, в которой возникает противоречие вида p q false, где p и q - убеждения агентов.

Основными типами конфликтов в многоагентных системах являются:

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

Конфликты, обусловленные неполнотой имеющейся у агента модели окружающего мира и моделей других агентов. Последние конфликты принято связывать с понятием рефлексии агента. Проблемы рефлексии (безотносительно к интеллектуальным агентам) исследуются в работе [65]. Упомянутая работа дает достаточно адекватные способы описания конфликтов данного вида, которые, однако, в настоящее время в известных работах эти модели вообще не принимаются во внимание.

Конфликты связанные с конкуренцией за совместные ресурсы или конфликты, связанные с наличием противоречивости целей.

Под разрешением конфликта понимается снятие логического противоречия вида p q false за счет отбрасывания одной из альтернатив в соответствии с некоторым критерием, или смены p и q вместе. Существует множество различных механизмов разрешения конфликтов, как например:

разрешение конфликтов с использованием централизованного механизма (например, при наличии арбитра);

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

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

Рассмотрим более подробно несколько примеров.

Механизм разрешения конфликтов, основанный на модели убеждений с приоритетами. При этом варианте агенты обмениваются информацией с целью достичь соглашения. Когда агент получает информацию, несовместимую с его локальными убеждениями, он либо отвергает ее, либо принимает, отбрасывая собственные убеждения. Имеется несколько типов метрик для определения силы убеждения, например, основанные на функции полезности [60], шкалированные величины. Механизм разрешения конфликтов, предложенный в [50], использует символьное шкалирование приоритетов убеждений. Убеждениям ставятся в соответствие приоритеты трех уровней: ограничения (constraints), предпочтения (preferences) и гипотезы (options).

Для убеждения Q степень доверия BD есть одно из следующих значений: BD(Q) {N, P, O, U}, где N (от necessarily) означает, что Q - необходимо истинно, P (oт preferably): Q - предпочтительное убеждение, O (oт optionally): Q - возможное убеждение, U: Q есть ложь. Над множеством {N, P, O, U}, определены [...] операции Е и Д, cогласно следующим таблицам:

Д

N

P

O

U

Е

N

P

O

U

N

N

P

O

U

N

N

N

N

N

P

P

P

O

U

P

N

P

P

P

O

O

O

O

U

O

N

P

O

O

U

U

U

U

U

U

N

P

O

U

Тогда, например, BD(P Q) = BD(P) Е BD(Q).

Другим возможным вариантом является механизм разрешения конфликтов с помощью введения уровней компетентности агентов [4], в соответствии с которым упорядочиваются их убеждения. Приведем определение уровня доверия к убеждению b, заимствованное из работы [4]:

Если:

b1 есть убеждение агента a1, имеющего цель в роли r1, такое, что b1 требуется для достижения этой цели, и

b2 есть убеждение агента a2, имеющего цель в роли r2, такое, что b2 необходимо для достижения этой цели, и

b1 конфликтует с b2,

Тогда:

b1 имеет больший уровень доверия, чем b2 тогда, и только тогда, когда, в соответствии с уровнем компетентности (a2 r2) < (a1 r1), или, иными словами, агент a1, играющий роль r1, более компетентен, чем a2 в роли r2.

4.3 Протоколы и языки координации

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

Теория речевых актов (Speech Act Theory, см. [51]). Переговоры строятся с использованием небольшого числа примитивов, например, ASK, TELL, REJECT, REQUEST, COMMIT, NEGOTIATE. Процесс переговоров начинается тогда, когда агент посылает сообщение, содержащее его точку зрения (позицию, attitude) по некоторому вопросу. Посредством обмена cообщениями ASK, TELL, REJECT агенты могут обсуждать некоторую тему и приходить к общему решению. Во время переговоров агенты обновляют свои базы знаний и, тем самым, повышают свои способности отвечать на новые запросы.

Протокол контрактных сетей (Contract Net Protocol) [45, 46] предназначен для координации в системах распределенного решения проблем. Каждый узел контрактной сети способен выполнять определенные задачи. Если в процессе решения один узел (заказчик) не в состоянии решить некоторую задачу, он ищет другой подходящий узел, который способен ее решить. При этом он рассылает объявление потенциальным подрядчикам (contractors) о вакансии на выполнение некоторого договора. Если на это объявление отвечают несколько узлов, то заказчик, пользуясь некоторым критерием, выбирает наиболее подходящего подрядчика. Посредством торгов заказчик и подрядчик заключают договор (contract). Вариации этого протокола используются в так называемых “электронных предприятиях” (electronic enterprises).

СOOL (COOrdination Language) [4, 5] язык во многом схожий с языком KQML (см. Раздел 6), предназначенный для управления совместными действиями. Важнейшими конструкциями языка являются планы переговоров, определяющие состояния и правила переговоров (conversation rules), и переговоры, определяющие текущее состояние плана, исполняемого в конкретный момент. Агенты могут иметь активными несколько переговоров и управлять их переключением и приостановкой, а также динамически создавать дочерние переговоры.

UNP (Unified Negotiation Protocol) описан в работе [60]. В указанной работе приводится механизм разрешения конфликтов, который позволяет повысить суммарную полезность, достигаемую агентами. Рассматриваются конфликтные ситуации, для разрешения которых используется “бросание монетки”, т.е. механизм рандомизации. При этом, в зависимости от того, кто выигрывает жребий, удовлетворяются цели либо обоих агентов, либо только одного. Для подобных ситуаций авторы используют термин "полукооперативная сделка". В условиях полукооперативных сделок агенты могут повысить суммарную полезность, договорившись о координировании совместных действий.



5. Архитектура многоагентных систем

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

При выборе архитектуры многоагентной системы необходимо иметь в виду два ее аспекта:

-архитектуру, поддерживающую методы взаимодействия агентов в процессе функционирования системы в целом, и

-архитектуру отдельного агента.

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

...