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

СЕВЕРО - КАВКАЗСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ

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

ДЕДЕГКАЕВА ЛАРИСА МАГОМЕТОВНА

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

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

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: д.т.н., проф.

Хадонов З.М.

Владикавказ - 1999

СОДЕРЖАНИЕ

Стр.

Введение 4

1. Состояние вопроса и постановка задачи 8

1.1. Обзор методов автоматизированного проектирования систем управления 8

1.2. Преобразование ДСМ в детерминированный автомат 19

1.3. Задача декомпозиционного синтеза 28

1.4. Выводы 33

2. Анализ функционирования автоматов по входным векторам

2.1. Структуры автономного функционирования систем логического управления

2.2. Анализ пересекающихся контуров

2.3. Определение номера вершины контура по ее спектру

2.4. Пересекающиеся контуры с прерывистой общей частью

2.5. Преобразование структур графоидов к стандартному виду

2.6. Выводы

34

34 41 50

52

57 70

3. Разработка системы проектирования абстрактной декомпозиции и ее имитационное моделирование

3.1. Выделение контуров автономного функционирования

3.2. Генератор графоидов с заданными параметрами

3.3. Выводы

4. Абстрактная декомпозиция систем управления (на примерах системы управления промышленной автоматики и системы управления информационными

процессами) 91

4.1. Построение автомата управления установкой

очистки воды 92

4.2. Построение автомата управления локальной вычислительной сетью 101

4.3. Выводы 122

Заключение 123

Литература 124

Приложения 145

77 79 90

ВВЕДЕНИЕ

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

Системы управления представляются конечно-автоматными моделями, дискретно-событийными моделями (ДСМ), как вероятностными, так и детерминированными, пакетами прикладных программ. Идеи конечно-автоматной интерпретации систем управления получили большое развитие в трудах ряда отечественных и зарубежных ученых, таких как Глуш-ков В.А., Гаврилов М.А., Горбатов В.А., Поспелов Д.А., Кобринский Н.Е., Трахтенброт Б.А., Лазарев В.Г., Хафман Д., Ангер С., Мак-Класки И., Полл М., Миллер Р.

С середины 80-х годов большое внимание разработке и анализу ДСМ, состоящим из взаимодействующих модулей дискретных событий, таких как производственные системы и сети связи, системы с непрерывными переменными. Различным аспектам разработки и анализа ДСМ посвящены работы Зиглера Б.П., Цао С. (США), Рамаджа П.Дж., Уонема У.М. (Канада), Коэна Г., Моллера П., Кадра Ж.-П. (Франция), Горбатовой М.В., Захарова В.А., Крицкого С.П.(Россия) и др. ДСМ позволяют достаточно полно учитывать воздействия внешней среды, однако они имеют большое количество физических состояний, что затрудняет обработку сложных технологических систем. Вследствие этого представляется целесообраз-

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

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

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

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

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

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

Целью работы является исследование разложимости и разработка методики разложения автоматных операторов, заданных графоидами, в

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

Для достижения указанной цели в работе:

- решена задача характеризации разложимости графоидов в терминах автоматов автономного функционирования;

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

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

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

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

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

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

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

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

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

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

Практическая значимость работы состоит:

- в создании методики построения графовых моделей систем управления по заданному описанию управляемого процесса;

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

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

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

Апробация работы. Основные положения диссертационной работы доложены и обсуждены на научно-технических конференциях СКГТУ (г.Владикавказ, 1998-1999 г.г.) и Международной конференции «Информационная математика, кибернетика, искусственный интеллект в инфор-мациологии» (г.Москва - г.Владикавказ, 1999 г.)

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

1. СОСТОЯНИЕ ВОПРОСА И ПОСТАНОВКА ЗАДАЧИ

1.1. Обзор методов автоматизированного проектирования

систем управления

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

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

Задачи проектирования этих систем еще более усложняются, когда их динамикой нельзя пренебречь. Для дискретно-событийных динамических систем (ДСДС), согласно Цао С.[1] , характерны динамические свойства непрерывных систем, но такие специфические особенности, как случайность поведения и сильная взаимосвязь составных частей и ресурсов, присущие каждой индивидуальной ДСДС и отличают их от систем с непрерывной переменной. ДСДС используются в качестве моделей широкого класса приложений от гибких автоматизированных производств до сетей связи и вычислительных систем[2]. К общим особенностям по-

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

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

ДСС представляют также динамической системой, которая эволюционирует в соответствии с внезапным возникновением физических событий, порой в заранее неизвестные нерегулярные моменты времени [3]. Такие системы появляются в целом ряде приложений, начиная от операционных систем ЭВМ и кончая управлением сложными многорежимными процессами.

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

Вычислительные задачи для ДСМ отличаются высокой сложностью, проявляющейся при решении задач синтеза управления [56, 64, 67, 78,

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

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

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

и

событий. Это делается путем использования функции перехода какого-либо вида, путем определения системы алгебраических уравнений или средствами логического исчисления высказываний и предикатов. Допустимые траектории событий формируют строгое подмножество всех возможных последовательностей событий. Если задано свойство последовательности событий определяется каждая ли допустимая траектория имеет желаемое свойство. Типичные свойства, представляющие интерес это - устойчивость, правильность упорядочения событий, желаемое динамическое поведение, координация элементарных процессов для достижения желаемой цели. Логические модели могут быть также использованы в качестве основы для вычислений, например, для синтеза ДСС. Число состояний в функции перехода при определении допустимых траекторий может иметь экспоненциальную зависимость от некоторых параметров системы. Простые алгоритмы в этом случае быстро становятся несостоятельными с вычислительной точки зрения. Обычно стараются сделать упрощение путем агрегирования, разукрупнения или применения иерархических и других специальных структур [3].

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

Стохастические модели несколько отличаются от логических [31,31, 72]. В них задача определения множества допустимых траекторий в фа- • зовом пространстве довольно тривиальна. Сложность же моделирования и анализа заключается в определении степени пригодности этого множества и в использовании ее при нахождении распределения вероятностей и статистических моментов переменных, представляющих интерес. Сто-

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