Пошук

Панель інструментів

Іншими мовами

Мережа Петрі

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

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

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

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

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

Результатом виконання переходу є зміна кількості "фішок" у вхідних та вихідних позиціях цього переходу, тобто зміна маркування (стану) мережі Петрі. Нове маркування $μ 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$ - перехід що виконується $μ i + 1 (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;
Обмеженість - досліджує виконання умови що кількість "фішок" в позиції не перевищує заданого числа,
Зберігальність - досліджує виконання умови що кількість "фішок" в мережі не змінюється,
Оберненість - для довільного досяжного стану досліджується існування послідовності виконань переходів яка повертає мережу в початковий стан),
Активність переходів - досліджує можливість виконання певних переходів та наявність тупиків - станів у яких переходи не дозволені та для яких неможливо досягти стану в якому ці переходи дозволені,
Досяжність маркування - досліджує існування послідовності виконань переходів при якій можна досягнути задане маркування,
Покриття - досліджує існування послідовності виконань переходів при якій можна досягнути маркування що покриває (є більшим) за задане маркування.

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