Мережа Петрі

Приклад мережі Петрі.

Мережа Петрі — математична абстракція для представлення дискретних розподілених систем. Графічно представляється у вигляді дводольного орієнтованого мультиграфу з маркерами («фішками») (маркований орієнтований граф), який має дві групи вершин: позиції та переходи. Позиції можуть бути пустими або маркованими та визначають <стан> мережі. Переходи визначають дії. Орієнтовані ребра графу задають зв'язки між позиціями та переходами. Процес функціонування мережі Петрі полягає в послідовному «виконанні» переходів, та відповідному перерахункові кількості «фішок» у позиціях. Дуги можуть бути кратними, коли два вузли з'єднані більше ніж однією дугою однакового напрямку. Альтернативно, для відображення кратності дуг може використовуватися функція «ваги» дуг.

Визначення

Мережа Петрі задається у вигляді маркованого дводольного орієнтованого графу. Розрізняють два види вершин:

• Позиції. P — множина позицій,
• Переходи. T — множина переходів.

Ребра називають дугами. Петлі в графі мереж Петрі неможливі, оскільки дуги можуть з'єднувати лише вершини різних типів (позиції та переходи). Позиції що з'єднані дугами з переходом називають вхідними та вихідними для цього переходу, відповідно до напрямку цих дуг.

Кожній позиції приписують деяке ціле додатнє число

$\mu_p \in \mathbb{N} \cup \{0\}$

що називається маркуванням. Сукупність маркувань всіх позицій можна записувати у вигляді вектора.

Таким чином, для того щоб задати мережу Петрі, необхідно задати пару

$\left\langle\mathbf N, \mu_0 \right\rangle$

де $\mu_0 = \left\{\mu(p_1),\mu(p_2),...\mu(p_n)\right\}$ — вектор маркування позицій, $\mathbf N$ — структура мережі Петрі:

$\mathbf N = \left\langle\mathbf P, \mathbf T, \mathbf I, \mathbf O \right\rangle$.

де $\mathbf P$ — множина позицій, $\mathbf T$ — множина переходів, $\mathbf I$ — вхідна функція, $\mathbf O$ — вихідна функція.
Вхідна та вихідна функції задаються у вигляді множин комлектів позицій, які є вхідними та вихідними для заданого переходу:

$\mathbf I = \left\{\mathbf I(t_j)\right\}$, $\mathbf \mathbf I(t_j) = \left\{p_k\right\}$.

$\mathbf O = \left\{\mathbf O(t_j)\right\}$, $\mathbf \mathbf O(t_j) = \left\{p_k\right\}$.

Комплект — узагальнення множини, в якому допускається багаторазове включення однакових елементів. Для комплектів визначається операція кратності. Для запису функції кратності використовується символ #. Кратність вхідної (вихідної) позиції $p_i$ для переходу $t_j$ це кількість появ позиції $p_i$ у вхідному (вихідному) комплекті переходу $t_j$:

$\#(p_i, \mathbf I(t_j))$.

Альтернативною формою представлення вхідної та вихідної функції є задання множини дуг та окремого вектору кратності (ваги) дуг.
Виконання переходу можливе лише за наявності достатньої кількості «фішок» у його вхідних позиціях. Умова можливості виконання переходу $t_j$:

$\mu(p_i) \ge \;\#\left(p_i, \mathbf I(t_j)\right) \forall p_i\in\mathbf P$.

Результатом виконання переходу є зміна кількості «фішок» у вхідних та вихідних позиціях цього переходу, тобто зміна маркування (стану) мережі Петрі. Нове маркування $\mu^{i+1}$ визначається таким співвідношенням:

$\mu^{i+1}(p_i) = \mu^i(p_i) - \#(p_i, \mathbf I(t_j)) + \#(p_i, \mathbf O(t_j))$,

де $t_j$ — перехід що виконується $\mu^{i}(p_i)$ — попереднє маркування.
Цей вираз дозволяє записати векторну функцію наступного стану, яка виражає наступне маркування мережі Петрі через попереднє маркування та перехід що виконується:

$\mu^{i+1} = \delta\left(\mu^i, t_j\right)$.

Для заданої послідовності виконання переходів $\sigma = \left\langle t_{j1}, t_{j2},... ,t_{jl}\right\rangle$ використовується розширена функція наступного стану:

$\mu^{i+l} = \delta\left(\mu^i, \sigma\right) = \delta\left(... \delta\left(\delta\left(\mu^i, t_{j1}\right), t_{j2}\right),... ,t_{jl}\right)$.

Виконання переходів є атомарним, тобто перехід змінює стан всіх вхідних та вихідних позицій однією дією, яка не може бути перервана виконанням іншого переходу. Виконання мереж Петрі в цілому є недетермінованим:

1. відразу декілька переходів можуть бути дозволеними, і кожен з них може бути виконаний
2. дозволені переходи не обов'язково виконуються. Дозволений перехід може бути виконаний.

Взагалі, мережі Петрі не розглядають поняття «часу» виконання переходу, а лише послідовність виконань. За допомогою мереж Петрі можна моделювати такі якості як:

• асинхронність,
• конфліктнісь,
• паралелізм.

Типи

• Часова мережа – переходи також мають вагу, що визначає тривалість спрацьовування(затримку);
• Стохастична мережа – затримки є випадковими величинами;
• Функціональна мережа – затримки визначаються, як функції деяких аргументів, наприклад: кількості міток в будь-яких позиціях, станами деяких переходів;
• Кольорова мережа – мітки можуть бути різних типів, що позначаються кольорами, тип мітки може бути використаний як аргумент в функціональних мережах;
• Інгібаторна мережа – можливі деякі інгібіторні дуги, котрі забороняють спрацьовування переходів, якщо в позиції, пов'язаній з переходом інгібіторної дуги знаходиться мітка.

Дослідження мережі Петрі

Основні методи дослідження мереж Петрі:

1. Дерево досягальності,
2. Графічний,
3. Аналітичний,
4. За допомогою еквівалентних перетвореннь.

Взагалі, мережі Петрі досліджують на такі властивості:

1. Безпечність — досліджує виконання умови що кількість «фішок» в позиції не перевищує 1;
2. Обмеженість — досліджує виконання умови що кількість «фішок» в позиції не перевищує заданого числа,
3. Зберігальність — досліджує виконання умови що кількість «фішок» в мережі не змінюється,
4. Оберненість — для довільного досяжного стану досліджується існування послідовності виконань переходів яка повертає мережу в початковий стан),
5. Активність переходів — досліджує можливість виконання певних переходів та наявність тупиків — станів у яких переходи не дозволені та для яких неможливо досягти стану в якому ці переходи дозволені,
6. Досяжність маркування — досліджує існування послідовності виконань переходів при якій можна досягнути задане маркування,
7. Покриття — досліджує існування послідовності виконань переходів при якій можна досягнути маркування що покриває, тобто є більшим за задане маркування.

Умова зберігальності може бути послаблена, для чого вводять поняття функції ваги:

$\mathbf W:\qquad(\mathbf T \times \mathbf P) \cup (\mathbf P \times \mathbf T) \to \mathbb N \cup \{0\}$

яка залишається постійною під час роботи.

Більшість досліджень мереж Петрі можна звести до побудови дерева досяжності.

Див. також

• Теорія графів,
• Розподілена система,
• Скінченний автомат.

Література

• Reisig, Wolfgang; Rozenberg, Grzegorz (1998). Lectures on Petri Nets I--basic models: advances in Petri Nets. Berlin: Springer. ISBN 3-540-65306-6. 
• Reisig, Wolfgang; Rozenberg, Grzegorz (1998). Lectures on Petri nets II--applications: advances in Petri nets. Berlin: Springer. ISBN 3-540-65307-4.