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

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА И ОРДЕНА ОКТЯБРЬСКИ РЕВОЛЮЦИИ АВИАЦИОННЫЙ ИНСТИТУТ имени СЕРГО ОРДЖОЧИКИДЗЕ

УДК 681.3.06 На правах рукописи

Марченко Антон Леонардович

МЕТОДЫ РЕАЛИЗАЦИИ СИСТЕМ ПРОДУКЦИОННОГО ПРОГРАММИРОВАНИЯ

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

АВТОРЕФЕРАТ

диссертациии на соискание ученой степени кандидата физико-математических наук

Москва Издательство МАИ 1991

Работа выполнена во Всесоюзном научно-исследовательском институте прикладных автоматизированных систем (ВНИИПАС)

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

профессор Шатровский Л.И.

Официальные оппоненты доктор технических наук,

профессор Кузин Л.Т.

кандидат физико-математических наук Хорошевский В.Ф.

Ведущая организация

Международный Центр Технологии Программирования "Технософт".

Защита диссертации состоится (^¿^/Щ /1-Я 1992г.

в _ час. _ мин. на заседании специализированного

совета К053.18.09 в Московском авиационном институте по адресу _

С диссертацией можно ознакомится в библиотеке МАИ.

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

Автореферат разослан 1992. г •

Ученый секретарь специализированного совета

■ Г.-«

. Л. .1Ш8С

тдг-л :артациЯ

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

актуальность темы

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

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

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

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

1. Разработан язык представления знаний ОРБ-Н;

2. Разработаны алгоритмы интерпретации, обеспечивающие эффективное выполнение программ на языке представления знаний;

3. Предложен и реализован комплекс средств управления выводом решения в системах продукционного программирования;

4. Создана система продукционного программирования HAMMER и проведено практическое исследование применимости языка представления знаний OPS-H для решения задач различного класса.

На защиту выносятся следующие результаты:

- язык программирования OPS-H и методы его реализации;

- алгоритмы интерпретации для языка OPS-H;

- средства управления выводом решения;

- система продукционного программирования для разработки экспертных систем HAMMER в составе компилятора языка OPS-H, интерпретатора и базового набора действий;

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

Практическая ценность. Использование системы HAMMER позволяет разрабатывать и эксплуатировать ЭС различного назначения и большой сложности.

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

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

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

Объем работы. Диссертация состоит из введения, четырех разделов, приложения и списка литературы и содержит 155 страниц; список литературы состоит из 51 наименования.

СОДЕРЖАНИЕ РАБОТЫ

Экспертными системами принято называть прикладные компьютерные программы специального вида, предназначаемые

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

Отличительной чертой ЭС является метод решения, который предполагает использование специальных знаний о предметной области. Решение задачи обеспечивается в первую очередь за счет применения этих знаний. Методы решения задач при этом часто бывают аналогичны методам, которые используют "эксперты" - специалисты в этой области знаний. Их конкретные знания и обширный опыт, представленные в машинно-ориентированном виде составляют основу ЭС.

Способы представления информации о предметной области определяют модели представления знаний. При создании экспертных систем часто единственным источником информации является человек - специалист в узкой предметной области, способный лишь в привычной для него форме изложить и в дальнейшем уточнить все относящиеся к задаче сведения. Поэтому при разработке моделей представления знаний для экспертных систем большое значение имеет близость разрабатываемой модели традиционным методам работы со знаниями. Широко известны логические , сетевые и фреймовые модели, а также продукционные модели представления знаний. С моделями представления знаний непосредственно связаны специализированные языки представления знаний, позволяющие в соответствии с принятой при создании ЭС моделью представления знаний ' адекватно формализовать знания эксперта. К настоящему времени на основе продукционного формализма реализовано большое количество языков представления знаний. Среди них - РЕФАЛ, PROLOG , языки программирования семейства OPS, а также реализованный автором язык OPS-H. Разработка и эксплуатация ЭС предполагает специальную систему программирования - набор программных средств, которые в процессе решения задачи обеспечивают возможность применения опыта эксперта, формализованного средствами языка представления знаний . Архитектура системы программирования в значительной степени определяется моделью представления знаний и может включать в

качестве компонент интерпретатор языка представления знаний, средства поддержки, объяснения и разработки ЭС.

Система продукционного программирования HAMMER ориентирована на язык представления знаний OPS-H (OPS-HAMMER), прототипом которого является язык OPS5.

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

г-ЮК—, |—78KJ-1 (-180К--...-;

|hm.exe| |procOl.exe| |??.exe | внешние h

1-1 I-1 ¡системная частьЦ процедуры | h

I—100K-, Ц--ill

I_I

j

??.exe Программные компоненты h

-1 h

I_I I

proc02.exe| Ц

Компоненты системы HAMMER разделяются на вспомогательные, исполнительные и программные. Взаимодействие компонент обеспечивается монитором , который является резидентной частью системы. Его загрузочный модуль располагается в файле "hm.exe" и занимает около ЮК дисковой памяти. Вспомогательные компоненты системы располагаются в файлах "proc01.exe" и "proc02.exe". Первая компонента занимает около 78К байт и обеспечивает интерфейс с пользователем, вторая занимает около 100К байт , включает транслятор, элементы системы поддержки управляющей и рабочей

памяти и служит для преобразования текстов OPS-H программ во внутреннее представление системы. Файлы с исходным текстом OPS-H программ имеют расширение ".И", файлам с внутренним представлении присваивается расширение ".cmf".

Исполнительные компоненты могут располагаться в ".ехе" файлах с произвольными именами (отличными от "hm.exe", "proc01.exe" и "proc02.exe"). Исполнительные компоненты обеспечивают выполнение OPS-H программ. В оперативной памяти исполнительные компоненты вместе с внутренним представлением OPS-H программ образуют процессы. Исполнительная компонента в оперативной памяти является ядром процесса. Ядро процесса включает машину вывода, базовый набор действий, системы поддержки управляющей и рабочей памяти, которые входят в системную часть исполнительной компоненты. Системная часть исполнительной компоненты занимает на диске около 180К байт. Исполнительная компонента может также включать внешние процедуры. Множество внешних процедур формируется непосредственно разработчиком ЭС и объединяется с системной частью в загрузочный модуль в результате процесса сборки.

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

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

Язык OPS-H ориентирован на работу с данными реляционной структуры. Программа на языке OPS-H в общем случае представляется как множество модулей. Тексту модулей предшествует описание данных. Данное характеризуется уникальным именем и непустым множеством кортежей пар атрибут-значение; входящие в кортеж атрибуты различаются по именам. Значениями атрибутов в существующей версии системы могут быть либо символьные атомы - последовательности произвольных символов, либо числа. За описанием данных следуют сгруппированные по сегментам продукции . В начале

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

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

К числу особенностей языка OPS-H следует отнести:

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

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

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

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

1. Интерпретация условий в продукциях и выбор продукций, не

содержащих невыполняемых условий (признак выполнимости таких продукций устанавливается равным 0). 2. Выполнение действий найденных продукций.

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

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

В системе реализована возможность управления порядком записи кодов данных в список. Это управление непосредственно реализуется с помощью действий cut I Ist, iniist, lnlist-f, inlist-b. Эти действия входят в базовый набор действий системы HAMMER и могут включаться в консеквент любой продукции сегмента. Действие outlist удаляет из списка кодов элементы списка, указанные в аргументах действия. Удаление элементов из списка позволяет сделать процесс вывода нечувствительными к изменениям состояния рабочей памяти. Тройка Iniist, inlist-f, inlist-b модифицирует . список, изменяя при этом порядок элементов в списке и определяет последовательность обращения интерпретатора к продукциям активного сегмента. Включение в этот список новых элементов позволяет активизировать продукции, не связанные с текущими изменениями рабочей памяти. Аналогичным образом производится модификация списка действями изменения состояния рабочей памяти и действиями ввода, каждое из которых может быть использовано в одном из трех вариантах (без суффикса и с суффиксами '-f','-b').

В системе реализована возможность управления порядком

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

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

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

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

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

модификацией списков указателей на условия и списка переменных.

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

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

Действия ssp и sspall позволяют изменять значение stop-атрибута продукций в любом сегменте выполняемого модуля.

Ненулевое значение stop-атрибута продукции влечет выключение продукции непосредственно после ее выполнения с последующим ее автоматическим включением через определенное число циклов работы интерпретатора. Это число не превышает значения stop-атрибута продукции.

Действие stop-transit в сочетании с действиями ssp и sspall определяет периодичность обращения интерпретатора к продукциям.

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

После выполнения действия stop-transit со значением ключа 'OFF', при переходе из одного сегмента в другой промежуточные значения счетчикор циклов не сохраняются и после возвращения или повторного перехода в исходный сегмент отсчет циклов производится непосредственно с момента нового выполнения продукции.

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

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

В системе HAMMER реализовано еще одно эффективное средство управления выводом - управление с помощью произвольных алгоритмов (в частности, алгоритмов выбора продукций из конфликтного множества) . При этом алгоритм описывается явным образом в специальной последовательности сегментов - последовательности сегментов управления выводом. Первому сегменту этой последовательности должно быть присвоено имя "МЕТА". Последовательность сегментов управления выводом завершает текст программы в модуле. При описании алгоритмов выбора продукций в сегментах управления выводом должны встречаться переменные с именами "M1KEY" и "M2KEY", значения которых определяют алгоритм выбора продукции.

В ходе выполнения OPS-H модуля, содержащего сегмент с

именем МЕТА в режиме проддержки конфликтного множества автоматически включается система поддержки регистров системы и меняется алгоритм работы интерпретатора.

Цикл работы интерпретатора включает в этом случае семь этапов:

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

2. Выключение режима поддержки конфликтного множества и передача управления в сегмент с именем МЕТА.

3. (1.) Интерпретация условий в продукциях сегмента с именем МЕТА и поиск продукции, не содержащей невыполняемых условий.

4. (2.) Выполнение действий найденной на предыдущем этапе продукции.

5. Включение режима поддержки конфликтного множества и передача управления в активный сегмент.

6. Выбор продукции из конфликтного множества.

7. Выполнение действий выбранной продукции.

Переход от этапа 4.(2.) к этапу 5. происходит после остановки машины вывода в результате выполнения действия halt, либо после того, как на вход машины вывода перестают поступать сообщения об изменениях в рабочей памяти (оказывается пустым список кодов измененных данных).

Существенное влияние на процесс выбора продукций из конфликтного множества оказывают значения переменных M1KEY и M2KEY, означивание которых происходит на этапах 3.(1.) и 4.(2.). В зависимости от значений переменных M1KEY и M2KEY существует возможность выбора продукций по имени, номеру вхождения продукции в конфликтное множество или значению rat i ng-атрибута.

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

любому условию в продукциях и сохраняет структуру исходной программы . Система поддержки управляющей памяти на основе анализа всех загружаемых в память условий, входящих в продукции сегмента, создает список указателей на условия. Этот упорядоченный по кодам имен данных список состоит из пар вида <N,Un>, где N - код данного, Un - указатель на загружаемое условие. Список указателей на условия минимален, поскольку в него не включаются пары вида <N,U1>, <N,U2>, где U1 и U2 указатели на различные условия, входящие в одну и ту же продукцию. Список указателей на условия и непосредственно сами внутренние представления условий в сети являются входными узлами интерпретатора системы.

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

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

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

Система HAMMER включает дополнительные средства поддержки ЭС, к которым относятся программые модули, обеспечивающие дополнительные возможности при разработке и выполнении OPS-H-программ. Утилита hjnaster позволяет в произвольном ".cm Г' файле изменять значения stop и ratlng-атрибутов, атрибутов доступности продукций, устанавливать порядок продукций в сегментах программы. Эту утилиту целесообразно использовать при разработке и выполнении многомодульных ЭС, когда один из модулей системы в интерактивном режиме осуществляет модификацию остальных модулей системы, обеспечивая настройку ЭС на решение конкретной задачи. Утилита cmfhf позволяет восстанавливать

текст OPS-H-программы по входной информации, содержащейся в ".craf" файле. Утилита cmf_wmf обеспечивает преобразование информации из формата базы знаний в формат базы данных системы. Утилита wmf_cmf обеспечивает обратное преобразование инфирмации.

Общий объем разработанного автором программного обеспечения составляет около 25 ООО строк языка СИ.

По системе HAMMER подготовлена документация объемом в 100 страниц.

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

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

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

1. На основе анализа широко используемого в системах продукционного пограммирования Rete-алгоритма выявлена взаимосвязь структуры управляющей памяти системы с алгоритмом сопоставления.

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

3. В качестве базового средства для построения ЭС предложен язык программирования OPS-H, синтаксис и выразительные возможности которого значительно расширены за счет явного введения кванторов при атрибутных переменных и сегментации программ.

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

5. Разработана и реализована система продукционного программирования HAMMER в составе :

- компилятора с языка OPS-H,

- интерпретатора системы,

- базового набора действий.

- систем поддержки управляющей и рабочей памяти,

- дополнительны;« средств поддержки ЭС.

6. Система HAMMER и методика ее использования внедрены на предприятии и в высшем учебном заведении.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ 1. Марченко А.Л. Инструментальная система HAMMER (руководство пользователя). -М.: ВНИИПАС, 1990, 56 с.

2. Марченко А.Л. Система HAMMER.-М.:

Сборник трудов ВНИИПАС N1. ВНИИПАС, 1988, стр.57-60.

3. Марченко А.Л. Тезисы доклада о системе HAMMER в сборнике

"Технология проектирования интеллектуальных систем (матерниалы семинара)" -М.: 1989, стр.34-36.

4. Марченко А.Л. Тезисы доклада о системе HAMMER в сборнике

"Диалоговые средства в АСУ (тезисы докладов республиканской научно-технической конференции)" -Кишинев: 1988, стр.69-71.

5. Марченко А.Л. Тезисы доклада о системе HAMMER в сборнике "Технология разработки экспертных систем (тезисы

докладов республиканской школы-семинара)" -Кишинев: 1987, стр.158-161.

6. Марченко А.Л. Тезисы доклада о системе HAMMER в сборнике

"Тезисы докладов всесоюзной конференции по искусственному интеллекту (Переславль-Залесский,1988)" -М.: 1988, Т.1, стр. 219.

7." Марченко А.Л. Тезисы доклада о системе HAMMER в сборнике

"2 Всесоюзная конференция "Искусственный интеллект 90"" -Минск: 1990, книга "Выставка", стр. 25-27.

8. Марченко А.Л. Тезисы доклада о системе HAMMER в сборнике

"Диалог "Человек - ЭВМ" (тезисы докладов конференции)" -Свердловск: 1989, часть 2, стр. 128-130.

Подписано к печати 22.II.91. Заказ^7^В/5514.Тираж 100.

125871, Москва, Волоколамское шоссе, 4