Механизмы координации
Простейший метод, с помощью которого группа агентов может обеспечить координацию при выполнении совместного плана, состоит в принятии определенного соглашения (convention) до начала совместной деятельности. Соглашением является любое ограничение, касающееся выбора совместных планов, выходящее за рамки того основного ограничения, в соответствии с которым совместный план должен работать, если ему следуют все агенты. Например, соглашение "придерживаться своей стороны поля" станет причиной того, что партнеры в парном теннисе выберут план 2, а соглашение, что "один игрок всегда остается у сетки", приведет их к плану 1. Некоторые соглашения, такие как вождение по правильной стороне дороги, приняты настолько широко, что считаются общественными законами. Естественные языки также могут рассматриваться как соглашения.
Соглашения, указанные в предыдущем абзаце, являются характерными для конкретной проблемной области и могут быть реализованы путем внесения в описания действий таких ограничений, которые позволили бы исключить нарушения соответствующего соглашения. Более общий подход состоит в использовании соглашений, независимых от проблемной области. Например, если каждый агент эксплуатирует один и тот же алгоритм многотельного планирования с одними и теми же входными данными, то может следовать соглашению о выполнении первого найденного осуществимого совместного плана и быть уверенным в том, что другие агенты сделают такой же выбор. Более надежная, но и более дорогостоящая стратегия могла бы состоять в том, чтобы выработать все совместные планы, а затем выбрать, например, тот из них, внешнее представление для вывода на печать которого находится на первом месте в алфавитном порядке.
Соглашения могут также возникать благодаря эволюционным процессам. Например, колонии общественных насекомых выполняют очень сложные совместные планы, а осуществление подобных действий к тому же обеспечивается благодаря общим генетическим характеристикам отдельных особей в этой колонии. Согласованность действий может также быть обусловлена тем фактом, что отход от соглашений приводит к уменьшению эволюционной приспособляемости всех особей, поэтому любой осуществимый совместный план может стать шагом к стабильному равновесию. Аналогичные условия распространяются и на процесс развития любого человеческого языка, когда важным становится не тот факт, на каком языке должен говорить каждый индивидуум, а тот факт, что все индивидуумы должны говорить на одном и тот же языке. Наш последний пример относится к тому, как ведут себя птицы, сбиваясь в стаи во время полета. Вполне приемлемая модель такого процесса может быть получена, если каждый птицеподобный агент (который иногда именуется орнитоидом или бондом от слова boid, или birdoid) выполняет три перечисленных ниже правила, применяя определенный метод их комбинирования.
1. Отделение. Направлять свой полет подальше от соседей, если ты начинаешь к ним слишком заметно приближаться.
2. Соединение в линию. Придерживаться направления полета, позволяющего занять среднюю позицию по отношению к соседям.
3. Выравнивание. Рулить в сторону средней ориентации (направления движения) соседей.
Если все птицы выполняют одни и те же описанные выше правила, то вся стая обнаруживает эмерджентное поведение (от слова emergent — появляющийся), совершая полет в виде одного псевдоустойчивого тела приблизительно с постоянной плотностью, которое не рассеивается со временем. Как и в случае общественных насекомых, для каждого агента не требуется обладание совместным планом, который моделировал бы действия других агентов.
Как правило, принимаются такие соглашения, которые охватывают целый универсум отдельных задач мультиагентного планирования, а не требуют разработки с нуля перед началом решения каждой новой задачи. Это может приводить к недостаточной гибкости и нарушениям в работе, как иногда можно наблюдать в парном теннисе, когда мяч пролетает приблизительно на равных расстояниях между двумя партнерами. В отсутствие применимого соглашения агенты могут использовать общение для получения общих знаний об осуществимом совместном плане. Например, в парном теннисе игрок может крикнуть "Мой!" или "Твой!", имея в виду мяч, чтобы указать на предпочтительный для него совместный план. Механизмы общения рассматриваются более подробно в главе 22, в которой отмечается, что общение не обязательно требует устного обмена репликами. Например, один игрок может неявно сообщить о предпочтительном совместном плане другому, просто выполнив его первую часть. В нашей задаче игры в теннис, если агент А направился к сетке, то агент В обязан отойти назад, к линии подачи, чтобы отбить мяч, поскольку план 2 является единственным совместным планом, который начинается с того, что агент А направляется к сетке. Такой подход к координированию действия, иногда называемый распознаванием плана (plan recognition), является применимым, если для безошибочного определения нужного совместного плана достаточно одного действия (или краткой последовательности действий).
Вся нагрузка по определению того, как агенты должны приходить к успешному совместному плану, может быть возложена либо на проектировщиков агентов, либо на самих агентов. В первом случае проектировщик агента должен доказать, что правила и стратегии агентов будут успешными, еще до того, как агенты приступят к планированию. Сами агенты смогут правильно и успешно реагировать на обстановку, если заложенные в них правила и стратегии применимы для той среды, в которой они существуют, и им не нужно иметь явные модели, описывающие действия других агентов. А в последнем случае агентам приходится больше рассуждать; они должны доказывать или демонстрировать другими способами, что их планы будут успешными, принимая во внимание рассуждения других агентов. Например, в среде с двумя логическими агентами, А и В, оба этих агента могут иметь следующее определение:
Vp, s Feasibleip, s) <=> CommonKnowledge ({А, В}, Achieves (p, s, Goal))
В нем указано, что в любой ситуации s план р представляет собой осуществимый совместный план в данной ситуации, если оба агента располагают знаниями о том, что план р позволяет достичь цели. Нам потребуются дополнительные аксиомы для формирования общих знаний о совместном намерении (joint intention) выполнить конкретный совместный план; только после этого агенты могут приступать к действиям.