Некоторые обобщения сетей Петри

↑

▷ Содержание

⇐ ПредыдущаяСтр 8 из 11Следующая ⇒

Рассмотренное в разделах 2.1.1 – 2.1.3 базовое определение сети Петри позволяет моделировать широкий класс дискретных систем. Однако в ряде случаев этих возможностей оказывается недостаточно, поэтому вводят обобщения этих сетей, которые обладают расширенными возможностями моделирования. Упомянем некоторые из них.

Ингибиторные сети (ИСП, IPN) – это сети Петри, для которых функция инцидентности имеет вид , т.е. она дополнена специальной функцией инцидентности , которая вводит ингибиторные дуги для тех пар , для которых . Ингибиторные дуги связывают только позиции с переходами, эти дуги на рисунках заканчиваются не стрелками, а кружочками (рисунок 2.3). Кратность этих дуг всегда равна 1.

р исунок 2.3 Фрагмент СП с ингибиторной дугой

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

,                                                          (2.9)

т.е. по сравнению с условием (2.6) введено дополнительное условие: позиция , соединенная с переходом  ингибиторной дугой, не должна содержать фишек (должна иметь нулевую маркировку). Так, переход t на рисунке 2.3 может срабатывать только при  и .

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

а)                                                 б)

Рисунок 2.4 Сеть Петри с заданными приоритетами (а), эквивалентная цепь Маркова при вероятностном срабатывании переходов (б)

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

Пусть на рисунке 2.4 а) вероятность срабатывания перехода  равна p, а вероятность срабатывания  равна . Тогда обозначив маркировки , , , получим цепь Маркова (рисунок 2.4 б).

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

В отличие от обыкновенных сетей Петри, в иерархических сетях имеются два типа переходов: простые и составные. Простые переходы ничем не отличаются от рассмотренных ранее, а составные переходы содержат внутри себя сеть Петри более низкого уровня. Формально они состоят из входного («головного») и выходного («хвостового») переходов, между ними находится некоторая сеть Петри, которая, в свою очередь, также может быть иерархической.

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

Рисунок 2.5 Иерархическая сеть Петри

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

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

Ниже приведено дерево маркировок сетей  и  при указанных на рис. 2.5 начальных маркировках (рисунок 2.6).

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

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

Рисунок 2.6 Схема работы иерархической сети Петри

2.1.6 Инварианты сетей Петри

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

Различают инварианты позиций и инварианты переходов.

Для того, чтобы пояснить смысл этих терминов, введем в рассмотрение -матрицу

,

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

1. Инварианты позиций. Припишем каждой позиции  некоторый вес , который может принимать целочисленные значения – положительные, отрицательные или нулевые. Эти веса образуют -вектор-строку

.

Рассмотрим -вектор-строку  и определим условия, при которых этот вектор является нулевым, т.е.

                                                                         (2.10)

где  - -вектор-строка, состоящая из нулей,  - ненулевой -вектор.

Представим матрицу  в виде -столбца:

,

где -вектор-строка. Тогда условие (4.10) может быть представлено в виде

.

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

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

; , .                         (2.11)

Таким образом, вектор  имеет вид

и в силу (2.11) обеспечивается выполнение условия (2.10).

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

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

Построенный описанным образом вектор  называется инвариантом позиций сети Петри.

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

.

Рассмотрим -вектор-столбец и определим условия, при которых этот вектор является нулевым, т.е.

,                         (2.12)

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

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

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

Вектор , удовлетворяющий условию (2.12), называется инвариантом переходов.

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

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

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

, .

Такая сеть Петри, как было сказано выше, называется консервативной.

Пример. Рассмотрим сеть Петри, изображенную на рисунке 2.1 и составим для нее матрицу :

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

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

.

Это означает, что при последовательном срабатывании переходов ,  (в любом порядке) маркировка сети повторяется. Это также видно на рисунке 2.2. Но это не единственный инвариант по переходам. Цепочка срабатываний переходов (t ₁, t ₁, t ₂ , t ₄)  в любом порядке приводит к той же маркировке.

Лабораторная работа № 4 Моделирование систем с помощью
обыкновенных сетей Петри

Цель работы:

- освоить основные формализмы обыкновенных сетей Петри (PN).

- научиться составлять формальное описание PN.

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

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

Содержание работы

1) Изучить теоретический материал по учебнику [1], [2] или лекциям. Получить свой вариант задания

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

3) Для заданного варианта задания:

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

2. Для начальной маркировки PN, указанной в таблице, составить дерево разметок на глубину до 5 шагов или до общего числа маркировок, равного 100. При обнаружении повторяющихся маркировок они помечаются значками Mp_i, где i - номер обнаруженной повторяющейся маркировки, а построение дерева продолжается только из одной из них. Циклические маркировки, т.е. повторяющиеся на одном пути в дереве, обозначаются Mc_i. Тупиковые маркировки обозначаются Mt_i.

3. Выписать все полученные слова свободного языка PN, начиная с пустого слова. Аналогично п.2 указать повторения, циклы и тупики.

4. Оценить свойства PN: ограниченность, консервативность, безопасность, живость.

Оформление работы

Оформленный отчет по лабораторной работе должен содержать:

- титульный лист с указанием фамилий исполнителей, группы и номера варианта;

- исходную схему с начальной маркировкой;

- матрицы инцидентности;

- дерево маркировок;

- словарь свободного языка PN;

- анализ свойств рассматриваемой PN;

- листинг программы.

Таблица исходных данных

Исходные схемы PN

А

Б

В

Г

Д

Контрольные вопросы

1. Какие элементы содержит сеть Петри?

2. Сформулируйте правило срабатывания сети Петри.

3. По какому правилу меняются маркировки сети при срабатывании одного перехода?

4. Как построить дерево маркировок сети до определенной глубины?

5. Дайте определение ограниченности позиции в сети.

6. Какие основные свойства переходов вы знаете?

7. Что такое множество достижимости сети Петри?

Лабораторная работа № 5 Моделирование систем с помощью
ингибиторных сетей Петри

Цель работы:

- освоить основные формализмы ингибиторных сетей Петри (IPN).

- научиться составлять формальное описание IPN.

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

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

Содержание работы

1) Изучить описание ингибиторных связей и особенности функционирования IPN по учебникам [1], [2] или по лекциям.

2) Модернизировать разработанную в лабораторной работе №4 программу, введя в нее описание и механизм работы IPN.

3) Провести исследование заданного варианта IPN аналогично исследованию в лабораторной работе №4 (пункты 1-4). Сравнить дерево маркировок и свободный язык IPN с аналогичными характеристиками обыкновенной PN.

Исходные данные

В соответствии с указанным номером варианта, в схему, использованную в лабораторной работе №4, внести следующие изменения:

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

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

Оформление работы

Оформленный отчет по лабораторной работе должен содержать:

- титульный лист с указанием фамилий исполнителей, группы и номера варианта;

- исходную схему с начальной маркировкой;

- матрицы инцидентности;

- дерево маркировок;

- словарь свободного языка PN;

- анализ свойств рассматриваемой PN;

- листинг программы.

Таблица исходных данных

Контрольные вопросы

8. Какие элементы содержит сеть Петри?

9. Сформулируйте правило срабатывания сети Петри.

10. По какому правилу меняются маркировки сети при срабатывании одного перехода?

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

12. Дайте определение ограниченности позиции в сети.

13. Какие основные свойства переходов вы знаете?

14. Что такое множество достижимости сети Петри?

Познавательные статьи:



Техника прыжка в длину с разбега

Тактические действия в защите

История Олимпийских игр

История развития права интеллектуальной собственности