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

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

                                                                         Введение

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

    В то же время многие задачи проектирования (например, подавляющее большинство задач структурного синтеза) плохо поддаются автоматизации, решаются вручную, эвристически на основе опыта и интуиции разработчика. При этом качество получаемых решений определяющим образом зависит от творческих способностей человека. Такие задачи принято называть плохоформализуемыми, к ним относятся: 1) задачи, не имеющие точно выраженной математической постановки (в терминах АП - задачи, не имеющие конструктивной ММ) и/или 2) задачи, решение которых алгоритмическими методами невозможно или неэффективно. Наряду с поиском и разработкой формальных подходов к решению таких задач перспективным является использование методов и средств искусственного интеллекта.

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

   Кроме перечисленных выше плохоформализуемые задачи обычно обладают следующими особенностями:

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

    Плохоформализуемые задачи - это чаще всего задачи в нечисловой форме.

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

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

   Пример. Иллюстрацией первого уровня интеллектуальности могут служить подсистемы трассировки печатных плат, в которых 90...95% межсоединений трассируются формальными методами, а для размещения в автоматическом режиме остальных используются эвристические приемы. Ко второму уровню может быть отнесена САПР жидкостных расходомеров, в которой для выбора физических принципов действия расходомеров используется подсистема структурного синтеза, воплощающая в себе методы ИИ. К средствам построения САПР третьего уровня интеллектуальности относится мониторная подсистема INTERLOG, служащая средством интеграции независимых программных комплексов в единую САПР и основанная на идеологии ИИ.

                                 Представление знаний 

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

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

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

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

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

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

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

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

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

   Пример. Экстенсионалом понятия "числа Фибоначчи" является бесконечное множество целых чисел 1,1,2,3,5,8,... , интенсионалом - следующее правило порождения:

 С1=1, С2=1, Сk=Сk-1+Сk-2 для k = 3,4.... .

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

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

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

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

Рис. 1. Классификация моделей представления знаний

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

   Пример. Пусть необходимо представить знания о чрезвычайно упрощенной предметной области "проектирование башен". Башня представляет собой сооружение из крыши и поддерживающего ее ствола. Крыша может быть призматической высотой 4 м или плоской высотой 1 м. Ствол башни может состоять из 1, 2 или 3 блоков одинаковой формы. Цилиндрические блоки имеют высоту 5 м и 3 м, а блоки в виде параллелепипеда - 4 м и 2 м. Все башни в нашей предметной области должны иметь громоотвод и сигнальный маяк на крыше.

    Основной  задачей, решаемой в этой предметной  области, является создание проекта  башни заданной высоты.

                                            Семантические сети (СС)

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

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

   Пример. На рис. 2. представлен фрагмент СС, описывающей башню из нашего примера, состоящую из крыши призматической формы и ствола из двух цилиндрических блоков высотой по 3 и 5. Дуги, помеченные символами ISA, соответствуют отношению "быть элементом множества" (is a - быть одним из), а дуги, помеченные AKO - отношению "быть подмножеством" (a kind of).

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

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

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

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

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