|
Читайте также: |
Однако, построение дерева вывода не даёт решения задачи. Следующим пунктом рассмотрим алгоритм поиска сопряженных ветвей (рис 4.5).
Рис 4.5. Алгоритм поиска сопряженных ветвей в дереве логического вывода формулы диалоговой логики.
Данный алгоритм поиска соглашений относится к классу P-полных, его вычислительная сложность оценивается O(m2*n2), где n-количество открытых ветвей, а m-максимальное количество литер типа &*или &. Алгоритм также прекрасно распараллеливается. Например, в отдельном процессе можно проводить проверку для каждой пары ветвей.
На выходе алгоритма получаем пары сопрягаемых ветвей, которые образуют множество возможных соглашений. Каждое соглашение из этого множества удовлетворяет условиям задачи, однако некоторые из них могут быть избыточными или не удовлетворять иным критериям оптимальности. Сформулируем условия задачи, обозначенной в Пункте 4 (см. выше список основных шагов при решении задач средствами диалоговой логики). Соглашение представляет собой набор множеств, каждое из которых, в свою очередь, представляет совокупность означенных литер, образующих частичную интерпретацию формулы для одного из агентов-участников диалога:
agr = <S1,S2,…,Sn>, Si = {si|si=DjXk, DjÎLi}, где Li – множество истинностных значений логики агента i, Xk-некоторая литера, представляющая собой атомарный элемент универсума. Множество найденных соглашений AGR = {agr} образует область определения.
Необходимо задание критериев оптимальности. Пусть задан набор Ki(agr)=Xi, где iÎ{1..n}, agrÎAGR, XiÎ R. Тогда оптимальное соглашение argопт должно удовлетворять следующим условиям: "iÎ{1..n}, "agrÎAGR Ki(agrопт)£Ki(agr).
Например, критерием оптимальности будет являться критерий избыточности, задаваемый следующим образом: Red(agr) = |S1|+|S2|+…+|Sn|
В простейшем алгоритме оптимизации, осуществляется простой перебор всех полученных соглашений и отбрасывание неоптимальных вариантов. Вычислительная сложность алгоритма оценивается O(n), где n-количество вариантов соглашений. Более продвинутые алгоритмы могут осуществлять поиск не только на множестве соглашений, но и на всём множестве возможных интерпретаций.
Задача, сформулированная в Пункте 6, также как и задача пункта 1 сильно зависима от специфики конкретного диалогового фрейма, и её решение индивидуально для различных коммуникативных актов.
4.2 Методика построения агентно-ориентированных систем на базе диалоговых логик
На настоящий момент существует большое количество различных подходов к проектированию и разработке как больших программных комплексов, таких какими являются, например, CRM-системы, так и более мелких систем. Подходы к разработке и проектированию основываются на принципах восходящего, нисходящего, итерационного проектирования, прототипирования. Также активное применение находят методики визуального проектирования с использованием CASE-средств.
4.2.1 Классификация существующих методологий проектирования агентно-ориентированных систем.
Методологии проектирования агентно-ориентированных систем всё еще находятся в начальной стадии развития. Известные подходы можно разделить на четыре основных класса:
· базирующиеся на объектно-ориентированных методах и технологиях с использованием соответствующих расширений;
· использующие традиционные методы инженерии знаний;
· основанные на организационно-ориентированных представлениях;
· комбинирующие в различной степени методы трёх первых классов.
На рис. 4.6 показано взаимное влияние наиболее известных на данный момент методологий.
Рис. 4.6 Взаимное влияние агентно-ориентированных методологий.
В методологиях первого класса разрабатываются расширения объектно-ориентированных методологий и технологий для проектирования АОС. Известны попытки непосредственного применения UML-нотации для представления агентно-ориентированных систем и образцов взаимодействия агентов. Однако эти предложения не могут охватить автономность и проактивное поведение агентов, так же как и богатство их взаимодействий. С другой стороны, некоторые предлагают расширить и адаптировать объектно-ориентированные модели и технологии для определения методологий МАС. Это ведёт, например, к расширенным моделям для представления агентного поведения и взаимодействия агентов и агентно-ориентированным расширениям UML [182]. Однако, хотя эти средства могут обеспечивать достаточные описания автономного поведения агентов и их взаимодействий, они не имеют адекватных концептуальных механизмов для работы с организациями и сообществами агентов.
Второй класс агентно-ориентированных методологий строится на расширении традиционных методов инженерии знаний [129,170]. Эти методологии обеспечивают формальные и композиционные языки моделирования для верификации структуры системы и функций и хорошо применимы к моделированию знание- и информационно-ориентированных агентов. Однако, так как эти подходы обычно предполагают централизованный взгляд на системы, основанные на знаниях, они не могут обеспечить адекватные модели и подходы для социального рассмотрения МАС.
Подход Common Kads пытается снять эти ограничения, явно вводя в методологию абстракцию агентного сообщества. Однако, это нововведение сводится к моделированию сообщества как коллекции взаимодействующих сущностей без идентификации концептов, таких как социальные задачи или социальные законы. MAS-CommonKADS – это методология разработки агентно-ориентированного программного обеспечения, предназначенная для применения на этапах анализа и проектирования. Она является гибридом хорошо известной методологии инженерии знаний CommonKADS, объектно-ориентированной методологии «Техника объектного моделирования» (Object Modelling Technique – OMT), объектно-ориентированной инженерии программного обеспечения (Object-oriented Software Engineering – OOSE) и метода проектирования, получившего название «проектирование, управляемое ответственностью» (Responsibility Driven Design – RRD). Основным отличием этой методологии от других является то, что разрабатываемая агентно-ориентированная система рассматривается с различных точек зрения. Разработчик получает описание, позволяющее выполнять реализацию на различных программных платформах. Сильной стороной методологии принято считать использование стандартных методов инженерии программного обеспечения, которые расширяются естественным способом. MAS-CommonKADS создавалась в расчете на многоразовое использование материалов, полученных на каждом уровне проектирования, что дает возможность использования данных из других проектов. Главный недостаток этой методологии – слабая поддержка этапов проектирования, тестирования и кодирования.
В работах В.А. Виттиха, П.О. Скобелева, С.В. Батищева предложена методика создания прикладных открытых МАС на основе концепции сетей потребностей и возможностей (ПВ-сетей) [1,26]. Данная методика поддержана развитыми инструментальными средствами и обеспечивает эффективную реализацию прикладных МАС в рамках заявленной концепции. Однако, она ориентирована на сравнительно узкий класс систем промышленной логистики и агентную модель, описывающую конкуренцию за ресурсы.
Другие модели и подходы направлены на создание АОС с «организационно–ориентированной» точки зрения [138,178]. Однако, эти подходы определяют организацию просто как коллекцию взаимодействующих ролей, таким образом, не разрешая проблемы коллективного поведения агентов.
В работах [126,183] предложена и исследована методология Gaia. Gaia – это методология агентно-ориентированного анализа и проектирования, явно использующая организационную точку зрения. Наиболее абстрактной сущностью в иерархии концептов Gaia является «система». Хотя термин «система» используется в стандартном смысле, он также означает «сообщество» или «организацию». Следующий уровень иерархии – это роли. Роль определяется тремя атрибутами: ответственности, разрешения, протоколы. Ответственности определяют функциональность и являются ключевым атрибутом, связанным с ролью. Ответственности разделяются на два типа: жизненные свойства и свойства безопасности. Для реализации ответственностей роль обычно связывается с множеством разрешений. Разрешения являются «правами», связанными с ролью и идентифицируют ресурсы, которые доступны в этой роли, для реализации ответственности. В различных системах, которые обычно моделируются, разрешения становятся информационными ресурсами. Роль идентифицируется определённым числом протоколов, которые определяют пути взаимодействия с другими ролями.
Ограничения и недостатки методологии Gaia проявляются в следующем:
· отсутствует строгое формальное определение модели предметной области (от общего концепта «система» сразу необходимо переходить к «ролям», «роли» сопоставляется агентный тип, а тип может иметь несколько экземпляров агентов);
· трудно выразить реальную иерархическую структуру корпоративных и производственных систем, «роли» как бы предполагают однородность функционального или задачного пространства;
· нет градации агентов по уровням интеллектуальной иерархии, что предполагает интеллектуальную однородность агентов, а это далеко не так в сложных системах;
· организационная структура системы статична, т.е. ни число агентов, ни их отношения не изменяются в текущем времени;
· агенты проявляют глобально согласованное поведение: они имеют некоторую общую цель и не проявляют соревновательного поведения.
Достаточно оригинальная методология проектирования МАС, основанная на концепции М-архитектуры, развивается в работах коллектива польских ученых во главе с K. Cetnarowicz [129]. В структуре данной методологии определяются такие конструкции как жизненное пространство агентов, типы агентов, отношения между агентами и жизненным пространством и отношения среди агентов. Агентная архитектура рассматривается с двух различных точек зрения: как интеллектуальный профиль, описывающий способность агента решать данную проблему, и как энергетический профиль, описывающий «жизненную энергию» агента и разрешающий уничтожение нежизнеспособных агентов.
Методология Тropos [177] реализует идею использования концепции моделирования требований для построения системы такой, какой она должна быть. В методологии можно выделить следующие фазы: ранние требования, поздние требования, проектирование архитектуры и детальное проектирование. Анализ требований в Тropos делится на две стадии – ранний анализ и поздний анализ. Ранний анализ сосредоточен на изучении среды, в которой АОС будет функционировать. Поздний анализ описывает функциональные и нефункциональные требования к системе. Заинтересованные стороны представляются как социальные личности (акторы), зависящие друг от друга посредством целей, которые должны быть достигнуты, задач, которые должны быть выполнены, и ресурсов, которые должны быть получены. Каркас моделирования содержит стратегическую модель зависимостей (диаграмма личностей в Тropos), показывающую взаимозависимости между личностями, также как стратегическая диаграмма отношений показывает причины, по которым акторам необходимо поддерживать отношения с другими акторами. Во время раннего анализа требований разработчик представляет все сущности в виде социальных акторов. Такая модель дает возможность ответить на вопрос «почему?» в дополнение к обычным вопросам «что?» и «как?» по поводу функционирования системы. На стадии позднего анализа требований модель дополняется акторами, которые описывают систему такой, какой она должна быть и показывают зависимости между системой и средой.
В последние годы расширяется класс методологий проектирования агентно-ориентированных систем, комбинирующих объектно-ориентированные и организационные подходы. Методология PASSI расшифровывается как «процесс для спецификации и реализации агентных сообществ» (Process for Agent Societies Specification and Implementation) [165]. Она является результатом длительного периода теоретических исследований и экспериментов в области робототехники. Авторы методологии старались использовать существующие стандарты везде, где это возможно. Поэтому в качестве языка моделирования выбран UML, для реализации агентов используется архитектура FIPA, а для представления знаний при обмене сообщений между агентами используется XML. Применение методологии PASSI требует последовательного построения совокупности моделей, отражающих различные аспекты проектирования агентно-ориентированной системы.
Методология Prometheus поддерживает разработку агентных систем на основе целей и планов [127]. Предполагается, что основными пользователями методологии станут инженеры-программисты, работающие в промышленности, а также студенты информационных специальностей. Методология Prometheus предоставляет два средства автоматизации труда проектировщика МАС. Первое средство – это инструмент проектирования Prometheus (Prometheus Design Tool), который позволяет разрабатывать все виды необходимых диаграмм и строить по ним отчёты. Функциональность PDT постоянно расширяется, инструмент является свободно распространяемым. Второй инструмент, поддерживающий методологию Prometheus – это среда разработки Jack (JACK Development Environment), которая предоставляет возможности для рисования обзорных диаграмм в стиле методологии Prometheus. На основе этих диаграмм среда позволяет сгенерировать скелет программного кода и следить за тем, чтобы изменения, произведённые в коде, отображались и на диаграммах. Разработчики считают главным достоинством методологии её практичность и способность к улучшению на основе отзывов прикладных программистов. Отмечается также эффективность её применения при изучении студентами МАС. Однако, Prometheus имеет и свои недостатки. Для описания социального взаимодействия агентов используются только протоколы и сообщения. Расширение возможностей поддержки более специфичных типов агентных взаимодействий требует дальнейшего развития методологии. Prometheus также не поддерживает мобильность агентов, так как авторы методологии считают, что это свойство не является основным для ИА. Такие фазы разработки как реализация, тестирование и отладка в этой методологии поддерживаются достаточно ограниченно. Еще одна особенность методологии – отсутствие поддержки UML. С одной стороны это хорошо, т.к. не привязывает проектировщика к объектно-ориентированной парадигме, а с другой стороны, это не дает множеству программистов воспользоваться инструментом, с которым они хорошо знакомы.
Таким образом, ни одна из методологий проектирования агентно-ориентированных систем не является на сегодняшний день в достаточной мере универсальной и общепризнанной. В связи с этим, представляется нецелесообразным в данной диссертации привязываться лишь к одной из них. Вместо этого постараемся в максимальной степени универсально описать один аспект проектирования агентно-ориентированных систем, связанный с формализацией взаимодействия агентов при помощи диалоговых логик. Этот аспект в той или иной мере учитывается во всех приведённых выше подходах.
4.2.2 Методика проектирования взаимодействий между агентами с использованием диалоговых логик.
С точки зрения диалоговой семантики, выражение «истина рождается в диалоге», приобретает буквальный характер. Диалоговая кооперативная семантика даёт широкие возможности спецификации знаний агентов в аспекте их коллективного взаимодействия, а диалоговая логика позволяет разрешить сложную коммуникативную ситуацию и прийти к оптимальному соглашению. Такой тандем позволяет отойти от привычных механизмов диалога, основанных на протоколах коммуникации, и вывести взаимодействие на новый уровень (см. рис 4.7). В этом параграфе будет рассмотрен один из способов, позволяющих осуществить этот переход.
Рис 4.7. Уровни коммуникации агентов в МАС.
Для начала определим, в каких ситуациях необходимо применение диалоговой логики, а в каких можно ограничиться протоколами коммуникации.
Механизм протоколов коммуникации достаточен для случаев взаимодействия:
· предполагающих лишь участие реактивных агентов;
· являющихся типовыми случаями коммуникативных актов, включенными в библиотеку FIPA ACL (информирование, запрос информации, предложение, отклонение/принятие и т.п.);
· предполагающих строгую субординацию агентов, при которой значимыми являются лишь представления одного из агентов.
Применение диалоговой логики необходимо:
· в ситуации конфликта знаний/мнений/интересов агентов-участников (например, в диалоге-полемике, убеждении, торгов);
· в случае неопределенности знаний агентов-участников (диалоге выявления знаний, диалоге принятия решений и т.п.);
· если по итогам взаимодействия необходим пересмотр знаний или мнений агентов-участников, или использование рефлексивных методов анализа ситуации.
Применение диалоговой логики не отменяет использование других коммуникативных методов, таких как протоколы коммуникации или, к примеру, диаграмма последовательности UML. Диалоговая логика применяется как надстройка над ними, хотя возможны ситуации (например, если несколько агентов работают на одной машине в рамках централизованной МАС), когда использование таких механизмов необязательно. В любом случае роль таких механизмов сводится к осуществлению обмена информацией о диалоге.
Рассмотрим пример протокола коммуникации при взаимодействии заказчика и поставщика, когда диалог ведётся средствами диалоговой логики.
Рис 4.8. Протокол коммуникации агента-поставщика и агента-заказчика при использовании диалоговой логики.
После спецификации средства обеспечения диалога, необходимо приступить к непосредственно к определению механизмов диалоговой логики. Первое что предстоит выбрать: тип логик агентов участников, объединив которые при помощи диалогового произведения определим логику диалога. Затем задаём общие цели и правила диалога, после чего необходимо определение механизмов выработки мнений агентов участников и пересмотра их мнений, если таковые имеются. Наконец, последними определяются критерии выбора оптимального соглашения.
Итак, краткая методика проектирования взаимодействий между агентами с использованием диалоговой логики будет выглядеть следующим образом:
1. Выделить ситуацию взаимодействия, определить состав и количество участвующих агентов.
2. Определить необходимость применения диалоговой логики в данной ситуации взаимодействия.
3. Выделить агентов, которые могут являться инициаторами взаимодействия, создать протокол взаимодействия, руководствуясь следующими правилами:
a. Любой агент может отказаться от дальнейшего диалога в любой момент его развития.
b. Должны быть предусмотрены механизмы, для продолжения или завершения диалога в любой аварийной ситуации (например, сбоя в среде транспортировки сообщений или ошибке в функционировании агента-участника).
c. Если агентно-ориентированная система является открытой, то должна быть обеспечена совместимость протокола взаимодействия со стандартами FIPA ACL.
d. Также, если агентно-ориентированная система является открытой, то должна быть обеспечена безопасность передачи сообщений при помощи криптографии.
4. Выбрать диалоговую логику или задать механизм ее формирования на основе логик агентов-участников. В последнем случае этот механизм должен быть отражён при построении протокола коммуникации (см. предыдущий шаг).
5. Выбрать общие правила и цели диалога, инвариантные по отношению к мнениям агентов-участников, или задать механизм их формирования. В последнем случае этот механизм также должен быть отражён при построении протокола коммуникации (см. шаг 3)
6. Задать критерии выбора оптимальных соглашений.
7. Определить при необходимости механизмы пересмотра мнений, агентов-участников диалога.
Приведённая выше методика является довольно универсальной, благодаря чему может быть вписана в произвольную методологию проектирования агентно-ориентированных систем. Обратной стороной этого является её слабая степень детализации, которая может быть повышена дальнейшими исследованиями в различных методологических рамках.
4.3. Реализация взаимодействия программных агентов в системах класса SRM
В электронной коммерции часто приходится иметь дело с несколькими клиентами или партнёрами по бизнесу. Это поставщики, службы доставки грузов в регионы, платёжные системы, розничные и оптовые покупатели (рис.4.9). При обслуживании заказов довольно значительная часть времени уходит на различные согласования и переговоры (в частности, на выяснение наличия и резервирование товара у поставщика).
| Интернет-магазин |
| Поставщик 1 |
| Поставщик N |
| WEB покупатели |
| запрос- ответ |
| запрос- ответ |
| Служба доставки |
| доставка |
| запрос- ответ |
| платеж |
| Платежная система |
| Рис.4.9. Общая схема работы Интернет-магазина |
При поступлении заказа в интернет-магазин делается запрос поставщику на отгрузку необходимого товара. Аналогичный запрос может быть одновременно послан еще нескольким поставщикам. Ответы могут быть различными. Так, поставщики могут подтвердить заказ, отказать или послать контрпредложение (предложить аналогичный товар или скорректировать сроки). После подтверждения заказа в процессе общения с покупателем, уточняется время и место доставки.
Со временем о каждом поставщике складывается некое представление: он «надёжен», «ненадёжен» или «непредсказуем».
Аналогичную модель можно использовать и во взаимодействии двух программных агентов – участников бизнес-процесса. В результате у агента фирмы (A) складывается представление о конкретном поставщике (агент B) (рис. 4.10).
| B |
| Ag |
| Neg |
| DAg |
| X |
| Bel |
| DBel |
| Pl |
| Dbt |
| A |
| Рис.4.10. Модель представления агента A об агенте B на основе произведения логик |
Обозначим ответы агента B: “Ag”– согласен, “DAg”– несогласен, “Neg”– переговорить (или контрпредложение). Обозначим «мнения» агента А об агенте B. Пусть: “Bel” – уверен, “Pl” – полагает, “DBt” – сомневается, “DBel” – не верит. Пусть p – некое предложение, например «Обеспечить поставку лыж размера 170 см по закупочной цене 100$ в 3 дня».
Тогда возможны следующие 12 вариантов сообщений:
Bel(A, p, Ag(B)) – агент A уверен, что агент B согласится на предложение p;
Bel(A,p,DAg(B)) – агент A уверен, что агент B не согласится на предложение p;
Bel(A, p, Neg(B)) – агент A уверен, что агент B переговорит предложение p;
Pl(A, p, Ag(B)) – агент A полагает, что агент B согласится на предложение p;
Pl(A,p,DAg(B)) – агент A полагает, что агент B не согласится на предложение p;
Pl(A, p, Neg(B)) – агент A полагает, что агент B переговорит предложение p;
Dbt(A,p,Ag(B))– агент A сомневается, что агент B согласится на предложение p;
Dbt(A,p,DAg(B)) – агент A сомневается, что агент B не согласится на предложение p;
Dbt(A,p,Neg(B))– агент A сомневается, что агент B переговорит предложение p;
Dbel(A,p,Ag(B)) – агент A не верит, что агент B согласится на предложение p;
Dbel(A,p,DAg(B)) – агент A не верит, что агент B не согласится на предложение p;
Dbel(A,p,Neg(B)) – агент A не верит, что агент B переговорит предложение p.
Данную схему коммуникаций можно с успехом применить в отношениях между розничным покупателем и фирмой, а также при выборе фирмы подрядчика, предоставляющего услуги доставки. При этом возникает сложная сеть взаимодействий всех участников бизнес-процесса.
| Ф2 |
| Ф1 |
| Ф3 |
| Р1 |
| П1 |
| П2 |
| П3 |
| Д1 |
| Д2 |
| Д3 |
| M1 |
| M2 |
| M3 |
| Р2 |
| Р3 |
| Рис.4.11. Схема отношений участников бизнес-процесса. |
На рис.4.11 обозначено: Р1..Р3 – розничные покупатели, Ф1…Ф3 – фирмы продавцы, Д1…Д3 – службы доставки в регионы, П1….П3 – поставщики, М1…М3 - производители. Из схемы видно, что розничный покупатель может использовать схему отношений с фирмами-продавцами, фирмы-продавцы – со службами доставки и с поставщиками, а поставщики с производителями.
Каждое из этих отношений можно рассмотреть в рамках парадигмы клиент-сервер, где под клиентом подразумевается агент, совершающий запрос. Например, клиентом является интернет-магазин, отправляющий заказ на перевозку товаров из пункта “А” в пункт “Б”. Сервер, в данном случае, транспортная компания, должен обработать этот запрос и отправить ответ в установленной форме. Согласен ли безусловно сервер обслужить клиента, выполнив его запрос, либо он отказывается от заказа, либо необходимо дальнейшее согласование условий выполнения заказа (при этом можно послать свои условия клиенту).
Здесь предлагается следующая унифицированная структура для моделирования взаимодействий реальных и виртуальных агентов в системах электронной коммерции (под виртуальными агентами здесь будем понимать программные модули, а под реальными – конкретные лица или фирмы).
| I |
| Клиент |
| Агент Клиента |
| Агент Сервера 1 |
| Агент Сервера N |
| Сервер 1 |
| Сервер N |
| Агент-посредник |
| Агент-посредник |
| II |
| a |
| a |
| a |
| b |
| b |
| c |
| c |
| Рис.4.12. Инфраструктура взаимодействий агентов, участвующих в электронной коммерции |
На рис.4.12. введены следующие обозначения:
| a |
| b |
Дата добавления: 2015-09-04; просмотров: 49 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Доказательство. 4 страница | | | Доказательство. 6 страница |