14. Sieci Petriego.

Definicja i klasyfikacje sieci Petriego. Reprezentacje teoriomnogościowa,

graficzna i macierzowa. Modelowanie - przykłady zastosowań.

Formalizm teorii sieci Petriego umożliwia opis dynamiki systemów, których dominująca cecha jest występowanie wzajemnie warunkujących się operacji i procesów, tzn. na dynamiczny opis asynchronicznie zachodzących w systemie zdarzeń.

W rozważanej reprezentacji, z każdym ze zdarzeń związany jest zbiór warunków wejściowych (koniecznych dla jego zajścia), których spełnienie umożliwia jego zajście i w konsekwencji spełnienie zbioru warunków wyjściowych stanowiących warunki wejściowe dla zachodzenia kolejnych zdarzeń.

Sieć Petriego uporządkowana szóstka postaci: PN = (P,T,E,K,W,M_o)

P, T - niepuste, skończone, wzajemnie nie przecinające się zbiory

Odpowiednio pozycji (miejsc) i przejść (tranzycji).

E ⊂ (P × T) ∪ (T × P) - relacja incydencji

K :P → N - funkcja pojemność miejsc

W :E → N - funkcja krotności (pojemności) łuków

M₀ :P → N₀ - funkcja znakowania początkowego, spełniająca warunek:

∀p∈P : M₀(p) ≤ K(p)

N - zbiór licz naturalnych, N₀ = N ∪ {0}.

W reprezentacji graficznej PN odpowiada sieć, w której występują dwa typy wierzchołków: pogrubione kreski, odpowiadające przejściom, oraz okręgi, odpowiadające miejscom.

Elementy relacji incydencji są reprezentowane przez łuki oznaczone wartościami funkcji krotności W(x,y).

Znakowanie sieci jest reprezentowane za pomocą znaczników, gdzie z każdą współrzędna wektora M₀ = (M₀(p₁), M₀(p₂),..., M₀(p_n)) , n = ||P||, jest związany odpowiedni okrąg zawierający M₀(p_i) znaczników, ||P|| - moc zbioru P.

Do opisu dynamiki wykorzystywana jest funkcja przejścia postaci:

δ : N_o^K(p₁⁾ × N_o^K(p₂⁾ × ... × N_o^K(p_n⁾ ×T → N_o^K(p₁⁾ × N_o^K(p₂⁾ × ... × N_o^K(p_n⁾

gdzie: N_o^K(p_i⁾ = {0,1,2,...,K(p_i)}

określona dla par (M,t) ,M ∈ N_o^K(p₁⁾ × N_o^K(p₂⁾ × ... × N_o^K(p_n⁾ , t ∈ T

spełniających poniższe warunki przygotowania przejść:

gdzie: ^.t = {p | (p,t) ∈ E} - zbiór miejsc wejściowych przejścia t

t^. = {p | (t,p) ∈ E} - zbiór miejsc wyjściowych przejścia t

Uwaga

Funkcja przejścia δ umożliwia wyznaczanie stanu M' osiągalnego bezpośrednio ze stanu M dla t spełniającego warunki i) , ii).

W przypadku występowania przejść typu „źródło”, gdzie ^.t = ∅, oraz przejść typu „ujście”, gdzie t^. = ∅, warunki przygotowania przejść redukują się odpowiednio do warunku ii) oraz i).

Przykład

PN = (P,T,E,K,W,M_o) ,

P = {p₁,p₂,p₃,p₄,p₅) , T = {t₁}, E = {(p₁,t₁), (p₂,t₁), (p₃,t₁), (t₁,p₄), (t₁,p₅)} ,

K(p₁) = K(p₂) = K(p₄) = K(p₅) = 1 ; K(p₃) = 2 ,

W(p₁,t₁) = W(p₂,t₁) = W(t₁,p₄) = W(t₁,p₅) ; W(p₃,t₁) = 2

M₀ = (1,1,1,0,0) M₀ = (1,1,1,1,0) M₀ = (1,1,2,0,0)

Związek między stanem aktualnym M oraz bezpośrednio z niego osiągalnym stanem M' określa zależność

M(p) - W(p,t) jeżeli p ∈ ^.t

M'(p) = M(p) + W(t,p) jeżeli p ∈ t^.

M(p) w pozostałych przypadkach

Przykład

Reprezentacja algebraiczna PN = (C, K, W, M₀)

gdzie:

C - macierz incydencji o wymiarze (m × n) , m = ||T|| , n = ||P|| , o elementach

W(t_i,p_j) dla (t_i,p_j) ∈ E

c_ij = -W(p_j,t_i) dla (p_j,t_i) ∈ E

0 dla {(t_i,p_j)} ∪ {(p_j,t_i)} ⊄ E

Reprezentacja ta umożliwia wyznaczanie kolejnych oznakowań sieci, prowadzone w oparciu o proste działania algebraiczne:

M' = M + e[t]C

gdzie:

e[t] - wektor jednostkowy o wymiarze (1 × m), w którym wartości wszystkich współrzędnych oprócz jednej są równe zeru, a współrzędnej o wartości 1 odpowiada indeks przejścia aktualnie przygotowanego w stanie M

Przykład

p₁ p₂

t₁ 1 0

C = t₂ -2 2

t₃ 0 -4

1 0

M = M₀ + e[t₁]C = (0,0) + (1,0,0) -2 2 = (1,0)

0 -4

1 0

M' = M + e[t₁]C = (1,0) + (1,0,0) -2 2 = (2,0)

0 -4

1 0

M“ = M' + e[t₂]C = (2,0) + (0,1,0) -2 2 = (0,2)

0 -4

1 0

M“' = M“ + e[t₁]C = (0,2) + (1,0,0) -2 2 = (1,2)

0 -4

Przykład

Modelowanie

IF p₁ & p₂ & p₃ THEN p₄ & p₅

Przykład

Klasy sieci Petriego

Zwykła sieć Petriego (sieć markowana)

PN = (P,T,E,K,W,M_o)

i) ∀p∈P, K(p) = ∝

ii) ∀(x,y)∈E, W(x,y)= 1

Podklasy zwykłych sieci Petriego

Maszyna stanowa

Zwykła sieć Petriego, dla której spełniony jest warunek:

i) ∀t∈T, ||^.t|| = ||t^.|| = 1

Przykład

Graf znakowany

Zwykła sieć Petriego, dla której spełniony jest warunek:

i) ∀p∈P, ||^.p|| = ||p^.|| = 1

Przykład

Rozszerzenia zwykłych sieci Petriego

Sieci ze wzbronieniami

Sieci kolorowane

Sieci czasowe

Sieci rozmyte

...

15. Sieci Petriego.

Analiza właściwości - żywotność strukturalna i funkcjonalna. Zjawiska blokady i konfuzji. Niezmienniki. Programy użytkowe.

Właściwości

Żywotność

Sieć PN = (P,T,E,K,W,M_o) należy do klasy sieci żywych wtedy i tylko wtedy gdy:

∀t∈T ∀M∈R(PN,M₀) ∃M' ∈ R(PN,M) : t jest przygotowane dla M'

gdzie:

R(PN,M₀) - zbiór znakowań osiagalnych ze znakowania M₀ w sieci PN

R(PN,M) - zbiór znakowań osiagalnych ze znakowania M w sieci PN

Uwaga

Właściwości żywotności przypisana jest tym sieciom, w których dla każdego znakowania M osiągalnego ze znakowania początkowego M₀ oraz dla każdego przejścia t istnieje znakowanie M', osiągalne ze znakowania M, dla którego przejście to jest przygotowane

Przykład

Sieć żywa strukturalnie Sieć żywa funkcjonalnie

Uwaga

Sieci żywe są sieciami bezblokadowymi tzn. sieciami, w których dla każdego znakowania istnieje przejście przygotowane oraz istnieje sekwencja paleń przeprowadzająca to znakowanie w znakowanie początkowe

p₄

p₅

p₁

p₂

p₃

t₁

2

p₄

p₅

p₁

p₂

p₃

t₁

p₄

p₅

p₄

p₅

p₁

p₂

p₃

t₁

2

p₁

p₂

p₃

t₁

p₄

p₅

p₁

p₂

p₃

t₁

2

p₄

p₅

p₁

p₂

p₃

t₁

2

p₄

p₅

p₁

p₂

p₃

t₁

2

1 2 2 4

t₁ p₁ t₂ p₂ t₃

t₁ p₁ t₂ p₂ t₃

1 2 2 4

t₁ p₁ t₂ p₂ t₃

1 2 2 4

t₁ p₁ t₂ p₂ t₃

1 2 2 4

t₁ p₁ t₂ p₂ t₃

1 2 2 4

t₁ p₁ t₂ p₂ t₃

1 2 2 4

1 2 2 4

t₁ p₁ t₂ p₂ t₃

1 2 2 4

t₁ p₁ t₂ p₂ t₃

t₁ p₁ t₂ p₂ t₃

1 2 2 4

1 2 2 4

t₁ p₁ t₂ p₂ t₃

p₄

p₅

p₁

p₂

p₃

t₁

2

t₁ p₁ t₂ p₂ t₃

t₁ p₁ t₂ p₂ t₃

1 2 2 4

t

t₁ p₁ t₂ p₂ t₃

t₁ p₁ t₂ p₂ t₃

t₁ p'₁ t₄ p“₁ t₂ p₂ t₃

t₁ p₁ t₂ p₂ t₃

1 2 2 4

t₁ p₁ t₂ p₂ t₃

1 2 2 4

M

P

O

T

R

t₁ p₁ t₂ p₂ t₃ p_3­ t₄ p₄ t₅ p₅ t₆

p₈

p₇

p₈

t'₁ t'₂ t'_{3 ­} t'₄ t'₅ t'₆