Агенториентированная технология построения систем искусственного интеллекта.

Евгений Борисов

16 февраля 2003 г.

ttp://mechanoid.narod.ru/misc/agents/index.html

1 Основные понятия

Двумя базовыми понятиями агенториентированого подхода, к построению систем ИИ, служат агент и среда. Единого определения этих понятий нет.
Неформально агент и среда могут быть описаны так :

Агент - автономная система, способная принимать решения исходя из своих внутренних представления о среде.
Агент существует в среде.
Агент взаимодействует другими агентами и со средой.
Агент может изменять среду.

В [6] агент определяется как интеллектуальное искусственное существо (носитель ИИ).

В [1] агент рассматривается как некоторый объект, который можно отделить от остального мира. Он существует во времени и пространстве, может взаимодействовать с другими агентами и средами, выполняя некоторые действия.

В [5] агент это автоматическая (полуавтоматическая) программно-аппаратная система, которая решает комплекс задач в динамично изменяющейся среде.

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

Требования к агентам по [5]

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

Классификация агентов по [5]

Реактивные агенты (behavior-based agent или situated agent).
Эти агенты действуют в режиме реального времени, обычно основываясь на очень небольшом количестве информации и простых правилах "ситуация-действие". Отсутствует символическое представление мира, вместо этого реактивные агенты принимают решения основываясь непосредственно на информации от своих датчиков. Вместо корректного или оптимального поведения, основное внимание в этом классе систем уделяется живучести.
Мыслящие агенты сохраняют внутреннее представление о мире как ментальное состояние, которое может меняться в процессе размышлений агента. Такая архитектура известна как BDI
(belief-desire-intention убеждения-желания-намерения).
Внутреннее состояние агента описывается с помощью множества ментальных категорий.
1. убеждения - представления о текущем состоянии среды.
2. желание - состояния среды, в которые агент стремится среду перевести. Агент может иметь несовместимые желания; желания могут быть не достижимы.
3. цели - множество совместимых и достижимых желаний.
4. намерение - множество избранных целей. Необходимо выделять некоторое множество целей для достижения, поскольку агент ограничен в ресурсах и не может достичь всех целей одномоментно.
Смешанные типы архитектур. Рассмотренные типы систем страдают рядом недостатков.
- Чистые реактивные агенты имеют очень ограниченную область применения, потому что на них трудно реализовать целеустремленное поведение.
- Большинство мыслящих агентов основываются на общих механизмах рассуждений. Они не достаточно гибкие и слишком медленно реагируют на внешние события.
Возможный путь преодоления этих ограничений есть многоуровневая архитектура. Главная идея такого подхода состоит в разбиении функциональных возможностей агента на несколько иерархических уровней. Каждый такой уровень взаимодействует с остальными в порядке иерархии.

2 InteRRaP

INTEgration of Reactive behavior and RAtional Plannig - объединение реактивного поведения и рационального планирования (по [5]).

2.1 Агент и среда

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

Составные части состояния InteRRaP агента:

ощущение (perception) агента.
мн-во убеждений (beliefs) - информационное состояние.
ситуация (situation). Ситуация это состояние среды. Она определяется как некоторая структура (множество), состоящая из убеждений агента.
мн-во целей (goals). Цель можно определить как состояние среды (ситуацию).
мн-во намерений (intentions). намерение - сформировавшийся план действий, который в последствии выполняется.

Среда в InteRRaP явным образом не определяется и присутствует как интуитивное понятие.

Для описания агента в InteRRaP определены специальные языки.

2.2 Архитектура

Принципиальная идея архитектуры InteRRaP состоит в разделении агента на три уровня (в соответствии с идеей смешанной архитектуры т.е. реактивность + способность к планированию) :

уровень поведения (behavior-based layer) - включает реактивность и методы решения стандартных (простых) задач.
уровень локального планирования (local planning layer) - предоставляет механизм для реализации целеустремленности.
уровень совместного планирования (cooperative planning layer) - служит для взаимодействия с другими агентами.

Решения для архитектуры управления агента InteRRaP

активация снизу-вверх (bottom-up activations) - уровень задействуется, только если уровень не может справиться с ситуацией.
выполнение сверху-вниз (top-down execution) - каждый уровень для достижения своих целей использует операционные примитивы определенные на ниже расположенном уровне.

**Рисунок:** схема InteRRaP
$\includegraphics[origin]{pict/interap.ps}$

Цикл управления в общем виде выглядит так :
ощущение $\rightarrow$ распознавание $\rightarrow$ решение $\rightarrow$ действие

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

порождение и пересмотр убеждений (belief generation and
revision) - отношение между убеждениями агента и его ощущениями.
оценка ситуации (situation recognition) - извлекает ситуацию из убеждений агента. Позволяет агенту определять степень необходимости действовать.
активация цели (goal activation) - определяет цели агента для данной ситуаций.
планирование (planning) - отображает текущие цели агента в мн-во операционных примитивов для достижения этих целей. Определяет 'что делать'
назначение (scheduling) - процесс слияния частичных планов для различных целей в единый план выполнения. Определяет 'что и когда делать'
выполнение (execution) - служит для корректного и своевременного применения запланированного.

Ниже представлен класс описывающий InteRRaP уровень

 class layer

  attributes
    Higher, Lower    /* соседние уровни */
    Bel, Goals, Ints /* текущие убеждения, цели, намерения */
    Sit, Sit-desc    /* ситуации и их описания */
    Ops    /* доступные операционные примитивы */
    Actreq /* активирующий запрос с уровня i-1 */
    Com    /* поручение с уровня i+1 */
   [...]

  methods
    b-upd +<Bel> {...}    /* коррекция убеждений */
    s-rec +<Sit> +<Bel> +<Sit-desc>{...} /* определение ситуации*/
    g-act +<Sit> +<Goals> {...} /* активация целей */
    comp-check +<Sg> +<Ops> {...} /* проверка компетенции */
    op-select +<Sg> +<Ops> {...}  /* планирование */
    schedule +<Int> +<Ints> {...} /* назначение */
    execute +<Int> {...}  /* исполнение */
   [...]

   cycle
     Bel = b-upd(Bel);
     Sit = s-rec(Sit U Actreq, Bel, Sit-desc);
     Goals = g-act( Sit, Goals );
     Sg = {(S,G)| (S in Sit)^(G in Goals)^(G = g-act(G,_))};
     (Comp-sg, Nocomp-sg) = comp-check(Sg, Ops);
     foreach Sg' from Nocomp-sg /* передача управления на уровень выше */
       Higher <- receive(request, activate(Sg'));
     Int = op-select(Comp-sg, Ops);
     Int = schedule(Int, Com);
     Int = execute(Int);

Рассмотрим операционные примитивы. Модели поведения (patterns of behavior - PoBs) есть самый нижний уровень операционных примитивов. Это есть некоторые стандартные решения. Они представлены в виде программ на execution language.

class PoB
  attributes
      Name
      Type   /* { reactor | procedure }*/
      Args   /* аргументы активации PoB */
      State  /* { inactive | active | committed }*/
      Resources /* список требуемых ресурсов */
      Priority  /* целое число - статический приоритет PoB*/
      Act-cond  /* условие активации */
      Succ-cond /* условие успешного завершения */
      Fail-cond /* условие неудачного завершения */
      Exeption-list /* список с описаниями
                       исключений (exeptions) */
      Body      /* выполняемая программа */
  methods
      meth init     /* инициализазия PoB */
      meth activate /* активация PoB */
      meth step     /* выполнение следующего шага PoB */
      meth uncommit /* остановка выполнения PoB */
      meth check-act-cond /* проверка условий активации */
      meth check-monitors /* проверка условий мониторинга */
      meth enable   /* разрешить активацию PoB */
      meth disable  /* запретить активацию PoB */
      meth inhibit <Sit> /* затормозить активацию PoB */
      meth permit <Sit>  /* отменить предшествующее
                            торможение  */

2.3 Языки

В InteRRaP определяется несколько языков. Языки организованы как иерархическая структура. С помощью этих языков осуществляется описание системы.

Язык execution language служит для описания моделей поведения. Execution language строился с учетом следующих соображений. В процессе функционирования агента могут возникать события, требующие немедленного ответа. Следовательно, важным требованием к выполняемой программе есть возможность ее прерывать. Это требование можно удовлетворить рассматривая программу как последовательность элементарных (атомарных) инструкций и определить процедуру пошагового выполнения чтобы программу можно было прервать на любом такой инструкции. Таким образом, execution language должен допускать пошаговое выполнение непрерывных(атомарных) блоков программы.
БНФ execution language:
```
 program ::= block [ ';' program ]
 block ::= '{' block-content '}' | primitive-inst
 block-content ::= while condition
                     do block-content od |
                   if condition
                      then block-content
                      else block-content fi |
                   primitive-inst
 primitive-inst ::= wif_execution |
                    lpl-call |
                    pob-activation |
                    modifier
 condition ::= ATOMIC FORMULA
 wif-execution ::= ex '(' wif-primitive ')'
 lpl-call ::= call '(' lpl ',' do '(' goal-spec ')' ')' | ...
 pob-activation ::= activate '(' pob-spec-list ')'
 wif-primitive ::= LIST OF DOMAIN-DEPENDENT ACTUATOR / SENSOR CALLS
 goal-spec ::= FORMULA
 pob-spec-list ::= '[' { pob-spec }+ ']'
 pob-spec ::= pobname '(' PARAMETER-LIST ')'
 pobname ::= ATOM
 modifier ::= assert GROUND FORMULA |
              retract GROUND FORMULA
```
( primitives in uppercase )
Исполнение программ на этом языке осуществляет метод step класса PoB.
Более высокий уровень операционных примитивов это уровень локального планирования. Планы, составляющие уровень локального планирования операционных примитивов, представляются как программы на языке . Основой для такого языка служат модели поведения, т.е. элементарные шаги плана берутся из моделей поведения.
Язык определяется следующим образом :
1. $P=\{p_0,p_1,\ldots\}$ - множество элементарных шагов плана.
2. $C=\{c_0,c_1,\ldots\}$ - множество предикатов.
тогда
1. $\epsilon \in L_0$ - пустой план
2. для $p \in P$ $p \in L_0$
3. для имеем
  - $p_0,\ldots,p_n \in L_0$ - последовательная композиция
  - $p_0;\ldots;p_n \in L_0$ - дизъюнктивная композиция
4. для имеем
  - if then else fi $\in L_0$
  - while do od $\in L_0$
На основе определяются языки общих планов и .
Язык :
- множество агентов.

есть -план где
1. Р есть
  - $\epsilon \in L_0$ - пустой план, или
  - множество $[(a_1,P_1),\ldots,(a_n,P_n)]$
    где
    это $P_i = p_{i1},\ldots,p_{im_i}$ - конъюнкция -планов агента
2. $C=[c_1,\ldots,c_m]$ - множество условий в форме
  между $p_i = p_{ik_i} \in P_i$ и $p_j = p_{jk_j} \in P_j$ , $i\neq j$
Язык :
- множество агентов.
- множество ролей для агентов.
- ролевые переменные.
есть -план где
1. Р есть
  - $\epsilon \in L_0$ - пустой план, или
  - множество $[(r_1:R_1,P_1),\ldots,(r_k:R_k,P_k)]$
    где
    это $P_i = p_{i1},\ldots,p_{im_i}$ - конъюнкция -планов агента
2. $C=[c_1,\ldots,c_m]$ - множество условий в форме
  между $p_i\in P_i$ и $p_j\in P_j$ , $i\neq j$

3 AE - ''Агенты и Среды''

AE - ''agents and environments'' (''агенты и среды'') (по [2] [1])

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

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

Агент и среда определяется в терминах алгебры поведений. Поведение рассматривается как элемент алгебры поведений над алгеброй действий .

3.1 Алгебра действий

Операции алгебры действий :

$a\times b$ комбинация действий
операция недетерминированного выбора
операция последовательной композиции

Также определены :

$\delta$ - пустое действие (нейтральный элемент для комбинации)
- нулевой элемент (невозможное действие)

$\displaystyle a\times b =b\times a$			(1)
$\displaystyle (a\times b) \times c= a\times (b \times c)$			(2)
$\displaystyle a\times \delta = \delta \times a = a$			(3)
$\displaystyle a\times 0 = 0 \times a = 0$			(4)
$\displaystyle a+a=a$			(5)
$\displaystyle a+b=b+a$			(6)
$\displaystyle a+b)+c=a+(b+c)$			(7)
$\displaystyle a+0=a$			(8)
$\displaystyle (ab)c=a(bc)$			(9)
$\displaystyle a\delta=\delta a=a$			(10)
$\displaystyle a0=0a=0$			(11)
$\displaystyle (a+b)\times c = a\times c + b\times c$			(12)
$\displaystyle (a+b)c = ac + bc$			(13)
$\displaystyle c(a+b) = ca + cb$			(14)

Таким образом алгебра действий есть коммутативный моноид.

Действие называется детерминированным, если оно не может быть представлено как недетерминированный выбор двух различных ненулевых действий.
Детерминированное действие называется примитивным, если данное действие нельзя разбить на комбинацию действий отличных от и $\delta$ (действия и $\delta$ есть примитивными).
Недетерминированное или непримитивное действие называется составным.

3.2 Алгебра поведений

Алгебра поведений имеет две операции :

недетерминированный выбор - ассоциативная, коммутативная, идемпотентная, бинарная операция $u+v\ ;\ u,v \in F(A)$
операция префикса где $a\in A$ это действие, $u\in F(A)$ это поведение

$\bot$ - минимальный элемент алгебры поведений
$\Delta$ - пустое поведение не выполняет никаких действий, описывает завершение процесса
- невозможное поведение, нейтральный элемент для недетерминированного выбора, описывается таким же символом что и невозможное действие

$\displaystyle u+v=v+u$			(15)
$\displaystyle (u+v)+w=u+(v+w)$			(16)
$\displaystyle u+u=u$			(17)
$\displaystyle u+0=0+u=u (a+b)u = au + bu$			(18)
$\displaystyle 0u=0$			(19)

где $u,v,w\in F(A)$ - поведения, $a,b\in A$ - действия

Отношение аппроксимации (approximation) $\subseteq$ алгебры поведений над есть минимальный частичный порядок, который удовлетворяет выше представленные соотношения для алгебры поведений.

Каждое поведение может быть представлено как

$\begin{displaymath}u = \sum_{i\in I} a_i u_i+\varepsilon\end{displaymath}$

где

- ненулевое детерминированное действие,

- поведение,

- некоторое множество индексов, $\varepsilon=\Delta,\bot,\Delta+\bot,0$ - терминальные константы

3.3 Агент

Для агента в терминах AE понятие 'состояние' в явном виде не определяется. Вместо этого вводится понятие 'поведение' как агента в данном состоянии. Агент и его поведение рассматриваются как эквивалентные понятия. Агент определяется в терминах алгебры поведений.

3.4 Среда

Среда это агент снабженный функцией внедрения

$\begin{displaymath}Ins(e, u) = e[u]\end{displaymath}$

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

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

3.5 MIE

Система MIE использует модель ''агенты и среды''. MIE - математическая информационная среда, это мультиагентная система из агентов разных типов [1]. MIE осуществляет интерактивную обработку математических текстов (чтение, понимание, запись, проверка на корректность и непротиворечивость etc.). Математические тексты представлены в виде формализованного математического языка (FML) близкого к естественному. Это позволяет автоматически получать информацию из обычных математических текстов, представленных в электронном виде.

Типы агентов MIE:

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

Для реализации MIE используется система алгебраического программирования - APS с базовым языком APLAN. APLAN основывается на логике переписывания и позволяет комбинировать различные программные парадигмы : процедурную, функциональную, алгебраическую и логическую.

Язык действий AL [3] представляет собой часть APS. Этот язык используется для описания вычислительных систем, которые содержат элементы параллелизма и сетевой работы, распределенных систем и систем, которые должны взаимодействовать со средой. Построение агента в APS происходит по следующей схеме.

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

Литература

1: A. A. Letichevsky, J. V. Kapitonova, V. A. Volkov
''Proving theorem and reading mathematical texts in Mathematical Information Enviroment'', international workshop RTETP-2000, Kyiv, 29-31 May 2000, ISBN 966-02-1654-8
2: A.A.Letichevsky, D.R.Gilbert
''A model for interactions of agents and environments.''
3: A.A.Letichevsky, D.R.Gilbert
''A general theory of action languages''
''Кибернетика и системный анализ'', 1998, N1
4: Х.Уэно, Т.Кояма, Т.Окамото, Б.Мацуби, М.Исидзука
''Представление и использование знаний'', Москва, ''МИР'', 1987.
5: Mluller Jorg P.
''The design intelligence agents : a layered approach''
Springer 1996 (Lectures notes in computer science; vol. 1177 : Lectures notes in artifical intelligence) ISBN 3-540-62003-6
6: В.В.Девятков ''Системы искусственного интеллекта''
Москва,''МГТУ им. Н.Э.Баумана'', 2001

Evgeny S. Borisov
2005-03-15