Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 166

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 166)

А иногда как раз и требуются одновременные действия, например, если портативный холодильник, заполненный напитками, смогут отнести на теннисный корт только два агента. В описании для этого действия должно быть сказано, что агент А не сможет выполнить действие Оассу, если нет другого агента, В, который одновременно выполнил бы лействие Сарау применительно к тому же холодильнику: 608 Часть 1Ч. Планирование Асс1оп(оатту(А, соо1ег, Сопспггепт: Пагху(В, Ргесопсн Ае(А, Лете) Вггесг: Ат(А, ГЛете) АЕ(соо1ет, Лете, слете), соо1ег, Лете, слете), л АГ(соо1ет, Лете) л Соо1ег(соо1ет), л АГ(соо1ет, слеге) л — АЕ(А, Лете) л Лете)) При использовании такого представления появляется возможность создать планировщик, который весьма напоминает планировщик с частичным упорядочением, действующий по алгоритму РОР.

Но между этими двумя планировщиками существуют три различия, которые описаны ниже. 1. Кроме отношения временного упорядочения л -~ В разрешается использовать отношения л = В и А -л В, которые означают одновременно и "прежде или одновременно", соответственно. 2. Если какое-то новое действие требует одновременных действий, необходимо конкретизировать эти действия, используя новые или существующие действия в плане.

3. Запрещенные одновременные действия являются дополнительным источником ограничений. Каждое ограничение должно быть разрешено путем наложения на конфликтующие действия таких ограничений, чтобы они могли быть выполнены либо прежде, либо позже другого конфликтующего действия. Такое представление позволяет создать алгоритм планирования для многотельных проблемных областей, эквивалентный алгоритму РОР.

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

Соглашением является любое ограничение, касающееся выбора совместных планов, выходящее за рамки того основного ограничения, в соответствии с которым совместный план должен работать, если ему следуют все агенты. Например, соглашение "придерживаться своей стороны поля" станет причиной того, что партнеры в парном теннисе выберут план 2, а соглашение, что "один игрок всегда остается у сетки", приведет их к плану 1. Некоторые соглашения, такие как вождение по правильной стороне дороги, приняты настолько широко, что считаются 'а.

общественными законами. Естественные языки также могут рассматриваться как соглашения. Соглашения, указанные в предыдущем абзаце, являются характерными для конкретной проблемной области и могут быть реализованы путем внесения в описания действий таких ограничений, которые позволили бы исключить нарушения соответствующего соглашения. Более общий подход состоит в использовании соглашений, независимых от проблемной области. Например, если каждый агент эксплуатирует один и тот же алгоритм многотельного планирования с одними и теми же входными данными, то может следовать соглашению о выполнении первого найденного осу- Глава 12.

Планирование и осуществление действий в реальном мире 609 шествимого совместного плана и быть уверенным в том, что другие агенты сделают такой же выбор. Более надежная, но и более дорогостоящая стратегия могла бы состоять в том, чтобы выработать все совместные планы, а затем выбрать, например, тот из них, внешнее представление для вывода на печать которого находится на первом месте в алфавитном порядке. Соглашения могут также возникать благодаря эволюционным процессам. Например, колонии обгцественных насекомых выполняют очень сложные совместные планы, а осуществление подобных действий к тому же обеспечивается благодаря общим генетическим характеристикам отдельных особей в этой колонии. Согласованность действий может также быть обусловлена тем фактом, что отход от соглашений приводит к уменьшению эволюционной приспособляемости всех особей, поэтому любой осуьцествимый совместный план может стать шагом к стабильному равновесию.

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

Вполне приемлемая модель такого процесса может быть получена, если каждый птицеподобный агент (который иногда именуется орлитоидом или 'ж бондом от слова ЬоЫ, или Ь1гдоЫ) выполняет три перечисленных ниже правила, применяя определенный метод их комбинирования. 1. Отделение. Направлять свой полет подальше от соседей, если ты начинаешь к ним слишком заметно приближаться. 2.

Соединение в линию. Придерживаться направления полета, позволяющего занять среднюю позицию по отношению к соседям. 3. Выравнивание. Рулить в сторону средней ориентации (направления движения) соседей. Если все птицы выполняют одни и те же описанные выше правила, то вся стая обнаруживает Ж эмерджентное поведение (от слова ешегяепг — появляющийся), совершая полет в виде одного псевдоустойчивого тела приблизительно с постоянной плотностью, которое не рассеивается со временем. Как и в случае общественных насекомых, д~и каждого агента не требуется обладание совместным планом, который моделировал бы действия других агентов.

Как правило, принимаются такие соглашения, которые охватывают целый универсум отдельных задач мультиагентного планирования, а не требуют разработки с нуля перед началом решения каждой новой задачи. Это может приводить к недостаточной гибкости и нарушениям в работе, как иногда можно наблюдать в парном теннисе, когда мяч пролетает приблизительно на равных расстояниях между двумя партнерами. В отсутствие применимого соглашения агенты могут использовать общение для получения общих знаний об осуществимом совместном плане. Например, в парном теннисе игрок может крикнуть "Мой!" или "Твой!", имея в виду мяч, чтобы указать на предпочтительный для него совместный план.

Механизмы общения рассматриваются более подробно в главе 22, в которой отмечается, что общение не обязательно требует устного обмена репликами. Например, один игрок может неявно сообщить о предпочтительном совместном плане другому, просто выполнив его первую часть. В нашей задаче игры в теннис, если агент А направился к сетке, то 6! О Часть!У. Планирование агент и обязан отойти назад, к линии подачи, чтобы отбить мяч, поскольку план 2 является единственным совместным планом, который начинается с того, что агент А направляется к сетке.

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

А в последнем случае агентам приходится больше рассуждать; они должны доказывать или демонстрировать другими способами, что их планы будуг успешными, принимая во внимание рассуждения других агентов. Например, в среде с двумя логическими агентами, А и и, оба этих агента могут иметь следую)цсе определение; чр,з реаахьте(р, а) с» согхаопкпаьцег)яе((д, д), дслхегея(р, а, ооа1) ) В нем указано, что в любой ситуации з план р представляет собой осуществимый совместный план в данной ситуации, если оба агента располагают знаниями о том, что план р позволяет достичь цели. Нам потребуются дополнительные аксиомы для формирования общих знаний о ог совместном намерении Цо)п( ш(еп(юп) выполнить конкретный совместный план; только после этого агенты могут приступать к действиям.

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

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

Характеристики

Список файлов книги