7.4. Раскопка Веб-сайтов
8. Многоагентные иис
Распределенные интеллектуальные системы, как новое направление в искусственном интеллекте, возникли в 80-е годы прошлого столетия. В настоящее время такие системы разделяются на системы распределенного решения задач (Distributed Problem Solving) и многоагентные системы (Multi-Agent System) [7].
В основе систем распределенного решения задач лежит декомпозиция полной задачи на частичные задачи. Каждая частичная задача обрабатывается локальным решателем. Получаемые локальные решения далее объединяются, что позволяет сформировать решение полной задачи. Такой распределенный процесс дает возможность решать много более сложные задачи, чем это можно сделать один централизованный решатель.
Многоагентные системы (МАС) состоят их простых или интеллектуальных агентов. Интеллектуальный агент первоначально рассматривался как автономная компьютерная программа, способная демонстрировать интеллектуальное взаимодействие со средой и, в частности, с человеком. Известный тест А. Тьюринга позволял установить, может ли компьютерная программа на равных взаимодействовать с человеком. В рамках этого теста человек общался с некоторой программой через монитор. Он мог задавать любые вопросы и формировать утверждения. После некоторого времени общения требовалось решить, где функционирует человек, а где программа. Если такой тест не мог отличить человека от программы, то в соответствии с А. Тьюрингом, программа рассматривалась как интеллектуальная. Такая автономная программа, отвечающая в реальном времени на утверждения человека, могла быть названа агентом.
В современных МАС интеллектуальные агенты взаимодействуют при решении задач с общей целью. Такое взаимодействие организуется на основе протоколов и реализуется путем обмена сообщениями на специальном языке, понятном всем агентам. Взаимодействие агентов позволяет решать в рамках всей системы много более сложные задачи, чем те, которые могут решать отдельные агенты. Оно должно быть построено так, чтобы оптимизировать процесс достижения цели всей системой, например, по критерию минимума коммуникаций агентов.
8.1. Системы с интеллектуальными агентами на правилах
В этой главе интеллектуальный агент рассматривается как автономная интеллектуальная программа, которая способна к восприятию внешней информации о среде и самостоятельному принятию решений о действиях в ней в соответствии с поставленными целями. В отличие от простого агента такой агент должен иметь способность к планированию и гибким автоматическим действиям для достижения поставленных целей.
Можно формализовать рассмотренное понятие агента в виде некоторой абстрактной модели. Предположим, что состояние окружающий среды может быть охарактеризовано как набор S={s1,s2…} состояний среды. Предположим также, что в каждый данный момент среда находится в одном из этих состояний. Способность агента к действию может быть представлена как набор A={a1,a2,…} действий. Тогда абстрактно агент может быть описан функцией
action: S*→A,
которая отображает последовательность состояний среды на действия. Такой агент решает, какое действие выполнить на основе своей истории, т.е. собственном опыте, накопленном к текущему моменту. Этот опыт представлен, как последовательность состояний окружения, в которых агент успел побывать.
Поведение (недетерминированное) среды может быть смоделировано функцией
env: S x A→(S),
которая принимает текущее состояние среды s S и действие a A (выполняемое агентом) и отображает их на набор состояний среды env(s,a) – тех которые являются результатом выполнения действия a в состоянии s. Если все наборы в диапазоне env являются однозначными (например, если результат выполнения действия и любом состоянии единственен), тогда окружение детерминировано, и его поведение может быть точно предсказано.
Можно представить взаимодействия агента с окружением как последовательность пар «состояние-действие», определяющая историю h, т.е.
h: (s0, a0)→(s1, a1)→(s2, a2)→(su, au) →…→(su+1, au+1) →…,
где s0 исходное состояние окружения, (например, когда агент начинает выполнение), au – действие, которое выбрал для выполнения агент в состоянии su (которое само является возможным результатом выполнение действия au-1 в состоянии su-1). Если действия агента action: S*A, а env: S x A (S) - окружение и s0 начальное состояние окружение, тогда указанная последовательность будет представлять возможную историю агента в окружении, если выполняются два следующих условия:
uN, au = action((s0, s1, …, su));
uN такое, что u > 0, suenv(su-1, au-1).
Поведение агента action: S*A в окружении env: S x A(S) - это набор всех историй, которые удовлетворяют этим свойствам. Если некоторое свойство заключает в себе все эти истории, то оно может считаться инвариантным свойством агента в данном окружении. Например, если агент является регулятором атомного реактора (т.е. окружением является атомный реактор) и все возможные истории включают пары «регулятор-реактор, при которых реактор не взрывается, то это может считаться инвариантным (желаемым) свойством. Можно обозначить набор всех историй агента в окружении как hist(agent,environment). Два агента ag1 и ag2 считаются идентичными по поведению в данном окружении env, если hist(ag1,env)=hist(ag2,env) и просто эквивалентными, если они идентичны по поведению в любом окружении.
Определенный класс агентов решает, что им делать, без ссылки на свою историю. Они полностью основывают свое решение на настоящем моменте, без ссылки на прошлое. Такие агенты называются чисто реактивными, поскольку они просто реагируют на окружающую обстановку. Формально поведение чисто реактивного агента может быть представлено функцией
action: SA.
Несложно увидеть, что каждый чисто реактивный агент является эквивалентом стандартного агента, но обратное в общем случае неверно.
Пример: простой агент-термостат на правилах
Система, управляющая нагревателем воздуха в помещении, являет собой пример простого, чисто реактивного агента. Предположим, без потери объективности, что среда агента может быть в одном из двух состояний: слишком холодно или температура в норме. Тогда действие термостатной функции просто:
action(s)= heater off if s=temperature OK
heater on otherwise.
Агент на абстрактном уровне достаточно прост для анализа. Однако это не помогает конструировать агентов, поскольку не дает информации о структуре функции действия. По этой причине следует уточнить абстрактную модель агентов, разбивая ее на подсистемы. Первое уточнение связано с разделением функции принятия решения агента на восприятие и действие. Введем функцию see, которая определяет способность агента наблюдать за своим окружением, тогда как функция action представляется собой процесс принятия решения агентом. See функция может быть реализована аппаратно в случае, если агент находится в физическом мире: например это может быть видео камера или инфракрасный сенсор на мобильном роботе. Для программного агента сенсорами могут быть системные команды, которые предоставляют информацию о программном окружении. Выходом функции see является percept (восприятие, ощущение) – входное восприятие. Пусть P будет набор (не пустой) результатов восприятия. Тогда see функция:
see:S→P,
которая относит состояния окружающей среды к восприятиям, и функцию action теперь можно записать как
action:P*→A,
которая относит последовательность восприятий к действиям.
Пример: многоуровневый агент на правилах
Для организации сложного поведения может быть построен агент на правилах с несколькими уровнями восприятия и принятия решений. Такой тип агента используется, например, для моделирования агентов-футболистов для виртуальной среды футбола роботов RoboCup Soccer Simulation Server.
Один из вариантов такого агента на правилах представлен на рис.8.1. Он соответствует играющему агенту команды Polytech-DrWeb [20]. Агент включает несколько уровней: тактический, поведения и навыков.
Уровень тактических решений выбирает текущее поведение, основываясь на глобальной информации обо всех игроках, положениях маркеров поля по отношению к игроку и положении мяча, а также параметрах определяющих стратегию команды (роли игроков, формации, планы игры), которые инициализируются на старте игры. Возможно динамическое изменение стратегии команды в процессе игры.
Уровень поведения включает процедуры, определяющие поведение агента при игре: ведение мяча с препятствиями, перехват мяча, пассы, прессинг и т.д. Различное поведение выбирается в соответствии с текущими состояниями среды и игрока. При реализации разного поведения используются процедуры уровня навыков игрока.
Уровень навыков игрока включает бегание с разгонами и поворотами, обход препятствий, удар в данную позицию и т.д. Результатом работы процедур этого уровня является последовательный набор команд, исполняемых сервером (типы таких команд были перечислены в предыдущем разделе).
Состояние игрока - это набор его внутренних параметров: энергических (усталость, усилия, восстановление), кинетических и различных статистических параметров. Этот набор параметров необходим для выработки правильных решений с учетом энергии игрока и его текущих возможностей.
Синхронизация - "сердце" агента. Она использует моментальный снимок состояния окружающей среды и агента для управления его реакцией. Действие этой компоненты похоже на планирование работы компьютера операционной системой реального времени. Синхронизация позволяет избежать возможных пропусков команд и оптимизирует взаимодействие клиента с сервером.
Модель среды реализует: моделирование поведения противника, слежение и предсказание движений мяча, моделирование и слежение за расходом энергии игрока. От качества модели среды зависят прогнозирующие возможности агента и эффективность принимаемых им решений.
Представление поля дополняет модель среды, сохраняя текущие параметры, привязанные к маркерам футбольного поля: позиции игроков, позиции маркеров по отношению к игроку, позицию и направление движения мяча и т.д.
Восприятие отвечает за прием информации (зрительной, звуковой, физической) от сервера, ее распознавание и формирование условий, необходимых для выбора текущего поведения агента.
Агент должен работать, как клиент футбольного сервера, определяющего клиент-серверную среду (Soccer Server). Поэтому очень важна правильная синхронизация его действий в цикле симуляции. При нарушении синхронизации возможны случаи нарушения работы агента, например, пропуски летящего мяча, неправильные пассы и пр.
Программа агента, как правило, реализуется на языке Си для операционной среды Unix, поскольку сервер работает в этой среде. Существуют достаточно обширные библиотеки модулей и оболочки, которые целесообразно использовать при разработке программы [21]. Некоторое упрощение разработки достигается использованием готовых модулей нижнего уровня агента (навыков работы с мячом). При этом основные усилия сосредотачиваются на понимании работы заимствованных модулей и разработке верхних поведенческих уровней агентов.