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

Р Г Б ОД РОССИЙСКАЯ АКАДЕМИЯ НАУК Сибирское отделение

^ О MAP 1997 Вычислительный центр

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

Яхно Татьяна Михайловна

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

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

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

№

Г

Новосибирск 1997

Работа выполнена б Институте систем информатики Сибирского отделения Российской академии наук (ИСИ СО РАН)

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

доктор физико-математических наук, профессор ВОРОНИН Ю.Л. доктор физико-математических наук, профессор ЗАГОРУИКО Н.Г. доктор физико-математических наук, профессор КЛЕЩЕВ A.C.

Ведущая организация: Российский научно-исследовательский институт информационных технологий и систем автоматизированного проектирования (г.Москва)

Защита состоится 25 марта 1997 г. в 15 часов на заседании специализированного совета Д 002.10.02 при Вычислительном центре СО РАН по адресу: Новосибирск,90, проспект Акад. Лаврентьева, 6

С диссертацией можно ознакомиться в читальном зале библиотеки ВЦ СО РАН (пр.Акад.Лаврентьева, 6)

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

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

специализированного совета Г.И.Забиняко

Общая характеристика работы

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

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

Начало исследованиям по представлению знаний было положено в первой половине 60-х годов в работах Е.Фейгенбаума, Г.Саймона, Д.Слейгла, А.Ньюэлла.

С середины 70-х годов систематические исследования по представлению знаний в интеллектуальных системах проводятся как в нашей стране, так и за рубежом. Значительного продвижения добились коллективы, руководимые Д.А.Поспеловым, Э.В.Поповым, А.С.Нариньянн, А.С.Клещевым, Н.Г.Загоруйко, Г.С.Осиповым и другими.

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

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

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

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

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

Апробация работы и публикации. Результаты работы докладывались и обсуждались на Всесоюзных конференциях по искусственному интеллекту (Переславль-Залесскин 1988, Минск 1990, Тверь 1992), международной конференции " Программное обеспечение ЭВМ" (Калинин, 1987), Всесоюзной конференции "Параллельное программирование и высокопроизводительные структуры" (Киев, 1988), Всесоюзном совещании "Экспертные системы" (Суздаль, 1990; Москва, 1992), Всесоюзной конференции "Интеллектуальные системы в машиностроении" (Самара, 1991), международной конференции "Запад-Восток: проблемы искусственного интеллекта" (Москва, 1993), международной конференции CSAM'93 (С.тПетербург, 1993), международной летней школе-НАТО (Таллинн, 1993), международных конференциях AI&ES (Германия, 1994), EUITT'95 (Германия, 1995), CONTESSA'95 (Германия, 1995), РАСТ'96 (Англия, 1996), PSI'96 (Новосибирск, 1996) и намного-численных докладах семинаров Института систем информатики.

Публикации. По теме диссертации опубликовано 53 работы, в .том числе 13 в центральных и 12 в зарубежных изданиях.

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

Содержание работы

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

Одно из наиболее популярных средств представления знаний в интеллектуальных системах — системы продукций (СП), которые являются естественным развитием систем продукций Поста, нормальных алгоритмов Маркова и моделей формальных грамматик. В искусственном интеллекте СП рассматриваются как программные системы определенной архитектуры, в которых преобразование информационной структуры задается в виде множества правил вида

<условие применимости —* действие>. Условие предъявляет требования к текущему состоянию структуры, а действие содержит описание тех операций, которые надо произвести, если структура удовлетворяет этим требованиям.

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

а) универсальность, что обеспечивает возможность создания многообразия проблемно-ориентированных СП;

б) естественная модульность организации: каждое правило представляет собой законченный фрагмент знаний о предметной области;

в) легкость и естественность спецификации знаний, простота их модификации и расширения;

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

д) асинхронность и недетерминированность, что делает СП перспективными для реализации на параллельных ЭВМ.

Первая глава диссертации посвящена исследованию систем продукций.

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

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

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

В разделе 3.2. первой главы введены основные определения, Состояние конъюнктивной-базы данных (¿) определяется ц виде конъюнкции фактов, где каждый факт представляет собою равенство или неравенство термов в исчислении предикатов первого порядка. Через О обозначим множество возможных состояний базы данных. Среди'отношений выделено фиксированное двуместное отношение тип. Множество уаг(с1) задаст переменные, входящие в факты состояния й, Т((1) — типы переменных множества ьаг(<1). Традиционным образом введем понятие подстановки: • .

О = {tl/v1,t■2/v2, ■ ■- ^т/Ут] ,

где — терм, и; — переменная, тип(1{) = тип(и;), г = 1...т. За-, иись (10 означает результат одновременной гимены каждого вхождения переменной в (1 на соответствующий терм , -

С

Для преобразования состояния базы данных введены операции: Для фиксированного d'€ D:

1) операция исключения: elim\d'\ : D —* D

elim[d'](d) = d\d'-

2) операция добавления:а<М[(/'] : D —» D

add[d'](d) = dUd'.

Эти два типа операций позволяют выполнить любое редактирование базы данных.

Программа преобразования базы данных определена как конечная последовательность введенных операций для любых d'G D.

Для каждой программы г определено множество переменных, которое она добавляет в базу данных т(г), и множество переменных ont (г), которое она исключает из базы данных. Программа называется позитивной, если она не содержит операции исключения фактов.

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

Продукция определяется как пара pr =< g, г >, где q — состояние базы данных q 6 D, г — программа, причем qii г связаны соотношением var(q) Э out(r).

Система продукций — это конечное множество пар Рг = {< q, г >}. Будем говорить, что непосредственно выводимо из d\ при помощи продукции pr =< q, г >, (¿1 ¿г), если найдется такая подстановка в, что di. Э qd, а

d2 = r0(qO)U(di\q9).

Если найдется последовательность продукций pri, ..., ргк, рг{ £ Рг, г = к > 0, и состояний базы d0, di, ..., dk таких, что

J Pr 1 J Pr2- prt ,

d0 —► ai —» ... —► dh,

то говорим, что dk выводимо из do, и пишем do —> dk или do pri '_>,prfc clK, a pri, ргг, ..., prk назовем последовательностью применимых к do продукций. Если do dk и Vpr (dk —► d' =>• d' = dk), то dk назовем результирующим состоянием базы данных do-

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

Систему продукций назовем конфлюэнтной, если для любых состояний базы d, d', d" таких, что d —+ d' и d —* d", следует, что найдется d'" такое, что d' A d'" и d" A d'".

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

Утверждение 1. Система продукций, каждая продукция которой имеет позитивную программу, конфлюэнтна.

Утверждение 2. Пусть Рг — система продукций, в которой выполнено условие: для любых pn :=< qi, ri >, ргг =< 92, >, РП ф Р^г (Г(91) П T(q2) = 0) V (T(oui(ri)) П T(q2) = 0),

тогда Рг — коммутативна и устойчива.

Утверждение 3. Пусть для Рг выполнено условие утверждения 2. Если дополнительно выполнено

• для любых рг; =< Qi, Г{ >, prj =< qj,rj >, г, j = 1. .. n

Т(?<)ПТ(|п(г,-))='0, .

• для исходного состояния базы do выполнено условие: для всех подстановок 0;, Oj, если дД- С dg и qjOj С do, то

qiOi П qjOj = 0.'

Тогда Рг 11а do корректна.

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

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

Состоянием дизъюнктивной базы назовем любое конечное множество

с/е 2°, d= {dt}t=i...m- '

'Keller К.М. Л Fundamental Theorem of Asynchronous-Parallel Computation // beet lire Notes in Computer Science. Parallel Processings — 1975. — Vol. 24. — P. 102-112.

Вывод над дизъюнктивной базой данных (вывод-2) определим следующим образом. Пусть заданы с1 = {¿,ь}*=1...т и рг =< <7, г >. Тогда будем говорить, что из й диЗЪЮПКтивПО выводимо = {«/ц;}1Ь = 1."..т+1 п° продукции рг, если найдутся такие 0 (подстановка), к (1 < к < т), что

Ч9Сёк, (1т+1 = г0(д0)и{с1к\Я0).

Очевидно, что при выводе-2 любая система продукций конфлюэнт-на на дизъюнктивной базе. Кроме того, пусть в, — конъюнктивное состояние базы данных. Тогда если вывод-2 для в. заканчивается, то все возможные результирующие состояния, которые можно получить выводом-1, входят в результирующее состояние базы данных вывода-2 в виде дизъюнктивных членов. По сути, вывод-2 представляет собой полный перебор в пространстве возможных состояний. Основной недостаток такого вывода — комбинаторный рост дизъюнктивных членов. В разделе 3.6. первой главы предложены различные варианты оптимизации такого перебора. Одним из вариантов является задание специальных эвристических функций управления выводом.

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

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

• рг-Н означает, что условия продукции рг, активированной на г шаге вывода, должны быть истинны после проверки;

• р)— означает, что условия продукции рг, активированной на г шаге вывода, должны быть ложны после проверки;

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

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

операциями между ними, среди которых выделены: последовательная проверка условий (•), одновременная (,) и альтернативная (;). Такие формулы названы управляющими, а множество продукций с управляющей формулой — структурированной системой продукций.

В разделе 3.7. формально описаны синтаксис и семантика управляющих формул, их свойства, а также определен вывод в структурированной СП. Язык управления позволяет структурировать множество продукций до начала вывода и динамически управлять выводом в зависимости от значений условий применимости продукций.

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

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

Оба предложенных языка являются средством задания эвристик, необходимых для сокращения перебора при поиске решения.

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

а) анализа запросов к базам данных на естественном языке;

б) препроцессоров к доказателям теорем и пакетам прикладных задач;

в) анализа топологических чертежей интегральных схем.

Первые экспериментальные программные продукционные системы

были разработаны автором под руководством А.С.Нариньяни1.

1 Нариньяни A.C., Яхно Т.М. Контекстно-зависимая грамматика с разрывными

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

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

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

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

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

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

составляющим!! в системе восходчщего анализа // Взаимодействие с ЭВМ на естественном языке. — Новосибирск, 1978. — С. 157-165.

Нариньяни A.C., Яхно Т.М. Процедура "сверху-вниз" как недетерминированный параллельный процесс // Computers and Artificial Intelligence. — 1982. — Vol. 1, N

4. — P. 301-315.

Языки:

• универсальные языки программирования,

• языки искусственного интеллекта (языки инженерии знаний).

Инструментальные системы:

• библиотеки инструментальных средств (toolbox),

• оболочки (shells).

• программные обстановки (environments)

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

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

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

Другие показания, субъективные, поступают от специалиста (мастера, врача), наблюдающего за объектом.

Каждому показателю приписывается определенная область значений. Например, температура, кроме количественных значений, может быть "высокая", "низкая", "выше средней" и т.д. Рассуждения ведутся па качественном уровне. Некоторая совокупность показаний характеризует состояние системы. Выделяется ряд состояний, которые можно охарактеризовать как аномальные состояния (отклонения от нормы, аварии, болезни), или Л-состояния.

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

. • какими признаками характеризуется А-состояиие;

• что вызвало конкретное Л-состояние, каковы его причины;

• к каким последствиям выявленное состояние может привести;

• какова история развития процесса;

• какие меры нужно предпринять, чтобы устранить или ослабить обнаруженное А-состояние.

В процессе решения задачи диагностики ЭС проходит следующие этапы:

1. Первичная интерпретация данных: накапливается информация, поступающая в качестве объективных и субъективных данных.

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

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

4. Уточнение множества гипотез: в процессе подтверждения/опровержения гипотезы могут появиться и новые гипотезы, которые тоже необходимо рассмотреть.

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

Описанная модель задач диагностики была реализована в оболочке DI*GEN, предназначенной для создания экспертных систем.

Вторая часть главы 2 содержит описание-формализмов знаний, используемых в оболочке DI*GEN. Средствами представления знаний в оболочке DI*GEN являются системы продукций и фреймы. В данной главе приведен набор базовых фреймов и описан механизм трансформации фреймов в продукционные правила.

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

Основной принцип, реализованный в оболочке DI*GEN, состоит в том, что все проблемные знания описываются экспертом на этапе наполнения оболочки во фреймо-ориентированном стиле, а продукционное

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

Такой подход стал возможен в силу определенной ориентации оболочки DI*GEN на решение задач диагностики. Зафиксировав структуру используемых фреймов, удалось определить операционную семантику продукционных правил и механизм трансформации конкретных фреймов в конкретные продукционные правила.

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

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

Описывая проблемную область, конструктор должен зафиксировать множество параметров, которые характеризуют состояние диагностируемого объекта. Для этого эксперту предлагается фиксированный набор фреймов, заранее определенной структуры (например, фреймы ПАРАМЕТР, СОСТОЯНИЕ, ОПЕРАЦИЯ). Задачей эксперта является создание экземпляров этих абстрактных понятий. Процесс создания базы знаний состоит в заполнении слотов выбранных фреймов конкретными значения,ми, отражающими знания данного эксперта. Например, фрейм для описания А-состояния имеет следующую структуру: фрейм СОСТОЯНИЕ

имя : СТРОКА

код СТРОКА

признаки : АГРЕГАТ из ПАРАМЕТР или СОСТОЯНИЕ

контрпризнаки : АГРЕГАТ из ПАРАМЕТР или СОСТОЯНИЕ

причины : АГРЕГАТ из ПАРАМЕТР или СОСТОЯНИЕ

рекомендации : АГРЕГАТ из ОПЕРАЦИЯ

несовместимость: АГРЕГАТ из СОСТОЯНИЕ

комментарии : ТЕКСТ

Признаки, контрпризнаки, причины, рекомендации, несовместимые

состояния тоже описываются некоторыми фреймами фиксированной структуры.

Так как структура используемых фреймов определяется заранее, это позволяет определить семантику продукционных правил, используемых на этапе консультации. Одним из результатов диссертационной работы является разработка механизма трансформации фреймов в продукционные правила.

Рассмотрим правила преобразования на примере некоторого фрейма из модели технической диагностики.

Пусть имеется описание некоторого состояния: фрейм АВАРИЯ1 : СОСТОЯНИЕ имя : АВАРИЯ1

признаки : {<Пар1, Зн1>, Сост1}

контрпризнаки : {<Пар2, Зн2>, Сост2} причины : {<ПарЗ, ЗнЗ, время-нЗ, время-вЗ>

<СостЗ, время-н4, время-в4>)-рекомендации : {0п1,0п2} несовместимость : {Сост4, СостБ}

Данный фрейм трансформируется в следующие группы правил: группа ПРИЗНАКИ правило 1:

<если <Пар1, Зн1> то АВАРИЯ1 +>. правило 2:

<если Сост1 то АВАРИЯ1 +>.

Интерпретация правила 1: если в диагностируемой системе отмечен параметр Пар1 со значением Зн1, то это является положительным признаком состояния АВАРИЯ1.

Термин "положительный признак" означает, что этот признак повышает вес гипотезы, группа КОНТРПРИЗНАКИ правило 3:

<если <Пар2, Зн2> то АВАРИЯ1 - >. правило 4:

<если Сост2 то АВАРИЯ1 - >.

Интерпретация правила 3: если в диагностируемой системе отмечен параметр Пар2 со значением Зн2, то это является отрицательным признаком состояния АВАРИЯ 1.

Термин отрицательный признак означает, что этот признак работает на понижение веса гипотезы, группа ПРИЧИНЫ

правило 5:

<если <ПарЗ, ЗнЗ> то АВАРИЯ1 через [время-нЗ, время-вЗ]>.

правило 6:

<если СостЗ то АВАРИЯ1 через [время-н4, время-в4]>.

Интерпретация правила 5: если в диагностируемой системе отмечен параметр ПарЗ со значением ЗнЗ, то это может вызвать аварийное состояние АВАРИЯ1 в течение временного интервала [время-нЗ, время-вЗ].

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

В разделе 3 второй главы описана технология конструирования ЭС с помощью оболочки DI*GEN. Для того чтобы построить экспертную систему, конструктору необходимо выполнить два основных действия: наполнить оболочку знаниями (построить иерархию понятий) и собрать готовую экспертную систему.

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

1. Описание областей значений параметров диагностируемого объекта в виде лексических (качественных) значений. Область значений параметра характеризует динамику изменения или спектр принимаемых значений.

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

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

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

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

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

• содержимое базы знаний проверяется на целостность и непротиворечивость;

« фреймы, находящиеся в базе знаний, трансформируются в продукционные правила;

• продукционные правила и начальное наполнение ЭС преобразуется в тексты программ на С++;

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

В заключении второй главы рассматривается этап использования ЭС на примерах экспертных систем КАРДИОЛОГ, предназначенной для дифференциальной диагностики сердечно-сосудистых заболеваний, и экспертной системы ДОМНА, предназначенной для диагностики технологических состояний доменной печи.

Работа экспертной системы КАРДИОЛОГ делится на несколько следующих друг за другом этапов.

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

2. Уточнение гипотез. На втором этапе ЭС пытается уточнить гипотезы, выдвинутые на первом этапе. Для этого система использует стратегию подтверждения гипотез, задавая вопросы врачу на естественном

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

3. Диагноз. В результате работы ЭС сообщает заболевание, получившее максимальный вес, при условии, что этот вес выше некоторого порога, заданного экспертом.

В полном объеме оболочка DI*GEN была реализована совместно с С.Я. Гринбергом на языке С++. Данная оболочка использовалась в ряде организаций, в том числе в НПО "ЧЕРМЕТАВТОМАТИКА" (г.Москва), завод "ХИМКОНЦЕНТРАТ" (г.Новосибирск).

С помощью оболочки DI*GEN разработан ряд ЭС. Система ДОМНА создана совместно с НПО "ЧЕРМЕТАВТОМАТИКА" и предназначена для диагностики оборудования и хода производственного процесса доменной печи. С 1990 по 1993 гг. система проходила опытную эксплуатацию на Магнитогорском металлургическом заводе.

В сотрудничестве со специалистами Института экспериментальной и клинической медицины г.Новосибирска создана ЭС КАРДИОЛОГ для диагностики сердечно-сосудистых заболеваний. Система имеет сертификат качества областного кардиологического центра.

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

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

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

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

Если системы продукций и фреймы уже являются классическими средствами представления, то системы ограничений становятся попу-

лярными только сейчас. Парадигма программирования в ограничениях основана па простой идее: работать не с точно заданными объектами, а с их частично определенными описаниями. Задача при таком подходе описывается в виде множества переменных и системы ограничений над ними. Необходимо найти совокупность значений этих переменных, которые бы удовлетворяли заданной системе ограничений.

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

Широкий класс задач проектирования, планирования и составления расписаний получил название задач удовлетворения ограничениям. Среди методов решения этих задач выделяется метод недоопределенных вычислений, предложенный А.С.Нариньяни в начале 80-х годов. 1

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

Задача, в которой значения переменных не доопределены, представляется в виде недоопределенной модели (Ii-модели).

Рассмотрим произвольную многосортную алгебру Q = (A,F), где А — совокупность элементов щ, каждому из которых сопоставлен соответствующий сорт Si, и F — множество унарных, бинарных и т. д. операций, замкнутых на А. Напомним, что | 5j| — это множество значений сорта 5,-.

Пусть сорт *Si есть множество всех подмножеств Si (т. е. 2'5,1). Алгебре Q поставим в соответствие алгебру *Q = (*А,* F), где "А — это совокупность элементов каждому из которых сопоставлен сорт *Si, и каждая операция * f F является расширением соответствующей операции / £ F на * А. Расширение каждой ш-арной операции / £ F представляет собой m-арную операцию */, чье применение к произвольной совокупности *ai,* аг,... ,* ат таких, что "а,- 6 1, воз-

^arin'yani A.S. Subdefiniteness and Basic Means of Knowledge Representation// Computers and Artificial Intelligence. 1983.-Vol.2.-N.5.-P.443-452.

вращает следующий результат:

" К* а1* а2, ■ ■ ■ ,* От) = и {/(а1,а2,...,ат)}.

г = 1 ...т

Таким образом, результат применения операции */ к аргументам *а\*а.2,...,'ат есть множество. значений, полученных применением операции / к каждому элементу декартова произведения *а1 х* а2 х* ат. Очевидно, что, выполняя операцию */ с элементами из. А, получим элемент из *А, содержащий только одно значение, которое совпадает с результатом вычисления операции / с теми же самыми элементами из А.

В дальнейшем будем называть *<2 недоопределенным расширением С} (или Н-расширением) и каждую */ £* Р — Н-расширением соответствующей операции /, все элементы * А — недоопределенными значениями (Н-значениями), элементы, принадлежащие А, — определенными значениями, а'элемент, совпадающий с А, — полной неопределенностью.

Недоопределенная модель (II-модель) М состоит из следующих четырех множеств:

М = {Х,У/,С,Е),

где X — множество объектов из заданной предметной области; Я — множество отношений (или ограничений) на объектах из X. Каждому отношению г ставятся в соответствие функции fjx, которые называют функциями интерпретации этого отношения. Таким образом, функции интерпретации отношения г позволяют вычислять значения одних параметров данного отношения в зависимости от значений других его параметров. В дальнейшем будем предполагать, что количество функций интерпретации отношения г совпадает с количеством параметров отношения. \¥ — множество функций присваивания, С — множество функций проверки корректности.

С каждым объектом х £ X связаны:

—• недоопределенный тип Тх и множество допустимых операций над его значениями;

— Н-значение *ах\

■—функция присваивания

— функция проверки корректности Сх.

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

х £ Л' и определяющая новое значение объекта как функцию от текущего и присваиваемого значений.

Например, пусть текущее Н-значенне числового объекта х равно множеству {3,6,9,1} и ему присваивается новое Н-значение, равное {1,2,3,4,5}. Предположим, что функция присваивания вычисляется согласно правилу пересечения двух множеств. В таком случае новым текущим Н-значением объекта х станет множество {1,3}.

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

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

Отношения г Е R должны быть функционально интерпретируемыми.

IIa уровне интерпретации Ii-модель представляется двудольным ориентированным графом (Ii-сеть) в комплексе с потоковым вычислительным алгоритмом. В Ii-сети выделены два типа вершин: объекты и функции. Дуги связывают функциональные к объектные вершины. Входящие в вершину-функцию дуги соотносят с ней объекты, значения которых выступают в качестве входных аргументов для функции, исходящие — указывают на объекты, где должна производиться запись вырабатываемых функцией результатов.

Каждой объектной вершине ставятся в соответствие тип и значение. С объектной вершиной также связываются функции присваивания и проверки корректности.

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

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

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

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

В третьем разделе третьей главы описано использование недоопределенных моделей для решения задач с конечными областями значений переменных С8Р(ГО). К задачам этого типа относятся задачи управления и размещения объектов на плоскости, прокладка оптимальных маршрутов, целочисленная оптимизация, раскраска графов и многие другие, которые получили название комбинаторных задач с дискретными областями значений.

В настоящее время не существует эффективного алгоритма для решения произвольной ОБР^Б), хотя каждая задача и решается за конечное число попыток. Поэтому все усилия обычно направлены на то, чтобы уменьшить число этих попыток. Метод недоопределенных вычислений позволяет найти точное решение путем исследования различных гипотез и их следствий. Недоопределенные вычисления позволяют нам получать решения без использования перебора. Математическую сущность перебора оказалось удобно описывать с помощью расширения понятия множества до недоопределенного множества, семантика которого . описывается следующим образом.

Пусть А — {Ах , А?,..'. Ап] и В = {В\, В2,. ■ ■ Вт} — два конечных множества. Тогда пара (А, В) задает нед о определенное множество X, причем гарантируется, что

(1) все значения А^ принадлежат X, и

(2) все элементы X содержатся среди значений В]. Таким образом, А С X С В.

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

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

В общем случае задаются ограничение (}[х,у,г) и Н-значения пе-

ременных х, у, г равные соответственно *а, *Ь, *с. При уточнении II-значения переменной х элемент а из Н-значения *а никогда не отсеивается, если существуют такие 6 £ *6 и с £ *е, для которых выполняется 6, с). По этому правилу отсеиваются только те значения-кандидаты переменной х, которые заведомо нарушают ограничение С}(х,у,г), и поэтому уточнения всегда корректны с логической точки зрения. Ни одно сделанное уточнение не отменяется впоследствии, т.е. недоопре-деленные вычисления являются непереборным алгоритмом. Поскольку Н-значения меняются от менее точных к более точным, результат недо-определенных вычислений не зависит от порядка уточнений.

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

Механизмы перебора встроены в операции над множествами. В частности, построение множества при помощи формирователя вида А = {х|/;1(х)} включает в себя формирование гипотез относительно элементов данного множества и обход в глубину дерева таких гипотез. Вершина дерева изображает момент вычислений, когда, не прибегая к перебору, невозможно ни уточнить значения переменных, ни утверждать, что найдено решение системы Р(х). Такая вершина имеет два поддерева. Они представляют два альтернативных пути поиска элементов А, которые поочередно исследуются.

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

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

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

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

- сохранить математическую естественность описания решаемых задач;

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

- построить систему программирования для решения символьно логических задач.

Например, задача проверки двудолыюсти графа описывается в системе LogiCalc следующим образом.

[1] G={(1,2),(2,3),(3,4),(1,4)};

[2] color={l. .4}—>{'green, 'white};

[3] color(l)='green;

[4] G sub {(i,j)l not color(i)=color(j)}

Рис. 1. проверка двудолыюсти графа за время 0(п2) •

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

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

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

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

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

Понятие прямоугольник может служить примером структурного не-доопределенного типа со следующей структурой:

object Rectangle:

1) R : nrec;

R — недоопределенный прямоугольник. Недоопределенность здесь понимается в следующем смысле: каждый прямоугольник рассматривается как область, через которую может проходить путь, составляющий решение задачи. Если можно показать, что через какую-то часть области данный путь не проходит, то, исключая ее из рассмотрения, мы доопределяем (уточняем) данную область. С помощью такой операции корректным образом сужается пространство поиска решения.

пгес — это тип, описывающий недоопределенный прямоугольник заданием координат его диагонали: (xl,yl,x2,y2), при этом zl < х2 и у\ < у2 , а при уточнении его прямоугольником (xl',yl',x2',y2') должны выполняться неравенства:

х 1 < xl' < х2' < х2\ у\ < 2/1' < 2/2' < 2/2;

2) weigt : double-,

Задание <beca прямоугольника.

3) arr : список указателей на смежные объекты; switch : boolean;

switch = true, если объект участвует в рассмотрении, и switch — false, если объект из рассмотрения исключен.

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

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

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

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

На основании проведенных исследований была спроектирована и реализована инструментальная система для решения задач проектирования на плоскости совместно с аспирантом Г.Б.Чеблаковым.

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

В рамках исследований недоопределенных моделей был изучен механизм интеграции недоопределенных моделей с логическим программированием. Широко известный язык программирования в ограничениях ECLiPSe (являющийся результатом выполнения европейского проекта ESPRIT), предназначенный для решения задач планирования, проектирования, составления расписаний, хорошо зарекомендовавший себя при решении реальных прикладных задач, имеет существенный недостаток, сужающий область его применения. Этот недостаток состоит в отсутствии средств описания ограничений над вещественными типами данных. Все ограничения в ECLiPSe описываются только для целых чисел. Одним из способов расширения возможностей языка ECLiPSe является включение недоопределенных вычислений над вещественными типами данных в язык. Для решения этой задачи библиотека вещественных интервальных функций была встроена в ECLiPSe (реализация выполнена аспирантом В.З. Зильберфайном), и предложен способ описания недоопределенных вычислений в рамках логической парадигмы вычислений. Расширенная версия языка была использована для решения широкого круга прикладных задач, в том числе задач финансового планирования и задач прректирования на плоскости, требующих сложных расчетов.

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

Основные результаты работы

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

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

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

- Разработана технология построения диагностических ЭС. На основе данной технологии реализована проблемно-ориентированная оболочка 01*СЕ]Ч, предназначенная для создания промышленных диагностических ЭС. Средствами этой оболочки реализовано Несколько прикладных ЭС, и обоснована практическая значимость предложенной технологии.

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

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

Основные публикации по теме диссертации

1. Яхно Т.М. Формальная модель вычислений в системах продукций // Известия АН СССР. Техническая кибернетика, -1988.-N2.-C.76-81.

2. Трапезников С.П., Яхно Т.М. ЗАПСИБ: от лингвистического процессора к конструктору экспертных систем // Труды Всесоюзной конференции по искусственному интеллекту. -Переславль-Залесский, 1988.— С.77-85.

3. Яхно Т.М. Потоковые вычисления в системах продукций // Труды Всесоюз.конф. "Параллельное программирование и высокопроизводительные структуры".-Киев, 1988.-С. 124-146.

4. Яхно Т.М. Системы продукций: структура, технология применение. // -Новосибирск: изд. ВЦ СО АН СССР, 1990.-127 с.

5. Гринберг С.Я., Яхно Т.М. Решение задач технической диагностики с использование оболочки DI*GEN // Известия АН СССР. Техническая кибернетика.-1990.-N. 5.-С. 147-153.

6. Гринберг С.Я., Яхно Т.М. DI*GEN: оболочка для создания диагностических экспертных систем // Тезисы докладов II Всесоюз. конф.по Искусственному интеллекту .-Минск, 1990.-С.191-197.

7. Greenberg S., Yakhno Т. DI*GEN: the Shell for Diagnostic Expert System Construction // Current Topics in Informatic Systems Research.-Novosibirsk, 1991.-P.81-99. .

8. Гринберг С!Я., Шустерман В.P., Якобсон И.С., Яхно Т.М. Экспертная система дифференциальной диагностики кардиалгий // Третья конференция по искусственному интеллекту КИИ-92.-Тверь 1992.— Т.2.-С.22-25. .

9. Гринберг С.Я., Смола В.В., Яхно Т.М^ Интеграция базы данных и базы знаний в оболочке DI*GEN // Экспертные системы. Базы данных и базы знаний. -М., 1992.-С.96-100.

10. Яхно Т.М., Френкель М.М. Экспертная система управления ходом доменной плавки // Сталь. -1992.-N.7.-C.15-18.

11. Yakhno Т. Integration of Different Knowledge Representation Means in Knowledge Bases // NATO Advanced Study Institute "Constraint Programming".-Tallinn, 1993 -P.99-106.

12. Greenberg. S., Yakhno T. The Shell DI*GEN: Efficient Implementation of Declarative Knowledge Representation // Proc.International Congress on Computer Systems and Applied Mathematics CSAM'93,1993.-P.368-374.

13. Гринберг С.Я., Яхпо Т.М. Об одной эффективной реализации декларативного формализма в проблемно-ориентированной оболочке // Тезисы докладов II Междун.научно-техн. семинара "Теоретические и прикладные проблемы моделирования предметных областей в системах баз данных и знаний." -Киев, 1993.-С.156-160.

14. Yakhno Т., Greenberg S. Efficient Implementation of Declarative knowledge Representation in Problem-Oriented ES Shell // New Computing Techniques in Physics Research. -World Scientific, 1994.—P. 177—183.

15. Yakhno T. Natural Language Interface for Knowledge Representation System for Mathematics // New Computing Techniques in Physics Research. -World Scientific, 1994.-P.173-176.

16. Yakhno T. Constraint Programming: Subdefinite Models and their Applications // Proc.Third International Congress on Intelligent Techniques and Soft Computing. -Aachen, Germany, 1995.-P. 1897-1903.

17. Яхно Т.М. Программирование в ограничениях: обзор и классификация подходов и методов // Системная информатика. Вып.4. Теоретическое и системное программирование.-Новосибирск: Наука 1995.-С.160-192.

18. Яхно Т.М., Петров Е.С. LogiCalc: интеграция методов программирования в ограничениях и недоопределенных моделей // Программирование. -1996. -N3. -С.70-79.

19. Yakhno Т., Petrov Е. Integrating Constraint Programming and Sub-definite Models // Perspectives'of System Informatics. -Berlin a.o.:Springer, 1996.-P.80-90.-(Lect.Notes Comput.Sci.; Vol.1181).

20. Yakhno Т., Petrov E. LogiCalc: Integrating Constraint Programming and Subdefionite Models // Proc. International Conference "Practical Application Constraint Technology". -London, UK, 1996.-P.357-372.

21. Yakhno T, Cheblakov G, Zilberfain V. FISSURE: Finder of Solutions with Subdefinite Resources // Constraint Databases and Applications.-Berlin a.o.:Springer, 1996.-P.167-185.-(Lect.Notes Comput.Sci.; Vol.1034).

22. Нариньяни А., Семенов А., Телерман В., Швецов И., Яхно Т. Недоопределенные модели и их приложения // Системная информатика.Вып.5.Архитектурные, формальные и программные модели.-Новосибирск, 1996.-С.122-185.

23. Яхно Т.М. Представление знаний в системах ограничений // Актуальные проблемы информатики, прикладной математики и механики. Часть III. -Красноярск: изд. СО РАН, 1996.-С. 158-170.