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

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

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

ИВАНИЩЕВ

Алексей Вячеславович

УДК 681.322-181.4

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

СПЕЦИАЛЬНОСТЬ 05.13.16 — ПРИМЕНЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ, МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ И МАТЕМАТИЧЕСКИХ МЕТОДОВ В НАУЧНЫХ ИССЛЕДОВАНИЯХ

АВТОРЕФЕРАТ

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

САНКТ-ПЕТЕРБУРГ — 1992

Работа выполнена в Санкт-Петербургском институте информатики и автоматизации РАН.

Научный руководитель — доктор физико-математических наук, профессор СЛИСЕНКО А. О.

Официальные оппоненты: доктор технических наук, профессор ГОРОДЕЦКИЙ В. И. кандидат технических наук, старший научный сотрудник ТАРАКАНОВ А. О.

Ведущая организация: Военный инженерно-космический краснознаменный институт имени А. Ф. Можайского.

Защита состоится « » 1992 г. в часов на

заседании специализированного совета Д.003.62.01 при Санкт-Петербургском институте информатики и автоматизации РАН но адресу: 199178, Санкт-Петербург, 14 линия, д. 39.

С диссертацией можно ознакомиться в библиотеке специализированного совета Д.003.62.01.

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

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

кандидат технических наук В. Е. МАРЛЕЙ

: " ... , . - - _ п _

¡эЛБ-'Л'Л.'I !

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

Актуальность^

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

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

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

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

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

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

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

Многочисленные попытки применения экспертных систем пока-

- л -

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

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

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

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

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

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

Разработана формализация рассматриваемой предметной «•блжчи ('. учетом особенностей поставленной задачи.

Впервые разработан метод обеспечения полноты диагностических :->кепертн\1х знчний с реализацией технологии соответствующе г- > интерактивного итерационного процесса, разработаны явристи-•".•-ские алгоритмы анализа диагностических знаний на полноту.

Разработан оригинальный логико-графический язык ПРЕДЛОГ .'•'Я'1 ь'-аимодейстьи* эксперта с базой знаний, основанный на идео-

графическом подходе и ориентированный на непрограммирующего эксперта.

Практическая ценность работы.

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

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

- Реализован экранный графический редактор диагностических экспертных знаний, использующий разработанный автором проблемно-ориентированный логико-графический язык ПРЕДЛОГ.

Апробация.

Результаты работы имеют практические внедрения. Поставленная задача диагностирования решена путем внедрения диагностической инструментальной системы ИДЭКС в Военном инженерно-космическом институте имени А.Ф.Можайского и в научно-производственном объединении "Красная звезда".

Метод обеспечения полноты базы знаний диагностической экспертной системы апробирован в результате его применения для экспертной системы ИДЭКС по месту ее внедрения (ь НПО "Красная звезда"). В результате применения процедуры определения неполноты были сформулированы дополнительные экспертные правила, отсутствовавшие во внедренной версии БЗ.

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

Результаты диссертационной работы докладывались на 1-й отраслевой научно-технической конференции молодых специалистов и ученых Министерства общего машиностроения ( г.' Харьков, сентябрь Iе©? г.), на научно-технических конференциях молодых специалист!! в КС "Арсенал" им. М.В.Фрунзе (".С-Петербург, 'июль 1987 г., апрель 1988 г.), на научных семинарах в Военном инженерно-космическом институте имени А.Ф.Можайского ( г. С.-Петербург,

январь 1992 г.) и в Санкт-Пе'герОургском институте информатики и автоматизации РАН (г. С-Петербург, апрель 199Е г.'.

Публикации.

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

С^^тща_и_объем_дассертащюнндй_работыЛ

Диссертация состоит из введения, четырех глав, заключения, списка использованной литературы и приложений. Объем диссертационной работы: 170 страниц, 16 рисунков и 1-4 таблиц.

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

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

- Разработанный логико-графический язык ПРЕДЛОГ является эффективным средством взаимодействия эксперта с базой знаний в экспертных системах, решающих задачи диагностики, основанные на анализе измерений.

- Редактор диагностических экспертных знаний, реализующий логико-графический язык ПРЕДЛОГ, является основой для инструментального средства построения диагностических экспертных систем рассматриваемого класса.

- Реализованный прототип - инструментальная система ИДЭКС -решает поставленную задачу диагностирования.

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

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

Во___введении обосновывается актуальность проблемы.

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

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

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

Для оценки функционирования ОД используется множество физических параметров Р - { р1, р2 , ... р^ }, каждый из которых связан с датчиком, размещенным на ОД.

Входной информацией для системы диагностирования является массив дискретных значений множества Р физических параметров ОД, измеренных за некоторый интервал времени - интервал измерений Т = ^п'^' где ~ начало интервала, ^ - конец интервала.

Изменения значений физического параметра р^ описываются непрерывной функцией £^(1;), определенной на интервале измерений Т. Каждая функция 1^(1;) представлена в массиве измерений множеством своих дискретных отсчетов - троек: Р = (1^, Т^), где - имя параметра, У^ - значение- параметра, Т^ - время регистрации значения параметра.

Процесс диагностирования заключается в -последовательном определении состояния ОД в каждый момент времени ^ е [1^,1^]. В результате формируется текстовый протокол функционирования ОД за интервал Т, который выдается специалистам по управлению. Протокол содержит описание процесса функционирования ОД, с указанием неисправностей и рекомендаций по их устранению.

Представление состояния ОД з^) в виде вектора дискретных значений физических параметров Х(1;) = Г2(10, ... ^Ш)

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

(Ю. ^(Ю, , Гк(1;) —» э^Ю.

В качестве экспортных знаний рассматриваются логические правила вывода в секвенциональной форме виДа ЕСЛИ ... ТО, связывающие диагностические заключения с совокупностью значений измерительных параметров, качественными характеристиками их изменений и взаимными количественными соотношениями.

С точки зрения диагностирования определяющей информацией для

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

= {]-<» [ц.,^.,], •■■ » С),

где: ч1 < ч2 < ... < - границы интервалов из множества действительных чисел;

£ . а.| 1 - замкнутый интервал, вырождающийся в точку; ] ч2 [ - открытый интервал.

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

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

I £ ч

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

В1 & В2 & ... Вп —* Б ( 1 )

Каждое условие В-^ в правиле определено относительно одного из параметров р^, причем, в каждом правиле допускается не более одного условия относительно некоторого параметра р^.

Условия в правилах имеют следующий дизъюнктивный вид: В1(Р1) = (11г V 11(1ц.1) ^(г+ет))' >

где: С 1.г, 11(1Ч1) .....11(1Чж) > = I.'; I.' с I.;

= { , ,..., ) - множество числоеых

интервалов, определенных для параметра р^ в рассматриваемой БЗ;

1 = 1 ,к; г = 1 ,п£; у/ = 0,п^; 1 - номер условия в правиле. Множество 11' = { 11г, 11(г+1), .... ^1(Г+,у) ) представляет собой множества • интервалов выполнимости условия е данном правиле И, а множество ' - множество интервалов невыполнимости условия В1, причем: * и =

В случае, когда в процессе вывода решения применено правило, антецедент которого содержит только условия вида (2 ), еыбод соответствующего диагноза имеет единичную длину И: 11=1.

В^ также может иметь вид Б. В этом случае, условием выполнимости В-^ является выполнимость .другого правила - с

консеквентом В. Тогда при выводе мохет возникнуть "зацепление" двух правил, реализуемое с помощью правила "сечения", являющегося аналогом правила сокращения посылки ( modus ропепз):

Г —> с Л с —> в

Г Л —> В ■

При этом длина вывода h оказывается всегда больше 1.

Для диагностической базы знаний рассматриваемого класса на практике существует ограничение на длину вывода: в среднем h = 1.75 и не. превосходит 3. Особенностью БЗ также является то, что в ней выполняется требование однозначности диагноза,- т.е.-отсутствуют правила вида:

В1 & В2 & ... Вп —► D1 v ... v Dz.

Во_второй__главе рассмотрены основные средства построения

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

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

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

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

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

Логико-гра^гееский язык взаимодействия с диагностической базой знаний ПРЕДЛОГ (Представление ЛОгико-Графическое) относится к языковым средствам инструментальной системы диагностирования.

Рассмотрены два вида представления операторов языка ПРЕДЛОГ с точки зрения их использования в экспертной системе: внутренний (машинный) и внешний (пользовательский). Представление правил на машинном уровне - это синтаксическая/конструкция, соответствующая нотации логических формул в системе логического программирования Турбо-Пролог, которая используется в качестве машины логического вывода. Каждому оператору языка (см. табл.1) на внешнем уровне соответствует идеограмма - рисунок, несущий смысловую нагрузку. Например, для оператора, имеющего следующее содержание: "значение параметра = N находится в пределах допусковою интервала [а,Ь] в течение интервала времени [1:1,1:2 ]",

определены: предикат Р1 (Н ^»р^.а.Ь), логическое условие выполнимости предиката:

3 а 3 Ь |— а < ^(1;) < Ь для V t с »1Д21, а также соответствующая идеограмма (см. Рис.1). Полнота разработанного семантического базиса определяется экспериментальным путем, который на практике показывает его достаточность для описания состояний рассматриваемого класса объектов. При этом язык ПРЕДЛОГ является открытой системой.

Показано применение оператора идентификации (см.табл.1, п.13) для представления консеквентов (заголовков) правил.

Продемонстрирована- возможность использования языка ПРЕДЛОГ для описания достаточно сложных состояний ОД.

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

Таблица 1.

Перечень базисных операторов языка ПРЕДЛОГ

Описание отношения Предикат

1. Значение параметра х находится в допуске [а,ъ] в течение интервала времени [1;п^к] * P1(tn,tk,x,a,b)

2. Параметр х имеет значение а P2(tn,tk,x,a)

3. Значение параметра х больше а F3(tn,tk,x,a)

4. Значение параметра х меньше а F4(tn,tk,x,a)

5. Значение параметра х изменилось скачком на величину а.на время Т1 P5(tn,tk,x,a,Ti)

6. Значение параметра х изменилось скачком на величину -а на время Т1 F6(tn,tk,x,a,Ti)

7. Значение параметра"х.увеличилось до величины а P7(tn,tk,x,a)

8. Значение параметра х уменьшилось до величины а F8(tn,tk,x,a)

Q. Значение параметра х возрастает от величины а до величины Ь P9(tn,tk,x,a,b)

10. Значение параметра х убывает от величины а до величины Ъ P10(tn,tk,x,a,b)

11 . Значение параметра х больше значения параметра у P11(tn,tk,x,y) •

12 ..Значение параметра х меньше значения параметра у F12(tn,tk,x,y)

13 . Объект С! находится в состоянии 0 P13(tn,tk,Q,C)

14 . Значение параметра х соответствует значению параметра у: х=Г(у) P14(tn,tx,x,f(y))

15 . Временной сдвиг на длительность Т F15(tn,tk,T)

16. Вычисления по алгоритму, содержащемуся в файле с именем PR0C P16(tn.tk.PROC)

* - далее в описании других отношений слова "в течение интервала времени П.пДк]" - опущены и подразумеваются по умолчанию.

Рис.1. Структура идеограммы оператораяаька ПРЕДЛОГ, имеющего следующее семантическое содержание: "значение параметра р^ = N находится в пределах допускового интервала [ а, Ъ ] в течение интервала времени [ 1;1, t2 ]".

1 - поле изображения идеограммы,

2 - поле идентификатора физического параметра,

3 - поле значения предметных констант,

4 - графические элементы идеограммы.

После ввода правила осуществляется автоматическая генерация машинного представления нового правила и контроль БЗ на противоречивость с учетом нового правила.

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

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

Метазнания в рассматриваемой системе'описывают иерархическое факторизованное пространство поиска решений и представляют собой описание ОД в виде дерева С(Е,и), где Е - множество вершин графа, соответствующих функциональным элементам диагностируемого объекта, II - множество ребер, связывающих вершины графа-. На множествах Е и и определено отношение функциональной подчиненности элементов ОД. Элемент функционально подчинен элементу если существует ориентированная дуга и^, соединяющая вершины е-^ и е1+1, соответствующие ^ и ^ (1 - уровень иерархии ).

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

Качество полученного решения при этом зависит от полноты БЗ экспертной системы, т.е. от того, насколько полно представлены возможные' диагностируемые состояния каждого элемента ОД.

В__третьей__главе представлен разработанный автором метод

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

Практика показывает, что »М^кглрность. применения ЭС полностью определяется ■ качеством и ч<>лнотой используемых

- 14 -

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

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

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

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

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

Если Б - множество возможных состояний ОД, то для каждой диагностической БЗ существуют два непересекающиеся подмножеств?; Бр и Бп, называемые соответственно областью полноты и областью неполноты БЗ, причем: Б = Бр II Бп. Область полноты .Бр состоит из тех состояний объекта диагностирования, для которых существует

- 15 -

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

Процедура определения неполноты ликвидирует или редуцирует область неполноты для данной БЗ путем формирования символьных описаний области неполноты и предъявления их эксперту.

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

Для определения свойства полноты (неполноты) диагностической БЗ используется понятие диагностического признака, как пропозициональной переменной а^, определяющей факт вхождения значения физического параметра р1 = С в соответствующий числовой интервал: с <= 11Л е 1г

Определение: БЗ диагностической ЭС является полной тогда и только тогда, когда для каждого входного набора диагностических признаков из правил, входящих в БЗ. выводим какой-либо диагноз.

Т.е. для полной БЗ и любого дойустимого набора значений физических параметров р1, ... .р^ имеется диагностируемое состояние Б, определяемое пропозициональной переменной такое, что:

БЗ I— р1, — «—» Б-р

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

Если ео всех правилах БЗ относительно одного параметра р^ определено М условий вида В, то множество формируется на основе следующего множества констант: С = и Ст,

где Ст - множество числовых констант, используемых в условии Вт, т = 1,М.

Процедура определения неполноты БЗ начинает свою работу с проверки выполнения необходимого условия полноты БЗ. Для каждого

из условий Б(р^), определенных относительно параметра р^, определяются множества интервалов выполнимости этих условий в кавдом из правил R1,.. .RL: (R1), (R2),.. (RL) .Тогда необходимое условие полноты диагностической БЗ будет выглядеть следующим образом:

V i V J 113 с { Х1* (R1), (Е2), ... ^'(HL) }, где: i = bk; 3 = TTn^; iij = card ( Ij ).

Содержательно данное условие может быть интерпретировано как необходимость участия кавдого из числовых интервалов I^j е Ij для параметров р1, ... , р^ в качестве интервала выполнимости хотя бы одного из условий в правилах БЗ.

Разработанные алгоритмы применяются к БЗ, модифицированной относительно исходной и состоящей из приведенных правил, т.е. из правил, содержащих условия вида ( 2 ), с длиной вывода h = 1. Количество приведенных правил на практике оказывается приемлемым - не больше общего числа правил, т.к. количество "зацеплений" и средняя длина вывода невелики.

В Т-алгоритме (для табличного представления области невыполнимости правил) используется таблица А, состоящая из диагностических признаков а^, определенных для каждого из параметров р^ е Р: А = { а^, а12, •■• а]П1' а21' а22' ""

а2п2'' •■■ ' ak1' ak2' aknR K

Обычно диагнозы определяются значениями лишь1 некоторых из физических параметров и в БЗ используются правила с условиями, определенными относительно соответствующего множества параметров Рд с р. Элементы множества PR называются параметрами правила R.

Таблица А используется для представления наборов значений диагностических признаков a^j, выполняющих некоторое правило R, т.е. для представления области выполнимости AR правила R. Элементами таблицы AR являются значения а^, определяемые следующим образом: а^j = 0, если а^ не участвует в условии B(pj). Иначе, а^ = I.

Например, для правила: В(р.|) В(р3) В(р1с_1) ВСр^) —»- D, имеющего в терминах диагностических признаков а^ следующий вид:

(а,2 V а13 V а14) & (а33 V а34 V ... V 33^) & а(к_, )3 &

& (ак1 УНк2 V а^) —* D,

область выполнимости может быть представлена с- помощью таблицы Ад (см. рис.2).

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

к П1

& V а,, (1. V <эи V ... V (Ц,

1=1 3=1 13 1 <£ т;

где: к - количество физичесгапс параметров, п^ - мощность множества В = { сЦ, (3^, ... (12 } - множество диагнозов.

Каждое правило Н определяет некоторый диагноз й^:

& В^ -> йд, где 1 - номер параметра правила.

1

Учитывая, что В-^ = V а^ г+у?, получаем формулу ( 3 ), которая определяет область полноты БЗ, т.е. множество диагнозов, выводимых в БЗ:

к П1

& V аи V & Вщ, ( 3 )

1=1 ¿=1 и 1

<

где и - количество правил в БЗ.

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

\ 1

I *=

П1

V а11 1 ¿=1 13

ММ (4}

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

Т-алгоритм позволяет оценить "вклад" каждого правила в обеспечение полноты БЗ. Каждый набор признаков в таблице А образует

путь »7, состоящий из участков: Су^ _____Г Участок связывает

дрй признака, находящиеся в смежных рядах 2- и г+1 таблицы

!'<"№. рИ'-. £).

"11

а11 а12 а13 а14 • • ■ а1п1

а21 а22 а24 . . . а2п2

№12

а32 а33 а34 • " • аЗпЗ

"13

а41 а42 а43 а44 " ■ ' а4п4

а(к-1)1 а(к-1)2 а(к-1)3 а(к-1)4 • • а(к-1 )п(к-1)

И1 (к-1) ^^ "2 (к-1)

ак1 ак2 акЗ ак4 акпк

Рис.2. Представление -области выполнимости правила й с помощью таблицы А^ .

- область выполнимости правила И;

- один из наборов значений а^, выполняющих правило Н;

- один из наборов невыполнимости правила Н;

«12, *13, ... «1(к_п} и {«21> «22, «23, ... «2(к-1)} - участки, образующие соответственно, наборы и Ир.

- 19 -

Количество путей, проходящих через данный участок * в исходной таблице А, называется полной мощностью М^л) данного участка и вычисляется по формуле:

Mf(w) = п, • IL, ..... п^ . 1^2 •

п.

к'

где п^ = card - мощность множества числовых интервалов, определенных для параметра pj. При этом, участок w соединяет любые два элемента таблицы А, находящиеся соответственно в г-м и (г+1)-м рядах таблицы.

Мощность множества U(R,w) = { W^, Wg, ... , Ws> всех путей, выполняющих правило R, таких, что для каждого t: w е Wt, называется реальной мощностью Ы^д wj участка w относительно правила R. Значение реальной мощности Мщ wj участка, соединяющего любые два элемента, находящиеся соответственно в г-м и (14-1 )-м рядах таблицы AR, определяется по формулам:

M(R,w) = Z1 1 z2 ( 5 >

k

где: z1 = | | dBfp^, I * r, i * r+1 ( 6 )

1=1

для всех pj, являющихся параметрами правила R, т.е. относительно которых в правиле R присутствуют условия В(р^);

при этом: dBipj) - количество диагностических признаков параметра. plf участвующих в дизъюнкции условия В(р^); к

z2 = J | nlf 1 t г, 1 yt r+1 ( 7 )

1=1

для всех plf не являющихся параметрами правила R, т.е. не участвующих в правиле R;

п^ = carl Ij - мощность множества числовых интервалов, определенных для параметра р^.

Область выполнимости правила R содержит определенное количество наборов - путей, проходящих через участки таблицы Ад. Значение реальной мощности М^ wj участка w представляет собой числовую оценку "вклада" данного участка w в обеспечение полноты БЗ относительно правила R.

- 20 -

Сравнивая сумму значений реальных мощностей участка Ы^ ^, найденных относительно каждого из правил по формулам (5) - (7), со значением полной мощности данного участка' М^.(ет), можно получить числовую оценку У(уг), характеризующую количество путей, проходящих через этот участок для всего множества правил, т.е. для данной БЗ:

Ь

У(и) = М^я) - 2 М^ где Ь - количество правил в БЗ.

1

При этом, если У(т?) > 0, то БЗ обладает свойством неполноты относительно данного участка, т.е. существуют пути И, такие, что « ( I, и для которых невыполнима формула ( 4 ).

Если У(и) < О, то БЗ избыточна относительно данного участка.

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

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

■ В П-алгоритме решения той же задачи проверки свойства полноты базы знаний диагностической ЭС используются пропозициональные переменные а1, ___ ак для представления наборов значений

параметров р1, ... рк, выполняющих правила. Переменная а^ = 1, если параметр р^ имеет такое значение, что условна В(р^) ■ выполнимо, т.е. если значение р^ лежит в одном из интервалов выполнимости е условия В(р£). В противном случае а.^ = 0.

Набор переменных а1, а2, ... ак, выполняющий правило и, может быть представлен функцией: (И) = а1 а2 ... ак- Тогда, наборы невыполнимости правила и могут быть объединены в функцию:

а1 а2,,> ^ 7 а1 а2 '■■ ^ У а1 а2 • ак•

.Операции элементарного поглощения Аи V А = А и обобщенного

- 21 -

склеивания по методу Блейка АС V ВС = АС V ВС V АВ дают сокращенное представление функции: £0(й) = а1 V а1 ^ V а1 ^ V

... V а1 а^ = а1 У а1 ( а^ V Е^ V ... V а^ ).

Используя соответствие между значениями переменной а^ и множествами интервалов выполнимости и невыполнимости

1"(Р£) условия в(р£), область невыполнимости э • всего правила и может быть записана:

X' ' (р1 ) У 14р.,) 1"(Р2) V ... V 1'(Рк_1) Г'Чр^), (8)

где р1, ... рк- параметры правила и.

Например, с использованием вспомогательных обозначений: = А1, 112 = А2, ... , 121 = В1, 122 = В2, ... и т.д., при условии, что: 1^) = { А1, А2, АЗ, А4, А5 }; 1(р2) - { В1, В2, ВЗ, В4, В5 }; 1(р3) = { 01, С2, СЗ, 04, 05, Об, 07 }, область невыполнимости Зг'(И) данного правила и:

(А1 У А2) (В2 у ВЗ V В4) (03 у 04 у 05) —» Бд, может быть записана следующим образом :

Б^Ш) = АЗ У А4 У А5 У (А1 У А2) (В1 У В5) У (А1 У А2) (С1 У С2 У Сб V С7).

Область неполноты ВЗ соответствует области невыполнимости всех правил, входящих в ВЗ, т.е. область неполноты зг' всей БЗ: зг- = П 8Г' (1^), где 1 - номер правила в БЗ.

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

определении пересечения областей неполноты всех правил:

(( ... (8р'(1Ц) П з^О^» п вр,<нэ>) ... П зг'(нь) = вг»,

где ь - количество правил в БЗ.

Учитывая, что пропозициональные наборы, выполняющие одновременно две булевские функции í1 и 12, могут быть представлены третьей булевской функцией г = & 12, то, функция, описывающая совместные наборы выполнимости множества функций ^...,ГЬ, может быть определена как:

= (( ... & тг)) & г3) ... & гь). ( 9 )

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

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

Операция определения пересечения зг*(т-Н2) областей неполноты двух правил зг'(Ш) и зг'(И2) заключается в попарном сопоставлении всех конъшктов, входящих в форму л^, описывапцие Ег'(И1) и Бг' (Л2). При определении результата операции попарного сопоставления учитывается наличие общих параметров, присутствующих в обоих конъюнктах, а также наличие совпадающих обозначений интервалов для таких параметров.

Так, для конъюнктов •= ( А1 V А2 V аз ) ( сэ V 04 ) ( И Т ВЗ Т В4 V Ю ) И к^ = ( АЗ V А4 V А5 ) ( ШУП2ТВЗ ) множество общих парметров - { а, б }, множества совпадающих обозначений интервалов - С АЗ } и { В2, гз >. Тогда - результирующий КОНЬШКТ к^д - АЗ (1)2 V 1)3) (С3 V С4).

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

один набор значений параметров р1.....р^ не может одновременно

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

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

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

В данной главе показано применение Т- и П-алгоритмов для решения двух практических задач - устранения неполноты баз знаний

по диагностированию пароводяной энергетической установки и системы электропитания, входящих в состав систем обеспечения технических объектов.

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

1_Н9твертой_главе рассмотрены вопросы практической реализации результатов исследований.

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

Рассмотрена реализация в системе ИДЭКС логико-графического •редактора экспертных знаний, поддерживающего язык ПРЕДЛОГ; ■зредств настройки под конкретный объект диагностирования и представления. метазнаний, обеспечивающих организацию выбранной стратегии поиска решений. Кроме того, рассмотрены интерфейсные средства системы ИДЭКС, включающие в себя три уровня взаимодействия с пользователями: с основным пользователем ЭС - оператором по диагностированию; с инженером по знаниям и сопрововдению системы; с экспертом - специалистом в вопросах диагностирования.

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

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

Массив измерительной информации, использованный для проверки работы экспертной системы, моделирует в общей сложности 500-1500

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

Прототип диагностической инструментальной системы реализован на персональном компьютере типа РС АТ и функционирует под управлением операционной системы РС БОБ, версии 3.3. Объем используемой оперативной памяти компьютера составляет 380 КБайт, средняя скорость получения одного диагноза составляет 0,5-4 с, в зависимости от сложности диагностируемой ситуации и количества примененных диагностических правил. Длительность программирования составила 8 чел/мес.

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

ЗАКЛЮЧЕНИЕ

В результате проведенной научно-исследовательской и практической работы автором была реализована инструментальная система ИДЕКС для построения диагностических ЭС, ориентированных на анализ результатов измерений.

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

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

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

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

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

- формализация рассматриваемой предметной области с учетом особенностей поставленной задачи;

- разработка метода обеспечения полноты диагностических экспертных знаний с реализацией технологии интерактивного итерационного процесса, разработка эвристических алгоритмов анализа диагностических знаний на полноту, в двух реализациях: Ти П-алгоритмы;

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

Кроме того работа имеет также ноеьш практические результаты:

- инструментальная диагностическая система ИДЭКС, решающая поставленную задачу диагностирования по разработанной технологии с использованием методологии систем, основанных на знаниях;

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

логико-графический экранный редактор диагностических экспертных знаний;

- алгоритмические средства, реализующие эвристический подход к стратегии поиска решения, основанной на методе иерархической "генерации и проверки";

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

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

(. Ивангац-гь А.Ь. Система автоматизации оперативной функциональной диагностики на основе идеографического представления.- /'/Вопросы алгоритмического моделирования гугжннх систгм.. л.: АН СССР, ЛИИАН, 1988, 235 с. с ил.

2. Иванищев A.B. Экспертная система диагностирования сложных абъек/гов.- Л.: АН СССР, ЛИИАН, препринт No 104, 1989,- 33 с.

3. Иванищев A.B. Алгоритм обеспечения функциональной полноты экспертных знаний. - // Алгоритмическое моделирование: инструментальные средства и модели., СПб.: РАН, СПИИРАН, 1992.

4. Иванищев A.B. Средства обеспечения функциональной полноты экспертных знаний. - // Методы автоматизации обработки информации., СПб.: РАН, СПИИРАН, 1992.

Подписано к печати 5. И О ЭХ, . Заказ 1%%2 , Тираж

формат бумаги 60x84 1/16, печ.л. Бесплатно. Ш - 3 "Ленуприздата".

191104 Ленинград, Литейный пр., дом № 55.