Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 165
Текст из файла (страница 165)
Агент, действующий в соответствии с этим алгоритмом, хранит в своей базе знаний постоянно сушествую)ций план и в каждой операции удаляет из этого плана по одному дефекту. Затем он выполняет некоторое действие (хотя таким действием часто бывает пустая операция л)ог)р) и повторяет цикл. Этот агент способен преодолевать многие проблемы, перечисленные при обсуждении перепланирующего агента на с. 599. В частности, он может действовать в реальном времени, пользуется удачным стечением обстоятельств, способен формулировать цели самостоятельно и справляется с непредвиденными ситуациями, которые влияют на выполнение плана в будущем. Листинг 12.6. Алшрнтм непрерывно планирующею агента с частичным упорядочением сопеапиоин-Ров-лдепе.
после получения очередных результатов восприятия агент удаляет один дефект нз своего постоянно обновляемого плана, а затем возвращает действие. Агенту часто приходится выполнять много этапов планирования, связанных е удалением дефектов, в течение которых ен возвращает пустую еперапню лгоор, пока ен не будет готов выполнить какее-те реальное действие Йипсгаоп Соппапцоцз-РОР-Адепп)регсерс) гесигпе действие аселоп вгаеас: р1ап, план, первоначально содержащий только действия Ясагс и Гйпдап асехоп < — моОр )действие г)сор применяется по умолчанию) еггессз(леаге) = црс)асе)еггессз)Ясаке), регсере) Пещоче-Р1аы(р1ап) ГГ Возможно, выполнение этой операции приведет /Г к обновлению действия ассхоп гееигп асейоп 605 Глава 12. Планирование и осуществление действий в реальном мире 12.7. МУЛЬТИАГЕНТНОЕ ПЛАНИРОВАНИЕ До сих пор нам приходилось иметь дело только с одноагентными вариантами среды, в которых рассматриваемый агент действует в одиночестве.
А если в этой среде есть также другие агенты, наш агент может просто включить их в свою модель среды, не изменяя своих основных алгоритмов. Но во многих случаях такой подход приводит к низкой производительности, поскольку взаимодействие с другими агентами во многом отличается от взаимодействия с природой. В частности, природа (как обычно принято считать) безразлична к намерениям агента", а другие агенты — нет. В данном разделе приведены основные сведения о мультиагентном планировании, которое предназначено для решения указанных проблем. Как было показано в главе 2, мультиагентные варианты среды могут быть кооперативными или конкурентными.
Начнем с простого кооперативного примера: планирование действий команды в парном теннисе. Для определения действий обоих игроков в команде могут быть составлены планы; в этом разделе будут описаны методы эффективного формирования таких планов. Эффективно сформированный план полезен, но не гарантирует успеха; прежде всего агенты должны согласиться использовать один и тот же план! Для этого требуется определенная форма координации, которая может быть достигнута с помощью общения.
Кооперация: совместные цели и планы Два агента, играющие в одной команде в парный теннис, имеют единую цель— выиграть матч, что приводит к возникновению различных подцелей. Предположим, что в какой-то момент игры они имеют общую цель — отбить мяч, который направлен на их половину поля, и обеспечить, чтобы по меныцей мере один из них играл под сеткой. Мы можем представить это общее намерение в виде задачи 'оь мультиагентного планирования, как показано в листинге 12.7. Листинг 12.7. Задача игры в парный теннис.
Два агента еграют в одной команде е могут присутствовать в одном вз четырех мест: [ъеяе,ваае11ее] (слева„у задней линии), [нддье, Ваеездпе] (справа, у задней линии), [ъеде,)еес] (слева, лед сеткой) в [дхдде,л)ее] (справа, под сеткой). Мяч может быль отбит, если в нужном месте находится один и только один ипюк Адепте (А, В) 1п1С(АС(А, [Ьете, Ваае11пе] ) х АС(В, (Лудлт, нее] ) х Арртоаслтпд(ва11, [Нддьт, Ваее11пе] ) ) п Ратепет(А,В) х Раттпет(В,А) Соа1(нееитпет)(Ва11) л АС(адепт, [х, Иет]) ) Астдоп(НЗ т(адепс, Ва11), Ртесопсн Арртоаопдпд(ва11, [х, у]) л АС(адепе, (х, у]) л Ратепет(адепт,ратепет) л -АС(ратепет,[х,у]), Еттесе: Яеситпет)(Ва11)) Аседоп(со(адепе, [х, у]), Ртесопьн Ат(адепт, [а, Ь]), Еттесе: АС(адепе, [х,у]) п АС(адепе, [а, .Ь])) 606 Частью(.
Планирование В этой постановке задачи применяются два новых средства. Во-первых, в высказывании Адепсе (А, В) объявляется, что в плане участвуют два агента, А и В [по условиям данной задачи противостоящие им игроки не рассматриваются как агенты). Во-вторых, в каждом действии в качестве формального параметра упоминается агент, поскольку нам необхолимо следить за тем, что делает каждый агент. Решением мультиагентной задачи планирования является ек совместный план Оо[п( р1ап), состоящий из действий для каждого агента. Совместный план представляет собой решение, если цель будет достигнута при условии, что каждый агент выполнит назначенные ему действия.
Решением данной задачи игры в теннис является приведенный ниже план. Р1ап 1: А: [Оп(А, [Я1цде, Ваае11пе]), ндь(А, Ва11)] В: [Впор(В), асор(В)] Если оба агента имеют одинаковую базу знаний и если это решение является единственным, то все сложится идеально; каждый из агентов сможет определить это решение, а затем совместно выполнить его. Ио к большому сожалению для этих агентов [и мы вскоре увидим, почему им приходится об этом сожалеть), существует другой план, позволяющий так же успешно достичь цели, как и первый: Р1ап 2: [Оп(А, [ЬеГЕ, Нес]),. Нпор(А)] В: [Ое(В, [Я1ОНЕ, Ьаае11пе]), Н1Е(В, Ва11)] Если агент А выберет план 2, а агент  — план 1, то никто из них не отобьет мяч.
И наоборот, если агент А выберет план 1, а агент в — план 2, то они, вероятно, столкнутся друг с другом; ни один из них не отобьет мяч, и к тому же пространство под сеткой может остаться неприкрытым. Поэтому само существование правильных совместных планов еше не означает, что цель будет достигнута. Агентам нужен некоторый механизм 'ек координации для достижения одного и того же совместного плана; более того, оба агента должны обладать общими знаниями [см. главу 10) о том, что должен быть выполнен некоторый конкретный совместный план. Многотельное планирование В данном разделе речь пойдет в основном о формировании правильных совместных планов, а вопросы координации мы пока отложим.
Авторы называют данный подход Ъ. миоготельиым планированием [пш!([Ьобу р!ап1ипа); по суги именно в этом состоит задача планирования, с которой сталкивается также один централизованный агент, который может раздавать указания по выполнению действий каждой из нескольких физических сущностей. А если рассматривается случай, в котором действует несколько настоящих агентов, такое планирование дает возможность каждому агенту выяснить, каковы возможные совместные планы, которые позволили бы агентам добиться успеха, если бы они действовали согласованно. Применяемый нами подход к многотельному планированию будет основан на планировании с частичным упорядочением, которое описано в разделе 11пй Чтобы упростить решение этой проблемы, мы будем исходить из предположения о полной " С нами могут не согласиться жители Соединенного Королевства, гле сами действия ло подготовке пикника гарантируют дождь.
Глава 12. Планирование и осуществление действий в реальном мире 607 наблюдаемости среды. Есть еще один дополнительный вопрос, который не возникает в одноагентном случае: среда больше не является в полном смысле этого слова статической, поскольку другие агенты могут действовать, пока какой-то конкретный агент размышляет.
Поэтому необходимо позаботиться о 'а. синхронизации. Для упрощения мы будем предполагать, что каждое действие занимает одно и то же количество времени и что действия, выполняемые в каждом пункте совместного плана, являются одновременными. В любой момент времени каждый агент выполняет одно и только одно действие (возможно, включая пустую операцию ИоОр).
Такое множество одновременных действий называется 'оь совместным действием ()о[и[ асйоп). Например, совместным действием в проблемной области тенниса (с. 1) с агентами л и в является <д)оОр (А), нз с (в, ва22) >. Совместный план состоит из частично упорядоченного графа совместных действий. Например, план 2 для описанной выше залачи игры в теннис может быть представлен как такая последовательность совместных лействий: <оо[Д, [ЬеЕС, Иее] ), Во[в, [Лддле, Ваае1дпе] ) > <Воср[я), ВЕС(В, ВаЗЗ) > Это планирование может быть выполнено с помощью обычного алгоритма РОР, применяемого к множеству всех возможных совместных действий. Единсгвснная проблема состоит в огромных размерах этого множества: при наличии 10 действии и 5 агентов количество совместных действий составляет 10'.
Было бы очень утомп- тельным правильное определение предусловий и результатов каждого деиствия, а разработка плана на таком большом множестве стала бы неэффективной. Альтернативный подход заключается в том, что совместные действия определяются неявно путем описания того, как каждое отдельное действие сочетается с другими возможными действиями.
Такой подход должен быть проще, поскольку большинство действий независимы друг от друга, поэтому нам потребуется перечислить лишь немного действий, которые действительно взаимодействуют друг с другом. Это можно сделать, дополнив обычные описания действий Б[г[рз или АГ)Е одним новым средством — 'а. списком одновременных действий (сопсиггеш асйоп 1]з[). Этот список аналогичен предусловию любого описания действия, за исключением того, что в нем описываются не переменные состояния, а действия, которые должны или не должны выполняться одновременно. Например, действие удара по мячу, вд с, может быть описано следую)цим образом: лссд (и'е(л, ваП), Сопспгсепо: НЕС[В, па<1), Всесопд: Лрргоаслдпц(ва<1, [х, у]) л ЛС(Л, [х, у]), ЕЕЕесе: Лееигпед(вазз)) В данном случае мы встречаемся с ограничением, запрещавшим одновременное выполнение, согласно которому при выполнении действия вус одним агентом не должно быть выполнения действия еед с другим агентом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
