Мережі Петрі

Мережі Петрі (МП) — математичний апарат для моделювання динамічних дискретних систем. Вперше описані Карлом Петрі у 1962 році.

Рисунок 1 — Приклад  мережі Петрі. Білими колами позначені позиції, смужками — переходи, чорними колами — мітки.

МП використовуються для моделювання асинхронних систем, що функціонують як сукупність паралельних взаємодіючих процесів. Аналіз МП дозволяє отримати інформацію про структуру та динамічну поведінку модельованої системи.

Причинно-наслідковий зв'язок подій в асинхронних системах задається множиною відношень вигляду «умови-події». У МП умови — це позиції, а події — переходи. Відповідно до цього граф МП є двочастковим орієнтованим мультиграфом. Орієнтовані дуги можуть сполучати лише позиції і переходи в прямому і зворотному напрямі. МП є мультиграфом, оскільки допускається кратність дуг між позиціями і переходами.

B графах МП кількісні характеристики умов (числа натурального ряду) прийнято задавати числом міток у відповідних позиціях.

Послідовності подій відображуються спрацьовуваннями переходів. Виконання якої-небудь умови пов'язане з появою однієї або декількох міток у відповідній цій умові позиції. Угоди про правила спрацьовування переходів є способом представлення причинно-наслідкових зв'язків між умовами і подіями в системі (рис.1).

Історія

МП розроблялися спеціально для моделювання тих систем, які містять взаємодіючі паралельні компоненти. Вперше МП запропонував Карл Петрі у своїй докторській дисертації «Kommunikation mit Automaten» («Зв'язок автоматів»). Він сформулював основні поняття теорії зв'язку асинхронних компонент обчислювальної системи. Зокрема, детально розглянув опис причинних зв'язків між подіями. Його дисертація присвячена, головним чином, теоретичній розробці основних понять, з яких почали розвиток МП.

Робота Петрі привернула увагу А. В. Хольта і співробітників з Information System Theory (Теорія інформаційних систем) фірми Applied Data Research (ADR). Ними була розвинена велика частина початків теорії, запропоновані позначення і представлення МП, опубліковані в окремому звіті, що має назву «Events and Conditions» («Події і умови»). У цій роботі показано, як МП можна застосувати до аналізу і моделювання систем, що включають паралельні компоненти.

Робота Петрі привернула також увагу групи, що працює над проєктом MAC в Массачусетському технологічному інституті (МТІ). Керована професором Дж. Б. Деннісом група обчислювальних структур стала джерелом значних досліджень і публікацій по МП, було написано декілька дисертацій на ступень доктора філософії і безліч звітів і меморандумів. Групою обчислювальних структур були проведені дві великі конференції з МП: Конференція Проєкта MAC з паралельних систем і паралельних обчислень в 1970 р. у Вудс Холле і Конференції з МП і пов'язаних з ними методів в 1975 р. в МТІ. Обидві ці конференції внесли вклад до поширення результатів і методів теорії МП.

Визначення

МП задається у вигляді маркованого двочасткового орієнтованого графу. Розрізняють два типи вершин: позиції (позначаються колами) і переходи (позначаються смужками). МП може бути формально подана у вигляді як сукупність множин: $N=(P,T,G,\Omega )$, де

$P=\{p_{1},p_{2}...p_{n}\}$ — множина всіх позицій ($n$ — кількість позицій);

$T=\{t_{1},t_{2}...t_{m}\}$ — множина переходів ($m$ — кількість переходів);

$G=\{G_{p-t},G_{t-p}\}$ — множина дуг мережі: $G_{p-t}=(p\times t)$, $G_{t-p}=(t\times p)$ — множини дуг, що ведуть відповідно від переходів до позицій і від позицій до переходів (дуг, що з'єднують однорідні вершини, не існує);

$\Omega =\{\omega _{1},\omega _{2}...\omega _{k}\}$ — множина ваг дуг ($k$ — кількість дуг).

Кожна позиція може бути маркована, тобто містити певну кількість маркерів. Якщо позначити числа міток, які перебувають в i-й позиції $p_{i}$, як $m_{i}$, то маркування всієї мережі: $M=\{m_{1},m_{2}...m_{n}\}$. Тоді повне визначення МП, включаючи дані про початкове маркування, можна записати у вигляді $PN=(N,M_{0})$, де $M_{0}$ — початкове маркування мережі.

При моделюванні процесів прийняття рішень за допомогою МП її позиції інтерпретують собою деякі умови, стани, значення змінних тощо. Переходи інтерпретують собою логічні пропозиції (прийняття рішень), відповідні виконанню дій, при цьому вхідні позиції — умови виконання дій, вихідні позиції — результат виконання дій. Дія (перехід) пов'язана з прийняттям будь-якого рішення, яке ініційоване певними умовами і результатом якого є новий стан (умова).

Правила спрацьовування переходів

Рисунок 2 — Фрагмент мережі Петрі до а) і після б) спрацьовування переходу

Перехід спрацьовує, якщо для кожної з його вхідних позицій виконується умова $N_{i}\geq K_{i}$, де $N_{i}$ — число маркерів в i-й вхідний позиції, $K_{i}$  - число дуг, що йдуть від i-й позиції до переходу; при спрацьовуванні переходу число маркерів в i-й вхідний позиції зменшується на $K_{i}$, а в j-й вихідний позиції збільшується на $M_{j}$, де $M_{j}$ — число дуг, що пов'язують перехід з j-ю позицією.

На рисунку 2 показаний приклад розподілу маркерів по позиціях перед спрацьовуванням, це маркування записують у вигляді (2,2,3,1). Після спрацьовування переходу маркування стає іншим: (1,0,1,4).

Граф досяжності

У МП кожній вершині відповідає певне маркування, а кожній дузі — перехід, який спрацьовує при цьому маркуванні. Таким чином, граф досяжності представляється як $GD=(V,E)$ де

$V$ — множина вершин (маркувань, відповідних вершин): $V=\{M_{1},M_{2}...M_{q}\}$, $M_{i}$ — i-те маркування, $q$ — кількість маркувань;

$E=\{e_{1},e_{2}...e_{p}\}$ — множина дуг, що зв'язують вершини ($p$ — кількість дуг).

Кожна дуга представляється як сукупність $e_{i}=\{\alpha _{1},\alpha _{2},T\}$, де

$\alpha _{1}$ и $\alpha _{2}$ — номери початкової і кінцевої вершин графу;

$T=\{t_{1},t_{2}...t_{k}\}$ — множина переходів, відповідний дузі, $k$ — кількість переходів, що одночасно спрацьовують при переході від одного маркування до іншого.

Алгоритм побудови графу для мереж Петрі

Рисунок 3 — Граф досяжності мережі Петрі

1. За початкове береться маркування $M_{0}$ і йому привласнюється мітка «нове». 2. Для кожного «нового» маркування виконувати наступні операції:

2.1 Для «нового» маркування М_нов визначаються всі переходи, які можуть бути запущені, а також всі можливі комбінації цих переходів.

2.2 Для кожного дозволеного переходу або комбінації переходів здійснюються такі дії:

2.2.1 Визначається маркування$M'$, яке утворюється при спрацьовуванні даного переходу (комбінації переходів).

2.2.2 Переглядаються всі маркування на шляху від $M'$ до початкової $M_{0}$. Якщо на шляху знаходиться маркування $M''$, елементи якої більше або рівні відповідним елементам нової і яка не дорівнює $M'$, то замість елементів $m_{i}^{'}$, які більше, ніж елементи $m_{i}$маркування $M_{0}$, записується символ"$\omega$"(нескінченність). У масив $E$ записується дуга з відповідними $\alpha _{1}$, $\alpha _{2}$ и $T$.

2.2.3 Проглядаються всі маркування графу. Якщо знаходиться маркування, рівне новому, то в масив $E$ записується нова дуга, у якій $\alpha _{1}$ = $\alpha _{2}$ і рівні номера знайденого маркування.

2.2.4 Якщо в попередніх пунктах 2.2 і 2.3 маркування не знайдені, то створюється нова вершина графу, в яку записується нове маркування, в масив $E$ записується дуга, у якій $\alpha _{1}$ дорівнює номеру початкового маркування, $\alpha _{2}$ — номеру нового маркування, $T$ — набір переходів, спрацювання яких призвело до переходу від одного маркування до іншого. Далі визначається масив всіх дозволених переходів і розрахунок триває, починаючи з п. 2.2

Для розглянутого вище прикладу  МП граф досяжності має вигляд (рисунок 3), список маркувань приведений у таблиці 1.

Таблиця 1 — Список маркувань.

	(Р1 Р2 Р3 Р4 Р5 Р6 Р7 Р8)
M1	(11000000)
M2	(00100000)
M3	(00010000)
M4	(00000100)
M5	(00000001)
M6	(00001000)
M7	(00000010)

Види мереж Петрі

Види мереж Петрі:

1. Часова МП — мережа характеризується введенням затримок при переміщенні маркера, затримка може бути зв'язана як з переходом так і з позицією.
2. Стохастична МП — затримки є випадковими параметрами.
3. Функціональна МП — затримки визначаються як функції деяких аргументів, наприклад, кількості міток в яких-небудь позиціях, стани деяких переходів.
4. Кольорова МП — мітки можуть бути різних типів, що позначаються кольорами, тип мітки може бути використаний як аргумент у функціональних мережах.
5. Інгібіторна МП — можливі інгібіторні дуги, що забороняють спрацьовування переходу, якщо у вхідній позиції, пов'язаної з переходом інгібіторною дугою, знаходиться мітка.
6. Ієрархічна МП — містить не миттєві переходи, в які вкладені інші, можливо, також ієрархічні, мережі. Спрацьовування такого переходу характеризує виконання повного життєвого циклу вкладеної мережі.
7. Потокова МП (Work Flow  Petri Nets — WF) -  називається мережею потоків робіт (WF-мережею), використовують для моделювання потоків робіт в WorkFlow системах.
8. Мережі з пріоритетами — додають до дозволених переходів пріоритети і тим самим дозволяють понизити недетермінованість спрацьовувань, обмежуючи безліч дозволених переходів групою переходів з найвищим пріоритетом.

Властивості мереж Петрі

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

1. Безпека позиції. Позиція $p_{i}\in P$ називається безпечною в заданому початковому маркуванні $\mu _{0}$, якщо в процесі роботи цієї мережі в даній позиції $p_{i}$ ніколи не з'явиться більш за один маркер, тобто $\mu (p_{i})\leq 1$. Мережа Петрі називається безпечною, якщо безпечні всі її позиції. Ця властивість важлива при моделюванні каналів передачі даних (за відсутності буфера).
2. Обмеженість. Позиція $p_{i}\in P$ називається обмеженою в заданому початковому маркуванні $\mu _{0}$, якщо в процесі роботи цієї мережі в даній позиції $p_{i}$ ніколи не з'явиться більш за $k$-маркерів, тобто $\mu (p_{i})\leq k$.
3. Стійкість. МП називається стійкою, якщо для будь-якого її переходу $t_{i}\in T$ виконується наступна умова: стан збудження цього переходу $t_{i}^{*}$ не може бути зняте спрацьовуванням іншого будь-якого переходу. Якщо в мережі є альтернативні переходи, то вона є нестійкою.
4. Досяжність. Маркування $\mu ^{'}$ називається досяжним з деякого маркування $\mu$, якщо для даної моделі МП можна вказати таку послідовність спрацьовування переходів, яка переводить маркування $\mu$ у маркування $\mu ^{'}$. $\mu {\xrightarrow {\alpha }}\mu ^{'},\alpha =t_{i1}t_{i2}...t_{ik}$
5. Активність (жвавість). Перехід $t\in T$ називається активним (живим) в заданому початковому маркуванні $\mu _{0}$, якщо для будь-якого маркування $\mu ^{'}$, досяжного з $\mu _{0}$ можна вказати ланцюжок спрацьовувань переходів, який призводить до порушення переходу $t$. Ця властивість має важливе значення при дослідженні проблем зависання, зациклення і блокування процесів і можливості завершення процесу. Мережа називається активною в заданому початковому маркуванні μ₀, якщо активні (живі) всі її переходи.

Процес функціонування мереж Петрі

Процес функціонування мережі Петрі задається наступними двома правилами:

1. Якщо в деякий момент часу в кожній вхідній позиції переходу $t$ є хоча б по одному маркеру, то перехід $t$ називається збудженим. $\forall p\in I(t)(\mu (p)\geq 1)\Rightarrow t^{*}$, де $t^{*}$ — збудження переходу
2. Збуджений перехід може спрацювати; момент спрацьовування збудженого переходу не задається і може бути цілковито випадковим. Якщо перехід $t$ спрацює, то відбувається зміна маркування позицій і з кожної вхідної позиції   видаляються по одному маркеру, а в кожну вихідну позицію   додаються по одному маркеру: $\forall p\in I(t)(\mu (p):=\mu (p)-1)$, $\forall p\in O(t)(\mu (p):=\mu (p)+1)$. За цими правилами МП функціонують, починаючи з початкового маркування $\mu _{0}$, і процес буде тривати до тих пір, поки може бути збуджений хоча б один перехід. Маркування $\mu$, при якому жоден перехід не збуджений, називається тупиковим. Після досягнення тупикового маркування робота мережі припиняється.

Нечітке моделювання з використанням мереж Петрі

В процесі моделювання за допомогою МП інколи доводиться описувати стан, настання якого не прогнозоване. У класичних МП спрацьовування переходу залежить від того, чи вірна умова чи ні. Але інколи необхідна МП, здатна працювати з невизначеними величинами («малий», «великий», …), — нечітка МП.

Нечітка мережа Петрі задається 6-ма змінними: НМП = $\{P,T,W,\alpha (t),\tau (t),M_{0}(P)\}$, де

$P$ — кінцевий набір нечітких позицій, і з'єднання між позиціями можуть набувати будь-яких ненегативних натуральних значень.

$T$- кінцевий набір нечітких переходів.

$W$– нечітке відношення з маркуванням на $P\times T$ або $T\times P$, зване ваговою функцією, яка показує вхідну величину на дузі від позиції до переходу  або вихідну величину на дузі від переходу до позиції.

$\alpha (t)$ і $\tau (t)$ — невід'ємні речові функції від $T$, які показують пріоритет з'єднання і поріг спрацьовування переходу відповідно.

$M_{0}(t)$ — невід'ємна речова функція від $P$, що показує початкове маркування і також звана початковим розподілом ресурсів.

Нехай мітка буде носієм нечіткої величини, з'єднання будуть визначатися лінгвістичними висловлюваннями правил ЯКЩО-ТО і переходи будуть представляти базове нечітке відношення виходячи з правил ЯКЩО-ТО.

Нечіткі правила ЯКЩО-ТО — принцип, який використовується для опису логічної залежності між змінними в такій формі: ЯКЩО $X_{1}$ належить $A_{1}$ І $X_{n}$ належить $A_{n}$ ТО $Y$ належить $B$, де $A_{1},...,A_{n}$ і $B$ — певні вирази, що характеризують змінні $X_{1},...,X_{n}$ і $Y$. Вони найчастіше задаються лінгвістично.

Частина перед ТО називається антецедент, частина після ТО називається сукцедент. Змінні $X_{1},...,X_{n}$ називаються вхідними або незалежними змінними. Мінлива $Y$ називається вихідною або залежною змінною.

Нечіткі правила ЯКЩО-ТО зазвичай об'єднуються разом, утворюючи лінгвістичний опис.

Література

• Ачасова С. М., Бандман О. Л. Корректность параллельных вычислительных процессов. — Н.: Наука, 1990. — 253 с.
• Котов В. Е. Сети Петри. — М.: Наука, 1984. — 160 с.
• Мараховский  В. Б., Розенблюм  Л. Я.,  Яковлев  А. В. Моделирование параллельных процессов. Сети Петри. Курс для системных архитекторов, программистов, системных аналитиков, проектировщиков сложных систем управления. — Санкт-Петербург: Профессиональная литература, АйТи-Подготовка, 2014. — 400 с.
• Норенков И. П., Кузьмик П. К.  Информационная поддержка наукоемких изделий.  М.: МГТУ им. Н. Э. Баумана.   2002. — 347с. 
• Питерсон Дж. Теория сетей Петри и моделирование систем. — М: Мир, 1984. — 264 с.
• Слепцов А. И., Юрасов А. А. Автоматизация проектирования управляющих систем гибких автоматизированных производств /Под ред. Б. Н. Малиновского.– К.: Техніка, 1986.–160 с.
• Тэрано, Т.; Асаи, К.; Сугэно, М.  Прикладные нечеткие системы.  М.: Мир.   1993. — 368с.

Див. також

• Система масового обслуговування
• Кінцевий автомат
• Теорія графів

Джерела

• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
• Роджерс Х.. Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)