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

Министерство науки, высшей школы и технической политики Российской Федерации

Московский ордена Трудового Красного Знамени горный институт

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

АЛЯПКИН Валерий Владимирович

УДК 681.51.001.63 : 681.3: 519.95

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

Специальность 05.13.12 — «Системы автоматизации проектирования (промышленность)»

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

/

Москва 1992

Работа выполнена в'Московском ордена Трудового Красного Знамени горном институте.

Научный руководитель канд. теш. наук, доц.. ФЕДОРОВ Н. В.

Официальные оппоненты: докт. техн. наук, проф. ФРОЛОВ А. Б., . канд. техн. наук, доц. ЗАХАРОВ В. Н. .

■ Ведущая организация — КБ «Аметист». Защита диссертации состоится « .Э. . »ок,гя&РЯ 1992 г.

в \Ьос. час. на заседании специализированного совета Д^ОБЗ. 1(2.12 Московского ордена Трудового Красного Знамени горного института по адресу: 117935, Москва, Ленинский проспект, 6. Л 2 "ЪЧ '

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

Автореферат разослан « & . » О.Е . . 1992л\

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

докт. техн. наук, проф. ТОРХОВ В. Л.

ОБШ ХАРАКТЕРИСТИКА РАБОТ«

Актуальность работы. Широкое развитие современных методов проектирования, ориентированных на использование ЭВМ в различных предметных областях, требует соверяенно нового подхода к организации процесса проектирования. Инженеры-практики не смогут успеино использовать новейшие теоретические разработки до тех пор, пока не будут иметь в своем распоряжении удобные практические средстаа и методы. Все это обуславливает актуальность задачи интеллектуализации автоматизированного проектирования

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

Одновременно следует отметить, что одним из Основных направлений развития систем интеллектуализации САПР является

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

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

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

исследование на основе предложенной методики математической модели САПР и реализацию сценарного подхода в проектировании СйПР и накоплении опыта проектирования;

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

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

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

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

Методы исследования. Поставленная в работе задача решается методами теории сетей Петри, теории графэв. теории оптимизации.

- 3 -

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

предловена методика представления математическое! модели СЛПР в пространстве модель - модуль в терминах модифицированиях сетей Петри, позволяющая реализовать сценарный подход в процессе проектирования;

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

разработаны алгоритмы, реализуЕЗие предловеикнй подход к проектирования САПР.

Практическая ценность и реализация рззчльтатов работа. На основе предлоаенной математической «опели СГ.ПР н методов пороядения сценариев проскткрозя из разработан пакет инструментальных программных средств, нпаариантних к исследуекыа предметным областя»,

Предловена ветодяка накопления экспертных знаний и методика их использования в процессе проектирования. На основе разработанных програм*шнх средств создан "Интеллектуальный проектировзйк СГ;ПР", вход^ий в интегрированнуз среду САПР Электронных систем КБ "Аметист". что практически привело к сникенйв традоенкостн процесса проектирования электронных издэлкй,

Расчвтнкй яконогичаский эффект составляет 117.5 тыс. руб. в

год,

Апробация работы. Основные полоаения диссертации докладывались на XIII Всесоззном симпозиуме "Логическое управление с 'использование« - ЭВМ", XIII ' Координационном совещании "Математическое обеспечение интеллектуальных систем САПР-ГАП" (г. Феодосия, 1991г.), на научных семинарах "Новые информационные технологии" (г.Москва, 1991г.) и "Персональные ЭВМ: опыт применения средств программного обеспечения, перспективы развития" (г.Ленинград, 1990г.), на нзучно-практической

конференции "Современные задачи управления и внедрения ногой техники связи в условиях рыночных отновений" (г.Пенза, 1991г.).

Публикации. Основное содержание работы отрааено в четырех публикациях.

Объеи и структура работы. Диссертационная работа состоит из введения и заключения, изловенных на 142 страницах маиинописного текста, включает 31 рисунок, 4 таблицы и список литературы из 85 наименований.

ОСНОВНОЕ С0ДЕР5АННЕ РАБОТЫ

Программное обеспечение третьего поколения базируется на новой принципе - "кодел;«." систематических действий эксперта. Это связано с услоянениеи peuasunx в САПР задач, тенденцией автоматизации нз только отдельных зтапос разработки, но и процесса проектиронаакя с целэн. Появление интегрированных СЙПР позволяет использовать в одной систекс несколько различных подходов к ргвгшш проектных задач. Для эффективного Санкционирования cxosimx CfiüP при их разработке применяются принципы искусственного интеллгкта, что сливает стойкость разработок, уцьнызет риск концептуальных оеибок. повывает "дружественность" систем и допускает работу с пользователями, нэ яьлявцчыися специалистами в области вычислительной техники. Инструментальные средства интеллектуализации САПР инвариантна по отновенив к предметной области т.к. являптся средствами обработки залокенных в системе знаний.

Ревение этой задачи связано как с исследованиями в области искусственного интеллекта, так и с теоретическими вопросами создания систем автоматизированного проектирования. Значительный вклад в изучение этих проблем внесли Глувков В.М.. Горбатов В. А., Девятков В.Ь.. Корячко Е.П., Норенков И.Т. Перминов О.Н., Петренко Л.И.. Поспелов Г.С., Поспелов fl.fi.. Рябов Л.Т., Тыугу Э.Х.. Чистов В.П. Дейкстра Э., Кнут Д., ^одд Е.. Ульман & Хсар Ч. и другие,

Услп»нени» t систем проектирования связано с возникновением нобьх подходов к реиешл задач проектирования, а так«е с

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

- получение математической модели предметной области, применимой для реиения задач управления проектированием:

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

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

- накопление, представление и использование знаний о процессе реаения;

- разработка программного обеспечения, реализующего разработаннуо концепция интеллектуального проектирования в САПР.

1. Представление сценария САПР в виде модельного графа

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

Определение 1. Назовем сценарием проекта последовательность модулей с входными и выходными моделям , реализуявую данный проект . Сценарий проекта представик в виде модельного графа

G=<U,U> , где U=U 1UU2 ; UlfUI2=/ . Множество Ut=<vil.v[2.....vin)

-есть множество модулей , множество V2=(vjl,v]2.....vjk) -есть

множество моделей . Причем дуга (vl,vj)(u , vltUl , vJc<J2 , если модуль vi имеет в качестве выходной модель vj. и дуга (vl.ua)tU , vnÇUi, vlÇU2, если модуль vu имеет в качестве выходной модель vl.

Определение 2. Сценарием САПР назовем объединение всех возможных сценариев проектов , которые можно выполнить с помокьи данной £АПР . Сценарий САПР можно представить в виде модельного графа G=Û Gi, где L - число возможных сценариев проектов.

Интеллектуальный проектировщик САПР долиен решать следующие задачи. Задачи планирования:

1. По заданному мновеству входн"х и выходных моделей

<уЛ,ч12.....у]1)СЧ2 определить возмоеность реализации проекта ,

т.е. определить полноту задания входных моделей для получения требуемых выходных моделей .

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

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

4. Определить мнояество данных, которые необходимо хранить на каидом этапе проектирования.

5. Задача прогнозирования: по заданному мнонеству входных

моделей (у]1,у]2.....у]1)Си2 и мнонеству преобразований,

задаваемых сценарием САПР, определить "ноиество выходных моделей {уП + 1,«П+2.....иП+и), которне могут быть получены.

6. Задача диагностики: по заданному мноиеству выходных

моделей у}2..... и]и) и мнонеству преобразований,

задаваемых сценарием САПР, определить мнонество входных моделей (у]ш+1, и)ш+2, ... У]В+1).

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

7. За_ача моделирования САПР. Из заданного сценарием САПР множества преобразована. (модельного графа О виделить подмнпнество (подграф) преобразований, достаточных для решения ряда прикладных задач.

2. Представление сценария САПР в виде сетей Петри

Пусть кандый модуль в качестве выходной модели имеет только .ну моде;,' Каждому сценарии проекта, представлрнному в виде аьудс.льного гпафа £-<и,1Ь, моино поставит) г^ответствие сеть ПЫРИ С= Р.1.1.0>.

Определение 3. Сетьп Петри сценария проекта назовем сеть С=<Р,Т,1,0>, полученнув из двудольного графа сценария проекта

&=<и,Ч> по следувчим правилам: Р=и2=(у}1,у]2.....у]к)- кавдой

позиции соответствует модел1 . Т=и1={у11,V12.....иIп}- кавдому

переходу соответствует модуль.

Позиция рI€ и2 является входной позицией для перехода если дуга (р1,Ц) принадлегит И, т.е.: рЦКЦ) < = > (р!Л])Ы).

Позиция рЦУ2 является выходной пизицией перехода .

если дуга (Ц, рП принадлевит мновествд дуг П. т.е.:

р1{0а}> < = > (ti.pl ни .

Кратность позиции р1 (я(р1.0(1])) определяется стелены) полувыхода вервшш р!£02 в графе С .

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

Кавдому сценария САПР , представленному в виде иоделышго графа С=<и,и>, иовно поставить в соответствие сеть Петри. Пусть 61, где 61 - 1-й возможный сценарий проекта. Кагдоиу сценарии проекта 51 ковно поставить в соответствие сеть Петри С=<Р1.Т1,П,01>.

Определение 4. Сеть Петри сценария СА^Р С=<Р,Т,I,0>. соответствуи^ая модельному графу сценария С-<и,1Ь, определяется в

Ь Ь I. и

виде : Р=и Р1 , 7=У Т1 , 1=П П . 01.

1*1 1=1 ¡»1

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

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

Пусть в результате выполнения проектной операции (модуля), описываемой вервиной двудольного графа Е=<и.11>, VI 1(111 мовет быть получена в зависимости от Ч' входных моделей :

(у]'Ч>,у]Ч>+1.....у1Ч>»Ч*- ПСи2 одна ИJ (1(<1>=2) выходных моделей :

у]... или или ... . или V3в+(3—1 ,(и]|,и]а+1.....у]а«й-1)Си2.

Поставим в соответствие графу сценария Б сеть Петри следующего вида.

1. Аналогично сценарии проекта, гч.е камдый модуль имеет единственную выходную модель, каждой позиции соответствует модель, а каждому переходу - модуль:

P'=U2; T'=Ui; 0' и I' : pit I •( t j) <=> (pi.tj)iu .

pitO'itj) < = > (t].pl *u

с соответствусцим замечанием о кратности вершины pi (т.е. о tt( pi ,0( tj))).

2. Введем дополнительно позицию р^. и d переходов: tn.ta+i.....to+d-1:

о-'ШЫр^) :»(pff.0"(ti))=i ; i"(ti)={p^): o-cti>=ipi>;

»(pi,0"(ti)) равна степени полувыхода вершины vji в графе Б , где i =в.в+1.....в+d-i.

3. Будем считать . что в результате работы модуля tl получается некоторая модель и индикатор f^.. показывающий, какая именно выходная модель из множества 0(р* ) . В зависимости от значения fy будет запускаться один из d введенных переходов . И фишка (фишки) в цовой маркировке будет присвоена той позиции , которая соответствует значению индикатора f^ . Таким образом, следующими будут запускаться переходы , имеющие в качестве входа именно ту модел , которую указал индикатор .

4. Получена сеть Петри С=<Р.Т,1,0>:

Р = P'U { Р^ ) ; Т = T'U (tn.tr. >1.....tB+d-l);

I = I'll I"; 0 = O'U 0" \ О'Ш). Сценарий системы проектирования получается аналогичным образом путем объе-инения сценариев проектов.

Задачи интеллектуаль. зго проектировщика САПР могут быть сформулированы в терминах теории сетей Петри .

1. Для сети Петри С с маркировкой М и маркировки Н* определить ,.что Н4RrС,И) , где R(C,H) - множество достижимости для сети Петри С=< Р,Т.I.О> с маркировкой М .

Рекенке задачи достиаимости для сети Петри позволяет определить возможность реализации проекта имеющимися в системе ; "та^атизиг-¡ванного проектирования средствами.

2. Дчя сети Петри С с маркировкой и маркировки М определить маркировку И" и К"' такую, ч-о И'" досчаима из

маркировки М" и И" покрывает маркировку М; а М'" покрывает маркировку М' .

Речение задачи обратной достижимости и задачи покрываемое™'1 позволяет определить множество входных моделей , необходимых для получения выходных моделей , если множество входных моделей задано неполностью.

Маркировка Н представляет собой множества входных моделей; маркировка М' - множество выходных моделей. При условии, что задача достижимости (см. задачу N1) не имеет решения, ищется множество входных моделей (этому множеству соответствует маркиров.,а М"), удовлетворяющее условию Ы" > М, и при этом множество выходных моделей (соответствующее маркировке М'"), включающееся в.множество достижимости !*(С,И"), содержит множество выходных моделей Н', т.е. М"' >М'. Таким образом, нахождение разности множеств входных моделей, соо.зетствующих М" и М. даст множество недостающих моделей.

3. Для сети Петри С с начальной маркировкой М определить последовательность ' запуска переходов до получения маркировки И'", которая покрывает конечную маркировку М'.

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

4. Для сет.. Петри С с начальной маркировкой и определить множество достижимости Я(С,М).

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

5. Для сети Петри С и маркировки М' определить множество начальных иаркировок М такое, что М'(Р'С.М).

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

В, Для сети Петри С с множеством начальных маркировок II и иношеством конечных маркировок |Г определить множество переходов Т такое, что ( И(Т> < = > (8 (Н"Д1 )=Н"где либо И"\М"ШС,М>,

либо НЧ R( С,М" ' )).

Решение этой задачи позволит ппределить подмножество модулей, применимых при заданных входных моделях (соответствующих маркировкам М) либо применяемых для получения указанных выходных моделей (соответствующих маркировкам И'). Таким образом, выделенное подмножество модулей составит ядро прикладной САПР, предназначенной для решения задач вида: "по множеству моделей из N получить модели из M' ", а также задач 1-5 из приведенного списка на выделенном подмножестве Т.

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

3. Построение и использование сокращенного графа достижимости для ренения задач интеллектуального проектировщика

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

Определение 5. Сокращенным гр^ом достижимости G=<U,U> лля сети Петри С=<Р,Т,1,0> с маркировкой Mo назовем граф, в котором с рератчами связываются маркировки, а с дугами - множество переходив. Построение сокращенного графа достикимости происходит по приведенному ни*е алго.иму.

Рассмотрим алгоритм построения сокращенного графа достижимости сети Петри С=<Р.Т.I.О> с маркировкой Но .

Ka*kja вершина сокращенного графа достижимости связывается с маркировкой H[1j ; в маркировке число фишек мояет быть неотрицательным целим числом. Какдая вершина классифицируется или как граничная, или как терминальная вершина, или как f N■.ення;.

Граничными вериинами являются вершины которые еще не ибрайотанн алгоритмом. Терминальными - вершины, обработанные алгоритм* и ь cî';( lit ïj.K с данной маркировку« неьсомсины никакие

- и -

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

Алгоритм превращает граничные вершины во внутренние и*> терминальные. Граничные вершины делятся на два класса; граничные вершины с конфликтом и граничные вершины без конфликта. Граничная вериина i является граничной вершиной с конфликтом, рсли в маркировке МН1 существузт+Mj t i ЪО ( число фишек в позиции j больие нуля) и число дуг dj >0. исходящи" из позиции ], больна, чем число дуг dj >0, входящих в позицию ]. В противном случае граничная вериина является граничной верниной без конфликта. Число Ki ,1фликтов в позиции J определяется числом сочетаний В сценарии системы, допускавшем несколько выходных модулей, будут присутствовать, конфликтные вершины двух типов. Вершины первого типа содеряат ' конфликт ", разрешение которого заключается в выборе сценария проекта.

В различных npoeKijx модель мояет быть входной для разного вида и числа модулей. Сеть сценария проекта не содержит конфликтных вершим первого рода, т.к. строится с учетом степени полувыхода вершины в модельном графе G, что отражено в кратности позиции pl во входных и выходных функциях переходов. При объединении сценариев проектов в сценарий САПР возникает ситуация, при которой из впраины р] d] dj. (Противополоиного знака здесь, по построении объединенного сценария, быть не монет: т.е. либо dj = dj - нет "конфликта", либо dl > dj - есть "конфликт".) р.'-реярние "конфликтов", возникающие при этих условиях, соответствует либо выбору одного из существующих проектов, либо порождению нового проекта, который стал возиояен благодаря объединению различных сиензриев проектов в единую систему прорктирогзния.

Вервии« ыорого типа содеряат конфликт', разревпние которого приводит к определении ветви я пределах сценария одного проекта в завигимпсти от услоеий работы модуля . соотвс :твусщего конфликтной вершине , налагаемых входными моделями . Зти условия Формализуются в виде индикатора-функции.

Вершины с конфликтами в сценарии систекы проектирования обрабатываются одинаково. Для в¿раин второго типа по построению dj = 1. Поэтому число конфликтов CdJ - С*, = d], т.е. раьно

числу выходных вершин.

Алгоритм построения сокращенного графа достижимости.

ВО: vOfcUfl: uívO^Ho HHILE (3 х - граничная вершина) It: ЕслиSСHtх],tj) - не определеноV tJtТ. то х терминальная иначе 112

В2: Если х - граничная вершина без конфликта, то neu z:

1. и=(х.г)£11д: u(u) определяется переходами,

разрешенными в С с Mix]

2. MIzl: для pi:

Если tj£T разрешен в Htx), то MIzH-StMIxl.tJ )1 иначе MIzH=MIxH ЕслиЗ гЧид: MCz' ЬМЫ, то z = z' х - становится внутренней 13: Если х - граничная вершина с конфликтом,

то neu (zl, z2.....zk), k= ]1•j2-..,•in

tij

ш - число конфликтных вершин в С с И С х 1; H = Cdj

u=(x,zl) и Ktzl] - определяется аналогично_|2 с

учетом 1-го разрешена из к конфликтов il=l.k) END HHILE

Конец.

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

Рассмотрим класс начальных маркировок Ип-í Hn 1.Мп2.....Mrik), :í;u делягучй множеством ьсех проектов , которые mosho выполнить в (и. une автоматизированного проектирования. ,ип"ст;им , для каждой начальной манкировки Hill и заданной сети Петрм системы £•■•• Р.Т.! ,0> построен сокращенный граф достияимости Gi .

Определим операцию объединения GiUGj сокращенных графов достижимости Gi и Gj , построенных по сети Петри С=<Р.Т,I.О> с начальными маркировками Мni и MnJ соответственно .

Определение 6. Пусть Gi=<Ui,Ui>, где

UI={vi Ifu11 ),v2i(u2i).....vnlíunl)};

Ui =íul 1 сы 1 i ),u2i(u2i).....ukKuki)>;

Gj--<Uj.Uj>;

Uj={vij(ui] ).v2j(u2J).....vlj(ulj )>:

Uj--'ulJ(ulJ ),u2j(u2j).....vbHubJ )}.

Причем каждый вес вершины и определяется множеством позиций

u=fpii,pl2.....plk) , а каждый вес дуги и определяется множеством

переходов u=(tj 1 ,t]2.....t]n>.

Тогда G=G1UG! есть грал, определяемый следующим образом: G=<U,U>. причем считается, что вершины vjfcUJ и viíUl идентичны, если n(vi)Cutvj) или u(vJ)Cuívi), результирующая вершина имеет вес u(vj) или ы(V1) соответственно ; U=Ut4Uj. причем считается, что дуги uléUi и uJtU] идентичны, если u(ui)=u(uj). Если u(vl)Cu(vJ), то всем вершинам графа Gi,, из которых достижима вершина vi, дописываем вес - u(vj)\u(vi), а также вершинам, которые достижимы из vi. При таком объединении вершин следует учитывать их смежность. Пусть в графе "I вершины vil и vi2 инцидентны дуге ui, а в графе GJ вершины v] 1 и vj2 -дуге uj и при этом попарно выполняются условия вклк^. ния для весов u(vil) и u(vjl), ыСV12) и u(vj2), Мы объединяем вершины vil и vjl. При этом вершины vi2 и vj2 объединяются только в том случае, если iHvil ICuCvji ) и u(vji)\u(vil)=u(vj2)\u(vi2).

Определение 7. Сокращенным графом достижимости системн с сетью Петри С=<Р,Т,1,0> и множеством началышх маркировок Hn={Mni,Hn2.....Мпк) назовем граф G=U Gi.

Сокращенный граф достижимости системы позволяет решить все перечисленные выше задачи .

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

моделей (pll.piL.....pi'i) и выходных моделей (pjl.p'"1.....pim>

определить возможность реализации проекта, необходимо Е> сокращегчом графе достижимости ^истемы найти две вершины: ul с весом Ml и v2 с весом М2. для которых существует п»ть от вершины Vi у вершине v2 и Hi-thi'rtHDCfpil.pil.....р!п>;

- [/. -

<pj 1 ,pj2.....pJn)CH2 (1) .

Если множество входных моделей задано не полностью, то, чтобы определить множество входных моделей, необходимых для получения заданных выходных моделей, надо найти в сокращенном графе достижимости системы вержину v2 с весом Н2 такую, что

функционал 32=J(H2',(pji,pJ2.....р]и)) минимален, и вершину vi.

причем существует путь от вершины vt к v2 и

31HI',(pil,pi2.....pin)) минимальна и не содержит конфликтных

вершин второго типа, то _ есть позиций типа р.^ , так как Фактически они не соответствуит никакой входной модели, а являются ливь фиктивной входной (выходной) моделью и служат для отражения различных ситуаций Формирования выходных моделей в зависимости от работы модуля. Здесь Ml'и М2'-множества. соответствующие комплектам И1 и М2. Здесь Л г х) некоторый Функционал, характеризующий трудоемкость получения молелей ннояества х. Вид функционала определяется экспертом. В простейшс..: случае он может вычисляться как мощность множества !u(v)\x!:

31--ГД1! = !И1'\{р11,р12.....pin)!

32-!Д2!г!И2'Ч{рЛ,р3 2.....pjni)!

Решение этой задачи осуществляется известным алгоритмом Дейкстры.

Тогда множество входных моделей . необходимых для получения заданных выходных моделей , будет определяться следующим образом: (р 1 i,р12.....р1п)1Ш\(И2|Ш).

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

предь!дузем случае. Причем если переходы t.]l,tJ2.....tjn

взвешивают одну дугу, то модули, соотвстствукчио переходам t]i,tj2.....tjn, можно выполнять параллельно.

Множество данных, которые необходимо хранить на каждом этапе проектирования, определяется следувц:-;« образом: MiU( МiЧ( К2ЛМ1)), где Mi - вес вериины vi полученного пути.

Задача прогнозирования. Для определения нноиества выходных моделей Mt, которое можно получить с помощь» системы проектирования по заданным входным моделям. Ко необходимо:

выделить множество вервин сокращенного грзфа достияимости

(у)(и]) / и](у])СМо) и найти все вершины сокращенного графа достияимпсти, в которые существует путь из выделенного множества вершин. Мноиество, являющJecя объединением мноиеств, которые соответствуют комплектам весов найденных вершин, будет являться подмноуствон Ш.;

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

Возьмем и вершину графа, обозначии ио(ио); дуги, инцидентные эти л вершине - ио(и ), ио'(и '),... и т.д. вериины, инцидентные этик дугам у!(и1), у1'(и1'),... и т.д., далее дуги - иКи1 ), и1'(и1'), ... и т.д. Теперь сформулируем свойства:

1. ио( уо ) \ ы 1С у 1) С И о 1) » 1) - чтрих'.- опуаены у обозначений верь'шш «КуП

2. М1 = 8* (иоС у о) \ Ы1(У1 ), «'(и0 ) )

* - расширенная функция следующего состояния, получаемая в результата одновременного запуска переходов и С V1): и* (У4) - у НУ! )Г!ЧО(УО)№Н

3. М1 *Б'(ИЫ. ин{им ) ) 1 = 2. 3.....п ,

где п-длина пути в подграфе и1(у1) = и1(у1)П«1-Н«1-1 )1>Н1

Мновестэо, являсщееся объединением мнояеств, соответствующих комплектам весов вертаин, всех найденных Подграфов будет являться подмножеством ЙЬ. за исклачепием (во( «о)ПиК VI ))\ Но

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

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

выделить множество вершин сокращенного графа Д1 тикимости (у](и.) ) / МоСиЛ у] ) );

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

1. Выделить вершины и)(и]) так,.р? что существует дц 1,

<1 1 *

инцЦчентная уИи]) и уНы]) и направленная от у](иЗ) к у](и)), и

веса вервин удовлетворяют условии:

1. ыЗ (VЛ) N иДу} )£ Но , ,

2. ыНУ}) \ и}(у})с МС.ННУ!) \ и](у|))(

В множество вершин включается вервина V5с ы31, а в множество маркировок, из ко^рого может быть достигнута маркировка Ко, маркировка Н1 = ы]СV1) \ и^у]). к к

2. На к-м ваге выделить квершину у|(и]) такие, что сущерву^т дуга1>( и^цадентнар V] (и! ) и у] (и] ) и направленная от V} (»1 ¿к у| (и] р веса вервин удовлетворяют условию: • 1. «¿С^)\и|Су1)СИк-1 ь к н к.(

2. «] (у] ) \ и](</})£ Й(С,и}(1/]) \ )>

В -ножество вершин вклю^ае^ся ве^иин^(у](и]) , а в множество маркировок маркировка Мк = ы^у]) \ «] (у] ).

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

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

Зти запчи могут быть так»е решены путем моделирования сети Петри. Для решения задачи ппогнозирования I пользуется исходная сеть Петри с Ко в качестве начальной маркировки.

Для решения задачи диагностики используется сеть Петри, в которой входные и выходные функции меняется местами. Начальная маркировка остается той же самой. Отличие задачи прогнозирования от задачи диагностики состоит в ток, что ревениеи первой является множество позиций, которые могут быть промаркированы в процессе проектирования: решением второй является множество маркировок, из которых может быть достигнута маркировка Ко (либо для об[ тной сети это просто множество догтижииости К(С',Ио)>. Множество маркировок является множеством множеств гшиций.

Задача моделирования САПР может быть ревена как задача планирования- для различных множеств начальных и конечных

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

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

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

На основе предложенных методов интетлектуального управления процессом проектирования были разработаны инструментальные прграммные средства "Интеллектуалы й проектировщик САПР". Программы написаны на языке С++ и рассчитаны на применение на IBM совместимых компьютерах в операционной среде MS DÛS.

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

Дл" построения модели САПР в терминах сети Петри пользователь должен с помощь» модуля INTFhCE представить системе

информацию об используемых моделях; информацию об используемых модулях; информацию об используемых проектах; информацию о САПР. На основе этой информации формируются файлы sel, хранящие сведения о моделях, модулях, проектах и системе, С использованием этих файлов модуль INTFACE подготавливает информацию net i для работы модуля PETRI. Модуль PETRI использует информации о начальной маркировке сети шк]. Выходной информацией модуля является граф достижимости gdij. Модуль GD осуществляет операцию объединения графов достижимости. Модуль DI3KSTRA использует сокращенный граф достижимости и сведения о входных-выходных моделях проекта tz и реализует алгоритмы планирования и оптимизации, основанные на задаче поиска кратчайшего пути и методе "обратной волны". Модуль МАКЕ использует данные, подготовленные модулем DI3KSTRA - utl, для формирования файла «ар, содержащего информацию о мпдулях и моделях, требуемых длл реализации проекта. Структура взаимодействия программных модулей представлена на рис. 1.

Подготовку информации для работы модуля iNTFACE осуществляет разработчик САПР, формируя входные данные о взаимодействии единиц системы проектирования и базы данных и характеристики программных компонент и моделей. Опытный эксперт-проектировщик указывает на основе собственной практики типовые проекты, выполняемые в системе, и их фрагменты, что формализуется в виде маркировок nkj и используется для построения сокращенного графа достижимости, аккумулирующего знания. конечный пользователь, используя подготовленную в системе информацию, решает задачи проектирования, представляя в качестве входных данных входные и выходные модели технического задания, получает результат в виде технологической карты с указанием порядка применения модулей (с учетом параллелизма), моделей, хранимых на каждом этапе проектирования. В первом случае маркировки сети Петри определяются как Mol=(sci) Mtl=(netl). во втором - Mo2=(neti, nkj. ed) Mt2={t¡d), в третьем - Ko3=(2sci. ed. tz) Mt3={itap).

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

"Интеллектуальный проектировщик САПР" был внедрен в практику проектных работ в КБ "Аметист" а составе комплекса инструментальных средств САПР Электронных систем, позволившего

sc),

Рис. 1. Структура взаимодействия программ ^нтелл< ;туальи~го проектировщика

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

ОСНОВНЫЕ ВЫВОД» И РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

для решения практических задач в САПР с числом модулей 255.

3. Созданные программные средства внедрены в практику проектирования электронных изделий в райках САПР Электронных систем в КБ "Аметист" с годовым экономическим эффектом 117,5 тыс. РУб.

Основные положения диссертации опубликованы в следующих работах:

1. Киселев А,И., Попов Е.И., Караваев С.Я., Лляпкин В.В. Пакет прикладных программ для моделирования, анализа и оптимизации динамических процессов и систем // Персональные ЭВМ: опыт применения средстз прогрэыкного обеспечения, перспективы развития / Натериаг!, краткосрочного семинара 22-23 ноября,- Л.: Л/МТП, 1390, с.53-50.

?.Плапкин Э.В., Осдоров 11.3. Автоматизированное планирование проектов в САПР // Новые информационные технологии в планировании, управлении и в производстве / Материалы сеиннара.-М.: 11ДНТП. 1591, с. 133-137,

3. йляпкин В.В. Лерсоьальныл ЭВН в ::нзенерной практике: проблемы создания интеллектуальных средств проектирования систем связи // Современнее гздачи управления и внедрения новей техники связи в условиях рыночных отношений, - Пенза: ПДНТП. 1991, с.31-34.

4. йляпкин В.В. Архитектура системы автоматизированного планирования проектов СДПР // Логическое управление с использованием ЭВМ. Математическое обеспечение интегрированных систем САПР-ГАП: Тезисы докладов. / XIV Всесоюзный симпозиум и Хй Координационное совещание. - Москва - Феодосия, 1991, с.290-295.

Подписано в печать 15.07.92. Форма 60x90/16 Объем 1 печ л. Тира« 100 зкз. Заказ Яо

Типография МГЦ. Лени'чскчЛ проспект, 5.