Мережа Петрі

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Приклад мережі Петрі.

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

Визначення[ред.ред. код]

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

  • Позиції. 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.