1712

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

Диссертация

Информатика, кибернетика и программирование

Программные системы поддержки отношений с клиентами и поставщиками в электронном бизнесе. Моделирование диалога между агентами в подсистемах управлениях отношениями между агентами многоагентных систем. Роль диалога и переговоров во взаимодействиях, реализуемых в системах управления отношениями с поставщиками и клиентами. Многозначные и нечёткие логики в диалоговых задачах ИИ.

Русский

2013-01-06

1.27 MB

121 чел.

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

Специальность 05.13.11 – " Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей "

Диссертация на соискание ученой степени кандидата технических наук


Список основных сокращений

Сокращение

Значение

БД

БЗ

ДцИИ

ИИ

ИС

ИИС

ЛГА

МАС

ПО

ПК

РИИ

СУБД

СRM

SRM

RM

База данных

База знаний

Децентрализованный искусственный интеллект

Искусственный интеллект

Интеллектуальная система

Интеллектуальная информационная система

Локальная группа агентов

Многоагентная система

Программное обеспечение

Программный комплекс

Распределенный искусственный интеллект

Система управления базой данных

Система управления отношениями с заказчиками

Система управления отношениями с поставщиками

Система управления отношениями


Оглавление

Список основных сокращений 2

Введение. 5

Глава 1. Программные системы поддержки отношений с клиентами и поставщиками в электронном бизнесе 14

1.1. Классификация систем электронной коммерции, CRM и SRM-системы 15

1.2. Основные принципы построения современных систем класса CRM и SRM. 26

1.3. Агентно-ориентированный подход к построению RM-систем 27

1.4. Проблемы организации взаимодействия между агентами в МАС 30

Выводы по первой главе. 33

Глава 2. Моделирование диалога между агентами в подсистемах управлениях отношениями между агентами многоагентных систем 34

2.1. Понятие взаимодействия агентов и его основные характеристики 35

2.2. Диалог и переговоры, их роль при построении RM систем 40

2.2.1. Понятия диалога и переговоров 40

2.2.2. Типы диалога 43

2.2.3. Принципы осуществления диалога: максимы Грайса 45

2.2.4. Роль диалога и переговоров во взаимодействиях, реализуемых в системах управления отношениями с поставщиками и клиентами 47

2.3. Общая классификация формальных моделей диалога 48

2.4. Диалоговые сети и коммуникативные акты 50

2.4.1. Теория диалоговых сетей 51

2.4.2. Формальная модель диалога на основе протокола коммуникации 52

2.4.3. Формальная автоматная модель диалога 57

2.5. Теоретико-игровые модели диалога 60

2.5.1 Подход Хинтикки 60

2.5.2. Оперативная семантика П.Лоренцена 61

2.6. Диалоговые игры 63

2.7. Семантики диалоговых логик 65

2.7.1. Семантики Данна-Белнапа 67

2.7.2. Многомерность истинности в диалоге: векторные семантики 67

2.7.3. Распределённость истинности: диалоговые (теоретико-игровые) семантики 69

2.8. Формальное описание диалога с помощью системы правил 69

Выводы по второй главе. 71

Глава 3. Многозначные и нечёткие логики в диалоговых задачах ИИ 74

3.1. Многозначные логики в описании диалогов 74

3.2. Модели диалога на основе произведений логик 75

3.2.1. Подход от лингвистики к логике 75

3.2.2. Произведения решёток и логик, бирешётки 76

3.3. Базовые логики для описания диалогов между агентами 80

3.3.1. Минимальнозначная логика диалога 80

3.3.2. Вывод в четырехзначной диалоговой логике Ldmin 92

3.4. Диалоговое произведение логик и вывод на нем. 99

3.5. Модализированные логики диалога 108

3.6. Некоторые диалоговые логики высокой значности. 115

3.7. Бесконечнозначные (нечёткие) логики диалога. 119

3.8. Логические модели рефлексии агентов 123

Выводы по третьей главе. 133

4. ПРОГРАММНЫЕ АГЕНТЫ ПОДДЕРЖКИ УПРАВЛЕНИЯ ВЗАИМОДЕЙСТВИЕМ С ПОСТАВЩИКАМИ И ЗАКАЗЧИКАМИ 134

4.1 Компьютерное моделирование диалога агентов на базе диалоговых логик 134

4.1.1 Представление знаний, мнений и целей агентов на языке диалоговой логики. 134

4.1.2 Алгоритмы автоматического решения задач с использованием диалоговой логики. 141

4.2 Методика построения агентно-ориентированных систем на базе диалоговых логик 146

4.2.1 Классификация существующих методологий проектирования агентно-ориентированных систем. 146

4.2.2 Методика проектирования взаимодействий между агентами с использованием диалоговых логик. 154

4.3. Реализация взаимодействия программных агентов в системах класса SRM 158

4.4 RM-система управления взаимодействием с поставщиками и заказчиками. 164

Выводы по четвертой главе 168

Заключение 169

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

Приложения..............................................................................................................................................189


Введение.

Актуальность темы исследований. В современном бизнесе набирают силу тенденции клиентоцентризма, заключающиеся в развитии индивидуального подхода к клиенту. Эти тенденции объясняют необходимость построения новых средств математического и программного обеспечения вычислительных комплексов и компьютерных сетей, используемых в бизнесе, в частности, разработки программных систем управления взаимодействиями предприятиями с клиентами (CRM) и поставщиками (SRM). Такие системы должны позволять не только уметь выполнять базовые запросы клиентов, но также замещать менеджера по работе с клиентами в случае, если требования клиентов носят нечеткий характер. В идеале, система должна выполнять любые запросы в автоматическом режиме, допуская вмешательство оператора лишь в наиболее критических или особо важных для бизнеса ситуациях.

В диссертации предлагается использовать агентно-ориентированный подход к разработке и внедрению систем класса CRM и SRM (RM-систем). Целесообразность применения агентно-ориентированного подхода обуславливается характером задач, решаемых в рамках таких систем, а также высокой степенью эффективности при построении масштабируемых систем и систем, поддерживающих автоматическое решение нетиповых задач. Задачи организации взаимодействия и ведения диалога с клиентами или поставщиками предполагают активное участие различных программных подсистем предприятия, таких как Billing (финансовая подсистема), ERP (Enterprise Resource Planning – подсистема планирования ресурсов), производство, продажи и других. Их интеграция в единое целое сама по себе представляет нетривиальную задачу, решаемую на практике методами восходящего проектирования, проблемы применения которых при построении крупных систем общеизвестны. Агентно-ориентированный подход позволяет избежать этих трудностей и при незначительных дополнительных затратах реализовать систему, обладающую высокой степенью масштабирования и гибкости при решении нетривиальных задач.

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

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

Среди наиболее известных работ в области теории агентов и многоагентных систем следует отметить публикации К.Хьюитта, М.Вулдриджа, И.Демазо, Н.Дженнингса, Д.Клини, П.Маэс, Ж.Фербе, И.Шоэма, В.И.Городецкого, И.В.Котенко, Д.А.Поспелова, П.О.Скобелева, А.В.Смирнова, В.Б.Тарасова, В.Ф.Хорошевского и др.

Поддержка управления взаимодействием включает в себя в качестве подзадачи элементы принятия решений. Общие проблемы построения систем поддержки принятия решений рассмотрены в монографиях О.М.Ларичева, А.И.Тихонова и В.Я.Цветкова, Э.А.Трахтенгерца и др., а конкретные примеры разработки таких систем даны в работах А.А.Башлыкова, В.Н.Вагина, А.П.Еремеева, И.Б.Фоминых и др.

В работе используется логический аппарат моделирования диалога в RM-системах, опирающийся на методы многозначной логики (логическую семантику Данна-Белнапа, логические матрицы Тарского-Лукасевича, вывод по аналитическим таблицам Смаллиана). Большой вклад в развитие многозначных логик внесли Я. Лукасевич, Ч.Пирс, Э. Пост, Д.А. Бочвар, Х. фон Вригт, А. Гейтинг, С.К. Клини, Р.Мак-Нотон, Н. Решер, Н. Белнап, М.Гинсберг, М.Фиттинг, А.В.Кузнецов, С.В.Яблонский, В.К. Финн, О.М.Аншаков, А.С.Карпенко, и др. Логическим средствам в ИИ посвящены монографии В.Н.Вагина с сотр., Дж.Минкера, А.Тейза и др., Э.Тернера, а логическим подходам к разработке автономных агентов и многоагентных систем – работы Дж.Аллена, М.К.Валиева, М.Дженесерета, М.Джорджефа, К.Конолиге, П.Коэна, А.Левека, Дж.Мозеса, А.Рао, Г.С.Плесневича, В.Б.Тарасова, Р.Фагина, Дж.Халперна, и др.

Объектом исследования являются распределённые системы управления взаимодействием с поставщиками и заказчиками, разрабатываемые как многоагентные системы (МАС).

Предмет исследования составляют методы представления взаимодействий (диалога) между агентами на основе многозначных логик, а также модели мнений и оценок автономных агентов.

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

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

В диссертационной работе решаются следующие основные задачи:

  1. обоснование целесообразности разработки интегрированной системы управления взаимодействием с поставщиками и заказчиками и её построение как системы с распределенной архитектурой;
  2. разработка агентно-ориентированного подхода к построению RM-систем, включая разработку конкретной многоагентной архитектуры для RM-системы, построение архитектуры и программная реализация отдельных агентов;
  3. анализ методов моделирования диалога между агентами системы с целью построения автоматных моделей и систем, основанных на правилах и протоколах взаимодействия;
  4. построение логик диалога на основе декартова произведения логик агентов-участников диалога и новых операций смешивания;
  5. исследование функциональной полноты диалоговых логик и разработка методов вывода на них;
  6. построение методов представления знаний, мнений и целей агентов на языке диалоговой логики, а также алгоритмов вывода, поиска сопрягаемых ветвей, формирования списка соглашений и поиска оптимального соглашения;
  7. анализ основных методологий построения агентно-ориентированных приложений и формулировка универсального методологического подхода к построению агентно-ориентированных систем на базе диалоговых логик;
  8. разработка программной архитектуры RM-систем, разработка и внедрение агентно-ориентированной системы, основанной на взаимодействии с заказчиками и поставщиками.

Методы исследования. В диссертации использованы методы теории множеств и теории алгоритмов, теории решёток и бирешёток, математической логики и теории программирования, теории агентов и многоагентных систем.

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

Научная новизна работы заключается в разработке логико-математического аппарата для представления диалогового взаимодействия в МАС, формализации модальных оценок и разрешения конфликтов в многоагентной системе на базе произведения логик.

Новыми в диссертации являются:

  1.  модель распределённой открытой системы управления взаимодействием с поставщиками и заказчиками на основе агентно-ориентированного подхода;
  2.  логико-математический аппарат описания диалога на основе диалогового произведения логик;
  3.  механизм комбинированного вывода на базе аналитических таблиц для логик диалога, построенных как диалоговое произведение многозначных логик или нечётких логик;
  4.  универсальный методологический подход к построению агентно-ориентированных систем на базе диалоговых логик.

Практическая значимость работы определяется широким распространением систем класса CRM и SRM и связана с разработкой методов, алгоритмов и программных средств поддержки управления взаимодействием с поставщиком и заказчиком. Она подтверждается результатами использования предложенных моделей и методов в агентно-ориентированной системе взаимодействия с заказчиками и поставщиками, а также пятью свидетельствами об отраслевой регистрации ОФАП. Применение предложенной в работе распределенной агентно-ориентированной архитектуры позволило повысить скорость и качество работы с запросами клиентов, повысило уровень автоматизации взаимодействия с другими подсистемами и регионами. Практическая ценность разработанных моделей представления диалога как диалогового произведения и методов комбинированного вывода на базе аналитических таблиц, заключается в том, что их применение возможно не только в RM-системах, но и в других распределенных многоагентных системах при формализации диалога и разрешении возникающих конфликтов.

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

Основные результаты диссертации были получены при выполнении работ по грантам Российского фонда фундаментальных исследований №04-01-00306 и №07-01-00656. Результаты работы были использованы в учебном процессе кафедры прикладной математики Московского энергетического института (технического университета), кафедры «Компьютерные системы автоматизации производства» МГТУ им.Н.Э.Баумана, а также Института информационных технологий, экономики и менеджмента. Акты о внедрении и использовании результатов работы прилагаются в диссертации. По основным положениям и результатам диссертации были сделаны восемь докладов на научных конференциях. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 12 печатных работах, из них 2 статьи в журналах, рекомендованных ВАК.

На защиту выносятся:

  1.  агентно-ориентированная архитектура распределённой открытой системы управления взаимодействиями с поставщиками и заказчиками;
  2.  диалоговая решётка D4 и минимальнозначная логика Ldmin для работы с диалогами двух агентов;
  3.  диалоговое произведение логик, опирающееся на их декартово произведение и операции смешивания, как основа моделирования сложных диалоговых взаимодействий;
  4.  логика LP8 для представления модальностей мнений агентов, участвующих в диалоге;
  5.  метод комбинированного вывода на диалоговом произведении многозначных и нечетких логик;
  6.  методология проектирования диалога агентов в агентно-ориентированных системах на базе диалоговых логик.

Структура работы.

Глава 1 содержит описание основных проблем разработки современных систем класса CRM и SRM и обоснование необходимости построения открытых распределённых систем. В ней отмечается потребность в организации автоматизированного диалога между поставщиками, заказчиками и агентами системы. Для решения этих проблем предлагается строить системы CRM и SRM на основе многоагентного подхода. Предлагается также использовать аппарат неклассических, в первую очередь, многозначных логик в интересах организации взаимодействия предприятия с поставщиками и заказчиками.

Глава 2 содержит обзор текущего состояния исследований в области моделирования диалогового взаимодействия в МАС. Проведена формализация понятия диалога, дана классификация типов и моделей диалога, исследованы лингвистические и формальные модели диалога, исследована специфика диалога в системах управления с поставщиками и заказчиками.

Глава 3 включает основные теоретические результаты работы. В начале главы содержится критический анализ логических методов моделирования диалога. Анализируются варианты построения диалоговых игр как системы, основанной на правилах взаимодействия. Однако эти модели задают лишь структуру взаимодействия, позволяя строить диалоги различной сложности. Такие модели представляют собой усовершенствованный механизм построения сценариев взаимодействия, который не пригоден для определения семантики переговоров и установления соглашений. Для решения проблемы установления истинности при ведении переговоров, а также для построения адекватного механизма разрешения конфликтов и достижения соглашений предложен подход на базе произведений многозначных логик, лежащих в основе диалогового процесса, и операций смешивания (согласования).

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

В заключении подведены основные итоги работы и кратко описаны ее результаты и направления дальнейших исследований.


Глава 1. Программные системы поддержки отношений с клиентами и поставщиками в электронном бизнесе

Задачей CRM-системы является обеспечение высокого уровня индивидуализации взаимодействия компании с ее клиентами. В связи с массовостью современных рынков такое взаимодействие становится возможным, только если система предоставляет достаточно высокую степень автоматизации и интеллектуализации.

К сожалению, большая часть современных CRM-систем построена по принципу жёсткой алгоритмизации возможных взаимодействий, и решение сколько-нибудь нетиповых задач ставит их в тупик. [4]

Индивидуализация достигается за счет сохранения всей доступной информации о клиенте: личной (пол, возраст, место жительства), и истории запросов к системе (что покупал, чем интересовался, на что жаловался и т.д.) Собираемая информация анализируется вручную, и на ее основании могут реализовываться целевые программы и акции, направленные на конкретные группы клиентов. Также клиенты могут классифицироваться по степени лояльности. Это помогает, например, сокращать издержки при использовании кредитных программ.

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

Аналогичные проблемы возникают и в системах класса SRM. Их меньшая распространённость связана с тем, что современные компании в первую очередь ориентируются на потребителя. [175,114] Но это не делает задачи взаимодействия с поставщиками неактуальными.

В настоящей главе рассмотрены структура и механизмы работы современных систем класса CRM и SRM, а также предложен новый децентрализованный агентно-ориентированный подход к построению подобных систем.

1.1. Классификация систем электронной коммерции, CRM и SRM-системы

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

Согласно наиболее общей классификации, системы электронного бизнеса разделяются на: B2B, B2C, B2G, C2B, C2C, B2E (см. таблицу 1.1).

Таблица 1.1. Классификация систем электронной коммерции.

Аббревиатура

Расшифровка

Пояснение

Примеры

B2B

Business to Business

Ведение бизнеса между крупными компаниями, интернет-биржи, системы оптовой торговли.

business2business.ru, lke.ru,

polypipe.ru, torg.azovmetallosnab.com

torg.severstal.ru

rusbiz.ru

B2C

Business to Customer

Розничные интернет-магазины, аукционы, обратные аукционы

amazon.com, ozon.ru, bolero.ru, kant.ru

B2G

Business to Government

Охватывают сферу бизнес-отношений государства с гражданами, а также граждан и государственных органов между собой.

mosnalog.ru

C2B

Customer to Business

Системы поддержки онлайновых розничных покупок, предложения частных лиц. Предоставляет потребителю возможность самостоятельно устанавливать стоимость для различных товаров и услуг, предлагаемых компаниями.

priceline.com

C2C

Customer to Customer

Так называемые web-барахолки, сайты для частных лиц, где можно продать или купить что-либо

web-bazar.ru, baraholka.ru, sportbazar.ru, eBay.ru, molotok.ru

B2E

Business to Employee

Поддержка взаимоотношений компании и служащих, сайты вакансий и поиска работы

job.ru

B2B – системы обеспечивающие взаимодействие между компаниями. Программные средства, которые необходимы для систем электронной коммерции, составляют класс прикладного программного обеспечения B2B. Такие программные средства базируются, естественно, на Web-технологиях, т. е. на языках разметки XML и HTML, протоколах HTTP и FTP. Аналитики считают, что для B2B применение стандарта языка XML сыграет такую же определяющую роль, какую имел в 90-х годах общепринятый стандарт HTML для распространения информационных ресурсов Web. Значительную часть программного обеспечения B2B составляют средства интеграции корпоративных информационных систем класса ERP, таких, например, как R/3 фирмы SAP AG, с системами электронной коммерции.

Одной из форм реализации системы Электронной Коммерции класса B2B является электронная торговая площадка (ЭТП) (Рис. 1.1.). ЭТП – это web-сайт, предназначенный для непосредственной организации он-лайн деятельности специалистов служб закупок и сбыта различных предприятий. На электронной торговой площадке создаются автоматизированные рабочие места (АРМ) для специалистов по сбыту или снабжению и для обеспечения их необходимыми сервисами. Это может быть создание и поддержка фирменных каталогов, поиск продавцов и покупателей, проведение тендеров, аукционов и других видов конкурсов в режиме он-лайн, комплекс средств интерактивного он-лайн взаимодействия контрагентов, маркетинговый и конъюнктурный анализ, предконтрактная и контрактная подготовка, проведение платежей поставщикам и контроля поставок. ЭТП может фактически предоставлять все функции, необходимые для обеспечения сбыта и снабжения. Электронная торговая площадка представляет собой сложноорганизованную систему со своей инфраструктурой. Её функционирование обеспечивает группа специалистов в данной предметной области, служба технической поддержки и другие сервисные службы. Работа на торговой площадке является, как правило, платной. Причем на некоторых торговых площадках взимается комиссия (в размере нескольких процентов или долей процента) от проводимых операций (транзакций). На других площадках доступ оплачивается фиксированной суммой, не зависящей от проводимых операций. При этом стоимость работы на торговой площадке несопоставимо ниже стоимости создания своего интернет-магазина или своей электронной службы снабжения.

Компания5

B2B

система

Компания2

Компания3

Компания4

Компания6

Компания7

Компания1

WEB

Рис.1.1. Иллюстрация системы класса B2B

B2C - бизнес для Потребителя (B2C) является наиболее популярной формой электронной коммерции на сегодняшний день. В этом случае деятельность нацелена на прямые продажи для потребителя. Один из самых крупных примеров B2C - это www.amazon.com, американский книготорговый сайт, услугами которого пользуются более 30 миллионов клиентов по всему миру. Именно он сумел подорвать обычный букинистический рынок США в течение нескольких лет. При решённых проблемах с доступом в Интернет в регионах, надежной работой платежных систем и служб доставки, B2C эффективен для устранения различий между крупными городами и удаленными регионами в смысле доступности товаров и услуг для потребителя. B2С создает новую технологию продаж, которая облегчает доставку товаров и услуг потребителям в любой части мира. Еще один плюс B2C - прямые продажи с минимальным количеством посредников. Устранение посредников в идеале дает возможность устанавливать конкурентные цены на местах и даже увеличивать их (исключая процент посредников), что естественно приведёт к росту прибыли.

B2Gсистемы поддержки взаимоотношений компаний с государством. Применяются для сбора налогов, регистрации транспортных средств, регистрации патентов, выдачи необходимой информации и т.д. В результате сокращается объем бумажной работы, а проведение необходимых процедур значительно ускорится. То, что раньше требовало от граждан долгого стояния в очередях, общения с правительственным чиновником и производства и перемещения большого количества бумажных документов, теперь происходит в течение нескольких минут. Развитие моделей взаимоотношений субъекта с государством может привести к принятию важных законов путем всеобщего, тайного онлайнового волеизъявления на правительственном сайте. Каждый недовольный каким-либо законом сможет выразить свое мнение, и, при накоплении определенной "критической массы", такой закон автоматически будет включён в повестку дня законодателей.

C2C - потребитель для потребителя. Хорошо известный пример компании типа C2C – eBay – компания по проведению онлайновых аукционов. eBay представляет собой "виртуальное торговое сообщество потребителей", где каждый человек может покупать и продавать вещи. Из Российских компаний, таковыми являются molotok.ru и baraholka.ru. Таким образом, аукционы eBay, www.molotok.ru и www.baraholka.ru, являются прекрасным примером проведения сделок типа C2C посредством Интернета.

C2B - потребитель для Бизнеса. Системы данной архитектуры также называют “Предприятие, управляемое клиентом”. Предоставляет потребителю возможность самостоятельно устанавливать стоимость для различных товаров и услуг, предлагаемых компаниями. Этот вид электронной коммерции является наименее развитым по сравнению с остальными. В качестве примера можно привести американскую компанию www.priceline.com, которая даёт возможность своему покупателю назвать цену, за которую он хотел бы купить товар или услугу. Таким образом, формируется спрос, который не означает, что совершится продажа по запрошенной цене. Продавец, пользуясь данными текущего спроса, принимает окончательное решение. Сайт C2B выступает в роли посредника-брокера в попытке найти продавца за сформированную предложениями покупателей цену.

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

Система управления взаимодействием с клиентами (Customer Relationship Management System, CRM-система) — корпоративная информационная система, предназначенная для улучшения обслуживания клиентов путём сохранения информации о клиентах и истории взаимоотношений с клиентами, установления и улучшения бизнес-процедур на основе сохранённой информации и последующей оценки их эффективности. Её основные принципы таковы:

  1.  наличие единого хранилища информации, откуда в любой момент доступны все сведения обо всех случаях взаимодействия с клиентами;
  2.  синхронизированность управления множественными каналами взаимодействия (то есть существуют организационные процедуры, которые регламентируют использование этой системы и информации в каждом подразделении компании);
  3.  постоянный анализ собранной информации о клиентах и принятии соответствующих организационных решений — например, сегментация клиентов на основе их значимости для компании.

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

Классифицируют возможности (модули) CRM по функциональности и уровням обработки информации. По функциональности выделяют блоки:

  1.  продажи;
  2.  маркетинг;
  3.  сервисное обслуживание.

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

По уровням обработки информации:

  1.  Оперативный — регистрация и оперативный доступ к первичной информации по Событиям, Компаниям, Проектам, Контактам, Документам и т. д.
  2.  Аналитический — отчётность по первичным данным и самое главное более глубокий анализ информации в различных разрезах (воронка продаж, анализ результатов маркетинговых мероприятий, анализ эффективности продаж в разрезе продуктов, сегментов клиентов, регионов и т. п.)
  3.  Коллаборационный (англ. collaboration - сотрудничество; совместные, согласованные действия) — уровень организации тесного взаимодействия с конечными потребителями, клиентами, вплоть до влияния клиента на внутренние процессы компании (опросы, для изменения качеств продукта или порядка обслуживания, web-страницы для отслеживания клиентами состояния заказа, уведомление по SMS о проведённых транзакциях по банковскому счету, возможность для клиента самостоятельно скомплектовать и заказать в online, к примеру, автомобиль или компьютер из доступных блоков и опций и др.)

Ранее (примерно до 2000 года) CRM-системы, как правило, были «однобоки» (так называемые «менеджеры контактов», или системы поддержки маркетинговых мероприятий, или системы для автоматизации сервисных служб). Однако к 2006 году практически все современные CRM-системы получили в большей или меньшей степени все указанные возможности и уровни обработки информации. [134]

Основными целями систем класса CRM является автоматизация процесса продаж и повышение качества взаимоотношений с клиентами. Эти системы, чаще всего, ориентированы на поддержку всего цикла взаимоотношений с клиентами, начиная от момента установления первого контакта, до «закрепления» клиента за фирмой и его последующего обслуживания. Основной целью стратегии CRM является привлечение новых клиентов посредством маркетинга, и удержание старых. Главными факторами, заставляющими клиента обратиться в ту же компанию (где он уже имел опыт взаимодействия), являются положительный опыт работы и выгодные условия сделки. Персонификация продаж с учетом привычек, предпочтений клиента позволяет создать наиболее выгодное предложение для клиента.

Среди основных компонентов системы класса CRM можно выделить:

  1.  Инструментарий управления контактами с клиентами. Эти средства включают базу данных о клиентах (фамилия, телефон, адрес, хобби, предпочтения, привычки и др.), а также историю взаимодействий.
  2.  Средства контактирования с клиентами (электронная почта, web-форумы, конференции, чаты, телефония).
  3.  Аналитические средства. Предоставляют различные отчёты по результатам взаимодействия с клиентами.

Следует отметить, что CRM-система может быть как частью общей системы управления бизнесом компании, например, частью ERP, так и самостоятельной системой управления взаимоотношениями с клиентами.

Основными модулями системы класса CRM являются: модуль автоматизации торговли, модуль автоматизации маркетинга, модуль поддержки и информационного обеспечения клиентов.

Основными функциями модуля автоматизации торговли являются:

  1.  Взаимодействие с клиентами – ведение баз данных по продажам, управление контактами, генерация специальных товарных предложений.
  2.  Генерация и обновление каталогов товара, прайс-листов.
  3.  Ведение отчётности по продажам, прогнозирование продаж, оценка наличия товара на складе и в соответствии с этим генерация заказов поставщикам.

Главными функциями модуля автоматизации маркетинга являются:

  1.  Выделение основных целевых аудиторий маркетинговой акции.
  2.  Проведение акций, ориентированных на конкретную целевую аудиторию, используя различные каналы общения с покупателями (в результате клиент получает полезную информацию, соответствующую его интересам).
  3.  Оценка эффективности маркетинговых и рекламных кампаний, управление стоимостью компании в целом и отдельными событиями.

Основными функциями модуля поддержки и информационного обеспечения клиентов являются:

  1.  Сбор и хранение заявок на обслуживание от клиентов посредством всевозможных средств взаимодействия (телефон, e-mail, личная встреча и др.)
  2.  Управление базой знаний о типичных проблемах (FAQ – часто задаваемые вопросы), а также способы их разрешения.
  3.  Контроль над выполнением заявок, с учётом предпочтений клиентов.
  4.  Обратная связь с клиентами – получение оценки степени удовлетворенности клиента деятельностью различных служб предприятия.

Ключевыми входными данными систем класса CRM являются данные о клиентах, указанных при регистрации: имя, фамилия, координаты и предпочтения. Впоследствии исходный «портрет» клиента дополняется сведениями, собранными в процессе взаимодействия: история покупок, доверенные лица, график работы, семейное положение, и многое другое. Система CRM «помнит» всё о покупателе, учитывая эти сведения при взаимодействии с ним.

Системы управления взаимодействием с поставщиками (Supplier Relationship Management System, SRM-система) – корпоративная информационная система, предназначенная для улучшения обслуживания поставщиков, путём сохранения информации о истории взаимоотношений и выполняемых поставках.

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

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

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

1.2. Основные принципы построения современных систем класса CRM и SRM.

Типовая архитектура современной системы класса CRM/SRM представлена на рис 1.2.

 

БД

Серверы

бизнес-логики

Операторы

Операторы

Клиенты/ поставщики

Интернет/ Интранет

Другие подсистемы

(Аналитика, ERP, и пр.)

Регион 1

Регион 2

Рис.1.2 Общая архитектура RM-системы

В состав системы входят: серверы обработки бизнес-логики, машины операторов, БД часто распредёленная. Связь осуществляется через интернет или интранет при помощи таких механизмов, как MSMQ, RPC, Web-служб, COM+, NET.Remoting и др.

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

В каждом отдельном регионе обычно устанавливается свой экземпляр системы, что приводит к тому, что в сложных случаях, требующих участия систем из разных регионов, выполнение запроса клиента возможно только с активным участием операторов и служб технической поддержки. Это происходит в силу следующих причин:

  1.  в разных регионах, как правило, используются собственные БД;
  2.  в разных регионах могут использовать различные версии системы;
  3.  в разных регионах применяются различные настройки и используются разные механизмы, тарифы и политики.

Итак, к недостаткам типичных систем класса CRM и SRM можно отнести следующее:

  1.  Недостаточную гибкость системы при работе с новыми или нетиповыми случаями запросов.
  2.  Трудности взаимодействия систем, установленных в различных регионах или на различных предприятиях.

Для преодоления этих трудностей предлагается использовать агентно-ориентированный подход к построению систем класса CRM и SRM.

1.3. Агентно-ориентированный подход к построению RM-систем

Существенные перспективы открывает использование технологии программных агентов, в рамках стратегической системы управления бизнесом на предприятии. Известно, что, программный агент, это – автономная программная единица, имеющая цель, ресурсы для ее достижения, способная адаптироваться к ситуации, а также способная вступать в контакт с другими агентами. Внедрение агентов в систему позволяет решать многочисленные задачи без участия человека, а также позволяет интегрировать многочисленные разрозненные приложения в единую систему. Например, «агентизация» всего комплекса программ управления компанией (как правило, программ не интегрированных, и не «понимающих» друг друга при взаимодействии) с помощью продуктов BeeGent [80], позволяет существенно повысить эффективность взаимодействия различных приложений. Также агенты могут выступать как посредники между менеджером (владельцем агента) и объектом управления (процесс, компания, отдел, и т.д.). Возможности мобильных агентов предполагают миграцию по различным узлам корпоративной сети, и выполнение своего кода на различных платформах. Главными преимуществами агентно-ориентированного подхода к построению ИИС предприятия являются:

  1.  Эффективное взаимодействие различных бизнес приложений.
  2.  Поддержка взаимодействия в транснациональных корпорациях (в различных часовых поясах, валютах и т.д.)
  3.  Существенное сокращение расходов на поддержание рутинных и механических процессов.

На рис 1.3 представлена структура агентно-ориентированной RM-системы. Такая система состоит из следующих частей:

  1.  GUI – интерфейс пользователя.
  2.  Оперативная БД – база данных, хранящая информацию о запросах, пользователях, ресурсах и т.п. Аналогична базе данных не агентно-ориентированной системы.
  3.  БД Онтологии – хранит информацию о предметной области и о способах конструирования формальных запросов.
  4.  Агенты-координаторы – агенты, отвечающие за выполнение запроса поставщика или клиента.
  5.  Агенты бизнес-логики – агенты, ответственные за исполнение того или иного конкретного запроса.
  6.  Агент-субординатор – агент, отвечающий за планирование и контроль деятельности агентов системы.

Оперативная

БД

БД Онтологии

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

Клиент / Поставщик / Оператор

Агенты

бизнес-логики

(агенты исполнители)

Формальный запрос

GUI

Вербальный запрос

Другие классические подсистемы

(Аналитика, ERP, и пр.)

Другие регионы

Другие агентно-ориентированные подсистемы

Агент-субординатор

Рис.1.3. Общая структура агентно-ориентированной RM-системы.

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

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

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

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

Детальный анализ диалоговых систем в ИИ и построение такого механизма взаимодействия будет проведено в главе 2.

1.4. Проблемы организации взаимодействия между агентами в МАС

Проведённый ранее анализ систем класса CRM и SRM выявил их близость с идейной и технической точек зрения, позволив выделить более общий класс систем поддержки взаимоотношений, RM-систем (Relation Management system).

Выделим основные функции RM-систем:

  1.  Сохранение и использование информации о контактах, эффективное планирование контактов в аспекте их временного, технического и физического распределения для каждого агента системы.
  2.  Сохранение и использование истории взаимодействия, извлечение знаний о предпочтениях, интересах, намерениях, использование её в целях оптимизации взаимодействия и повышения уровня кооперации (лояльности) между агентами-участниками.
  3.  Предоставление эффективных средств и механизмов контроля и управления, в том числе автоматического, взаимодействием агентов системы, распределением ресурсов, установкой приоритетов и стратегией коммуникации.

Представим графически схему функционирования RM-систем, организовав её по известному принципу пирамиды потребностей А. Маслоу. (см. рис 1.4.) Подобное представление становится возможным, так как для обеспечения функциональности высокого уровня необходима реализация более простых функций. Так без сохранения контактов, невозможно вообще любое обращение к клиентам со стороны компании, сохранение истории взаимодействия позволяет различать агентов, их интересы и потребности, а управление приоритетами и ресурсами позволяет сосредоточить свои усилия на наиболее перспективных и важных для компании направлениях.

Управление контактами

Управление отношениями

Управление стратегией

Рис 1.4. Пирамида задач, решаемых в рамках RM-системы.

Рассматривая задачу шире, в рамках теории многоагентных систем можно утверждать, что в любых МАС необходима подсистема управления взаимодействиями между агентами, в той или иной мере выполняющая вышеперечисленные функции. При отсутствии такой системы или замещающего ее механизма (например, архитектуры доски объявлений, или иного механизма координации) взаимодействие между агентами становится невозможным, как и само существование системы как единого целого. Наличие полнофункциональной RM-системы выводит МАС на новый уровень самоорганизации, упрощая взаимодействие между агентами системы, масштабирование системы, интеграцию различных МАС, позволяя агентам использовать и накапливать коллективные знания о других агентах, что несомненно делает их взаимодействие более эффективным.

Очевидно, что основным направлением исследования при построении RM-систем должен стать анализ и формализация процессов коммуникативного взаимодействия (диалога) агентов.


Выводы по первой главе.

Следующие основные результаты, были получены в первой главе:

  1.  Описаны структура и функции систем класса CRM и SRM. Выявлены недостатки классической архитектуры.
  2.  Сформулированы основные принципы построения CRM и SRM-систем. Выявлены проблемы, затрудняющие разработку и функционирование подобных систем.
  3.  Предложен агентно-ориентированный подход к построению систем класса SRM и CRM, проведён сравнительный анализ классических и агентно-ориентированных RM-систем.
  4.  Обоснована необходимость наличия RM-подсистем в МАС, что позволяет использовать результаты диссертации при построении МАС в других предметных областях.
  5.  Разработана общая программная архитектура RM систем, описаны подходы к ее реализации.

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


Глава 2. Моделирование диалога между агентами в подсистемах управлениях отношениями между агентами многоагентных систем

Как было показано в первой главе, центральной проблемой при построении МАС для RM-систем, является проблема обеспечения диалога между агентами.

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

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

2.1. Понятие взаимодействия агентов и его основные характеристики

Взаимодействие агентов — вот первое, что выступает перед нами, когда мы говорим о создании MAC. Взаимодействие означает установление двусторонних и многосторонних динамических отношений между агентами. При этом оно является одновременно источником и продуктом некоторой организации. Иными словами, взаимодействие представляет собой не только следствие каких-либо действий, выполняемых агентами в MAC в одно и то же время, но и необходимое условие формирования виртуальных коллективов и искусственных сообществ. Один из лозунгов синергетического ИИ гласит: «нет знаний без взаимодействия!»

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

Когда-то Платон утверждал, что необходимыми условиями взаимодействия являются соразмерность и согласованность вступающих в него объектов. Аристотель [5] подчеркивал, что взаимодействовать могут тела, находящиеся в определённом (возбуждённом) состоянии и вблизи друг от друга. Еще одним атрибутом взаимодействия нередко выступает ритмичность, выражающая соотношение между аспектами его устойчивости и изменчивости.

Главными характеристиками любого взаимодействия являются направленность, избирательность, интенсивность и динамичность. Всё это в полной мере относится и к взаимодействиям агентов. Во-первых, взаимодействия между агентами имеют определённую направленность — положительную или отрицательную, т. е. носят характер содействия или противодействия, притяжения или отталкивания, кооперации или конкуренции, сотрудничества или конфликта, координации или субординации, и т.п. Так содействие агентов друг другу означает их взаимопомощь, когда действия одних агентов помогают действиям других. Происходит согласование индивидуальных действий в интересах усиления конечного эффекта (достижения синергии). Содействие перерастает в кооперацию при наличии общей цели, взаимной адаптации и широком использовании возможностей друг друга. Наоборот, в случае противодействия агенты мешают друг другу, препятствуют достижению индивидуальных целей каждого.

Помимо этих базовых полярных видов взаимодействия возможны промежуточные ситуации. Наиболее очевидной представляется ситуация взаимного уклонения от взаимодействия, например, ввиду антипатии агентов. Кроме того, содействие может быть не только двунаправленным, но и однонаправленным (вырожденный случай). При этом один агент способствует достижению целей другого, а второй уклоняется от взаимодействия. Примером может служить ситуация обучения, когда один агент (учитель) стремится обучить другого, а второй отказывается обучаться и лишь имитирует понимание. Нередко встречается и «зеркальная» ситуация однонаправленного противодействия, когда один агент препятствует действиям другого, а тот, в свою очередь, уклоняется от встречи с первым. Наконец, при контрастном взаимодействии получаем противоречие: один агент старается содействовать другому, а тот активно ему противодействует.

Во-вторых, взаимодействия между агентами избирательны. При формировании MAC взаимодействуют лишь такие агенты, которые некоторым образом соответствуют друг другу и поставленной задаче. При этом агенты могут быть связаны в одном отношении и независимы в другом. Одни агенты могут взаимодействовать друг с другом с большей лёгкостью, а другие — с меньшей. Например, взаимодействие облегчается в случае пространственного сближения агентов, их гомогенизации, предварительного знакомства друг с другом и т. п.

В-третьих, взаимосвязи и взаимозависимости между агентами обычно не сводятся к дихотомическому случаю («связь присутствует» или «связь отсутствует»), а характеризуются некоторой силой (интенсивностью). Например, «агент аm сильно зависит от агента аi» или «агент aj мало взаимодействует с агентом аk». Как правило, каждый агент одновременно, но с разной интенсивностью взаимодействует с несколькими другими агентами.

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

Социальные нормы выступают как важнейшие ориентиры взаимодействия агентов. Особым видом социальной нормы в MAC является соглашение между агентами. Преимущество такого соглашения состоит в его устойчивости. Нет смысла заключать соглашение, если предварительно известно, что кто-нибудь из агентов уклонится от его выполнения.

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

Общая проблема анализа взаимодействий между агентами включает следующие задачи:

  1.  идентификация ситуации взаимодействия агентов;
  2.  выделение основных ролей агентов в MAC и распределение их между агентами;
  3.  определение числа взаимодействующих агентов;
  4.  определение типов взаимодействующих агентов;
  5.  построение формальной модели взаимодействия;
  6.  определение набора возможных стратегий агентов;
  7.  определение множества коммуникативных действий.

В целом, многообразные ситуации взаимодействия агентов необходимо анализировать на различных уровнях. Сложная ситуация реального взаимодействия, в которой всегда переплетены кооперативные и конфликтные аспекты, распадается на более простые ситуации. В частности, следует отличать макроситуацию, когда учитываются взаимодействия всех агентов MAC, от микроситуаций, в которых подлежат рассмотрению лишь отдельные, локальные взаимодействия. При таком подходе можно ранжировать по значимости различные виды взаимодействий и точно определить их место в MAC. Например, развитие сотрудничества агентов в MAC может стимулироваться отношениями локального соперничества.

Рассмотрим основные функции коммуникации по Р.Якобсону (см. [97]) и их место в диалоге агентов. Выразительная (экспрессивная) функция сфокусирована на агенте-источнике информации: она выражает отношение агента к тому, что он стремится передать другому. Напротив, конативная функция сосредоточена на агенте-приемнике информации. В свою очередь, фатическая функция направлена не столько на передачу информации, сколько на обеспечение контакта между агентами. Эстетическая функция связана с формой сообщения, а металингвистическая функция отсылает на код (она используется для определения значения того или иного слова). Референциальная функция основана на контексте.

Контекст – это ситуация, в которой находятся взаимодействующие агенты, причем контексты источника и приёмника могут различаться. По мнению Ю.М.Лотмана [56], различие контекстов у агентов при их коммуникации превращает сам процесс взаимодействия из пассивной передачи информации в конфликтную игру, в ходе которой каждая сторона стремится изменить цели и мнения противоположной стороны.

В контексте анализа взаимодействия агентов и их групп представляет интерес концепция групповой динамики К.Левина, опирающаяся на его теорию поля. Подобно тому, как индивидуальный агент и его окружение формируют психологическое поле, группа агентов и ее окружение образуют социальное поле. Групповое поведение в любой момент времени является функцией общего состояния социального поля. Оно определяется конкурирующими подгруппами в группе, отдельными агентами, ограничениями и каналами общения (см. [117]). В групповой динамике введено понятие валентности, близкое к направленности. Здесь валентность характеризует взаимное притяжение или отталкивание агентов: положительная валентность отражает стремление агентов в определенный район «силового поля», отрицательная — движение в обратную сторону.

В книге [33] анализируются такие виды взаимодействия, как кооперация и конкуренция. Выделяются две разновидности кооперативных отношений: союзничество (аддитивный эффект объединения агентов) и партнерство (мультипликативный эффект объединения агентов). Важным показателем степени кооперации служит количество включенных в нее агентов. Конкуренция характеризуется отрицательным эффектом объединения агентов, а конфликт чреват приближением к гомеостатическим границам агентов.

Характерным примером взаимодействия является диалог. Слово диалог греческого происхождения и изначально означает тип речевой коммуникации, осуществляемый при помощи обмена сообщениями между двумя и более лицами [159]. Очевидно, что понятие диалог в данной интерпретации охватывает весь спектр речевого взаимодействия и отличается лишь от монолога, который тем не менее можно рассматривать как внутренний рефлексивный диалог.

2.2. Диалог и переговоры, их роль при построении RM систем

Прежде чем рассматривать различные модели диалога, следует определиться с содержанием понятия диалог. Понимание диалога как взаимодействия требует уточнения, так как сам термин взаимодействие интерпретируется по-разному. В данной диссертации будем рассматривать диалог в русле теории коммуникации.

2.2.1. Понятия диалога и переговоров

Несмотря на то, что диалог как литературная форма известен с древнейших времён, серьезные исследования диалога и построения первых моделей диалогового взаимодействия начались лишь в середине ХХ-го века. В первую очередь следует упомянуть работы родоначальника теории речевых (коммуникативных) актов Дж. Остина [64].

Остин предложил рассматривать каждое высказывание субъекта диалога как речевой акт. Каждый речевой акт при этом состоит из трёх аспектов локутивного, иллокутивного и перлокутивного. Подобная трёхуровневая форма анализа высказывания предполагает выделение локутивного акта (от латинского locutio «говорение»), как акта говорения, который в свою очередь включает в себя произнесение звуков (акт фонации), употребление слов, связывание их по правилам грамматики, обозначение с их помощью тех или иных объектов (акт референции), приписывание этим объектам тех или иных свойств и отношений (акт предикации), иллокутивного акта, то есть речевого акта, рассматриваемого с точки зрения его внеязыковой цели (вопрос, утверждение, информирование предупреждение и т.д), и перлокутивного акта, то есть речевого акта, рассматриваемого в аспекте его реальных последствий для субъектов диалога. В данной работе нас в первую очередь интересуют модели, находящиеся на втором и третьем уровне анализа коммуникативного акта.

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

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

Переговоры в МАС представляют собой механизм координации (самоорганизации) действий агентов с целью установления устойчивого динамического распределения ресурсов, удовлетворяющего коллективным требованиям агентов МАС и не противоречащему их индивидуальным интересам.

Переговоры агентов можно интерпретировать как распределённый процесс поиска в пространстве потенциальных соглашений. Этот процесс является нелинейным, поэтому обычно пространство поиска не уменьшается, пока решение не достигнуто, так как цели агентов могут немного измениться или стать совершенно новыми. В большинстве случаев, каждый отдельный агент «обрабатывает» только часть общего пространства поиска и, в ее пределах существует область, которая удовлетворяет его ожиданиям. Каждый агент имеет определённый набор целей в пределах точек соглашений, которые являются приемлемыми для этого. Поиск успешно завершается, когда точка соглашения достигнута, т.е. там существует непустое пересечение среди индивидуальных мест. Процесс заканчивается, когда заканчивается поиск, независимо от его успеха или неудачи.

Если агент а1, нуждается в сотрудничестве относительно некоторой константы p, это порождает глобальный запрос сотрудничества, на который агенты системы отреагируют отображением их готовности рассмотреть данный запрос. Когда другой агент, например а2, получает сообщение от агента а1, запрашивая сотрудничество для определенной литеры - диалог начинается между а1 и а2, в котором они договорятся о получении p. Чтобы сотрудничать, агент а2 пытается строить план, который не должен конфликтовать с его собственными намерениями. Если знания агента недостаточно для построения плана, диалог может быть продолжен со встречным предложением. Если агент а1 не может принять это встречное предложение, агент а2 может сделать запрос другому агенту в группе, например к агенту а3, приостанавливая диалог с а1 и устанавливая новый с а3. Диалог между двумя агентами продолжается, пока соглашение не достигнуто, или один из них решает, что не способен сотрудничать. Эта последняя ситуация могла возникнуть из-за недостатка знания, или конфликтов среди целей. Если существует конфликт между агентом а1 и агентом а2, первый может повторить его запрос, но на сей раз с большей силой. Существование конфликтов между агентами а2 и а3 может также предотвратить успешное завершение диалога между а1 и а2. В этих случаях, модель переговоров предлагает, что агент а2 сообщил агенту а1, что конфликт с агентом а3 препятствует этому сотрудничеству; следовательно, агент а1 должен быть тем, который направляет агента а3 на решение конфликта и достижение соглашения.

2.2.2. Типы диалога

Значимым результатом исследований диалога явилась классификация типов диалога, предложенная теоретиками аргументации Д.Вальтоном и Э.Краббе [179]. Эта классификация основана на информации о протекании диалога, которой обладают его участники (релевантности к теме обсуждения), их индивидуальных целях, и коллективных интересах, которые они разделяют.

В диалоге поиска информации (information-seeking dialogue) один из участников ищет ответ на некоторый вопрос (вопросы), обращаясь к другим участникам, которые, по его мнению, знают ответ на этот вопрос.

В диалоге выявления знаний (inquiry dialogue) участники сотрудничают для получения ответа на вопрос (вопросы), ответ на который изначально неизвестен ни одному из участников диалога.

В диалоге убеждения (persuasion dialogue) один из участников пытается убедить другого принять суждение, которое тот изначально не разделяет.

В диалоге торгов (negotiation dialogue) участники торгуются, пытаясь установить удовлетворяющее всех распределение дефицитного ресурса, пусть даже оно и будет ущемлять индивидуальные интересы некоторых из них.

В диалоге принятия решений (deliberation dialogue) участники сотрудничают чтобы принять решение о том, какое действие или курс выбрать в некоторой ситуации. Участники диалога делят ответственность за принятое решение или, по крайней мере, демонстрируют желание обсудить, будут ли они нести ответственность за такое решение. Следует иметь в виду, что наилучший образ действий для группы может конфликтовать с убеждениями или намерениями отдельных членов группы, кроме того ни один из участников может не обладать всей информацией, необходимой для определения лучшего для группы варианта.

В диалоге-полемике (eristic dialogue) обмениваются словесными выпадами, заменяя физический конфликт вербально, с целью выражения скрытых обид.

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

Однако, следует учитывать, что большая часть реальных диалогов, как между людьми, так и между программными агентами является комбинацией двух или нескольких из описанных типов диалога. Например, выполнение запроса к системе CRM о доступных услугах, может перерасти в диалог, направленный на убеждение клиента воспользоваться той или иной возможностью, который затем перерастает в диалог торгов о стоимости данного действия. Обе стороны могут как быть осведомлены о различной природе текущей стадии диалога в каждой фазе, и о смене фаз, как и не иметь об этом представления. Экземпляры одного типа диалога, включённого в другой, называются вложенными (embedded) диалогами [161]. Таким образом, наличие формальной системы описания диалога, включающей средства конструирования вложенных диалогов описанных выше типов, является необходимым условием адекватной формализации диалогового процесса.

2.2.3. Принципы осуществления диалога: максимы Грайса

Для понимания принципов взаимодействия в процессе диалога не достаточно только описание диалога, данное средствами синтактики или семантики. Важную роль играет прагматический аспект такого взаимодействия. В этой связи в первую очередь следует обратить внимание на работы Пола Грайса [146] посвящённые анализу правил коммуникации, основанных на соблюдении определенных условий, названных им условиями кооперации. Соблюдение этих условий делает возможным конструктивный диалог. Смысл предложенного принципа заключается в том, что участники диалога сотрудничают имея общей целью достижение взаимопонимания. В рамках кооперативных отношений между агентами выделяются следующие коммуникативные правила, называемые максимами Грайса (принципы «идеального диалога»).

1. Максима количества информации (принцип оптимума количества информации). 

Передаваемая в процессе диалога агенту информация должна быть достаточной для его действий. Иными словами, сообщение не должно содержать информации, большей, чем требуется агенту, Перефразируя правило «бритвы» Оккама, можно сказать: «Не умножайте в диалоге сообщения сверх надобности».

2. Максима качества информации (принцип честности агентов или принцип минимума ложной информации).

В диалоге один агент не должен сообщать ложную информацию другому агенту. Эту максиму можно также выразить «судебной» формулой «Говори правду и только правду» или высказыванием «Не говори того, на что у тебя нет достаточных оснований».

3. Максима релевантности информации.

Передаваемая при взаимодействии агентов информация должна соответствовать контексту диалога. Это можно выразить фразой «Говори по делу».

4. Максима способа (формы) выражения информации.

Передаваемая информация должна быть краткой, точной и упорядоченной. Здесь уместны высказывания «Будь краток». «Избегай неясных выражений».

Любой правильный речевой акт должен удовлетворять принципу координации и четырём максимам Грайса. Для обеспечения совместимости в группе агенты должны соблюдать правила коммуникации. Это позволяет строить протоколы коммуникации. В протоколе коммуникации должны содержаться: тип коммуникативного акта, имена агентов отправителя и получателя сообщений, содержание передаваемого сообщения. Следует также отразить характер изменения мнений агентов в процессе коммуникации.

Несмотря на декларативную форму изложения, максимы Грайса не являются руководством к действию, а лишь описывают необходимые правила, соблюдение которых гарантирует взаимопонимание и отсутствие у агентов-участников скрытых или враждебных намерений. Очевидно, при построении МАС в частности, при разработке подсистемы управления отношениями между агентами (RM-системы) наличие подобных интенций привело бы к внутреннему системному противоречию.

2.2.4. Роль диалога и переговоров во взаимодействиях, реализуемых в системах управления отношениями с поставщиками и клиентами

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

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

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

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

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

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

2.3. Общая классификация формальных моделей диалога

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

Существующие формальные модели диалогового взаимодействия можно условно разделить на три группы или направления исследований (см. рис. 2.1).

Модели диалога

автоматные

игровые

логические

Речевые акты

Диалоговые сети

Диалоговые игры

Диалоговые логики

классические

многозначные

нечеткие

Рис 2.1. Классификация моделей диалога.

К первому направлению относится теория речевых актов и теория диалоговых сетей. Построенные в рамках данного направления модели взаимодействия в основном относятся к автоматным моделям и их расширениям, основанным на теории множеств. Ключевым при взаимодействии считаются ментальные состояния агентов и протоколы коммуникации.

Работы второго направления связаны в первую очередь с теорией игр и основаны на приложении её к задачам синтеза диалога. В рамках данного подхода взаимодействие между агентами принято сводить к нескольким заранее исследованным вариантам группового поведения, полагая что все реальные диалоги могут быть сведены к шести базовым типам: получению знаний (information-seeking), выявлению знаний (inquiry), убеждению (persuasion), торгам (negotiation), принятию решений (deliberation) и спору (strife-ridden). Модели взаимодействия в этом случае строятся как игра между участниками диалога, каждый возможный ход агента-участника определяется набором правил, а цели варьируются в зависимости от типа диалога.

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

Несмотря на многообразие игровых семантик, большая часть их основана на антагонизме проппонента и оппонента и базируется на классической схеме некоалиционной игры с нулевой суммой. Очевидно, что такие семантики плохо подходят для диалоговых логик, предназначенных для описания конструктивного диалога между агентами МАС. В связи с этим актуальна задача построения кооперативной игровой семантики для диалоговых логик.

2.4. Диалоговые сети и коммуникативные акты

Ранее в этой работе уже упоминалось о теории речевых актов. В соответствии с этой теорией, диалог состоит из речевых или коммуникативных актов, совершаемых его участниками, каждый такой акт имеет форму выражения (локутивный акт), цель высказывания (иллокутивный акт) и последствия (перлокутивный акт). Речевые акты подразделяются на следующие группы [172]: директивные, ассертивные, промиссивные, экспрессивные и декларативные. Директивные акты (директивы) выражают намерение одного агента поручить другому агенту какое-то дело, заставить его выполнить некоторые действия. Ассертивные акты (утверждения) позволяют информировать агента о состоянии среды (других агентов). Промиссивные акты (обещания) отражают обязательства агентов выполнить действия. Экспрессивные (выразительные) акты отражают внутреннее состояние агента. Наконец, декларативные акты характеризуют выполнение действия, связанного с самой речью (отрывком речи).

В рамках этой концепции удобно моделировать агентов-участников диалога как автоматы, с заранее определёнными ментальными состояниями, зависящими от состояния диалога. Вся совокупность этих состояний называется протоколом коммуникации (см. например [82]).

В настоящее время теория речевых актов все еще активно развивается и существует множество расширений этой теории. Например, известно, что все современные языки взаимодействия агентов (ACL, KQML) основаны на этой теории[139,140]. Рассмотрим некоторые из таких расширений.

2.4.1. Теория диалоговых сетей

Теория диалоговых сетей есть расширение теории речевых актов, которое опирается на определение протоколов коммуникации. Всякий речевой акт представляет собой цепочку фраз (высказываний), в результате которых происходят изменения ментальных состояний у собеседников.

Главные свойства коммуникативных структур типа диалогов (по Т.Винограду и Ф.Флоресу) [180] таковы:

  1.  Диалоги начинаются с исходного речевого акта (ассертивного, промиссивного, экзерситивного, декларативного или экспрессивного) и характеризуют намерения одного агента по отношению к другому.
  2.  На каждом шаге диалога существует ограниченный набор возможных действий (принять, отклонить, сделать контрпредложение и т.п.).
  3.  Существуют терминальные состояния, определяющие завершение диалога. Когда достигается одно из этих состояний, диалог считается законченным.
  4.  Речевые акты меняют не только состояние диалога, но и состояния агентов (убеждения, желания, намерения), которые всегда зависят от диалога и его результатов.

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

2.4.2. Формальная модель диалога на основе протокола коммуникации

В качестве альтернативы автоматной модели можно рассмотреть модель взаимодействия на базе протоколов коммуникации. Эта модель наиболее удобна на практике, если взаимодействие в МАС можно свести к фиксированному количеству заранее специфицированных случаев. Протокол коммуникации для взаимодействия двух агентов можно определить так:

 COM = (ST1, ST2, INIT1, INIT2, M1, M2, 1, 2, 1, 2, 1, 2),

где ST1 – множество состояния первого агента,

ST2 – множество состояний второго агента,

INIT1 – множества начальных состояний первого агента,

INIT2 – множества начальных состояний второго агента,

M1 – множество сообщений первого агента второму,

M2 – множество сообщений второго агента первому,

1 : ST1 x M2  ST1 – функция, определяющая реакцию первого агента на сообщение второго,

2 : ST2 x M1  ST2 – функция, определяющая реакцию второго агента на сообщение первого,

1 : ST1  (ST1), где (ST1) – множество всех подмножеств ST1, - функция определяющая возможное изменение состояния первого агента. При взаимодействии конкретное состояние выбирается в зависимости от различных внешних и внутренних факторов, определяющих поведение агента, то есть выбор недетерминирован.

1 : ST1  (ST1) – аналогичная функция для описания изменения состояний второго агента.

1 : ST1  M1 – определяет сообщения первого агента, отправляемые им второму при переходе в новое состояние.

2 : ST2  M2 – то же самое для второго агента.

Протоколы взаимодействия удобно графически представлять с помощью диаграммы, напоминающей диаграмму состояний UML [159]. Назовём этот тип диаграмм расширенными диаграммами состояний. Пример такой диаграммы для описания протокола последовательных монотонных уступок приведен на рис 2.2.

Протоколы взаимодействия также иногда называют сценариями взаимодействия. Но под сценарием взаимодействия будем понимать конкретную реализацию протокола, один сеанс обмена сообщений, подчиняющийся данному протоколу. Сценарий взаимодействия удобно иллюстрировать диаграммой последовательности (sequence diagram) UML. Приведём пример сценария взаимодействия двух агентов, подчиняющегося протоколу взаимных последовательных уступок.


Агент 1

Агент 2

INITDIALOG

Агент начинает диалог посылая предложение

WAIT

Состояния ожидания ответа собеседника

Accept

Counter-propose

propose

ACCEPTING

Согласие и заключение сделки

PROPOSING

Уступка и выдвижение контрпредложения

Refuse

REFUSING

Отказ от сделки

WAIT

Состояние ожидания ответа собеседника

Accept

Counter-propose

ACCEPTING

Согласие и заключение сделки

PROPOSING

Уступка и выдвижение контрпредложения

Refuse

REFUSING

Отказ от сделки

propose

ENDDIALOG

Завершение разговора

ENDDIALOG

Завершение разговора

propose

accept-proposal

reject-proposal

reject-proposal

accept-proposal

Рис. 2.2. Протокол последовательных уступок в виде расширенной диаграммы состояний.

Рис. 2.3. Один из возможных сценариев взаимодействия агентов в протоколе минимальных последовательных уступок в виде диаграммы последовательности.

Рассмотрим в качестве иллюстрации взаимодействие агентов в контрактной сети (рис 2.4). В примере участвуют следующие агенты: агент-заказчик (inviter), агент-посредник (mediator) и агенты-исполнители (bidders). Агент-заказчик инициирует взаимодействие, отправляя сообщение агенту-посреднику. Агент-посредник отсылает запросы агентам-исполнителям, получает их предложения, выбирает наиболее перспективное, входит в состояние переговоров с этим агентом, договаривается о цене и возвращается обратно, затем сообщает результат агенту-заказчику.

Рис. 2.4. Протокол коммуникаций агентов для контрактной сети

Модель на основе протоколов коммуникации, на настоящий момент, чаще всего используется на практике при построении МАС. Однако, эта модель, не может описать нетиповые ситуации взаимодействия, спрогнозировать развитие диалога. На основе этой модели нельзя сделать никаких выводов о целесообразности, эффективности, желательности, необходимости диалога. Для агента протокол коммуникации – лишь механизм, предписание, выполняя которое он может взаимодействовать с другими агентами.

2.4.3. Формальная автоматная модель диалога 

Построим автоматную модель диалога между агентами. Как известно, конечный автомат может быть задан с помощью пяти параметров M = (Q, Σ, δ, q0, F), где:

Q — конечное множество состояний автомата;

q0 — начальное состояние автомата, q0  Q;

F — множество заключительных (или допускающих) состояний, таких что F  Q. При достижении одного из этих состояний работа автомата прекращается;

Σ — допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;

δ — заданное отображение множества Σ x Q во множество состояний Q, δ: Σ x Q  Q (функция переходов).

Рассмотрим совокупность агентов, образующих мультиагентную систему (МАС). МАС, можно определить следующим образом [97]:

MAS = (A, E, R, ORG),

где А — множество агентов;

Е = {еi} — среда, в которой находится данная система;

R — множество взаимодействий между агентами;

ORG — множество базовых организационных структур, соответствующих конкретным функциям (ролям) агентов и установившимся отношениям между ними.

Каждый агент a  A представим в следующем виде:

a = ( S, s0, F, I, O, Σ, δ ),

где S – множество состояний агента;

 s0 – начальное состояние;

 F – множество конечных состояний;

 I – множество принимаемых сообщений;

 O – множество посылаемых сообщений;

 Σ – входной алфавит агента, последовательность сообщений, подающихся на вход агента, зависит от среды;

– пустое сообщение (сообщение не отправляется);

 δ: (I  Σ) x S  S x (O  {}) – функция переходов.

Множества I и O индивидуальны для каждого агента, на всём множестве агентов МАС можно построить функции I(a) и O(a), определяющие соответственно множество принимаемых и получаемых агентом а сообщений. Потребуем выполнения следующих условий:

(a1  A) (i  I(a1)) ! (a2  A) ! (o  O(a2)) : i ≡ o (2.1)

(a1  A) (o  O(a1)) ! (a2  A) ! (i  I(a2)) : io (2.2)

Здесь ! – квантор существования единственного элемента, т.е. !а  a(ba). Назовем совокупность (2.1) и (2.2) условием согласования входа и выхода или условием замкнутости системы.

Лемма 2.1. В случае выполнения условия замкнутости МАС, для всех агентов системы существует такое множество взаимодействий R, что любое x  (I  O) можно представить в виде кортежа (представление M.I):

x = < a1, a2, t >, где

 a1  A – агент-отправитель сообщения;

 а2  A – агент-получатель сообщения;

 t  R - тип сообщения (взаимодействия).

Доказательство довольно очевидно. Выберем произвольного агента а1 Рассмотрим x  I(a1). Согласно (2.1) существует только один агент а2, и единственное сообщение o  O(a2) такое что xo. Выберем в качестве первого элемента кортежа a1, в качестве второго – а2, а в качестве третьего положим некоторый тип взаимодействия tx. Если такого типа нет во множестве R, то пополним его образовав R = R  { tx } Аналогично, для случая x  O(a2) согласно (2.2) существует сообщение i  O(i2) такое что xo. Точно также формируем результирующий кортеж и пополняем множество R.

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

Назовем минимальным такое множество взаимодействий R, у которого не существует подмножества, удовлетворяющего представлению M.I. Очевидно, если МАС можно описать в виде M.I, то существует минимальное множество взаимодействий Rmin, удовлетворяющее этому представлению.

Автоматная модель диалога удобна для описания МАС, состоящих из рефлексивных агентов, но она также может рассматривать и более сложные системы, если сделать функцию переходов недетерминированной (δ: (I  Σ) x S  P(S x (O  )), где P(X) – множество всех подмножеств Х).

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

2.5. Теоретико-игровые модели диалога

2.5.1 Подход Хинтикки

Я.Хинтикка [153],[154] рассматривает процесс познания как математическую игру (в смысле теории игр). Основные черты предлагаемого теоретико-игрового определения истины (ТИОИ) таковы:

  1.  В нём используется понятие выигрышной стратегии (а не победы в игре) — правила, определяющего, какой ход должен сделать игрок в каждой возможной игровой ситуации для того, чтобы достичь победы вне зависимости от того, какую стратегию изберет соперник.
  2.  Оно не сводится к формальным (но интерпретированным) первопорядковым языкам. Хотя в естественных языках кванторы ведут себя иначе, чем в них, ТИОИ может быть распространено на них, как и на другие логические языки.
  3.  Теоретико-игровая интерпретация кванторов используется во всех случаях, когда неприменимо тарскианское определение истины.
  4.  ТИОИ дает условия истинности первопорядковых предложений, формулируя их в терминах игровых стратегий, которые сами приводимы к логическому анализу и формулировке в логических терминах (функции Сколема).
  5.  Собственно понятие истины является при теоретико-игровом подходе вспомогательным, поскольку при нем определяется значение квантифицированных предложений путем определения их условий истинности. Следует различать игры на поиск истины (truth - seeking games ) (т.е. эпистемические игры) и игры на установление (или верификацию) истины ( truth - establishing games ) (т.е. семантические игры), где условия истинности в определенном смысле даны заранее.

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

2.5.2. Оперативная семантика П.Лоренцена

Лоренцен [157] рассматривает процесс установления истинности предложения как некоторую игру между пропонентом и оппонентам. Технически оперативная семантика подобна семантическим таблицам Бета, но идейно учитывается диалогический характер игры и социальный характер познания.

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

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

Диалогически-определенные предложения противопоставляются в определённом смысле истинностно-определенным и доказуемостно-определённым. Под первыми понимаются предложения, которым произвольно приписывается одно из истинностных значений – «истинно» или «ложно» (в двузначной логике): предложения (атомарные) являются истинными или ложными «сами по себе». Однако не все предложения таковы: имеются и такие, которые невозможно определить с точки зрения истинности. В этом случае можно попытаться (как, скажем, в арифметике) доказать это предложение при наличии метода, позволяющего относительно каждой попытки доказательства сказать, является оно доказательством или нет. Это и характеризуется с помощью понятия доказуемостно-определимого предложения.

Диалоговый подход Лоренцена ориентирован на семантический анализ истинности в аспекте диспута. Это затрудняет его применения в случае рассмотрения диалога не как спора, но как процесса переговоров. Иными словами, аргументационные семантики не годятся для описания процессов согласования и кооперации.

2.6. Диалоговые игры

Диалоговая игра – это взаимодействие между двумя и более игроками, в которой каждый игрок «ходит», совершая высказывания, в согласии с заранее определённым набором правил.

В настоящее время диалоговые игры применяются для изучения недедуктивных форм вывода и для определения теоретико-игровой семантики различных типов классических и неклассических логик. Основное применение диалоговых игр в ИИ состоит в разработке протоколов коммуникации между программными агентами [162].

В основе теоретико-игровой семантики лежат, с одной стороны, математическая теория игр, а с другой—теоретико-модельная семантика. Как и эту последнюю, теоретико-игровую семантику интересует отношение M |= tS. Однако, в отличие от теоретико-модельной семантики M |= tS анализируется в терминах игры, которая, говоря неформально, интерпретирует предложение S посредством процесса вычисления истинностного значения, направленного от предложения как целого к его частям. Эта игра, представляющая, таким образом, нашу основную интерпретационную (семантическую) единицу, вводит в рассмотрение параметры нового вида (такие, как "память" и "информационное множество"), которые исследователь затем стремится использовать в семантическом анализе. Всё это приводит к тому, что семантика становится более процессуально-ориентированной. И неудивительно, что при таком подходе поддаются трактовке анафорические явления, дискурсивные феномены и вообще проблемы, входящие в компетенцию семантики текста. Совершенно ясно, что такие характеристики и инструменты анализа отсутствуют в теоретико-модельной семантике, где любые феномены процессуального характера не могут не оставаться исключением.

Новизна теоретико-игровой семантики — если сравнивать ее с теоретико-модельной — носит относительный характер. С одной стороны, представляется, что многие интерпретационные правила теоретико-игровой семантики нетрудно перефразировать в терминах рекурсивных определений истинности. Однако в некоторых случаях теоретико-игровой аппарат приводит, по-видимому, к более естественной терминологии анализа семантических феноменов, чем аппарат теоретико-модельной семантики, основным инструментом которой является рекурсивное определение истинности.

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

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

Диалоговые игры это в первую очередь, логические модели с игровыми семантиками [161]. Поэтому в следующем разделе проводится анализ возможных семантик для диалоговых логик.

2.7. Семантики диалоговых логик

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

В иных логиках, например, релевантных, может учитываться и смысловое содержание понятий (такие логики называются интенсиональными). Так в интенсиональных логиках необязательно, чтобы все истинные высказывания были эквивалентными.

Семантика уделяет главное внимание описанию и определению таких понятий, как «истина», «ложь», «неопределённость», «противоречивость».

Современная логическая семантика включает два основных направления: теория истины и теория значения. Среди различных подходов в русле первого направления можно отметить: теоретико-модельные семантики, которые, по сути, представляют собой архетип семантической теории истины А.Тарского [102,103]; семантики истинностных значений, развитые Дж.Данном [131] и Н.Белнапом [122]; здесь значения истинности формул задаются только в виде валентностей без какого-либо обращения к предметной области; игровые семантики, в частности, оперативная семантика П.Лоренцена [157], который рассматривает процесс установления истинности предложения как игру между пропонентом и оппонентом, диалоговые семантики на основе формализма бирешёток.

Развитие нетрадиционных логических семантик в середине XX-го века началось с критики двух главных принципов классической логической семантики – принципа бивалентости T(p)  F(p) и принципа однозначности T={T}, F={F}, где p – предложение, которое характеризуется двумя истинностными значениями: T – истина или F – ложь, причем эти значения суть одноточечные множества.

Поскольку в классической логике понятия ложности и отрицания являются взаимозаменяемыми ( p означает F(p)), легко заметить, что в ней также справедлив принцип дополнительности T(p) + F(p) = 1.

В общем случае, будем представлять истинностное суждение в виде пары: p, v(p), где pP, P – множество предложений, а v:PV, V – множество значений истинности.

Примерами нетрадиционных семантик, пригодными для представления процессов диалога, являются семантики Данна-Белнапа, аргументационные семантики, многомерные (векторные) семантики, теоретико-игровые семантики

2.7.1. Семантики Данна-Белнапа

Основная идея семантики Дж. Данна [132],[133] заключается в отказе от принципа однозначности с допущением истиннозначных провалов I = {} = «ни истина, ни ложь» и пресыщенных оценок истинности B = {T, F} = «и истина, и ложь». В первом случае оценки истинности и ложности понимают

как частичные, а во втором – как составные, амбивалентные.

В целом, речь идет о переходе от обычного множества значений истинности V (например, V2 = 2 = {T, F}) к множеству всех подмножеств 2V, задающему мультиоценку истинности (например, 2V2 = 4 = {T, B, I, F}).

Аналогично примерами естественных расширений принципа бивалентности служат: принцип тривалентности T(p)  F(p)  I(p) в трёхзначных семантиках (например, в семантике Клини), принцип тетравалентности T(p)F(p)B(p)I(p) в четырёхзначной семантике Данна-Белнапа и пр.

Дальнейшее обобщение подхода Данна-Белнапа заключается в переходе к множеству нечётких подмножеств значений истинности [0,1]V, множеству L-нечётких подмножеств (в смысле Дж.Гогена) значений истинности LV и т.д.

2.7.2. Многомерность истинности в диалоге: векторные семантики

Дж. Данн [131] предложил понимать истинность как отношение, которое не обязательно является функциональным. При этом в общем случае F(p)  1– T(p), т.е. понятие «ложь» больше не является дополнением «истины», а выступает в качестве самостоятельного понятия; таким образом, условия ложности предложения должны определяться параллельно с условиями их истинности. Возникает двухмерная (векторная) семантика, исходящая из независимости истинности и ложности. Подобная двухосновная семантика может быть получена путём прямого произведения элементарных семантик.

Родоначальником многомерных логик является русский логик Н.А.Васильев [21], который почти сто лет назад ввел понятие «воображаемой логики» трёх измерений. В основе этой логики лежат три типа атомарных предложений: позитивные, негативные и индифферентные (акцидентальные).

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

Пусть V=[0,1], т.е. T, F [0,1]. Тогда в двухмерных логических семантиках валентность v любого предложения p задаётся парой не зависимых друг от друга величин v(p) = (T(p), F(p)), т.е. определяется в единичном квадрате v: P[0,1]2, а в трёхмерных семантиках – тройкой vB(p) = (T(p), F(p), B(p)) (паранепротиворечивые семантики) или тройкой vI(p) = (T(p), F(p), I(p)) (параполные семантики). Как частные случаи, получаем тавтологическую семантику vT(p) = (1, 0, 0), парадоксальные семантики vP(p) = (1, 1, B(p)), псевдопарадоксальные семантики vPP(p) = (1, F(p), B(p)), чисто фаллибилистические семантики vf(p) = (0, 0, I(p)) и т.п.

Модализация истинностных значений (в стиле Н. Решера [167]) на основе мер возможности Заде П и необходимости Дюбуа-Прада N, приводящая к нарушению принципа дополнительности, связана с формированием возможностных 2T(p) + F(p) 1 и необходимостных T(p) + F(p) 1 семантик.

Построение многомерных логик может опираться на нестандартные нечёткие множества с интервальнозначными или векторными функциями принадлежности. Показательными примерами последних служат интуиционистские нечёткие логики и нейтрософские логики.

В середине 80-х годов К. Атанасов ввел понятие интуиционистского нечёткого множества, описываемого парой функций принадлежности  и непринадлежности  соответственно: А = {(x А(x), А(x))} или : X  [0,1], : X  [0,1], (x)+(x)  1. Соответственно, здесь интуиционистская семантика опирается на пару v(p) = (T(p), F(p)) и условие T(p) + F(p) 1. Непосредственными обобщениями являются интервальнозначная интуиционистская семантика, когда T, F  [0,1] и нечёткая интуиционистская семантика T, F[0,1][0,1].

В свою очередь, стандартная нейтрософская cемантика (по Ф.Смарандаче) задается в виде vI: P [0,1]3, vI(p) = (T(p), F(p), I(p)), где T(p) – степень истинности высказывания p, F(p) – степень его ложности, а I(p) – степень его неопределённости, T, F, I – числа или подинтервалы интервала [0,1].

2.7.3. Распределённость истинности: диалоговые (теоретико-игровые) семантики

В диалоговых семантиках валентность любой формулы p их множества Р определяется двумя агентами: пропонентом a1 и оппонентом a2. Пропонент a1, выдвигающий некоторый тезис (формулу) p, стремится доказать его истинность, а оппонент a2, напротив, хочет опровергнуть его. Пространство значений истинности имеет вид VD = V1  V2, так что оценка истинности формулы p в переговорах двух агентов является двухосновной, vD: P V1V2. Сам их диалог может быть представлен в виде четвёрки D = А, P, v1, v2, где А ={a1, a2}, , v1: Р V1, v2: РV2. Построим бирешётку оценок истинности BLV ={(v1, v2) v1L1, v2L2}, где L1 и L2 – две различные решётки, например, L1 = [0, +1] и L2 = [1, 0]. Тогда базовая семантика переговоров может быть представлена парами значений истинности: (+1, 0) = (T1, F2), (0, 1) = (F1, T2), (0, 0) = (F1, F2), (+1,1) = (T1, T2).

2.8. Формальное описание диалога с помощью системы правил

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

Рассмотрим формальное описание диалога с помощью системы правил [162]. Предположим, что предмет диалога между агентами может быть представлен на некотором логическом языке, чьи ППФ могут быть обозначены строчными латинскими буквами p, q, r и т.д. Тогда формализация диалоговой игры состоит из следующих элементов.

Стартовые правила (commencement rules): Правила, описывающие обстоятельства, при которых начинается диалог.

Правила построения (locutions): Правила, определяющие, какие диалоговые действия разрешены. Обычно, правила построения позволяют участникам добавлять выражения, подвергать сомнению или подтверждать добавленные ранее. Подтверждение выражения означает его доказательство или предоставление аргументов в его пользу. Правила диалоговой игры также могут позволять участникам добавлять выражения, которые имеют разную степень убедительности для них самих. Например, можно только предложить выражение в качестве возможного варианта или декларировать и отстаивать его истинность.

Правила комбинации (combination rules): Правила, определяющие контекст диалога при котором то или иное диалоговое действие разрешено, обязательно или запрещено. Например, может быть запрещено в процессе одного и того же диалога добавлять выражение p, а затем ¬p, предварительно не отменив предыдущего выражения.

Правила соглашения (commitments): Правила, определяющие обстоятельства, при которых участники диалога могут выражать своё отношение к добавленным выражениям. Обычно, добавление выражения в процессе диалога означает демонстрацию другим участникам диалога определённого уровня (не)одобрения, согласия, требования. Например, в диалоге торгов добавление предложения обычно выражает желание осуществить транзакцию на условиях, описанных в предложении. По Гамблину [148] формальная диалоговая система должна содержать и поддерживать набор соглашений каждого участника, называемый хранилищем соглашений. Эти хранилища обычно являются немонотонными в том смысле, что участники могут при определенных обстоятельствах отменять свои соглашения.

Правила завершения (termination rules): Правила, определяющие обстоятельства завершения диалога. Эти правила также могут определять исход диалога, т.е., например, указывать, смог ли проппонент защитить изначальный тезис.

На основании такой системы правил возможно построение динамической модели автоматизированного диалога. Однако совокупность перечисленных правил задает лишь фреймворк взаимодействия, позволяя строить диалоги различной сложности. Фактически, такая модель это усовершенствованный механизм построения сценариев взаимодействия, он не пригоден для определения семантики переговоров и установления соглашений.

Для развития формальной теории диалогов между агентами в МАС нужны варианты интеграции теоретико-игровых и логических моделей с использованием аппарата многозначных и нечётких логик.

Выводы по второй главе.

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

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

В рамках существующей парадигмы были построены модели взаимодействия агентов на основе протоколов коммуникации. Данная модель позволяет строить диалог и переговоры агентов в заранее определенных ситуациях взаимодействия. Их применение позволяет реализовывать не только базовую функциональность, но и закладывает основу для реализации механизмов более высокого уровня.

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

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


Глава 3. Многозначные и нечёткие логики в диалоговых задачах ИИ

3.1. Многозначные логики в описании диалогов

Для решения проблемы установления истинности при ведении переговоров, а также для построения адекватного механизма разрешения конфликтов и достижения соглашений предложим подход, основанный на использовании многозначных логик [6,7], как основы диалогового процесса.

Сформулируем основные отличительные черты диалоговых логик, которые являются структурно и функционально определяющими.

Многомерность семантики. Вследствие наличия различных ролей в процессе диалога, семантика диалоговой логики не может быть одномерной, и должна предлагать как минимум два измерения. Например, в диалоге клиента и продавца предикат P(X,C) = «продажа товара Х по цене C», означает с точки зрения продавца передачу предмета X в обмен на вознаграждение С, а с точки зрения клиента прямо противоположный процесс. Соответственно, истинность предиката P(X,C) для продавца означает возможность осуществить продажу, а для покупателя – желание совершить покупку.

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

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

Начнём с лингвистического анализа диалогов, происходящих в RM-системе.

3.2. Модели диалога на основе произведений логик

3.2.1. Подход от лингвистики к логике

Рассмотрим диалог, происходящий между поставщиком и заказчиком при заказе на поставку товара. Пусть имеется набор товаров G: {G1,G2,…,Gn}, каждый товар описывается набором параметров P(Gi)=<p1,p2,…,pm> (базовая стоимость, модель, размер, вид, цвет и т.п.). Условия поставки товара также описываются другим набором параметров S(Gi)=<s1,s2,…,sk> (стоимость партии, ее размер, сроки поставки). В процессе диалога стороны должны прийти к соглашению, относительно параметров доставки и заключить контракт. Согласно классическому протоколу ведения переговоров, заказчик должен сначала сформулировать свои требования и отправить их поставщику, который, в свою очередь, должен выдвинуть предложения, относительно предполагаемой поставки и ее условий, заказчик может согласиться, отказаться или потребовать пересмотра требований и выдвинуть контрпредложение, которое в свою очередь может быть принято, отклонено и/или модифицировано поставщиком. Переговоры завершаются либо после заключения контракта, либо если стороны приходят к соглашению о невозможности взаимовыгодной сделки.

Протокол взаимодействия, подходящий для подобного случая диалога был приведён в главе 2. Это протокол последовательных монотонных уступок. Использование протокола взаимодействия позволяет автоматизировать и упростить ведение переговоров, однако каждый раз для достижения цели придется проходить полный цикл переговоров.

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

Переменными среды в данном случае будут товары и условия их поставки. Реакцией собеседников на конкретное предложение о поставке может быть либо согласие - T, либо отвержение - F, либо частичное согласие (выдвижение контрпредложения) - I. Получаем девятизначную логику {<T,T>,<T,I>,<T,F>,<I,T>,<I,I>,<I,F>,<F,T>,<F,I>,<F,F>} с выделенным значением <T,T>. На основании знаний, полученных собеседниками из истории взаимодействия или иных источников, можно делать априорные выводы о результате переговоров.

3.2.2. Произведения решёток и логик, бирешётки

При использовании многозначных логик с размерностью более 3 элементов [17,18], а именно такие логики наиболее удобны для описания ситуаций диалога, важную роль играет теория бирешёток, основанная на теории решёток [12,34], впервые предложенная Гинсбергом [144], развитая в работах Фиттинга [141,142,143] и Аврона [129]. Дадим некоторые определения.

Определение 3.1. Предбирешёткой называется структура (B, t, k), где t и k – частичные порядки на B, каждый из которых образует структуру алгебраической решетки (с точной верхней и нижней гранями).

Если (B, t, k) предбирешётка, то на ней можно определить операции  и  как взятие точной верхней и точной нижней граней на решетке (B, t), и ,  как взятие точной верхней и нижней граней на решётке (B, k). Также обозначим как t и f наибольший и наименьший элементы решётки (B, t), а T и  наибольший и наименьший элементы решётки (B, k).

Определение 3.2. Пусть (B, t, k) предбирешётка. На ней определена операция отрицания, если существует отображение  : B  B, такое что:

x t y  y t x,

x k y  x k y,

x = x.

Определение 3.3. Пусть (B, t, k) предбирешётка. На ней определена операция слияния, если существует отображение  : B  B, такое что:

x t y  x t y,

x k y  y k x,

 x = x.

Определение 3.4. Предбирёшетка с отрицанием (B, t, k, ) называется бирешёткой.

Определение 3.5. Бирешётка (B, t, k) является дистрибутивной, если все операции , ,  и  дистрибутивны друг относительно друга.

Определение 3.6. Бирешётка (B, t, k) является сплетенной бирешёткой, если все операции , ,  и  монотонны относительно порядков t, k 

Каждая дистрибутивная бирешётка является сплетённой [174].

Определение 3.7. Пусть (L1, 1) и (L2, 2) – решетки. Тогда L1L2 есть бирешётка вида (L1 x L2, t, k), где:

<x1,x2> t <y1,y2>  x1 1 y1 и y2 2 x2,

<x1,x2> k <y1,y2>  x1 1 y1 и x2 2 y2,

Очевидно, бирешётка L1L2 всегда является сплетённой, а если L1 и L2 дистрибутивны, то и L1L2 также дистрибутивна. Операции , , ,  на L1L2 определяются следующим образом:

<x1,x2><y1,y2> = < x1y1, x2y2>

<x1,x2><y1,y2> = < x1y1, x2y2>

<x1,x2><y1,y2> = < x1y1, x2y2>

<x1,x2><y1,y2> = < x1y1, x2y2>

Определение 3.8. Бирешётка является билинейной, если любые ее два элемента сравнимы по крайней мере по одному из ее порядков.

Для класса билинейных бирешёток в [120] доказано, что любая эквивалентность формул имеет место также и в четырёхзначной решётке Белнапа, т.е. любая логика операций , , , ,  на такой бирешётке сводима к логике Белнапа.

Определение 3.9. Бифильтром бирешётки B является непустое множество F  B, такое что:

a  b  F если a  F и b  F

a  b  F если a  F и b  F

Определение 3.10. Бифильтр называется первичным, если также удовлетворяются следующие условия:

a  b  F если a  F и b  F

a  b  F если a  F и b  F

Определение 3.11. Логической бирешёткой называется пара (B, F), где B – бирешётка, а F – первичный бифильтр.

Наименьшей логической бирешёткой является логика Белнапа (FOUR, {t,T}), кроме того, согласно [120] каждая дистрибутивная бирешётка может быть превращена в логическую бирешётку.

В логической бирешётке (B, F) означивание v на B, есть функция, задающая истинностное значение каждой атомарной формуле, означивание не атомарных формул происходит стандартным образом, вычислением значения. Означивание v выполняет формулу  (v |= ), если v()  F. Означивание, выполняющее каждую формулу в заданном наборе формул , называется моделью , набор всех моделей  обозначается mod().

Операция материальной импликации p|q, определённая как pq, не является удобной для описания вывода, в [120] вводится следующая операция импликации:

Определение 3.12. Пусть (B, F) – логическая бирешётка. Определим:

a  b = b, если a  F,

 t, в противном случае.

Определение 3.13. Сильная импликация и эквиваленция определяются следующим образом:

  = (  )  (  )

  = (  )  (  )

Для бирешёток получено множество интересных результатов, в частности в [122] доказано, что вывод в любых логических бирешётках с операциями {, , , ,  } сводим к выводу на четырёхзначной бирешётке. Мы будем пользоваться в дальнейшем отдельными определениями и результатами, полученными в теории бирешёток, однако бирешётки не полностью отвечаю требованиям, налагаемым на диалоговые решётки, в частности, требованию кооперативности.

3.3. Базовые логики для описания диалогов между агентами

3.3.1. Минимальнозначная логика диалога

Как известно, семантика логики вопросов и ответов Белнапа иллюстрируется с помощью логической решетки L4, задающей порядок истинности V, а семантика логики Фитинга – с помощью аппроксимационной решетки Скотта A4, порядок которой отождествляется с порядком знаний К. В [100] были введены модальные решетки M4 и М4, опирающиеся на порядок уверенности (необходимости) и порядок предположения (возможности). Ниже по аналогии введем понятия диалоговой решетки и двойственной ей решетки диспута (или конкурентной решетки).

Вначале построим минимальнозначную диалоговую логику Ldmin на основе произведений двузначных логик двух агентов 1 и 2 – участников диалога. Множество логических значений можно представить графически в виде диалоговой решетки D4, представленной следующей диаграммой Хассе (рис 3.1).

<F1,T2>

<T1,F2>

<T1,T2>

T1

F1

T2

F2

=

D4

<F1,F2>

Рис. 3.1. Диаграмма Хассе для диалоговой решётки D4.

Четырёхзначная семантика диалога Ldmin строится как произведение семантик агентов – участников диалога. Интерпретация полученных истинностных значений интуитивно вполне понятна: <F1,F2> – «ложь для обоих агентов», <T1,F2> – «истина для первого агента, ложь для второго», <F1,T2> – «ложь для первого агента, истина для второго», <Т1,T2> – «истина для обоих агентов». Здесь пары <F1,F2>, <T1,T2> можно понимать как точки согласия, а пары <T1,F2>, <F1,T2> как точки противоречия.

Если цель диалога формулируется как достижение соглашения, то соответствующее отношение порядка можно понимать как порядок cоглашения С. Например, <F1,F2> С <T1,F2> С <Т1,T2> означает, что ситуация «истина для обоих агентов», равнозначная наличию соглашения между ними, будет предпочтительнее ситуации «истина одного агента – ложь другого», когда соглашения между агентами нет, но оно считается возможным. Последняя ситуация предпочтительнее, чем «ложь для обоих агентов», которая здесь отождествляется с невозможностью заключения соглашения (или отказом от него). Итак, в логике соглашения выделенным значением является <Т1,T2> = T (cм. таблицу 3.1).

Таблица 3.1. Истинностные значения четырёхзначной диалоговой логики

Значение в бирешетке D4

Обозначение

Интерпретация

<T1,T2>

T

Подтвержденная (согласованная) истина

<T1,F2>

I

Внутренняя истина (истина для первого агента)

<F1,T2>

E

Внешняя истина (истина для второго агента)

<F1,F2>

F

Подтвержденная ложь

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

В свою очередь, повернув диалоговую решётку D4 по часовой стрелке на 90 градусов, получаем решётку диспута (спора) K4 с отношением порядка G (порядок выигрыша). Здесь можно использовать аргументационную семантику, например, T – «аргумент найден», а F – «возражение не найдено». При этом <T1,F2> интерпретируется как победа в споре первого агента и поражение второго, поскольку первый агент нашел неопровержимый аргумент, <F1,T2> – как обратная ситуация, <Т1,T2> – как ничья (аргументы обоих агентов взаимно опровергаемы), а <F1,F2> – как отказ от спора. Тогда, например, имеем <F1,T2> G <F1,F2> G ,<T1,F2>, т.е. в логике диспута K4 значение <T1,F2> следует брать в качестве выделенного значения.

<T1,T2>

 <F1,F2>

<T1,F2>

<F1,T2>

 <F1,T2>

<T1,F2>

<T1,T2>

<F1,F2>

D4

K4

Рис. 3.2. Переход от диалоговой решётки D4 к решётке диспута K4

На основе решёток D4 и K4 легко построить диалоговую бирешётку. Пусть V, С,G  – биупорядоченное множество. В случае, когда его компоненты V, С и V,G  образуют полные решетки, биупорядоченное множество превращается в предбирешётку. Наконец, получаем диалоговую бирешётку, когда два различных отношения порядка связаны между собой с помощью специальной операции операции отрицания ¬2, удовлетворяющей условиям:

v1,v2V, v1Сv2  ¬2v2С¬2v1; (3.1)

v1,v2V, v1Gv2  ¬2v1G¬2v2; (3.2)

 vV, ¬2¬2v=v. (3.3)

Рассмотрим операции логики Ldmin. Общее количество возможных унарных операций в логике Ldmin равно 44=256, бинарных (44)2=65536. Если предположить, что T соответствует бинарной истине, а F - бинарной лжи, то можно определить консервативное отрицание. Унарная операция n является операцией консервативного отрицания в том случае, если n(T)=F, а n(F) = (T). Таких операций 16. Инверсивным отрицанием назовем такую унарную операцию n, которая меняет порядок истинности: x≥1y  n(y)≥1n(x), таких отрицаний насчитывается 36, из них 32 консервативных. Если же требовать x>1y  n(y)>1n(x), то есть строгой инверсивности, то таких отрицаний будет всего 12 (из них все консервативные). Отрицание n является биективным, если существует обратная операция n-1, такая что n(n-1(x))=n-1(n(x))=x. Если n-1=n, то такое отрицание назовем классическим (выполняется закон снятия двойного отрицания).

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

Таблица 3.2. Отрицания в логике Ldmin

x 

1x 

2 x 

3 x 

4 x 

5 x 

T 

F 

T 

F 

E 

I 

I 

E 

E 

I 

F 

T 

E 

I 

I 

E 

T 

F 

F 

T 

F 

T 

I 

E 

Первое отрицание 1x, являющееся примером составного, однородного, консервативного отрицания, представляет собой обращение (инверсию) обоих базовых порядков С и G. Так отрицание по порядку С показывает, что противоположностью соглашения между агентами T является невозможность его заключения F, тогда как отрицание по порядку G означает конверсию – смену ролей агентов (пропонент превращается в оппонента, первоначальный победитель оказывается побежденным и т.п.).

Следующие два отрицания являются примерами составных неоднородных отрицаний. Так второе отрицание ¬2, совпадающее по форме с отрицанием Фиттинга, сохраняет порядок соглашения С, но инвертирует порядок диспута G (показывая, например, смену ролей агентов). Подобная конверсия может применяться при рефлексивных рассуждениях.

В свою очередь, третье отрицание ¬3, которое инвертирует порядок соглашения С, но сохраняет порядок диспута G, аналогично отрицанию Белнапа: противоположностью соглашения оказывается отказ от него (свойство консервативности), в то время как порядок диспута не меняется. По сути, в данном случае диалог агентов «заходит в тупик».

Операции отрицания позволяют естествнным образом представить возражения агентов друг другу. Так четвёртое отрицание 4 семантически соответствует возражению оппонента пропоненту (внутреннее возражение в случае рефлексивных рассуждений), а пятое отрицание 5. – возражению пропонента оппоненту. В совокупности отрицания 4 и 5 формируют операцию циклического отрицания.

Рассмотрим свойства введённых операций:

11х = ¬2¬2х = ¬3¬3х = 4 4 х = 5 5 х = х (3.4)

1х = 4 5 х (3.5)

4 х = ¬2 5 ¬2х , 5 х = ¬2 4 ¬2х (3.6)

1¬2х = ¬21х, 14х = 41х, 15х = 51х, 45х = 54х, (3.7)

Обратим внимание на то, что отрицания ¬2 и 4, ¬2 и 5, ¬3 и 4, а также ¬3 и 5 не перестановочны, т.е.

¬24х  4¬2х, ¬25х  5¬2х, ¬34х  4¬3х, ¬35х  5¬3х, (3.8)

Лемма 3.1 Композиция унарных операций отрицания {4,5} и любой нульарной (константной) операции {F,E,I,T} позволяют построить любую нульарную функцию над Ldmin.

Доказательство. Рассмотрим два произвольных значения x, y  Ldmin.

Пусть x = (x1,x2), y = (y1,y2). Требуется доказать, что существует последовательность i1 i2… iN , такая что i1 i2… iNx = y. Рассмотрим 4 случая:

x1 = y1 и x2 = y2, тогда x = y

x1  y1 и x2 = y2, тогда 4x = y

x1  y1 и x2  y2, тогда 45x = y

x1 = y1 и x2  y2, тогда 5x = y.

Если при произвольном =x мы получаем любой требуемый нам у, т.е. произвольную нульарную функцию. Лемма доказана.

Другие подобные системы операций вытекают из соотношений (3.5), (3.6). Этими системами отрицаний являются: {,¬2,4}, {,¬2,5}, {,¬3,4}, {,¬3,5}, {,¬1, 4}, {,¬1, 5}. Системы {,1,¬2}, {,1,¬3} и {,¬2,¬3} не являются полными, так как в силу своей рефлексивной симметричности, операции 1, ¬2 и ¬3 не могут превратить точку согласия в точку противоречия и наоборот. Очевидно, что ни одна из операций 3 4 также не может являться достаточной, поэтому {4,5}, {¬2,4}, {¬2,5}, {¬3,4}, {¬3,5}, {1,4}, {1,5} минимальные системы отрицаний.

Рассмотрим теперь правила композиции. Логические операции «или» и «и» определим, как взятие наименьшей верхней и наибольшей нижней грани частичных порядков С и G.

Таблица 3.3. Истинностная конъюнкция в логике Ldmin


x1y

T

I

E

F

T

T

I

E

F

I

I

I

F

F

E

E

F

E

F

F

F

F

F

F

Таблица 3.4. Истинностная дизъюнкция в логике Ldmin

x1y

T

I

E

F

T

T

T

T

T

I

T

I

T

I

E

T

T

E

E

F

T

I

E

F

Таблица 3.5. Спорная конъюнкция в логике Ldmin

x2y

T

I

E

F

T

T

T

E

E

I

T

I

E

F

E

E

E

E

E

F

E

F

E

F

Таблица 3.6. Спорная дизъюнкция в логике Ldmin

x2y

T

I

E

F

T

T

I

T

I

I

I

I

I

I

E

T

I

E

F

F

I

I

F

F

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

x1y = y1x, x2y = y2x, x1y = y1x, x2y = y2x, (3.9)

x1x = x, x2x= x, x1x = x, x2x = x, (3.10)

(x1y)1z = x1(y1z), (x2y)2z = x2(y2z),

(x1y)1z = x1(y1z), (x2y)2z = x2(y2z), (3.11)

(x1y)1z = (x1z) 1 (y1z), (x1y)1z = (x1z)1(y1z),

(x2y)2z = (x2z) 2 (y2z), (x2y)2z = (x2z)2(y2z), (3.12)

Проверим законы Де Моргана для различных наборов логических связок. Для истинностного отрицания 1 правила Де Моргана срабатывают всегда, для рефлексивного отрицания ¬2 эти законы работают только для спорных связок (2 и 2), иными словами выполняются следующие соотношения:

1(x1y) = 1y11x, 1(x1y) = 1y11x

1(x2y) = 1y21x, 1(x2y) = 1y21x

¬2(x2y) = ¬2y2¬2x, ¬2(x2y) = ¬2y2¬2x (3.13) Прочие комбинации логических связок не подчиняются законам Де Моргана, однако после выбора иных выделенных значений логики, это может поменяться. Приведём эти соотношения:

¬2(x1y)  ¬2y1¬2x, ¬2(x1y)  ¬2y1¬2x

5(x1y)  5y15x, 5(x1y)  5y15x

5(x2y)  5y25x, 5(x2y)  5y25x

4(x1y)  4y14x, 4(x1y)  4y14x

4(x2y)  4y24x, 4(x2y)  4y24x (3.14)

Лемма 3.2 Композиция операций из множества {¬2,4,1} позволяет построить любую нульарную функцию над Ldmin.

Доказательство.

Рассмотрим выражение

 4x1¬24¬2x (3.15)

Его значение тождественно T при любых x, поэтому, если использовать его в качестве замены константной операции, то из леммы 3.1 вытекает, что {¬2,4,1} также позволяют построить любую нульарную функцию над Lmin. Лемма доказана.

Рассмотрим функции 1(x), 2(x), 3(x) и 4(x) (см. таблицу 3.7) Назовём эти функции характеристическими функциями Ldmin.

Таблица 3.7. Характеристические функции Ldmin

x

1(x)

2(x)

3(x)

4(x)

T

T

F

F

F

I

F

T

F

F

E

F

F

T

F

F

F

F

F

T

Найдем для них представление через композицию ¬2, 4, 1:

1(Х) = 1[1x1¬21x] = 4¬24¬2[4¬24¬2x1¬24¬24¬2x]

2(Х) = 1[4x1¬24x] = 4¬24¬2[4x1¬24x]

3(Х) = 1[5x1¬25x] = 4¬24¬2[¬24¬2x14¬2x]

4(Х) = 1[x1¬2x] = 4¬24¬2 [x1¬2x] (3.16)

Операция 1(Х) имеет интересную семантику. Смысл этой операции в том, что она, фактически, переводит многозначную логику в двузначную. Можно выразить это так: «всё что не признано истиной является ложью».

Теорема 3.1. Система операций {¬2,4,1} является полной системой логических операций над Ldmin

Доказательство.

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

Пусть, теорема выполняется для n-арных операций, докажем, что она тогда выполняется для (n+1)-арных операций.

Рассмотрим произвольную функцию Ф(x1,x2,…xn,xn+1). Согласно индуктивному допущению Ф(x1,x2,…xn,T), Ф(x1,x2,…xn,I), Ф(x1,x2,…xn,E), Ф(x1,x2,…xn,F) выразимы при помощи композиции операций из {¬2,4,1}. Обозначим эти выражения Ф1, Ф2, Ф3 и Ф4 соответственно.

Сконструируем

Фnew = [Ф111(хn+1)]1[Ф212(хn+1)]1[Ф313(хn+1)]1[Ф414(хn+1)]

Воспользовавшись соотношениями (3.4), (3.5), (3.6) и (3.13) получим:

Фnew =4¬24¬2 [4¬24¬2Ф11 4¬24¬21(хn+1) ] 1

4¬24¬2 [4¬24¬2Ф2 1 4¬24¬22(хn+1) ] 1

4¬24¬2 [4¬24¬2Ф3 1 4¬24¬23(хn+1) ] 1

4¬24¬2 [4¬24¬2Ф4 1 4¬24¬24(хn+1) ] (3.17)

Выражение Фnew принимает значение Ф1, если хn+1 = T, F2, если хn+1 = I, Ф3, если хn+1 = E и Ф4, если хn+1 = F, иными словами Ф(x1,x2,…xn,xn+1) = Фnew. При любых значениях хn+1. Теорема доказана.

Лемма 3.3 Все операции системы {¬2, 4,1} независимы друг от друга (не выражаются композицией остальных).

Доказательство. Очевидно, что бинарная операция 1 не может быть представлена композицией унарных операций ¬2 и 4.

Операция ¬3 не может быть представлена композицией ¬2 и 1. Рассмотрим все возможные представления:

x  4x 

¬2x  4x

¬2(x1¬2x)=x1¬2x  4x

Все остальные представления сводимы к перечисленным трём в силу (3.4), (3.10) и (3.11).

Аналогично, операция ¬2 не может быть представлена композицией 4 и 1:

x  ¬2x 

4x  ¬2x

4(x1¬3x) = x14x  ¬2x

Все остальные представления сводимы к этим трём в силу тех же (3.4), (3.10) и (3.11).

Лемма доказана.

Следствие 3.1. Система операций {¬2, 4,1} образует базис операций Ldmin.

Рассмотрим теперь различные определения операции импликации. Импликацию можно задать, как при помощи комбинации отрицания и дизъюнкции, так и независимо. Для начала рассмотрим комбинационные определения:

x1y  1x1y (3.18) x1’y  1x2y (3.22)

x2y  ¬2x1y (3.19) x2’y  ¬2x2y (3.23)

x3y  4x1y (3.20) x3’y  4x2y (3.24)

x4y  5x1y (3.21) x4’y  5x2y (3.25)

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

В классической двузначной логике импликация должна быть истинной тогда и только тогда, когда следствие всегда имеет место, если имеет место предпосылка. Если говорить в терминах семантики возможных миров, импликация истинна в тех мирах, где: либо выполняется и следствие и посылка, либо только следствие, либо ничего. Если пойти дальше, можно прийти к интерпретации с точки зрения теории множеств. Истинность любой формулы А ограничивает универсум возможных значений до некоторого множества N, и если A1  A2, то N1  N2. Так, общезначимая формула не ограничивает универсум, поэтому может являться предпосылкой только другой общезначимой, и наоборот, тождественно ложная формула имеет в качестве допустимых значений пустое множество и, поэтому, ее следствием может выступать что угодно. К сожалению, такая интерпретация становится возможной для многозначной логики, только после выбора множества выделенных значений, поэтому поговорим о ней позже.

Рассмотрим импликацию, как следствие для обоих агентов. Эта импликация эквивалентна введенной ранее импликации 1. Её таблица истинности будет выглядеть так:

Таблица 3.8. Импликация как следствие для обоих агентов в логике Lmin

х1y

T

I

E

F

T

T

I

E

F

I

T

T

E

E

E

T

I

T

I

F

T

T

T

T

Рассмотрим импликацию как следствие для первого агента и как обратное следствие для второго. Смысл такого определения проявляется в логике спора. Её таблица истинности будет выглядеть так:

Таблица 3.9. Импликация как следствие для первого агента и обратное следствие для второго агента в логике Lmin

х5y

T

I

E

F

T

T

T

E

E

I

I

T

E

E

E

T

T

T

T

F

I

T

I

T

Этой операции не соответствует ни одно из определений (3.18)-(3.25). Её можно выразить следующим образом:

x5y = 5x15y = ¬15x15y = 4x1¬24¬2y (3.26)

Дальнейшее исследование логики Ldmin продолжим с построения аппарата логического вывода.

3.3.2. Вывод в четырехзначной диалоговой логике Ldmin

В предыдущем параграфе введена и описана четырехзначная диалоговая логика Ldmin, рассмотрены операции отрицания, конъюнкции, дизъюнкции, импликации и выявлены их свойства, также доказано, что система операций {¬2,¬3,1} образует базис данной логики. Однако, этого недостаточно для практического применения, необходим эффективный механизм вывода и, в первую очередь, определения общезначимости формулы в логике Ldmin.

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

Для начала введём следующие определения.

Определение 3.14. Пусть X есть конечное множество атомарных формул X = {a, b, c …}, тогда однозначное соответствие s: XLdmin называется сетапом, или единичным сетапом, здесь Lmin = {T,F,I,E}.

Определение 3.15. Формула F является выполнимой в логике Ldmin, если существует такой сетап s, при котором F принимает значение T.

Определение 3.16. Формула F является общезначимой в логике Ldmin, если на любом сетапе s, F принимает значение T.

Определение 3.17. Формула F является внутренне выполнимой в логике Ldmin, если существует такой сетап s, при котором F принимает значение T или I.

Определение 3.18. Формула F является внутренне общезначимой в логике Ldmin, если на любом сетапе s, F принимает значение T или I.

Определение 3.19. Формула F является внешне выполнимой в логике Ldmin, если существует такой сетап s, при котором F принимает значение T или E.

Определение 3.20. Формула F является внешне общезначимой в логике Ldmin, если на любом сетапе s, F принимает значение T или E.

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

Существует два варианта вывода на базе аналитических таблиц: с использованием означенных формул и без них. В диссертации используется вариант с использованием означенных формул.

Определение 3.21. Означенная формула – это запись вида FX, TX, IX или EX, где X - формула.

В классическом методе аналитических таблиц TX читается как “X – истина”, а FX X – ложь”. Аналитическая таблица – это дерево с означенными формулами в качестве подписей в узлах дерева. В корне дерева находится исходная означенная формула. Ветви дерева получаются декомпозицией формулы, выполняемой по определенным правилам.

В классической логике если формула X выводима (общезначима), то она не может быть ложью. При доказательстве формулы табличным способом первоначально формула X отвергается. Для того, чтобы доказать некоторую формулу X, ей приписывается ложное значение (FX), после чего строится дерева вывода для FX с целью получить противоречие. Если противоречие получено, формула X считается доказанной. Критерием противоречия является замкнутость дерева вывода. Ветвь дерева называется замкнутой, если она содержит одновременно FA и TA, где Aнекоторая подформула исходной формулы X. Если все ветви дерева формулы FX являются замкнутыми, то дерево вывода является замкнутым.

В методе аналитических таблиц для классической логики применяются следующие правила построения подветок: если встречается T(XY), то образуется два новых элемента ветви TX и TY. В случае, если встречается F(XY), ветвь расщепляется на две, в одной из которых добавляется FX, в другой FY.

При построении метода вывода на базе аналитических таблиц для четырехзначных логик важно определить способ означивания формул и дать критерий замкнутости дерева вывода.

Определение 3.22. Дерево вывода означенной формулы X, это граф (G,V) связностью 1, каждая вершина которого помечена означенной формулой, таким образом, что потомками каждой вершины являются вершины, помеченные формулами получающимися при декомпозиции означенной формулы, находящийся в вершине дерева.

Означенная формула Y является декомпозицией означенной формулы Х, YX, тогда и только тогда когда получена из Х при помощи правил декомпозиции. Существует четыре типа правил: -правила, -правила, -правила и -правила аналогичные правилам для логики Белнапа, предложенным Фиттингом (см.[140]).

1

1

1

3

4

1

3

5

6

2

2

1

2

2

4

1

1

1

2

T¬2X

TX

T4X

IX

F X1Y

FX

FY

I¬2X

EX

I4X

TX

E¬2X

IX

E4X

FX

F¬2X

FX

F4X

EX

1

2

3

4

I X1Y

IX

IY

FY

FX

E X1Y

EX

EY

FY

FX

1

2

3

4

5

6

T X1Y

IX

EY

EX

IY

TX

TY

Рис 3.3. Правила декомпозиции базисных функций в логике Ldmin

Так как операции {¬2, 4,1} образуют базис в Ldmin, то набор приведенных выше правил достаточен для декомпозиции произвольной формулы Ldmin. Для удобства использования можно аналогичным образом построить правила вывода для производных операций (см. рис 3.4).

1

1

1

2

T1X

FX

T5X

EX

T X1Y

TX

TY

I1X

EX

I5X

FX

E X2Y

EX

EY

E1X

IX

E5X

TX

I X2Y

IX

IY

F1X

TX

F5X

IX

F X1Y

TX

FY

1

2

3

4

I X1Y

IX

IY

TY

TX

E X1Y

EX

EY

TY

TX

T X2Y

TX

TY

EY

EX

F X2Y

FX

FY

EY

EX

T X2Y

TX

TY

IY

IX

F X2Y

FX

FY

IY

IX

E X1Y

IX

EY

FY

TX

I X1Y

EX

IY

FY

TX

1

2

3

4

5

6

F X1Y

IX

EY

EX

IY

FX

FY

I X2Y

TX

FY

FX

TY

IX

IY

E X2Y

TX

FY

FX

TY

EX

EY

T X1Y

IX

IY

EX

EY

FX

TY

Рис 3.4. Правила декомпозиции производных функций в логике Ldmin

Определим отношение декомпозиции .

Пусть x и y – ППФ Ldmin, тогда xy тогда и только тогда когда:

или x соответствует , y соответствует 1, в -правиле,

или x соответствует , y соответствует 1, в -правиле,

или x соответствует 1, y соответствует 2, в -правиле,

или x соответствует , y соответствует 1, в -правиле,

или x соответствует , y соответствует 3, в -правиле,

или x соответствует , y соответствует 4, в -правиле,

или x соответствует 1, y соответствует 2, в -правиле,

или x соответствует 3, y соответствует 1, в -правиле,

или x соответствует 4, y соответствует 2, в -правиле.

Лемма 3.4 Для любой ППФ Ldmin существует дерево вывода.

Доказательство. Существует единственное правило декомпозиции (см. 3.3) для любой связки из множества {¬2, 4,1} и любого значения формулы, т.е. для любой означенной формулы вида D¬2F1, D4F1, DF11F2, где D{T,F,E,I}, F1,F2ППФ Ldmin, существует единственное правило декомпозиции, применив которое мы уменьшаем количество логических связок на 1, в конечном итоге неизбежно перейдем к атомарным формулам, которые не могут быть далее разложены по правилам декомпозиции, но которые выражают ограничения на значение соответствующих переменных.

Определение 3.23. Ветвь дерева вывода называется замкнутой, если в ней существуют две вершины, помеченные одинаковыми формулами, означенными различным образом.

Определение 3.24. Дерево вывода означенной формулы X, является замкнутым тогда и только тогда, когда каждая его ветвь замкнута.

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

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

Таблица 3.10. Результаты вывода для формулы Х методом аналитических таблиц.

TX

FX

IX

EX

Результат

не замкнуто

замкнуто

замкнуто

замкнуто

Х тождественно истинно

(всегда принимает значение T)

замкнуто

не замкнуто

замкнуто

замкнуто

Х тождественно ложно

(всегда принимает значение F)

замкнуто

замкнуто

не замкнуто

замкнуто

Х тождественно внутренне истинно

(всегда принимает значение I)

замкнуто

замкнуто

замкнуто

не замкнуто

Х тождественно внешне истинно

(всегда принимает значение E)

не замкнуто

не замкнуто

замкнуто

замкнуто

Х тождественно согласно

(всегда принимает значение T или F)

замкнуто

замкнуто

не замкнуто

не замкнуто

Х тождественно спорно

(всегда принимает значение I или E)

не замкнуто

замкнуто

не замкнуто

замкнуто

Х тождественно истинно для первого агента

(всегда принимает значение T или I)

не замкнуто

замкнуто

замкнуто

не замкнуто

Х тождественно истинно для второго агента

(всегда принимает значение T или E)

замкнуто

не замкнуто

замкнуто

не замкнуто

Х тождественно ложно для первого агента

(всегда принимает значение F или E)

замкнуто

не замкнуто

не замкнуто

замкнуто

Х тождественно ложно для второго агента

(всегда принимает значение F или I)

не замкнуто

не замкнуто

не замкнуто

не замкнуто

Х полностью неопределенно

(может принимать любые значения)

замкнуто

не замкнуто

не замкнуто

не замкнуто

Х частично неопределенно

(X не может принимать значение T)

не замкнуто

замкнуто

не замкнуто

не замкнуто

Х частично неопределенно

(X не может принимать значение F)

не замкнуто

не замкнуто

замкнуто

не замкнуто

Х частично неопределенно

(X не может принимать значение I)

не замкнуто

не замкнуто

не замкнуто

замкнуто

Х частично неопределенно

(X не может принимать значение E)

Приведем пример вывода при помощи аналитических таблиц в Ldmin. Пусть дана формула 4A 1¬24¬2A, докажем что она является тавтологией.

0: F 4A1¬24¬2A

3: F A (1)

2: F ¬24¬2A (0)

3: E A (1)

4: F 4¬2 A (1)

5: E ¬2 A (4)

6: IA (5)

х

0: E 4A 1¬24¬2A

1: E 4A (0)

2: E ¬24¬2A (0)

4: I 4¬2A (2)

5: T ¬2A (4)

6: T A (5)

х

1: F 4A (0)

7: F 4A (0)

8: E ¬24¬2A (0)

9: E A (7)

10: I 4¬2A (8)

11: T ¬2A (10)

12: T A (11)

х

13: E 4A (0)

14: F ¬24¬2A (0)

15: F A (13)

16: F 4¬2A (14)

17: E ¬2A (16)

18: I A (17)

х

3: T A (1)

0: I 4 A1¬24¬2A

1: I 4A (0)

2: I ¬24¬2A (0)

4: E 4¬2A (2)

5: F ¬2A (4)

6: F A (5)

х

7: F 4A (0)

8: I ¬24¬2A (0)

9: E A (7)

10: E 4¬2A (8)

11: F ¬2A (10)

12: F A (11)

х

13: I 4A (0)

14: F ¬24¬2A (0)

15: T A (13)

16: F 4¬2A (14)

17: E ¬2A (16)

18: I A (17)

х

Рис 3.5. Пример вывода при помощи аналитических таблиц в Ldmin.

Как видим на рис 3.5, все деревья для означиваний F, E и I являются замкнутыми. Следовательно, формула 4A 1¬24¬2A может принимать только значение T, т.е. 4A 1¬24¬2A – тождественно истинна.

3.4. Диалоговое произведение логик и вывод на нем.

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

В связи с этим рассмотрим подход, связанный с определением вывода в произведении логик через композицию выводов в базовых логиках. Рассмотрим две логики L1 и L2 (мы подразумеваем, что этими логиками пользуются два разных агента – участника диалога). Пусть существует формула F, она является тавтологией (тождественно истинна) в логиках обоих агентов, будет ли она тавтологией в логике L1L2?

Для начала введём несколько определений.

Определение 3.25. Операция , определенная на L1L2 является дистрибутивной относительно декартова произведения логик, если существуют такие 1* и 2*, что (<x1,y1>,<x2,y2>,…,<xn,yn>) = <1*(x1,x2,…,xn), 2*(y1,y2,…,yn)>.

Определение 3.26. Диалоговым произведением L1L2 логик L1 и L2 назовём следующее отображение

: (L1,{1,…,n},T1)(L2,{1,…,m},T2)  (L1L2,{1*,…,k*},T1T2), такое что {f1*,…,fk*} – базис для функций, дистрибутивных относительно L1L2.

Лемма 3.4. Для любой формулы Ф, составленной из связок, дистрибутивных относительно L1L2, существует эквивалентное представление <Ф1,Ф2>.

Доказательство весьма тривиально. Согласно определению диалогового произведения, любую k-арную связку i*, можно представить в виде i*(<x1,y1>,<x2,y2>,…,<xk,yk>) = <i’(x1,x2,…,xk), i’’(y1,y2,…,yk)>. Если все <x1,y1>,<x2,y2>,…,<xk,yk> - атомарны, то лемма выполняется для случая произвольной формулы с одной связкой.

Пусть лемма доказана для любой формулы, включающей не более n логических связок. Рассмотрим формулу Фn+1 включающую n+1 логическую связку. Пусть связка последнего уровня (последняя в порядке применения) это j*(1, 2,…, l), где 1,…, l – формулы, включающие не более n логических связок, для них лемма выполняется по индуктивному допущению, следовательно, существует удовлетворяющие условию леммы 11, 21,…, 1l, 2l, такие что i=<1i,2i>. Опять-таки, по определению диалогового произведения имеем: j*(<11,21>,<12,22>,…,<1l,2l>)=<i’(11,12,…,1l), fi’’(21,22,…,2l)>=<Ф1,Ф2>.

Следствие 3.2. Пусть формула Ф общезначима в логиках L1 и L2, тогда она общезначима и в логике L1L2 и наоборот.

Доказательство. Вытекает из леммы 3.4.

Таким образом, выводимость в L1L2 напрямую следует из выводимости в L1 и L2. Однако, достаточно ли этого? Будет ли система функций для L1L2 функционально полной?

Лемма 3.5. Любая система функций, дистрибутивных относительно декартова произведения нетривиальных логик L1L2, не полна функционально.

Доказательство. Выберем в логиках L1 и L2 по два значения (это можно сделать, так как логики нетривиальны), обозначим их T1, F1, T2 и F2 соответственно. Рассмотрим унарную функцию (<x,y>), определённую на L1L2, которая принимает значение <T1,T2> тогда и только тогда, когда x=T1 и y=T2, а во всех других случаях она принимает <F1,F2>.

Предположим противное, пусть существует такая система функций {1,…, k}, что  представима их композицией. Тогда, согласно лемме 3.4, существуют такие 1*,2*, что  (<x,y>) = <1*,2*>. Из определения  вытекает: 1*(T1) = T1, 2*(F2) = F2. Следовательно,  (<T1,F2>) = <T1,F1> С другой стороны, согласно определению, <T1,F2>) = <F1,F2>. Следовательно, допущение неверно и лемма доказана.

Итак, система функций диалогового произведения не является функционально полной: не хватает «смешивающих», не дистрибутивных относительно L1L2 операций, результат которых не может быть декомпозирован на базовые логики. Примером такой функции может служить операция возражения (¬2 в Lmin). Если в формулу входит такая операция, то, очевидно, ее вывод нельзя будет основывать на выводе в базовых логиках.

Определение 3.27. Выбранными истинностными значениями многозначной логики L назовем два произвольно выбранных значения T и F таких, что T  F.

Определение 3.28. Обобщенной операцией «и» назовем произвольную операцию  такую, что для любых X  L выполняется: T  X = X, F  X = F.

Определение 3.29. Обобщенной операцией «или» назовем произвольную операцию  такую, что для любых X  L выполняется: T  X = T, F  X = X.

Определение 3.30. Пусть существуют многомерные логики L1 и L2. Пусть на обеих логиках определены выбранные истинностные значения: на L1  T1 и F1, на L2  T2 и F2, соответственно. Операцией смешивания назовем такую операцию & : L1L2 L1L2, что

&(<x,y>) = <T1,T2> если x=T1 и y=T2,

<F1,F2> если xT1 или yT2 (в противном случае).

Теорема 3.2. Пусть существует система функций , которая является базисом диалогового произведения конечнозначных логик L1L2, тогда {&} будет являться функционально полной системой операций определенных на L1L2.

Доказательство. Докажем теорему сперва для унарных операций. Пусть существует произвольная функция (<x,y>), докажем что ее можно построить путем композиции функций из {&}. Рассмотрим произвольные значения x=xi, y=yj. При помощи композиции функций из  можно построить следующие дистрибутивные относительно декартова произведения логик функции:

1i(<x,y>) = <T1,F2>, если x=xi 2 j(<x,y>) = <F1,T2>, если y=yj

<F1,F2>, если xхi <F1,F2>, если yyj

Функции 1i и 2j дистрибутивны относительно L1L2 так как представимы в виде 1i(<x,y>) = <1i*(x),F2> и 2j(<x,y>) = <F1,2j*(y)>, где 1j*(x), 2j*(y) – характеристические функции соответствующих логик.

Выберем функции, являющиеся обобщенными операциями «и» и «или»:

<x1,y1><x2,y2> = <x1x2,y1y2>

<x1,y1><x2,y2> = <x1x2,y1y2>

Рассмотрим функцию <xi,yj>(<x,y>) = 1i(<x,y>)&2j(<x,y>). Эта функция принимает значение <T1,T2>, если x=xi и y=yj, и значение <F1,F2> во всех остальных случаях. Теперь построим

*(x,y) = <x0,y0>L1xL2 (<x0,y0>(<x,y>)<x0,y0>).

Функция *(x,y) совпадает с (x,y) при любых <x0,y0>  L1 x L2

Теорема доказана для унарных функций.

Пусть теперь теорема выполняется для n-арных функций, требуется доказать, что она справедлива для n+1-арных функций.

Рассмотрим произвольную функцию (x1,x2,…xn,xn+1). Согласно индуктивному допущению функция (x1,x2,…xn,<x0,y0>) выразима при помощи композиции операций из {&} для любых <x0,y0>  L1 x L2, то есть существует формула F<x0,y0>, такая что (x1,x2,…xn, <x0,y0>) представима в виде F<x0,y0>.

(x1,x2,…xn,xn+1) = DL1L2 ( F<x0,y0><x0,y0> ), где <x0,y0> строится также как и в случае для унарных функций.

Теорема доказана.

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

Определение 3.31. Полным диалоговым произведением L1L2 логик L1 и L2 назовём следующее отображение

:(L1,{1,…, n},T1)(L2,{1,…,m},T2)  (L1L2,{1*,…,k*}{&},T1T2), такое что {1*,…,k*} – базис для функций, дистрибутивных относительно L1L2.

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

Для построения комбинированного вывода на полном диалоговом произведении логик необходимы: правила табличного вывода для базовых логик и специальные правила вывода для “&”. Также, с целью повышения удобства, возможно использование дополнительных правил вывода для других не дистрибутивных относительно произведения логик связок.

Процедура построения аналитической таблицы для формулы  в L1  L2.

  1.  Индексируем все k вхождений связки & в формулу . После чего, в  будут встречаться &1, &2,…&k ровно по одному разу.
  2.  Представим формулу покоординатно в виде <1,2>. Для этого все дистрибутивные относительно  связки *(X1,X2,…,Xn) расписываем в виде <*1(X1,X2,…,Xn), *2(X1,X2,…,Xn)>, где *1,*2 – соответствующее дистрибутивное представление; а недистрибутивные связки &i(X) просто заменяем <&i(X), &i(X)>.
  3.  Строим деревья вывода по методу аналитических таблиц для обеих частей получившегося кортежа, для всех вариантов означивания <D1,D2><1,2>. При этом для связок &i применяем следующие правила (см. рис 3.6).

T&X

D&X

F&X

T&x

х

F& x

F& x

F& x *

T&*x

FX

DX

TX

TX

Рис 3.6. Специальные табличные правила для операции смешивания &; последнее правило включает ветви для всех D  F, D  T; х – означает, что ветвь замкнута.

Определение 3.32. Деревья вывода D11 и D22, считаются сопряженными, если проверяемая означенная формула есть <D1,D2>. Две ветви сопряженных деревьев считаются сопрягаемыми, если для каждого вхождения D1j&i* в одну из ветвей, не существует вхождения D2j&i в другую ветвь, такого что D1jD2j

  1.  После построения деревьев вывода для всех возможных вариантов означивания выполняем следующую процедуру:
  2.   Для всех открытых ветвей ищем сопрягаемые им открытые ветви.
  3.   Если сопрягаемая ветвь не найдена, то помечаем ветвь как замкнутую.
  4.   Проверяем наличие незамкнутых ветвей, если таковые присутствуют, то дерево вывода для данного варианта означивания выполнимо, в противном случае дерево вывода для данного варианта означивания замкнуто.
  5.  Если деревья вывода замкнуты для всех вариантов означивания, кроме одного, то формула всегда принимает значения в соответствии с этим вариантом.

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

Теорема 3.3 Формула  может принимать значение <D1,D2> тогда и только тогда, когда в деревьях вывода D11 и D22 существуют сопрягаемые открытые ветви. 1 и 1 построены в соответствии с приведённым выше алгоритмом.

Доказательство. Необходимость. Пусть формула  может принимать значение <D1,D2>, т.е. существует такой сетап s1, что s1() = <D1,D2>.

Рассмотрим сетап s1. В соответствии с методом аналитических таблиц для многозначной логики, этому сетапу должна соответствовать пара открытых ветвей деревьев D11 и D22. Допустим противное, они не сопрягаемы, т.е. существует вхождение D1j&i* в одну из ветвей, и существует вхождение D2j&i в другую ветвь, такое что D1jD2j. Это означает что для j-того вхождения символа & интерпретация подформулы , к которой применяется этот символ, есть D2j. В силу табличного правила для &, это невозможно, так как тогда не будет достигнуто требуемое значение D1j. Получили противоречие, следовательно необходимость доказана.

Достаточность. Рассмотрим пару открытых сопрягаемых ветвей D11 и D22. Выписав все атомарные литеры, входящие в эти ветви, получаем их частичную интерпретацию. Выберем произвольную интерпретацию оставшихся атомарных литер. Получим сетап s1, s1() = <D1,D2>. Теорема доказана.

Как уже было отмечено, несмотря на то, что операция & является достаточной для перехода к полной системе функций, использование также и других недистрибутивных относительно произведения логик операций может упростить построение и вывод формул в таких логиках. В связи с этим, в методе комбинированного табличного вывода возможно использование специальных правил и для других вариантов недистрибутивных связок. В качестве примера рассмотрим связку &, представляющую собой обобщённое возражение. Пусть дано диалоговое произведение двух одинаковых логик LL. Операция & определяется следующим образом: &<x,y> = <y,x>. Пусть для определённости L = {T,F,I}, тогда специальные правила вывода для & будут выглядеть так:

T&X

F&X

I&X

T&x

F&x

I&x

T&x

F&x

I&x

T&x

F&x

I&x

T&*x

T&*x

T&*x

F&*x

F&*x

F&*x

F&*x

F&*x

F&*x

TX

FX

IX

TX

FX

IX

TX

FX

IX

Рис 3.7. Специальные табличные правила для операции возражения &.

В завершении параграфа, отметим еще один момент, связанный с операцией диалогового произведения логик. Несмотря на то, что эта операция является бинарной, она весьма легко обобщается на случай конечного числа аргументов, а именно: n(L1,L2,…,Ln) = L1L2…Ln. Это позволяет рассматривать и описывать диалоги не только между двумя, но также и любым другим конечным числом агентов-участников.

3.5. Модализированные логики диалога

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

В [15],[16] показана связь модальностей и интенциональных характеристик агентов, а также разработана модель, позволяющая описывать модальные характеристики высказывания при помощи аппарата многозначных логик.

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

Рассмотрим примеры таких логик (см. рис. 3.8)

F

T

F

T

T

F

T

F

N

(V, T)

(V, F)

(Y, F)

(Y, T)

(Y, N)

(W, T)

(W, N)

(W, F)

(V, N)

(a)

(б)

(в)

(г)

(д)

(V, T)

(Y, T)

(Y, N)

(V, N)

(V, F)

(Y, F)

Рис 3.8 Примеры модальных (многозначных) логик агентов-участников диалога: a-двузначная, а-трёхзначная, б-четырёхзначная, в-шестизначная, г-девятизначная, д-бесконечнозначная (нечёткая)

Из представленных логик 2 (б,в) уже являются произведениями логик истинности и логик модальности. При комбинировании представленных логик, возможно получение разнообразных диалоговых логик для различных диалоговых систем.

Рассмотрим еще один пример такой логики, восьмизначную логику возможности. Множество ее истинностных значений представлено на следующем рисунке (3.9).

F

F

T

T

N

U

R

B

Рис 3.9 Восьмизначная логика возможности Lp8.

Рассмотрим интерпретацию истинностных значений.

Таблица 3.11 Интерпретация истинностных значений восьмизначной логики возможности Lp8.

Значение

Интерпретация

N

Полная неопределённость: «ничего неизвестно»

B

Полное противоречие:

«необходима и истина и ложь одновременно»

F

Потенциальная ложь: «возможна ложь»

T

Потенциальная истина: «возможна истина»

F

Однозначная ложь: «необходима ложь»

T

Однозначная истина: «необходима истина»

U

Неопределённость: «возможна как истина, так и ложь»

R

Бивалентность: «либо всегда истина, либо всегда ложь»

Кроме описания модальности логика Lp8 обладает еще одним достоинством. Она позволяет описывать простые квантифицируемые значения на основе многозначности. Введем следующее определение.

Пусть имеем некоторое множество единичных сетапов W. Рассмотрим предикат P(x), где x  W. Агент A может обладать следующими знаниями относительно значения предиката P(x):

Нет никакой информации – запишем P = N,

xP(x)=F – запишем P = F,

xP(x)=T – запишем P = T,

xP(x)=F – запишем P = F,

xP(x)=T – запишем P = T,

xy(P(x)=T)&(P(y)=F) – запишем P = U,

(xP(x)=T)( yP(y)=F) – запишем P = R,

(xP(x)=T)&( yP(y)=F) – запишем P = B.

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

В силу того, что Lp8 является решёткой, возможна дефиниция операций дизъюнкции и конъюнкции как взятия наибольшей нижней и наименьшей верхней граней, соответственно. Операцию отрицания определим следующим образом:

Таблица 3.12 Операция отрицания в логике Lp8

Х

¬Х

X

¬X

N

B

F

T

B

N

T

F

F

T

U

R

T

F

R

U

Обратим внимание, что семантика операции строго сохраняется при переходе к форме с кванторами:

¬xP(x)=x¬P(x) : ¬T = F , ¬F = T

¬xP(x)= x¬P(x) : ¬T = F, ¬F = T

¬xy(P(x)&¬P(y)) = xy(¬P(x)P(y)) : ¬U = R

¬(xP(x)y¬P(y)) = xy (¬P(x)&P(y)) : ¬R = U

Определим множество формул логики первого порядка, сводимых к исчислению Lp8. Очевидно, что любая формула логики предикатов первого порядка представима в Lp8, если все кванторы стоят непосредственно перед предикатами, в этом случае можно переобозначить:

xP(x)  Р  {F, T, F, T}

xP(x)  Р  {F, T}

Пусть 1…n  {,} - кванторы

1x12x2…nxnP(x1,x2,…,xn)  Р {F, T, F, T}, если i = , i1…n

1x12x2…nxnP(x1,x2,…,xn)  Р {F, T}, если i = , i1…n

Далее простой перебор возможных значений переменных, образованных из предикатов, позволяет определить общезначимость формулы (T), тождественную ложность (F), выполнимость (T) и пр.

Определение 3.33. Назовем ППФ логики предикатов первого порядка сводимой к Lp8, если возможна описанная выше проверка.

В любой ППФ логики первого порядка возможно внесение кванторов по следующим правилам:

x(P(x)Q) = xP(x)Q (3.27)

x(P(x)&Q) = xP(x)&Q (3.28)

1x2y (P(x)Q(y)) = 1xP(x)2xQ(x) (3.29)

x(P(x)Q(x)) = xP(x)xQ(x) (3.30)

x(P(x)&Q(x)) = xP(x)&xQ(x) (3.31)

где ,1,2  {,} – кванторы

С другой стороны внесение кванторов невозможно в следующих случаях:

x(P(x) &Q(x))  xP(x)&xQ(x) (3.32)

x(P(x)Q(x))  xP(x)xQ(x) (3.33)

Соответственно, несводимые к Lp8 ППФ это такие формулы, в которых встречаются указанные выше выражения.

Основное преимущество Lp8 раскрывается при использовании в автономном агенте. Пусть существует набор фактов d1,d2,…,dn, где di = ( Pi(aj) = Di ), где Di  {T,F}. Изначально всем переменным среды p1,p2,...,pn устанавливается значение N, при поступлении факта di, переменная pi, соответствующая предикату Pi принимает значение F, если Di = F, или T в противном случае. Также существует набор достоверных знаний b1, b2,…,bn, где bi = ( pi = Li ), где Li  {N,B,T,F,F,T,U,R}, эти знания могут быть получены из надёжных источников, заданы первоначально или получены в результате вывода. При поступлении bi, pi устанавливается в Li.

Определим операции конъюнкции и дизъюнкции как взятие точной верхней и нижней граней соответственно, на их основании определим импликацию материально.

Таблица 3.13 Операция конъюнкции в логике Lp8

хy

N

F

T

R

F

T

U

B

N

N

F

T

R

F

T

U

B

F

F

F

U

F

F

B

U

B

T

T

U

T

T

B

T

U

B

R

R

F

T

R

F

T

B

B

F

F

F

B

F

F

B

B

B

T

T

B

T

T

B

T

B

B

U

U

U

U

B

B

B

U

B

B

B

B

B

B

B

B

B

B

Таблица 3.14 Операция дизъюнкции в логике Lp8

хy

N

F

T

R

F

T

U

B

N

N

N

N

N

N

N

N

N

F

N

F

N

N

F

N

F

F

T

N

N

T

N

N

T

T

T

R

N

N

N

R

R

R

N

B

F

N

F

N

R

F

R

F

F

T

N

N

T

R

R

T

T

T

U

N

F

T

N

F

T

U

U

B

N

F

T

B

F

T

U

B

Таблица 3.15 Операция материальной импликации в логике Lp8

хmy

N

F

T

R

F

T

U

B

N

N

F

T

R

F

T

U

B

F

N

N

T

R

R

T

T

T

T

N

F

N

R

F

R

F

F

R