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

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

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

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

 

   Пример. ПС для рассматриваемой нами предметной области с башнями может быть реализована следующим образом.

    Поскольку предметная область проста, то W можно реализовать в виде линейного списка троек (объект атрибут значение). Начальное состояние W в такой форме показано ниже:

      (крыша  форма призма)

      (крыша  форма плоск.)

      (призма  высота 4)

      (плоск. высота 1)

      (блок  форма цилиндр)

      (блок  форма паралл.)

      (цилиндр  высота 5)

      (цилиндр  высота 3)

      (паралл. высота 4)

      (паралл. высота 2)

   Целью использования ПС в этом примере пусть будет проектирование башни любой высоты, тогда конечное состояние W должно содержать тройку (башня высота X), где Х - обозначение переменной (т. е. высота проектируемой башни в данном случае для нас безразлична).

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

ЕСЛИ НЕ (ствол  X Y) И (блок форма F) И (F высота H),

      ТО  ДОБАВИТЬ [(ствол кол_бл. 1), (ствол высота H)]

ЕСЛИ НЕ (ствол  X Y) И (блок форма F) И (F высота H1) И (F высота H2),

      ТО  ДОБАВИТЬ [(ствол кол_бл. 2), (ствол высота H1+H2)]

ЕСЛИ НЕ (башня  X Y) И (крыша форма F) И (F высота H1) И (ствол высота H2),

      ТО  ДОБАВИТЬ (башня высота H1+H2)

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

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

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

    Недостатками являются:

1. относительно низкая эффективность, связанная с необходимостью сопоставления левых частей большого количества продукций с объемной W (в реальных ПС на это расходуется 90-98% времени);
2. сложность контроля правильности функционирования.

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

                                  Интерпретатор в ПС

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

1. направление поиска;
2. режим использования продукций;
3. способ разрешения конфликтов между продукциями;
4. метод поиска.

 
 

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

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

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

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

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

1. упорядочение продукций,
2. упорядочение данных в рабочей памяти,
3. специальные случаи условий продукций,
4. информация о предыстории применения продукций.

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

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

                              Методы поиска решений в ПС

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

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

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

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

    Алгоритм этого вида поиска для нахождения одного какого-либо решения кратко может быть представлен в следующем виде:

1. поместить в очередь корневую (начальную) вершину;
2. выбрать из очереди вершину и раскрыть ее (если очередь пуста, то целевая вершина недостижима);
3. если среди дочерних вершин есть целевая, то конец;
4. поместить список дочерних вершин в конец очереди и перейти к п. 2.

 Алгоритм поиска  в глубину выбирает вершины  для раскрытия в порядке, обратном  их порождению:

1. поместить в стек корневую (начальную) вершину;
2. выбрать из стека первую вершину и раскрыть ее (если стек пуст, то целевая вершина недостижима);
3. если в списке дочерних вершин есть целевая, то конец;
4. список дочерних вершин поместить в стек и перейти к п. 2.

Пример. Рассмотрим простую формальную продукционную  систему, начальное состояние рабочей  памяти которой обозначим А, а конечное - Р. Множество продукций составляют следующие: Р1: А->В Р7: D->H P13: F->N

P2: A->C P8: D->I P14: G->O

P3: A->D P9: E->J P15: G->P

P4: B->E P10: E->K P16: H->Q

P5: B->F P11: E->L P17: I->R

P6: C->G P12: F->M P18: I->S

   Где прописные латинские буквы A...S обозначают состояние рабочей памяти в целом, а не отдельных ее элементов. Запись вида x->y есть сокращение формулы ЕСЛИ x, ТО y.

    Дерево поиска для рассматриваемой системы продукций приведено на рисунке, его вершины помечены состояниями рабочей памяти, а дуги - имена продукций. Метод поиска в ширину осуществляет раскрытие вершин по ярусам сверху-вниз, а внутри яруса - слева-направо (в нашем примере в "алфавитном" порядке от А до Р). Последовательность применения продукций для порождения дочерних состояний соответствует порядку их нумерации - от Р1 до Р18.