Proceedings 2002

Select proceedings

Contents

МОДЕЛЬ ДИАЛОГА ИНТЕЛЛЕКТУАЛЬНЫХ АГЕНТОВ

 

 

Г. В. Рыбина

Московский Инженерно-Физический Институт

(Государственный Университет)

galina@ailab.mephi.ru

 

В. Ю. Берзин

Московский Инженерно-Физический Институт

(Государственный Университет)

galina@ailab.mephi.ru

 

 

Ключевые слова: модель диалога, локальная структура диалога, интеллектуальный агент, сети Петри

 

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

 

 

1.    Введение

 

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

Как правило, например в работе [1], модель диалога рассматривается в виде набора простейших протоколов взаимодействия, при этом каждый протокол задается в терминах состояний участников взаимодействия и действий участников, вызывающих переходы между этими состояниями. Тем самым, протокол взаимодействия участников может быть описан в виде недетерминированного конечного автомата. Главным недостатком подобного подхода является игнорирование таких понятий, как зависимость структуры диалога от решаемой в ходе взаимодействия задачи и текущего контекста диалога [2, 3].

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

Анализ этих и других известных работ, в частности [5, 6] показывает, что для моделирования взаимодействия интеллектуальных агентов используется незначительная часть результатов исследований  и разработок из богатого опыта построения человеко-машинных интерфейсов и интеллектуальных диалоговых систем.

Ниже обсуждаются результаты теоретического и экспериментального программного моделирования взаимодействия интеллектуальных агентов на основе разработанной модели диалога [8], построение которой оказалось возможным благодаря эволюционному осмыслению некоторых конкретных предложений отечественных исследователей ([2, 3, 7]).

 

 

2.      Постановка задачи

 

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

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

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

 

 

3.    Модель локальной структуры диалога

 

Модель локальной структуры диалога интеллектуальных агентов в терминах формализма сетей Петри [9] выглядит следующим образом:

LS = <Р, Т, I, О, C, L, M>,

где  Р={Pj} конечное множество состояний диалога (позиций);

Т={Ti} конечное множество переходов, с каждым из которых может быть связано некоторое условное выражение, использующее язык взаимодействия L;

С = {Ck} - множество типов высказываний на языке L (цветов), причем состав множества C существенно зависит от языка, на котором ведется взаимодействие;

  L – язык взаимодействия (KQML [11]);

I : T → {Delk} – каждый переход отображается во множество точек удаления цветов при осуществлении этого перехода. Каждая из точек удаления характеризуется позицией, из которой должен быть удален цвет и собственно цветом;

O : T → {Addk} – каждый переход отображается во множество точек добавления цветов при осуществлении этого перехода, а каждая из точек добавления характеризуется позицией, в которую должен быть добавлен цвет и собственно цветом;

M : P ® {<S0, Mark0>j} – начальная маркировка позиций

Рассмотрим каждый из компонентов более подробно.

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

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

Состав множества цветов существенно зависит от используемого языка взаимодействия. В том случае, если используется язык KQML ([11]), во множество цветов включаются такие элементы, как “Информирование о себе”, “Просьба добавить информацию в БД”, “Отклик”, “Запрос”, “Множественный запрос”, “Задание”, “Управление”, “Определение способностей”, “Уведомление”, “Работа в сети”.

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

 

 

4.    Алгоритм построения последовательности коммуникативных действий интеллектуальных агентов

 

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

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

Более детально, алгоритм выглядит следующим образом:

Шаг 1 Построение рабочей памяти решателя

  • Каждой позиции сети Петри соответствует ровно один объект из рабочей памяти решателя
  • Список атрибутов у всех объектов, соответствующих позициям, одинаков. Каждый атрибут соответствует одному из цветов (типов KQML - сообщений). Служебный атрибут показывает активность позиции.
  • Тип каждого атрибута – целое число.
  • Значение каждого атрибута определяется, как число вхождений соответствующего цвета в раскраску соответствующей позиции
  • Создается дополнительный объект трассировки с единственным атрибутом трассировки
  • Создается дополнительный объект окончания вывода с единственным атрибутом окончания вывода

Шаг 2 Построение базы знаний решателя

  • Построение правил, основанных на переходах

Ø      Построение предусловия правила: для каждой из пометок, входящих в предусловия или в список удаления перехода элементарное предусловие определяется, либо как:

(<Atr_Pos_from> >= <Tr>),

где <Atr_Pos_from> - значение соответствующего атрибута объекта, соответствующего позиции начала перехода;

<Tr> - количество вхождений атрибута в предусловие перехода.

либо, как

(<Atr_Pos> >= <Tr>),

где <Atr_Pos> - значение соответствующего атрибута объекта, указанного в списке удаления

<Tr> - количество вхождений атрибута в список удаления перехода.

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

Предусловие правила определяется, как конъюнкция всех элементарных предусловий.

Ø      Построение списка действий удалений и добавлений правила

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

Ø      Построение действий фиксации служебной информации

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

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

Ø      Построение правила вида if <предусловие> then <список действий добавления/удаления/фиксации служебной информации>

  • Построение правил, основанных на позициях

Ø      Если позиция является заключительной, то создается правило, предусловием выполнения которого является проверка атрибута активности позиции, а список действий включает установку атрибута окончания вывода объекта окончания вывода в значение “истина”.

Ø      Если коммуникативное состояние позиции – ожидание реакции, то создаются правила, предусловием выполнения которых является проверка атрибута активности позиции, а список действий состоит в увеличении значения одного из атрибутов позиции на 1 (Это означает, что в ходе выполнения ожидается приход сообщения, тип которого может быть добавлен в пометку позиции).

Шаг 3 Ожидание результатов вывода

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

Шаг 4 Формирование последовательности коммуникативных действий

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

В терминологии теории графов соседние переходы в последовательности сработавших переходов являются инцидентными одной позиции

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

i-ая позиция в последовательности позиций это та позиция, которой инцидентны i-ый и (i + 1) –ый переход из последовательности переходов.

Шаг 5 Выполнение последовательности коммуникативных действий.

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

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

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

 

 

5.      Пример диалога интеллектуальных агентов

 

Рассмотрим использование данной модели на примере простейшего диалога, связанного с информационным запросом:

Агент А отправляет запрос другим агентам

  • Ожидается 3 ответа от других агентов
  • После прихода ровно 3 ответов диалог успешно оканчивается
  • В случае прихода менее 3 ответов за данный промежуток времени открывается другой поддиалог

Наглядно этот диалог представлен на рис. 1.

Рис. 1 Пример диалога

 

В таблицах 1 и 2 приведены характеристики вершин и переходов данного диалога.

 

Таблица 1 Характеристики позиций

 

Позиция

Коммуникативное состояние

Раскраска

множество действий

1

Action

Æ

achieve …

2

Reaction

Æ

wait …

3

Final

Æ

Æ

4

Final

Æ

call subdialog

 

Таблица 2 Характеристики переходов

 

Переход

Предусловие

Удаление

Добавление

1-2

Æ

Æ

Æ

2-3

(tell 3)

(2 tell 3)

Æ

2-4

(no_performative 1)

(2 no_performative 1)

Æ

 

В процессе определения коммуникативной последовательности будут построены объекты рабочей памяти решателя, описанные в таблице 3.

 

 

 

 

Таблица 3. Объекты рабочей памяти

 

Имя объекта

Имя атрибута

Начальное значение атрибута

db_pos_1

active

true

tell

0

achieve

0

no_performative

0

db_pos_2

active

false

tell

0

achieve

0

no_performative

0

db_pos_3

active

False

tell

0

achieve

0

no_performative

0

db_pos_4

active

False

tell

0

achieve

0

no_performative

0

trace_obj

trace

sequence ()

 

При этом в базу правил решателя будут помещены следующие правила:

 

Источник

Текст

Переход 1-2

if the active of db_pos_1 = true then conclude that the active of db_pos_1 = false and conclude that the active of db_pos_2 = true and conclude that the trace of trace_obj = concatenate(the trace of trace_obj, “1-2”)

Переход 2-3

if the active of db_pos_2 = true and the tell of db_pos_2 >= 3 then conclude that the active of db_pos_2 = false and conclude that the active of db_pos_3 = true and conclude that the tell of db_pos_2= the tell of db_pos_2 – 3 and conclude that the trace of trace_obj = concatenate(the trace of trace_obj, “2-3”)

Переход 2-4

if the active of db_pos_2 = true and the no_performative of db_pos_2 >= 1 then conclude that the active of db_pos_2 = false and conclude that the active of db_pos_4 = true and conclude that the no_performative of db_pos_2= the no_performative of db_pos_2 – 1 and conclude that the trace of trace_obj = concatenate(the trace of trace_obj, “2-4”)

Позиция 2

if the active of db_pos_2 = true the conclude that the tell of db_pos_2 = the tell of db_pos_2 + 1

Позиция 2

if the active of db_pos_2 = true the conclude that the no_performative of db_pos_2 = the no_performative of db_pos_2 + 1

Позиция 2

if the active of db_pos_2 = true the conclude that the achieve of db_pos_2 = the achieve of db_pos_2 + 1

Позиция 3

if the active of db_pos_3 = true then conclude that final = true

Позиция 4

if the active of db_pos_4 = true then conclude that final = true

 

Если начальное значение final равно false и в качестве целевого утверждения ставится final = true, то после выполнения обратного вывода значение атрибута trace объекта trace_obj становится равным (“1-2”, “2-3”).

На основании данной информации сразу получается, что выполнять надо позиции в последовательности 1 – 2 – 3.

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

 

 

6.    Заключение

 

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

Работа выполнена при поддержке РФФИ РАН (грант № 00-01-00679).

 

 

Литература

 

  1. Muller J.P. A Cooperation Model for Autonomous Agents // Proceedings of the Third International Workshop on Agent Theories, Architectures, and Languages (ATAL96), Budapest, Hungary, 1996, P. 135-147.
  2. Рыбина Г.В., Естественно-языковая система для автоматизации рассчетных работ в САПР и АСУ ТП // Прикладные и экспериментальные лингвистические процессоры. Новосибирск: ВЦ СО АН СССР, 1982, с. 60 - 75.
  3. Дракин В.И., Попов Э.В., Преображенский А.Б., Общение конечных пользователей с системами обработки данных, Москва, Радио и Связь, 1988.
  4. d'Inverno M., Luck M., and Wooldridge M. Cooperation Structures // Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-97), Nagoya, Japan, 1997, p.600-605.
  5. Barbuceanu M. and Fox M. S. Conflict Management with a Credibility/Deniability Model // Proceedings of AAAI-94 Workshop on Models of Conflict Management for Cooperative Problem Solving, AAAI Technical Report, 1994
  6. Wooldridge M. and Haddadi A. Making it up as they go along: A theory of reactive cooperation // Agents and Multi-Agent Systems - Formalisms, Methodologies, and Applications / Ed. by W. Wobcke, M. Pagnucco, and C. Zhang. Springer-Verlag, June 1998.
  7. Койт М. Управление процессом общения в диалоговой системе // Труды международного семинара Диалог’99. В 2 томах. Т. 2. Таруса, 1999, с. 124 – 129.
  8. Рыбина Г.В., Петухов Д.М. Модель взаимодействия интеллектуальных агентов // Сборник научных трудов международной конференции "Знания-Диалог-Решение" (KDS'2001). С.-Петербург: ACKIC, 2001.
  9. Дж.Питерсон. Теория сетей Петри и моделирование систем: Пер. с англ. - М.: Мир, 1984. - 264 с.
  10. Woods W.A. Transition Network Grammars for Natural Language Analysis // Communications of the Association for Computing Machinery, 1976, p. 591 – 606.
  11. Labrou Y., Finin T., 1997. A proposal for a new KQML specification // TR CS-97-03. February 3, 1997.

 

 

Intelligent agent dialog model

Galina Valentinovna Rybina, Viatcheslav Yurjevitch Berzin

 

Key words: dialog model, local dialog structure, intelligent agent, petri net

 

The paper discusses questions related to intelligent agents interaction model for multiagent systems development. The local dialog structure model is proposed for intelligent agent interaction. Intelligent agent communicative action sequence constructing procedure with using the proposed model is considered.

 

Collection of proceedings