Одноуровневая архитектура взаимодействия агентов

 

Ярким примером одноуровневой (полностью децентрализованной) архитектуры является архитектура системы для планирования совещаний (встреч) [6]. Это приложение является представителем довольно широкого круга задач, которые имеют много общего в формальной постановке. Это те задачи, которые имеют дело с динамическим составлением расписаний выполнения некоторого вида деятельности в условиях ограниченных ресурсов. Представителями задач подобного рода являются, например, задачи составления расписания обслуживания судов в морском порту [62], задачи диспетчерского обслуживания движения самолетов в аэропорту [39], планирование работ в гибких автоматизированных производствах [34] и ряд других.

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

В такой ситуации каждый участник предстоящей встречи представляется в процессе планирования своим агентом (“электронным секретарем”), который знает все о своем клиенте и совсем немного о других участниках встречи. Стратегия поиска решения в этом случае предполагает использование переговоров для поиска глобально согласованного решения. При этом, хотя агенты остаются равноправными участниками переговоров, каждому из них по специальному алгоритму назначается определенная роль, причем роли агентов могут динамически меняться. Поясним это кратко на примере [6].

1.Начальный вызов. Агент - инициатор встречи устанавливает контакт с агентами заданных участников потенциальной встречи для выяснения их интереса к ней, при этом он указывает параметры встречи: дату, время, длительность, тему. Каждый секретарь спрашивает своего пользователя о том, проявляет ли он интерес к встрече. Если пользователь отвечает положительно, то его секретарь отвечает инициатору встречи о заинтересованности и указывает при этом “фактор ограничений”, который рассчитывается как сумма весов уже запланированных встреч на тот период, который предлагает инициатор встречи. Веса формируются таким образом:

вес=1, если запланированная встреча может быть передвинута;

вес=2, если такая встреча передвинуты быть не может.

Если агент отказывается от встречи, то он просто удаляется из списка участников и далее не рассматривается в задаче планирования.

2.Схема переговоров. Самый простой случай - когда все согласившиеся встретиться агенты передали суммарный вес - фактор ограничений, равный 0. Это означает, что они принимают время, предложенное инициатором, и переговоры на этом завершаются.

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

Агент, который имеет наибольший фактор ограничений (он имеет меньше всех свободного времени для планируемой встречи и сокращает в наибольшей мере пространство поиска компромисса) получает статус МС (Most Constrained) и далее он берет на себя роль координатора переговоров. Фактически этому агенту назначается роль лидера в традиционной терминологии теории распределенных вычислений. Остальные агенты получают статусы МС2, МС3,... в порядке убывания их факторов ограниченности, последний из них - LC (Least Constrained).

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

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