Искусственный интеллект в САПР

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

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

Рис. 3. Пример интенсиональной семантической сети

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

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

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

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

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

               Фреймовые модели  представления знаний 

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

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

имя_фрейма:ISA-_или_АКО-ссылка

         (описание_слота#1;

                 .     .     .

          описание_слота#N) .

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

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

имя_слота(ЗНАЧЕНИЕ:значение_слота;

          ТИП:тип_значения_слота;

          УМОЛЧАНИЕ:значение_по_умолчанию;

          ДЕМОНЫ:имена_процедур-демонов;

          СЛУГИ:имена_процедур-слуг)

    Обязательными  в структуре слота являются  только ячейки ЗНАЧЕНИЕ и ТИП,  обеспечивающие интерпретируемость  и структурированность в представлении  знаний. Фрейм, все слоты которые характеризуются только значением и типом, полностью аналогичен структуре (struct) языка C. Для адресации к структурным единицам фрейма используется конкатенация символов имя_фрейма.имя_слота.имя_ячейки. Для отображения во фреймовом представлении свойств связности и активности знаний служат три последние ячейки слота. Ячейка УМОЛЧАНИЕ содержит стандартное ("стереотипное", предполагаемое, ожидаемое) значение слота, что дает возможность манипулировать фреймами в недоопределенных ситуациях, когда отсутствует конкретная информация о целом ряде аспектов объекта или явления. С помощью ячеек ДЕМОНЫ и СЛУГИ задаются имена присоединенных к фрейму процедур.

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

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

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

   Пример. Фрагмент интенсиональной части БЗ на основе фреймов для рассматриваемого нами примера с башней может иметь следующий вид:

башни: сооружения

   (крыша

       (ЗНАЧЕНИЕ: крыши;

        ТИП: ссылка);

    ствол

       (ЗНАЧЕНИЕ: стволы;

        ТИП: ссылка;

        СЛУГИ: расч_кол_бл);

    высота 

       (ЗНАЧЕНИЕ: <>;

        ТИП: положит. действ. число;

        ДЕМОНЫ: расч_высоты);

    имеет

       (ЗНАЧЕНИЕ: громоотвод, маяк;

        ТИП: текст);

    цвет

       (ЗНАЧЕНИЕ: <>;

        ТИП: множество {красный, . . . , фиолетовый};

        УМОЛЧАНИЕ: желтый) )

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

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

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

башня_1: башни

   (крыша

       (ЗНАЧЕНИЕ: крыша_1;

        ТИП: ссылка);

    ствол

       (ЗНАЧЕНИЕ: ствол_1;

        ТИП: ссылка) ;

    высота

       (ЗНАЧЕНИЕ: 12;

      ТИП: положит. действ. число;

      ДЕМОНЫ: расч_высоты);

    цвет

       (ЗНАЧЕНИЕ: <>;

      ТИП: множество {красный, ..., фиолетовый};

      УМОЛЧАНИЕ: желтый) )

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

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

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

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

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

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

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

                           Продукционные системы (ПС)

    Под ПС будем понимать систему <W, P, I>, состоящую из трех компонент, где W - рабочая память, содержащая информацию, характеризующую текущее состояние предметной области, P -множество продукций вида ЕСЛИ условие, ТО следствие, применимых к W; I - интерпретатор (решатель), управляющий применением продукций. Общая постановка задач при использовании ПС - даны начальное W0 и конечное Wk состояния рабочей памяти, необходимо найти путь (пути) из W0 в Wk, реализуемый последовательностью применения продукций из P.

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

    Множество продукций P составляет основу интенсиональной части БЗ. Основное достоинство ПС как раз состоит в том, что с помощью продукций наиболее адекватно отражаются механизмы принятия решений человеком, основанные, как показывают результаты психологических исследований, на правилах типа "причина-следствие", "посылка-заключение", "условие-действие". Левая часть продукции (ЕСЛИ ...) представляет собой заданное в декларативной форме условие ее применимости, выраженное в виде объединенных связками И, ИЛИ, НЕ требований к элементам W. Оценка условий применимости продукций осуществляется интерпретатором. Правая часть продукции (ТО...) может иметь декларативную или процедурную форму и задает изменения, которые необходимо выполнить в случае истинности условия в левой части. Если правая часть продукции задана в декларативной форме, то предписываемые ею изменения в W (удаление, модификация, добавление элементов) реализуются интерпретатором. В альтернативной форме правой части подразумевается наличие ассоциированной с продукцией процедуры, непосредственно выполняющей в W все необходимые изменения. В ПС, W которых организуется с использованием представлений на основе фреймов или СС, целесообразным является представление и самих продукций в рамках этих формализмов (в виде специальных фреймов-продукций и фрагментов СС) - этим достигается единообразие в организации компонентов ПС.