Petri ağı

Bir petri ağı (yer/geçiş ağı, yerleşim/geçiş ağı veya Y/G ağı olarak da bilinir) sistemlerin incelenmesi için kullanılabilecek bir araçtır. Petri ağları, sistemin matematiksel bir modelle modellenebilmesine izin verir. Bir Petri ağı, geçiş ve yerleşim düğümlerinden oluşan tek yönlü iki parçalı graf olarak da tanımlanabilir. Ok şeklinde gösterilen yönlü eğriler, bir geçişten önce ve sonra hangi yerlerin olduğunu tanımlarlar.

Bazı kaynaklar Petri ağlarının 1939 Ağustos'unda, henüz 13 yaşında olan Carl Adam Petri tarafından, kimyasal prosesleri tarif etmek amacıyla bulunduğunu belirtirler.

Petri ağları, UML, BPMN ve EPC gibi endüstri standartlarına benzer şekilde seçim, tekrarlama, eşzamanlı çalışma gerektiren adımlı prosesler için bir grafiksel notasyon sunar. Ancak bu standartların ötesinde, proses analizi için geliştirilmiş matematiksel teorisiyle ilgili proseslerin çalışmasını matematiksel bir kesinlikte modelleyebilir.

(a) Petri ağ yörüngesi örneği

Petri ağ temelleri

Bir petri ağı yerler, geçişler ve eğrilerden oluşur. Yerler ve geçişler, graf teorisindeki düğümler ve kenarlar ile eşdeğerdir. Eğriler bir yerden bir geçişe veya bir geçişten bir yere doğru koşarlar. İki yer arasında veya iki geçiş arasında bir eğri olamaz. Geçişe giriş yapan eğri hangi yerden çıkış yaptıysa, bu yere geçişin giriş yeri; Geçişten çıkış yapan eğri hangi yere giriş yaptıysa, bu yere geçişin çıkış yeri denir.

Grafiksel olarak bir Petri ağındaki bir yer ayrık sayıdaki işaretler içerebilir. Bu işaretler jeton olarak adlandırılır. Jetonların herhangi bir anda yerler üzerindeki dağılımı işaretleme, jeton dağılımı veya konfigürasyon olarak adlandırılır.

Bir geçişin giriş yerlerinde yeterli jeton var ise, bu geçiş etkinleştirilmiş veya tetiklenebilir denir.

Etkinleştirilmiş bir diğer ifade ile, tetiklenebilir bir geçiş tetiklendiğinde, giriş yerlerinden ihtiyaç duyulan miktarda jeton tüketir ve çıkış yerlerinde üretilmesi gereken miktarda jeton üretilir. Bu 'gereken' miktarlar, ilgili geçişin ağırlığı, ayrık sistemler için özelleştirirsek geçişin üzerinde yazan rakam, ile gösterilir.

Tetikleme anlıktır. Tek seferde gerçekleşir ve yarıda bırakılamaz.

Bir çalışma kuralı tanımlanmadığı sürece, Petri ağlarının çalışması deterministik değildir. Aynı anda birden fazla geçiş tetiklendiğinde, hangisinin tetikleneceği bilinemez ya da bir başka deyişle, geçişlerin herhangi birisi tetiklenebilir.

Tetikleme deterministik olmadığından ve ağda herhangi bir yerde birden fazla sayıda jeton bulunabileceğinden, Petri ağları dağıtılmış sistemlerin eşzamanlı davranışını modellemek için uygundur.

Resmi tanım ve temel terminoloji

Petri ağları basit ağ olarak adlandırılan ağların kapsamını genişleten durum-geçiş sistemleridir.

Tanım 1. Bir $N=(P,T,F)$ ağı üç parametrelidir, öyle ki:

1. $P$ ve $T$ sırasıyla yerlerin ve geçişlerin ayrık sonlu kümeleridir.
2. $F\subset (P\times T)\cup (T\times P)$ ya da akış ilişkilerinin(graflardaki eğrilerin) bir kümesidir.

Tanım 2. Verilen bir N = (P, T, F ) ağındaki bir konfigürasyon C kümesiyle gösterilir, öyle ki  C ⊆ P.

Aktifleştirilmiş bir geçişe sahip bir Petri ağı

Geçiş tetiklendikten Petri ağının durumu. (geçiş tetiklenmeden önceki hali yukarıda)

Tanım 3. Bir basit ağ EN = (N, C ) formundaki ağdır, öyle ki:

1. N = (P, T, F ) bir ağdır.
2. C, C ⊆ P olan bir konfigürasyondur.

Tanım 4. Bir Petri ağı, PN = (N, M, W ) formundaki ağdır ve basit ağın kapsamını genişletir, öyle ki:

1. N = (P, T, F ) bir ağdır.
2. M : P → Z Z'nin sayılabilir küme olduğu bir yerler çoklu kümesidir. M(not:marking), konfigürasyon konseptini genişletir ve Petri ağlarında genellikle işaretleme(jeton dağılımı) olarak tanımlanır.
3. W : F → Z bir eğri çoklu kümesidir. Öyle ki, W(not: weight) her eğrinin üzerindeki sayı(yahut eğrinin ağırlığı) eğri katsayısının/çarpanının bir ölçüsüdür.

Eğer bir Petri ağı, basit ağa eş ise, Z {0,1} sayılabilir kümesi olabilir ve P 'deki M'nin altındaki 1'e karşılık gelen elemanlar, bir konfigürasyon oluşturur. (not: özetle her yerde en fazla 1 jeton bulunur). Benzer olarak, eğer bir Petri ağı, bir basit ağ değilse, M çoklu küme konfigürasyonların bir alt kümesi olarak ifade edilebilir. (not: özetle basit bir ağda her yer sadece tek bir jeton içerebilirken, Petri ağında böyle bir kısıtlama bulunmamaktadır.)

Bir Petri ağı diyagramında yerler genellikle çember işareti ile, geçişler ise uzunca ve dar dikdörtgenler tarafından, eğriler yerlerden geçişlere yahut geçişlerden yerlere bağlantıları gösteren tek yönlü oklar tarafından modellenir.

Eğer diyagram basit bir ağa ait olsaydı, yerler yine çemberler tarafından gösterilecekti. Ancak bu defa, her bir çember bir jeton içerebilecekti. Yukarıda sağda gözüken Petri ağı ise birden fazla jeton içermektedir. Tüm Petri ağına dağıtılmış jeton konfigürasyonuna, işaretleme adı verilir.

Yukarıda sağdaki resimde, p₁ yeri, t geçişinin giriş yeridir; p₂ yeri ise aynı geçişin çıkış yeridir. Üst resimde bulunan PN₀ Petri ağı, M₀ işaretlemesi ile alt resimde bulunan PN₁ ağı ise M₁ işaretlemesi ile konfigüre edilmiş(yahut işaretlenmiş) olsun. PN₀'ın konfigürasyonu, tüm giriş yerleri yeteri kadar sayıda jeton (resimlerde noktalar olarak gösteriliyor) içerdiği için t geçişini etkinleştirir. bir yerin "yeteri kadar jeton" içermesi demek, o yerden geçişe giden eğrinin ağırlığına eşit veya daha fazla sayıda jetona sahip olması demektir. Bir geçiş, sadece ve sadece etkinleştirilmiş ise, tetiklenebilir. Bu örnekte, t 'nin tetiklenmesi(ateşlenmesi) M_0' konfigürasyonundan M₁ konfigürasyonuna bir geçiş yapılmasını sağlar ve PN₁ Petri ağına ulaşılması ile sonuçlanır (sağ üstte, alttaki resim).

Hatırlatma 1. "büyük veya eşittir" tabirinin kesin anlamı, tetikleme kuralındaki toplama işleminin cebirsel kesinliğine bağlıdır. Cebirsel özelliklerdeki farklı varyasyonlar bizi farklı Petri ağı sınıflarına götürebilir. Örneğin: Cebirsel Petri Ağları.

Sıradaki resmi tanım, (Peterson 1981)'in tanımıdır. Birçok alternatif tanım da mevcuttur.

Sentaks

Bir Petri ağı grafı(bazıları tarafından Petri ağı olarak da söylenir ancak aşağıya bakın) $(S,T,W)\!$ olarak ifade edilecek şekilde, üç elemanlıdır(tuple). Öyle ki:

• S yerlerin sonlu kümesidir.
• T geçişlerin sonlu kümesidir.
• S ve T ayrıktır. herhangi bir nesne, hem bir geçişte hem de bir yer olamaz.(bir nesne ya geçiştir ya yerdir).
• $W:(S\times T)\cup (T\times S)\to \mathbb {N}$ eğriler multisetidir.. Her bir eğriye, negatif olmayan bir tam sayı(Eğri ağırlığı) ataması yapar.

Akış ilişkisi eğrilerin bir kümesidir: $F=\{(x,y)\mid W(x,y)>0\}$. Birçok kitap, eğrilerin ağırlığının yalnızca 1 olabileceğini yazar. Bu yazılar genellikle Petri ağlarını W yerine F' ile tanımlarlar. Bu yaklaşım kullanıldığında, bir Petri ağı iki parçalı multigraf $(S\cup T,F)$ haline dönüşür.

Bir geçişin girdi kümesi(preset) t, o geçişe ait giriş yerlerinin kümesidir: ${}^{\bullet }t=\{s\in S\mid W(s,t)>0\}$; Geçişin çıktı kümesi(postset) geçişe ait çıkış yerlerinin kümesidir: $t^{\bullet }=\{s\in S\mid W(t,s)>0\}$. yerlerin girdi çıktı kümelerinin tanımları benzerdir (analoji).

Bir Petri ağının(grafının) işaretlemesi onun yerlerinin bir multisetidir.Yeni, $M:S\to \mathbb {N}$. adreslemesi için, işaretleme her yere belirli sayılarda jeton ataması yapar deriz. .

A Petri ağı (bazıları tarafından işaretli Petri ağı olarak da adlandırılır - yukarıya bakın) 4 elemanlı bir kümedir. $(S,T,W,M_{0})\!$, Öyle ki:

• $(S,T,W)$ bir petri ağıdır.
• $M_{0}$ (Petri ağına ait bir işaretleme olan) ilk işaretlemedir.

Çalışma mantığı

Kelimelerle ifade edersek:

• M işaretlemesindeki(konfigürasyonundaki) t geçişinin ateşlenmesi, geçişin giriş yerlerinden(s) $W(s,t)$ adet jetonun tüketilmesine, ve geçişin çıkış yerlerinde(s) $W(t,s)$ adet jetonun üretilmesine sebep olur.
• M işaretlemesindeki(konfigürasyonundaki) bir geçiş için, sadece ve sadece $\forall s:M(s)\geq W(s,t)$ koşulu sağlanıyorsa, yani geçişin giriş yerlerinde tüketim için yeterli jeton varsa geçiş etkinleştirilmiştir (tetiklenebilir/ateşlenebilir).

Bizler, genellikle tetiklerin rastgele zamanlarda tetiklendiği durumlarda neler olabileceği ile ilgileniriz.

Bir adımda ulaşılabilirlik

Eğer $M\to _{G}M'$ ise, M işaretlemesinden bir adımda $M'$ işaretlemesine ulaşılabilir deriz. (Ya da $M'$ , M'den bir adımda ulaşılabilirdir)

Ulaşılabilirlik

${\to _{G}}^{*}$ 'nin $\to _{G}$'nin reflexive transitive closure'u olduğu durumlarda ; $M{\to _{G}}^{*}M'$ ise, herhangi bir adım sayısında ulaşılabiliyorsa, $M'$ , M 'den ulaşılabilirdir deriz.

$N=(S,T,W,M_{0})\!$, işaretli bir Petri ağı olmak üzere, $M_{0}$ ilk işaretlemesinden itibaren gerçekleştirilebilecek tetiklemelerle ilgileniriz. Bu, ulaşılabiir işaretlemeler kümesidir ve $R(N)\ {\stackrel {D}{=}}\ \{M'\mid M_{0}{\to _{(S,T,W)}}^{*}M'\}$şeklinde gösterilir.

Ulaşılabilirlik grafı

N'nin ulaşılabilirlik grafı , onun ulaşılabilir işaretlemeleri$R(N)$ ile sınırlanmış geçiş ilişkileridir $\to _{G}$ . Bu, ağın durum uzayıdır. (özetle, ağın alabileceği tüm durumları gösteren kümedir)

G grafına ve' $M_{0}$ 'ilk durumuna sahip bir Petri ağındaki ateşleme sekansı (ya da sıralı ateşleme kümesi)' ${\vec {\sigma }}=\langle t_{i_{1}}\ldots t_{i_{n}}\rangle$ 'ile gösterilir. Öyle ki;'$M_{0}\to _{G,t_{i_{1}}}M_{1}\wedge \ldots \wedge M_{n-1}\to _{G,t_{i_{n}}}M_{n}$. Burada tetikleme sekanslarının kümesi $L(N)$ ile gösterilmiştir.

Tanımlardaki farklılıklar

Daha önce de belirtildiği gibi, tanım farklılıklarının en genel olanı, eğri ağırlıklarını göz ardı etmek ve W ile gösterilen eğriler multisetini, $F\subseteq (S\times T)\cup (T\times S)$ ile gösterilen ve akış ilişkisi olarak adlandırılan bir basit küme ile değiştirmektir. Bu ifade gücünü (expressive power) sınırlandırmaz, her ikisi de birbirleri yerine kullanılabilir.

Genel olarak kullanılan bir diğer farklılık da, Desel ve Juhás (2001)'ın da kullandığı üzere, kapasitelerin yerler üzerinde tanımlanmış olmasına izin verilmesidir. Aşağıda ekler bölümünde bu konu tartışılmıştır.

Vektör ve matris şeklinde formulasyon - vektörleştirme

Bir Petri ağına ilişkin işaretlemeler(jeton dağılımları) $(S,T,W,M_{0})\!$, negatif olmayan tam sayıların $|S|$ boyutlu vektörleri olarak ifade edilebilir.

Vektörün geçiş ilişkisi, $|S|$ * $|T|$ boyutundaki bir çift matrisle gösterilebilir:

• $W^{-}$, öyle ki $\forall s,t:W^{-}[s,t]=W(s,t)$
• $W^{+}$, öyle ki $\forall s,t:W^{+}[s,t]=W(t,s).$

Ardından farkları olan

• $W^{T}=W^{+}-W^{-}$

ifadesi, ulaşılabilir jeton dağılımlarını matris çarpımı şeklinde göstermek için aşağıdaki şekilde kullanılabilir.

Herhangi bir w ateşleme(geçiş/tetikleme) sekansı için, her geçişe kendi ağırlığını w atayan bir $o(w)$ yazalım. Bu durumda

• $R(N)=\{M\mid \exists w:M=M_{0}+W^{T}\cdot o(w)\wedge w\!$, $N$'ye ait bir ateşleme sekansı'dır.$\}\!$.

w'nin bir ateşleme sekansı olması gerektiğine dikkat edin; geçişlerin rastgele tetiklenmesine izin vermek, genellikle daha büyük bir küme oluşturur.

(b) Örnek bir Petri ağı

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

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

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

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