Координация поведения агентов в мультиагентной системе
Наиболее известными моделями координации поведения агентов являются: теоретико-игровые модели, модели коллективного поведения автоматов, модели планирования коллективного поведения, модели на основе BDI-архитектур (Belief – Desire – Intention), модели координации поведения на основе конкуренции.
Теоретико-игровые модели. Предметом теории игр являются задачи выбора решений в условиях неопределенности и конфликта. Наличие конфликта предполагает существование как минимум двух участников, которых называют игроками. Множество решений, возможных для выбора каждым игроком, называется стратегией. Равновесными точками игры (оптимальными решениями) называют такие состояния, когда ни одному из игроков невыгодно менять свою позицию. Понятие равновесия оказалось весьма полезным в теории MAC, поскольку механизм поиска равновесных ситуаций может использоваться как средство самоорганизации коллективного поведения агентов. Следствием подобной интерпретации является подход, в котором необходимые атрибуты коллективного поведения агентов обеспечиваются путем конструирования правил игры. Кроме того, на основе развития теории игр в области MAC предпринимаются попытки построения эффективных, устойчивых, полностью распределенных протоколов переговоров, направленных на координацию коллективного поведения агентов.
Множество возможных ситуаций выбора поведения пары агентов классифицируется следующим образом.
1. Симметричная кооперация, когда существует непустое множество стратегий (переговорное множество), при использовании которых оба агента достигают своих целей и получают больший эффект, чем в ситуациях, когда они действуют поодиночке.
2. Симметричный компромисс, когда достижение цели в одиночку более выгодно для каждого агента, однако невозможно в присутствии другого агента.
3. Несимметричная кооперация или несимметричный компромисс_– один из агентов может самостоятельно достичь своей цели в присутствии другого агента, а другой – только засчет кооперации с первым.
4. Конфликт – переговорное множество пусто, т.е. не существует стратегий, обеспечивающих достижение целей обоих агентов.
Теоретико-игровые модели позволяют для всех перечисленных случаев сконструировать наборы правил переговоров, следуя которым агенты придут к некоторому соглашению, отвечающему состоянию равновесия. Это достигается засчет использования множества дополнительных предположений и специальных приемов. Например, кроме стоимости цели в рассмотрение вводится понятие ценности цели, а в качестве одной из возможных стратегий может выступать стратегия манипулирования информацией о ценности целей (т.е. агенты могут сообщать друг другу заведомо ложные значения). При этом «нечестные» агенты могут либо увеличить свой доход, либо освободиться от части своей работы.
Модели коллективного поведения автоматов. Они основаны на идеях рандомизации, самоорганизации и полной распределенности. Модели этого типа подходят для построения протоколов переговоров в задачах, которые характеризуются большим количеством очень простых взаимодействий с неизвестными характеристиками.
Модели планирования коллективного поведения. Планирование может быть централизованным, частично централизованным или распределенным (децентрализованным). В последнем случае агенты сами принимают решения о выборе своих действий в процессе координации частных планов, всвязи с чем возникают вопросы о рациональной децентрализации, о возможности изменения целей при возникновении конфликтов, а также проблемы вычислительной сложности.
Модели на основе BDI-архитектур. В моделях этого класса применяются аксиоматические методы теории игр и логической парадигмы искусственного интеллекта. Для описания агентов используются логические средства, в том числе темпоральные и модальные логики. Акцент делается на описании интенсиональных понятий, таких, как убеждения (belief), желания (desire) и намерения (intention). Задача координации поведения агентов решается путем согласования результатов логического вывода в базах знаний отдельных агентов, полученных для текущего состояния внешней среды, в которой действуют агенты. Логический вывод осуществляется непосредственно в процессе функционирования агентов, что приводит к высокой сложности моделей, вычислительным трудностям и к проблемам, связанным с аксиоматическим описанием нетривиальных ситуаций, например, когда перед агентом возникает выбор между решением собственной задачи и выполнением обязательств по отношению к партнерам.
Модели на основе конкуренции. В моделях данного класса используется понятие аукцион в качестве механизма координации поведения агентов. Использование механизма аукциона основано на предположении о возможности явной передачи «полезности» от одного агента к другому или к агенту-аукционеру, причем эта полезность обычно имеет смысл денег.
Аукционы принято разделять на открытые и закрытые. В первом случае предлагаемые цены объявляются всем участникам. В закрытом аукционе о предлагаемых ценах знает только аукционер. Открытые аукционы различаются по способу проведения. В так называемых английских аукционах обычно задается стартовая цена, которая может увеличиваться участниками в ходе торгов. Побеждает тот, кто даст максимальную цену. Голландский аукцион начинается с верхней цены, которая постепенно снижается. Победителем считается тот, кто дал наибольшую текущую цену. Закрытые аукционы разделяют на аукционы первой и второй цены. В аукционах первой цены побеждает тот, кто предложил самую высокую цену, известную только аукционеру. В аукционах второй цены победитель определяется таким же способом, но платит за товар не свою цену, а вторую по величине. Теоретически доказано, что все разновидности аукционов эквивалентны для аукционера, однако практика показывает иное. Например, если участники аукциона не склонны к риску, то аукционер стимулирует повышение цены продажи при проведении голландского аукциона первой цены. Существуют варианты «групповых» аукционов, когда один или несколько участников представляют интересы группы, и в случае выигрыша проводится аукцион внутри группы. При этом на внутреннем аукционе товар продается по более высокой цене по сравнению с ценой внешнего аукциона. Полученная разница делится между участниками группы.
Сам по себе механизм аукциона не затрагивает способов принятия решений участниками. Решения могут приниматься на основе некоторой модели рассуждений, которая может использовать различные типы знаний, доступных агентам, и разнообразные способы их обработки.
Аукцион всегда должен заканчиваться. Для этого в стратегии его проведения должны быть заложены средства для разрешения возможных конфликтов (например, при наличии нескольких победителей). Одним из самых простых способов разрешения конфликтов является рандомизация, когда применяется случайный механизм выбора.