Мультиагентные системы

Свойство Маркова

Рассмотрим снова рефлексивного агента с реактивной тактикой π(ot) = at в полностью обозреваемом мире. Предположение обозреваемости подразумевает, что st  = ot, и, таким образом, тактика агента π(st) = at. Другими словами, в обозреваемом мире тактика рефлексивного агента является отображением из состояний мира в действия. Выгода состоит в том, что во многих задачах состояние мира в момент времени t дает полное описание истории до момента времени t.

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

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

До сих пор мы рассматривали, как стратегия агента может зависеть от последнего события и отдельных характеристик окружения. Однако, как мы обсуждали вначале, принятие оптимального решения может также зависеть от оценки будущего.

Стохастические переходы

В каждый момент времени t  агент выбирает действие at  из конечного множества действий A. После выбора агентом действия мир меняется как его следствие. Модель перехода (иногда называют моделью мира) определят, как меняется мир после совершения действия. Если текущее состояние мира st  и агент совершает действие at, мы можем выделить два случая.

1.      В детерминистическом мире модель перехода отображает единственным образом пару «состояние–действие» (st, at) в новое состояние st + 1. В шахматах, например, каждый ход изменяет игровую позицию.

2.      В стохастическом мире модель перехода отображает пару «состояние–действие» в распределение вероятности P(st + 1  | st, at)  состояний. Как и в рассмотренном выше случае с частичной обозреваемостью, st + 1  — это случайная величина, которая может принимать все возможные значения в множестве S  с соответствующей вероятностью P(st + 1  | st, at). Самые практические приложения включают стохастические модели перехода, например, движение робота неточно из-за того, что его колеса скользят.

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

Для классического искусственного интеллекта целью отдельной задачи является желаемое состояние мира. Таким образом,планирование определяется как поиск оптимальной стратегии. Когда мир детерминистический, планирование переходит в поиск по графу для каждого варианта существующего метода. В стохастическом же мире может не перейти в простой поиск по графу, так как переход из состояния в состояние не является детерминистическим. Теперь агент при планировании может принимать в расчет неточности переходов. Чтобы понять, как это может быть использовано, заметим, что в детерминистическом мире агент предпочитает по умолчанию конечное состояние неконечному. В общем случае, агент сохраняет настройки при переходе из состояния в состояние. Например, робот, играющий в футбол, будет стараться забить очко, стараться меньше стоять с мячом перед пустыми воротами и т.п.  Чтобы формализовать это понятие, свяжем с каждым состоянием s  вещественное числоU(s), называемое полезностью состояния этого агента. Формально, для двух состояний s  и s*  выполняется U(s) > U(s*) тогда и только тогда, когда агент предпочитает состояние s  состоянию s*, а U(s)  = U(s*), если для агента эти состояния неразличимы. Интуитивно понятно, что чем выше полезность, тем выгоднее состояние, в котором находится агент. Заметим, что в мультиагентных системах желаемое состояние для одного из агентов может не быть желаемым для остальных. Например, в футболе забивание гола является нежелательным для противоположной команды.

Принятие решения в стохастическом мире

Теперь возникает вопрос, как агент может эффективно использовать функции полезности для принятия решения. Предположим, что у нас мир стохастический с моделью перехода P(st + 1  | st, at), находящийся в состоянии st  до тех пор, пока агент обдумывает, какое действие ему совершить. Пусть U(s)  — функция полезности состояния какого-то агента. Предположим, что у нас только один агент. Тогда принятие решения основано на предположении, что оптимальное действие агента должно быть максимумом полезности, т.е.

a*t = max∑P(st + 1 | st, at)·U(st + 1),

где суммирование выполняется по всевозможным состояниям st + 1. Чтобы увидеть, насколько полезно действие, агент должен умножить полезность каждого возможного конечного состояния на вероятность попадания в это состояние, и потом просуммировать полученный результат. Тогда агент может выбрать действие a*t  с максимальной суммой. Если каждое состояние мира имеет величину полезности, агент может произвести вычисления и выбрать оптимальное действие для каждого возможного состояния. Тогда агент со стратегией может оптимально переводить состояние в действие.

3.      Структура мультиагентной системы принятий решений для оценки деятельности предприятия

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

Общая схема принятия решений включает следующие этапы:

1)    спецификация требований;

2)    генерация решений;

3)    оценка альтернатив;

4)    выбор эффективного решения.

Оценку решений проводит рабочая группа, состоящая из руководителя, аналитика и экспертов.

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

Для поддержки группового процесса принятия решений используется программная реализация метода анализа иерархий:

        формирование и согласование иерархической структуры показателей;

        оценка и согласование качественных показателей проекта;

        оценка и согласование важности показателей;

        ранжирование альтернативных решений и согласование результатов.

На каждом этапе предусмотрены процедуры согласования экспертных мнений.

Ядром мультиагентной системы является менеджер знаний,  использующий три внешних компонента:

        информационную модель проблемной области в виде упорядоченного набора показателей качества решений;

        средства технической и программной поддержки;

        множество типов пользователей (руководитель, координатор, эксперт, аналитик).

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

Основные функции агентов в системе:

Агент-руководитель:

        предоставляет набор процедур для облегчения работы руководителя в распределенной системе;

        вычисляет конечный результат на основании данных, полученных от других агентов;

        отслеживает согласованность решения, вырабатываемого группой;

        предоставляет средства визуализации результатов работы;

        подготавливает сообщения агенту-координатору;

        выполняет почтовые функции в распределенной среде.

Агент-координатор:

        обеспечивает выполнение пошагового алгоритма принятия решения;

        поддерживает целостность баз данных системы на групповом уровне и вносит в них необходимые изменения;

        подготавливает диалоговые формы для информационного обмена через Интернет.

Агент-эксперт:

        поддерживает выполнение текущего шага задания;

        готовит сообщение агенту-координатору;

        поддерживает целостность локальных баз данных;

        выполняет почтовые функции в распределенной среде.

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

Агент-координатор собирает сообщения о готовности выполненных заданий от всех членов группы. При выполнении всего пакета заданий его состояние изменяется, и посылается сообщение агенту руководителя.

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

Заключение

Итак,  многоагентная система (МАС, англ. Multi-agent system) — это система, образованная несколькими взаимодействующими интеллектуальными агентами. Многоагентные системы могут быть использованы для решения таких проблем, которые сложно или невозможно решить с помощью одного агента или монолитной системы (англ.). Примерами таких задач являются онлайн-торговля, ликвидация чрезвычайных ситуаций, и моделирование социальных структур.

В многоагентной системе агенты имеют несколько важных характеристик:

        Автономность: агенты, хотя бы частично, независимы

        Ограниченность представления: ни у одного из агентов нет представления о всей системе, или система слишком сложна, чтобы знание о ней имело практическое применение для агента.

        Децентрализация: нет агентов, управляющих всей системой

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

В многоагентных системах может проявляться самоорганизация и сложное поведение даже если стратегия поведения каждого агента достаточно проста. Это лежит в основе так называемого роевого интеллекта.

Агенты могут обмениваться полученными знаниями, используя некоторый специальный язык и подчиняясь установленным правилам «общения» (протоколам) в системе. Примерами таких языков являются Knowledge Query Manipulation Language (KQML) и FIPA’s Agent Communication Language (ACL).

Список литературы:

1.Гаврилова Т. А., Хорошевский В. Ф. Базы знаний интеллектуальных систем. – СПб.: Питер, 2000.

2.Смирнов А. В., Шереметов Л. Б. Многоагентная технология проектирования сложных систем.

3.Городецкий В.И. Многоагентные системы: современное состояние исследований и перспективы //Новости искусственного интеллекта, н.1, 1996.

4.Борщёв А. От системной динамики и традиционного ИМ – к практическим агентным моделям: причины, технология, инструменты/ www.gpss.ru.

5. http://aivanoff.blogspot.com/2007/12/blog-post_18.html

6. Андрейчиков А.В. Андрейчикова О.Н. Интеллектуальные информационные системы: Учебник для вузов