Разработка и оптимизация графовых моделей САПР систем управления тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Дедегкаева, Лариса Магометовна

• Дедегкаева, Лариса Магометовна
• кандидат технических наук
• 1999

Оглавление диссертации кандидат технических наук Дедегкаева, Лариса Магометовна

СОДЕРЖАНИЕ

Стр.

Введение

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

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

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

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

1.4. Выводы

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

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

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

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

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

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

2.6. Выводы

34

34 41

52

57

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

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

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

3.3. Выводы

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

процессами)

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

очистки воды

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

4.3. Выводы

Заключение

Литература

Приложения

77 79

Введение диссертации (часть автореферата) на тему «Разработка и оптимизация графовых моделей САПР систем управления»

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и

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

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

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

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

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

Вч< ^ и

системах с динамическои топологиеи взаимодеиствия произвольны и меняются во времени.

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

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

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

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

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

Таким образом, понятие языковой сложности ведет к частичному упорядочению ДСМ - формализмов, так что более сложный формализм имеет более высокую описательную возможность, чем менее сложный.

Дискретно - событийная модель - это любое конечное математическое представление бесконечного множества. Для некоторых целей необходимо описывать не только логическую последовательность событий, выполненную системой, но также и значения времени наступления событий. Временная дискретно-событийная модель [5, 40] представляет собой математическое описание всех временных следов, выполненных системой. Временной след-это последовательность вида

б = ( )(а2, ^ )(аз, Ь )* • •» где а!а2а3- логический след, означающий, что событие анТ имеет место после события а!; момент времени, в который произошло событие, причем необходимо, чтобы 1:1< %

Возможна еще более сложная модель, способная обеспечить статистическое описание временных следов. Это стохастическая дискретно-событийная модель, выполняющая следы вида

в(лу) = (а! (\vXti (у/)), (а2 г2 (ы)), (а} (ш)) . .., где а] , 11 ,а2 Д2 - случайные переменные, w- выборочная точка, так что s(w)- выборочный путь. Каждый выборочный путь является временным следом, и стохастическая ДСМ определяет распределение вероятностей по набору всех временных следов.

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

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

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

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

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

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

Процесс синтеза сложного автомата Глушков В.М. подразделяет на этапы - блочного, абстрактного, структурного, комбинационного и надежностного синтеза [7]. Разделение на этапы дает лишь общую ориентировку в вопросе о том, через какие стадии проходит решение задачи синтеза цифровых автоматов. Впервые идея применения булевой алгебры к проблемам комбинационного синтеза релейно-контактных схем была применена в работах Шестакова В.И. и К.Шеннона. Далее теория комбинационного синтеза пополнилась структурным и блочным синте-

зом автоматов в работах Д.Хафмена, Г.Мили, Шестакова В.И., М.Уилкса. Начало в абстрактной теории автоматов было положено в работах С.К.Клини и Э.Мура . В теории синтеза надежностных схем из ненадежных элементов Д.Неймана положено начало математической теории надежностного синтеза. В работах Глушкова В.М., использовавшего результаты, полученные Д.АуфенкампоМ и Ф.Хоном, теория абстрактного синтеза автоматов была доведена до уровня, обеспечивающего возможность приложения ее к решению реальных задач синтеза цифровых автоматов. Также была решена задача сопряжения этапов абстрактного и структурного синтеза и представления структурной теории в виде, пригодном для решения проблем синтеза цифровых автоматов с запоминающими элементами любой природы. В [7] изложена теория синтеза цифровых автоматов как единая математическая теория.

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

Для описания условий работы микропрограммных автоматов широкое распространение получил язык логических схем алгоритмов (JICA)[9], который полно отражает особенности микропрограммного автомата (МА) и может быть использован для выполнения некоторых эта-

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

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

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

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

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

Л

п = 1оё2|{Х>}| (1.1)

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

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

На абстрактном уровне определение объема памяти означает определение числа вершин графа переходов. Граф переходов есть граф G = < S,U > , каждая вершина которого взаимно однозначно соответствует внутреннему состоянию автомата, и если из состояния Si автомат переходит в состояние Sj, то соответствующие им вершины V; и v j соединяются дугой (v j 5 v j ) е U, взвешенной парой векторов ( X, Y ), при которых этот переход осуществляется.

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

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

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

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

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

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

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

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

множества следов системы (как отработанных, так и вероятных) и частотно-временные параметры.

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

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

Система управления технологическим процессом, как правило, включает объект управления (ОУ), т.е. сам технологический процесс; устройство управления (УУ) и внешнюю случайную среду(ВСС), в которой функционирует объект управления.

Устройство управления подает входные сигналы на объект управления. Но внешняя среда, в которой работает система, является случайной; и на вход объекта управления могут поступать случайные воздействия извне, каждое из которых переводит систему в заранее определенное технологическим процессом состояние. Под случайными воздействиями будем понимать - нештатные. Каждому нештатному воздействию соответствует известный отклик и реакция системы на данное воздействие экспериментально установлена в процессе отработки технологического процесса. Описывая поведение системы в терминах алгебры дискретных событий [5, 6], можно получить простую и достаточно достоверную модель. Обозначим множество контролируемых воздействий, поступающих на объект управления от УУ как - Хй; множество неконтролируемых воз-

V u VJ w V Л7

действии от случайной внешней среды - Xs; множество разрешенных состояний - Qd; множество случайных состояний- Qs.

Рассмотрим некоторую дискретную модель, которая описывает технологический процесс, протекающий в случайной среде G (Q, А, 5, q0) , где Q- множество состояний; А- множество следов; 5 =XuW, где X-множество воздействий, W-их вероятность; q0 -начальное состояние. Пусть ОУ находится в некотором контролируемом состоянии Qi е Qd. В очередной дискретный момент времени устройство управления должно подать на ОУ управляющее воздействие Xi eXd, после чего система перейдет в контролируемое состояние Qi+i е Qd. При поступлении на объект управления случайного воздействия Xk е Xs система переходит в состояние Qk е Qs. Множество случайных воздействий Xs для конкретного технологического процесса переводит систему во множество состояний Qs, каждое из которых заранее известно. Тогда мы можем положить, что при подаче входного воздействия Xi е Xd система перейдет либо в состояние Qd , либо к одному из состояний Qkj е Q s и случайные процессы можно описать как известные и перейти к детерминированному автомату. В результате совокупность следов А ДСМ G , функционирующей в случайной среде можно преобразовать следующим образом в детерминированный автомат (рис.1.1.).

Преобразование приводит к детерминированному автомату F(Q,X), в котором множество состояний Q совпадает с множеством состояний ДСМ, а множество воздействий X совпадает с множеством контролируемых воздействий Xd и выбранных неконтролируемых воздействий Xs:

х= xd и x.s.

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

Рис. 1.1 Детерминированный автомат, полученный из ДСМ.

ствия Х5. Такое преобразование уменьшает количество переменных, определяющих работу автомата. Исключается параметр А (множество следов), который и есть совокупность воздействий X и состояний К тому же мы допускаем что, все случайные воздействия приводят в конкретном случае к известным нетехнологическим состояниям, являющимися достоверными, вероятность которых \У<1 = 1. В результате получается детерминированный автомат, в котором определены входные воздействия X и состояния , к которым эти воздействия приводят.

Например, рассмотрим автомат, управляющий процессом производства бисульфата натрия непрерывным способом [30]. По описанию процесса определим множество состояний данного автомата: (^г Серная кислота поступает в промывной бак; сернистый газ подается в промывную башню; запущен вентилятор для просасывания газа через всю систему; подается вода в содорастворитель.

С>2 - Сернистый газ поступает в промывную башню; вода в содораство-рителе нагревается.

СЬ- Разбавленная нагретая кислота стекает в отстойный бак; сода загружается в содорастворитель порциями; подается сжатый газ для переме-

шивания раствора; охлажденная серная кислота подается в промывную башню.

С>4 - Газ проходит через брызгоуловитель; определяется температура содового раствора.

С>5 - Газ подается в поглотительную башню; включается насос, раствор соды перекачивается в расходный бак; нагревается раствор соды в баке. С)6- Готовый раствор стекает в сборник, насосом перекачивается на склад; нагретый раствор соды поступает в сборник. (^7 - Кислота, из сборника с содовым раствором, насосом перекачивается в промывную башню.

0>8 - Готовый продукт стекает в хранилище; проводится анализ готового продукта ; часть продукта подается в сборник.

С>9 - Выключается вентилятор; прекращено приготовление содового раствора.

СЬо - Выключается насос, перекачивающий готовый продукт в хранилища.

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

С>15 - Продукт поступает на склад; подается очередная порция соды и кислоты.

Множество микрокоманд поступающих на автомат: К1 - включить насос; подать серную кислоту в промывной бак. К2 - подать серную кислоту в промывную башню. КЗ - нагретую кислоту спустить в отстойный бак.

К4 - пропустить кислоту через холодильник; подать в промывную башню.

К5 - пропустить газ через брызгоулавливатель.

Кб - подать газ в поглотительную башню.

К7 - включить насос, подающий конденсат в поглотительную башню. К8 - открыть вентиль для спуска продукта в сборник; подать продукт на склад.

К9 - подать кислоту и содовый раствор в поглотительную башню.

К10 - перекачать раствор соды в расходный бак.

К11 - подать нагретый раствор соды в сборник.

К12 - открыть вентиль, спустить готовый продукт в хранилище.

К13 - провести анализ готового продукта. »

К14 - спустить готовый продукт в сборник.

К15 - включить вентилятор.

К16 - заполнить водой содорастворитель.

К17 - включить нагрев воды в содорастворителе.

К18 - загрузить порцию соды в содорастворитель.

К19 - включить подачу сжатого воздуха для перемешивания раствора соды в содорастворителе.

К20 - определить температуру содового раствора. К21 - выключить вентилятор.

К22 - выключить насос, перекачивающий продукт в хранилище.

К23 - выключить насос, подающий раствор в поглотительную башню.

К24 - спустить сульфит - бисульфатный раствор в бак- сборник.

К25 - выключить насос, подающий кислоту в промывную башню.

К26 - остановить приготовление содового раствора.

К27 - уменьшить подачу содового раствора.

К28 - повысить концентрацию соды в растворе.

К29 - понизить концентрацию газа.

КЗ 0 - отключить электроэнергию.

КЗ 1 - передать продукт на склад.

Управляющие воздействия формируются как совокупность микрокоманд и можно записать, что каждое

XI =и

7=1

Следовательно, множество управляющих воздействий:

Хх - К1у К2 иК15иК16;

Х2 -К2иК17;

Х3 - КЗуК4у К18 уК19;

Х4 - К5 оК20;

Х5 - Кб 0К7 иКЮ;

Х6 -К8у К9 уКИ;

Х7 - К9;

Х8-К120К13 уКМ; 1

Х9 - К21у К26;

Хю ~ К22;

Хц-К23;

Х12 - К24;

Х13-К25;

Х14 - К13 уК27;

Хи-КбиЮЗ;

Х!6 - К28;

Хп - К29;

Х18-К30;

Х19-КЗ1.

Для рассматриваемого технологического процесса контролируемые воздействия Х<1 = {Хх ,Х2 ,...,Хх7 ,Хх9}(рисЛ.2.). Нештатным воздействием является Х18. Например, когда автомат находится в состоянии (¡)5, поступление контролируемого воздействия Х5 переводит его в состояние С>6. Если в этом же состоянии поступает нештатное воздействие Хх8, то система переходит в состояние С>9, которое предусмотрено для ситуации отключения электроэнергии, и оно не может считаться случайным, так как предварительно сформирована цепь событий постепенно оста -

Рис. 1.2. Автоматный графоид процесса производства бисульфата натрия.

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

Алгоритм преобразования ДСМ в детерминированный автомат.

1. Шаг 1=0.

2. Является ли текущее состояние С! конечным? Если да, то перейти к

4

шагу 6; иначе перейти к шагу 3.

3. Возможно ли поступление случайного воздействия от внешней среды? Если да, то перейти к шагу 4; иначе - к шагу 5.

4. Если при поступлении случайного воздействия Х8 автомат переходит в состояние С)5, а при поступлении контролируемого воздействия Хс1 - в состояние С^ , то:

4.1. Взвесить контролируемый переход Хй , а каждый возможный неконтролируемый - Х5;

4.2. 1 е 5 , каждое из которых является результатом поступления воздействия Х3] соответственно.

5. Увеличить значение счетчика 1 на 1. Перейти к шагу 2.

6. Конец алгоритма.

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

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

осуществляется их декомпозиция на абстрактном уровне проектирования.

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

Разработке различных аспектов проблемы уменьшения размерности решаемых при проектировании автомата задач посвящены исследования ряда зарубежных и отечественных ученых.

Хартманис, впервые исследовавший эту задачу, ввел специальный язык-язык разбиений на множестве состояний автомата со свойством подстановки - СП - разбиений [11]. Дальнейшее развитие язык СП-разбиений получил в [12], где Хартманисом и Стирнзом введено понятие системы множеств и создана абстрактная математическая система -алгебра пар. Системы множеств отличаются от разбиений тем, что они могут иметь пересекающиеся блоки (подмножества). Это обобщение позволяет находить разложение автомата за счет введения избыточных состояний (расщепления состояний). Для повышения возможностей этого подхода Нобуеки, Тадаши, Нориоши предложили расширение этой алгебры до алгебры троек, четверок, ..., п-к, что в свою очередь, было основано на использовании свойств соответствующих разбиений.

В работах Йоли [13, 14] построение декомпозиции основано на нахождении униформных допустимых разбиений, являющихся частный случаем СП-разбиений- случаем, когда во всех блоках разбиения содержится равное число элементов. Для нахождения допустимых униформных разбиений Иоли использует аппарат гомоморфного отображения графов.Это связано с рассмотрением всех частичных подграфов автоматного графоида по буквам входного алфавита. Необходимость содержательного анализа всех переходов автомата делает практически невозможным разработку эффективных алгоритмов решения задачи декомпозиции.

Метод, позволяющий находить для произвольного автомата эквивалентный ему автомат, на множестве состояний которого существует хотя бы одно разбиение со свойством подстановки и, вследствие этого, разделимый на два подавтомата, предложен Кохави[15]. Однако, в работе Кохави не содержится процедуры, которая бы позволила по виду заданной таблицы переходов определять эффективность предложенного метода.

В работах Григорян А.К. [16, 17] разработан метод, позволяющий по двум заданным автоматам находить третий, такой, что в композиции с одним из заданных он дает автомат, эквивалентный заданному автомату.

Расширив понятие разбиений со свойством подстановки введением ПС-связки, О.П.Кузнецов исследовал задачу декомпозиции автоматов с разделением входов [18]. Однако этот метод декомпозиции применим к сравнительно узкому классу автоматов, являющемуся подклассом автоматов с СП-разбиением на множестве состояний.

Наиболее полное исследование и всесторонняя разработка проблем, связанных с декомпозицией конечных автоматов, содержится в цикле работ [19-24], проведенных под руководством А.В.Мелихова. Эти

4

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

Из различных видов декомпозиции, разработанных в перечисленных источниках, задаче ослабления функциональной связности и уменьшения взаимного влияния компонент разложения при сохранении максимального быстродействия и универсальности в наибольшей степени соответствует параллельная декомпозиция [42, 43, 58] с общим входом и общим выходным преобразователем.

Такая декомпозиция может быть проиллюстрирована следующим образом на рис. 1.3.; где KQ -комбинационная схема i-того автомата ; Ц -память i-того подавтомата; X - множество входных состояний исходного

п

X Y = f(X,S)

—» -h КС

-.....-W

а)

б)

Рис.1.3. Одно- а) и многокомпонентный б) автомат

и компонентных автоматов ; У - множество выходных состояний автомата [34, 53].

Такому представлению автомата в терминах функций на графах (автоматных графоидов) соответствует разложение графа переходов заданного автомата О = < 8, и > в частичное декартово произведение графов

в! = < 8ьи1> ; = < 82,и2> ;...; ^ = < ЗД>

такое, что

ОсЦв, ,

I

где в! - граф переходов 1- го компонентного автомата.

Для этой цели в [25, 27, 35, 37] предложен аппарат раскраски вспомогательного неориентированного графа , называемого графом зацепления 03, спектром красок. Носитель графа зацепления совпадает с носителем графоида заданного автомата, а сигнатура из определяется [26] выражением

(( 3 Хк ,ХШ) (Хк сХт)) (Р(81Хк) = 8а&Р(^Хт) =

I

-> {8ь8(}еи,. (1.2)

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

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

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

Для частичной компенсации дефицита информации было введено понятие степени зацепленности. Согласно [26] состояния в! и Sj к-зацеплены, если вершины $ и ^ графоида являются началами непересекающихся путей длины 'к' с одинаково взвешенными соответствующими участками, т.е. ( в! е Цз(к) & 83) £ Ш^Ч

Для порядкового ряда графов зацепления С3(1), Оэ(2) , ..., Оэ(к), очевидно, справедливо

Ь ( 03(1)) > И ( 03(2)) > ... > Ь ( С3(к)), где - И (03(к)) - хроматическое число графа зацепления. Построение этого ряда ведется до тех пор, пока не будет выполнено условие

Ь(Оза))<чУ,

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

и = { (из(1)\из(2)) и (из(2)\ из(3)) и...и(из(М)\ и,®) }.

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

1.4. Выводы

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

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

Показана возможность преобразования ДСМ в детерминированный автомат и процедуры этого преобразования, а также целесообразность

I

этого преобразования на примере реального процесса.

2. АНАЛИЗ АВТОМАТОВ АВТОНОМНОГО ФУНКЦИОНИРОВАНИЯ

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

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

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

Попытка восполнить дефицит информации построением порядкового ряда графа зацепления Оз(1), Оз(2),... , Оз(1с) приводит к громоздким конструкциям, при анализе которых, порой приходится решать задачи комбинаторной сложности. Пусть, например, автомат задан одним из графоидов 0x1, Ох^ вхк (рис.2.1.). Эти графоиды трансформируются в одну и ту же структуру графа зацепления - полный подграф плотности Р(0)=К

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

Рис. 2.1 Структуры-прообразы полных подграфов графа зацепления.

ни зацепленности с последующей реализацией зависимой раскраски графа [27, 62] может привести к удовлетворительному результату в первых двух случаях [41 -44, 81, 84, 85].

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

Р( вз{1)) > Р(вз(2)) > ... >Р(Оз(й))

имеет место

V к ( Р (Оз(к)) = Р ( вз(к+1))) и независимо от того существует объективно нетривиальное разложение или нет, оно не может быть найдено выполнением различного рода преобразований над графом зацепления. Для повышения универсальности метода декомпозиции и с целью исключения бесперспективного перебора вариантов при разложении графоидов, содержащих контуры автономного функционирования, целесообразно использовать еще одну формализацию, связанную с анализом структур графоида, в первую очередь, контуров автономного функционирования [63]. Актуальность исследования разложимости контуров обусловлена кроме того тем, что графы переходов целого класса автоматов, известных как микропрограммные, представляют собой различные сочетания контуров.

Ограничения на разложимость автоматов, накладываемые контурами автономного функционирования, определяются длиной контура. Поэтому представляет интерес исследование разложимости собственно контура автономного функционирования. Пусть необходимо построить п-компонентное разложение контура длины Ь. В дальнейшем будем отождествлять имя контура с его длиной. Обозначим через А е I = = { 1, 2, ..., п }, | С); | = а; множество состояний в ьтой компоненте разложения и перенумеруем вершины, образующие контур, в соответствии с их упорядоченностью. Вершинам контура поставим во взаимнооднозначное соответствие последовательности (с^ц, ,Яш), где

qH e Qb q2¡ e Q2, ..., qni e Qn . Эти последовательности будем называть также спектрами красок, а их элементы - красками. Необходимость обеспечения детерминированности переходов в компонентах разложения приводит к установлению некоторой регулярности следования индексов красок в каждом из разрядов последовательности. Пусть, например, в первом разряде индексы первых a¡ вершин sb s2, ..., sai образуют последовательность (qn, qi2, qiai )> тогда такую же последовательность должны образовывать индексы, сопоставляемые следующим ai вершинам sai+i, sai+2, ..., sai+ai и т. д. Исходя из этого может быть сформулирована теорема 1.

Теорема 1 . Для того, чтобы контур автономного функционирования был разложим в n-компонентное произведение, необходимо и достаточно, чтобы длина контура L равнялась наименьшему общему знаменателю U чисел аь а2,..., ац.

Доказательство.

Необходимые условия. Пусть контур разложим. Тогда вершинам контура можно сопоставить последовательность вершин (qn, q2j, ..., qni), так, что в каждой из компонент j они образуют последовательность длины аь повторяющуюся целое число L / a¡ раз, так как в противном случае j-ая компонента была бы недетерминированной. Из этого следует, что L является общим знаменателем чисел a¡/jeJ={l,2, ..., п}.С другой стороны, если бы существовал L' < L, который также является общим знаменателем чисел aj, то начиная с вершины с номером L'+l происходило бы повторение последовательностей, отождествленных уже первыми U вершинами, что нарушает взаимную однозначность соответствия между вершинами контура и последовательностями ( qn, q2j,..., qni). Таким образом, L = L' - наименьший общий знаменатель чисел аь а2,ап.

Достаточные условия. Пусть L- наименьший общий знаменатель чисел аь а2,..., ап. Тогда, упорядоченная последовательность ( q j, aj) вершин j- той компоненты разложения ( q jb q j2, ..., qjaj) целое число раз уклады-

вается в Ь, что исключает возможность возникновения недетерминированных переходов. Взаимная однозначность соответствия между последовательностями ( я2ь Яш) и вершинами контура обеспечивается тем, что первая вершина, которой соответствует последовательность

Япап) >

является в этом случае последней вершиной контура. Это доказывает достаточность условия теоремы.

Проиллюстрируем теорему для случая двухкомпонентного разложения конкретными примерами. Во взаимно - однозначное соответствие вершинам Бк сопоставим пары

( Р ) / еР, Ч) где Р и - множества состояний в первой и второй компонентах разложения. Пусть Ь=7 (рис. 2.2а). Этот контур без нарушения порядка следования красок можно раскрасить либо одной, либо семью красками и для него существует только тривиальное разложение.

Пусть Ь=24=4х6=3х8. При раскраске вершин этого контура, в соответствии с первым разложением, начиная с 13-той вершины, спектры повторяются. Если же использовать второе разложение Ь , тот получим нетривиальную 2-х компонентную декомпозицию.

Если Ь=6=2хЗ ,в этом случае имеем единственное разложение для Ь и оно удовлетворяет условию теоремы, и как видно из рис 2.4. вершины

контура можно раскрасить без нарушения регулярности следования кра-

6

сок в компонентах спектра.

На рис. 2.26 и 2.3(а и б) приведена двухкомпонентная раскраска контуров спектром, порождающая разложение с минимально возможными мощностями множеств состояний в компонентах.

а) б)

Рис.2.2. Раскраска контуров длины а) Ь = 7 и б) Ь = 8

а) б)

Рис. 2.3 Двухкомпонентная раскраска контура Ь=12 для тривиального случая а)Ь=12х1 и нетривиального случая б ) Ь=3х4

Рис 2.4.Двухкомпонентная раскраска контура Ь=6=2хЗ ( а) и компоненты разложения (б ).

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

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

В случае, когда длина контура Ь (контур) не удовлетворяет условию теоремы, то гомеоморфным расширением носителя они приводятся к виду, когда Ь =1/. Длины контуров мощю представить в виде произведения = I Р^ х I I, и = IР] I х | |, где множество вершин в первой компоненте ¿-того контура, - множество вершин второй компоненты I -того контура. Мощности этих множеств равны числам красок в первой и второй компоненте раскраски соответственно, с последующим установлением упорядоченности индексов вершин (красок) в первой и второй компоненте. Вершинам контуров присваиваются номера от 1 до Ъх и от 1 до , независимо от истинных индексов вершин, образующих эти контуры.

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

Для пересекающихся контуров одинаковой длины порядок раскраски и длина общей части /у не имеют значения, тогда как при раскраске пересекающихся контуров различной длины результат раскраски зависит как от длины общей части, так и от порядка раскраски. Например, на рис.2.5а для контуров Ь]= Ь2 =10, длина общей части Ц =5, состоит из множества вершин 8у ={84 ,вб ,87 } и первым раскрашен контур Ьь а на рис. 2.56 /ц = I вц I = 3 и вц = { 88,89 ,вю} и первым раскрашен контур 2.

Р2Я4 Р1ЧЗ

а)

Р2Я4 Р2Ч4 Р^З

I

б)

Рис. 2. 5. Двухкомпонентная раскраска Ь=10 с 1у=3 а) и1у=5 б)

В случае пересекающихся контуров разной длины для Ц возможны следующие значения:

1) /у = 0 , т.е. контуры не пересекаются.

2) 0 < /у < min (IР | J Q |); для таких случаев ограничения определяются спектрами вершин Sy , т.к. их раскраска в первом контуре устанавливает регулярность следования красок в общей части.

3) Ц = min (| РI J QI ); раскраска контуров с такой общей частью позволяет сохранить детерминированность переходов в обоих контурах.

4) /у > min ( | Р | J Q | ); для контуров с такой общей частью невозможно двухкомпонентное разложение автомата, т.к. установившаяся регулярность следования красок для вершин Sy, присвоенная им при раскраске первого контура, не позволяет целое число раз повторится на длине второго контура, что ведет к недетерминированности переходов, если не увеличить число красок соответствующим образом (рис. 2.6 ).

Исключением для /у являются случаи, когда разложение пересекающихся контуров Li = I Pf | х I Qi I и Lj = I Pj I x | Qj | имеет вид:

а) I QiI> IPil = IPjl < I Qj I;

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Дедегкаева, Лариса Магометовна

4.3. Выводы

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

Спроектирована также абстрактная декомпозиция системы управления промышленной автоматики. Графоид автомата управления системы очистки воды содержит 35 вершин, в результате декомпозиции получили два подавтомата с 5 и 7 состояниями соответственно.

ЗАКЛЮЧЕНИЕ

По результатам диссертационной работы сделаны следующие выводы:

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

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

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

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

5. Созданы математические и программные средства декомпозиции СЛУ на абстрактном этапе синтеза.

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

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

Список литературы диссертационного исследования кандидат технических наук Дедегкаева, Лариса Магометовна, 1999 год

Литература

1. Цао.С. Сравнительный анализ динамики непрерывных и дискретно-событийных систем // ТИИЭР, т.77, №1, январь 1989.

2.Райтер Р., Вальран Ж.С. Распределенное имитационное моделирование дискретно-событийных систем // ТИИЭР, т.77, №1, январь 1989.

3. Рамадж П.Дж.Г., Уонем У.М. управление дискретно-событийными системами // ТИИЭР, т.77, №1, январь 1989.

4. Зиглер Б.П. Представление динамических систем на основе дискретно-событийных описаний: Интеллектуальное управление на базе событий // ТИИЭР, т.77, №1, январь 1989.

5. Инан К.М., Варайя П.П. Алгебры дискретно-событийных моделей // ТИИЭР, т.77, №1, январь 1989.

6. Коэн Г., Молл ер П., Кадра Ж.-П., Вьо М. Алгебраические средства оценивания характеристик дискретно-событийных систем // ТИИЭР, т.77, №1, январь 1989.

7. Глушков В.М. Синтез цифровых автоматов. - М.: Физматгиз, 1962.

у ■

8. Талль А.А. Анкетный язык и абстрактный синтез минимальных последовательностных машин // Автоматика и телемеханика, №6, т. XXV, 1964.

9. Пийль Е.И. Кодирование состояний входа в микропрограммном автомате. Сб. Автоматы и управление. - М.: Наука, 1972.

10. Горбатов В.А. Схемы управления ЦВМ и графы. - М.: Энергия, 1971.

11. Hartmanis I. On the state assignment problem for sequential mashines I, IRE Trans. On Electronic Computers, EC-10, N2, 1961.

12. Hartmanis I., Stearns R.E. Pair algebra and its application to automata theory / Information and control, I., N7, 1964.

13. Yoli M. The cascade decomposition of sequential machines / I. IRE Trans. On Electronic Computers, EC-10, N4, 1961.

14. Yoli M., Ginsburg A. On homomorphic images of transition grafs / I. Franklin Inst., 278, N.5, 1964.

15. Kohavi Z. Secondary state assignment for sequential machines / I. IRE Trans. On Electronic Computers, EC-13, N.3, 1964.

16. Григорян A.K. Метод декомпозиции конечных автоматов // Автоматика и телемеханика, №5, 1968.

17. Григорян А.К. Метод декомпозиции конечных автоматов с выделением выходного и входного автоматов // Автоматика и телемеханика, №10, 1968.

18. Кузнецов О.П. Параллельная декомпозиция автоматов с разделением входов // Автоматика и телемеханика, №3, 1969.

19. Мелихов А.И. Некоторые операции над графами // Изв. АН СССР. Техн.кибернетика, №6, 1964.

I

20. Мелихов А.И., Дворянцев Ю.А. Разложение графов и конечных автоматов относительно операции умножения // Кибернетика, №3, 1965.

21. Мелихов А.И., Бернштейн JI.C., Карелин В.А. Разложение графов и конечных автоматов по операции суммирования // Изв. АН СССР. Техн.кибернетика, №2, 1968.

22. Мелихов А.И., Дворянцев Ю.А. Теоретико-множественные и алгебраические операции над конечными автоматами // Изв. АН СССР. Техн.кибернетика, №3, 1967.

23. Мелихов А.И., Бернштейн JI.C., Карелин В.П. О декомпозиции абстрактных автоматов // Кибернетика, №3, 1969.

24. Мелихов А.И. Ориентированные графы и конечные автоматы.- М.: Наука, 1971.

25. Горбатов В.А., Дедегкаев А.Г. Метод расщепления запрещенных фигур при построении параллельной декомпозиции систем / Сб. Прикладные вопросы теории систем и системотехнике.- М.: МДНТП, 1973.

26. Горбатов В.А., Дедегкаев А.Г. Запрещенные фигуры при параллельной декомпозиции автоматов / В кн.: Оптимизация дискретных систем управления.- ГВЦ Госплана СССР, 1972.

27. Горбатов В.А., Макаренков C.B. Запрещенные фигуры при совместной минимизации системы булевых функций в классе решетчатых ДНФ / В кн.: Оптимизация дискретных систем управления. - ГВЦ Госплана СССР, 1972.

28. Дедегкаев А.Г. Использование зависимой раскраски графов при построении декомпозиции автоматных операторов / В кн. Логическое управление в промышленности.- Ижевск, ИМИ, 1984.

29. Горбатов В.А., Кафаров В.В., Павлов П.Г. Логическое управление технологическими процессами.- М.: Энергия, 1978.

30. Зарецкий С.А. Технология электрохимических производств.- М.: В.Ш., 1970. '

31. Дедегкаев А.Г., Динцис Д.Ю. Особенности функционирования управляющего автомата в случайной среде // Международный конгресс информатизации пам. А. Нобеля. Материалы конгресса.- Ижевск, 1995.

32. Дедегкаев А.Г., Динцис Д.Ю. Частный случай детерминирования конечного автомата / Сб. Труды СКГТУ, вып.1, Терек, Владикавказ, 1995.

33. Айзерман М.А., Гусев Л.А., Розоноэр Л.И., Талль A.A. Логика. Автоматы. Алгоритмы.- М.: Физматгиз, 1963.

34. Отчет о НИР «Разработка параллельных систем логического управления для САПР «Компас-Р»(Заключительный)» , Орджоникидзе, 1985.

35. Горбатов В.А. Теория частично упорядоченных систем.- М.: Сов.радио, 1976.

36. Горбатов В.А. Синтез композиции операционного и управляющего автоматов в вычислительной технике.- М.: В.Ш., 1973.

37. Горбатов В.А. Семантическая теория проектирования автоматов.- М.: Энергия, 1979.

38. Горбатов В.А., Останков Б.Л., Фролов С.А. Регулярные структуры автоматного управления.- М.: Машиностроение, 1980.

39. Автоматизация проектирования сложных логических структур / Горбатов В.А., Демьянов В.Ф., Кулиев Г.Б. и др. Под ред. проф. В.А.Горбатова.- М.: Энергия, 1978.

40. Горбатов В.А. Интеллектуальные информационные технологии и стратегии (состояние и перспективы) // Информационные технологии, январь, 1995.

41. Харари Ф. Теория графов.- М.: Мир, 1973.

42. Горбатов В.А. Информационная математика.- М.: Наука, 1997.

43. Горбатов В.А. Основы дискретной математики.- М.: В.Ш., 1986.

44. Ope О. Теория графов.- М.: Наука. Главная редакция физико-математической литературы, 1980.

45. Поспелов Д.А. Логические методы анализа и синтеза схем.-Л.- М.: Энергия, 1964.

46. Горбатов В.А., Павлов П.Г., Четвериков В.Н. Логическое управление информационными процессами.- М.: Энергоиздат, 1984.

47. Горбатов В.А., Крылов А.В, Федоров Н.В. САПР систем логического управления.- М.: Энергоиздат, 1988.

48. Планирование эксперимента в исследовании технологических процессов. Под ред. Э.К.Лецкого.- М.: Мир, 1977.

49. Горбатов В.А. Минимизация логических структур при общем подходе к синтезу. Теория дискретных систем.- М.: изд. МЭИ, 1967.

50. Горбатов В.А., Смирнов М.И., Хлытчиев И.С. Логическое управление распределенными системами.- М.: Энергоиздат, 1991.

51. Горбатов В.А. Синтез микропрограммных автоматов по временным диаграммам их функционирования. Цифровая вычислительная техника и программирование, вып.5- М.: Сов.радио,1969.

52. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов.-М.:Энергия, 1970.

53. Евреинов Э.В., Прангишвили И.В. Цифровые автоматы с настраиваемой структурой.- М.: Энергия, 1974.

54. Закрецкий А.Д. Алгоритмы синтеза дискретных автоматов.- М.: Наука, 1971.

55. Рогинский В.Н. Основы дискретной автоматики.- М.: Связь, 1975.

56. Минский М.М. Вычисления и автоматы.- М.: Мир, 1971.

57. Трахтенброт Б.А. Алгоритмы и вычислительные автоматы.- М.: Сов.радио, 1974.

58. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика.- М.: Наука. Физматлит, 1999.

59. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.- М.: Мир, 1979.

60. Горбатов В.А. Оценки при выборе направления вычислений в задачах синтеза конечных автоматов // Изв. АН СССР. Техническая кибернетика.-1970.-№4.

61. Горбатова М.В. Теория трасс / Информационные коммуникации, сети, системы и технологии.-М.: МАИ, 1993.

62. Зыков А.А. Теория конечных графов.- Новосибирск: Наука, 1969.

63. Майника Э. Алгоритмы оптимизации на сетях и графах.- М.: Мир. 1981.

64. Поспелов Д.А. Логико - лингвистические модели в системах управления.- М.: Энергия, 1981.

65. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика.- М.: Мир, 1980.

66. Свами М., Тхуласираман К. Графы, сети и алгоритмы.- М.: Мир, 1984.

67. Юзвишин И.И. Инфомациология.- М.: Радио и связь, 1996.

68. Дедегкаева Л.М. Технологические процессы как объекты управления / В кн. - Электронные приборы и устройства в промышленности. Тезисы докладов юбилейной конференции. - Владикавказ: Терек. - 1994.

69. Цаллагов А.Г., Маркман М.Я., Дедегкаева Л.М. Программируемый контроллер технологических процессов / В кн. - Электронные приборы и

устройства в промышленности. Тезисы докладов юбилейной конференции. - Владикавказ: Терек - 1994.

70. Дедегкаева Л.М. Использование планирования эксперимента при проектировании АСУТП / Труды СКГТУ, выпуск 5.- Владикавказ: Терек, 1998.

71. Дедегкаев А.Г., Рязанов В.П., Дедегкаева Л.М. Применение дискретной модели управления при проектировании металлургических процессов / Сб. Логическое управление организационными структурами. СКГТУ, Владикавказ: Терек, 1998.

72. Дедегкаев А.Г., Динцис Д.Ю., Дедегкаева Л.М. Особенности

I

графоидов стохастических автоматов, накладывающие ограничения на их разложимость / Сб. Логическое управление организационными структурами. СКГТУ, Владикавказ: Терек, 1998.

73. Динцис Д.Ю., Дедегкаева Л.М., Рязанов В.П. О возможности преобразования автоматных графоидов технологических процессов к стандартному виду / Труды СКГТУ, выпуск 5, Владикавказ: Терек, 1998.

74. Дедегкаев А.Г., Пагиев К.Х., Дедегкаева Л.М. Некоторые особенности раскраски вершин контуров автономного функционирования / В сб. «Логическое управление процессами и системами». Материалы международной конференции «Информационная математика, кибернетика, искусственный интеллект в информациологии», Москва-Владикавказ, 1999.

75. Пагиев К.Х., Дедегкаева Л.М. Некоторые особенности декомпозиции микропрограммных автоматов управления технологическими процессами / Труды СКГТУ, выпуск 6, Владикавказ: Терек, 1999.

76. Хадонов З.М., Динцис Д.Ю., Дедегкаева Л.М. Алгоритм выделения контуров автономного функционирования в автоматном графоиде / В сб. «Логическое управление процессами и системами». Материалы международной конференции «Информационная математика, кибернетика, искусственный интеллект в информациологии», Москва-Владикавказ, 1999.

77. Норенков И.П. Введение в автоматизированное проектирование технических устройств.- М.: В.Ш., 1986.

78. Цурков В.И. Декомпозиция в задачах большой размерности.- М.: Наука, 1981.

79. Романовский И.В. Алгоритмы решения экстремальных задач.- М.: Наука, 1977.

80. Бурков В.Н., Ланда Б.Д., Ловецкий С.Б. Сетевые модели и задачи управления. -М.: Сов.радио, 1967.

81. Горбатова М.В. Быстродействующий алгоритм раскраски вершин графа / В кн.: Логическое управление в промышленности.- Ижевск: ИМИ, 1984.

82. Шнейдер A.A. Классификация и анализ эвристических алгоритмов раскраски вершин графа // Кибернетика, 1984, №4.

83. Советов Б.Я., Яковлев С.А. Моделирование систем. — М.: Наука, 1987.

84. Малина О.В. Сравнительная характеристика множеств запрещенных фигур объектов различной природы // Информационная математика в информациологии.- Сборник трудов, Москва - Ижевск, 1997.

85. Лашенков A.B. Декомпозиционный подход к раскраске вершин графа // Академический сборник научных трудов. Проблемы характеризационного анализа и логического управления.- М.: 1999.

I