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

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

Ингибиторные сети (ИСП, IPN) – это сети Петри, для которых функция инцидентности имеет вид F = F^P U F^t U F^I, т.е. она дополнена специальной функцией инцидентности FI: P x T -> {0, 1}, которая вводит ингибиторные дуги для тех пар (p_i, t_j), для которых f_i^I_j = 1. Ингибиторные дуги на рисунках заканчиваются не стрелками, а кружочками (рис. 2.3). Кратность этих дуг всегда равна 1.

p₁

t

p₃

p₂

Рис. 2.3

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

(μ _i ≥ f _i ^p_j) _^ (μ k * f_k^I_j = 0),

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

Сети с приоритетами. При определении сети Петри отмечаласьнедетерминированность ее работы: если имеется возможность срабатывания нескольких переходов, то срабатывает любой из них. При моделировании реальных систем могут сложиться ситуации, когда последовательность срабатываний необходимо регламентировать. Это можно сделать, введя множество приоритетов PR: Т —> { 0, 1, … }и приписав каждому из переходов t_j соответствующее целочисленное значение приоритета pr_j. Тогда правило срабатывания переходов модифицируется: если на некотором такте работы сети PN имеется возможность для срабатывания нескольких переходов, то срабатывает тот из них, который имеет наивысший приоритет. Так, из двух готовых к срабатыванию переходов t₁ и t₂ . на рисунке 2.4 а первым должен сработать переход t₂, имеющий приоритет pr₂ =1, поскольку приоритет перехода t₁ pr₁ = 2, т.е. ниже.

Рис. 2.4

Сети со случайными срабатываниями переходов. В описанной выше ситуации, когда имеется возможность срабатывания нескольких переходов t_i, t_j, …t_s, их приоритет можно задавать вероятностями срабатывания каждого их переходов p_i, p_j, …p_s, причем p_i+p_j+…+ p_s=1. Тогда исходная маркировка М_о приведет на следующих шагах работы сети к набору маркировок М_i, М_j, …М_s, каждая из которых будет помечена соответствующей вероятностью. Отождествив маркировки с состоянием сети и положив, что вероятности не зависят от работы сети в предыдущие такты, мы получим цепь Маркова, описывающию вероятностное поведение системы (см. Главу 3).

Пусть на рисунке 2.4 а вероятность срабатывания перехода t₁ равна p, а вероятность срабатывания t₂ равна q = 1 – p. Тогда, обозначив маркировки М₀ = [ 1100 ], М₁ = [ 0010 ], М₂ = [ 0001 ], получим цепь Маркова (рис. 2.4 б).

Рис. 2.5

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

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

Пример иерархической сети N, в которой имеется составной переход t₂, содержащий внутри себя сеть N ", показан на рисунке 2.5. Составной переход t₂ имеет «голову» t'₂ и «хвост» t" ₂, между которыми заключена сеть N', состоящая из позиций p₂₁ – p₂₅ и переходов t₂₁ – t₂₃.

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

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

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

Мы видим, что на шаге θ = 2 происходит составного перехода t₂ и сети N' в следующем порядке: срабатывание t'₂ -> запуск N' -> окончание работы N' ивосстановление ее начальной маркировки -> срабатывание t₂ и продолжение работы сети N.

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

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

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

Формальное определение и подробное описание работы раскрашенных сетей Петри приведено в п. 2.2

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

Упомянем еще некоторые расширения сетей Петри: синхронные самомодифицируемые (с изменяющейся кратностью дуг, когда F^p и F^t зависят от τ), и другие, описанные в литературе [8], [9], [17] - [25].

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

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

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

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

V = || f_j ^t_i – f_i ^p_j || = (F^t)^T – F^P,

каждый элемент которой v_ij = f_j^t_i – f_i ^p_j показывает разность между числом поступивших фишек – f _j^t_i и числом изъятых f _ij^p, т.е. изменение маркировки позиции р_i Є Р при срабатывании перехода t _j Є Т. В силу того, что f _j^t_i -. и f _ij^p - целые числа, величины v_ij также целые. В зависимости от знака v_ij присрабатыванииперехода t _j в позиции p_i число фишек либо увеличивается (v_ij > 0), либо уменьшается (v_ij < 0), либо остается неизменным (v_ij = 0).

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

Рассмотрим m - вектор-строку Y = U · V и определим условия, при которых этот вектор является нулевым, т.е.

Y= Û · V = Ø _m, (2.10)

где Ø _m - m -вектор-строка, состоящая из нулей; Û - ненулевой n - вектор.

Представим матрицу V в виде п – столбца

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

Отсюда следует, что условие (2.10) при Û ≠ 0 может выполняться только в том случае, если среди строк Vi матрицы V найдутся линейные независимые строки.

Пусть для простоты имеются две такие строки с номерами k и l – Vk и Vi, которые соответствуют в матрице V позициям рk и р, и пусть соответствующие веса не равны нулю: uk ≠ 0, ul ≠ 0. Веса остальных позиций положим равными нулю: ui = 0 при i ≠ k, i ≠ l. В силу линейной зависимости строк k и l веса u и u можно подобрать таким образом, что

û kVk+û lVl=Ø m; û lvlj+û lvlj=0, j=1, ….., m. (2.11)

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

Û = [ 0, ….., 0, û k, 0, …., 0, û l, 0, ….0]

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

Подсчитываем теперь приращение числа фишек в позициях рk и р l при срабатывании перехода

t Є T. Пусть до срабатывания перехода tj маркировки в позициях рk и рl были соответственно μ r и μ l. После срабатывания t маркировки с учетом введенных весов û k и û l стали равными μ ’ k = μ k + û k v kj, μ ’ l =μ l +û l v lj, а их сумма μ ’ k + μ ’ l = μ k + û k v kj + μ l + û l v lj = μ k + μ l в силу (2 11). Таким образом, сумма μ _k + μ _l при учете введенных весов позиций û _k, û _l остается постоянной при срабатывании любого перехода и равна этой сумме при начальной маркировке М ₀.
Построенный описаннымобразом вектор Û называется инвариантом позиций сети Петри.

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

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

_m

Z = V · W = [ V¹, V², …, V^m ]· Ŵ = Σ V^jŵ _j = Ø _n, (2.12)

^j=1

где Ø _n - п -вектор, состоящий из пулей; Ŵ - ненулевой т- вектор; V ⁱ - i-й п -столбец матрицы V. умножив веса и, и щ на постоянное число k = const, мы Аналогично сказанному выше можно убедиться в том, что условие (2.12) выполняется только в том случае, когда среди столбцов матрицы V найдутся линейнозависимые. Пусть имеются два линейно зависимых столбца с номерами р и q, которые соответствуют переходам t_p и t_q, и пусть соответствующие веса не равны нулю, w_p≠ 0, w_q≠ 0. Остальные веса положим нулевыми: w_j = 0 при j ≠ р, j ≠ q. В силу линейной зависимости векторов V^р и V^q можно подобрать вeca w_p и w_q таким образом, чтобы выполнялось условие (2.12).

Проанализируем теперь, как будет изменяться сети при последовательном срабатывании переходов t_p и t’_q. Пусть маркировка некоторой позиции р_i до срабатывания переходов была μ _.

После срабатывания t_p она (с учетом веса ŵ _р) стала μ _{i =} μ _i + ŵ _pv_ip, а после срабатывания t_q (с учетом веса ŵ _q) μ _i= μ _i + ŵ _pv_ip +ŵ _qv_iq = μ _i. Таким образом, после последнего срабатывания t_p и t_q получается исходная маркировка всех позиций, i= 1, ……, n.

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

Приведенные рассуждения легко обобщаются и на случай, когда число линейно зависимых строк (и столбцов) в матрице V больше двух. Напомним, что число линейно независимых строк матрицы V равно числу ее линейно независимых столбцов и равно рангу матрицы V, который обозначается буквой r_v. Величина d_v = min (n, m) - r_v, называется дефектом матрицы V. Таким образом, для того чтобы можно было построить инварианты позиций и переходов сети Петри Û, Ŵ, удовлетворяющие условиям (2.10), (2.12), необходимо чтобы дефект матрицы V был больше нуля: d_v > 0.

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

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

_n

Σ μ _i (θ) = const, θ = 0, 1, 2, …..

ⁱ⁼¹

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

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

Легко видеть, что в этой матрице первая и третья строки линейно зависимы, причем достаточно взять веса û ₁= 1, û ₃=1, û ₂=0. При этом получим вектор-инвариант по позициям Û = [1, 0, 1], следовательно, сумма фишек в позициях р₁ и р₃ постоянна при срабатывании любого перехода: μ ₁ + μ ₃= const, в чем легко убедиться, проанализировав дерево маркировок на рисунке 2.2.

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

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

Инварианты для более сложной сети Петри рассматриваются в п. 3.7.