2. Координация в многоагентных системах (мас).

Общие принципы координации в МАС

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

М.Месарович (1970) сформулировал три базовых принципа координации в МАС: прогнозирование, развязывание и оценка взаимодействий.

В основе большинства известных методов координации МАС, лежит понятие "совместных обязательств" (commitments) агентов, которое предполагает выполнение агентом действий, ведущих к достижению цели в интересах сообщества агентов. Одной из форм обязательств агента является его роль. Другое важное понятие - это общественные "соглашения" (conventions). Оно фиксирует условия, при которых обязательства выполняются, и обстоятельства, когда агент может или должен отказываться от исполнения взятых на себя обязательств.

Известна гипотеза, которая утверждает, что "все механизмы координации в МАС могут быть выражены в терминах (совместных) обязательств агентов и соглашений". Ее справедливость показана на примерах координации.

Пример 1: Управление воздушным движением в районе аэропорта и разрешение непредвиденных конфликтов.

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

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

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

3. Взаимодействие агентов.

Cамоорганизация и эмерджентность

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

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

1. Взаимодействия между индивидуумами через среду.

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

3. Запаздывающая отрицательная обратная связь (испарение феромона по времени)

4. Изменение поведения с увеличением количества феромона на пути к источнику пищи).

Основными чертами самоорганизации являются:

1. Автономность – взаимодействие в внешним миром допустимо, но недопустимо управление из внешнего мира

2. Адаптивность и робастность по отношению к изменениям – способность реагировать подходящим образом на изменения среды

3. Возрастание порядка – в соответствии с возрастанием организации системы (уменьшение числа состояний системы, появление пространственной, временной и функциональной структур; появление состояний системы на метауровне - аттракторов)

4. Динамика – самоорганизация есть процесс, но не какое-либо конечное состояние.

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

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

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

Сложные взаимодействия агентов. Аукционы.

Проведение аукционов является примером сложного взаимодействия агентов. Аукцион (лат. «повышаю») метод проведения торговли каким-либо товаром, ценными бумагами и т.д. Совсем не обязательно аукционы проходят с повышением цены. Аукцион – способ продажи , основанный на конкуренции. Для каждого участника аукциона ценности делятся на три вида: личная, общая и коррелированная ценность. Существуют 4 основных вида аукционов:

прямой (английский),

голландский (оптовый),

янки (своей цены),

обратный.

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

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

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

Название голландского аукциона происходит от рынка цветов в Голландии. Это оптовый аукцион, на котором продавец может выставлять много единиц товара одновременно. Покупатели могут претендовать на покупку многих единиц товара. Все выигравшие покупатели платят только минимальную из выигравших цен.

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

Биржи

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

Аукционы – это частный случай биржи. Администратор биржи определяет набор предметов M = {1, 2, …, m}, которые доступны для торговли.

Ставка (bid) – это совокупность вида

, где – количество предметов вещи i, - цена

Если p_j > 0, то ставка – это запрос на продажу, иначе – на покупку.

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

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