2012-12-15
Carl Adam Petri (1926-2010)
Kommunikation mit Automaten –
praca doktorska (1962)
Najkrótsza droga
Maksymalny przepływ
Najtańszy przepływ
Analiza czynności (zdarzeń)
…
Elementy sieci Petriego
Problemy
statyczne
Zbiór wierzchołków grafu
opisujących możliwe stany
badanego systemu (sytuacje,
warunki logiczne)
Oznaczane graficznie elipsą
(okręgiem)
opis procesów współbieżnych za
pomocą notacji graficznej
metoda modelowania pozwalającą na
przedstawianie i analizowanie
procesów przebiegających równolegle
Zbiór wierzchołków grafu
opisujących zdarzenia, które
modyfikują stany badanego
systemu
Oznaczane graficznie
prostokątami
1
2012-12-15
Elementy grafu opisujące relacje pomiędzy
stanami badanego systemu a zdarzeniami:
◦ wskazują stany, w których zdarzenie może zajść
(warunki konieczne)
◦ wskazują stany, w których zdarzenie nie może
zajść (blokady)
◦ wskazują zmianę stanu powodowaną przez
zdarzenie
Oznaczane graficznie liniami zakończonymi
strzałkami (kółkami)
Graf jest dwudzielny, tzn. łuki łączą
wierzchołki różnych typów
Łuki są skierowane
Łuki mogą być wielokrotne (mogą mieć
przypisane wagi)
Tranzycje mogą być wykonywane natychmiast
lub z pewnym opóźnieniem
Łuki są trzech typów: wejściowe do tranzycji,
wyjściowe z tranzycji, inhibitory tranzycji
Mogą występować pętle
Nierozróżnialne znaczniki występujące w
miejscach, używane są do rozróżniania
stanów sieci Petriego (znakowanie sieci)
Dla miejsc opisujących warunki występowanie
znacznika oznacza, że warunek jest spełniony
(prawda), brak znacznika – warunek nie jest
spełniony (fałsz)
Dla miejsc opisujących sytuacje liczba
znaczników określa rodzaj sytuacji
Pozwalają opisać dynamikę systemu
Znakowanie początkowe, znakowania
pośrednie i końcowe
Reguły określające dynamikę sieci (reguły
zmiany znakowania)
Ta sama sieć z różnymi znakowaniami
początkowymi opisuje różne systemy
2
2012-12-15
Tranzycję t nazywamy aktywną przy oznakowaniu M gdy:
• wszystkie miejsca wejściowe tranzycji zawierają odpowiednią
liczbę znaczników,
• wszystkie inhibitory tranzycji nie zawierają znaczników.
Odpalenie tranzycji t, aktywnej przy oznakowaniu M, powoduje:
• usunięcie znaczników z każdego miejsca wejściowego,
• dodanie znaczników do wszystkich miejsc wyjściowych.
to znaczy powoduje zmianę oznakowania na
〉 ′.
jest zapisywana skrótowo
′.
Zależność ta
3
2012-12-15
Przykłady z różnych gałęzi
transportu
i tak dalej … w nieskończoność
4
2012-12-15
Sieć jest nazywana żywą, jeśli wszystkie jej
tranzycje są żywe
Tranzycja t jest żywa, jeśli dla każdego
znakowania M (osiągalnego ze znakowania
początkowego) istnieje takie znakowanie M’,
w którym tranzycja t jest aktywna
Tranzycja, która nie jest żywa – jest martwa
Znakowanie martwe – takie znakowanie, w
którym żadna tranzycja nie jest aktywna
Sieć Petriego nazywamy k-ograniczoną, jeśli
dla każdego osiągalnego znakowania, liczba
znaczników w dowolnym miejscu sieci jest
mniejsza niż k.
Sieć Petriego, która jest 1-ograniczona
nazywa się siecią bezpieczną
Znakowanie M’ nazywamy osiągalnym z M,
jeśli istnieje dowolny ciąg tranzycji, których
odpalenie powoduje przejście ze znakowania
M do znakowania M’
Analiza osiągalności jest kluczowa przy
rozważaniu systemów transportowych –
pozwala np. znaleźć stany niebezpieczne,
ocenić prawdopodobieństwo wypadku itp.
Pułapka – zbiór miejsc, które nigdy nie stracą
znaczników.
Zatrzask (blokada) – zbiór miejsc, który po
utracie wszystkich znaczników nie będzie
nigdy znakowany ponownie
Sieć Petriego nazywamy odwracalną, jeśli dla
dowolnego znakowania M (osiągalnego ze
znakowania początkowego M0) istnieje
sekwencja tranzycji, których odpalenie
powoduje przejście do znakowania
początkowego M0.
pułapka
zatrzask
5
2012-12-15
Uogólniona sieć Petriego jest opisana piątką
=
Znakowana sieć Petriego jest opisany szóstką
, , , ,
=
gdzie:
P – zbiór miejsc,
=
∩
T – zbiór tranzycji,
= ∅,
−
=
∈ :
,
t ∈T
, można zdefiniować:
=
∈ :
,
> 0 – zbiór wyjść tranzycji t,
=
∈ :
,
> 0 – zbiór inhibitorów tranzycji t.
=
, , , ,
, !,
0
gdzie
=
, , , ,
- uogólniona sieć Petriego,
!: → ℕ ∪ ∞ – pojemność miejsc sieci , przy czym symbol ∞ oznacza,
że miejsce ma nieograniczoną pojemność,
0:
→ ℤ+ % ∀ ∈ :
0
≤!
– znakowanie początkowe.
=
gdzie
, , , , ,
=
, , , ,
- uogólniona sieć Petriego,
→ ℤ+ – jest znakowaniem początkowym, tzn. funkcją przypisującą
każdemu z miejsc liczbę całkowitą nieujemną. Mówimy również, że
znakowanie określa liczbę znaczników przypisanych każdemu z miejsc.
> 0 – zbiór wejść tranzycji t,
Realizacja tranzycji nie jest natychmiastowa, lecz zajmuje określony czas.
Sieć miejsc i przejść jest to uogólniona, znakowana sieć Petriego,
uzupełniona o charakterystykę miejsc interpretowaną jako ich pojemność, to
znaczy maksymalną liczbę znaczników jakie może pomieścić każde z miejsc.
0
0:
I, O, H, to funkcje odpowiednio wejścia, wyjścia oraz inhibitory:
Mając daną tranzycję
+
, , , , ,
gdzie
0, (
, , , , ,
0
– znakowana sieć Petriego,
•
•
•
•
Znaczniki różnych typów.
Typ znacznika nazywany jest kolorem.
Każde miejsce ma przypisany zbiór kolorów, które może przechowywać.
Łuki i przejścia mają przypisane wyrażenia, które pozwalają na
manipulowanie różnymi typami znaczników.
+
= Γ, , , , , , +, -, .,
0
(: → ℝ+ – funkcja opóźnień, określająca opóźnienie statyczne τ(t)
tranzycji t.
gdzie
Czas związany z realizacją tranzycji:
Г – niepusty, skończony zbiór kolorów,
• deterministyczny
• opisany zmienną losową o zadanym rozkładzie prawdopodobieństwa.
Opóźnienie dynamiczne δ(t) - reszta czasu pozostałego do odpalenia
tranzycji t.
=
, , , , ,
0
– znakowana sieć Petriego,
C – funkcja określająca jakiego koloru
przechowywane w danym miejscu: +: → Γ,
znaczniki
mogą
być
G – funkcja określająca warunki, jakie muszą być spełnione, aby tranzycja
mogła być odpalona;
E – funkcja opisująca tzw. wagi łuków,
6
Download

Dr ZDZISŁAW JAN ZASADA – urodził się w Gołaszewie, gmina