Разработка и исследование моделей устойчивых коопераций в мультиагентных системах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

"о

СТ) На правах рукописи

О ®

Со ^ «V

О-

БРЛЙНОВ Святослав Брайнов

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

01.01.09 - Математическая кибернетика

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1998

Работа выполнена в Вычислительном Центре Российской Академии Наук

Научный руководитель: - доктор технических наук, доцент В.Ф.Хорошевский

Официальные оппоненты: доктор технических наук,

профессор В. И. Городецкий кандидат технических наук,

доцент В. Б. Тарасов

Ведущая организация: Институт Программных Систем РАН

Защита состоится 1998 года в 14 час. на заседании специализированного

совета К 002.32.01 при Вычислительном Центре Российской Академии Наук. Адрес совета: 117967, ГСП-1, г. Москва, ул. Вавилова, дом 40. С диссертацией можно ознакомиться в библиотеке института.

Автореферат разослан "2 5" 1998 года.

Ученый секретарь специализированного Совета, доктор физико-математических наук, член-шрр. РАН

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Если ранние исследования в области РИИ основывались на предположении о благонамеренности (benevolence) агентов, то современные работы однозначно ориентированы на эгоистических агентов (self-interested agents).

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

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

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

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

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

- Формализация понятия устойчивости и определение необходимых и достаточных условий стабильности мультиагентных соглашений.

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

- Исследование разработанных моделей поведения. В данной работе решаются следующие задачи:

1. Разработка формальной модели устойчивых по отклонениям мультиагентных планов.

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

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

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

5. Анализ результатов моделирования.

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

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

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

Научная новизна данной работы состоит в следующим:

1. Впервые в области РИИ разработана формальная модель устойчивых мультиагентных планов.

2. Впервые в области РИИ разработана формальная модель альтруистической кооперации в мультиагентных системах.

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

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

Апробация работы. Основные положения диссертации докладывались и обсуждались на следующих конференциях-.

Европейская конференция по искусственному интеллекту (ЕСАГ96, Будапешт, Венгрия); Рабочая конференция Empirical Artificial Intelligence'96 (Будапешт, 1996); Международная конференция Information Technologies and Programming'95 (Пловдив, Болгария); Европейская конференция по искусственному интеллекту (ЕСАГ94, Амстердам, Голландия); Международная конференция по искусственному интеллекту (AIMSA'94, София, Болгария); Международная конференция Information Technologies and Programming'94 (София, Болгария); и семинарах:

Отдела проблем искусственного интеллекта, Вычислительный центр, РАН (Москва, Россия, 1998); Исследовательского Центра Искусственного Интеллекта ИПС РАН (Переславль-Залесский, Россия, 1998); Института математики и информатики, БАН ( София, Болгария, 1997); Лаборатории по искусственному интеллекту, Свободный Университет (Брюссель, Бельгия, 1996); Департамента информатики, Университет Лимбург (Маастрихт, Голландия, 1996);

Публикации. Материалы диссертационной работы опубликованы в 5 печатных работах.

Диссертация состоит из введения, четырех глав, заключения, списка литературы и одного приложения. Основная часть диссертации содержит 122 страницы текста и 28 рисунков. Список цитированной литературы содержит 102 наименования.

СОДЕРЖАНИЕ РАБОТЫ Во введении приводится обоснование актуальности темы, формулируются цели и основные задачи исследования и кратко излагается содержание работы.

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

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

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

Кроме модели ведения переговоров, в первой главе рассматривается модель договорных сетей (contract nets), являющейся одной из самых ранних моделей кооперации в области РИИ. Анализируются основные недостатки модели договорных сетей и доказывается, что основной причиной этих недостатков является допущение об эгоистичности агентов.

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

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

Во второй главе представлено формальное описание разработанной модели устойчивых мультиагентных планов.

В данной работе будем придерживаться следующих условных обозначений. Множество N состоит из всех агентов, N - конечно и |N|=n. Отсюда следует, что мультиагентая среда закрыта и конечна. Цель агента i обозначим - g,. Пусть G, - множество всех состояний среды, которые удовлетворяют условиям цели g, где isN. Через (pi,P2,...,Pn) обозначим совместный план всех агентов для перехода от первоначального состояния среды S0, через промежуточные состояния S1, S2...,Sm'', к заключительному состоянию SmeGinG2 n...nG„. В записи совместного плана (pi,p2,.-->Pn) Pi означает индивидуальный подплан агента ieN.

Через Pi обозначим множество планов агента i, а через ft - множество всех состояний среды. Pj - конечно, a Q - счетно.

Пусть S - группа агентов, т.е. S - подмножество N. Через N-S обозначим дополнение множества S в N. В этих обозначениях совместный план (pi,P2,---.Pn) можно записать в следующем виде: (ps,Pn-s)> где ps - совместный план группы агентов S и рц-s - совместный план группы агентов N-S.

Функция полезности U, агента i определяется следующим образом:

U,(pi,... ,p„)=Worth1(Sn,)-Cost,(pi), (1)'

где: Worth, - функция ценности агента i, Cost, - функция расходов агента I, SraeG,nG2n...nG„ .

Функция Worthj определена на множестве О. , а функция Cost, - на множестве Р, . Обе функции принимают вещественные значения.

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

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

Определение 2. Назовем совместный план p=(pi,p2,. ..,Рп) устойчивым по отклонениям, если для любой группы агентов ScN н? существует эффективного отклонения, которое для всех членов группы S более выгодно, чем первоначальный план р при условии, что все остальные агенты N-S придерживаются плана р. Под эффективчым отклонением группы S подразумевается такое отклонение, которое не поддается дальнейшим отклонениям со стороны членов группы S.

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

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

Утверждение 1. Следующие условия являются достаточными для индивидуальной устойчивости плана р = (рьр,):

В работе доказывается, что если функции расходов обоих агентов убывают монотонно в цепочке состояний 5°,81, Б2...,в"1"1. Б"1 , то условия (2)-(5) являются и необходимыми для индивидуальной устойчивости.

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

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

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

Определение 8. Назовем кооперативную мультиагентную ситуацию полукооперативной, если в ней все совместные планы неустойчивы.

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

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

Утверждение 4. Пусть в эффективном совместном плане р двух агентов агент 1 зависит от агента j и агент j зависит от агента ¡, тогда план р индивидуально и коалиционно устойчив.

созиЭ0) > СОБ^ф,),

СОБ^') > СОЗ^(р,),

сов^Б^'^иКа/) > созг,(р,к+1), 1 < к < т-1

со5^(82к)-и,(а,к+1) > ссв^р^1), 1 < к 5 т-1

(2)

(3)

(4)

(5)

Обоюдная зависимость агентов является достаточным условием для устойчивости совместного плана:

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

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

Утверждение 9. Эффективный совместный план (р1,...,р„), построенный на зависимости агентов, является индивидуально устойчивым тогда и только тогда, когда он построен на взаимной зависимости агентов.

Утверждение 10. Если в совместном плане (рм-Ш) группа агентов 8сМ-] зависит от агента], то в этом плане любой член группы Э зависит от агента].

Последнее утверждгние нельзя обратить. Из того, что агент 1 зависит от группы агенов 8 не следует, что агент 1 зависит от каждого члена группы 8.

Из следующих двух утверждений видна взаимосвязь между понятиями устойчивости и групповой зависимости.

Утверждение 12. Если в эффективном совместном плане (р$д):

а) план р5 группы Б построен на взаимной зависимости агентов;

б) группа 8 зависит от агента];

в) агент] зависит от группы Б,

то план (ряд) индивидуально и коалиционно устойчив.

Утверждение 7 можно усилить следующим образом: Утверждение 13. Если в эффективном совместном плане (рз,р.|):

а) план р5 группы Б построен на взаимной зависимости агентов;

б) группа Б зависит от агента];

в) агент] зависит от агента ¡6 Б,

то план (р$,Р}) индивидуально и коалиционно устойчив.

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

Определение 23. Агента т назовем альтруистом по отношению к агентам 1,...,к, если выполняются следующие условия:

а) функция полезности агента т зависит от функций полезности агентов 1,... ,к;

б) для каждого ¡, 1<1<к, ит возрастает с возрастанием и, и ит убывает с убыванием

Определение 24. Агента т назовем эгоистом по отношению к агентам 1,...,к, если функция полезности иш агента т не зависит от функций полезности 1_1|,.. .,1^.

Определение 25. Агента т назовем завистливым по отношению к агентам 1,...,к, если выполняются следующие условия:

а) функция полезности агента т зависит от функций полезности агентов 1,...,к;

б) для каждого ¡, 1<1<к, ит убывает с возрастанием Ц и иш возрастает с убыванием Ц

В следующем определении вводится понятие степень альтруизма.

Определение 26. Пусть агент 1 является альтруистом по отношению к агенту ^ Предположим, что существует

ди аи,

ач(р)= — (р)/ т^-(р), где р - совместный план.

Назовем ау(р) степенью альтруизма агента 1 по отношению к агенту j в плане р. Агента 1 назовем:

- ориентированным на себя, если «ч(р)< 1;

- ориентированным на другого, если аи(р)>1;

- агентом с нейтральной ориентацией, если аи(р)=1.

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

Утверждение 14. Пусть:

Ц(р)='МогШ1^,)- СОБфЭ-ССцСОЗф), Ц(р)="\УогЛ^)- ал созЦр)- соэ^р), где р - совместный план двух агентов 1 и а,,, ач - константы и <хч, ач > 0. Тогда, если функции расходов обоих агентов дифференцируемы на множестве всех совместных планов Р, и существует совместный план р еР, который максимизирует одновременно функции полезности агентов 1 и], то: а„(р') а^(р*)=1.

Таким образом ориентации агентов взаимно дополняют друг друга.

Утверждение 14 нельзя перенести буквально на случай, когда множество совместных планов Р дискретно. Для получения аналогичного результата необходимо ввести дополнительные ограничения на множество Р.

Определение 27. Назовем множество всех совместных планов Р двух агентов i и j симметричным, если для каждого реР, существует р'еР, такой что: cost,(p')=costj(p), costj(p')=cost,(p).

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

Следующее утверждение является аналогом утверждения 14 для дискретного множества планов.

Утверждение 15. Пусть:

U,(p)=Worth,(gi)- cost,(p)-aijCostj(p),

U,(p)=Worthj(gj)- ccjj cost,(p> cost,(p), где p - совместный план двух агентов i и j и ац, щ - константы. Тогда, если множество всех совместных планов Р симметрично, и существует совместный план р'еР, который максимизирует одновременно функции полезности агентов i и j, то в этом плане оба агента не могут быть одновременно ориентированы на себя или одновременно ориентированы на другого.

В заключительной части третьей главы проведен формальный анализ переговоров с участием альтруистических и завистливых агентов. Предметом переговоров является цена контракта t - га сумма, которую агент i должен заплатить агенту j для выполнения задачи z. При определении t оба агента учитывают только расходы Cj агента j для выполнения задачи z. Предполагаем, что pt 2 с,.

Поведение альтруистического агента в ходе переговоров выявляется в следующем утверждении:

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

Аналогичным образом, для поведения завистливого агента в ходе переговоров получаем:

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

Проанализировано стратегическое взаимодействие покупателя i и продавца j при наличии неточной информации о стоимости pt задачи и расходов Cj для ее выполнения. Показано, что, если покупатель ведет переговоры с альтруистическим продавцом, то покупателю выгодно завысить стоимость задачи. Если покупатель ведет переговоры с завистливым продавцом, то покупателю выгодно объявить заниженную стоимость задачи. Данная ситуация проанализирована и с точки зрения продавца.

В диссертационной работе все вышеприведенные утверждения доказаны.

В четвертой главе приведен сравнительной анализ инструментальных средств для моделирования кооперации в распределенном искусственном интеллекте. Выделены основные преимущества и удобства применения экологическою программирования при разработке мультиагентных систем. Обоснован выбор экологического программирования в качестве основы мультиагентной модели в программной системе COOP. В системе COOP моделируется мультиагентное взаимодействие в условиях контролируемого эксперимента. При этом мультиагентная среда Е является квадратом с заданной координатной сеткой, в котором перемещаются агенты из множества N. Каждый агент располагает ограниченной возможностью воспринимать окружающую среду. Радиус восприятия одинаков для всех агентов. Множество пассивных объектов О состоит из фиксированного числа единиц питания. В начале каждого эксперимента единицы питания расположены случайным образом в квадрате Е. Единицы питания могут быть "съедены" агентами множества N. После "съедания", каждая единица питания воспроизводится в квадрате Е на случайном месте. Таким образом, независимо от действий агентов, количество единиц питания остается постоянным. Каждая единица питания обладает энергетической стоимостью. Энергетические стоимости всех единиц питания равны.

Агенты множества N выполняют следующие элементарные действия: стоят на месте, передвигаются в соседний квадрат координатной сети Е, "съедают" единицу питания.

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

Каждый агент характеризуется своим внутренним состоянием, которое представляется набором переменных и их значениями. Переменными внутреннего состояния являются: energy (задает уровень энергии каждого агента. После "съедания" единицы питания энергетический уровень агента увеличивается на энергетическую стоимость единицы питания. Если энергетический уровень падает до нуля, то агент погибает, т. е. его место в квадрате Е освобождается); hungry (задает энергетический уровень "голодного" агента); fed (задает энергетический уровень "сытого" агента); c_hungry (задает энергетический уровень, необходимый для выхода из коалиции); c_fed (задает энергетический уровень, необходимый для участия в коалиции); type (задает тип поведения агента).

Множество сообщений состоит го следующих элементов: Help (сообщение о помощи); Cooperate_With_Me (сообщение о желании вступить в коалицию).

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

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

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

В экспериментах проанализировано поведение различных популяций агентов. Дтя каждой популяции проведено 70 экспериментов на модели по 500 шагов каждый. В ходе эксперимента наблюдению подвергнуты 12 популяций, что составляет в общей сложности 840 экспериментов. Результаты экспериментов систематизированы и проанализированы с помощью системы Microsoft Excel.-

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

На рис. 1 изображены результаты моделирования для популяций Альтруист20-3, Альтруист10-3 и Эгоист20-3. Радиус восприятия агентов трех популяций равен трем. Параметр hungry для агентов первой популяции равен 20, для агентов второй популяции - 10, а для агентов третьей популяции - 20.

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

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

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

• Увеличение радиуса восприятия ухудшает выживаемость и суммарную энгргшо альтруистической популяции.

• Параметр hungry оказывает непосредственное влияние на выживаемость и суммарную энергию альтруистической популяции. При понижении стоимости параметра hungry активность популяции увел'¡читается и ее параметры улучшаются.

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

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

Рис. 1. Результаты моделирования для популяций Альтруист20-3, АльтруисгЮ-З иЭгонсг20-3

эгоистической популяции. Преимущества альтруистического поведения становятся более заметными в конкуренции с эгоистическим поведением.

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

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

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

В заключении рассмотрены основные результаты диссертации.

Приложение 1 содержит полный текст результатов моделирования Объем результатов составляет 15 таблиц и 34 графика..

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

При этом можно выделить следующие научные и практические результаты, полученные автором:

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

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

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

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

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

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

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

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

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

9. Проведенные эксперименты подтвердили функциональные возможности системы COOP для моделирования устойчивости мультиагентной кооперации и процесса оказания помощи.

По теме диссертации опубликованы следующее работы:

1. Brainov S., Altruistic Cooperation Between Self-interested Agents, In Proceedings of the 12th European Conference on Artificial intelligence, ECAI'96, Budapest, John Wiley & Sons, pp. 519-523,1996.

2. Brainov S., Stable Coalitional Structure of Multiagent Plans, In proceedings of 20th International Conference "Information Technologies and Programming", Sofia, pp.58-65, 1995

3. Brainov S., Deviation-Proof Plans in Open Multiagent Environments, In Proceedings of 11th European Conference on Artificial Intelligence ECAI'94, Amsterdam, John Wiley & Sons, pp. 274-278, 1994.

4. Brainov S., Reciprocal Commitments in Multiagent Plans, In Proceedings of 19th International Conference "Information Technologies and Programming", Sofia, pp. 77-83,1994.

5. Brainov S., Deviation-Proof Plans in Multiagent Environments In Proceedings of Sixth International Conference AIMSA'94, Sofia, 1994.