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

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

16 февраля 2003 г.

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
  - while do od
На основе определяются языки общих планов и .
Язык :
- множество агентов.

есть -план где
1. Р есть
  - $\epsilon \in L_0$ - пустой план, или
  - множество $[(a_1,P_1),\ldots,(a_n,P_n)]$
    где
    это $P_i = p_{i1},\ldots,p_{im_i}$ - конъюнкция -планов агента
2. - множество условий в форме
  между $p_i = p_{ik_i} \in P_i$ и $p_j = p_{jk_j} \in P_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. - множество условий в форме
  между $p_i\in P_i$ и $p_j\in P_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)
			(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 Алгебра поведений

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

недетерминированный выбор - ассоциативная, коммутативная, идемпотентная, бинарная операция
операция префикса где $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: Muller 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

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