МУЛЬТИАГЕНТНОЕ ПЛАНИРОВАНИЕ
До сих пор нам приходилось иметь дело только с одноагентными вариантами среды, в которых рассматриваемый агент действует в одиночестве. А если в этой среде есть также другие агенты, наш агент может просто включить их в свою модель среды, не изменяя своих основных алгоритмов. Но во многих случаях такой подход приводит к низкой производительности, поскольку взаимодействие с другими агентами во многом отличается от взаимодействия с природой. В частности, природа (как обычно принято считать) безразлична к намерениям агента15, а другие агенты — нет. В данном разделе приведены основные сведения о мультиагентном планировании, которое предназначено для решения указанных проблем.
Как было показано в главе 2, мультиагентные варианты среды могут быть кооперативными или конкурентными. Начнем с простого кооперативного примера: планирование действий команды в парном теннисе. Для определения действий обоих игроков в команде могут быть составлены планы; в этом разделе будут описаны методы эффективного формирования таких планов. Эффективно сформированный план полезен, но не гарантирует успеха; прежде всего агенты должны согласиться использовать один и тот же план! Для этого требуется определенная форма координации, которая может быть достигнута с помощью общения.
Кооперация: совместные цели и планы
Два агента, играющие в одной команде в парный теннис, имеют единую цель — выиграть матч, что приводит к возникновению различных подцелей. Предположим, что в какой-то момент игры они имеют общую цель — отбить мяч, который направлен на их половину поля, и обеспечить, чтобы по меньшей мере один из них играл под сеткой. Мы можем представить это общее намерение в виде задачи мультиагентного планирования, как показано в листинге 12.7.
Листинг 12.7. Задача игры в парный теннис. Два агента играют в одной команде и могут присутствовать в одном из четырех мест: [Left,Baseline] (слева, у задней линии), [Right, Baseline] (справа, у задней линии), [Left, Net] (слева, под сеткой) и [Right, Net] (справа, под сеткой). Мяч может быть отбит, если в нужном месте находится один и только один игрок
Agents(А, В)
Init(At(A, [Left, Baseline]) л At(В, [Right, Net]) л
Approaching{Ball, [Right, Baseline])) л Partner(A,B) л Partner(B,A) Goal(Returned(Ball) л At(agent, [x, Net]))
Action(Hit(agent, Ball),
Precond: Approaching (Ball, [x, у] ) л At(agent, [x, у] ) л Partner (agent, partner) л —At (partner, [x,y] ) ,
Effect: Returned(Ball)) Action(Go(agent, [x, y] ) ,
Precond: At(agent, [a, b]),
Effect: At(agent, [x,y]) л —At(agent, [a, b]))
В этой постановке задачи применяются два новых средства. Во-первых, в высказывании Agents {А, В) объявляется, что в плане участвуют два агента, Аи В (по условиям данной задачи противостоящие им игроки не рассматриваются как агенты). Во-вторых, в каждом действии в качестве формального параметра упоминается агент, поскольку нам необходимо следить за тем, что делает каждый агент.
Решением мультиагентной задачи планирования является совместный план (joint plan), состоящий из действий для каждого агента. Совместный план представляет собой решение, если цель будет достигнута при условии, что каждый агент выполнит назначенные ему действия. Решением данной задачи игры в теннис является приведенный ниже план.
Plan 1:
A: [Go{A, [Right, Baseline]), Hit{A, Ball)] В: [NoOp{В), NoOp(В)]
Если оба агента имеют одинаковую базу знаний и если это решение является единственным, то все сложится идеально; каждый из агентов сможет определить это решение, а затем совместно выполнить его. Но к большому сожалению для этих агентов (и мы вскоре увидим, почему им приходится об этом сожалеть), существует другой план, позволяющий так же успешно достичь цели, как и первый:
Plan 2:
A: [Go(A, [Left, Net]),, NoOp(A)]
В: [Go{B, [Right, baseline]), Hit(B, Ball)]
Если агент А выберет план 2, а агент В — план 1, то никто из них не отобьет мяч. И наоборот, если агент А выберет план 1, а агент В— план 2, то они, вероятно, столкнутся друг с другом; ни один из них не отобьет мяч, и к тому же пространство под сеткой может остаться неприкрытым. Поэтому само существование правильных совместных планов еще не означает, что цель будет достигнута. Агентам нужен некоторый механизм координации для достижения одного и того же совместного плана; более того, оба агента должны обладать общими знаниями (см. главу 10) о том, что должен быть выполнен некоторый конкретный совместный план.