Лекция: КООРДИНАЦИЯ ПОВЕДЕНИЯ АГЕНТОВ В МУЛЬТИАГЕНТНОЙ СИСТЕМЕ.

Наиболее известными моделями координации поведения агентов являются: теоретико-игровые модели, модели коллек­тивного поведения автоматов, модели планирования коллектив­ного поведения, модели на основе ВDI -архитектур (Belief ­Desire — Intention), модели координации поведения на основе конкуренции.

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

В работе [24] множество возможных ситуаций выбора поведе­ния пары агентов классифицируется следующим образом.

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

2. Симметричный компромисс, когда достижение цели в оди­ночку более выгодно для каждого агента, однако невозможно в присутствии другого агента.

3. Несимметричная кооперация или несимметричный компро­мисс — один из агентов может самостоятельно достичь своей це­ли в присутствии другого агента, а другой — только за счет коопе­рации с первым.

4. Конфликт — переговорное множество пусто, т. е. не сущест­вует стратегий, обеспечивающих достижение целей обоих агентов.

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

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

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

Модели на основе BDI — архumекmур [12, 17]. В моделях этого класса применяются аксиоматические методы теории игр и логи­ческой парадигмы искусственного интеллекта. Для описания агентов используются логические средства, в том числе темпо­ральные логики. Акцент делается на описании ин­тенсиональных понятий, таких, как убеждения (belief), желания (desire) и намерения (intention). Задача координации поведения агентов решается путем согласования результатов логического вывода в базах знаний отдельных агентов, полученных для теку­щего состояния внешней среды, в которой действуют агенты. Ло­гический вывод осуществляется непосредственно в процессе функционирования агентов, что приводит к высокой сложности моделей, вычислительным трудностям и к проблемам, связан­ным с аксиоматическим описанием нетривиальных ситуаций, например, когда перед агентом возникает выбор между решени­ем собственной задачи и выполнением обязательств по отноше­нию к партнерам.

Модели на основе конкуренции. В моделях данного класса ис­пользуется понятие аукцион в качестве механизма координации поведения агентов. Использование механизма аукциона основано на предположении о возможности явной передачи «полезнос­ти» от одного агента к другому или к агенту-аукционеру, причем эта полезность обычно имеет смысл денег [4].

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

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

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

 

 

еще рефераты
Еще работы по информатике