Координация поведения агентов в мультиагентной системе

В процессе моделирования коллективной работы агентов воз­никает множество проблем:

• распознавание необходимости кооперации;

• выбор подходящих партнеров;

• возможность учета интересов партнеров;

• организация переговоров о совместных действиях;

• формирование планов совместных действий;

• синхронизация совместных действий;

• декомпозиция задач и разделение обязанностей;

• выявление конфликтующих целей;

• конкуренция за совместные ресурсы;

• формирование правил поведения в коллективе;

• обучение поведению в коллективе и т. д.

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

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

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

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

4. Реализация рефлексивного управления, сущность кото­рого заключается в том, чтобы заставить субъекта осознанно под­чиняться влиянию извне, т. е. сформировать у него такие жела­ния и намерения (интенции), которые совпадают с требованиями окружения.

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

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

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

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

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

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

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

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

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