Сеть Петри

редактировать

A Сеть Петри, также известная как сеть размещения / перехода (PT), является одной из несколько математических языков моделирования для описания распределенных систем. Это класс динамической системы дискретных событий. Сеть Петри - это ориентированный двудольный граф, который имеет два типа элементов, места и переходы, изображенные как белые кружки и прямоугольники соответственно. Место может содержать любое количество жетонов, обозначенных черными кружками. Переход разрешен, если все точки, подключенные к нему в качестве входов, содержат хотя бы один токен. Некоторые источники утверждают, что сети Петри были изобретены в августе 1939 года Карлом Адамом Петри - в возрасте 13 лет - для этой цели. описания химических процессов.

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

(a) Пример траектории сети Петри

Содержание

1 Основы сети Петри
2 Формальное определение и основная терминология
- 2.1 Синтаксис
- 2.2 Семантика выполнения
3 Варианты определения
4 Формулировка в терминах векторов и матриц
5 Математические свойства сетей Петри
- 5.1 Достижимость
- 5.2 Жизнеспособность
- 5.3 Ограниченность
6 Дискретные, непрерывные и гибридные сети Петри
7 Расширения
8 Ограничения
9 Сети рабочих процессов
10 Другие модели параллелизма
11 Области приложений
12 См. Также
13 Ссылки
14 Дополнительная литература
15 Внешние ссылки

Основы сети Петри

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

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

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

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

Формальное определение и основная терминология

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

Определение 1. A сеть представляет собой тройку $N = (P, T, F) {\ displaystyle N = (P, T, F)}$ $N = (P, T, F)$ где:

$P {\ displaystyle P}$ $P$ и $T {\ displaystyle T}$ $T$ представляют собой непересекающиеся конечные наборы позиций и переходов, соответственно.
$F ⊆ (P × T) ∪ (T × P) {\ displaystyle F \ substeq (P \ times T) \ cup (T \ times P)}$ ${\ displaystyle F \ substeq (P \ times T) \ cup (T \ times P)}$ - это набор дуг (или отношений потоков).

Определение 2. Учитывая a net N = (P, T, F), конфигурация - это набор C, так что C ⊆ P.

Сеть Петри с разрешенным переходом.

Сеть Петри, которая следует после срабатывания перехода (Начальная сеть Петри на рисунке выше).

Определение 3. Элементарная сеть - это сеть form EN = (N, C), где:

N = (P, T, F) - сеть.
C таково, что C ⊆ P - конфигурация.

Определение 4. Сеть Петри - это сеть вида PN = (N, M, W), которая расширяет элементарную сеть так, что:

N = (P, T, F) является сетью.
M: P → Z - это место мультимножество, где Z - счетное множество. M расширяет концепцию конфигурации и обычно описывается со ссылкой на диаграммы сети Петри как маркировку.
W: F → Z - дуга мультимножество, так что количество (или вес) для каждой дуги является мерой кратности дуги.

Если сеть Петри эквивалентна элементарной сети, то Z может быть счетным множеством {0,1} и теми элементами в P, которые отображают к 1 под M образуют конфигурацию. Точно так же, если сеть Петри не является элементарной сетью, то мультимножество M можно интерпретировать как представляющее не одноэлементный набор конфигураций. В этом отношении M расширяет понятие конфигурации элементарных сетей на сети Петри.

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

На верхнем рисунке (см. Справа) позиция p 1 является входной точкой перехода t; тогда как место p 2 является выходным местом для того же перехода. Пусть PN 0 (верхний рисунок) будет сетью Петри с настроенной маркировкой M 0, а PN 1 (нижний рисунок) будет сетью Петри с маркировкой настроен M 1. Конфигурация PN 0 обеспечивает переход t через свойство, что все входные позиции имеют достаточное количество маркеров (показанных на фигурах точками), «равное или большее», чем кратности на их соответствующих дугах к t. Один и только один раз переход активируется, переход срабатывает. В этом примере запуск перехода t генерирует карту, для которой настроена маркировка M 1 в изображении M 0, и в результате получается сеть Петри PN 1, как показано на нижнем рисунке. На схеме правило активации перехода может быть охарактеризовано путем вычитания количества токенов из его входных позиций, равного кратности соответствующих входных дуг, и накопления нового количества токенов в выходных местах, равного кратности соответствующих входных дуг. выходные дуги.

Замечание 1. Точное значение «равно или больше» будет зависеть от точных алгебраических свойств сложения, применяемого к Z в правиле увольнения, где тонкие изменения алгебраических свойств могут привести к другим классам Сети Петри; например, алгебраические сети Петри.

Следующее формальное определение частично основано на (Peterson 1981). Существует множество альтернативных определений.

Синтаксис

A Граф сети Петри (который некоторые называют сетью Петри, но см. Ниже) представляет собой кортеж из 3- $(S, T, W) {\ displaystyle (S, T, W)}$ $(S, T, W)$ , где

S - это конечный набор мест
T - конечный набор переходов
S и T не пересекаются, то есть никакой объект не может быть одновременно местом и переходом
$W: (S × T) ∪ (T × S) → N {\ displaystyle W: (S \ times T) \ cup (T \ times S) \ to \ mathbb {N}}$ $W: (S \ times T) \ чашка (T \ times S) \ to \ mathbb {N}$ - это мультимножество из дуг, то есть он назначается каждой дуге неотрицательная целая кратность (или вес) дуги; обратите внимание, что никакая дуга не может соединять два места или два перехода.

Отношение потока - это набор дуг: $F = {(x, y) ∣ W (x, y)>0} {\ displaystyle F = \ {(x, y) \ mid W (x, y)>0 \}}$ $F = \{ (x,y) \mid W(x,y)>0 \}$ . Во многих учебниках дуги могут иметь только кратность 1. Эти тексты часто определяют сети Петри с использованием F вместо W. При использовании этого соглашения a Сетевой граф Петри - это двудольный мультиграф $(S ∪ T, F) {\ displaystyle (S \ cup T, F)}$ $(S \ cup T, F)$ с узловыми разбиениями S и T.

Предварительная установка перехода t - это набор его входных позиций: $∙ t = {s ∈ S ∣ W (s, t)>0} {\ displaystyle {} ^ {\ bullet} t = \ {s \ in S \ mid W (s, t)>0 \}}$ ${}^{\bullet}t = \{ s \in S \mid W(s,t)>0 \}$ ; его пост-набор - это набор его выходных мест: $t ∙ = {s ∈ S ∣ W (t, s)>0} {\ displaystyle t ^ {\ bullet} = \ {s \ in S \ mid W ( t, s)>0 \}}$ $t^{\bullet} = \{ s \in S \mid W(t,s)>0 \}$ . Определения pre- и postset мест аналогичны.

Маркировка сети Петри (графа) - это мультимножество ее мест, т. е. отображение $M: S → N {\ displaystyle M: S \ to \ mathbb {N}}$ $M: S \ to \ mathbb {N}$ . Мы говорим, что маркировка присваивает каждому месту количество маркеров.

A Сеть Петри (называемая маркированной Сеть Петри некоторыми, см. Выше) представляет собой набор из 4 элементов $(S, T, W, M 0) {\ displaystyle (S, T, W, M_ {0})}$ $(S, T, W, M_0)$ , где

$(S, T, W) {\ displaystyle (S, T, W)}$ $(S, T, W)$ - граф сети Петри;
$M 0 {\ displaystyle M_ {0}}$ $M_ {0}$ - начальная маркировка, маркировка графа сети Петри.

Семантика выполнения

Словами:

запуск перехода t в маркировке M потребляет $W (s, t){\ displaystyle W (s, t)}$ $W (s, t)$ токены из каждого из входных мест s, и производит $W (t, s) {\ displaystyle W (t, s)}$ $W (t, s)$ токенов в каждом из его выходных мест s
переход разрешен (он может сработать) в M, если во входных местах достаточно токенов для возможного потребления, то есть тогда и только тогда, когда $∀ s: M (s) ≥ W (s, t) {\ displaystyle \ forall s: M (s) \ geq W (s, t)}$ $\ forall s : M (s) \ geq W (s, t)$ .

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

Мы говорим, что отметка M 'достижима из отметки M за один шаг, если $M ⟶ GM ′ {\ displaystyle M {\ underset {G} {\ longrightarrow}} M'}$ $M{\underset {G}{\longrightarrow }}M'$ ; мы говорим, что он достижим из M, если $M ⟶ G ∗ M ′ {\ displaystyle M {\ overset {*} {\ underset {G} {\ longrightarrow}}} M '}$ $M{\overset {*}{\underset {G}{\longrightarrow }}}M'$ , где $⟶ G ∗ {\ displaystyle {\ overset {*} {\ underset {G} {\ longrightarrow}}}}$ ${\ displaystyle {\ overset {*} {\ underset {G} {\ longrightarrow}}}}$ - это рефлексивное переходное замыкание из $⟶ G {\ displaystyle {\ underset {G} {\ longrightarrow}}}$ ${\ displaystyle {\ underset {G} {\ longrightarrow}}}$ ; то есть, если до него можно добраться за 0 или более шагов.

Для (отмеченной) сети Петри $N = (S, T, W, M 0) {\ displaystyle N = (S, T, W, M_ {0})}$ ${\ displaystyle N = (S, T, W, M_ {0})}$ , нас интересуют запуски, которые могут выполняться, начиная с начальной маркировки $M 0 {\ displaystyle M_ {0}}$ $M_ {0}$ . Его набор меток достижимости - это множество $R (N) = D {M ′ | M 0 → (S, T, W) ∗ M ′} {\ Displaystyle R (N) \ {\ stackrel {D} {=}} \ \ left \ {M '{\ Bigg |} M_ {0} {\ xrightarrow [{(S, T, W)}] {*}} M '\ right \}}$ $R(N)\ {\stackrel {D}{=}}\ \left\{M'{\Bigg |}M_{0}{\xrightarrow[{(S,T,W)}]{*}}M'\right\}$

График достижимости N - это отношение перехода $⟶ G {\ displaystyle {\ underset {G} { \ longrightarrow}}}$ ${\ displaystyle {\ underset {G} {\ longrightarrow}}}$ ограничено доступной маркировкой $R (N) {\ displaystyle R (N)}$ $R (N)$ . Это пространство состояний сети.

Последовательность срабатывания сети Петри с графом G и начальной маркировкой $M 0 {\ displaystyle M_ {0}}$ $M_ {0}$ - это последовательность переходов $σ → = ⟨ t 1 ⋯ tn⟩ {\ displaystyle {\ vec {\ sigma}} = \ langle t_ {1} \ cdots t_ {n} \ rangle}$ ${\ displaystyle {\ vec {\ sigma}} = \ langle t_ {1} \ cdots t_ {n} \ rangle}$ такой, что $M 0 ⟶ G, t 1 M 1 ∧ ⋯ ∧ M n - 1 ⟶ G, tn M n {\ displaystyle M_ {0} {\ underset {G, t_ {1}} {\ longrightarrow}} M_ {1} \ wedge \ cdots \ wedge M_ { n-1} {\ underset {G, t_ {n}} {\ longrightarrow}} M_ {n}}$ ${\ displaystyle M_ {0} {\ underset {G, t_ {1}} {\ longrightarrow}} M_ {1} \ wedge \ cdots \ wedge M_ {n-1} {\ underset { G, t_ {n}} {\ longrightarrow}} M_ {n}}$ . Набор последовательностей срабатывания обозначается как $L (N) {\ displaystyle L (N)}$ $L (N)$ .

Варианты определения

Как уже отмечалось, обычным вариантом является запрет на кратность дуги и замена мешок дуг W с простым набором, называемым отношением потока, $F ⊆ (S × T) ∪ (T × S) {\ displaystyle F \ substeq (S \ times T) \ чашка (T \ times S)}$ $F \ substeq (S \ times T) \ cup (T \ times S)$ . Это не ограничивает выразительной силы, поскольку оба могут представлять друг друга.

Другой распространенный вариант, например in, Desel and Juhás (2001), позволяет определять мощности на местах. Это обсуждается ниже в разделе расширений.

Формулировка в терминах векторов и матриц

Маркировка сети Петри $(S, T, W, M 0) {\ displaystyle (S, T, W, M_ { 0})}$ $(S, T, W, M_0)$ можно рассматривать как векторы неотрицательных целых чисел длины $| S | {\ displaystyle | S |}$ $| S |$ .

Его отношение перехода можно описать как пару $| S | {\ displaystyle | S |}$ $| S |$ по $| Т | {\ displaystyle | T |}$ $| T |$ матрицы :

$W - {\ displaystyle W ^ {-}}$ $W ^ -$ , определенные как $∀ s, t: W - [s, t] = W (s, t) {\ displaystyle \ forall s, t: W ^ {-} [s, t] = W (s, t)}$ $\ forall s, t: W ^ - [s, t] = W (s, t)$
$W + {\ displaystyle W ^ {+}}$ $W ^ +$ , определенный как $∀ s, t: W + [s, t] = W (t, s). {\ displaystyle \ forall s, t: W ^ {+} [s, t] = W (t, s).}$ $\ forall s, t: W ^ + [s, t] = W (t, s).$

Тогда их разница

$WT = - W - + W + {\ displaystyle W ^ {T} = - W ^ {-} + W ^ {+}}$ ${\ displaystyle W ^ {T} = - W ^ {-} + W ^ {+}}$

можно использовать для описания достижимых отметок в терминах умножения матриц следующим образом. Для любой последовательности переходов w напишите $o (w) {\ displaystyle o (w)}$ $о (ш)$ для вектора, который отображает каждый переход на его количество вхождений в w. Тогда у нас есть

$R (N) = {M ∣ ∃ w: w - последовательность включения N и M = M 0 + WT ⋅ o (w)} {\ displaystyle R (N) = \ {M \ mid \ exists w: \ w {\ text {- это последовательность активации}} N \ {\ text {и}} \ M = M_ {0} + W ^ {T} \ cdot o (w) \}}$ ${\ displaystyle R (N) = \ {M \ mid \ exists w: \ w {\ text {- последовательность срабатывания}} N \ {\ text {и}} \ M = M_ {0} + W ^ {T} \ cdot o (w) \}}$ .

Обратите внимание, что должно требоваться, чтобы w была последовательностью срабатывания; разрешение произвольных последовательностей переходов обычно дает больший набор.

(б) Пример сети Петри

W - = [∗ t 1 t 2 p 1 1 0 p 2 0 1 p 3 0 1 p 4 0 0], W + = [∗ t 1 t 2 p 1 0 1 п 2 1 0 п 3 1 0 п 4 0 1], WT = [∗ t 1 t 2 p 1 - 1 1 p 2 1 - 1 p 3 1 - 1 p 4 0 1] {\ displaystyle W ^ { -} = {\ begin {bmatrix} * t1 t2 \\ p1 1 0 \\ p2 0 1 \\ p3 0 1 \\ p4 0 0 \ end {bmatrix}}, \ W ^ {+} = {\ begin {bmatrix} * t1 t2 \\ p1 0 1 \\ p2 1 0 \\ p3 1 0 \\ p4 0 1 \ end {bmatrix}}, \ W ^ {T} = {\ begin {bmatrix} * t1 t2 \\ p1 -1 1 \\ p2 1 -1 \\ p3 1 -1 \\ p4 0 1 \ end { bmatrix}}}

{\ displaystyle W ^ {-} = {\ begin {bmatrix} * t1 t2 \\ p1 1 0 \\ p2 0 1 \\ p3 0 1 \\ p4 0 0 \ end {bmatrix}}, \ W ^ {+} = {\ begin {bmatrix} * t1 t2 \\ p1 0 1 \\ p2 1 0 \\ p3 \ p4 0 1 \ end {bmatrix}}, \ W ^ {T} = {\ begin {bmatrix} * t1 t2 \\ p1 -1 1 \\ p2 1 -1 \\ p3 1 -1 \\ p4 0 1 \ end {bmatrix}}}

M 0 = [1 0 2 1] {\ displaystyle M_ {0} = {\ begin {bmatrix} 1 0 2 1 \ end {bmatrix}}}

{\ displaystyle M_ {0} = {\ begin {bmatrix} 1 0 2 1 \ end { bmatrix}}}

Математические свойства сетей Петри

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

Обзор таких проблем принятия решений с результатами разрешимости и сложности для сетей Петри и некоторых подклассов можно найти в Esparza and Nielsen (1995).

Достижимость

проблема достижимости для сетей Петри состоит в том, чтобы решить, учитывая сеть Петри N и маркировку M, $M ∈ R (N) {\ displaystyle M \ in R (N)}$ $M \ in R (N)$ .

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

Фактически, эта проблема была EXPSPACE -сложной за много лет до того, как была показана вообще разрешимость (Mayr, 1981). Продолжают публиковаться статьи о том, как это сделать эффективно. В 2018 году Czerwinski et al. улучшил нижнюю границу и показал, что проблема не в ЭЛЕМЕНТАРНОЙ.

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

Живучесть

Сеть Петри, в которой переход

t 0 {\ displaystyle t_ {0}}

t_ {0}

мертв, а для всех

j>0, {\ displaystyle j>0,}

j>0,

tj {\ displaystyle t_ {j}}

t_ {j}

L j {\ displaystyle L_ {j}}

L_j

-live

Сети Петри можно описать как имеющие разную степень живучести $L 1 - L 4 {\ displaystyle L_ {1} -L_ {4}}$ $L_1 - L_4$ . Сеть Петри $(N, M 0) { \ displaystyle (N, M_ {0})}$ $(N, M_0)$ называется $L k {\ displaystyle L_ {k}}$ $L_ {k}$ -live тогда и только тогда, когда все его переходы $L k {\ displaystyle L_ {k}}$ $L_ {k}$ -live, где переход

мертв, если он никогда не сработает, т. е. не входит ни в какую последовательность срабатывания в $L (N, M 0) {\ displaystyle L (N, M_ {0})}$ $L (N, M_0)$
$L 1 {\ displaystyle L_ {1}}$ $L_ {1}$ -live (потенциально активируемый), тогда и только тогда, когда он может выстрелить, т.е. он находится в s последовательность стрельбы в $L (N, M 0) {\ displaystyle L (N, M_ {0})}$ $L (N, M_0)$
$L 2 {\ displaystyle L_ {2}}$ $L_ {2}$ - жить, если может срабатывать произвольно часто, т.е. если для каждого положительного целого числа k это происходит не менее k раз в некоторой последовательности срабатывания в $L (N, M 0) {\ displaystyle L (N, M_ {0})}$ $L (N, M_0)$
$L 3 {\ displaystyle L_ {3}}$ $L_ {3}$ -живой, если он может срабатывать бесконечно часто, то есть если существует некоторая фиксированная (обязательно бесконечная) последовательность срабатывания, в которой для каждого положительного целого числа k переход $L 3 {\ displaystyle L_ {3}}$ $L_ {3}$ встречается как минимум k раз,
$L 4 {\ displaystyle L_ {4}}$ $L_4$ -live (live), если может всегда огонь, т.е. он $L 1 {\ displaystyle L_ {1}}$ $L_ {1}$ -в каждой достижимой отметке в $R (N, M 0) {\ displaystyle R (N, M_ { 0})}$ $R (N, M_0)$

Обратите внимание, что требования становятся все более строгими: $L j + 1 {\ displaystyle L_ {j + 1}}$ $L_ {j + 1}$ -liveness подразумевает $L j {\ displaystyle L_ {j}}$ $L_j$ -живость для $j ∈ 1, 2, 3 {\ textstyle \ textstyle {j \ in {1,2,3 }}}$ ${\ textstyle \ textstyle {j \ in {1,2,3}}}$ .

Эти определения соответствуют обзору Мураты, в котором дополнительно используется $L 0 {\ displaystyle L_ {0}}$ $L_ {0}$ -live как термин для мертвых.

Ограниченность

Граф достижимости N2.

Место в сети Петри называется k-ограниченным, если оно не содержит более k токенов во всех достижимых маркировках, включая начальную маркировку; считается безопасным, если он 1-ограничен; он ограничен, если он k-ограничен для некоторого k.

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

Обратите внимание, что сеть Петри ограничена тогда и только тогда, когда ее граф достижимости конечен.

Ограниченность разрешима, глядя на , покрывающее, путем построения Дерева Карпа –Миллера.

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

Некоторые определения сетей Петри явно допускают это как синтаксическую особенность. Формально сети Петри с емкостью мест можно определить как кортежи $(S, T, W, C, M 0) {\ displaystyle (S, T, W, C, M_ {0})}$ $(S, T, W, C, M_0)$ , где $(S, T, W, M 0) {\ displaystyle (S, T, W, M_ {0})}$ $(S, T, W, M_0)$ - сеть Петри, $C: P → ∣ N {\ displaystyle C: P \ rightarrow \! \! \! \ Shortmid \ mathbb {N}}$ ${\ displaystyle C: P \ rightarrow \! \! \! \ shortmid \ mathbb {N}}$ назначение пропускной способности (некоторым или всем) местам, и отношение перехода является обычным ограничено маркировкой, в которой каждое место с емкостью имеет не более указанного количества жетонов.

Неограниченная сеть Петри, N.

Например, если в сети N обоим разрядам назначена емкость 2, мы получаем сеть Петри с емкостью мест, скажем, N2; его график достижимости отображается справа.

Двуограниченная сеть Петри, полученная расширением N с помощью "встречных мест".

В качестве альтернативы, места могут быть ограничены путем расширения сети. Точнее, место можно сделать k-ограниченным, добавив «встречное место» с потоком, противоположным потоку места, и добавив жетоны, чтобы получить сумму в обоих местах k.

Дискретные, непрерывные и гибридные сети Петри

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

Расширения

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

Этот термин используется для обозначения многих формализмов сетей Петри, которые расширяют базовый формализм сетей P / T; сюда входят цветные сети Петри, иерархические сети Петри, такие как Сети внутри сетей, и все другие расширения, описанные в этом разделе. Этот термин также используется специально для типа цветных цепей, поддерживаемых CPN Tools.

Краткий список возможных расширений:

Дополнительные типы дуг; два общих типа:
- дуга сброса не накладывает предварительных условий на зажигание и освобождает место при срабатывании перехода; это делает достижимость неразрешимой, в то время как некоторые другие свойства, такие как завершение, остаются разрешимыми;
- запрещающая дуга накладывает предварительное условие, что переход может срабатывать только тогда, когда место пусто; это позволяет выражать произвольные вычисления числа токенов, что делает формализм полным по Тьюрингу и подразумевает существование универсальной сети.
В стандартной сети Петри токены неразличимы. В цветной сети Петри каждый токен имеет значение. В популярных инструментах для раскрашенных сетей Петри, таких как CPN Tools, значения токенов типизированы и могут быть протестированы (с использованием защитных выражений) и обработаны с помощью языка функционального программирования. Дочерней частью цветных сетей Петри являются правильно сформированные сети Петри, в которых выражения дуги и защиты ограничены, чтобы упростить анализ сети.
Еще одним популярным расширением сетей Петри является иерархия; это в форме различных представлений, поддерживающих уровни уточнения и абстракции, было изучено Фелингом. Другая форма иерархии встречается в так называемых объектных сетях Петри или объектных системах, где сеть Петри может содержать сети Петри в качестве своих токенов, вызывающих иерархию вложенных сетей Петри, которые взаимодействуют посредством синхронизации переходов на разных уровнях. См. Неформальное введение в объектные сети Петри.
A Система сложения векторов с состояниями (VASS) - формализм, эквивалентный сетям Петри. Однако на поверхностном уровне его можно рассматривать как обобщение сетей Петри. Рассмотрим конечный автомат , в котором каждый переход помечен переходом из сети Петри. Затем сеть Петри синхронизируется с конечным автоматом, т. Е. Переход в автомате выполняется одновременно с соответствующим переходом в сети Петри. Переход в автомате возможен только в том случае, если соответствующий переход в сети Петри разрешен, и только возможно инициировать переход в сети Петри, если в автомате, помеченном им, есть переход из текущего состояния.. (Определение VASS обычно формулируется несколько иначе.)
Приоритетные сети Петри добавляют приоритеты переходам, в результате чего переход не может сработать, если включен переход с более высоким приоритетом (т. Е. Может сработать). Таким образом, переходы находятся в приоритетных группах, и, например, группа приоритета 3 может срабатывать, только если все переходы отключены в группах 1 и 2. Внутри группы приоритетов срабатывание все еще недетерминировано.
Недетерминированное свойство было очень ценным, поскольку оно позволяет пользователь абстрагирует большое количество свойств (в зависимости от того, для чего используется сеть). Однако в некоторых случаях возникает необходимость в моделировании сроков, а не только структуры модели. Для этих случаев разработаны случаи, когда есть переходы, которые рассчитаны по времени, и, возможно, переходы, которые не рассчитаны по времени (если есть, переходы, которые не синхронизированы, имеют более высокий приоритет, чем синхронизированные). Дочерним элементом синхронизированных сетей Петри являются стохастические сети Петри , которые добавляют недетерминированное время посредством регулируемой случайности переходов. экспоненциальное случайное распределение обычно используется для "хронометрирования" этих сетей. В этом случае граф достижимости сетей можно использовать как непрерывную временную цепь Маркова (CTMC).
Дуалистические сети Петри (dP-Nets) - это расширение сети Петри, разработанное E, Dawis, et al. чтобы лучше представить реальный процесс. dP-Nets уравновешивают двойственность: изменение / отсутствие изменений, действие / пассивность, (преобразование) время / пространство и т. д. между двудольными конструкциями преобразования сети Петри и местом, что приводит к уникальной характеристике маркировки преобразований, т. е. когда трансформация "рабочая" отмечена. Это позволяет преобразованию запускаться (или быть отмеченным) несколько раз, представляя реальное поведение пропускной способности процесса. Обозначение преобразования предполагает, что время преобразования должно быть больше нуля. Нулевое время преобразования, используемое во многих типичных сетях Петри, может быть математически привлекательным, но непрактичным для представления реальных процессов. dP-Nets также используют мощь иерархической абстракции сетей Петри для изображения архитектуры процесса. Сложные технологические системы моделируются как ряд более простых сетей, связанных между собой через различные уровни иерархической абстракции. Архитектура процесса пакетного коммутатора демонстрируется, где требования к разработке организованы вокруг структуры разработанной системы.

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

Ограничения

Типы сетей Петри графически

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

В конечном автомате (SM) каждый переход имеет один входящая дуга и одна исходящая дуга, и все маркировки имеют ровно один жетон. Как следствие, не может быть параллелизма, но может быть конфликт (т.е. недетерминизм ). Математически: $∀ t ∈ T: | т ∙ | = | ∙ т | = 1 {\ displaystyle \ forall t \ in T: | t ^ {\ bullet} | = | {} ^ {\ bullet} t | = 1}$ $\ forall t \ in T: | t ^ \ bullet | = | {} ^ \ bullet t | = 1$
В отмеченном графе (MG), каждое место имеет одну входящую дугу и одну исходящую дугу. Это означает, что не может быть конфликта, но может быть параллелизм. Математически: $∀ s ∈ S: | с ∙ | = | ∙ с | = 1 {\ displaystyle \ forall s \ in S: | s ^ {\ bullet} | = | {} ^ {\ bullet} s | = 1}$ $\ forall s \ в S: | s ^ \ bullet | = | {} ^ \ bullet s | = 1$
В сети со свободным выбором (FC) каждая дуга из Место до перехода - это либо единственная дуга от этого места, либо единственная дуга до этого перехода, то есть может быть как параллелизм, так и конфликт, но не одновременно. Математически: $∀ s ∈ S: (| s ∙ | ≤ 1) ∨ (∙ (s ∙) = {s}) {\ displaystyle \ forall s \ in S: (| s ^ {\ bullet} | \ leq 1) \ vee ({} ^ {\ bullet} (s ^ {\ bullet}) = \ {s \})}$ $\ forall s \ in S: (| s ^ \ bullet | \ leq 1) \ vee ({} ^ \ bullet (s ^ \ bullet) = \ {s \})$
Расширенный свободный выбор (EFC) - сеть Петри, которая может быть преобразована в FC.
В сети асимметричного выбора (AC) может возникать параллелизм и конфликт (в сумме, путаница), но не симметрично. Математически: $∀ s 1, s 2 ∈ S: (s 1 ∙ ∩ s 2 ∙ ≠ ∅) → [(s 1 ∙ ⊆ s 2 ∙) ∨ (s 2 ∙ ⊆ s 1 ∙)] {\ displaystyle \ forall s_ {1}, s_ {2} \ in S: (s_ {1} {} ^ {\ bullet} \ cap s_ {2} {} ^ {\ bullet} \ neq \ emptyset) \ to [(s_ {1} {} ^ {\ bullet} \ substeq s_ {2} {} ^ {\ bullet}) \ vee (s_ {2} {} ^ {\ bullet} \ substeq s_ {1} {} ^ {\ bullet })]}$ $\ forall s_1, s_2 \ in S: (s_1 {} ^ \ bullet \ cap s_2 {} ^ \ bullet \ neq \ emptyset) \ to [(s_1 {} ^ \ bullet \ substeq s_2 {} ^ \ bullet) \ vee (s_2 {} ^ \ bullet \ substeq s_1 {} ^ \ bullet)]$

Сети рабочего процесса

(WF-сети) - это подкласс сетей Петри, предназначенный для моделирования рабочего процесса действий процесса. Переходы WF-net назначаются задачам или действиям, а места назначаются предварительным / пост-условиям. У WF-сетей есть дополнительные структурные и эксплуатационные требования, в основном добавление одного места ввода (источника) без предыдущих переходов и места вывода (приемника) без последующих переходов. Соответственно, могут быть определены маркировки начала и завершения, которые представляют состояние процесса.

WF-сети имеют свойство soundness, указывающее, что процесс с меткой начала из k токенов в исходном месте может достичь состояния завершения, отмеченного k токенами в своем месте приемника ( определяется как k-звук WF-net). Кроме того, все переходы в процессе могут срабатывать (т.е. для каждого перехода существует достижимое состояние, в котором переход разрешен). Общий звук (G-звук) WF-сеть определяется как k-звук для каждого k>0.

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

A хорошо управляемая сеть Петри - это сеть, в которой нет полностью различных элементарных путей между местом и переходом (или переходом и местом), т. Е. Если есть два пути между парой узлов, то эти пути имеют общий узел. Ациклическая хорошо управляемая WF-сеть - это звук (G-звук).

Расширенная WF-сеть - это сеть Петри, которая состоит из WF-сети с дополнительным переходом t (переход с обратной связью). Место стока соединено как входное место перехода t и место источника как его выходное место. Запуск перехода вызывает итерацию процесса (Примечание: расширенная WF-сеть не является WF-сетью).

WRI (Хорошо обрабатывается с помощью регулярных итераций) WF-сеть, является расширенной ациклической хорошо- обработал WF-net. Сеть WRI-WF может быть построена как композиция сетей, то есть путем замены перехода в сети WRI-WF подсетью, которая является сетью WRI-WF. Результат - тоже WRI-WF-net. WRI-WF-сети являются G-звуком, поэтому, используя только строительные блоки WRI-WF-net, можно получить WF-сети, которые имеют G-звук по конструкции.

Матрица структуры проекта (DSM) может моделировать взаимосвязи процессов и использоваться для планирования процессов. DSM-сети являются воплощением планов на основе DSM в рабочие процессы с помощью сетей Петри и эквивалентны WRI-WF-сетям. Процесс построения DSM-сети обеспечивает свойство прочности полученной сети.

Другие модели параллелизма

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

Подход к связи некоторых из этих моделей параллелизма предложен в главе Винскеля и Нильсена.

Области применения

См. также

Ссылки

Дополнительная литература

Cardoso, Janette; Камарго, Элоиза (1999). Нечеткость в сетях Петри. Physica-Verlag. ISBN 978-3-7908-1158-2.
Гробелна, Ивона (2011). «Формальная проверка спецификации встроенного логического контроллера с компьютерной дедукцией во временной логике». Przeglad Elektrotechniczny. 87 (12a): 47–50.
Дженсен, Курт (1997). Цветные сети Петри. Springer Verlag. ISBN 978-3-540-62867-5.
Котов, Вадим (1984). Сети Петри. Наука, Москва.
Патарича, Андраш (2004). Formális módszerek az informatikában (Формальные методы в информатике). TYPOTEX Kiadó. ISBN 978-963-9548-08-4.
Петерсон, Джеймс Л. (1977). «Сети Петри». ACM Computing Surveys. 9 (3): 223–252. doi : 10.1145 / 356698.356702. HDL : 10338.dmlcz / 135597. S2CID 3605804.
Петерсон, Джеймс Лайл (1981). Теория сетей Петри и моделирование систем. Прентис Холл. ISBN 978-0-13-661983-3. CS1 maint: ref = harv (ссылка )
Петри, Карл А. (1962). Kommunikation mit Automaten (докторская диссертация). Университет Бонна.
Петри, Карл Адам; Рейзиг, Вольфганг (2008). "Сеть Петри". Scholarpedia. 3 ( 4): 6477. doi : 10.4249 / scholarpedia.6477.
Reisig, Wolfgang (1992). Учебник по дизайну сетей Петри. Springer-Verlag. ISBN 978-3-540-52044-3.
Риман, Роберт-Кристоф (1999). Моделирование параллельных систем: структурные и семантические методы в исчислении сети Петри высокого уровня. Herbert Utz Verlag. ISBN 978-3-89675-629-9.
Störrle, Harald (2000). Модели архитектуры программного обеспечения - проектирование и анализ с помощью UML и сетей Петри. Книги по запросу. ISBN 978-3-8311-1330-9.
Чжоу, Mengchu ; Dicesare, Frank (1993). Синтез сетей Петри для управления дискретными событиями производственных систем. Kluwer Academic Publishers. ISBN 978-0-7923-9289-7.
Чжоу, Мэнчу ; Венкатеш, Курапати (1998). Моделирование, имитация и управление гибкими производственными системами: подход сети Петри. Мировое научное издательство. ISBN 978-981-02-3029-6.
Зайцев Дмитрий ( 2013). Кланы сетей Петри: проверка протоколов и оценка производительности сетей. LAP LAMBERT Academic Publishing. ISBN 978-3-659-42228-7.

Внешние ссылки

На Викискладе есть медиафайлы, связанные с сетями Петри.