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

На правах рукописи

Колосов Герман Геннадьевич

ОРГАНИЗАЦИЯ И ПРОЕКТИРОВАНИЕ ФУНКЦИОНАЛЬНО-ОРИЕНТИРОВАННЫХ ПРОЦЕССОРОВ ОБРАБОТКИ ПРОДУКЦИОННЫХ ЗНАНИЙ НА ОСНОВЕ КЕТЕ-СЕТИ ДЛЯ ИНТЕЛЛЕКТУАЛЬНЫХ АГЕНТОВ РЕАЛЬНОГО ВРЕМЕНИ

Специальность: 05.13.15 - Вычислительные машины и системы

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2005

Работа выполнена в Санкт-Петербургском государственном электротехническом университете «ЛЭТИ» им. В.И. Ульянова (Ленина)

Научный руководитель -

кандидат технических наук, доцент Пантелеев М.Г.

Официальные оппоненты:

доктор технических наук, доцент Сергеев М. Б.,

кандидат технических наук, доцент Крылов Б. А.

Ведущая организация - Санкт-Петербургский институт информатики и

автоматизации РАН

Защита диссертации состоится « ^ » _ 2005г. в 40 часов на

заседании диссертационного совета Д 212.238.01 Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» им. В.И. Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан «¿7» С&ИГлЦА 2005г.

Ученый секретарь

диссертационного совета г У/ V I Пантелеев М.Г.

2 PPM__

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Как показал анализ различных архитектур и приложений ИА, при построении агентов широко используются продукционные системы (ПС), задаваемые совокупностью правил «Если ..., то ...». Данная модель используется в разных подсистемах агента для представления как предметных, так и управляющих знаний и в ряде случаев составляет до 50% алгоритмического обеспечения ИА. Таким образом, эффективность функционирования ИА в открытых динамических средах может быть существенно повышена за счет средств аппаратной поддержки алгоритмов данного класса.

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

Быстрый прогресс технологии программируемых логических интегральных схем (ПЛИС) создал возможность реализации высокопроизводительных функционально-ориентированных процессоров (ФОП) обработки знаний в конструктиве типовых плат расширения, подключаемых к стандартным магистральным интерфейсам базовых вычислительных платформ. Перспективным направлением реализации ФОП обработки знаний во встроенных системах является использование «систем на кристалле» (System-on-programmable-chip), получивших значительное развитие в последние годы. Такой подход позволяет повысить функциональность и производительность ФОП за счет снижения затрат на взаимодействие с базовым процессорным ядром и возможности оперативной реконфигурации дополнительных аппаратных средств.

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

|«>С. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА

< ! "" '»■ jl

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

1. Анализ известных подходов к построению средств аппаратной поддержки ПС на основе RETE-сетей с точки зрения эффективности их использования при построении ИА РВ.

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

3. Анализ и разработка эффективных с точки зрения аппаратной реализации способов внутреннего представления и методов оптимизации RETE-сети;

4. Разработка базовых архитектур и методики проектирования ФОП аппаратной поддержки ПС на основе RETE-сети;

5. Разработка методов и алгоритмов эффективной компиляции ПБЗ в форматы внутреннего представления оптимизированной RETE-сети;

6. Разработка методики и экспериментальная оценка производительности ФОП с использованием макетного образца.

Предмет и методы исследования

Предметом исследования являются способы представления и обработки ПБЗ на основе RETE-сети и принципы организации ФОП аппаратной поддержки алгоритмов логического вывода для ПС на базе RETE-сетей. При решении поставленных задач использовались методы теории оптимизации, в частности целочисленное линейное программирование; теории автоматов; методы алгоритмизации и программирования на языках С++, Fortran; методы проектирования и разработки цифровой аппаратуры на базе ПЛИС с использованием языков описания дискретных устройств (VHDL).

Научную новизну работы составляют:

1. Модификации RETE-сети, ориентированные на аппаратную реализацию продукционных систем, отличающиеся от известных использованием статических структур данных, что позволяет при незначительном росте объема памяти БЗ существенно упростить архитектуру и повысить производительность ФОП.

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

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

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

Практическая значимость работы заключается в следующем:

1. Реализован алгоритм быстрой компиляции исходной БЗ в оптимальную RETE-сеть с квадратичной временной сложностью и предсказуемым временем обработки, позволяющий использовать ФОП в ИА РВ с динамическим формированием БЗ.

./- , „-.!»•. J

\;г '*» ; 1 * Wfr4p"4> ' 1

»»» г**

2. Разработан пакет VHDL-модулей масштабируемого ядра ФОП обработки ПБЗ на основе RETE-сети, позволяющий проектировать подобные устройства с учетом различных форм неопределенное™ и требований по параметрам обрабатываемых БЗ, таких как число объектов, глубина сети, ширина входного токена, и т.п.

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

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

5. С использованием созданного аппаратно-программного комплекса проведено экспериментальное исследование и установлено, что выигрыш ФОП в производительности по сравнению с программными интерпретаторами на процессорах общего назначения составляет от 10 до 40 раз в зависимости от характеристик БЗ и БД. Показано, что время обработки одного токена и всей БЗ являются предсказуемыми величинами, что имеет существенное значение при построении ИА РВ.

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

Внедрение результатов работы. Результаты диссертационной работы, полученные в ходе выполнения НИР 5937/ВТ-210, использовались на предприятии ФГУП НПП «Рубин» при разработке средств аппаратной поддержки экспертных систем реального времени для автоматизированных систем оценки и прогнозирования воздушной обстановки.

Работа также была поддержана грантом Минобразования РФ "Организация и проектирование процессоров аппаратной поддержки объектно-продукционных моделей представления и обработки знаний для интеллектуальных агентов реального времени" (НИР ВТ-39/ГТАТ, проект ТОО-3.3-2672) и двумя персональными грантами СПбГЭТУ за 2001 и 2002 гг.

Апробация результатов исследования. Основные положения и результаты работы докладывались и обсуждались на: 7-ой национальной конференции по искусственному интеллекту с международным участием «КИИ'2000» (Переел авль-Залесский, 2000); 4-й и 5-й международных симпозиумах «Интеллектуальные системы» ИНТЕЛС (Москва, 2000; Калуга, 2002); 4-й международной конференции по мягким вычислениям и измерениям SCM'2001 (Санкт-Петербург, 2001); международном конгрессе «Искусственный интеллект в XXI веке» ICAI'2001 (Двиномор-ское, 2001); международной НТК «СуперЭВМ и многопроцессорные вычислительные системы» MCS'2002 (Таганрог, 2002); международной конференции «Искусственные интеллектуальные системы» IEEE ICAIS'2002 (Двиноморское, 2002); 4-й и 5-й международных НТК «Искусственный интеллект. Интеллектуальные и многопроцессорные системы» ИМС (Двиноморское, 2003; Таганрог, 2004); НТК ППС СПбГЭТУ за 2001, 2002 и 2003 гг.

Публикации. По теме диссертации опубликовано 15 научных работ, в том числе 4 статьи в журналах и 1 авторское свидетельство на полезную модель.

Структура н объем работы.

Диссертация состоит из введения, четырех глав, заключения, трех приложений и списка литературы, включающего 202 наименования. Основная часть работы изложена на 146 страницах машинописного текста. Работа содержит 68 рисунков и 2 таблицы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность диссертационной работы, определяются цель и задачи исследования, формулируются научная новизна и практическая ценность результатов.

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

На примере ряда известных архитектур ИА РВ (SOAR, Guardian, REX и др.) показано, что агенты представляют собой гибридные системы ИИ, т.е. строятся с использованием разных моделей представления знаний и традиционных вычислительных алгоритмов. Значительный удельный вес при этом составляют ПС, используемые для представления как предметных, так и управляющих знаний.

Ядро ПС включает: базу знаний, представленную набором продукционных правил вида ЕСЛИ=>ТО; базу данных (рабочую память), содержащую множество фактов (элементов рабочей памяти - ЭРП), и машину логического вывода (MJIB), называемую также интерпретатором ПС. Левая часть правил задается набором условных элементов (УЭ) или предикатов, а правая часть - группой операторов. МЛВ реализует процесс вывода, включающий фазы: сопоставления (matching), разрешения конфликтов (conflict resolution), и выполнения действий (action). В процессе вывода МЛВ сопоставляет факты БД с УЭ правил. Известно, что вычислительные затраты на фазу сопоставления составляют до 90% общих вычислительных затрат при обработке ПС.

Известные на сегодняшний день способы представления ПБЗ являются разновидностями трех базовых методов: списочная форма, деревья решений (ДР) и RETE-сети. Область применения ДР ограничивается задачами описания данных, классификации и регрессии. Ключевой недостаток списочной формы заключается в необходимости сопоставления на каждой итерации всех фактов, независимо от того, изменились они или нет за время предыдущей итерации. Наиболее эффективным способом представления ПБЗ является RETE-сеть — граф потока данных специального вида, позволяющий исключить избыточность вычислений при обработке. На рис. 1 представлена RETE-сеть, соответствующая правилу : Самолет ?Р (Высота малая, Скорость высокая, Курс ?Х) И Объект ?К (Направление ?Х, Скорость средняя) => Цель ?Р = атака объекта ?К Сеть содержит три типа узлов с памятью: а-узлы, ß-узлы и терминальные. Добавление или удаление факта в БД влечет подачу соответствующего токена на вход RETE-сети. Токен попадает в а-узел, определяемый набором констант. Далее, он подается на вход ß-узла, где сопоставляется с поступившими ранее на другой вход по значению одной из переменных. При совпадении результат в виде кортежа ЭРП поступает на следующий ярус сети. В терминальный узел поступает набор

ЭРП, удовлетворяющий условию правила. В конфликтное множество при этом добавляется пара правило и набор удовлетворяющих ему объектов.

Существующие подходы к аппаратной поддержке RETE-сетей (DADO, Oflazer, Non-Von и др.) ориентированы на отображение состава БЗ в аппаратную структуру вычислителя, что влечет существенный рост аппаратных затрат и затрудняет возможность оперативной модификации БЗ или обработки разных БЗ одним аппаратным модулем. Системы с массовым параллелизмом и программируе-

(jtoöT)

(Объект)

Дерево Л проверки констант

(Скорость) (курс) ( Направл. ) (Скорость)

а-узлы-{[

ß-узлы -<

(Малаш) (высокая)

(средняя)

ТГ

ß4 - узел с комбинаторным накоплением токенов

Терминальный узел

Рисунок 1 - Пример RETE-сети

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

В ряде архитектур ИА РВ допускается модификация/формирование БЗ в процессе работы агента (CIRCA, REX, и др.). Использование ФОП в таких системах предполагает решение задачи эффективной компиляции RETE-сети из исходной БЗ за относительно малое и предсказуемое время. Построение оптимальной RETE-сети в общем случае является NP-полной задачей, поэтому необходима разработка методов эффективной компиляции, исключающих комбинаторный перебор вариантов сети.

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

Основным препятствием аппаратной реализации RETE-сети является комбинаторное накопление токенов в ß-памяти при увеличении глубины сети и количества объектов в БД. Это влечет необходимость использования динамических структур данных для организации памяти узлов и большие затраты на хранение и обработку вспомогательных данных. Аппаратная интерпретация в такой форме, как показывает анализ, не дает существенного выигрыша. Прямой переход к статиче-

ским структурам для классической КЕТЕ-сети приводит к резкому росту затрат памяти, определяемому выражением:

л=2 к=г " ч * /

где N - число объектов, Р - число классов, М - количество УЭ в правиле. Наибольший вклад в рост объема памяти вносят Р-узлы, выполняющие сопоставление предикатов по разным классам при наличии переменных одновременно в полях объекта и значения. Такие узлы названы «критическими».

Исходя из этого, в работе предложен ряд модификаций 1ШТЕ-сети, позволяющих использовать фиксированные форматы в структуре Р-узлов при умеренных затратах памяти:

1. Декомпозиция сложных УЭ правила во множества элементарных УЭ с фиксированным набором полей <класс, объект, атрибут, значение>.

2. Декомпозиция УЭ с двумя переменными во множества УЭ с фиксированным полем одной переменной.

3 Разбиение Р-подсети на отдельные подсети для каждого класса.

4. Замена терминальных узлов на новый тип узлов - у-узлы для систем, обрабатывающих отношения объектов разных классов.

5. Использование многовходовых р-узлов с учетом оптимального числа входов по критерию производительности.

6. Склеивание Р-узлов разных продукций, выполняющих сопоставление по одним и тем же подмножествам предикатов.

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

Затраты памяти для модифицированной КЕТЕ-сети оцениваются выражением:

№Чо^=ркГя+¥сР11кРщ, (2)

И

где Р - число классов, Уср - среднее число логических значений переменной, РУАК - число разных переменных в правиле, УАЯ, - число разных переменных в классе]. Например, для БЗ из 1000 правил со следующими характеристиками: N = 100; Р = 7; М = 30; РУАЯ=5; Уср = 4; УА^ = 3, КЕТЕ-сеть с фиксированной памятью в классическом варианте занимала бы 4*103 Гслов (1), тогда как в модифицированной форме - порядка 10 МСлов (2).

Класс

Атрибут (Высот:

Значение (м

^-подсеть класса «Самолет»

(направление)

(высокая)

Э-подсеть

класса

«Объект»

Рисунок 2 - Пример модифицированной RETE-сети

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

Проектирование ФОП аппаратной поддержки ПС предполагает на первом этапе построение виртуальной машины обработки RETE-сети как совокупности абстрактных элементов данных и укрупненных операций над ними.

ЭРП (факты) отображаются в виде WME = <Cls, Obj, Attr, Val>, где Cls -класс объекта, Obj - идентификатор объекта, Attr - атрибут, Val - значение. На вход RETE-сети подаются входные токены TKNln = <TG, WME>, где TG - тэг, передающий знак токена (добавление/удаление).

Конфликтное множество CS представляет собой набор упорядоченных пар, каждая из которых содержит продукцию и список удовлетворяющих ей объектов: CS = < (PR,, OLi), (PRz, OL2), ..., (PRp, OLP) >, где PR,... PRP - продукции; OL, ... OLp - списки удовлетворяющих им объектов; Р - количество продукций. При появлении в БД набора объектов, свойства которых удовлетворяют условию продукции, соответствующий набор вносится в конфликтное множество. Выходной токен RETE-сети содержит пару (PR¡, OLJ конфликтного множества. Операции над конфликтным множеством можно формально записать следующим образом: CSt+i = CS, u{(PR„ OL,)}, при положительном тэге токена, CS,+i = CSt \ {(PR,, OL,)}, при отрицательном тэге токена, где t - время до итерации; t+1 - время после итерации.

Терминальный узел хранит решения по продукции. На его вход поступает токен, содержащий полный набор ЭРП, удовлетворяющий условию продукции. На выходе формируется пара (PR,, OLj), где i - идентификатор продукции.

Базовой операцией алгоритма является операция сопоставления в Р-узле: Match (YM, TKNfiM): VTKN, е YM, TKNpM ° TKN,

»

где TKNjn = < TGdj, WME^ь WMEm 2, ■■■, WMEin_l > - входной токен, поступающий на вход X р-узла (в память ХМ); YM - память другого входа данного узла;

a°b - операция сравнения значений переменной в токенах а и Ь. Результатом операции является один или несколько выходных токенов TKNout =<TKNin , TKNmt>, TKNmt e ХМ, где TKNMT - найденный токен из памяти YM, удовлетворяющий условию сопоставления. Если тэг входного токена TG^ положительный, в р-узле выполняется операция добавления токена к памяти ХМ:

ADD (ХМ, TKNin): ХМ = Ж и {TKNin}.

Если тэг отрицательный, то выполняется удаление токена из памяти ХМ: DEL (ХМ, TKN/n): ХМ = ХМ \ {TKN,n}.

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

вычисляется по формуле ¡tkn = tconst + ta +ns +tr, где tcomt - время обработки констант; ta- время обработки а-узла; tp- время обработки Р-узла; tT- время обработки терминального узла; ns - количество слоев Р-подсети. Время обработки Р-узла определяет временную сложность алгоритма в целом.

Для представления RETE-сети в памяти ФОП в работе разработаны эффективные форматы указателей, подсети констант и слов а-, Р и у-памяти. Служебная информация (конец списка, число входов узла и т.п.) располагается в одном слове с указателем, что исключает дополнительные затраты на ее чтение и хранение. Общий формат сети включает дескриптор, определяющий параметры настройки ФОП на конкретную БЗ (длина сети, адрес массива у-узлов, тип неопределенности, и пр.).

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

В соответствии с принятым подходом к организации ФОП, RETE-сеть представлена в виде структуры, загружаемой в его ОЗУ. Базовая архитектура ФОП, по-

Рисунок 3 - Базовая архитектура ФОП

казанная на рис. 3, содержит аппаратный стек для реализации обхода сета в глубину, модуль сопоставления, используемый при обработке Р-узлов, и блок управления, реализующий интерпретатор 1*ЕТЕ-сети на микропрограммном уровне в терминах сигналов управления устройствами ФОП. Т.о., исключены этапы выборки и дешифрации команд, обычно имеющие место в процессорах. Ряд модулей разработан для вариантов четких и нечетких значений предикатов правил.

Поступление токена во входную очередь запускает обработку, в процессе которой производятся изменения в памяти узлов ИЕТЕ-сети. В результате номер активируемой продукции, если таковая имеется, поступает в выходную очередь вместе с набором объектов, удовлетворяющих ее условию. Цикл работы аппаратного интерпретатора включает выборку очередного слова из памяти во входной регистр (либо запись слова), сопоставление его с текущим токеном, если это слово р-памяти, вычисление адреса следующего слова. Сопоставление выполняется параллельно с вычислением и выдачей следующего адреса. Таким образом, одноступенчатый конвейер обеспечивает почти полную загрузку канала обмена с памятью (8090%), и дальнейшее дробление конвейера при данной организации памяти БЗ нецелесообразно. Память узлов располагается непосредственно в структуре ЯЕТЕ-сети вместе с указателями на последующие узлы, поэтому обращение к ней не требует отдельных операций адресной арифметики.

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

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

(1): 1 хХ(1,1) + 2хХ(2,1) +...+ КхХ(М,1) = N

(2): 1 хХ(1,2) + 2хХ(2,2) +...+КхХ(ИД)=Х(1,1)+Х(2,1) +... + Х(К,1)

(М): 1хХ(1М)+2хХ(2М^- ..-МхХ(ЫМ)=Х(1№-1)+Х(2М-1)<-- ..+Х(Ы№-1)

(М+1): Х(1 ,М) + Х(2,М) +... + Х(М,М) = 1

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

л-1 ( *-1 Л

£ («-/»)£

Г„(и) = 19и-7 + 2!^-—-—, л £ 2 .

Для каждого слоя р-подсети суммарная цена равна: = Т(2)хХ(2,1) + Т(3)хХ(3,1) +...+ Т(Ы)хХ(И,1),

Б2 = Т(2)хХ(2,2) + Т(3)хХ(3,2) +...+ Т(Ы)хХ(И,2),

БМ = Т(2)хХ(2,М) + Т(3)хХ(3,М) +...+ Т(Ы)хХ(И,Щ.

Тогда задача минимизации общей суммарной цены, т.е. значения функции 5=57 + 52 +... + отИхМ переменныхХ(1,1),..,,Х(1Я,М) является задачей целочисленного линейного программирования. Ее решение позволяет найти оптимальную по критерию времени обработки структуру Р-подсети для любого числа входов.

Еще одна возможность оптимизации КЕТЕ-сети заключается в склеивании Р-узлов из разных продукций, выполняющих сопоставление одних и тех же подмножеств УЭ. Нахождение оптимальных склеиваний требует в общем случае пол- », ного перебора и является ЫР-полной задачей. Для предложенной формы КЕТЕ-сети разработан способ склеивания, основанный на представлении продукций в виде строк двоичной матрицы, названной матрицей вхождений. С применением побитовых операций по транспонированной матрице вхождений находятся все непустые пересечения подмножеств УЭ за С2Н итераций, в то время как нахождение пересечений классическим методом потребовало бы экспоненциальной сложности. Найденные пересечения выбираются в порядке убывания степени и ранга (числа входов). При этом модификация матрицы позволяет отслеживать зависимые пересечения, понижать их ранг или исключать из рассмотрения.

На основе предложенных методов разработан и реализован алгоритм построения оптимальной КЕТЕ-сети. Экспериментально подтверждена его квадратичная временная сложность. Например, для количества входов сети порядка 100 на платформе РШ-700 он выполняется не более чем за 40 мс. (рис. 4). Такая невысокая и, что очень важно, предсказуемая сложность позволяет использовать данный алгоритм в системах с динамическим формированием БЗ.

х 100 ---

И 80...................................•

I §

во- - - ..... - - .

¡¡40.................................У^- '^ -

« с 20 - - * » ♦ .. I

Ш 0 -I................ЛИ* ♦♦ •,—. ■ , —-,-,-

О 20 40 60 80 100 120

ИА, Количество входов сети (всего пар атрибут-значение)

Рисунок 4 - Время компиляции КЕТЕ-сети На рис. 5 отражены результаты экспериментального сравнения производительности ФОП при использовании одного метода оптимизации и обоих методов одновременно по сравнению с неоптимизированной КЕТЕ-сетью. Подтверждается теоретический расчет 18%-го прироста при использовании многовходовых р-узлов, а суммарный выигрыш в производительности с ростом объема БЗ стремится к ве- /«

личине порядка 40%. Кроме того, оба метода позволяют сократить объем памяти БЗ.

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

.....' ' - *

........................ • •_,_

l*. о s x z

I- л -я и ц я

Hi

а 5 S = 8 Ё 5 о

и

У _«- -

60 -50 j 40 30

20 - ||f1|">ii Г1 if ""jf"""" * *

10

Mi i i 1 Л Ж

7- ' :

О 1000 2000 3000 4000 5000

_вРЯ, Суммарное количество УЭ всех продукций

- Погная оптимизация * Оптимизация по числу входов узлов

6000

Рисунок 5 - Сравнение производительности при использовании оптимизации

ван на использовании инструментальной среды проектирования и включает решение задач: определения подмножества БЗ в архитектуре НА, для которых разрабатываются средства аппаратной поддержки; преобразования правил к унифицированному виду; определения дополнительных аппаратных модулей для обработки неопределенных знаний и вспомогательных вычислительных алгоритмов; уточнения масштабируемых параметров базовой архитектуры; описания полной спецификации ФОП на HDL-языке (VHDL, Verilog); расчета параметров, влияющих на оптимальное число входов (J-узлов; реализации алгоритма компиляции БЗ заданного типа в оптимальную RETE-сеть в формат ФОП.

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

ФОП с предложенной архитектурой был реализован на базе ПЛИС Altera АСЕХ 1К100. Ядро ФОП реализовано на VHDL с помощью пакета FPGA Advantage. В качестве основного сравниваемого варианта выбрана реализация ПБЗ в среде CLIPS, широко используемой для построения ИА РВ. С целью повышения достоверности экспериментальных оценок был написан программный интерпретатор RETE-сети на С++, функционально аналогичный ФОП. В CLIPS введен ряд средств, позволяющих точно измерить время этапа сопоставления фактов. Результаты сравнения производительности получены на основании измерений по 400 сгенерированным БЗ различного объема. Методика оценки включает ряд способов минимизации влияния побочных эффектов на точность измерений для программ-*г ных реализаций (пятикратное повторение измерений с выбором лучшего результа-

та, повтор эксперимента на разных ПЭВМ, и т.п.). 1 Для взаимодействия с хост-машиной и экспериментальной оценки произво-

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

С точки зрения достоверности, важным результатом является то, что с ростом объема БЗ время обработки разными программными интерпретаторами приближается к одной и той же величине (рис. 6), что говорит об их одинаковой вы-

числительной сложности. Другим важным результатом является то, что время обработки одного токена и всей КЕТЕ-сети в целом является предсказуемой величиной и практически линейно зависит от параметров БЗ (рис. 7). Это позволяет агенту планировать время обработки в соответствии с текущим состоянием.

О 1000 2000 3000 4000 5000 6000 _SPN, Суммарное количество УЭ всех продукций

- По сравнению с CLIPS

• По сравнению с низкоуровневым программным интерпретатором Рисунок 6 - Выигрыш в производительности

S00

О 20 40 60 80 100 120 140

Р, Количество продукций

• Реальные значения — Приближенная линейная зависимость | Рисунок 7 - Время обработки токена

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

1. Виртуальная машина обработки КЕТЕ-сетей, представляющая собой совокупность абстрактных элементов данных и укрупненных операций над ними. Виртуальная машина позволяет систематизировать процесс проектирования ФОП.

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

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

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

5. Метод и алгоритм быстрой компиляции БЗ в модифицированную RETE-сеть с учетом склеивания Р-узлов, отличающийся использованием матричных и побитовых преобразований над антецедентами правил. Метод исключает комбинаторный перебор конфигураций сети и обеспечивает предсказуемое время ее построения с алгоритмической сложностью 0(N2). Это дает возможность использовать ФОП в системах с динамическим формированием ПБЗ.

6. Методика проектирования ФОП аппаратной поддержки ПС на основе RETE-сети, базирующаяся на представлении ядра в виде VHDL-библиотеки мега-функций, что обеспечивает переносимость и масштабируемость. Уточнен состав инструментальной среды проектирования, позволяющей автоматизировать процесс проектирования устройств данного класса.

7. Пакет VHDL-модулей масштабируемого ядра ФОП обработки ПБЗ на основе RETE-сети. Данный пакет позволяет проектировать подобные ФОП с учетом различных требований и ограничений по параметрам обрабатываемых БЗ, таких как максимальное число объектов, максимальная глубина RETE-сети, ширина входного токена, и т.п.

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

9. Программное обеспечение экспериментального комплекса, включающее: генераторы БЗ и БД, программный интерпретатор RETE-сети, компилятор БЗ в оптимизированную RETE-сеть, конверторы форматов (в том числе в CLIPS), программы взаимодействия с ФОП со сбором статистики, тестовые, и другие вспомогательные модули. Разработанное ПО позволяет отладить спроектированный ФОП и собрать статистику для экспериментальной оценки его эффективности. Оно также может использоваться как часть инструментальной среды проектирования.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Методы и средства построения интеллектуальных агентов реального времени / В.В. Денисов. Г.Г. Колосов, М.Г. Пантелеев, Д.В Пузанков // Труды 7-й нац. конф. по искусств, интеллекту с междунар. уч. КИИ"2000, г. Переславль-Залесский.

- М.: Изд-во Фи з.-ма г. лит., 2000. - Т.2. - С. 805-813.

2. Пантелеев M.I. Организация и проектирование средств аппаратной поддержки ишеллектуальных агенюв / М.Г. Пантелеев, В.В. Денисов, Г.Г. Колосов // Интеллектуальные системы (INTELS'2000): Труды 4-го междунар. симп. - М.: РУСАКИ, 2000. - С. 188-190.

3 Пантелеев М.Г". Процессоры аппаратной поддержки интеллектуальных агентов реального времени' разработка и реализация / М.Г. Пантелеев, В. В. Денисов. Г.Г. Колосов // Труды IV Междунар. конф. по мягким вычислениям и измерениям SCM'01. - СПб: СПбГЭТУ, 2001. - Т. 2. - С. 119-123.

4. Процессоры аппаратной поддержки интеллектуальных агентов реального времени: организация, проектирование, реализация / В.В. Денисов, Г.Г. Колосов, M Г. Пантелеев, Д.В. Пузанков // Труды междунар. конгресса Искусственный Интеллект в XXI веке 1САГ01. - М.: Изд-во Физ.-мат. лит., 2001. - С. 273-280.

5. Пантелеев M.I Архитектура процессора логического вывода для продукционных БЗ на основе RETE-сети / М.Г. Пашелеев, Г.Г Колосов // Изв. СПбГЭТУ "ЛЭТИ",- СПб.: Изд-во СПбГ'Э ГУ, 2002г. - Вып. 2. - С. 35-43.

6 Проектирование и реализация процессоров аппаратной поддержки интеллектуальных агентов реального времени / В.В. Денисов, Г.Г. Колосов. М.Г. Пантелеев, Д.В. Пузанков // Материалы междунар. науч.-техн. конф «СуперЭВМ и многопроцессорные вычислительные системы (MCS'2002). - Таганрог: Изд-во ТРТУ, 2002.-С. 216-220.

7. Проектирование и реализация средств аппаратной поддержки интеллектуальных агентов реального времени / Д.В. Пузанков, М.Г. Пантелеев, Г.Г. Колосов, И.Б. Говорухин // Труды междунар. конф. «Искусственные интеллектуальные системы» (IEEE ICAIS'02) и «Интеллектуальные САПР» (CAD-2002). - М.: Изд-во Физ.-мат. лит., 2002. - С. 236-243.

8. Design and Implementation of Hardwaic foi Real-Tiine Intelligent Agentb (Проектирование и реализация средств аппаратной поддержки интеллектуальных агентов реального времени) / M.G. Panteleev, D.V. Puzankov, G.G. Kolosov, I.B. Govorukhin. // Proceedings of 2002 IEEE Intl. Conference on Artificial Intelligence Systems (ICA1S 2002). - California, 2002. - P. 6-11.

9. Колосов Г. Г". Процессор аппаратной поддержки продукционных систем на основе RETE-сети / Г.Г. Колосов // Труды 5-го междунар. симп. «Интеллектуальные системы» (INTELS,2002). - M.: МГТУ им. Н. Э. Баумана, 2002.

- С. 306-308.

10. Организация и проектирование функционально-ориентированных процессоров аппаратной поддержки продукционных баз знаний / Д.В. Пузанков, М.Г Пантелеев, В.В. Денисов, Г.Г. Колосов // Изв. ВУЗов. Приборостроение. -СПб., 2003. - Т.46. №2. - С. 18-23.

11 Пантелеев М.Г Проектирование процессоров обработки продукционных баз ¡наний на основе RETL-ce i и / М.Г. Пантелеев, Г.Г. Колосов // Материалы меж-

дунар. науч.-техн. конф. «Интеллектуальные и многопроцессорные системы» ИМС'2003. - Таганрог: Над-во ТРТУ, 2003. - Т.2. - С. 102-105.

12. Пантелеев М.Г. Проектирование процессоров обработки продукционных баз знаний на основе ЯКТЕ-сети / М.Г. Пантелеев, Г.Г. Колосов // Искусственный интеллект. - 2003. - №3. - С. 465-173.

13. Пантелеев М.Г. Виртуальная машина интерпретатора ЯЕТЕ-сетей в задачах проектирования функционально-ориентированных процессоров / М.Г. Пантелеев, Г.Г. Колосов // Материалы 5-й междунар. науч.-техн. конф. - Таганрог: Изд-во ТРТУ. 2004. - Т. 1. - С. 292-296.

14. Пантелеев М.Г. Виртуальная машина интерпретатора ЯЕТЕ-сетей в задачах проектирования функционально-ориентированных процессоров / М.Г. Пантелеев, Г.Г. Колосов // Искусственный интеллект. - 2004. - №4. - С. 726-732.

15. А. с. 25951 РФ, МКИ в 06Р 7/00. Функционально-ориентированный процессор обработки продукционных знаний / М.Г. Пантелеев, В.В. Денисов, Г.Г. Колосов (РФ). - № 2002115379/20; заявл. 11.06.02; опубл. 27.10.02, Бюл. № 30. - 3 е.: ил.

Подписано в печать 06.09.05. Формат 60*84 1/16. Бумага офсетная. Печать офсетная. Печ. л. 1,0. Тираж 100 экз. Заказ 73.

Отпечатано с готового оригинал-макета в типографии Издательства СПбГЭТУ "ЛЭТИ"

Издательство СПбГЭТУ "ЛЭТИ" 197376, С.-Петербург, ул. Проф. Попова, 5

Р176 94

РНБ Русский фонд

2006:4 16819

Перечень сокращений и специальных терминов.

Введение.

1 Обзор архитектур и средств аппаратной поддержки ИА.

1.1 Продукционная модель представления знаний.

1.1.1 Общие сведения.

1.1.2 RETE-сеть и ее модификации.

1.1.3 Представление и обработка неопределенных знаний в ПС.

1.2 Интеллектуальные агенты.

1.2.1 Понятие ИА реального времени.

1.2.2 Архитектуры интеллектуальных агентов.

1.2.3 Место ПС в ИА РВ.

1.3 Анализ подходов к аппаратной поддержке ПС.

1.3.1 Процессоры с расширенной системой команд.

1.3.2 Многопроцессорные архитектуры.

1.3.3 Мультипроцессорные архитектуры с программируемой структурой.

1.3.4 Функционально-ориентированные сопроцессоры.

1.3.5 Нейросетевые (коннекционистские) реализации.

1.4 Универсальный интерпретатор ПС.

1.5 Выводы.

2 Организация MJIB на основе RETE-сети.

2.1 Виртуальная машина вывода для обработки продукционных систем на базе RETE-сети.

2.2 Анализ способов представления RETE-сети в памяти ФОП.

2.2.1 Статические структуры данных в классическом способе представления RETE-сети.

2.2.2 Модифицированная структура RETE-сети.

2.2.3 RETE-сеть в ПС с объектами одного класса.

2.2.4 Разработка форматов внутреннего представления RETE-сети.

2.3 Выводы.

3 Проектирование ФОП аппаратной поддержки ПС на основе RETE-сети.

3.1 Анализ архитектурных решений ФОП.

3.2 Методы оптимизации RETE-сети.

3.2.1 Обоснование подхода к оптимизации.

3.2.2 Постановка задачи оптимизации RETE-сети.

3.2.3 Метод оптимизации на основе склеивания и алгоритм компиляции RETE-сети.

3.3 Уточнение алгоритма интерпретатора.

3.4 Методика проектирования ФОП.

3.5 Выводы.

4 Реализация ФОП на БИС программируемой логики и экспериментальное исследование.

4.1 ПЛИС как элементная база для реализации ФОП аппаратной поддержки ИА РВ.

4.2 Проектирование процессора на языке VHDL.

4.3 Реализация ФОП на основе макетной платы.

4.4 Методика проведения эксперимента.

4.5 Программное обеспечение экспериментального образца ФОП.

4.6 Проведение и результаты эксперимента.

4.7 Выводы.

Актуальность темы. Системы искусственного интеллекта (СИИ) находят в последние годы все более широкое применение в самых различных областях: медицина, авиационная и космическая техника, бытовая техника, робототехника, системы управления предприятиями, социально-аналитические системы, интернет-приложения и так далее [1,2]. Современный этап развития СИИ связан с разработкой теории, методов и средств построения интеллектуальных агентов (ИА) - нового класса СИИ, способных к автономному целенаправленному функционированию в открытых, динамических и неопределенных средах [57, 59]. В частности, концепция ИА все шире используется в приложениях реального времени (РВ), включая бортовые и встраиваемые системы [95, 104, 106].

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

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

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

Существующие подходы к аппаратной поддержке ПС, такие как системы массового параллелизма [125-153], расширения набора команд стандартных микроконтроллеров [167-169] и процессоры поддержки высокоуровневых языков [172-177] по разным причинам не применимы или не обеспечивают требуемой эффективности в бортовых и встраиваемых приложениях ИА РВ [170, 178]. Наиболее важными из этих причин являются недостаточная гибкость и функциональность, а также существенные аппаратные затраты при увеличении объемов баз знаний. Эффективным подходом к реализации средств аппаратной поддержки для таких приложений являются ФОП обработки продукционных знаний, построенные по принципу универсального интерпретатора продукционных систем (УИ ПС) [68, 170, 171]. Данный принцип позволяет обрабатывать любые ПС в рамках заданных ограничений на форму представления знаний. Таким образом, ФОП может использоваться для обработки ПБЗ разных подсистем агента. Концепция УИ ПС была предложена и доказана ее эффективность для списочной формы представления продукционных знаний и деревьев решений.

Эффективной, с точки зрения вычислительных затрат, формой представления продукционных баз знаний является RETE-сеть [16] и ее модификации [18-20, 32, 35, 40-42], представляющие собой графы потока данных специального вида, позволяющие исключить из процесса логического вывода алгоритмическую избыточность. RETE-сеть уже более 20 лет активно используется в большинстве программных платформ с продукционным выводом. В том числе, такие широко известные платформы построения ИА, как CLIPS [21-23] и JESS [24] также используют RETE-сеть для внутреннего представления знаний. При этом CLIPS специально разработан и позиционируется NASA как платформа для бортовых систем реального времени.

Прогресс технологии ПЛИС создал предпосылки к реализации высокопроизводительных ФОП обработки знаний в габаритах типовых плат расширения, подключаемых к стандартным магистралям современных бортовых или настольных ЭВМ. Как показывает анализ, такой подход наиболее целесообразен для бортовых и встраиваемых систем [188-199]. Таким образом, разработка подобных ФОП аппаратной поддержки RETE-сетей является актуальной на сегодняшний день научной задачей. Стремительное развитие систем на кристалле в настоящее время обуславливает перспективность данного подхода для встроенных систем, создавая дополнительные возможности повышения функциональности и производительности ФОП за счет уменьшения затрат на взаимодействие с ядром основного процессора и возможности оперативной реконфигурации.

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

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

1. Анализ известных подходов к построению средств аппаратной поддержки ПС на основе RETE-сетей с точки зрения эффективности их использования при построении ИА РВ.

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

3. Анализ и разработка эффективных с точки зрения аппаратной реализации способов внутреннего представления и методов оптимизации RETE-сети;

4. Разработка базовых архитектур и методики проектирования ФОП аппаратной поддержки ПС на основе RETE-сети;

5. Разработка методов и алгоритмов эффективной компиляции исходных ПБЗ в форматы внутреннего представления оптимизированной RETE-сети;

6. Разработка методики и экспериментальная оценка производительности ФОП с использованием макетного образца.

Предмет и методы исследования

Предметом исследования являются способы представления и обработки ПБЗ на основе RETE-сети и принципы организации ФОП аппаратной поддержки алгоритмов логического вывода для ПС на базе RETE-сетей. Методами исследования являются целочисленное линейное программирование; методы оптимизации; элементы теории автоматов; методы алгоритмизации и программирования на языках С++, Fortran; методы проектирования аппаратуры на базе БИС программируемой логики с использованием языков описания дискретных устройств (VHDL).

Научную новизну работы составляют:

1. Модификации RETE-сети, ориентированные на аппаратную реализацию продукционных систем и отличающиеся от известных использованием статических структур данных, что позволяет при незначительном росте объема памяти базы знаний существенно упростить архитектуру и повысить производительность ФОП.

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

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

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

Практическая значимость работы заключается в следующем:

1. Разработан пакет VHDL-модулей масштабируемого ядра ФОП обработки продукционных БЗ на основе RETE-сети, позволяющий проектировать подобные устройства с учетом различных форм неопределенности и требований по параметрам обрабатываемых баз знаний, таких как максимальное число объектов, глубина RETE-сети, ширина входного токена, и т.п.

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

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

4. Написан ряд программных модулей для взаимодействия ФОП с базовой машиной и проведения экспериментальной оценки его производительности. Разработанные модули могут в дальнейшем использоваться в составе инструментальной среды проектирования устройств подобного класса.

5. На основе созданного аппаратно-программного комплекса проведено экспериментальное исследование и установлено, что выигрыш ФОП в производительности по сравнению с процессорами общего назначения составляет от 10 до 40 раз в зависимости от характеристик БЗ и БД. При оценке использовалось два разных подхода к организации программных интерпретаторов: стандартная платформа CLIPS, используемая для построения ИА, и низкоуровневый программный интерпретатор.

Достоверность результатов исследования.

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

Для экспериментальной оценки производительности ФОП в качестве основного сравниваемого варианта выбрана реализация в среде CLIPS, так как она наиболее широко используется для построения ИА РВ. С целью повышения достоверности экспериментальных оценок был также написан программный интерпретатор RETE-сети на С++, функционально аналогичный ФОП. В CLIPS был введен ряд средств, позволяющих точно измерить время этапа сопоставления фактов. Оценка программных платформ производилась дважды с использованием разных базовых вычислительных платформ (Pentium Ш-700МГц и Pentium IV-ЗГГц). Результаты сравнения производительности получены на основании измерений по 400 сгенерированным БЗ различного объема. Предложенная в работе методика оценки производительности включает ряд способов минимизации влияния побочных эффектов на точность измерений. Достоверность результатов измерений времени обработки БЗ программными интерпретаторами подтверждается приблизительным равенством результатов для БЗ большого объема. Измерения времени обработки тестовых БЗ в ФОП проводились с использованием счетчика тактов, специально введенного для этой цели в его структуру.

Внедрение результатов.

Теоретические и практические результаты диссертационной работы, полученные в ходе выполнения НИР 5937/ВТ-210, внедрены на предприятии ФГУП Н1111 «Рубин» при разработке принципов построения экспертных систем реального времени и средств их аппаратной поддержки для автоматизированных систем оценки и прогнозирования воздушной обстановки.

Работа также поддержана:

1. Грантом Министерства образования - "Организация и проектирование процессоров аппаратной поддержки объектно-продукционных моделей представления и обработки знаний для интеллектуальных агентов реального времени"/ НИР ВТ-39/ГТАТ, проект ТОО-3.3-2672, научный руководитель Пантелеев М.Г.

2. Персональным грантом СПбГЭТУ для студентов и аспирантов ЭТУ за 2001г.

3. Персональным грантом - «Разработка архитектур и методов проектирования функционально-ориентированных процессоров логического вывода для продукционных баз знаний на основе RETE-сети» по конкурсу проектов аспирантов и докторантов по разделу III Темплана Минобразования 2002г.

Апробация результатов исследования. Основные положения и результаты работы докладывались и обсуждались на научно-технических конференциях СПбГЭТУ в 2001-2003 гг., а также на следующих конференциях: седьмая национальная конференция по искусственному интеллекту с международным участием «КИИ'2000», Переславль-Залесский, 2000 г.; четвертый и пятый международные симпозиумы «Интеллектуальные системы» ИНТЕЛС, Москва, 2000г., Калуга, 2002 г.; четвертая международная конференция по мягким вычислениям и измерениям SCM'2001, Санкт-Петербург, 2001 г.; международный конгресс «Искусственный интеллект в XXI веке» 1САГ2001, Двиноморское, 2001 г.; международная научно-техническая конференция «СуперЭВМ и многопроцессорные вычислительные системы» MCS'2002, Таганрог, 2002 г.; международная конференция «Искусственные интеллектуальные системы» IEEE ICAIS'2002, Двиноморское, 2002 г.; четвертая и пятая международные научно-техническая конференция «Искусственный интеллект. Интеллектуальные и многопроцессорные системы» ИМС, Двиноморское, 2003 и 2004 г.

Публикации. По теме диссертации опубликовано 15 научных работ, в том числе 4 статьи в журналах, 10 тезисов докладов на международных научно-технических конференциях, 1 авторское свидетельство на полезную модель.

Структура и объем работы.

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

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

Полученные результаты позволяют перейти к проектированию ФОП обработки продукционных знаний на основе RETE-сети на базе единого научно обоснованного подхода.

Перспективными направлениями развития данной работы являются:

• развитие и оптимизация предложенной архитектуры ФОП с целью повышения степени параллелизма и/или тактовой частоты;

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

• анализ и решение задач проектирования многоядерной архитектуры ФОП для параллельной обработки токенов, Р-узлов и/или связанных баз знаний;

• анализ и разработка методики проектирования подобных ФОП в составе систем на кристалле с учетом особенностей применения SOPC и взаимодействия встроенного программного обеспечения с ФОП.

Заключение

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

1. Виртуальная машина обработки RETE-сетей, представляющая собой совокупность абстрактных элементов данных и укрупненных операций над ними. Виртуальная машина позволяет систематизировать процесс проектирования ФОП.

2. Модифицированная форма RETE-сети, ориентированная на использование статических структур данных, и позволяющая при незначительном увеличении объема занимаемой БЗ памяти существенно упростить архитектуру ФОП и повысить его производительность. На основе данной формы разработан эффективный формат внутреннего представления RETE-сети в памяти ФОП для случаев четких и нечетких значений предикатов, а также различной разрядности памяти.

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

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

5. Метод и алгоритм быстрой компиляции БЗ в модифицированную RETE-сеть с учетом склеивания р-узлов, отличающийся использованием матричных и побитовых преобразований над антецедентами правил. Метод позволяет исключить комбинаторный перебор конфигураций сети и обеспечивает предсказуемое время ее построения с алгоритмической сложностью 0(N ). Это дает возможность использовать данный метод в системах с динамическим формированием продукционных баз знаний.

6. Методика проектирования ФОП аппаратной поддержки ПС на основе RETE-сети, базирующаяся на представлении ядра в виде VHDL-библиотеки мегафункций, что обеспечивает переносимость и масштабируемость. Уточнен состав инструментальной среды проектирования, позволяющей автоматизировать процесс проектирования устройств данного класса.

7. Пакет VHDL-модулей масштабируемого ядра ФОП обработки продукционных БЗ на основе RETE-сети. Данный пакет позволяет проектировать подобные ФОП с учетом различных требований и ограничений по параметрам обрабатываемых БЗ, таких как максимальное число объектов, максимальная глубина RETE-сети, ширина входного токена, и т.п.

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

9. Программное обеспечение экспериментального комплекса, включающее: генераторы БЗ и БД, программный интерпретатор RETE-сети, компилятор БЗ в оптимизированную RETE-сеть, конверторы форматов (в том числе в CLIPS), программы взаимодействия с ФОП со сбором статистики, тестовые, и другие вспомогательные модули. Разработанное ПО позволяет отладить спроектированный ФОП и собрать статистику для экспериментальной оценки его эффективности. Оно также может использоваться как часть инструментальной среды проектирования.

С использованием разработанного аппаратно-программного комплекса проведено экспериментальное исследование и установлено, что выигрыш ФОП в производительности по сравнению с процессорами общего назначения составляет от 10 до 40 раз в зависимости от характеристик БЗ и БД; предложенные методы оптимизации RETE-сети дают совокупный прирост производительности ФОП на 40-60%; подтверждена квадратичная сложность компилятора RETE-сети; предложенный подход к построению ФОП аппаратной поддержки продукционных баз знаний на основе RETE-сети позволяет получить предсказуемое время обработки, что имеет существенное значение для построения ИА реального времени.

1. Девятков, В.В. Системы искусственного интеллекта: Учеб. пособие для вузов / В.В. Девятков. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. - 352с., ил.

2. Осипов, Г.С. Искусственный интеллект: состояние исследований и взгляд в будущее электронный ресурс. — Режим доступа: http://www.raai.org/about/persons/osipov/pages/ai/ai.html.

3. Шеннон, К. Работы по теории информации и кибернетике / К. Шеннон. — М.: Иностранная литература, 1963.

4. Искусственный интеллект. В 3 кн. Кн. 1. Системы общения и экспертные системы: справочник / Под ред. Попова Э.В. — М.: Радио и связь, 1990. 464 с.

5. Искусственный интеллект. В 3 кн. Кн.2. Модели и методы: справочник / Под ред. Поспелова Д.А. М.: Радио и связь, 1990. — 304 с.

6. Искусственный интеллект. В 3-х кн. Кн.З. Программные и аппаратные средства: справочник / Под ред. Захарова В.Н., Хорошевского В.Ф. — М.: Радио и связь, 1990. -368 с.

7. Simon, Н. A. Models of Bounded Rationality / Herbert Simon. Cambridge MA: MIT Press, 1982.-Vol 2.

8. Hanson, E. N. An overview of production rules in database systems / E. N. Hanson, J. Widom // Knowledge Eng. Review. 1993. - V.8, No 2. - P. 121-143.

9. Ishida, T. An Organizational Approach to Adaptive Production Systems / T. Ishida, M. Yokoo, L. Gasser // National Conference on Artificial Intelligence (AAAI-90). — 1990.-P. 52-58.

10. Forgy, C. L. OPS5 User's Manual: Technical Report CMU-CS-81-135. Pittsburgh PA: Carnegie Mellon University press, 1981.

11. Пантелеев, M. Г. Модели и средства построения экспертных систем: Учебное пособие / М. Г. Пантелеев, С. В. Родионов СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2003. -72 с.

12. Quinlan, J. R. С4.5: Programs for Machine learning / J. Ross Quinlan. Morgan Kaufmann Publishers, 1993.

13. Murthy, S. Automatic Construction of Decision Trees from Data: A Multi- disciplinary Survey / S. Muthy // Data Mining and Knowledge Discovery. 1998. — No 2. — P. 345-389.

14. Buntine, W.A. Theory of Learning Classification Rules Text. : PhD thesis : School of Computing Science, University of Technology / W.A. Buntine. Sydney, 1990.

15. Айвазян, С. А. Прикладная статистика и основы эконометрики / С. А. Айвазян, В. С. Мхитарян. М.: Юнити, 1998.

16. Forgy, С. L. RETE: A fast algorithm for the many pattern/many object pattern match problem / C. L. Forgy // Artificial Intelligence. 1982. - V. 19, No 1. - P. 17-37.

17. Tambe, M. The problem of expensive chunks and its solution by restricting expressiveness / M. Tambe, A. Newell, P. S. Rosenbloom // Machine Learning. — 1990. — Vol. 5, No. 3. P. 299-348.

18. Tambe, M. Uni-Rete: Specializing the Rete match algorithm for the unique-attribute representation : Technical Report CMU-CS-91-180 / M. Tambe, D. Kalp, P. S. Rosenbloom ; School of Computer Science, Carnegie Mellon University. 1991.

19. Meszaros, T. An Extension to the RETE Match Algorithm: Supporting both Forward and Backward Chaining / T. Meszaros // TEMPUS JEP3815 Workshop, Budapest, Hungary. 1994. - P. 13-17.

20. Perlin, M. Topologically Traversing the Rete Network / M. Perlin // Applied Artificial Intelligence. 1990. - V. 4, No3. - P. 155-177.

21. CLIPS User's Guide. Version 6.20, March 31st 2002 Electronic resource. / by Joseph C. Giarratano. 2002. - Режим доступа: http://www.ghg.net/clips /download/ docu-mentation/usrguide.pdf.

22. CLIPS Architecture Manual. Version 5.1, January 6th 1992 Electronic resource. 1992.— Режим доступа: http://www.ghg.net/clips/download/documentation/arch5-l.pdf

23. CLIPS Reference Manual. Vol. II. Advanced Programming Guide. Version 6.21, June 15th 2003 Electronic resource. 2003. - Режим доступа: http://www.ghg.net/clips/download/documentation/apg.pdf

24. Friedman-Hill, J. JESS: The Rule Engine for the Java Platform. SAND98-8206 (revised). Version 7.0.1, 17 September 2004. / J. Ernst Friedman-Hill. 2004.

25. Nayak, P. Comparison of the RETE and TREAT production matchers for SOAR: A summary / P. Nayak, A. Gupta, P. Rosenbloom // In Proceedings of National Conference on Artificial Intelligence (AAAI'88). 1988. - P. 693-698.

26. Wang, Y. W. A performance comparison of the RETE and TREAT algorithms for testing database rule conditions. Technical Reportrt WSU-CS-90-18. / Y. W. Wang, E. N. Hanson ; Dept. of Computer Science and Engineering, Wright State University. 1990.

27. Doorenbos, R. В. Production Matching for Large Learning Systems : Technical Report TR CMU-CS-95-113. / R. B. Doorenbos ; Carnegie Mellon University. January 31,1995.

28. Tambe, M. Investigating production system representations for non-combinatorial match / M. Tambe, P. S. Rosenbloom // Artificial Intelligence. 1994. - V. 68, No 1. - P. 155-199.

29. Match Algorithm for a Real Time Expert System / T. S. Perraju, G. Uma, В. E. Prasad, S. P. Rana // In Proceedings of the 7th International Conference on Database and Expert Systems Applications (DEXA 96). 1996.

30. Lee, P. Y. Optimizing Real-Time Equational Rule-Based Systems / P. Y. Lee., A. M. K. Cheng // IEEE Transactions on Software Engineering. Feb 2004. - Vol. 30, No. 2. -P. 112-125.

31. Acharya, A. Collection-oriented match: Scaling up the data in production systems. Technical Report CMU-CS-92-218 / A. Acharya, M. Tambe ; Carnegie-Mellon University. -Pittsburgh, December 1992.

32. Bouaud, J. TREE: A heuristic driven join strategy of a RETE-like pattern-matcher for a SOAR-like production system. Technical Report DIAM Rapport Interne RI-92-109, INSERM U194 / J. Bouaud; Department intelligence Artificielle et Medecine. 1992.

33. XC A Language for Embedded Rule Based Systems / E. Nuutila et al. // SIG-PLAN Notices. - 1987. - Vol. 22, No. 9. - P. 23-32.

34. Obermeyer, L. Evaluating Triggers Using Decision Trees / L. Obermeyer, D. P. Miranker // Proceedings of the sixth international conference on Information and knowledge management. — Las Vegas, November 1997. P. 144-150.

35. Miranker, D. P. TREAT: A better match algorithm for AI production systems / D. P. Miranker // In Proceedings of the Sixth National Conference on Artificial Intelligence (AAAI-87). August 1987. - P. 42-47.

36. Miranker, D. P. TREAT: A New and Efficient Match Algorithm for AI Production Systems / D. P. Miranker. Morgan Kaufmann Publishers, 1990. - 143 p. - ISBN 0934613-71-0.

37. On a Treat based production system compiler / D. P. Miranker, B. J. Lofaso, G. Farmer, A. Chandra, D. Brant // In Proceedings of 10th International Conference on Expert Systems. Avignon, France, June 1990. - P. 617-630.

38. Miranker, D. P. The organization and performance of a TREAT-based production system compiler / D. P. Miranker, B. J. Lofaso // IEEE Transactions on Knowledge and Data Engineering. March 1991. -Vol. 3, No. 1. - P. 3-10.

39. Kelly, M.A. An evaluation of DRETE on CUPID for OPS5 matching / M. A. Kelly, R. E. Seviora // In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89). Detroit MI, August 1989. - P. 84-90.

40. R++: Adding a Path-Based Rules to С++ / D. Litman, P.F. Patel-Schneider, A. Mishra, J. Crawford, D. Dvorak / IEEE Transactions on knowledge and Data Engineering. — May/June 2000. Vol. 14, No. 3. - P. 638-658.

41. Reasoning about Rete++ : White paper electronic resource. / Haley Enterprise. -October 1999. — Режим доступа: http://www.haley.com.

42. Batory, D. The LEAPS Algorithms : Technical Report 94-28 / D. Batory ; Department of Computer Sciences, University of Texas at Austin. — December 1994.

43. Effects of Database Size on Rule System Performance: Five Case Studies / D. A. Brant, T. Grose, B. Lofaso, D. P. Miranker // Proceedings of the 17th International Conference on Very Large Data Bases. 1991. - P. 287-296

44. On the Performance of Lazy Matching in Production Systems / D. P. Miranker, D. A. Brant, B. Lofaso, D. Gadbois // Proceedings of the 8th National Conference on Artificial Intelligence. AAAI Press, The MIT Press, 1990. - P. 685-692.

45. Brant, D. A. Index support for rule activation / D. A. Brant, D. P. Miranker // Proceedings of the 1993 ACM SIGMOD international conference on Management of data. — 1993. V. 22, No. 2. - P. 42-48.

46. Obermeyer, L. Selective Indexing Speeds Production Systems / L. Obermeyer, D. P. Miranker, D. A. Brant // Proceedings of the Seventh International Conference on Tools with Artificial Intelligence (КЛА1-95). 1995. - P. 416. - ISBN 0-8186-7312-5.

47. A New Approach to Modularity in Rule-Based Programming / J. C. Browne, A. Emerson, M. Gouda, D. P. Miranker // In Proceedings of the 6th International Conference on Tools with Artificial Intelligence. IEEE Press, 1994. - P. 18-25.

48. Venus: An objectoriented extension of rule-based programming : Technical report / D. P. Miranker, L. Obermeyer, L. Warshaw, and J. C. Browne ; University of Texas at Austin. -1998.

49. Hanson, E. Optimized trigger condition testing in Ariel using gator networks: Technical report TR97-021 / E. Hanson, S. Bodagala, U. Chadaga ; University of Florida, CISE Department. -1997.

50. Bassiliades, N. Processing Production Rules in DEVICE, an Active Knowledge Base System / N. Bassiliades, I. Vlahavas // Data & Knowledge Engineering. — 1997. Vol. 24, No. 2.-P. 117-155.

51. Bassiliades, N. DEVICE: Compiling production rules into event-driven rules using complex events / N. Bassiliades, I. Vlahavas // Information and Software Technology. — 1997. Vol. 39, No. 5. - P. 331-342.

52. Заде, JI. А. Понятие лингвистической переменной и его применение к принятию приближенных решений / Л. А. Заде. М.: Мир, 1976.

53. Нечеткие множества в моделях управления и искусственного интеллекта / А. Н. Аверкин, И. 3. Батыршин, А. Ф. Блишун, В. Б. Силов, В. Б. Тарасов ; под ред. Д.А. Поспелова. — М.: Наука, 1986. — 312 с.

54. Keller, J. М. Neural network implementation of fuzzy logic / J. M. Keller, R. R. Yager, H. Tahani // Fuzzy sets and systems. 1992. - Vol. 45, No .1, - P. 1-12.

55. Hardware solutions for fuzzy control / A. Costa et al. // Proceedings of the IEEE.- 1995. Vol. 83, No. 3. - P. 422-434.

56. Togai, M. VLSI implementation of a fuzzy-inference engine: toward an expert system on a chip / M. Togai, H. A. Watanabe // Information sciences. 1986. — Vol. 38, No 3.-P. 147-163.

57. Wooldridge, M. Intelligent Agents: Theory and Practice / M. Wooldridge, N. Jennings // The Knowledge Engineering Review. — 1995. — Vol. 10, No 2. P. 115-152.

58. Wooldridge, M. The control of reasoning in resource-bounded agents / M. Wooldridge // The Knowledge Engineering Review. 2001. - Vol. 16, No 3. - P. 215-240.

59. Тарасов, В. Б. Агенты, многоагентные системы, виртуальные сообщества: стратегическое направление в информатике и искусственном интеллекте / В. Б. Тарасов // Новости искусственного интеллекта. — 1998. №2. — С. 5-63.

60. Каляев, И. А. Распределенные системы планирования действий коллективных роботов / И. А. Каляев, А. Р. Гайдук, С. Г. Капустян. М.: Янус-К, 2002. - 292 с.

61. Coradeschi, S. A decision-mechanism for reactive and cooperating soccer-playing agents / S. Coradeschi, L. Karlsson // Workshop Notes of RoboCup Workshop, ICMAS-96.- Kyoto, Japan, 1996.

62. Cox, M. T. Goal Transformations in Continuous Planning / M. Т. Cox, M. M. Veloso // In Proceedings of the AAAI Fall Symposium on Distributed Continual Planning. -AAAI Press, October 1998. P. 23-30.

63. Mcllroy, D. Air combat tactics implementation in the Smart Whole AiR Mission Model (SWARMM) / D. Mcllroy, C. Heinze // In Proceedings of the First International SimTecT Conference. Melbourne, Australia, 1996. - P. 125-130.

64. Uckun S. A Control Architecture for Intelligent Mobile Robots : Technical Report KSL-93-09 / S. Uckun, B. Hayes-Roth ; Knowledge Systems Laboratory, Department of Computer Science, Stanford University. — January 1993.

65. Miraftabi, R. Agents on the Loose: An Overview of Agent Technologies / R. Miraftabi // The XIII Biennial Conference of the International Telecommunications Society (ITS). Buenos Aires, 2000.

66. Sahota, M. K. Reactive Deliberation: An Architecture for Real-time Intelligent Control in Dynamic Environments / M. K. Sahota // Appeared in AAAI-94. — 1994. P. 1303-1308.

67. Пантелеев, M. Г. Модели и методы построения интеллектуальных агентов реального времени / М. Г. Пантелеев // Материалы II Международной конференции по мягким вычислениям и измерениям. — СПб: СПбГЭТУ, 1999. — С. 114—117.

68. The HEARSAY-II speech understanding system: integrating knowledge to resolve uncertainty / L. Erman, B. Hayes-Roth, V. Lesser, D. Reddy / Computing Surveys. 1980. -Vol. 12, No. 2.-P. 213-253.

69. Corkill, D. D. Blackboard Systems / D. D. Corkill // Al Expert. September 1991. -Vol. 6, No. 9.-P. 40-47.

70. Hayes-Roth, B. Blackboard architecture for control / Barbara Hayes-Roth // Artificial Intelligence. -1985. No. 26. - P. 251-321.

71. Carver, N. A Revisionist View of Blackboard Systems / N Carver // Proceedings of the Midwest Artificial Intelligence and Cognitive Science Society Conference. May 1997.-P. 18-23.

72. Carver, N. The evolution of blackboard control architectures / N. Carver, V. Lesser // In Expert Systems with Applications: Special Issue on the Blackboard Paradigm and its Applications. -1994. Vol. 7, No. 1. - P. 1-30.

73. Laird, J. E. SOAR: An architecture for general intelligence / J. E. Laird, A. Newell, P. S. Rosenbloom // Artificial Intelligence. 1987. - Vol. 33, No 1. - P. 1-64.

74. Lewis, R. L. Cognitive Theory, SOAR. International Encyclopedia of the Social and Behavioral Sciences / R. L. Lewis ; Elsevier Science. Amsterdam: Pergamon, 2001.

75. Johnson, T. R. Control in Act-R and Soar // In Proceedings of the Nineteenth Annual Conference of the Cognitive Science Society. Lawrence-Erlbaum, 1997. - P. 343348.

76. Laird J. E., Congdon С. В., Coulter K. J. The Soar User's Manual. Version 8.2, Edition 1.-1999.

77. Soar: A Comparison with Rule-based Systems electronic resource. / Soar Technology. 2002. - Режим доступа: http://ai.eecs.umich.edu/soar/sitemaker/docs/ misc/SoarRBSComparison.pdf

78. Soar: A Functional Approach to General Intelligence electronic resource. / Soar Technology. 2002. — Режим доступа: http://ai.eecs.umich.edu/soar/sitemaker/ docs/misc/SoarFunctionalOverview.pdf

79. Scerri, P. Towards Adjustable Autonomy for the Real World / P. Scerri, D. V. Py-nadath, M. Tambe // Journal of Artificial Intelligence Research (JAIR). 2002. - No. 17. -P. 171-228.

80. Tambe, M. Building intelligent pilots for simulated rotary wing aircraft / M. Tambe, K. Schwamb, P. S. Rosenbloom // In proc. of the Fifth Conference on Computer Generated Forces and Behavioral Representation. May, 1995. - P. 39-44.

81. Tambe, M. Recursive agent and agent-group tracking in a real-time, dynamic environment / M. Tambe // In Proceedings of the First International Conference on Multi-Agent Systems (ICMAS-95). Menlo Park, California: AAAI Press, June 1995. - P. 368-375.

82. Tambe, M. Adaptive Agent Tracking in Real-world Multi-Agent Domains: A Preliminary Report / M. Tambe, J. Lewis, S. Wei-Min // International Journal of Human-Computer Studies. 1998. - Vol. 48, No 1. - P. 105-124.

83. Automated Intelligent Pilots for Combat Flight Simulation / M. J. Randolph, J. E. Laird, P. E. Nielsen, at all // AI Magazine. 1999. - Vol. 20, No. 1. - P. 27-41.

84. Intelligent Agents for Interactive Simulation Environments / M. J. Randolph, J. E. Laird, P. E. Nielsen, at all // AI Magazine. 1995. Vol. 16, No 1. - P. 15-39.

85. An Expert System Shell for Aerospace Applications / В. E. Prasad, T. S. Perraju, G. Uma, P. Umarani // IEEE Expert: Intelligent Systems and Their Applications. 1994. -Vol.9, No. 4.-P. 56-64.

86. Musliner, D. J. CIRCA: A Cooperative Intelligent Real-Time Control Architecture / D. J. Musliner, E. H. Durfee, K. G. Shin // IEEE Trans. Systems, Man, and Cybernetics. -1993.-Vol. 23, No. 6.-P. 1561-1574.

87. Musliner D. J. World Modeling for the Dynamic Construction of Real-Time Control Plans / D. J. Musliner, E. H. Durfee, K. G. Shin // Artificial Intelligence. 1995. - Vol. 74, No. l.-P. 83-127.

88. Planning and Resource Allocation for Hard Realtime, Fault-Tolerant Plan Execution / E. M. Atkins, T. F. Abdelzaher, K. G. Shin, E. H. Durfee // Proceedings of the third annual conference on Autonomous Agents. Seattle, Washington, 1999. - P. 244-251.

89. Atkins, E. M. Autonomous Flight with CIRCA-II / E. M. Atkins, E. H. Durfee, K. G. Shin // Autonomous Agents-99 Workshop on Autonomy Control Software. — May 1999.

90. Atkins, E. M. Knowledge Representation for Real-time Plan Development / E. M. Atkins // AAAI-2000 Workshop on Representational Issues for Real-World Planning Systems. AAAI Technical Report WS-00-07, July 2000. - P. 1-5.

91. Solus: An Autonomous Aircraft for Flight Control and Trajectory Planning Research / E. M. Atkins at al. // In Proc. American Control Conference. June 1998. — Vol. 2,-P. 689-693.

92. Development of Iterative Real-time Scheduler to Planner Feedback / С. B. McVey, E. M. Atkins, E. H. Durfee, K. G. Shin // Proceedings of IJCAI-97. August 1997. -P. 1267-1272.

93. Atkins, E. M. Buying Time for Resource-Bounded Planning / E. M. Atkins, E. H. Durfee, K. G. Shin // AAAI-97 Workshop: Building Resource-Bounded Reasoning Systems Technical Report. July 1997. - P. 7-11.

94. Atkins, E. M. Building a Plan with Real-Time Execution Guarantees / E. M. Atkins, E. H. Durfee, K. G. Shin // AAAI-96 Workshop on Structural Issues in Planning and Temporal Reasoning. August 1996.-P. 1-6.

95. На, V. Toward Decision-Theoretic CIRCA With Application to Real-Time Security Control / V. Ha, D. P. Musliner // In Working notes of the AAA! 2002 Workshop on Real-Time Decision Support Systems. July 2002. - P. 89-90.

96. Atkins, E. M. Plan development using local probabilistic models / E. M. Atkins, E. H. Durfee, K. G. Shin // In Proceedings Conference on Uncertainty in Artificial Intelligence. August 1996. - P. 49-56.

97. Hayes-Roth, B. Architectural Foundations for Real-Time Performance in Intelligent Agents / Barbara Hayes-Roth // The Journal of Real-Time Systems. 1990. - Vol. 2, Issue 1-2.-P. 99-125.

98. Larsson, J. E. Guardian: Final Evaluation : Technical Report KSL-96-25 / J. E. Larsson, B. Hayes-Roth, D. Gaba; Knowledge Systems Laboratory. August 1996.

99. Hayes-Roth, B. An Architecture for Adaptive Intelligent Systems. An architecture for adaptive intelligent systems / B. Hayes-Roth // Artificial Intelligence. — 1995. — Vol. 72, No. 12. P. 329-365.

100. Letichevsky, A. A. Proving theorem and reading mathematical texts in Mathematical Information Environment / A. A Letichevsky, J. V. Kapitonova, V. A. Volkov // International Workshop RTETP-2000. Kiev, May 2000. - P. 29-31. - ISBN 966-02-1654-8.

101. Letichevsky, A. A. A Model for Interaction of Agents and Environments / A. A. Letichevsky, D. R. Gilbert // In proceedings of The 14th International Workshop on Recent Trends in Algebraic Development Techniques. 1999. — P. 311-328.

102. Miiller, J. P. The design intelligence agents: A layered approach. / J. P. Mtiller // Lectures notes in artificial intelligence. 1996. - Vol. 1177. - ISBN 3-540-62003-6.

103. Mtiller, J. P. The agent architecture InteRRaP: Concept and application : Research Technical Report RR-93-26 / J. P. Mtiller, M. Pischel ; Deutsches Forschungszen-trum fur Kunstliche Intelligenz. Kaiserslautern, 1993.

104. Modeling crew assistants with multi-agent systems in fighter aircraft : Technical Report NLR-TR-2002-347 / A. M. Vollebregt, D. P. Hannessen, H. H. Hesselink, J. W. Beetstra; National Aerospace Laboratory NLR. Amsterdam, 2002.

105. Вагин, В. Н. Некоторые базовые принципы построения интеллектуальных систем поддержки принятия решений реального времени / В. Н. Вагин, А. П. Еремеев // Известия РАН. ТиСУ, 2001. - № 6. - С. 114-123.

106. Еремеев, А. П. Обработка недоопределенной информации в системе поддержки принятия решений реального времени применительно к оперативной службе электростанций / А. П. Еремеев, JI. С. Денисенко // Известия РАН. — Энергетика, 2002. № 2. - С. 32-43.

107. Shin, K. Real-Time Computing: A New Discipline of Computer Science and Engineering / K. Shin, P. Ramanathan // Proceedings of the IEEE. Jan 1994. — Vol. 82, No. 1.-P. 6-24.

108. Real-Time Knowledge-Based Systems / T. J. Laffey, P. A. Cox, J. L. Schmidt, S. M. Kao, J. Y. Read // AI Magazine. 1988. - V. 9, Issue 1. - P. 27-45.

109. Tsai, H. Termination analysis of OPS5 expert systems / H. Tsai, A. M. K. Cheng // In Proceedings of the AAAI National Conference on Artificial Intelligence, — Seattle, Washington, September 1994. P. 193-198.

110. Chen, I. R. Performance Evaluation of Rule Grouping on a Real Time Expert System Architecture /1. R. Chen, B. Poole // IEEE Transactions on Knowledge and Data Engineering. Dec. 1994. -V. 6, No. 6. - P. 883-891.

111. Мок, A. Response-time bounds of equal rule-based programs under rule priority structure / A. Мок, R. H. Wang // IEEE Transactions on Software Engineering. July, 1982. - V. 21, No. 7. -P. 593-623.

112. Zupan, B. Optimization of Rule-Based Systems via State Transition System Construction / B. Zupan, A. M. K. Cheng // Proc. IEEE-CS Conf. on Artificial Intelligence for Applications. San Antonio, TX, March 1994. - P. 320-326.

113. Zupan, B. Optimization of Rule-Based Systems Using State Space Graphs / B. Zupan, A. M. K. Cheng // IEEE Transactions on Knowledge and Data Engineering. — March/April 1998. Vol. 10, No. 2. - P. 238-254.

114. Lin, M. On semantics of reactive rule-based systems : DA Technical Report LiTH-IDA-R-96-35 / M. Lin, J. Malec, S. Nadjm-Tehrani ; Department of Computer and Information Science, Linkoping University. 1996. - ISSN-0281-4250.

115. Каляев, А. В. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений / А. В. Каляев, И. И. Левин. — М.: Янус-К, 2003. 380 с.

116. Еремеев, А. П. Параллельная модель для продукционной системы табличного типа / А. П. Еремеев // Изв. АН СССР. Техн. кибернет., 1990. — № 5. — С. 171-180.

117. Еремеев, А.П. Организация параллельных вычислений на основе моделей потока данных / А. П. Еремеев // Изв. РАН. — Техн. кибернет., 1993. — № 3. — С. 212-225.

118. Вагин, В. Н. Параллелизм в продукционных моделях представления знаний / В. Н. Вагин, А. П. Еремеев // Изв. РАН. Техн. кибернет., 1994. - № 1. - С. 4855.

119. Amaral, J. N. Concurrent Architecture for Serializable Production Systems / J. N. Amaral, J. Ghosh // IEEE Transactions on Parallel and Distributed Processing. Dec. 1996.-Vol. 7, No. 12.-P. 1265-1280.

120. Amaral, J. N. An Associative Memory Architecture for Concurrent Production Systems / J. N. Amaral, J. Ghosh // In Proc. 1994 IEEE International Conference on Systems, Man and Cybernetics. San Antonio: October 1994. - P. 2219-2224.

121. Amaral, J. N. Serializability Improves Parallel Execution of Production System / J. N. Amaral, J. Ghosh // In VII Brazilian Symposium on Computer Architecture High Performance Processing. July 1995.-P. 167-181.

122. Amaral, J. N. Using queuing theory for analytical performance evaluation of a multiple functional unit RETE network / J. N. Amaral, J. Ghosh // In XV Congress of the Brazilian Computer Society. July 1995. - P. 611-625.

123. Pasik, A. J. A Source-to-Source Transformation for Increasing Rule-Based System Parallelism / A. J. Pasik // IEEE Transactions on Knowledge and Data Engineering. -August 1992. Vol. 4, Issue 4. - P. 336-343.

124. Neiman, D. E. An Implementation of Multiple Worlds for Parallel Rule-Firing Production Systems : Technical Report 93-24 / D. E. Neiman ; Computer Science Department, UMASS @ Amherst. March 1993.

125. Neiman, D. E. Design and Control of Parallel Rule-Firing Production Systems : PhD thesis: University of Massachusetts / D. E. Neiman. Massachusetts: September 1992.

126. Schmolze, J. G. Guaranteeing Serializable Results in Synchronous Parallel Production Systems / J. G. Schmolze // Journal of Parallel and Distributed Computing. -1991.-Vol. 13, No. 13.-P. 348-365.

127. Schmolze, J. G. Comparison of three algorithms for ensuring serializability in parallel production systems / J. G. Schmolze, D. E. Neiman // In Proceedings of the National Conference on Artificial Intelligence (AAAI-92). San Jose, CA: July 1992.

128. Nayak, T. INFLOW: A Parallel Inference Machine Architecture for Rule Based Expert Systems / T. Nayak, A. Basu, S. Mukherjee // Computers and Artificial Intelligence. 1990. - Vol. 9, No.4. - P. 357-377.

129. Stolfo, S. J. DADO: A tree-structured machine architecture for production systems / S. J. Stolfo, D. E. Shaw // In National Conference on Artificial Intelligence AAAI. -1982.-P. 242-246.

130. Stolfo, S. J. DADO: A Parallel Processor for Expert Systems / S. J. Stolfo, D. P. Miranker// Proceedings of the International Conference on Parallel Processing (IEEE). — 1984. — P.74-82.

131. Shaw, D. E. NON-VON's applicability to three AI task areas / D. E. Shaw // In International Joint Conference on Artificial Intelligence. 1985. - P. 61-72.

132. Oflazer, K. Parallel execution of production systems / K. Oflazer // In IEEE International Conference on Parallel Processing. 1984. - P. 92-100.

133. Cheng, F. С. DFLOPS: A Data Flow Machine for Production Systems : Technical report CUCS-025-93 / F. C. Cheng, M.Y. Wu ; Columbia University. Columbia, 1993.

134. Wu, M.Y. Explicit Parallel Structuring for Rule Based Programming / M. Y. Wu, S. Yang, J. C. Browne // In Proceedings of IPPS'93: International Parallel Processing Symposium. -1993. P. 479-488.

135. Decomposition Abstraction in Parallel Rule Languages / M.Y. Wu, S. Yang, D. P. Miranker, J. C. Browne // IEEE Transactions on Parallel and Distributed Systems. -Nov. 1996.-Vol. 7, No. 11.-P. 1164-1184.

136. Goopta, A. High-Speed Implementation of Rule-Based Systems / A. Goopta, C. L. Forgy, A. Newell // ACM Transactions on Computer Systems. 1989. - Vol. 7, No. 2. -P. 119-146.

137. Srinivasa R. Parallel Rule-Based Isotach Systems : Technical Report CS-1999-04 / R. Srinivasa; Dept. of Computer Science, University of Virginia. Feb. 1999.

138. Wang, C. Y. Increasing Production System Parallelism via Synchronization Minimization and Check-Ahead Conflict Resolution / C. Y. Wang, A. M. K. Cheng // Proc. Int'l Conference on Parallel Processing. Oconomovoc, WI, Aug. 1995. - Vol. 3. - P. 8592.

139. Ishida, T. Parallel, Distributed and Multi-Agent Production Systems A Research Foundation for Distributed Artificial Intelligence / T. Ishida // International Conference on Multi-Agent Systems. - 1995.

140. Ishida, T. Parallel Rule Firing of Production Systems / T. Ishida // IEEE Transactions On Knowledge and Data Engineering. March 1991. - Vol. 3, No. 1. - P. 1117.

141. Ishida, T. An Optimization Algorithm for Production Systems / T. Ishida // IEEE Transactions on Knowledge and Data Engineering. 1994. - Vol. 6, No. 4. - P. 549558.

142. Stolfo, S. J. The PARULEL parallel rule language / S.J. Stolfo, H. M. Dewan, O. Wolfson // In Processings of International Conference on Parallel Processing. 1991. -No. 30-P. 11-36-45.

143. Ishida, T. Optimizing rules in production system programs / T. Ishida, S. J. Stolfo // In Proceedings of the National Conference of the American Association for Artificial Intelligence. 1988. - P. 699-704.

144. Wu, M. Y. Toward Semantic-Based Parallelism in Production Systems / M. Y. Wu, D. P. Miranker, J. C. Browne // Proc. ICPADS'94: International Conference on Parallel and Distributed Systems. 1994. - P. 752-758.

145. Rosenblatt R. Principles of Neurodynamics / R. Rosenblatt. Spartan Books, New York, 1962.

146. Mixnsky M., Papert S. Perceptions: An Introduction to Computational Geometry / M. Mixnsky, S. Papert MIT Press, Cambridge, Mass., 1969.

147. Джейн, А. К. Введение в искусственные нейронные сети / А. К. Джейн // Открытые системы. № 4. — 1997.

148. Jan, N. H. Heemskerk. Overview of neural hardware electronic resource. / N. Heemskerk Jan. — 1995. — Available at: ftp://flp.mrcapu.cam. ac.uk/pub/nn/murre/neurhard.ps.

149. Duman, F. Hardware Implementation of Neural Networks on General Purpose Microcontrollers / F. Duman, H. Erdem // Proceedings of International Conference on Signal Processing. ISSN 1304-2386. - September 2003. - Vol. 1, No. 2.

150. Liu, J. Fully Parallel Learning Neural Network Chip for Real-Time Control : PhD Thesis : Georgia Institute Of Technology / J. Liu. 1999. - 316 p.

151. Fast prototyping for hardware neural networks / G. Grossi at al. // International Conference on Artificial Neural Networks (ICANN-95). European Neural Network Society. October 1995. - P. 411-416.

152. Zhu, J. FPGA Implementations of Neural Networks a Survey of a Decade of Progress / J. Zhu, P. Sutton // In Proceedings of 13th International Conference on Field Programmable Logic and Applications (FPL 2003). - Lisbon, 2003.

153. Artificial neural network implementation on a single FPGA of a pipelined online backpropagation / R. Gadea, J. Cerda, F. Ballester, A. Mocholi // Proceedings of the 13th international symposium on System synthesis. 2000. - P. 225-230.

154. Digital Neurohardware: Principles and Perspectives / T. Schoenauer, A. Jah-nke, U. Roth, H. Klar // In Proc. Neuronale Netze in der Anwendung, NN'98. Magdeburg, 1998.-P. 101-106.

155. Serbedzija, N. В. Simulating Artificial Neural Networks on Parallel Architectures / Serbedzija N. B. // Computer. 1996. - Vol.29, No.3. - P. 56-63.

156. Synapse-1: A high-speed general purpose parallel neurocomputer system / U. Ramacher at al. // In Proc. 9th Intl. Symposium on Parallel Processing (IPPS'95). Los Alamitos, CA: IEEE Computer Society Press, 1995. - P. 774-781.

157. CPU 12 Reference Manual electronic resource. / Motorola Inc. 1996. - Режим доступа: http://www.mot-sps.com.

158. ST52F51x 8-bit Intelligent Control Unit (ICU) Datasheet. Rev. 2.3 electronic resource. / ST Microelectronics. May 2004. — Режим доступа: http://www.st.com/stonline/books/pdf/docs/8793.pdf

159. Salapura, V. Hardware/software co-design of a fuzzy RISC processor / V. Salapura, M. Gschwind // Proceedings of the conference on Design, automation and test in Europe. 1998. - P. 875-882. - ISBN:0-8186-8359-7.

160. Водяхо, А. И. Функционально-ориентированные процессоры / А. И. Во-дяхо, Д. В. Пузанков и др.. — JI.: Машиностроение, 1988. — 224с.

161. Вишняков, В. А. Аппаратно-программные средства процессоров логического вывода / В. А. Вишняков, Д. Ю. Буланже, О. В. Герман. — М.: Радио и связь, 1991.-263 с.

162. Щипцов, В. А. Проектирование архитектуры процессора для языка COMMON LISP Текст.: дис. . канд. техн. наук : 05.13.13 / В. А. Щипцов СПб.: ЛЭТИ, 1991.

163. Yasushi, Н. A 32-bit LISP Processor for the Al Workstation ELIS with a Multiple Programming Paradigm Language, TAO / H. Yasushi, W. Kazufumi, T. Ikuo // Journal of Information Processing. 2001. - Vol. 13, No. 02.

164. Тодорова, Э. С. Архитектура процессора, ориентированного на эффективное выполнение компилированных ПРОЛОГ-программ : дис. . канд. техн. наук : 05.13.13 / Э. С. Тодорова. СПб.: ЛЭТИ, 1993.

165. High performance integrated PROLOG processor IPP / S. Abe et al. // Proceedings of the 14th annual international symposium on Computer architecture. — 1987. — P. 100-107.

166. Nilsson, U. Logic, Programming and Prolog : 2ed. / U. Nilsson, J. Maluszyn-ski.- 1995.-ISBN 0-471-95996-0.

167. Pagni, A. WARP: Weight Associative Rule Processor. An Innovative Fuzzy Logic Controller / A. Pagni, R. Poluzzi, G. G. Rizzotto // IIZUKA'92-2ND International Conference on Fuzzy Logic and Neural Networks. 1992.

168. Andrea, G. B. Evolutionary Algorithms and Fuzzy Logic: A two-way integration / G.B. Andrea // Proc. 2nd Joint Conf. on Inf. Sciences. 1995. - P. 464-467.

169. Dipert, B. Silicon Segmentation electronic resource. / Electronic Design News. Issue Sep 18, 2003. - Режим доступа: http://www.reed-electronics.com/ednmag/index.asp?layout=articlePrint&articleID=CA321801.

170. Verilog Hardware Description Language Reference Manual (LRM). Version 1.0 / Open Verilog International, Inc. November, 1991.

171. Architecture Description Languages for Systems-on-Chip Design / H. Tomi-yama et al. // In Proc. of 6th Asia Pacific Conference on Chip Design Languages (APCHDL'99), Invited paper. Fukuoka, Japan, Oct. 1999. - P. 109-116.

172. EXPRESSION: An ADL for System Level Design Exploration. Technical Report 1998-29 / B. Halambi et al.; University of California, Irvine. 1998.

173. Бибило, П. H. Основы языка VHDL. М.: СОЛОН-Р, 2002. - 224 с.

174. Грушвицкий, Р. И. Проектирование систем на микросхемах программируемой логики / Р. И. Грушвицкий, А. X. Мурсаев, Е. П. Угрюмов. СПб.: БХВ-Петербург, 2002. - 608 е.: ил.

175. Пантелеев, М. Г. Организация и проектирование средств аппаратной поддержки интеллектуальных агентов / М.Г. Пантелеев, В.В. Денисов, Г.Г. Колосов // Интеллектуальные системы (INTELS'2000): Труды 4-го междунар. симп. М.: РУСАКИ, 2000.-С. 188-190.

176. Пантелеев, М. Г. Архитектура процессора логического вывода для продукционных БЗ на основе RETE-сети / М. Г. Пантелеев, Г. Г. Колосов // Изв. СПбГЭТУ "ЛЭТИ". СПб.: Изд-во СПбГЭТУ, 2002. - Вып. 2. - С. 35-43.

177. Колосов, Г. Г. Процессор аппаратной поддержки продукционных систем на основе RETE-сети / Г. Г. Колосов // Труды 5-го междунар. симп. «Интеллектуальные системы» (INTELS'2002). М.: МГТУ им. Н.Э. Баумана, 2002. - С. 306-308.

178. Организация и проектирование функционально-ориентированных процессоров аппаратной поддержки продукционных баз знаний / Д. В. Пузанков, М. Г. Пантелеев. В. В. Денисов, Г. Г. Колосов // Изв. ВУЗов. Приборостроение. СПб., 2003. - Т.46, №2. - С. 18-23.

179. Пантелеев, М. Г. Проектирование процессоров обработки продукционных баз знаний на основе RETE-сети / М. Г. Пантелеев, Г. Г. Колосов // Искусственный интеллект. 2003. - №3. - С. 465-473.

180. Пантелеев, М. Г. Виртуальная машина интерпретатора RETE-сетей в задачах проектирования функционально-ориентированных процессоров / М. Г. Пантелеев, Г. Г. Колосов // Искусственный интеллект. 2004. - №4. - С.726-732.

181. А. с. 25951 РФ, МКИ G 06F 7/00. Функционально-ориентированный процессор обработки продукционных знаний / М. Г. Пантелеев, В. В. Денисов, Г. Г. Колосов (РФ). -№ 2002115379/20; заявл. 11.06.02; опубл. 27.10.02, Бюл. № 30. 3 е.: ил.1. Список иллюстраций

182. Рисунок 1.1 — Списочная форма представления знаний.14

183. Рисунок 1.2 — Пример дерева решений.15

184. Рисунок 1.3 — Пример RETE-сети.17

185. Рисунок 1.4 — Сравнение подходов TREAT и RETE.19

186. Рисунок 1.5 — Исключение комбинаторики в Uni-Rete.21

187. Рисунок 1.6 — Диаграмма потока данных обработки неопределенностей в ПС.23

188. Рисунок 1.7 — Архитектура доски объявлений.29

189. Рисунок 1.8 — Обработка операторов в SOAR.31

190. Рисунок 1.9 — Архитектура CIRCA.33

191. Рисунок 1.10 — Пример БЗ в ИА РВ CIRCA-II.34

192. Рисунок 1.11 — Архитектура агента InteRRaP.37

193. Рисунок 1.12 — Архитектура GUARDIAN.41

194. Рисунок 1.13 — Архитектура ИА РВ REX.42

195. Рисунок 1.14 — Примеры правил в агенте REX.43

196. Рисунок 1.15 — Обобщенная архитектура ИА РВ.44

197. Рисунок 1.16 — Описание объектов среды в БД агента.47

198. Рисунок 1.17 — Получение вторичных признаков объектов среды.47

199. Рисунок 1.18 — Пример потокового графа вывода INFLOW.52

200. Рисунок 1.19 — Процессорный элемент параллельной архитектуры.55

201. Рисунок 1.20 — Формальный нейрон МакКаллока и Питгса.59

202. Рисунок 2.1 — Обработка потока данных в машине вывода на основе RETE-сети. 63

203. Рисунок 2.2 — Струюура RETE-сети.65

204. Рисунок 2.3 — Формирование выходного токена в р-узле.67

205. Рисунок 2.4 — Укрупненный алгоритм обработки токена.69

206. Рисунок 2.5 — Варианты размещения р-узлов в RETE-сети.70

207. Рисунок 2.6 — Пример RETE-сети.73

208. Рисунок 2.7 — Возможная конфигурация критических Р-узлов.77

209. Рисунок 2.8 — RETE-сеть для преобразованного фрагмента с константнымизначениями атрибутов.81

210. Рисунок 2.9 — Распределение токенов в узлах RETE-сети.82

211. Рисунок 2.10 — Представление конечных узлов парными множествами.83

212. Рисунок 2.11 — Пример RETE-сети, работающей в рамках одного класса.87

213. Рисунок 2.12 — Структура дерева констант.88

214. Рисунок 2.13 — Формат представления дерева констант.89

215. Рисунок 2.14 — Форматы слов а-, Р- и у-памяти.90

216. Рисунок 2.15 — Формат представления указателя.92

217. Рисунок 2.16 — Формат представления входного токена.93

218. Рисунок 2.17 — Общий формат представления RETE-сети.94

219. Рисунок 3.1 — Одноступенчатый конвейер в ФОП.96

220. Рисунок 3.2 — Архитектура ФОП.97

221. Рисунок 3.3 — Главный цикл интерпретатора.98

222. Рисунок 3.4 — Алгоритм обработки констант и а-узлов.99

223. Рисунок 3.5 — Структура блока сопоставления для четких значений предикатов. 100 Рисунок 3.6 — Структура блока сопоставления для нечетких значений предикатов 101

224. Рисунок 3.7 — Алгоритм обработки у- и двухвходовых р-узлов.102

225. Рисунок 3.8 — Структура блока формирования адреса.104

226. Рисунок 3.9 — Переход к многовходовому узлу.106

227. Рисунок 3.10 — Заполнение входов р-узла.108

228. Рисунок 3.11 — Зависимость числа шагов обработки узла от количества входов. 111 Рисунок 3.12 — Зависимость прироста производительности от числа входов узла. 112

229. Рисунок 3.13 — Укрупненный алгоритм построения оптимальной RETE-сети (начало)117

230. Рисунок 3.14 — Алгоритм обработки многовходового р-узла.120

231. Рисунок 3.15 — Обработка отрицательных токенов по принципу TREAT.121

232. Рисунок 3.16 — Методика проектирования ФОП с применением специализированнойсреды проектирования.125

233. Рисунок 4.1 — Рост стоимости разработки БИС/СБИС заказного типа.128

234. Рисунок 4.3 — Задание масштабирующих констант.133

235. Рисунок 4.4 — RETE-сеть отладочной базы знаний.134

236. Рисунок 4.5 — Тестовая последовательность токенов.134

237. Рисунок 4.6 — Фото платы экспериментального образца ФОП.135

238. Рисунок 4.7 — Пример RETE-сети для тестовой БЗ в формате .rtn.145

239. Рисунок 4.8 — Пример тестовой БЗ в формате ФОП.148

240. Рисунок 4.9 — Пример тестовой БД в формате ФОП.148

241. Рисунок 4.10 — Время оптимизации RETE-сети в зависимости от числа входов сети150

242. Рисунок 4.11 — Прирост производительности при оптимизации RETE-сети.150

243. Рисунок 4.12 — Зависимость времени обработки RETE-сети от объема БЗ.151

244. Рисунок 4.13 —Зависимость среднего времени обработки токена от числа продукций152

245. Рисунок 4.14 — Выигрыш в производительности ФОП по сравнению с выводом набазе CLIPS и низкоуровневого программного интерпретатора (Pentium III).152

246. Рисунок 4.15 — Выигрыш в производительности ФОП по сравнению с выводом на базе CLIPS и низкоуровневого программного интерпретатора (Pentium IV). 15300 ота ко "Си о яItn Й о яе