Мрежа на Петри

Мрежите на Петри (на английски: Petri net) задават един от няколкото езика за математическо моделиране и описание на дискретни разпределени системи. Мрежата на Петри е ориентиран двуделен (двуцветен) граф, чиито възли представляват:

• преходи (transitions), т.е. дискретни събития, които могат да настъпят,
• позиции (places), т.е. условия, и
• насочени (ориентирани) дъги, които описват кои позиции за кои преходи са пред и/или пост-условия.

Мрежите на Петри са дефинирани през 1962 година от Карл-Адам Петри.

Подобно на индустриални стандарти като UML-диаграмите, Business Process Modeling Notation и Event-driven process chain, появили се доста по-късно, мрежите на Петри предлагат графична нотация на постъпкови процеси, съдържащи избор, итерация и паралелно изпълнение. За разлика от тези стандарти, мрежите на Петри имат точна математическа дефиниция на семантиката на изпълнението си, с добре разработена математическа теория за анализ на процесите.

Неформално описание

Една мрежа на Петри се състои от позиции, преходи и насочени дъги. Една дъга свързва една позиция и един преход, но не и двойка позиции или двойка преходи. Позиция, от която започва дъга, се нарича входна позиция за прехода; а такава, в която влиза започнала от преход дъга, се нарича изходна позиция.

Позициите могат да съдържат произволен брой ядра (tokens). Разпределението на ядрата по позиции на мрежата се нарича маркировка (marking). Тя отразява състоянието на системата във фиксиран момент от време и се променя в някой следващ момент, в резултат от активиране на поне един преход. Преход в мрежата на Петри се активира, когато се появи ядро в някоя от входните му позиции; когато преход се активира, ядрата от входните позиции на прехода преминават към изходните му позиции. Преминаването на ядра през прехода се извършва на една (неделима) стъпка.

Мрежите на Петри са подходящ инструмент за моделиране на паралелни процеси и на конкурентното поведение на разпределени системи.

Формално определение

Синтаксис

Граф на мрежата на Петри е тройката ${\displaystyle (S,T,W)\!}$, при която

• ${\displaystyle S}$ е крайно непразно множество от позиции,
• ${\displaystyle T}$ е крайно непразно множество от преходи,
• сечението на множествата ${\displaystyle S}$ и ${\displaystyle T}$ е празното множество, т.е. никой от обектите в графа не може да е едновременно и позиция, и преход.
• ${\displaystyle W:(S\times T)\cup (T\times S)\to \mathbb {N} }$ е мултимножество от насочени дъги, т.е. дефинира дъгите и им присвоява по едно неотрицателно цяло число .

Множеството от входните позиции на преход е ${\displaystyle {}^{\bullet }t=\{s\in S\mid W(s,t)>0\}}$; множеството от изходните позиции на преход е: ${\displaystyle t^{\bullet }=\{s\in S\mid W(t,s)>0\}}$

Маркировка на графа на мрежата на Петри е мултимножество от своите позиции, т.е. изображение от вида ${\displaystyle M:S\to \mathbb {N} }$. Казваме, че маркировката присвоява на всяка позиция определен брой ядра.

Мрежа на Петри е четворката ${\displaystyle (S,T,W,M_{0})\!}$, при която

• ${\displaystyle (S,T,W)}$ е графът на мрежата на Петри;
• ${\displaystyle M_{0}}$ е началната маркировка на графа.

Семантика на изпълнението

Поведението на една мрежа на Петри се дефинира като релация на нейните маркировки, по следния начин:

Маркировки могат да се добавят като към всяко мултимножество: ${\displaystyle M+M'\ {\stackrel {D}{=}}\ \{s\to M(s)+M'(s)\mid s\in S\}}$

Изпълнението на графа на мрежата на Петри ${\displaystyle G=(S,T,W)\!}$ може да се определи като релацията преход ${\displaystyle \to _{G}}$ между нейните маркировки по следния начин:

• за всяко ${\displaystyle t}$ от ${\displaystyle T}$: ${\displaystyle M\to _{G,t}M'\ {\stackrel {D}{\Leftrightarrow }}\ \exists M'':S\to \mathbb {N} :\forall s\in S,M(s)=M''(s)+W(s,t)\ \wedge M'(s)=M''(s)+W(t,s)}$
• ${\displaystyle M\to _{G}M'\ {\stackrel {D}{\Leftrightarrow }}\ \exists t\in T:M\to _{G,t}M'}$

С други думи,

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

Интересуваме се най-вече какво може да се случи когато преходите могат продължително време да се активират в произволен ред.

Казваме, че една маркировка ${\displaystyle M'}$ е достижима от маркировката ${\displaystyle M}$ на един такт ако ${\displaystyle M\to _{G}M'}$; казваче, че е достижима от ${\displaystyle M}$ ако ${\displaystyle M{\to _{G}}^{*}M'}$, където ${\displaystyle {\to _{G}}^{*}}$ е транзитивно затваряне на ${\displaystyle \to _{G}}$; т.е. ако е достижима за 0 или повече такта (стъпки).

За една (маркирана) мрежа на Петри ${\displaystyle (S,T,W,M_{0})\!}$, се интересуваме от активациите, които могат да настъпят при дадена начална маркировка ${\displaystyle M_{0}}$. Множеството от достижимите маркировки е множеството ${\displaystyle R(N)\ {\stackrel {D}{=}}\ \{M'\mid M_{0}{\to _{(S,T,W)}}^{*}M'\}}$

Графът на достижимостта на ${\displaystyle N}$ е релацията на прехода ${\displaystyle \to _{G}}$, ограничена върху своите достижими маркировки ${\displaystyle R(N)}$.

Последователността от активациите за една мрежа на Петри с граф ${\displaystyle G}$ и начална маркировка ${\displaystyle M_{0}}$ е последователността от преходи ${\displaystyle {\vec {\sigma }}=\langle t_{i_{1}}\ldots t_{i_{n}}\rangle }$, за която ${\displaystyle M_{0}\to _{G,t_{i_{1}}}M_{1}\wedge \ldots \wedge M_{n-1}\to _{G,t_{i_{n}}}M_{n}}$. Множеството от последователности на активациите се означава с ${\displaystyle L(N)}$.

Формулировка чрез вектори и матрици

Маркировките на една мрежа на Петри ${\displaystyle (S,T,W,M_{0})\!}$ могат да бъдат разгледани като вектори от неотрицателни цели числа с дължина ${\displaystyle |S|}$.

Релацията на прехода на мрежата може да се опише като двойка матрици с размери ${\displaystyle |S|}$ на ${\displaystyle |T|}$:

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

Тогава, тяхната разлика ${\displaystyle W^{T}=W^{+}-W^{-}}$ може да се използва за описание на достижимите маркировки в термините на умножението на матрици.

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

• ${\displaystyle R(N)=\{M\mid \exists w:M=M_{0}+W^{T}\cdot o(w)\wedge w\!}$ е последователността от активации на ${\displaystyle N\}\!}$.

За отбелязване е изискването, че ${\displaystyle w}$ е определена последователност от активации, понеже разрешаването на произволни последователности от преходи ще генерира по-голямо множество.

Пример за мрежа на Петри

${\displaystyle W^{+}={\begin{bmatrix}*&t1&t2\\p1&0&1\\p2&1&0\\p3&1&0\\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}}}$

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

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

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

Едно от нещата, които правят мрежите на Петри интересни за изследване е, че те предоставят интересен баланс между моделиращата сила и анализируемостта: много неща, които е желателно да се знаят за конкурентните системи могат автоматично да се определят за мрежите на Петри, въпреки че в общия случай някои от тези неща са много ресурсоемки („скъпи“) за определяне. Изучавани са няколко подкласа от мрежи на Петри, които продължават да могат да моделират интересни класове от конкурентни системи, докато проблемите, които възникват в процеса на работа, са по-прости.

Достижимост

Проблемът за достижимостта при мрежите на Петри е да се определи за дадена мрежа на Петри ${\displaystyle N}$ и маркировка ${\displaystyle M}$, дали ${\displaystyle M\in R(N)}$.

Очевидно, проблемът се свежда до обхождането на гореописания граф на достижимостта до момента, в който или се достигне желаната маркировка, или става ясно, че тя повече не може да бъде достигната. Тази задача е по-трудна, отколкото на пръв поглед изглежда: в общия случай графът на достижимостта е безкраен и не е лесно да се определи кога търсенето да спре.

През 1976 година е доказано, че този проблем е с експоненциална сложност^[1], пет години преди да е доказано, че той изобщо е разрешим (Mayr, 1981). Продължават да се публикуват статии, които дискутират как да се намери по-ефективно решение.^[2]

Въпреки че достижимостта изглежда добър инструмент за откриване на грешни състояния, конструираният граф обикновено има твърде много състояния, които трябва да се проверяват, за да е удачен за практически нужди. За да се разреши този проблем, обикновено се прибягва към линейна темпорална логика за доказване кои състояния са недостижими, като открива набора от необходими условия за достигане на дадено състоянието и после доказва, че тези условия не могат да бъдат удовлетворени.

Живост

На мрежите на Петри могат да се присвоят различни степени на „живост“ (liveness) ${\displaystyle L_{0}-L_{4}}$. Докато степените на живост се дефинират над преходите на мрежата, тя самата се смята за ${\displaystyle L_{k}}$ „жива“ тогава и само тогава, когато всеки преход в нея е ${\displaystyle L_{k}}$ жив.

Един преход ${\displaystyle t}$ на мрежа на Петри ${\displaystyle (N,M_{0})}$ е:

• ${\displaystyle L_{0}}$ не е жив, или с други думи „мъртъв“, тогава и само тогава, когато той не може да бъде активиран, т.е. не принадлежи на нито една серия от активации ${\displaystyle {\vec {\sigma }}}$, където ${\displaystyle {\vec {\sigma }}\in L(N,M_{0})}$,
• ${\displaystyle L_{1}}$ жив, тогава и само тогава, когато е възможно той да бъде активиран, понеже принадлежи на една серия от активации ${\displaystyle {\vec {\sigma }}}$, където ${\displaystyle {\vec {\sigma }}\in L(N,M_{0})}$,
• ${\displaystyle L_{2}}$ жив, тогава и само тогава, когато за произволно положително цяло число ${\displaystyle k}$, преходът ${\displaystyle t}$ може да се активира поне k пъти в една серия от активации ${\displaystyle {\vec {\sigma }}}$, където ${\displaystyle {\vec {\sigma }}\in L(N,M_{0})}$,
• ${\displaystyle L_{3}}$ жив, тогава и само тогава, когато съществува серия от активации ${\displaystyle {\vec {\sigma }}\in L(N,M_{0})}$ където преходът ${\displaystyle t}$ се активира неограничен брой пъти,
• ${\displaystyle L_{4}}$ жив, или с други думи „жив“, тогава и само тогава, когато във всяко достижимо състояние M (т.е. ${\displaystyle \forall M\in R(N,M_{0})}$), преходът ${\displaystyle t}$ е ${\displaystyle L_{1}}$ жив.

Трябва да се отбележи, че строгостта на тези изисквания нараства постъпково, и в този смисъл ако един преход е ${\displaystyle L_{3}}$ жив, то той автоматично е и ${\displaystyle L_{1}}$ жив и ${\displaystyle L_{2}}$ жив.

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

Граф на достижимостта на (a) мрежа на Петри. Пример ако мрежата е 2-ограничена. В този случай тя може да има най-много 9 (т.е. ${\displaystyle 3^{2}}$) състояния.

Една мрежа на Петри се нарича ${\displaystyle k}$-ограничена, ако в никое от нейните достижими състояния не могат по едно и също време в една позиция да се съдържат повече от ${\displaystyle k}$ ядра. Една мрежа на Петри се нарича сигурна, ако е 1-ограничена, т.е. е сигурно, че между ядрата в позицията няма да настъпят конфликти за ресурси и др. Началната маркировка ${\displaystyle M_{0}}$, естествено, също е ограничена. Една мрежа на Петри е ограничена тогава и само тогава, когато всичките ѝ графи на достижимостта (т.е. графите на достижимост с всички възможни начални състояния) вкупом притежават краен брой състояния.

Формално, ${\displaystyle K:S\to \mathbb {N^{+}} }$ е множеството от ограничения на капацитета, които присвояват на всяка позиция ${\displaystyle s\in S}$ някакво цяло положително число ${\displaystyle n\in \mathbb {N^{+}} }$, означаващо максималния брой ядра, които едновременно могат да се съдържат в позицията. В класическата мрежа на Петри са дефинирани само капацитети на позициите; едва в обобщената мрежа на Петри на Генрих и Лаутенбах (H. J. Genrich, K. Lautenbach) са въведени и капацитети на позициите.

Източници

1. Lipton, R. "The Reachability Problem Requires Exponential Space", Technical Report 62, Yale University, 1976]
2. P. Küngas. Petri Net Reachability Checking Is Polynomial with Optimal Abstraction Hierarchies Архив на оригинала от 2012-02-09 в Wayback Machine.. In: Proceedings of the 6th International Symposium on Abstraction, Reformulation and Approximation, SARA 2005, Airth Castle, Scotland, UK, July 26 – 29, 2005]

Тази страница частично или изцяло представлява превод на страницата Petri net в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​