Лекция 7. Моделирование систем на основе теории сетей Петри 1
Работа добавлена на сайт samzan.net:
Лекция 7. Моделирование систем на основе теории сетей Петри
1. Сети Петри
Цветные сети Петри. Появление сетей этого класса связано с концепцией использования различных меток. Ранее все метки предполагались одинаковыми. Механизм функционирования сетей был связан только лишь с количествами меток во входных позициях переходов и определялся общими для всех меток условиями возбуждения переходов и правилами изменения различных позиций при выполнении сети. В цветных сетях каждая метка получает свой цвет. Условия возбуждения и правила срабатывания переходов для меток каждого цвета задаются независимо. Множество используемых при реализации цветных сетей красок выбирается конечным или бесконечным (например, счётным). При моделировании систем цветные сети чаще всего используются для построения компактных формальных и графических представлений, в составе которых имеются однотипные по структуре и характеру функционирования группы объектов.
Сети Петри со сдерживающими дугами. Сдерживающая дуга из позиции pi в переход tj имеет маленький кружок (а не стрелку). Кружок означает отрицание (“не”). Правила запуска изменяются следующим образом: переход является разрешённым, когда фишки присутствуют во всех его (обычных) входах и отсутствуют в сдерживающих входах. Переход запускается удалением фишек из всех его (обычных) входов. Так можно описывать переходы, «исключающее ИЛИ». В обычных СП переход запускается, когда все его входы имеют фишки (логика И). Переход “исключающее ИЛИ” запускается тогда и только тогда, когда только один из его входов имеет фишки, а все другие фишек не имеют. Когда переход запускается, он удаляет фишку только из входа с фишками.
Имеются ещё два других важных расширения СП.
Сети Петри с назначением приоритетов. Переходам могут быть поставлены в соответствие приоритеты так, что если ti и tk оба допустимы, то переход с высшим приоритетом будет запущен первым. Механизм назначения приоритетов может устанавливать порядок срабатывания переходов при возникновении конфликтов. Во-вторых, используют временные сети Петри.
Временные сети Петри. Во временных сетях Петри каждому переходу tj сопоставляются два момента времени τ1,j и τ2,j. Переход tj может быть запущен, только если он был разрешён к моменту времени τ1,j. Если он является разрешённым, то должен быть запущен до наступления момента времени τ2,j. Рассмотрим временные сети более подробно.
Формально временные сети задаются набором (P, T, I, O, μ°, Z), где P, T, I, O, μ имеют обычный смысл, а Z: P→R+ функция времени задержки меток в позициях сети. Работа временных сетей подчиняется следующим правилам:
▪ метки в позициях могут быть доступными или же недоступными;
▪ переходы считаются возбуждёнными, если все их входные позиции имеют метки и эти метки доступные;
▪ переходы срабатывают мгновенно в тот самый момент, как только будут выполнены условия их возбуждения. Правила перехода меток во временных сетях совпадают с аналогичными правилами для сетей Петри;
▪ каждая метка, совершившая переход из в , будет недоступной в в течении времени , начиная с момента её появления в . По истечению времени метка становится доступной.
Одним из интересных применений временных сетей являются задачи анализа периодических режимов функционирования систем. В сети можно обеспечить периодический режим работы с минимальным периодом. Такой режим достигается при использовании специального расписания включения переходов сети.
Расширенные сети Петри. Характерным для имитационных моделей формализующим фактором является применённый в них новый механизм описания состояния сети. Метки в расширенных сетях Петри являются носителями определённого количества атрибутов, в качестве которых могут выступать числа, логические переменные, текстовые конструкции, массивы, таблицы. Атрибуты меток могут быть функциями времени. Переходы меток при выполнении сети сопровождаются изменениями значений атрибутов. Эти изменения подчиняются специально определяемым в модели правилам (процедурам перехода). В расширенных сетях Петри средства описания процессов синхронизации событий значительно более развиты, чем рассмотренный ранее механизм блокировки меток во временных сетях.
А теперь рассмотрим конкретные варианты реализации расширенных сетей Петри.
2. Временные сети событий (ВСС)
ВСС=(Р,Т,Е) – связный биограф, где Р – конечное непустое множество позиций, Т – конечное непустое множество переходов, Е - отображение вида Т→Ф(Р); Ф(Р) – множество всех подмножеств Р. Позиции сети , отображают в модели все основные состояния процессов. Переходы , соответствуют событиям. Отображение находит все смежные с tj позиции из множества Р. Состояние ВСС определяется маркировкой позиций М: Р→N – функция маркировки - разметка сети. Применяемые в ВСС метки имеют атрибуты: - вектор атрибутов метки в позиции . Значения некоторых атрибутов могут быть функциями времени. Например, если позиция моделирует в сети состояние “Идёт обработка детали”, то атрибут в списке атрибутов метки может означать время, оставшееся до конца обработки.
Как правило, . Равенству соответствует тот факт, что состояние некоторого процесса в системе, представленного в модели некоторым элементарным высказыванием, реализовалось. Если , то наиболее простыми интерпретациями в этом случае являются состояния, возникающие при накоплении объектов, участвующих в процессе. Важно указать, что при необходимо упорядочивать множество меток в позиции. Например, если моделирует стек или очередь, то метки в позиции упорядочиваются линейно.
Механизм изменения состояний ВСС связан с выполнением переходов . Каждый переход можно записать в виде тройки . Здесь - условия возбуждения, - схема выполнения, - процедура перехода. Условие возбуждения - это предикат, определённый на множестве позиций из , истинный только в том случае, когда реализуется некоторая заданная разметка позиций множества . Кроме того, условие возбуждения, может включать ещё проверку значений атрибутов меток. Если значение какого-то атрибута является функцией времени, то обеспечивается соответствующая значению данной функции времени задержка. Схема выполнения определяет изменение разметки позиций сети при срабатывании перехода. Пусть - упорядоченное множество позиций, смежных с . Тогда схема - это вектор, элементы которого образуют биекцию с элементами множества . Любое положительное целое число в означает число меток, помещённых в соответствующую позицию после выполнения перехода. Целые отрицательные числа в указывают число удалённых меток из соответствующих позиций. Нулевые значения компонент отмечают изменяемые позиции (каждая изменяемая позиция не обязательно имеет единственную метку и образует с переходом цикл длины 2). Не изменяемые в результате срабатывания перехода позиции отмечаются в символом (*). Процедура перехода представляет собой правила вычисления атрибутов (для позиций, отмеченных в нулём) или добавления (удаления) меток.
Графическое изображение ВСС имеет некоторые отличительные особенности. Каждая позиция ВСС обозначатся кружком, каждый переход - барьером, позиции и переходы соединяются ориентированными или неориентированными рёбрами в соответствии с отображением Е и схемой выполнения перехода . Ребро не ориентируется, если в схеме для соответствующей позиции указывается символ (*). Ребро ориентируется от позиции к переходу, если в для этой позиции задано отрицательное число, от перехода к позиции – если положительнее число. Ребро будет двунаправленным, если задан 0.
3. Е-сети
Е-сети применяются в качестве имитационных моделей систем, структурируемых в виде сетей событий. Формально они определяются набором из 8 переменных:
Р – конечное непустое множество позиций сети P={}; - множество периферийных (не внутренних) позиций; - множество решающих позиций. Позиции играют в Е-сетях ту же самую роль, что и в сетях Петри. Обозначаются графически также кружком. Периферийные позиции используются для моделирования взаимосвязей системы с внешней средой. Решающие позиции не имеют прямых аналогов в СП. С их помощью в Е-сетях обеспечивается разрешение конфликтов и синхронизация событий. С каждой решающей позицией связан некоторый список предикатов, применяемый для формального описания условий выполнения переходов. Задаются эти позиции шестиугольниками.
В каждом состоянии сети позиции могут иметь или не иметь метку. Число меток в каждой позиции ≤1 (М: Р→{0,1}). Отмечается метки жирной точкой.
Второй элемент набора - конечное непустое множество переходов А={an}, которые задаются барьерами.
Третий элемент набора I(A), O(A) – множество позиций, смежных с переходами по входу (I) и выходу (О). Пары и , составленные из смежных позиций и переходов, соответствуют дугам сети.
Четвёртый элемент набора функция Z: A→R+, с помощью которой в Е-сетях задаются значения времени выполнения переходов, т.о. имитируются временные задержки, связанные с реализацией моделируемых событий.
Пятый элемент набора задаёт непустое конечное множество переменных – количественных оценок состояния модели.
Шестой элемент набора описывает множество решающих процедур, применяемых для разрешения конфликтов на переходах и синхронизации событий.
Седьмой элемент набора - множество процедур перехода.
Восьмой элемент набора обозначает начальную маркировку позиций.
При построении Е-сетей используется ограниченный набор типов переходов: T, I, F, X, Y, MX, MY (см. табл.). Два последних являются макрорасширениями X и Y переходов.
Таблица . Схемы выполнения переходов каждого типа
|
Графические и символьные изображения |
Комментарий |
|
|
(1,0)→(0,1) Переход активный, если р1 имеет метку а р2 – свободна. После срабатывания перехода появляется метка в р2, метка из р1 удаляется |
||
|
(1,1,0)→(0,0,1). Переход активный, если р1и р2 имеют метки, а p3 – свободный. После срабатывания перехода появляется метка в p3, метки из р1 и р2 удаляются |
||
|
(1,0,0)→(0,1,1) Переход активный, если р1 имеет метку, а р2 и р3 свободны. После срабатывания перехода появляются метки в р2 и р3, из р1 метка удаляется |
||
|
(0,1,0,0) →(*,0,1,0) (1,1,0,0) →(*,0,0,1) (0,1,1,0) →(*,0,1,1) (0,1,0,1) →(*,0,1,1) (1,1,1,0) →(*,0,1,1) (1,1,0,1) →(*,0,1,1) |
Если р2 и p3 свободны, а в р1 имеется метка, то на переходе возникает состояние конфликта. Конфликт исключается по значению решающей позиции: если, то метка “переходит” из р1 в р2; если , то из р1 в р3. Значение находится в результате применения решающей |
|
|
процедуры . Её выполнение заключается в проверке значений предикатов pr1 и pr2 . При истинности какого-то одного из них , при истинности другого . Если оба ложные, то В этом случае решающая позиция блокирует переход до момента результативного выполнения процедуры . (* означает, что необходимо снова определить значение ). Если на переходе конфликта нет (свободна только какая-то одна выходная позиция) и имеется метка в позиции р1, то переход будет выполняться по Т-схеме и по единственно возможному пути, независимо от того, какое значение имеет при этом решающая позиция |
||
|
(0,1,1,0)→(*,0,1,1) (1,1,1,0)→(*,1,0,1) (0,1,0,0)→(*,0,0,1) (0,0,1,0)→(*,0,0,1) (1,1,0,0)→(*,0,0,1) (1,0,1,0)→(*,0,0,1) |
Аналогично вышеописанному |
Макропереходы определяются несколько сложнее, чем соответствующие схемы X и Y переходов. Однако, главным в них по-прежнему остаётся сравнение значений решающей позиции и меток инцидентных переходу дуг.
Каждый переход Е-сети имеет три характеристики и записывается как где - тип перехода; - время перехода; - процедура перехода. Переход выполняется в 3 этапа:
- Проверяются условия активности перехода, а для X и Y переходов ещё и находятся значения решающей позиции и определяется конкретная схема срабатывания.
- Реализуется задержка выполнения перехода на время Z и пересчитываются значения атрибутов метки по правилам, указанным в процедуре .
- В соответствии со схемой перехода изменяются маркировки его входных и выходных позиций.
4. Комби-сети
Наиболее полный набор средств описания дискретных и дискретно-непрерывных систем в виде сетей событий применяется при построении Комби-сетей. Множество Р позиций К-сетей объединяет 6 подмножеств: Рэ – элементарные, Рт – с временной задержкой, Рд – долгоживущие, Рг - гибридные, Рк – комплексные, Рм – макропозиции. Каждой позиции отвечает некоторый характерный для данной позиции набор атрибутивных переменных , . Позиции сети могут не иметь маркеров, иметь единственный маркер, накапливать маркеры (M: P→N). При выполнении сети общее число действующих в ней маркеров изменяется и в каждый текущий момент времени равно МА. Всё множество МА маркеров разбивается на 4 класса: булевские, с атрибутивными переменными, долгоживущие, изменяющие вид с элементарного на долгоживущие и обратно. С двумя первыми классами связаны элементарные маркировки (запрещены для позиций Рд), третьему и четвёртому классам соотносятся долгоживущие маркировки (запрещены для позиций Рэ, Рт, Рм). Каждый класс МК использует определённую структуру данных, все маркеры класса МК, за исключением булевского класса, имеют множество атрибутивных переменных .
Множество Т переходов К-сети состоит из 5-ти подмножеств: Тэ - элементарных, Тпр – с прерыванием, Тд – долгоживущих, Тк – комплексных, Тм – макропереходов. Каждый характеризуется набором атрибутивных переменных.
Объединение всех наборов атрибутивных переменных сети образует множество ATTR её локальных переменных.
Связи Е между позициями и переходами в К-сетях задаются обычным для сетей Петри способом: .
Необходимые условия возбуждения переходов описываются логическими выражениями. Переход может перейти в возбуждённое состояние, если соответствующее этому переходу логическое выражение будет истинным. Другое необходимое условие возбуждения связано с текущей разметкой входных и выходных позиций перехода. В тех случаях, когда количество маркеров в больше, чем это необходимо для возбуждения перехода, возникает вопрос о механизме выбора удалённых маркеров. Такими механизмами могут быть: FIFO, LIFO, HVF, LVF, согласно заданным приоритетам или по указанию пользователя.
После перехода в позицию маркер становится недоступным в ней на время задержки τ(). Значения τ() могут быть определены различными способами: выбор случайной величины с заданным законом распределения, назначение констант из множества неотрицательных целых чисел, выбором по указанию пользователя и т.д.
Если , необходимо указать конкретную позицию , в которую переходят маркеры. Могут быть различные механизмы: равновероятный по тестовым условиям, по значениям атрибутивных переменных маркеров или по указанию пользователя.
Ещё одна особенность выполнения К-сетей обусловлена структурой её связей: в позициях Рд, возможны конфликтные ситуации, связанные с необходимостью выбора какого-то одного из нескольких возбуждённых переходов, смежных с . Для исключения конфликтов этого вида в К-сетях применяются специальные механизмы случайного выбора, выбора по номеру перехода или по вероятности и другие. Большое разнообразие возможных вариантов построения схемы переходов в К-сетях обусловило разработку основного набора таких схем, а также способов построения составных схем, создаваемых на базе элементов из основного набора.
Интерпретация перехода “исключающее ИЛИ” с помощью сдерживающих дуг
0(tj)
0(tj)
+
р2
T(р1,р2)
р1
2
р1
I(р1,р2,p3)
р3
р1
F(р1,р2,p3)
р3
р2
р1
X(rj,р1,р2,p3)
р3
р2
rj
р1
р2
rj
р3
Y(rj,p1,p2,p3)
2. почему люди покупают
3. і Обов~язкова та необов~язкова проводка лоцманом судна
4. Жители Португалии как и граждане других южных стран любят вкусно и сытно поесть
5. от степени уплотнения и пустотности
6. Лабораторная работа По курсу Технические измерения и приборы Тема Изучение конструкции и тарировка и
7. Организация производства зерна
8. Омский государственный технический университет Л
9. научно опираясь на экономический технический и социальный эксперимент а также на научный анализ явлений
10. ДЫХАНИЕ - реферат за 9-й класс
11. Лабораторная работа 4 Спектральный анализ в пакете программ MTLB ЦЕЛЬ РАБОТЫ.
12. ощущение обозначаются начальные процессы обнаружения и кодирования энергии физического мира.html
13. Экотоксикология Учебное пособие
14. Предмет и методы статистики
15. Test 0 I Open the brckets. nn buy new house before she got mrried
16. Лабораторная работа 312 Определение внутреннего сопротивления батарейки.
17. реферат на военных кафедрах ВУЗа
18. на тему ldquo;Зміни в статевих органах молочних залозах в обміні речовин жінки під час вагітностіrdquo;
19. ЛД062013 Содержание 1 Общие положения
20. Научноисторические основы изучения проблемы дисциплины школьников.html