Модификации сетей Петри (иерархические сети)

РТУ МИРЭА Дизайн Дизайн И. И. Гайдель Гайдель 2007 2007 Теория сетей Петри и моделирование систем Лекция 3 Дизайн И. Гайдель 2007 0 Теория сетей )Петри и моделирование систем Основны е определения и обозначения Определение 1. Сеть Петри (СП) - это двудольный ориентированный мультиграф N = (P, T, I, O, µ0), где: P - конечное непустое множество элементов, называемых позициями; конечное непустое множество элементов, называемых переходами; I: PT{0,1,2...} и O: PT{0,1,2...} - функции инцидентности; µ0 : P{0,1,2...} - начальная разметка. T- n =P- мощность множества P, m =T - мощность множества T. СП обычно представляют в виде геометрического объекта. При этом позиции изображают кружками, переходы - черточками или прямоугольниками. Дуга проводится от позиции pi к переходу tj, если I(pi, tj) > 0, и от перехода tj к позиции pi, если O( pi, tj) > 0. Дизайн И. Гайдель 2007 0 ) Теория сетей Петри и моделирование систем Основны е определения и обозначения Кратность дуги, соединяющей входную позицию pi с переходом tj, определяется величиной I(pi, tj). Аналогично кратность дуги, соединяющей переход tj с выходной позицией pi, определяется величиной O(pi, tj). Кратность рассматривается как возможность дублирования дуги, соединяющей вершины pi и tj (или tj и pi ), I(pi, tj) (или O(pi, tj)) раз. Если I(pi, tj) > 0, то позицию pi называют входной к переходу tj, а переход tj выходным к позиции pi. Множество входных позиций (pre(tj)) к переходу tj определяется как pre(tj)={ pI(pi, tj) > 0}, а множество выходных переходов (post(pi )) к позиции pi как post(pi)={ t  I(pi, tj) > 0} . Дизайн И. Гайдель 2007 0 ) Теория сетей Петри и моделирование систем Основны е определения и обозначения Аналогично, если O(pi, tj) > 0 , то переход tj называют входным к позиции pi, а позицию pi - выходной к переходу tj . Множество входных переходов к позиции pi определяется как pre(pi)={t | O(pi, tj) > 0}, а множество выходных позиций к переходу tj - как post(tj)={p | O(pi, tj) > 0}. Входная позиция pi к переходу tj называется головной, если pre(pi) =  . Аналогично выходная позиция pi к переходу tj называется хвостовой, если post(pi) =  . Дизайн И. Гайдель 2007 Теория сетей Петри и моделирование систем = (0,0). Основны е определения и обозначения Введем понятие элементарной сети. Определение 2. Элементарной сетью t называется СП N = (P, T, I, O, µ0 ), для которой T={t}; P={p',p''}; pre(t)={p'}, post(t) = {p''}; µ0 = (0,0). Дизайн И. Гайдель 2007 Теория сетей Петри и моделирование систем = (0,0). Основны е определения и обозначения При функционировании СП переходит от одной разметки к другой. Каждая разметка представляет собой функцию  : P{0,1,2...}. Переход может сработать при разметке , если он активен. Переход tj является активным, если pi  pre(tj): (pi ) >= I( pi, tj) . В результате срабатывания перехода tj разметка меняется в соответствии со следующим правилом: pi  (pre( tj)  post(tj)) : ‘(pi ) = (pi ) - I(pi, tj) + O( pi, tj) . В этом случае говорят, что разметка ‘ достижима от разметки  в результате срабатывания перехода tj, а разметка  предшествует ‘. СП останавливается, если при некоторой разметке не может сработать ни один из ее переходов. Такая разметка называется тупиковой. Таким образом, СП моделируют некоторую структуру и динамику ее функционирования. Дизайн И. Гайдель 2007 Теория сетей Петри и моделирование систем = (0,0). Основны е определения и обозначения Дизайн И. Гайдель 2007 Теория сетей Петри и моделирование систем = (0,0). Основны е определения и обозначения Дизайн И. Гайдель 2007 Теория сетей Петри и моделирование систем = (0,0). Основны е определения и обозначения Дизайн И. Гайдель 2007 Теория сетей Петри и моделирование систем = (0,0). Пример сети Петри P = {p1, p2, p3, p4} ; T = {t1, t2, t3, t4} Дизайн И. Гайдель 2007 Теория сетей Петри и моделирование систем = (0,0). Модификации сетей Петри (иерархические сети) Иерархические сети (ИСП) являются обобщением СП и служат для моделирования иерархических систем, которые наряду с неделимыми, атомарными компонентами содержат составные компоненты, представляющие собой отдельные подсистемы. Для определения ИСП множество переходов разбивается на подмножества простых и иерархических переходов (ИПР). Простым переходам соответствуют элементарные сети. ИПР представляет собой некоторый фрагмент СП. Сравнительный анализ выразительных свойств ИСП и СП показывает, что введение иерархии в сетевые модели существенно улучшает моделирующие способности СП-моделей. Дизайн И. Гайдель 2007 Теория сетей Петри и моделирование систем = (0,0). Модификации сетей Петри (ингибиторны е сети) В рассмотренных СП недостатком является то, что нельзя отметить срабатыванием перехода факт изменения разметки с ненулевого значения на нулевое. Таким образом из двух альтернатив (p)  0 и (p) = 0, содержащихся в операторе условного вычитания единицы, в СП можно представить только одну, первую, но нельзя отразить проверку на ноль, так как сеть не может реагировать непосредственно на отсутствие метки в позиции. В результате было показано, что СП не могут моделировать машины Минского и Тьюринга. Флинн и Аджервала модифицировали СП, введя в них специальные ингибиторные дуги, осуществляющие проверку на нулевую разметку, и показали, что получаемое обобщение дает класс сетей равномощных машине Тьюринга. Дизайн И. Гайдель 2007 Теория сетей Петри и моделирование систем = (0,0). Модификации сетей Петри (ингибиторны е сети) Ингибиторная сеть представляет собой СП, дополненную специальной функцией инцидентности FI:PT{0,1}, которая вводит ингибиторные дуги для тех пар (p,t), для которых FI(p,t) = 1. Ингибиторные дуги связывают только позиции с переходами и на рисунках изображаются заканчивающимися не стрелками, а маленькими кружочками. Правило срабатывания перехода в ингибиторной сети модифицируется следующим образом:  pi  pre(tj): ( pi )  I( pi, tj) & (pi )FI(p,t) = 0 . Дизайн И. Гайдель 2007 Теория сетей Петри и моделирование систем = (0,0). Модификации сетей Петри (приоритетны е сети) При описании функционирования СП отмечалась недетерминируемость следующего рода: если может сработать несколько переходов, то срабатывает любой из них. В реальных дискретных системах имеют место ситуации, когда из двух готовых сработать устройств требуется запустить вначале одно, а затем другое. Иными словами, одно из устройств имеет приоритет на запуск перед другим. Эти ситуации не моделируются в СП. Модифицируем определение СП следующим образом. Введем множество PR, элементы которого частично упорядочены отношением "" (меньше или равно). С каждым переходом t СП свяжем его приоритет pr(t), принадлежащий множеству PR. Дизайн И. Гайдель 2007 Теория сетей Петри и моделирование систем = (0,0). Модификации сетей Петри (приоритетны е сети) Правило срабатывания перехода дополним следующим условием: переход t может сработать при разметке  , если для любого другого перехода t' этой сети, который также может сработать при разметке , pr(t')pr(t). Другими словами, если несколько переходов готовы сработать, то срабатывает такой переход, приоритет которого не меньше приоритетов остальных готовых к срабатыванию переходов. Такую модификацию СП называют приоритетными сетями. Показано, что класс приоритетных СП является строго мощнее СП и равномощен классам машин Тьюринга и Минского. Дизайн И. Гайдель 2007 Теория сетей Петри и моделирование систем = (0,0). Модификации сетей Петри (временны е сети) При построении моделей очень важным является учет временных характеристик моделируемых событий. Предлагаемое расширение СП позволяет отразить в модели временные параметры системы. При этом фактор времени учитывается путем введения задержки между моментом изъятия меток из входных позиций сработавшего перехода и моментом помещения меток в выходные позиции данного перехода. Очевидно, что определенные таким образом временные СП могут использоваться в тех случаях, когда возможно предположение о постоянном времени протекания каждого процесса в модели. Дизайн И. Гайдель 2007 Теория сетей Петри и моделирование систем = (0,0). Модификации сетей Петри Наряду с описанными расширениями СП в современной литературе встречается ряд других расширений СП, которые учитывают специфику той предметной области, в которой используется аппарат СП. Среди данных расширений можно выделить стохастические СП, раскрашенные СП, Е-сети, СП для описания процедур принятия решений (нейронные, нечеткие, числовые, абстрактные) и другие. Дизайн И. Гайдель 2007 Спасибо за внимание!