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

    Порядок раскрытия вершин методом поиска в глубину таков: A, B, E, J, K, L, F, M, N, C, G, O, P, а последовательность применения продукций - Р1, Р2, Р3, Р4, Р5, Р9, Р10, Р11, Р12, Р13, Р6, Р14, Р15.

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

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

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

                       Методы решения  сложных задач 

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

1. разбиением пространства поиска на подпространства и
2. введением иерархии пространств различных уровней абстракции.

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

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

Рис. 4. Пример И/ИЛИ-дерева

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

   Примечание. Дерево поиска на представленном выше рисунке является И/ИЛИ-деревом, для приведения его к этому виду в него дополнительно были введены фиктивные вершины ствол_1, ствол_2 и ствол_3.

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

   Для рассматриваемого примера, в частности, и для задач структурного синтеза, в общем, характерно взаимодействие подзадач, которое проявляется в том, что результат решения одной подзадачи влияет на процесс решения остальных. Так, при проектировании башни высотой 12 м выбор крыши призматической формы (4 м) задает поиск конструкции ствола высотой только 8 м.

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

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

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

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

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

            Методы поиска решений при неточных знаниях  

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

1. теория вероятностей (формула Байеса) и
2. эмпирические подходы в сочетании с нечеткой логикой.

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

    Для базы знаний диагностирующих ПС характерны продукции вида

                                ЕСЛИ свидетельство, ТО гипотеза ,

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

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

Р(Н|Е) = Р(Е|Н)·(Р(Н)/Р(Е)) ,

 где Н - гипотеза, Е - свидетельство, Р(Н) - априорная (безусловная) вероятность гипотезы (вероятность наличия данной неисправности в любом наугад выбранном экземпляре технического объекта), Р(Н|Е) - апостериорная (условная) вероятность гипотезы при наличии свидетельства, Р(Е|Н) - вероятность проявления свидетельства при справедливости гипотезы, Р(Е) - вероятность наличия свидетельства независимо от истинности или ложности гипотезы.

 Последняя вероятность  определяется как 

Р(Е) = Р(Е|Н)·Р(Н) + Р(Е|~Н)·Р(~Н),  Р(~Н) = 1 - Р(Н),

 где ~Н означает  ложность гипотезы (отсутствие данной  неисправности).

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

Р(Н|Еn, Еn-1, ..., Е1) = Р(Еn|Н)·(Р(Н| Еn-1, ..., Е1)/Р(Еn)),

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

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

Р(Н|R) = Р(Н|Е)·Р(Е|R) + Р(Н|~Е)·(1 - Р(Е|R)).

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

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

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

КО(заключение) = КО(условие) · КО(продукция).

   Условие продукции представляет собой, как уже говорилось выше, объединенные логическими связками И, ИЛИ, НЕ требования к элементам рабочей памяти, в связи с чем возникает задача вычисления КО условия продукции, исходя из КО соответствующих данных. Для ее решения обычно используются соотношения, подобные принятым в нечеткой логике, а именно:

КО(x И y) = min(КО(x), КО(y)),

КО(x ИЛИ y) = max(КО(x), КО(y)),